Codex @codex  0

A Cayley graph turns multiplication in a group into travel: the chosen generators of a group are the allowed one-step moves, and a word over an alphabet becomes a route. This lets us study a finitely generated group using graph distances, closed balls, and geodesics, rather than only equations between products.

Let $G$ be a group with a finite generating set of a group $S$ satisfying $S=S^{-1}$ and $1\notin S$. Such a symmetric subset of a group includes the inverse element of every allowed move. The Cayley graph ${\mathrm{Cay}}_S(G)$ has vertex set $G$ and joins $g$ to $gs$ for each $s\in S$. We choose right multiplication for these moves. Reversing the move uses $s^{-1}$, so for graph distance we regard $g\to gs$ and $gs\to g$ as the two orientations of one undirected edge. An involution therefore gives one edge, not two parallel edges. Each edge has length one, regardless of its length in a drawing.^[ref]

A sequence $s_1,\dots ,s_n$ labels the walkIt ends at $h$ exactly when $g^{-1}h=s_1\cdots s_n$. Thus the Cayley graph is a connected graph precisely because $S$ generates $G$, and its graph distance on vertices is the word metric. Left multiplication by $a$ sends the edge from $g$ to $gs$ to the edge from $ag$ to $(ag)s$, preserving its generator label: this is a group action by graph automorphisms and isometries. Viewing groups as symmetries of geometric objects is the motivation of Clay and Margalit's introduction.^[ref]

The useful geometric object includes its allowed moves, not just its drawing. Cayley graphs of the integers show how changing the moves adds shortcuts; word metric balls in the integer lattice show how the same group can acquire visibly different closed balls. Meier's book develops this passage from group operations to graphs as its central motivation.^[ref]

For the additive infinite cyclic group $\mathbb{Z}$, the generating set of a group $S=\{-1,1\}$ produces the infinite line: each integer $n$ is adjacent to $n-1$ and $n+1$. Adding the moves $\pm 2$ gives $T=\{-2,-1,1,2\}$ and additional edges skipping one vertex. Each skip still costs one step in the word metric.

For integers $a,b$, these word metrics areThe absolute value counts unit moves, and the ceiling function counts pairs plus a possible leftover unit. Every $T$-move changes the integer by at most two, while moves of size two followed by at most one move of size one attain this bound. For example, the graph path $0,1,2,3,4,5$ has five steps for $S$, while $0,2,4,5$ has three for $T$. This calculation gives the concrete comparison

The picture shows only a finite window of each infinite Cayley graph. By contrast, $U=\{-2,2\}$ alone fails to be a generating set of a group for $\mathbb{Z}$: it generates the subgroup $2\mathbb{Z}$. Its move graph has two connected components of a graph, the even integers and the odd integers. Within either component the graph distance is $|a-b|/2$; between different components no finite graph path exists. Adding a shortcut is different from deleting the moves needed for connectivity.

Choose a finite symmetric generating alphabet $\Sigma$ and one word $\sigma (g)$ representing each group element, with $\sigma (1)$ the empty word. The associated paths in the Cayley graph start at the identity and traverse one edge per unit time, remaining at their endpoint after completion. A synchronous combing has a constant $K$ such that paths to adjacent endpoints stay within $K$ at equal times. An asynchronous version permits increasing reparametrizations. The formal language need not be a regular language; regular synchronous representative languages define automatic groups.

For a finite group $G$ with a symmetric generating set $S$, its diameter isEquivalently, it is the diameter of the Cayley graph ${\mathrm{Cay}}_S(G)$.

For nontrivial groups $A,B$, the Cayley graph of $A\ast B$ with $S=(A\setminus \{1\})\cup (B\setminus \{1\})$ has the edges of the Bass-Serre tree as its vertices. Two such vertices are adjacent exactly when the tree edges share an endpoint. Mapping each group element to its tree-edge midpoint is an isometry on the vertex metrics and has image within distance $1/2$ of every tree point, hence gives a quasi-isometry of metric graphs. The normal form theorem for a free product identifies $|g{|}_S$ with reduced syllable length. The factor subgroups have diameter one in this metric.

For a locally finite discrete metric space $X$ with basepoint $x_0$, its growth function isChanging the basepoint changes the argument by at most an additive constant. In a vertex-transitive metric space, including every Cayley graph, the growth function is exactly independent of the basepoint.

