Parametricity

Infinite Games in Hyperbolic Groups

Posted at — Jul 9, 2014

The other day I was sitting in The Coop in Cambridge, reading a book on combinatorial games, and so naturally I started wondering about games played in groups, or on their Cayley graphs at least. After a short T ride home, I discussed the idea with my roommate and I settled on the following game:

Let $G$ be a group with a specified presentation $\langle a_1, \dots, a_m \mid R \rangle$ and let $\Gamma$ be the corresponding Cayley graph. Fix some $k : \mathbb{N}, k \geq 1$. Then the game $E_{\Gamma, k}$ is played as follows:

There are two players, which for vividness I’ll call Rocket and Gravity. The players start on some vertex $v_0$ corresponding to the identity $e$ in $G$. The two players alternate turns, starting with Gravity. On its first move, Gravity moves to any vertex $v_1$ adjacent to $v_0$. Since we are in a Cayley graph, this amounts to choosing a generator.

Now suppose it is the $(i + 1)^{\text{th}}$ turn. If it is Gravity‘s turn, then as before, they select an adjacent vertex $v_{i + 2}$, but now we must have $v_{i + 1} \neq v_i$. In other words, the players may not backtrack. In yet other words, the word in $G$ corresponding to the path the players are building must be freely reduced. If it is **Rocket**‘s turn, they are allowed to choose $v_{i + 2}$ to be any vertex within $k$ edges of $v_{i + 1}$, again subject to the restriction that they may not move from $v_{i + 1}$ to $v_i$.

For each $i$, let $w_i$ be the word labelling a shortest path from $v_0$ to $v_i$. Then Gravity wins if $$ \limsup_{i \to \infty} |w_i| = \infty $$ and **Rocket** wins otherwise. I.e., if $$ \limsup_{i \to \infty} |w_i| < \infty $$ So, **Gravity** is trying to pull our hero away to infinity, while **Rocket** must struggle nobly till the end of time to stay within some bounded neighborhood of the origin.

The question then is, for a given $\Gamma$, what is the least $k$ such that Rocket has a winning strategy for the game $E_{\Gamma, k}$. Since $\Gamma$ is the Cayley graph of a finitely presented group, we have a weak upper bound (assuming every generator appears in some relator). Namely $\max_{r \in R} |r| - 1$, where $R$ again is our collection of relators. If **Rocket** has this many moves, then their winning strategy is simply to complete some relator containing the generator just chosen by **Gravity**.

It seems clear that in some cases this must be a lower bound as well. For example, consider the genus 2 surface group $\langle a, b, c, d \mid [a, b][c, d]\rangle$, shown above. If Rocket is given only 6 moves per turn, it seems clear that Gravity can succeed in pushing us out to boundary.

In fact this is the case, and we can say something more general: Take any group $G = \langle a_1, \dots, a_m | R \rangle$ with corresponding Cayley graph $\Gamma$, and let’s assume that $R$ is symmetrized (closed under inverses and cyclic permutations) for convenience. If $G$ is $C’(1/6)$ and for any $a_i$ there is an $a_j$ such that $a_i a_j$ does not appear as a subword of any relator in $R$, then Rocket requires at least $\max_{r \in R} |r| - 1$ moves per turn to have a winning strategy. Using the same proof, we can say something more general than this, but it is a bit complicated to state, so I won’t mention it for now.

So let’s prove this. We’ll give Rocket $\ell := \max_{r \in R} |r| - 2$ moves per turn, and construct a winning strategy for **Gravity**.

To prove this we’ll use, as with all facts about small cancellation groups, Greendlinger’s lemma.

The logic proof is to exhibit a strategy for Gravity such that

  1. If it’s Gravity‘s turn and a geodesic segment corresponding to the current position is $w$, then Gravity can choose a generator $a$ such that $wa$ is still geodesic. In other words, Gravity can increase the distance from the origin by 1 on each turn.

  2. If it’s Rocket‘s turn and a geodesic segment corresponding position is $w$, then for any $s$ of length at most $\ell$ (not backtracking on $w$) the length of the shortest word equal to $w\ell$ (which I’ll denote $|w\ell|$ is at least $|w|$. That is, Rocket can never decrease the distance to the origin.

It then follows that the $w_i$ are getting monotonically longer, so the strategy succeeds.

I’ll follow up this post eventually with proofs and pictures.