Cops and robbers for hyperbolic and virtually free groups Raphael Appenzeller and Kevin Klinge Abstract . Lee, Martínez-Pedroza and Rodríguez-Quinche define two new group invariants, the strong cop number sCop \operatorname{sCop} and the weak cop number wCop \operatorname{wCop} , by examining winning strategies for certain combinatorial games played on Cayley graphs of finitely generated groups. We show that a finitely generated group G G is Gromov-hyperbolic if and only if sCop ⁡ ( G ) = 1 \operatorname{sCop}(G)=1 . We show that G G is virtually free if and only if wCop ⁡ ( G ) = 1 \operatorname{wCop}(G)=1 , answering a question by Cornect and Martínez-Pedroza. We show that sCop ⁡ ( ℤ 2 ) = ∞ \operatorname{sCop}(\mathbb{Z}^{2})=\infty , answering a question from the original paper. It is still unknown whether there exist finite cop numbers not equal to 1, but we show that this is not possible for CAT(0)-groups. We provide machinery to explicitly compute strong cop numbers and give examples by applying it to certain lamplighter groups, the solvable Baumslag-Solitar groups, Grigorchuk’s group and Thompson’s group F F . 1991 Mathematics Subject Classification 20F67, 05C57, 51F30. 1. Introduction Cops and Robbers is a class of combinatorial two-player games that are usually played on graphs or more generally, on metric spaces. Lee, Martínez-Pedroza and Rodríguez-Quinche [ 12 ] introduced a version where the existence of a winning strategy for either player is invariant under quasi-isometries, making the game interesting from a geometric group theory perspective. The game depends on a parameter called the number of cops . The cop number of a graph is the smallest number of cops such that there exists a strategy for the cop player where they always win. The cop number of a finitely generated group is the cop number of one of its Cayley graphs. In this work, we characterize the cop numbers in terms of well-known geometric invariants and resolve some open questions in the literature. There are two versions of the game: the strong cop game and the weak cop game, yielding two notions of cop numbers, which are known to be different in general. Hyperbolic groups are known to have strong cop number 1 [ 12 , Theorem A] . We show that the converse also holds. Thus the strong cop number provides a new characterization of hyperbolic groups. Theorem A ( Theorem 3.4 ) . A finitely generated group G is Gromov-hyperbolic if and only if its strong cop number is 1 . We provide a similar characterization for the weak cop number. As the strong cop number is at most equal to the weak cop number, we know that the weak cop number can be 1 only for hyperbolic groups. However, [ 12 , Corollary J] states that one-ended hyperbolic groups have infinite weak cop number. We prove the following theorem that was first conjectured in [ 7 , Question 1.4] . Theorem B ( Theorem 3.5 ) . A finitely generated group G is virtually free if and only if its weak cop number is 1 . The weak cop numbers of some non-hyperbolic groups have been calculated. We upgrade some of these results to the strong cop numbers. The weak cop number of \mathbb{Z}^{2} is \infty [ 12 , Theorem C] , but the value of the strong cop number of \mathbb{Z}^{2} was left as an open question [ 12 , Question D] , which we resolve. Theorem C ( Theorem 4.1 ) . For any n\geqslant 2 , \mathbb{Z}^{n} has infinite strong cop number. By [ 12 , Theorem E] , groups that retract to \mathbb{Z}^{2} , such as Thompson’s group F , therefore also have strong cop number \infty . Another consequence of Theorem C is the following. Theorem D (Therems 5.9 and 5.10 ) . For finitely generated infinite groups G , G\times G has infinite strong cop number. Grigorchuk’s group and all other finitely generated branch groups have infinite strong cop number. Cornect and Martínez-Pedroza show that the weak cop number of lamplighter groups is \infty [ 7 , Theorem 1.5] . When the lamp group L is finite, we strengthen this result for the strong cop numbers. Theorem E ( Theorem 5.3 ) . Let L be a non-trivial finite group. Then the lamplighter group L\wr\mathbb{Z} has infinite strong cop number. Furthermore, we find the cop numbers of the solvable Baumslag-Solitar groups. Theorem F ( Theorem 5.6 ) . The solvable Baumslag-Solitar groups \operatorname{BS}(1,n) have infinite strong cop number. An important concept in the proof of Theorems A , C , E and F is what we call a meta-stage : where a stage consists of the cop player taking a move followed by the robber player taking a move, a meta-stage consists of multiple moves for both players. These moves have to be taken alternately as per the rules of the game. But by choosing them carefully, we can pretend that first one player takes all their moves within a single meta-stage and then the other player gets their moves, without providing a game-changing advantage to either player. From this point of view, results about the weak cop game can often be upgraded to the strong cop game. The existence of a homothety is one condition that enables such an upgrade. We call this strategy meta-gaming. Theorem G (Meta-gaming theorem, for details see Theorem 4.5 and Corollary 4.6 ) . If there is a sequence of quasi-surjective quasi-homotheties from a graph \Delta to a graph \Gamma , then the strong cop number of \Gamma is equal to the weak cop number of \Delta . Figure 1. An overview of known results for the strong and weak cop numbers. The existence of groups with combinations of cop numbers marked with ? is an open question. The marking ?^{\star} indicates that no group is known, but graphs are known. In fact, Theorems C and E are obtained from the meta-gaming theorem. On the other hand, when the weak and the strong cop numbers of a group are not equal, the meta-gaming theorem implies that homotheties cannot exist. By Theorems A and B , examples of such groups are hyperbolic groups that are not virtually free. The following are consequences for such groups and spaces that do not involve cop numbers. While the statements may be well known to experts, they serve as a proof of concept that the cop numbers can have broader applications. Corollary H ( Corollary 5.4 ) . If \Gamma is the Cayley graph of a finitely generated hyperbolic group that is not virtually free, then there does not exist a sequence of quasi-surjective homotheties. Corollary I ( Corollary 5.5 ) . The hyperbolic plane \mathbb{H}^{2} does not admit a surjective homothety h\colon\mathbb{H}^{2}\to\mathbb{H}^{2} . The main remaining open question is whether there exist groups with intermediate cop numbers. Question K ( [ 12 ] , Question K) . Are there any finitely generated groups with weak and/or strong cop numbers not equal to 1 or \infty ? If the answer to Question K is positive, then the cop numbers could become a valuable tool in geometric group theory since they would serve as close generalizations of being hyperbolic and/or being virtually free. If the answer is negative, Theorems A and B fully classify the cop numbers in terms of known invariants. In the special case of CAT(0)-groups we show that there are no intermediate strong cop numbers. Proposition J (Proposition 6.1 ) . If G is a CAT(0)-group, then \operatorname{sCop}(G)\in\{1,\infty\} . Figure 1 gives an overview of the results proven here. Outline. We start by defining the cop numbers and recalling some results about them in Section 2 . In Section 3 we prove the characterizations of hyperbolic and virtually free groups in terms of their cop numbers, Theorems A and B . Section 4 is dedicated to metagaming with homotheties. We start by showing that \operatorname{sCop}(\mathbb{Z}^{2})=\infty ( Theorem C ) before generalizing the argument to the meta-gaming theorem ( Theorem G ). In Section 5 , we collect the results about non-existence of homotheties (Corollaries 5.4 , 5.5 ), Lamplighter groups ( Theorem E ), solvable Baumslag-Solitar groups ( Theorem F ), Grigorchuk’s group (Theorem D ) and Thompson’s group F . In Section 6 we argue that CAT(0)-groups do not admit intermediate cop numbers. Acknowledgements. We would like to thank Francesco Fournier-Facio and Luca de Rosa, with whom we played many rounds of Cops and Robbers and had many fruitful discussions. For discussions about hyperbolicity and related questions, we would also like to thank Tommaso Goldhirsch, Hjalti Isleifson, Alexander Lytchak, Bianca Marchionna, José Pedro Quintanilha and Claudio Llosa Isenrich. We are thankful for a detailed report by an anonymous referee. The authors were partially supported by RTG 2229 “Asymptotic Invariants and Limits of Groups and Spaces” funded by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation). During the publication process of this paper, some of our results were independently obtained by [ 9 ] using different methods. There has also been partial progress on Question K : [ 13 ] shows that there are no intermediate weak cop numbers. 2. The weak and the strong cop numbers We start by recalling the definition of the cops and robbers game by Lee, Martínez-Pedroza, Rodríguez-Quinche [ 12 ] . The two-player game with perfect information is defined on a connected undirected graph \Gamma without double edges and loops. Apart from the graph itself, the game depends on six parameters: (1) the number of cops n\in\mathbb{N}\coloneq\mathbb{Z}_{\geqslant 1} , (2) v the treasure or base point : a vertex in \Gamma , (3) \sigma\in\mathbb{N} the cop speed , (4) \psi\in\mathbb{N} the robber speed , (5) \rho\in\mathbb{N} the cop reach and (6) R\in\mathbb{N} the robber radius . The game is played as follows. First, the cop player chooses n vertices of \Gamma as starting positions. Then the robber chooses one vertex of \Gamma as their starting position. The players take turns moving, starting with the cops. In each turn, the cop-player can move each cop along a path of length at most \sigma to some vertex in \Gamma . The robber-player then moves the robber along a path of length at most \psi ending in a vertex. One cop-move followed by one robber-move is called a stage . The cop-player wins if the robber is captured : during any stage in the game the robber’s position is at distance at most \rho from some cop’s position; or if the cops can eventually defend v : after some finite initial time, the robber never enters the closed ball of radius R around v . Note that the robber not only needs to be at least \rho away from the cops at the beginning and ends of stages but also during the whole movement of the robber. The robber needs to be able to take their path edge by edge without ever coming \rho -close to a cop. The weak cop number \operatorname{wCop}(\Gamma) of \Gamma is the smallest value n such that for any v\in\Gamma , the cop-player wins the game when first the cop-player chooses their speed \sigma and reach \rho and then the robber-player chooses their speed \psi and the radius R . Formally \displaystyle\operatorname{wCop}(\Gamma)=\inf\left\{n\in\mathbb{N}\colon\begin{array}[]{l}\forall v\in\Gamma,\exists\sigma\in\mathbb{N},\exists\rho\in\mathbb{N},\forall\psi\in\mathbb{N},\forall R\in\mathbb{N}\colon\\ \exists\text{ a winning strategy for the cop-player with $n$ cops.}\end{array}\right\}. The strong cop number \operatorname{sCop}(\Gamma) of \Gamma is defined similarly, except that the cop-player chooses \rho after the robber player chooses \psi , formally \displaystyle\operatorname{sCop}(\Gamma)=\inf\left\{n\in\mathbb{N}\colon\begin{array}[]{l}\forall v\in\Gamma,\exists\sigma\in\mathbb{N},\forall\psi\in\mathbb{N},\exists\rho\in\mathbb{N},\forall R\in\mathbb{N}\colon\\ \exists\text{ a winning strategy for the cop-player with $n$ cops.}\end{array}\right\}. Since \operatorname{wCop} and \operatorname{sCop} are preserved under quasi-isometry [ 12 , Corollary G] , the cop numbers \operatorname{wCop}(\Gamma) and \operatorname{sCop}(\Gamma) of a Cayley graph \Gamma=\operatorname{Cay}(G,S) of a finitely generated group G do not depend on the finite generating set S . This allows us to define \operatorname{wCop}(G)\coloneq\operatorname{wCop}(\Gamma) and \operatorname{sCop}(G)\coloneq\operatorname{sCop}(\Gamma) . It is an exercise to convince oneself that \operatorname{sCop}(\Gamma)\leqslant\operatorname{wCop}(\Gamma) . Moreover \operatorname{wCop}(\mathbb{Z})=\operatorname{sCop}(\mathbb{Z})=1 and this generalizes to infinite trees, such as Cayley graphs of free groups. Remark 2.1 . The existence of a winning strategy is always independent of the vertex v : Suppose that for v\in\Gamma there exists a winning strategy for the robber using speed \rho and reach R . Then there also exists a winning robber-strategy for v^{\prime}\in\Gamma by using the same speed, doing the same moves and picking the reach R^{\prime}\coloneq R+d_{\Gamma}(v,v^{\prime}) . In the case where \Gamma is a Cayley graph, we will for simplicity always choose v=1 . Remark 2.2 . As the cop numbers are invariant under quasi-isometry and every geodesic metric space is quasi-isometric to a graph, we may define the cop-number of arbitrary geodesic metric spaces. It is also possible to define the cops and robbers game directly on geodesic metric spaces where the players move along paths with lengths bounded by their speeds and thus define the cop number of a geodesic metric space. As in [ 12 , Theorem 4.2] the cop numbers for geodesic metric spaces are invariant under quasi-isometries, so these two methods yield the same definition. The following theorem is an important result about retractions, that was used by [ 12 ] to establish that the cop numbers are invariant under quasi-isometry. Theorem 2.3 ( [ 12 ] Theorem E) . Let \Gamma,\Delta be graphs. If there is a quasi-retraction from \Gamma to \Delta , then \operatorname{wCop}(\Delta)\leqslant\operatorname{wCop}(\Gamma)\quad\text{and}\quad\operatorname{sCop}(\Delta)\leqslant\operatorname{sCop}(\Gamma). 3. Cop numbers and known geometric invariants. 3.1. Strong cop number and hyperbolicity One of the most important invariants in geometric group theory is hyperbolicity. A geodesic metric space is hyperbolic if there exists \delta such that all triangles are \delta -slim (if the triangle is given by geodesics [x,y],[y,z],[x,z] , then [x,z]\subseteq N_{\delta}([x,y]\cup[y,z]) ). A finitely generated group is hyperbolic if its Cayley graphs are. We use the following alternative characterization of hyperbolicity for graphs in terms of thin bigons due to [ 15 ] . A bigon in a graph \Gamma is a pair of geodesic paths \gamma,\gamma^{\prime}\colon[0,\ell]\cap\mathbb{Z}\to\Gamma with \gamma(0)=\gamma^{\prime}(0) and \gamma(\ell)=\gamma^{\prime}(\ell) . For \delta\in\mathbb{R} , we say that bigons in a graph \Gamma are \delta -thin if for all t\in[0,\ell]\cap\mathbb{Z} , d(\gamma(t),\gamma^{\prime}(t))\leqslant\delta . Theorem 3.1 . [ 15 , Theorem 1.4] Let G be a finitely generated group and \Gamma the Cayley graph associated to a finite generating set of G . If there is a \delta such that all bigons are \delta -thin, then G is hyperbolic. Remark 3.2 . The theorem is only stated for Cayley graphs of groups in [ 15 ] , but the proof given there is valid for graphs in general. One should however be careful and note that the theorem does not hold for general geodesic metric spaces, such as \mathbb{R}^{2} . For general geodesic metric spaces, Pomroy proved a characterization of Gromov-hyperbolicity in terms of quasi-geodesic bigons [ 5 , Theorem 22] , but for us, it is easier to work with the characterization given here. The converse of Theorem 3.1 is also true: in a hyperbolic graph, every bigon is a degenerate triangle and \delta -slim bigons ( \gamma\subseteq N_{\delta}(\gamma^{\prime}) ) are 2\delta -thin, see for instance [ 5 , Lemma 4] . Corollary 3.3 . A graph is hyperbolic if and only if there is a \delta such that all bigons are \delta -thin. Lee, Martínez-Pedroza and Rodríguez-Quinche showed that every hyperbolic graph \Gamma has strong cop number 1 [ 12 , Theorem A] . The following theorem shows that this is a characterization of hyperbolicity. Theorem 3.4 . A graph \Gamma is hyperbolic if and only if \operatorname{sCop}(\Gamma)=1 . Proof. Because of [ 12 , Theorem A] , it suffices to show that if \Gamma is not hyperbolic, then \operatorname{sCop}(\Gamma)>1 . Let \Gamma be non-hyperbolic, then by Corollary 3.3 , for every \delta>0 there exist bigons that are not \delta -thin. We now describe a winning strategy for the robber against one strong cop. The game starts with the cop player choosing their speed \sigma . The robber then chooses speed \psi=96\sigma. The cop then chooses reach \rho , which we may assume without loss of generality to satisfy \rho\geqslant\sigma . Since \Gamma is not hyperbolic, there exists a \delta>32\rho and a bigon (\gamma,\gamma^{\prime}) that is \delta -thin, but not (\delta-1) -thin. The robber now chooses a radius R large enough so that a \delta -neighborhood of the bigon is contained in the ball of radius R around the base point. Next, the cop chooses a starting position. The distance \lambda:=\delta/16>2\rho\geqslant\rho+\sigma will play an important role in the following, it is a distance at which the robber is safe from the cop, even after the cop moves once. The bigon (\gamma,\gamma^{\prime}) has the property that there exists t\in[0,\ell] such that d(\gamma(t),\gamma^{\prime}(t))=\delta=16\lambda and we denote p:=\gamma(t) and p^{\prime}:=\gamma^{\prime}(t) . At least one of the two points p,p^{\prime} has distance larger than 5\lambda from the starting position of the cop, and the robber chooses that point as their starting point r_{0} . Without loss of generality r_{0}=p . The game now starts with a move from the cop. The strategy of the robber during the game is as follows. As long as the distance to the cop is at least 5\lambda , the robber just stays where they are and waits. As soon as the cop gets closer than 5\lambda to the robber, the robber will move from p to p^{\prime} along one of the two paths \eta_{\pm} starting at p , following along \gamma to \gamma(t\pm\delta) , then along some geodesic to \gamma^{\prime}(t\pm\delta) and finally along \gamma^{\prime} to p^{\prime} ; see Figure 2 for an illustration. In case t+\delta>\ell or t-\delta<0 , we let \eta_{\pm} just consist of the paths via \gamma(0) or \gamma(\ell) without the middle shortcut. Once arrived at p^{\prime} , the robber repeats the strategy of waiting until the cop gets closer than 5\lambda and then switches back to p . By the choice of R , the robber never strays too far from the base point, so to show that this is a winning strategy for the robber, it suffices to show that the robber can choose and follow one of the paths \eta_{+} or \eta_{-} without ever being caught. Figure 2. The robber finds a \delta -thin, but not (\delta-1) -thin bigon and waits at p . Once the cop gets closer than 5\lambda , the robber moves from p to p^{\prime} along one of two possible paths \eta_{+} or \eta_{-} , at most one of which can be blocked by the cop c_{0} . Figure 3. To prove that the robber r is not caught by the cop c during their movement along \eta_{+} we consider five cases. Case (e) is only needed if \ell2\lambda and for every u>0 , d(c_{0},\gamma(t+u))>\lambda . Intuitively the claim states that if \eta_{-} is blocked, then (at least the part along \gamma of) \eta_{+} is not blocked. Indeed, the triangle inequality gives s=d(\gamma(t-s),p)\geqslant d(c_{0},p)-d(c_{0},\gamma(t-s))>2\lambda . If u<2\lambda , then d(c_{0},\gamma(t+u))\geqslant d(c_{0},p)-d(\gamma(t+u),p)>4\lambda-2\lambda=2\lambda. by Equation 1 . If u>2\lambda , then d(c_{0},\gamma(t+u))\geqslant d(\gamma(t-s),\gamma(t+u))-d(\gamma(t-s),c_{0})>(s+u)-2\lambda>2\lambda concludes the proof of the claim. Analogously, if for some s\geqslant 0 , d(c_{0},\gamma(t+s))<2\lambda , then for every u\geqslant 0 , d(c_{0},\gamma(t-u))>2\lambda . This implies that at most one of the paths \eta_{+} or \eta_{-} can be blocked. Let us assume without loss of generality that \eta_{+} is not blocked. For the entire movement of the robber, we consider the following cases, illustrated in Figure 3 : (a) If r=\gamma(t+u) for some u\geqslant 0 , then d(c,r)\geqslant d(c_{0},\gamma(t+u))-d(c_{0},c)>2\lambda-\lambda=\lambda . (b) If d(r,\gamma(t+\delta))\leqslant 9\lambda , then d(r,c)\geqslant d(\gamma(t+\delta),p)-d(\gamma(t+\delta),r)-d(c,p)>16\lambda-9\lambda-6\lambda=\lambda by Equation ( 2 ). (c) If d(r,\gamma^{\prime}(t+\delta))\leqslant 7\lambda , then \displaystyle d(r,c) \displaystyle\geqslant d(\gamma(\ell),p)-d(\gamma(\ell),\gamma^{\prime}(t+\delta))-d(r,\gamma^{\prime}(t+\delta))-d(c,p) \displaystyle>(\ell-t)-(\ell-(t+\delta))-7\lambda-6\lambda=3\lambda>\lambda. (d) If d(r,p^{\prime})\leqslant 9\lambda , then d(r,c)\geqslant d(p,p^{\prime})-d(r,p^{\prime})-d(p,c)>\delta-9\lambda-6\lambda=\lambda . If t+\delta>\ell , there is no point \gamma(t+\delta) . Then we replace cases (b) and (c) by the following. (e) If d(r,p^{\prime})\geqslant 9\lambda and r\in\operatorname{im}(\gamma^{\prime}) , then d(\gamma(\ell),r)=d(p^{\prime},\gamma(\ell))-d(r,p^{\prime})\leqslant\ell-t-9\lambda and d(r,c)\geqslant d(p,\gamma(\ell))-d(p,c)-d(\gamma(\ell),r)>(\ell-t)-6\lambda-(\ell-t-9\lambda)=3\lambda>\lambda . While the robber moves along \eta_{+} , they are always in at least one of the cases above and thus never get caught. Finally, once the robber reaches p^{\prime} , we have that d(p^{\prime},c)\geqslant d(p^{\prime},p)-d(p,c)>10\lambda>5\lambda , so the strategy can repeat and the robber has a winning strategy. ∎ 3.2. Weak cop numbers and virtually free groups In this section we characterize the graphs and groups with weak cop number 1 , answering a question of Cornect and Martínez-Pedroza [ 7 , Question 1.4] . Theorem 3.5 . A finitely generated group G is virtually free if and only if it satisfies \operatorname{wCop}(G)=1 . Theorem 3.6 . Let X be a geodesic metric space. Then \operatorname{wCop}(X)=1 if and only if X is a quasi-tree. The two theorems are equivalent since the geometry and algebra of virtually free groups are related by the following well-known theorem. Theorem 3.7 ( [ 8 ] Theorem 20.45, or [ 11 ] Theorem 3.28, or [ 4 ] Corollary 10.7) . A finitely generated group is virtually free if and only if its Cayley graph is a quasi-tree. We use the following characterization of quasi-trees. Theorem 3.8 ( [ 14 ] , Theorem 4.6, Bottleneck Property) . A geodesic metric space X is a quasi-tree if and only if it satisfies the Bottleneck Property : There is some \delta>0 such that for all x,z\in X there exists y\in X with d(x,y)=d(y,z)=\frac{1}{2}d(x,z) and the property that any path \gamma from x to z satisfies d(\gamma,y)\leqslant\delta . Proof of Theorem 3.6 . Figure 4. The negation of the Bottleneck property guarantees the existence of a path \gamma connecting x and y outside a ball of size 6\lambda around y . If X is a quasi-tree, then it has \operatorname{wCop}(X)=1 . So suppose that X is not a quasi-tree. We provide a winning strategy for the robber against one weak cop. The game starts with the cop player picking speed \sigma and reach \rho . Set \lambda\coloneq\sigma+\rho . As X is not a quasi-tree, it does not satisfy the bottleneck property. Hence in X there are points x,y,z and a path \gamma connecting x to z such that d(x,y)=d(y,z)=\frac{1}{2}d(x,z) and d(y,\gamma)>6\lambda . Let \eta be a geodesic from x to z through y and denote by \eta_{-} and \eta_{+} the parts of \eta from x to y and from y to z respectively, see Figure 4 . The strategy for the robber is to end every move in either x or y and to move between the two points using either \eta_{-} or \eta_{+} and \gamma . Thus we pick the robber’s speed \psi and reach R large enough to allow these moves. Our strategy is to maintain the following invariant after every move of the robber: Let c denote the cop’s position at that time. (1) Either the robber is positioned at y and d(c,y)\geqslant 4\lambda (2) or the robber is positioned at x and d(c,y)<4\lambda . Note that as d(x,y)\geqslant d(\gamma,y)>6\lambda, this ensures that the robber cannot be caught during any of the cop player’s turns. Hence it is enough to prove that this invariant can indeed be maintained. Further, there is a point among x and y which may serve as a starting position for the robber to satisfy the invariant. To describe the robber’s moves, suppose first that the robber is currently positioned at y and hence the cop is at least 4\lambda away from y . As long as the cop does not come within distance 4\lambda of y , the robber stays at y . If the cop ever moves to some point c such that d(c,y)<4\lambda , the robber either moves along \eta_{-} to x , or along \eta_{+} to z and then along \gamma to x . Note that moving along either path takes the robber only one turn. Hence it suffices to show that the cop cannot block both paths at the same time. That is, we show that d(\gamma,c)\geqslant\lambda>\rho and d(\eta_{+},c)\geqslant\lambda\quad\text{or}\quad d(\eta_{-},c)\geqslant\lambda. By the triangle inequality, d(\gamma,c)\geqslant d(\gamma,y)-d(y,c)>6\lambda-4\lambda=2\lambda, so we only need to show that one of d(\eta_{\pm},c)\geqslant\lambda . Suppose that d(\eta_{+},c)<\lambda and let c^{\prime}\in\eta_{+} such that d(c^{\prime},c)<\lambda . As the cop just moved into the ball of radius 4\lambda around y , they moved at most \sigma\leqslant\lambda into that ball. That is, 3\lambda\leqslant d(c,y)<4\lambda . We want to show that d(\eta_{-},c)\geqslant\lambda . As \eta is a geodesic containing c^{\prime} , we have that d(\eta_{-},c^{\prime})=d(y,c^{\prime}) and hence \displaystyle d(\eta_{-},c) \displaystyle~\geqslant d(\eta_{-},c^{\prime})-d(c,c^{\prime})=d(y,c^{\prime})-d(c,c^{\prime}) \displaystyle~\geqslant d(y,c)-d(c,c^{\prime})-d(c,c^{\prime})\geqslant 3\lambda-\lambda-\lambda=\lambda>\rho, finishing the proof that at least one of \eta_{\pm} is not blocked by the cop. Now suppose that the robber is currently positioned at x . As long as the cop stays within the ball of radius 4\lambda around y , the robber stays at x . As soon as the cop moves to some point c such that d(c,y)\geqslant 4\lambda , we show that the path \gamma , as well as at least one of \eta_{\pm} is not blocked by the cop, so the robber can move to y . The proof uses essentially the same idea as the first part. Again, as the cop just moved to c from some point that had distance at most 4\lambda from y and they move only distance \sigma\leqslant\lambda , we know that 4\lambda\leqslant d(c,y)\leqslant 5\lambda and hence d(\gamma,c)\geqslant d(\gamma,y)-d(y,c)\geqslant 6\lambda-5\lambda=\lambda>\rho. Suppose that \eta_{+} is blocked by the cop. That is, there is some c^{\prime}\in\eta_{+} such that d(c,c^{\prime})\leqslant\sigma<\lambda . Then d(\eta_{-},c)\geqslant d(\eta_{-},c^{\prime})-d(c^{\prime},c)=d(y,c^{\prime})-d(c^{\prime},c)\geqslant d(y,c)-2d(c^{\prime},c)\geqslant 4\lambda-2\lambda>\lambda, finishing the proof. ∎ 4. Metagaming with quasi-homotheties 4.1. Strong cop number of \mathbb{Z}^{n} . The square grid \Gamma=\mathbb{Z}^{2} has \operatorname{wCop}(\mathbb{Z}^{2})=\infty [ 12 , Theorem C] , but the value of the strong cop number is left as an open question [ 12 , Question D] . We show that \operatorname{sCop}(\mathbb{Z}^{2})=\infty by reducing to the weak cop game. Theorem 4.1 . For n\geqslant 2 , \operatorname{sCop}(\mathbb{Z}^{n})=\infty . Proof. Since \mathbb{Z}^{n} retracts to \mathbb{Z}^{2} , it suffices to consider the case n=2 , by Theorem 2.3 . We have \operatorname{wCop}(\mathbb{Z}^{2})=\infty , meaning that there is a winning strategy for the robber against any number of weak cops. In the following, we describe a winning strategy for the robber against any number of strong cops, by reducing to the weak version of the game. Let n\in\mathbb{N} arbitrary and let \sigma_{0}=2 , \rho_{0}=3 . We know that there are \psi_{0},R_{0}\in\mathbb{N} such that there is a winning strategy for the robber-player. Throughout the proof, the robber-player will access this strategy as an oracle. This copy of \mathbb{Z}^{2} will be denoted by \mathbb{Z}_{o}^{2} . To show that \operatorname{sCop}(\mathbb{Z}^{2})>n , we will show that \exists v\in\mathbb{Z}^{2} , \forall\sigma\in\mathbb{N},\exists\psi\in\mathbb{N},\forall\rho\in\mathbb{N},\exists R\in\mathbb{N} such that there is no winning strategy for the cop-player with n cops. We choose v=0 . Given \sigma\in\mathbb{N} , we choose \psi=4\psi_{0}\sigma and given \rho\in\mathbb{N} , we choose R=4R_{0}\rho, where \psi_{0} and R_{0} are the values from the weak-cop game described above. We may assume without loss of generality that \rho is a multiple of \sigma by increasing \rho . The game starts with the cop-player choosing n starting positions c_{1},\ldots,c_{n}\in\mathbb{Z}^{2} . The robber-player chooses their starting position as follows. The robber-player considers the subgraph (4\rho\mathbb{Z})^{2}\subseteq\mathbb{Z}^{2} . Scaling by a factor 4\rho gives an isomorphism \iota\colon\mathbb{Z}_{o}^{2}\cong(4\rho\mathbb{Z})^{2} . For each cop c_{i} on \mathbb{Z}^{2} , the robber-player considers the location and chooses a closest vertex p_{i} of (4\rho\mathbb{Z})^{2} (there are at most 4 possible closest vertices). Note that d(p_{i},c_{i})\leqslant 4\rho . The robber-player now queries the oracle with the cop starting positions \iota^{-1}(p_{1}),\ldots,\iota^{-1}(p_{n})\in\mathbb{Z}_{o}^{2} to obtain a starting position in \mathbb{Z}_{o}^{2} and via \iota also a starting position r\in(4\rho\mathbb{Z})^{2}\subseteq\mathbb{Z} . We note that the robber is not currently captured, as \displaystyle 12\rho=4\rho\cdot\rho_{0}<4\rho\cdot d(\iota^{-1}(p_{i}),\iota^{-1}(r))=d(p_{i},r)\leqslant d(p_{i},c_{i})+d(c_{i},r)\leqslant 4\rho+d(c_{i},r) implies d(c_{i},r)>8\rho>\rho . During the game, the robber-player continues to play as if the game took place on (4\rho\mathbb{Z})^{2} : since the robber’s speed \psi is potentially much slower than the grid size 4\rho of (4\rho\mathbb{Z})^{2} , the robber can not move from one vertex of (4\rho\mathbb{Z})^{2} to another in one stage. Instead, we introduce the notion of a meta-stage , which consists of \rho/\sigma many stages on \mathbb{Z}^{2} . In one meta-stage, the robber can move a distance up to \psi\cdot\rho/\sigma=4\psi_{0}\sigma\cdot\rho/\sigma=4\rho\psi_{0}, corresponding to \psi_{0} many edges on \mathbb{Z}_{o}^{2} . At the beginning of a meta-stage, when it is the robber-player’s turn, they analyze the board and approximate the cop’s locations to vertices of (4\rho\mathbb{Z})^{2} as before. The robber-player then queries the oracle, to obtain a path \gamma to a new point in \mathbb{Z}_{o}^{2} that prevents the weak cop-player from having a winning strategy. For the rest of the meta-stage, the robber-player ignores the plays of the cop-player and just follows the corresponding path \iota(\gamma) on (4\rho\mathbb{Z})^{2}\subseteq\mathbb{Z}^{2} . We note that during one meta-stage, the cops can move at most \sigma\cdot\rho/\sigma=\rho which is a fourth of an edge length on the graph (4\rho\mathbb{Z})^{2} . However, since the cops are not restricted to grid points of (4\rho\mathbb{Z})^{2} , their perceived movement on (4\rho\mathbb{Z})^{2} can be larger. Let c_{t},c_{t+1}\in\mathbb{Z}^{2} be a cop’s position at the beginning and the end of a meta-stage, and let p_{t},p_{t+1}\in(4\rho\mathbb{Z})^{2} be the corresponding pretended locations. Since d(c_{t},p_{t})\leqslant 4\rho and d(c_{t+1},p_{t+1})\leqslant 4\rho , d(p_{t},p_{t+1})\leqslant d(p_{t},c_{t})+d(c_{t},c_{t+1})+d(c_{t+1},p_{t+1})\leqslant 8\rho+\rho<3(4\rho) and since distances between graph points on (4\rho\mathbb{Z})^{2} lie in (4\rho)\mathbb{Z} , we actually have d(p_{t},p_{t+1})\leqslant 8\rho and thus, from the point of view of \mathbb{Z}_{o}^{2} , cops can move at most \sigma_{0}=2 vertices per meta-stage. The range of the cops is \rho which even together with the 4\rho offsets of the actual locations to the perceived locations, is 9\rho\leqslant 3(4\rho) , and hence corresponds to at most \rho_{0}=3 edges on \mathbb{Z}_{o}^{2} . Finally, the radius R=4R_{0}\rho corresponds to a radius of R_{0} on \mathbb{Z}_{o}^{2} . From the above discussion, it follows that the movement of the cops and the robber on (4\rho\mathbb{Z})^{2} in terms of meta-stages corresponds to the movement on \mathbb{Z}^{2} in the weak cop game oracle. From this, it is clear that at the beginning of every meta-stage, the robber is not captured. We now argue why the robber never reaches a \rho -neighborhood of a cop, even at any point within a meta-stage or a stage. If at any time within a meta-stage, a cop c\in\mathbb{Z}^{2} is in reach \rho of one of the 4\rho-2 many points that lie on an edge between two vertices a,b\in(4\rho\mathbb{Z})^{2} , where \iota^{-1}(a) is adjacent to \iota^{-1}(b) in \mathbb{Z}_{o}^{2} , then any pretended location p of c is within distance 5\rho of both endpoints a,b . Moreover, the position of the cop at the beginning and the end of the meta-stage differs by at most \rho . Thus the position of the cop at the beginning and the end of the meta-stage is less than 8\rho from both endpoints a,b\in(4\rho\mathbb{Z})^{2} . Hence, in the oracle \mathbb{Z}_{o}^{2} , the corresponding vertices \iota^{-1}(a),\iota^{-1}(b) are reachable by the cop during the whole meta-stage. Hence, in the oracle \mathbb{Z}_{o}^{2} , the robber will never pass through the vertices \iota^{-1}(a) , \iota^{-1}(b)\in\mathbb{Z}_{o}^{2} , the robber in \mathbb{Z}^{2} will also never pass through a,b and neither through any points between a and b . A robber following this strategy can therefore not be captured and the cops cannot eventually defend v=0 . This means that there is no winning strategy for the cop-player. As this argument works for all n\in\mathbb{N} , we have \operatorname{sCop}{(\mathbb{Z}^{2})}=\infty . ∎ 4.2. Meta gaming for quasi-homotheties The main idea in the proof of Theorem 4.1 is to use a homothety \mathbb{Z}^{2}\to\mathbb{Z}^{2} to play in meta-stages. In this section, we generalize this idea in Theorem 4.5 , where we show that whenever certain quasi-homotheties exist, they can be used to upgrade results from the weak cop game to the strong cop game. An application of these results is given in Corollary 5.5 , where we show that the hyperbolic plane does not admit surjective homotheties. A map h\colon X\to X on a metric space X is called a homothety if there is some \mu>1 such that d(h(x),h(y))=\mu d(x,y) for all x,y\in X . In analogy to quasi-isometries, we generalize this notion as follows. Note that every homothety h and its powers h^{j} are already quasi-isometries, but the sequence h^{j} does not have uniform quasi-isometry constants. Definition 4.2 . Let A\geqslant 1,B\geqslant 0 , \rho=(\rho_{j})_{j} a sequence of positive integers with \rho_{j}\to\infty and \Gamma,\Delta_{j} graphs for j\in\mathbb{N} . A collection of \iota_{j}\colon\Delta_{j}\to\Gamma is called a sequence of (A\rho+B) -surjective (A,B) -quasi- \rho -homotheties if for all j\in\mathbb{N} (1) \forall x\in\Gamma,\exists\overline{x}\in\Delta_{j}\colon d_{\Gamma}(\iota_{j}(\overline{x}),x)\leqslant A\rho_{j}+B . (2) \forall\overline{x},\overline{y}\in\Delta_{j}\colon A^{-1}d_{\Delta_{j}}(\overline{x},\overline{y})-B\leqslant\frac{1}{\rho_{j}}d_{\Gamma}(\iota_{j}(\overline{x}),\iota_{j}(\overline{y}))\leqslant A\,d_{\Delta_{j}}(\overline{x},\overline{y})+B . Note that every surjective homothety h\colon\Gamma\to\Gamma with scaling \mu>1 gives rise to a sequence \iota_{j}:=h^{j}\colon\Gamma\to\Gamma of \rho -surjective (1,0) -quasi- \rho -homotheties, where \rho_{j}=\mu^{j} . As for quasi-isometries, quasi-homotheties admit quasi-inverses described in the following Lemma. Lemma 4.3 . Let \iota_{j}\colon\Delta_{j}\to\Gamma be a sequence of (A\rho+B) -surjective (A,B) -quasi- \rho -homotheties. Then there are maps \pi_{j}\colon\Gamma\to\Delta_{j} such that for all x,y\in\Gamma \frac{1}{A}d_{\Delta_{j}}(\pi_{j}(x),\pi_{j}(y))-(2A+3B)\leqslant\frac{1}{\rho_{j}}d_{\Gamma}(x,y)\leqslant A\,d_{\Delta_{j}}(\pi_{j}(x),\pi_{j}(y))+(2A+3B) and for all x\in\Gamma,\overline{x}\in\Delta_{j} d_{\Gamma}(x,\iota_{j}(\pi_{j}(x)))\leqslant A\rho_{j}+B\quad\text{ and }\quad d_{\Delta_{j}}(\overline{x},\pi_{j}(\iota_{j}(\overline{x})))\leqslant AB. Proof. We fix j and for simplicity just write \Delta=\Delta_{j} , \iota=\iota_{j},\rho=\rho_{j} and \pi=\pi_{j} . For x\in\Gamma , there exists \overline{x}\in\Delta (without loss of generality let \iota(\overline{x})=x when x\in\iota(\Delta) ) such that d_{\Gamma}(x,\iota(\overline{x}))\leqslant A\rho+B. Let \pi(x):=\overline{x} . Then \displaystyle d_{\Gamma}(x,y) \displaystyle\leqslant d_{\Gamma}(x,\iota(\overline{x}))+d_{\Gamma}(\iota(\overline{x}),\iota(\overline{y}))+d_{\Gamma}(\iota(\overline{y}),y) \displaystyle\leqslant 2(A\rho+B)+\rho(A\,d_{\Delta}(\overline{x},\overline{y})+B) \displaystyle\leqslant\rho(A\,d_{\Delta}(\overline{x},\overline{y})+2A+3B) and \displaystyle d_{\Gamma}(x,y) \displaystyle\geqslant d_{\Gamma}(\iota(\overline{x}),\iota(\overline{y}))-d_{\Gamma}(x,\iota(\overline{x}))-d_{\Gamma}(\iota(\overline{y}),y) \displaystyle\geqslant\rho\left(\frac{1}{A}d_{\Delta}(\overline{x},\overline{y})-B\right)-2(A\rho+B) \displaystyle\geqslant\rho\left(\frac{1}{A}d_{\Delta}(\overline{x},\overline{y})-(2A+3B)\right). It may happen that \iota is not injective, but we still have for \overline{x}\in\Delta \displaystyle d_{\Delta}(\overline{x},\pi(\iota(\overline{x}))) \displaystyle\leqslant A\left(\frac{1}{\rho}d_{\Gamma}(\iota(\overline{x}),\iota(\pi(\iota(\overline{x}))))+B\right) \displaystyle=A\left(\frac{1}{\rho}d_{\Gamma}(\iota(\overline{x}),\iota(\overline{x}))+B\right)=AB.\qed Remark 4.4 . To elaborate on the analogy to quasi-isometries, consider the following category: Objects are sequences of metric spaces and morphisms are uniform sequences of quasi-isometric embeddings, where by uniform we mean that all maps use the same error constants. A sequence of quasi-surjective quasi- \rho -homotheties from (X,\mu) to (Y,\nu) represents an isomorphism from the sequence (X,\rho_{j}\mu)_{j\in\mathbb{N}} to the constant sequence (Y,\nu)_{j\in\mathbb{N}} . The following is the most general version of the meta-gaming theorem we provide in this work. Theorem 4.5 (Meta-gaming theorem) . Let \Delta_{j} be graphs with \operatorname{wCop}(\Delta_{j})\geqslant m\in\mathbb{N}\cup\{\infty\} such that for every \overline{\sigma},\overline{\rho} there exist \overline{\psi},\overline{R} such that there exist winning strategies for the robber on \Delta_{j} against m cops, where if the cop picks speed \overline{\sigma} and reach \overline{\rho} , the robber picks speed \overline{\psi} and reach \overline{R} . Let A\geqslant 1,B\geqslant 0 and \rho_{j}\to\infty a sequence of positive integers. Let \iota_{j}\colon\Delta_{j}\to\Gamma be a sequence of (A\rho+B) -surjective (A,B) -quasi- \rho -homotheties. Then \operatorname{sCop}(\Gamma)\geqslant m . To digest this statement, consider the following, which is Theorem 4.5 if all the \Delta_{i} are isometric to some common graph \Gamma . Corollary 4.6 . Let \Gamma be a graph, A\geqslant 1,B\geqslant 0 and \rho_{j}\to\infty a sequence of positive integers. If there is a sequence \iota_{j}\colon\Gamma\to\Gamma of (A\rho+B) -surjective (A,B) -quasi- \rho -homotheties, then \operatorname{sCop}(\Gamma)=\operatorname{wCop}(\Gamma) . For example, for \Gamma=\operatorname{Cay}(\mathbb{Z}^{2}) , such \rho_{j} and fitting homotheties exist. We conclude that \operatorname{sCop}(\mathbb{Z}^{2})=\operatorname{wCop}(\mathbb{Z}^{2}) . Thus, Theorem 4.5 is really a generalization of Theorem 4.1 . Their proofs use the same basic idea. Proof of Theorem 4.5 . Let n\sigma and that \rho=\rho_{j} for some j large enough. The robber chooses the radius R=\rho(A\overline{R}+A+2B). The cop then chooses starting positions c_{i}\in\Gamma for i=1,\ldots,n . For the choice of j with \rho=\rho_{j} above, we fix \Delta:=\Delta_{j} and \iota:=\iota_{j}\colon\Delta\to\Gamma . Let \pi\colon\Gamma\to\Delta be the quasi-projection from Lemma 4.3 . Definition 4.2 and Lemma 4.3 are summed up by the following facts for x,y\in\Gamma,\overline{x},\overline{y}\in\Delta . (1) \displaystyle\forall x\in\Gamma\,\exists\overline{x}\in\Delta\colon d_{\Gamma}(\iota(\overline{x}),x)\leqslant A\rho+B (2) \displaystyle\frac{1}{A}d_{\Delta}(\overline{x},\overline{y})-B\leqslant\frac{1}{\rho}d_{\Gamma}(\iota(\overline{x}),\iota(\overline{y}))\leqslant A\,d_{\Delta}(\overline{x},\overline{y})+B (3) \displaystyle\frac{1}{A}d_{\Delta}(\pi(x),\pi(y))-(2A+3B)\leqslant\frac{1}{\rho}d_{\Gamma}(x,y)\leqslant A\,d_{\Delta}(\pi(x),\pi(y))+(2A+3B) (4) \displaystyle d_{\Gamma}(x,\iota(\pi(x)))\leqslant A\rho+B (5) \displaystyle d_{\Delta}(\overline{x},\pi(\iota(\overline{x})))\leqslant AB During the game, the robber uses the weak-cop game played on \Delta with parameters \overline{\sigma},\overline{\rho},\overline{\psi},\overline{R} as an oracle for how to play on \Gamma . To determine the robber’s starting position r_{0} , the robber consults the oracle with cop starting positions \pi(c_{i})\in\Delta to obtain a starting position \overline{r}\in\Delta with which the weak-cop game can be won on \Delta , in particular d_{\Delta}(\overline{r},\pi(c_{i}))>\overline{\rho}+\overline{\sigma} . The robber then chooses the actual starting position r:=\iota(\overline{r})\in\Gamma . By ( 3 ) and ( 5 ), \displaystyle d_{\Gamma}(\iota(\overline{r}),c_{i}) \displaystyle\geqslant\rho\left(\frac{1}{A}\left(d_{\Delta}(\pi(\iota(\overline{r})),\pi(c_{i}))-(2A+3B)\right)\right) \displaystyle\geqslant\rho\left(\frac{1}{A}(d_{\Delta}(\overline{r},\pi(c_{i}))-d_{\Delta}(\overline{r},\pi(\iota(\overline{r}))))-(2A+3B)\right) \displaystyle>\rho\left(\frac{1}{A}(\overline{\rho}+\overline{\sigma}-AB)-(2A+3B)\right) \displaystyle=\rho\left(4(2A+3B)+\frac{1}{A}\overline{\sigma}-B-(2A+3B)\right) \displaystyle\geqslant\rho(2(2A+3B))\geqslant 2\rho\geqslant\rho+\sigma, the robber is not caught at the starting position r , even after the cops move once. The game now proceeds in meta-stages. At the beginning of a meta-stage, the robber is placed at r_{t}=\iota(\overline{r}_{t}) for some \overline{r}_{t}\in\Delta . The cops’ positions c_{i} are projected to \Delta , and the oracle suggests a path \overline{r}_{t}=\overline{p}_{1},\overline{p}_{2},\ldots,\overline{p}_{k}\in\Delta along which the robber follows in a winning strategy on \Delta . The actual robber will now spend the next \lambda:=\lceil\rho/\sigma\rceil many turns following geodesic paths from p_{j}:=\iota(\overline{p}_{j}) to p_{j+1} for j\in\{1,\ldots,k-1\} to finally reach p_{k}\in\iota(\Delta) . During the meta-stage, the cops can also do \lambda many moves. The meta-stage strategy then repeats. To prove that this gives a winning strategy for the robber it remains to show that (a) the robber can actually move as described from p_{1} to p_{k} in \lambda many moves, (b) the movement of the cops for \lambda many turns corresponds to a valid single move when projected to \Delta , (c) the robber is never caught during a meta-stage, and (d) after any number of turns, the robber eventually returns to the ball of radius R around the base point. (a) We have d_{\Delta}(\overline{p}_{1},\overline{p}_{k})\leqslant\overline{\psi} . Using ( 2 ) and 1\leqslant\rho/\sigma\leqslant\lceil\rho/\sigma\rceil=\lambda , \displaystyle d_{\Gamma}(p_{1},p_{k}) \displaystyle\leqslant\rho\left(A\,d_{\Delta}(\overline{p}_{1},\overline{p}_{k})+B\right)\leqslant\frac{\rho}{\sigma}\sigma\left(A\overline{\psi}+B\right)\leqslant\lambda\sigma(A\overline{\psi}+B)\leqslant\lambda\psi shows that the robber can complete the movement from p_{1} to p_{k} within \lambda many turns. Figure 5. At the beginning of a meta-stage, the cop’s position c_{0} is provided to the oracle \Delta via \pi . In the oracle there is a winning strategy by following along the path \overline{p}_{1},\ldots,\overline{p}_{k} , which the robber implements in \Gamma , by following along p_{1}:=\iota(\overline{p}_{1}),\ldots,p_{k} . (b) If the starting position of a cop is c_{0}\in\Gamma , then their position c_{t}\in\Gamma after \lambda many turns satisfies d_{\Gamma}(c_{0},c_{t})\leqslant\lambda\sigma . Projected to \Delta , we use ( 3 ) and \lambda\sigma=\lceil\rho/\sigma\rceil\sigma\leqslant(\rho/\sigma+1)\sigma=\rho+\sigma\leqslant 2\rho to show \displaystyle d_{\Delta}(\pi(c_{0}),\pi(c_{t})) \displaystyle\leqslant A\left(\frac{1}{\rho}d_{\Gamma}(c_{0},c_{t})+2A+3B\right) \displaystyle\leqslant A\left(2+2A+3B\right)\leqslant A(4A+3B)=\overline{\sigma} which confirms that the projected movement of the cops corresponds to a valid movement in \Delta . (c) Let c_{t} be the position of a cop and r_{t} the position of the robber at any time (possibly even different times) during a meta-stage. Note that in the projected game, the cops \pi(c_{t}) are never too close to any of the vertices \overline{p}_{1},\ldots,\overline{p}_{k} of the path of the robber, namely d_{\Delta}(\pi(c_{t}),\overline{p}_{i})>\overline{\rho} for every i\in\{1,\ldots,k\} . Since the robber in \Gamma moves on geodesics along the p_{i} , there is a j\in\{1,\ldots,k\} such that d_{\Gamma}(r_{t},p_{j})\leqslant d_{\Gamma}(p_{j},p_{j+1}) . The situation is illustrated in Figure 5 . Using ( 2 ), we get an estimate \displaystyle d_{\Gamma}(r_{t},p_{j}) \displaystyle\leqslant d_{\Gamma}(\iota(\overline{p}_{j}),\iota(\overline{p}_{j+1}))\leqslant\rho(Ad_{\Delta}(\overline{p}_{j},\overline{p}_{j+1})+B)=\rho(A+B) on the distance from the robber to some p_{j} . We then use the triangle inequality, the above estimates, ( 2 ), ( 4 ) and \overline{\rho}=4A(2A+3B) to obtain \displaystyle d_{\Gamma}(r_{t},c_{t}) \displaystyle\geqslant d_{\Gamma}(\iota(\pi(c_{t})),\iota(\overline{p}_{j}))-d_{\Gamma}(r_{t},p_{j})-d_{\Gamma}(\iota(\pi(c_{t})),c_{t}) \displaystyle\geqslant\rho\left(\frac{1}{A}d_{\Delta}(\pi(c_{t}),\overline{p}_{j})-B\right)-\rho(A+B)-(A\rho+B) \displaystyle>\rho\left(\frac{1}{A}\overline{\rho}-B\right)-2\rho(A+B) \displaystyle=\rho(4(2A+3B)-B-2A-2B)\geqslant 2\rho\geqslant\rho+\sigma which means that r_{t} is always at least \rho far away from c_{t} , even after one more movement by a distance of at most \sigma by the cop. This means that the robber is never caught. (d) Let v be the base point in \Gamma and \pi(v) the base point in \Delta . For any number of turns k , there is a number k^{\prime}\geqslant k such that the robber is in the ball of radius \overline{R} around \pi(v) , that is d_{\Delta}(\pi(v),\overline{r})\leqslant\overline{R} , where \overline{r} is the position of the robber at the beginning of turn k^{\prime} . In \Gamma , the robber will eventually visit \iota(\overline{r}) , which lies in the ball by the following estimate. We use the triangle inequality, ( 4 ) and ( 2 ) to obtain \displaystyle d_{\Gamma}(v,\iota(\overline{r})) \displaystyle\leqslant d_{\Gamma}(v,\iota(\pi(v)))+d_{\Gamma}(\iota(\pi(v)),\iota(\overline{r})) \displaystyle\leqslant(A\rho+B)+\rho(A\,d_{\Delta}(\pi(v),\overline{r})+B) \displaystyle\leqslant\rho(A+B+A\overline{R}+B)=R. The above calculations show that the robber can implement the strategy from the weak cop game on \Delta using meta-stages to win the strong cop game on \Gamma . Hence \operatorname{sCop}(\Gamma)>n for every n\sigma+\rho . This ensures that for any g\in\Gamma and any element of h\in B_{\sigma+\rho}(g) , the states of the lamps at least at one of a_{i} and b_{i} coincide between g and h . That is, a cop positioned at g can not, within one move, reach a position where they can see a robber at an element h which has different lamp-states in both a_{i} and b_{i} . Defining a_{0}:=a_{n} and b_{0}:=b_{n} for convenience, the robber then chooses speed and radius \psi:=R:=2d_{\Delta}(a_{n},b_{n})+\sum_{i=1}^{n}d_{\Delta}(a_{i-1},a_{i})+d_{\Delta}(b_{i-1},b_{i}) which corresponds to the length of a loop \gamma in \Delta visiting all the points a_{i},b_{i} . Note that the numbers \psi and R only depend on \Delta but not on L . Next, the cops choose their starting positions. Let c_{i}(p)\in L be the lamp-state of the i ’th cop’s lamp at position p\in\Delta . The robber chooses 1\neq l_{0}\in L and sets \widebar{1}\coloneq l_{0} and \widebar{l}\coloneq 1 for every l\in L\setminus 1 . The robber then chooses a starting position such that the robber’s lamps have state r(a_{i})=\widebar{c_{i}(a_{i})} and r(b_{i})=\widebar{c_{i}(b_{i})} , and the lamplighter-position is a_{1} . In particular, this is a position where the robber’s lamp-states at a_{i} and b_{i} differ from those of the i ’th cop. Hence by construction, the robber cannot be caught in the cop player’s first move. But, after a cop move, it might be that for some i , c_{i}(a_{i}) equals r(a_{i}) , the state of the robber’s lamp at a_{i} and the same goes for b_{i} . But for any given i , only one of c_{i}(a_{i}) and c_{i}(b_{i}) can match the robber. The robber’s move is to have the lamplighter move along the loop \gamma traversing all the a_{i} and b_{i} . For every a_{i} where c_{i}(a_{i})=r(a_{i}) , the lamplighter switches the lamp to \widebar{c(a_{i})} and analogously for b_{i} . As a generator in S corresponds to switching a lamp and then moving the lamplighter along some t\in T , the robber’s move is of length at most \psi . By construction, no point on this path can be seen by any of the cops, so this gives a valid path for the robber player. To see this, note that from an individual cop’s perspective, any lamp configuration along the path might as well have been the robber’s starting position, and the cops are far enough away from the robber that changing the robber’s lamplighter-position does not get them close enough. Moreover, at no point does the robber leave the ball of radius R around their starting point. Repeating this strategy, the robber is never caught and never leaves the ball, thus winning the game. ∎ Remark 5.2 . In the above proof, the points a_{i},b_{i} could be chosen in such a way that for some base point v\in\Delta we have d(v,a_{i})=i and d(v,b_{i})=\sigma+\rho+i+1 . Then \psi\leqslant\sum_{i=1}^{n}2d(v,a_{i})+2d(v,b_{i})\leqslant 2\sum_{i=1}^{n}i+(\sigma+\rho+i+1)=2n(n+1+\sigma+\rho+1), so \psi does not even depend on \Delta , but only on n,\sigma and \rho . In the following, we restrict to H=\mathbb{Z} and L finite. Elements of G=L\wr\mathbb{Z} are then of the form (a,n) , where a=(\ldots,a_{0},a_{1},\ldots) with a_{k}\in L for k,n\in\mathbb{Z} . Theorem 5.3 . Let L be a non-trivial finite group and set G\coloneq L\wr\mathbb{Z} . Then \operatorname{sCop}(G)=\infty . Proof. We use the generating set L\times\{t\} , where t is a generator of \mathbb{Z} and let \Gamma:=\operatorname{Cay}(G,L\times\{t\}) . The goal is to apply Theorem 4.5 , so we have to provide a sequence \Delta_{j} and a sequence of quasi-homotheties from \Delta_{j} to \Gamma , see Definition 4.2 . We set H_{j}\coloneq L^{j}\wr\mathbb{Z} and identify it with its Cayley graph \Delta_{j}:=\operatorname{Cay}(H_{j},L^{j}\times\{s\}) with respect to the generating set L^{j}\times\{s\} , where s is a generator of \mathbb{Z} . We further set \rho_{j}\coloneq j and proceed to show that there exists a sequence of quasi-surjective quasi- \rho -homotheties \Delta_{j}\to\Gamma . The maps are given by \iota_{j}\colon\Delta_{j}\to\Gamma, \iota_{j}(a,n)\coloneq(b,j\cdot n) where b_{j\cdot k+i}=a_{k}^{(i)} for a_{k}=(a_{k}^{(0)},\ldots,a_{k}^{(j-1)})\in L^{j} and any k\in\mathbb{Z} and i\in\{0,\dots,j-1\} . See an illustration of this in Figure 6 . The constants that appear in Definition 4.2 are A=1,B=2 . b_{0}=a^{(0)}_{0} b_{1}=a^{(1)}_{0} b_{2}=a^{(2)}_{0} b_{3}=a^{(0)}_{1} b_{4}=a^{(1)}_{1} b_{5}=a^{(2)}_{1} a_{0}\in L^{3} a_{1}\in L^{3} Figure 6. The map \iota_{3}\colon L^{3}\wr\mathbb{Z}\to L\wr\mathbb{Z} of a quasi-homothety. To prove quasi-surjectivity, note that (b,n)\in\iota_{j}(\Delta_{j}) if and only if n is a multiple of j=\rho_{j} . If n^{\prime} is the largest multiple of j such that n^{\prime}\leqslant n , we have d_{\Gamma}\left((b,n),(b,n^{\prime})\right)=n-n^{\prime}\leqslant\rho_{j} and (b,n^{\prime})\in\iota_{j}(\Delta_{j}) . For the quasi-homothety-part let (a,n),(a^{\prime},n^{\prime})\in\Delta_{j} . If n\neq n^{\prime} or a_{k}\neq a_{k}^{\prime} for some k\neq n , the distance between these two elements in \Delta_{j} is the length of the shortest lamplighter-path in \mathbb{Z} from n to n^{\prime} that traverses all indices k where a_{k}\neq a_{k}^{\prime} . Similarly, the distance d_{\Gamma}\left(\iota_{j}(a,n),\iota_{j}(a^{\prime},n^{\prime})\right) is the length of the shortest lamplighter-path from jn to jn^{\prime} that traverses all indices k where b_{k}\neq b_{k}^{\prime} . If n=n^{\prime} and for all k\neq n we have a_{k}=a^{\prime}_{k} , then the distance from (a,n) to (a^{\prime},n^{\prime}) is 2 and the lamplighter has to travel along tt^{-1} , while the distance from \iota_{j}(a,n) to \iota_{j}(a^{\prime},n^{\prime}) is between 2 and 2j . Up to replacing t with t^{-1} , we may assume without loss of generality that n\leqslant n^{\prime} . In both cases above, the lamplighter-path is of the form t^{-r}t^{\ell}t^{-m} for some r,\ell,m\in\mathbb{Z}_{\geqslant 0} such that -r+\ell-m=n^{\prime}-n . If for some k\in\mathbb{Z} we have b_{k}\neq b^{\prime}_{k} , then a_{\lfloor k/j\rfloor}\neq a^{\prime}_{\lfloor k/j\rfloor} . Hence there is a (not necessarily shortest) lamplighter-path of the form s^{-jr}s^{j(\ell+1)}s^{-j(m+1)} that realizes a path from \iota_{j}(a,n) to \iota_{j}(a^{\prime},n^{\prime}) in \Gamma . It has length at most j(r+\ell+m+2) , so d_{\Gamma}(\iota_{j}(a,n),\iota_{j}(a^{\prime},n^{\prime}))\leqslant j(d_{\Delta_{j}}((a,n),(a^{\prime},n^{\prime}))+2). On the other hand, every lamplighter-path corresponding to a path from \iota_{j}(a,n) to \iota_{j}(a^{\prime},n^{\prime}) has to traverse at least the points jn , j(n-r) , j(n-r+\ell) and jn^{\prime} in order, so has length at least j(r+\ell+m) . Hence \displaystyle d_{\Delta_{j}}\left((a,n),(a^{\prime},n^{\prime})\right) \displaystyle=r+\ell+m\leqslant\frac{1}{j}d_{\Gamma}\left(\iota_{j}(a,n),\iota_{j}(a^{\prime},n^{\prime})\right)\leqslant d_{\Delta_{j}}\left((a,n),(a^{\prime},n^{\prime})\right) and \iota_{j} is indeed a sequence of (1,2) -quasi-surjective \rho -homotheties. Since the speed \psi and radius R in the weak cop game only depends on the speed \sigma , reach \rho and the group \mathbb{Z} , but not on \Delta_{j} by Lemma 5.1 , we can apply Theorem 4.5 to conclude \operatorname{sCop}(G)=\infty . ∎ 5.2. Non-existence of quasi-homotheties Corollary 5.4 . If \Gamma is the Cayley graph of a hyperbolic group G that is not virtually free, then there does not exist a sequence \iota_{j}\colon\Gamma\to\Gamma of (A\rho+B) -surjective (A,B) -quasi- \rho -homotheties, for any A\geqslant 1,B\geqslant 0,\rho_{j}\to\infty . For A=1,B=0 , there does not exist a sequence of \rho -surjective \rho -homotheties for \rho_{j}\to\infty . Proof. By Theorems 3.4 and 3.5 , for such graphs \Gamma , we have \operatorname{wCop}(\Gamma)>1 , but \operatorname{sCop}(\Gamma)=1 . The existence of a self-quasi-homothety would contradict Corollary 4.6 . ∎ Corollary 5.5 . The hyperbolic plane \mathbb{H}^{2} does not admit a surjective homothety h\colon\mathbb{H}^{2}\to\mathbb{H}^{2} with \mu>1 . Proof. It is well known that the hyperbolic plane is quasi-isometric to the Cayley graph of a cocompact lattice G<\operatorname{Isom}(\mathbb{H}^{2}) , and that all such lattices are hence one-ended, non-amenable and hyperbolic. Let \Gamma be a Cayley graph of G and f\colon\Gamma\to\mathbb{H}^{2},g\colon\mathbb{H}^{2}\to\Gamma be (C,D) -quasi-isometries for C\geqslant 1,D\geqslant 0 . We will now show that if h\colon\mathbb{H}^{2}\to\mathbb{H}^{2} is a surjective \mu -homothety for \mu>1 , then \iota_{j}:=g\circ h^{j}\circ f\colon\Gamma\to\Gamma is a sequence of (A\rho+B) -surjective (A,B) -quasi- \rho -homotheties for \rho_{j}=\mu^{j} , A=C^{2}D+1 and B=CD+D . But by Corollary 5.4 , this is impossible, so no surjective \mu -homothety of the hyperbolic plane exists. The (C,D) -homotheties f\colon\Gamma\to\mathbb{H}^{2} and g\colon\mathbb{H}^{2}\to\Gamma satisfy for \overline{x},\overline{y}\in\Gamma and x,y\in\mathbb{H}^{2} (1) \displaystyle\frac{1}{C}d_{\Gamma}(\overline{x},\overline{y})-D\leqslant d_{\mathbb{H}^{2}}(f(\overline{x}),f(\overline{y}))\leqslant C\,d_{\Gamma}(\overline{x},\overline{y})+D (2) \displaystyle\forall y\in\mathbb{H}^{2}\ \exists\overline{x}\in{\Gamma}\colon d_{\mathbb{H}^{2}}(f(\overline{x}),y)n for all n\geqslant 1 . This implies that whenever nn , as the robber player can just pretend that the missing m-1-n cops are placed at 1 and stay there during the whole game. Now for arbitrary m\geqslant 2 and n\geqslant 1 we can find k\geqslant 1 such that nn . This is true for all n , so \operatorname{sCop}(\operatorname{BS}(1,m))=\infty for all m\geqslant 2 as well. It thus suffices to show that there is a winning strategy for the robber player against n cops on the Cayley graph of \operatorname{BS}(1,n+1) , which we will do in the following. We assume the base point is at the neutral element. First, the cops choose a speed \sigma , without loss of generality we may assume \sigma\geqslant n+1 . The robber chooses \psi=34\sigma . The cops then choose a reach \rho , without loss of generality we may assume that 3\sigma<\rho . Finally, the robber chooses R=n(n+1)^{8\rho}+8\rho+n . Let S_{0}:=\left\{t^{m}a^{N}\in\operatorname{BS}(1,n+1)\colon 0\leqslant m\leqslant 8\rho,0\leqslant N\leqslant n(n+1)^{8\rho-m}\right\} be a rectangular region of the first sheet that has height 8\rho , length n at the top and length n(n+1)^{8\rho} at the bottom. We call A=\{a^{N}\in\operatorname{BS}(1,n+1)\colon N\in\mathbb{Z}\} the axis . The translates S_{i}:=a^{i}S_{0} for 1\leqslant i\leqslant n are copies of the rectangular region, but they are part of other sheets, in fact S_{i}\cap S_{j} is contained in the axis A for all i\neq j . Any path from one sheet to another has to pass through the axis. At the beginning of the game, the cops are placed somewhere and since there are n+1 upper parts of distinct sheets, there is at least one (with index i_{0} ) that does not contain a cop and the robber chooses to start at a^{i_{0}}t^{8\rho} . The robber is not captured at the beginning and during the first movement of the cops. The robber’s strategy now is the following. The robber stays put until one of the cops reaches at least height \rho/2 in the upper part of the sheet in which the robber is placed. As soon as that happens, the robber picks one of the other n sheets (say with index j ) that does not have any cops in the upper part and walks to the point a^{j}t^{8\rho} along one of n+1 possible paths described below. Walking along this path may take more than one turn, but the robber just keeps going until they reach their goal, we call the whole movement one meta-step . Then the procedure repeats. Figure 8. The path with index k from sheet S_{i} to sheet S_{j} passes through the axis A . The situation is illustrated for n=2 , k=1 , i=0 , j=1 , \rho=1/4 . The n+1 possible paths going from a^{i}t^{8\rho} to a^{j}t^{8\rho} , indexed by k\in\{0,1,\ldots n\} , are defined by following the sequence of steps a^{k}t^{-8\rho}a^{j-i}t^{8\rho}a^{-k} , see Figure 8 . The length of one of these paths is at most 3k+16\rho\leqslant 3n+16\rho\leqslant 17\rho . During the time it takes the robber to move distance 17\rho , the cops can move at most \sigma/\psi\cdot 17\rho=\rho/2 . Figure 9. A ball of radius r=4 centered at t^{H} in the standard sheet for H=1 . The largest M such that the ball reaches a^{M}t^{x} for some x\in\mathbb{Z} is M=\operatorname{hd}(H)=2^{r-1+H}=16 . We will show that the robber can choose one of the paths and follow along it without being caught by a cop. Let \operatorname{hd}(H):=\max\left\{M\colon d(t^{m},a^{M}t^{x})\leqslant 2\rho,m\leqslant H,x\in\mathbb{Z}\right\} be the maximal horizontal distance (as measured projected down on the axis) of a cop with height m\leqslant H that can reach distance 2\rho (by first walking up to \rho during the meta-step and then actually reaching \rho ), see Figure 9 . Note that the best way to reach far horizontally is to first reach up by distance 2\rho-1 and then over by distance 1 . This corresponds to a horizontal distance of (n+1)^{2\rho-1} at the level where the cop is positioned and to a horizontal distance of at most (n+1)^{3\rho-1} on the axis for a cop at height at most \rho/2+\sigma\leqslant\rho . Therefore \operatorname{hd}(\rho)<(n+1)^{3\rho} . Since the points a^{k(n+1)^{8\rho}+i} with 0\leqslant i\leqslant n lie more than n+1 times the distance (n+1)^{3\rho} apart from each other (for different k ), every cop can block at most one of the n+1 paths. There are only n cops, so the robber can choose one. Thus the cops can never capture the robber and they can also not protect the ball, since the robber always stays within the rectangles, and in particular within the radius R around the neutral element. ∎ Remark 5.7 . It is possible to define a quasi-retraction from \operatorname{BS}(1,m) to a sheet, but since the sheet is hyperbolic and hence has strong cop number 1 , one can not use the quasi-retraction Theorem 2.3 to infer Theorem 5.6 . 5.4. Grigorchuk’s group In this section we prove that the cop numbers of direct products of infinite groups are infinite. We apply this result to Grigorchuk’s group and other branch groups. We first notice that the following generalization of Theorem 4.1 holds. Theorem 5.8 . The quadrant \mathbb{N}\times\mathbb{N}\subseteq\mathbb{Z}^{2} has infinite strong cop number. Proof. After replacing \mathbb{Z}^{2} by \mathbb{N}^{2} , the proofs of [ 12 , Theorem C] and Theorem 4.1 can be followed word by word. Alternatively, once one has defined the winning strategies for the robber in the weak cop game, the result follows from Theorem 4.5 . ∎ The idea for the following theorem was communicated to us by Francesco Fournier-Facio. Theorem 5.9 . If G_{1},\ldots,G_{k} with k\geqslant 2 are finitely generated infinite groups and G=G_{1}\times\ldots\times G_{k} , then \operatorname{sCop}(G)=\infty . Proof. A Cayley graph \Gamma of an infinite finitely generated group has unbounded diameter. There exists a geodesic ray \gamma\colon[0,\infty)\to\Gamma starting at the neutral element \gamma(0)=e . The word length \ell\colon\Gamma\to\mathbb{Z}_{\geqslant 0} can be used to define a retraction 1 1 1 This is a retraction in the sense of metric spaces, but not in the sense of graph retractions as in [ 12 , Example 4.1(2)] . However, it is a quasi-retraction. \gamma\circ\ell\colon\Gamma\to\operatorname{im}(\gamma) : indeed, for all g,h\in\Gamma d(\gamma(\ell(g)),\gamma(\ell(h)))=\lvert\ell(h)-\ell(g)\rvert=|d(e,h)-d(e,g)\rvert\leqslant d(g,h) by the triangle inequality. Let \Gamma_{1},\Gamma_{2} be the Cayley graphs of G_{1},G_{2} and let \gamma_{1},\gamma_{2} and \ell_{1},\ell_{2} as above. In the Cayley graph of G , we obtain a retraction r:=\gamma_{1}\circ\ell_{1}\times\gamma_{2}\circ\ell_{2}\colon G\twoheadrightarrow G_{1}\times G_{2}\to\operatorname{im}(\gamma_{1})\times\operatorname{im}(\gamma_{2}) . The codomain is isometric to \mathbb{Z}_{>0}\times\mathbb{Z}_{>0} . By Theorems 2.3 and 5.8 , \operatorname{sCop}(G_{1}\times\ldots\times G_{k})=\infty . ∎ The Grigorchuk group and branch groups G more generally contain a finite index subgroup H that is isomorphic to a direct product L\times\ldots\times L with at least two factors, where L is a finitely generated infinite group (since H is finite index in the finitely generated infinite group G ) [ 2 , Definition 1.1] . Theorem 5.10 . The Grigorchuk group and, more generally, finitely generated branch groups have infinite strong cop numbers. Proof. It is clear that branch groups G are infinite. Any finite index subgroup H that is isomorphic to a direct product L\times\ldots\times L with at least two finitely generated infinite factors has \operatorname{sCop}(H)=\infty by Theorem 5.9 . Finite index subgroups have quasi-isometric Cayley graphs, so \operatorname{sCop}(G)=\infty . ∎ 5.5. Thompson’s group F It is well known among experts that Thompson’s group F admits a retraction to \mathbb{Z}^{2} , see for instance [ 1 , Cor. 3.10] or [ 7 , Section 4] . By Theorems 2.3 and 4.1 , then \operatorname{sCop}(F)\geqslant\operatorname{sCop}(\mathbb{Z}^{2})=\infty . The analogous proof for the weak cop number has previously been used for the weak cop number by [ 7 ] . Theorem 5.11 . The strong cop number of Thompson’s group F is infinite. 6. Intermediate cop numbers The main remaining open question is that of intermediate cop numbers. Partial results are known for graphs that are not Cayley-graphs of groups [ 12 , Corollary O] , but the question is wide open for finitely generated groups. Question K ( [ 12 ] Question K) . Are there any finitely generated groups with weak and/or strong cop numbers not equal to 1 or \infty ? A finitely generated group that acts geometrically on a CAT(0)-space is called a CAT(0)-group. Proposition 6.1 . If G is a CAT(0)-group, then \operatorname{sCop}(G)\in\{1,\infty\} . Proof. By Theorem 3.4 we may assume that G is a finitely generated non-hyperbolic group G that acts geometrically on a CAT(0)-space X . By [ 3 , Theorem 3.1, Chapter III. \Gamma ] , X is known to contain an isometrically embedded copy of the Euclidean plane. Since CAT(0)-spaces admit retractions to convex subspaces, Theorem 2.3 can be applied, to obtain \operatorname{sCop}(G)\geqslant\operatorname{sCop}(\mathbb{Z}^{2})=\infty by Theorem 4.1 . ∎ The cop numbers are closely related to phenomena of non-positive curvature. The question might therefore be especially interesting to solve for related classes of groups such as acylindrically hyperbolic groups, hierarchically hyperbolic groups, Helly groups or lacunary hyperbolic groups. As finitely presented groups are quotients of CAT(0)-groups, special attention should be given to groups that are not finitely presented. Our investigation into the Baumslag-Solitar groups, Lamplighter groups and Grigorchuk’s group points towards the possibility that groups with intermediate cop numbers are rare. We expect the following two results to hold, but do not have an opinion on the answer to Question K . Conjecture 6.2 . Hyperbolic groups have weak cop number 1 or \infty . 2 2 2 This has been shown to be true in [ 13 ] during the publication process of this paper. Conjecture 6.3 . Finitely presented groups have cop numbers 1 or \infty . Figure 10. The Cayley graph of the infinitely generated group G=\langle s_{2},s_{3}\ldots\colon(s_{n})^{n}=1\rangle with respect to the generating set S=\{s_{2},s_{3},\ldots\} has weak and strong cop numbers 2 . Remark 6.4 . Among infinitely generated groups, one can consider the Cayley graph of the group G=\langle s_{2},s_{3},\ldots\colon(s_{n})^{n}=1\rangle with respect to the generating set S=\{s_{2},s_{3},\ldots\} to obtain a graph \Gamma with \operatorname{sCop}(\Gamma)=\operatorname{wCop}(\Gamma)=2 , see Figure 10 . However, for infinitely generated groups, the Cayley graphs for different generating sets may not be quasi-isometric, so the cop numbers may not be invariants of the group either.