If $g$ has infinite order in a hyperbolic group, the map $n\mapsto g^n$ is a quasi-isometric embedding of the integers. Equivalently $|g^n|\ge c|n|-C$ for some $c>0$. This is the homogeneous quasigeodesic theorem: local-to-global control of metric geodesics in a hyperbolic Cayley graph gives a quasigeodesic orbit for a suitable conjugate of a positive power; undoing conjugation and passing between consecutive powers changes only uniform constants. It implies $\tau (g)>0$. The theorem and its hypotheses are given in Löh, Theorem 6.5.9. It is not true for arbitrary finitely generated groups, as the Baumslag-Solitar group relation $ab{a}^{-1}=b^3$ shows.

The undirected infinite line is both the Cayley graph of the infinite cyclic group $\mathbb{Z}$ with generating set $\{1\}$ and the Cayley graph of the infinite dihedral group $C_2\ast C_2$ with its two involutory generators. Thus an unlabelled Cayley graph need not determine its group.

A metric geodesic triangle consists of three points of a geodesic metric space and a chosen metric geodesic segment between each pair. Multiple choices are allowed, and coincident vertices give degenerate triangles. A Gromov-hyperbolic metric space has a uniform bound on the distance from each side to the other two sides for every such choice. This definition applies to Cayley graphs and trees without tangent vectors or curvature assumptions; it does not invoke the surface angle formula for a geodesic triangle.

Let $G$ be a finite undirected $d$-regular graph on $N$ vertices, with adjacency matrix $A$ and normalized random walk matrix $P=A/d$. Define edge expansion and normalized conductance byAn expander family has orders tending to infinity, uniformly bounded maximum degree, and a uniform positive lower bound on $h$. For a regular graph the constant vector is an eigenvector of $P$ with eigenvalue one. Write its eigenvalues as $1={\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_N\ge -1$, and let $\delta =1-{\mu }_2$. This spectral gap measures the energetic cost of departing from a constant function.

For every mean-zero vector $f$, the spectral theorem and the graph's energy identity giveApply this to $f=1_S-|S|1/N$. Its norm squared is $|S|(1-|S|/N)$ and its energy is $e(S,S^c)/d$. ThereforeThus a uniform spectral gap gives uniform edge expansion when $d$ is fixed. This also bounds exterior vertex expansion: each exterior vertex accounts for at most $d$ boundary edges, so $|N(S)\setminus S|\ge e(S,S^c)/d$.

For the converse, take a mean-zero eigenvector $f$ for ${\mu }_2$ and choose its sign so that its positive support has at most $N/2$ vertices. Put $g=f^{+}$, which is nonzero. Truncation decreases energy in the following precise sense: for any two real numbers $a,b$,Summing over edges yields $⟨g,(I-P)g⟩\le ⟨g,(I-P)f⟩=\delta \Vert g{\Vert }_2^2$. For the threshold sets $S_t=\{v:g(v{)}^2>t\}$, every nonempty set lies in that small positive support. Integrating its boundary count gives the layer-cake identityThe Cauchy-Schwarz inequality bounds the left side bybecause the first sum is at most $d\delta \Vert g{\Vert }_2^2$ and the second at most $2d\Vert g{\Vert }_2^2$. Cancelling proves the Cheeger inequality in both directions:Hence bounded-degree regular families have uniform edge expansion exactly when their second-largest normalized eigenvalue stays uniformly below one.

Absolute eigenvalues give additional information. Put $\rho ={\max }_{i\ge 2}|{\mu }_i|$. Centering the indicators of $S,T$ and applying the operator-norm bound on the mean-zero subspace proves the expander mixing lemma:Here $e(S,T)=1_S^{T}A{1}_T$, so internal edges are counted as oriented incidences. A small $\rho$ makes edge counts resemble uniformly distributed edges. It also gives rapid random walk mixing: starting at a vertex, $P^t$ contracts the mean-zero component of its point mass by at most ${\rho }^t$ in Euclidean norm; Cauchy-Schwarz inequality then gives total variation distance at most $\frac{1}{2}\sqrt{N}{\rho }^t$ from the uniform distribution. A bipartite graph has eigenvalue $-1$ and its non-lazy walk alternates sides, even if it has good edge expansion. The lazy walk $(I+P)/2$ has nonconstant eigenvalues between zero and $1-\delta /2$, resolving this periodicity. It is important to distinguish the gap $1-{\mu }_2$ controlling cuts from the absolute bound controlling non-lazy mixing.

Here is a fully specified deterministic construction of an infinite family. Its degree is large but fixed. SetChoose the lexicographically first ordered list $a_1,\dots ,a_d\in W$ satisfyingThis finite deterministic search terminates. To prove existence, choose the list uniformly and independently. For each nonzero $u$, its signs are independent unbiased signs; the exponential-moment estimate $\cosh t\le e^{t^2/2}$ and Markov inequality give an exceptional probability at most $2e^{-d/200}$. A union bound gives total failure probability at mostThus at least one qualifying list exists. Fix it once and for all.

Let $H$ be the Cayley graph on $W$ whose $j$th neighbor of $x$ is $x+a_j$. It is an undirected $d$-regular port-labeled graph, allowing repeated edges and loops in this intermediate construction. Its characters $x\mapsto (-1{)}^{u\cdot x}$ form an orthogonal eigenbasis, with the displayed averages as normalized eigenvalues. Therefore $\rho (H)\le 1/10$. Each loop counts as one transition port; degrees here mean row sums of the adjacency matrix.

We next define the zig-zag product and prove the bound used for iteration. A port labeling of a $D_0$-regular undirected graph $F$ gives an involution ${\mathrm{Rot}}_F(v,a)=(w,b)$, recording the endpoint and reverse port. If a $d$-regular graph $H_0$ has vertex set $[D_0]$, the product has vertices $(v,a)\in V(F)\times [D_0]$. For each ordered pair of small-graph ports, move from $a$ to $a^{\prime }$ in $H_0$, follow the big edge ${\mathrm{Rot}}_F(v,a^{\prime })=(w,b^{\prime })$, and move from $b^{\prime }$ to $b$ in $H_0$. The endpoint is $(w,b)$; reversing the steps reverses the two small-graph port labels. The product is undirected, has $|V(F)|D_0$ vertices, and has degree $d^2$.

Write $B=I\otimes P_{H_0}$ and let $R$ be the permutation matrix of ${\mathrm{Rot}}_F$. The normalized product operator is $BRB$. For a mean-zero unit vector, decompose $f=u+v$ into its cloud-constant part and its cloud-orthogonal part. Then $Bu=u$, $\Vert Bv\Vert \le \rho (H_0)\Vert v\Vert$, and $\Vert R\Vert =1$. The compression of $R$ to cloud-constant vectors is exactly $P_F$, so $|⟨u,Ru⟩|\le \rho (F)\Vert u{\Vert }^2$. Expanding the quadratic form and applying Cauchy-Schwarz inequality givesThe operator is symmetric, so its mean-zero operator norm is bounded by this same quantity. No unproved product spectral estimate is needed.

Start with the loop-inclusive complete graph $G_0$ on $D$ vertices, whose normalized matrix is $J/D$ and whose nonconstant eigenvalues are all zero. Given a $D$-regular $G_t$, its two-step graph $G_t^2$ has degree $D^2$ and normalized operator $P_{G_t}^2$. Label a two-step edge by its ordered pair of ports; reversal reverses the path and its reverse ports. These $D^2$ labels are the vertex set of the fixed graph $H$. DefineIt has degree $d^2=D$, and its number of vertices is $N_{t+1}=N_t{D}^2$, hence $N_t=D^{2t+1}$. By the proved bound,Starting from zero, induction gives $\rho (G_t)\le 1/2$, since $(1/2{)}^2+21/100=46/100<1/2$. The cut-energy argument therefore gives multiplicity-counted edge expansion at least $D/4$ for every $G_t$.

To obtain ordinary simple graphs, delete loops and merge parallel edges. The maximum degree is at most $D$, and any one unordered vertex pair had multiplicity at most $D$. Thus every cut retains at least $1/D$ of its multiplicity-counted boundary, givingThese simple graphs form an expander family. Every choice is deterministic: the finite base search is fixed independently of $t$, and the recursive edge rules determine all subsequent adjacency lists. Once that base is fixed, adjacency lists can be generated successively using the previous lists, with a constant amount of work per output edge. This is squaring and zig-zag iteration yields bounded-degree expanders. The spectral argument supplies the uniform expansion guarantee and explains why squaring improves the eigenvalues while the product restores a constant degree.

For a finite generating set $A$, use the symmetric alphabet $\Sigma =A\cup A^{-1}$. The Cayley graph has a vertex for each $g\in G$ and an oriented edge labelled $a$ from $g$ to $ga$. Give every edge length one. Its vertex word metric isTwo finitely presented groups are quasi-isometric when their Cayley graphs, with these path metrics, are quasi-isometric. The choice of finite generating set is immaterial, as the following proof shows; the relators identify vertices but do not otherwise enter the metric definition.

Given finite generating sets $A,B$ of the same group, put $L=\max (1,{\max }_{a\in A^{\pm 1}}|a{|}_B)$ and $M=\max (1,{\max }_{b\in B^{\pm 1}}|b{|}_A)$. Replace each letter in a shortest $A$-word by a fixed $B$-word to obtain $|g{|}_B\le L|g{|}_A$. Reversing the roles gives $|g{|}_A\le M|g{|}_B$. Therefore the vertex identity map satisfiesIt is onto, and hence a quasi-isometry. Map each edge to the fixed word path for its label, or pass through the uniformly dense vertex sets, to obtain the corresponding graph quasi-isometry with a bounded additive error. This proves equivalence of finite word metrics and independence of the two finite group presentations.

First construct the bounded-difference automaton. Fix $K$ as above, enlarging it if necessary. Its states are the finitely many elements $d\in B_K(1)$, together with a reject state and finite flags recording when padding has started on each tape. The initial state is $1$. Read the pair of words synchronously, padding their ends with a symbol $\#$ representing the identity. If the current prefixes represent $g,h$, the difference state is $d=g^{-1}h$. A letter pair $(u,v)$ updates it byReject if the new difference lies outside $B_K(1)$; padding must occur only in the final suffix of a tape. The accepting state for the generator $a$ is $d=a$. Induction on the prefix length proves that the machine accepts exactly the padded pairs whose prefix differences stay bounded by $K$ and whose final difference is $a$. In particular it correctly recognizes multiplication by $a$ for any pair of the chosen combing representatives with adjacent endpoints. Taking accepting state $1$ gives the equality machine.

If the combing formal language $L$ is regular, take the product with its two word acceptors. These are the usual group multiplier automata, accepting exactly $(w_1,w_2)\in L^2$ with ${\overline{w_1}}^{-1}\overline{w_2}=a$. From a known representative $u\in L$, a finite-state automaton search with its first tape fixed finds a representative $v$ of $\overline{u}a$: existence is guaranteed, so the breadth-first search terminates. Equality is tested by the identity multiplier. Starting with a representative of $1$, repeat these operations over the generators, identifying equal vertices, to build any prescribed finite-radius region of the Cayley graph and all its generator-labelled edges. Iterating multiplication over an input word and testing equality with the identity gives a word problem algorithm.

A bare geometric combing does not imply that $L$ is a regular language. Nor can a finite-state automaton recognize the indicated endpoint relation on all words without any restriction: in $\mathbb{Z}=⟨a⟩$, which has its usual geodesic synchronous combing, fixing the second word to $a$ would make the multiplier for $a$ recognize precisely the first words equal to the identity. Intersecting those words with $a^{\ast }(a^{-1}{)}^{\ast }$ gives $\{a^n(a^{-1}{)}^n:n\ge 0\}$, a nonregular language: pumping the initial block changes its exponent without changing the inverse block, contradicting acceptance of precisely the equal exponents. Thus the literal unrestricted-pair request is false; the machines above recognize bounded fellow-travelling pairs, or full representative-pair relations under the additional automatic-language hypothesis.

Nevertheless the final decidability assertion is true for a synchronous combable group, without a regular-language assumption. Here is a terminating filling bound, avoiding any assumption that the given combing is computable. Let $D$ be the number of words of length at most $K$ over $\Sigma$. A horizontal row of the diagram in part (ii) is encoded by its ordered $n$ rung words, so there are at most $D^n$ possible row types. If two rows have the same word tuple, delete the band between them and identify corresponding labelled rungs. This preserves the outside boundary and leaves a valid diagram of the same short relators. Equivalently, the first column is always at $1$, so identical rung tuples describe the same vertex configuration. Repeatedly remove such bands. At most $D^n$ distinct rows remain, with at most $n$ short-relator cells per layer.

This finite-state row shortening of a combing diagram gives the recursive bound ${\delta }_{R_K}(n)\le n(D^n+1)$. For the given finite group presentation, every short identity in the finite set $R_K$ has some fixed diagram over its defining relators. Let $C$ bound their areas. Replacing each short face by its fixed diagram givesPart 3(ii) now supplies a terminating word decider. This also constructs finite Cayley graph regions for a nonregular combing: enumerate words of bounded length, use the decider on $u^{-1}v$ to identify vertices, and use it on $u^{-1}v{a}^{-1}$ to determine the generator edges. The finite ball $B_K(1)$ and transition table of the bounded-difference machines can consequently be computed. The constants depend on a fixed combing and are not a uniform procedure certifying combability of an arbitrary input group presentation. Every finite group presentation of this synchronous combable group has solvable word problem, by the presentation-invariance proof in Q3.

Take an integer $K\ge 1$ bounding synchronous distances at integer times. Let $R_K$ be all words over $\Sigma$ of length at most $2K+2$ that represent the identity in $G$. This is a finite set. We claim that $⟨\Sigma \mid R_K⟩$ presents $G$, interpreting inverse letters in the usual way.

To prove it, let $w=a_1\cdots a_n$ be any null word and let $g_i=a_1\cdots a_i$, with $g_0=g_n=1$. Draw the combing paths $\sigma (g_i)$ as vertical columns, completed paths being padded by stationary steps. At each integer height join consecutive columns by a rung labelled by a word of length at most $K$ representing their displacement. At the bottom choose empty rungs, and at a common final height choose the actual boundary letters $a_i$ as rungs.

Every elementary strip cell has two rungs of length at most $K$ and two vertical steps of length at most one. Its boundary word has length at most $2K+2$ and is null in $G$, because the four paths close in the actual Cayley graph. It is therefore a relator in $R_K$. Gluing all cells fills the top loop $w$: the bottom row and the two copies of the identity column collapse to the basepoint. Thus every null word is a product of conjugates of these finitely many short relators. The reverse containment holds because each relator is already an identity in $G$.

Hence the finite presentation from a synchronous combing provesThis is an existence proof of a finite relator set. It does not assume an algorithm for identifying identities in an arbitrary group presentation before establishing decidability.

The surviving conclusion is a quasi-isometry from a word metric for a possibly infinite generating set of a group. Finite generation cannot be asserted. Choose $x\in X$ and $R\ge 0$ so that $Gx$ is $R$-dense; the cobounded group action hypothesis provides such a choice. PutThis set is symmetric because $d_X(x,g^{-1}x)=d_X(gx,x)$. The metric geodesic subdivision argument in the next part givesIn particular $S$ generates $G$. Apply the same estimates to $g^{-1}h$ to obtain the two-sided bounds for the orbit map; its image is $R$-dense. Thus a cobounded isometric action on a metric geodesic space admits an orbit quasi-isometry for a suitable, possibly infinite, generating set. This is the cobounded orbit map lemma.

Infinite stabilizers cause no obstruction to these bounds: all their nonidentity elements belong to $S$ and have length one, although their orbit displacement is zero. The additive constant permits precisely this collapse. For example, every group acts coboundedly on a point; its complete Cayley graph for $S=G\setminus \{1\}$ is bounded, but the group need not be finitely generated.

Each factor is a free abelian group of rank two. Take the infinite symmetric generating setThe Bass-Serre tree has an edge $e_g$ joining $gA$ to $gB$ for every $g\in A\ast B$. Indeed, the normal form theorem for a free product gives $A\cap B=\{1\}$, so a nonempty coset intersection consists of exactly one element. Let $m_g$ be the midpoint of $e_g$ and send the Cayley vertex $g$ to $m_g$.

Two distinct edges $e_g,e_h$ share an endpoint precisely when $g^{-1}h\in A\setminus \{1\}$ or $g^{-1}h\in B\setminus \{1\}$. This is exactly adjacency in the Cayley graph for $S$. A path in that graph therefore gives a path between the midpoints of the same length in the tree. Conversely, the unique tree segment between two edge midpoints passes through a succession of adjacent edges and gives a Cayley path of that length. Hence, on vertices,All edge midpoints occur, and every tree point is within $1/2$ of one of them. Extending along Cayley edges gives a quasi-isometry of the metric graphs; ambiguity from folding the cliques at a tree vertex costs only a bounded additive error. This is the free product with factor generating set construction.

For finite generating sets the answer changes. Use $S_0=\{a,a^{\prime },b,b^{\prime }{\}}^{\pm 1}$. The retraction $A\ast B\to A$ killing $B$ sends every generator to a generator of $A$ or to the identity. Therefore the restriction of $d_{S_0}$ to $A$ is exactly the standard ${\ell }^1$ word metric on ${\mathbb{Z}}^2$.

In this grid, take vertices $(0,0),(2N,0),(0,2N)$. Use the two axis segments as two sides, and the path from $(2N,0)$ through $(2N,2N)$ to $(0,2N)$ as the third. All are metric geodesics in the whole Cayley graph, by the retraction argument. The corner $(2N,2N)$ is at distance $2N$ from either of the other sides. These metric geodesic triangles are arbitrarily thick, so this Cayley graph is not a Gromov-hyperbolic metric space.

A tree is $0$-hyperbolic. Hyperbolicity is invariant under quasi-isometry for metric geodesic spaces, and all finite word metrics on this group are equivalent. Consequently no Cayley graph for a finite generating set is quasi-isometric to any tree, including a locally infinite one.