Word metric ($d_S$)

The word metric measures how many allowed moves are needed to change one group element into another. For a finite symmetric generating set of a group $S$ with $1\notin S$, it is the graph distance between vertices of the Cayley graph, equivalentlyHere word length counts letters in a shortest representative of $g^{-1}h$. The path metric on the entire Cayley graph also permits points inside edges; the word metric is its restriction to the group itself.^[ref]

The word metric is left invariant:This corresponds to the label-preserving group action on the Cayley graph. Symmetry follows by reversing a shortest graph path; concatenating routes gives the triangle inequality.^[ref]

Right invariance can fail in a non-abelian group, because right multiplication replaces $g^{-1}h$ by $a^{-1}{g}^{-1}ha$ through conjugation. In the free group $F(x,y)$ with $S=\{x,x^{-1},y,y^{-1}\}$, we have $d_S(1,y)=1$, whereas $d_S(x,yx)=|x^{-1}yx{|}_S=3$: the latter freely reduced word has three letters. In an abelian group, conjugation fixes each element, so right invariance does hold. Cayley graphs of the integers and word metric balls in the integer lattice give examples where the word metric can be calculated explicitly.

The closed word metric ball of radius $r\ge 0$ centred at a group element $g$ isThis is a closed ball for the word metric. A finite generating set of a group gives a finite word metric ball, because at most ${\sum }_{k=0}^{\lfloor r\rfloor }|S{|}^k$ words over an alphabet can represent its elements. Different words over an alphabet may represent the same element, so this is an upper bound. Word metric balls in the integer lattice give exact counts for two choices of moves.

The additive group ${\mathbb{Z}}^2$ gives a useful way to see what a word metric measures. Let $e_1=(1,0)$ and $e_2=(0,1)$, and choose the four-move generating set of a group $S=\{\pm e_1,\pm e_2\}$. Its Cayley graph is the square lattice. Each move changes exactly one coordinate by one, so the word length is the L1 norm, and the word metric is Manhattan distance:At least this many moves are necessary, and moving horizontally then vertically attains the bound. Bridson gives this square lattice as a basic Cayley graph example.^[ref]

Now allow all eight neighbouring lattice points as moves:Each coordinate changes by at most one per move. Use diagonal moves until the smaller displacement is exhausted, then use axis moves: the resulting word length is the maximum norm, and the word metric is Chebyshev distance. From $(0,0)$ to $(2,3)$, an $S$-route has five steps, while the $T$-route $(0,0),(1,1),(2,2),(2,3)$ has three.

The closed word metric balls $B_S(0,r)=\{v\in {\mathbb{Z}}^2:d_S(0,v)\le r\}$ consist of lattice points inside a diamond for $S$, and inside an axis-aligned square for $T$. For every nonnegative integer radius $r$,The diamond has $4k$ lattice points at word length $k>0$; the square has $2r+1$ choices for each coordinate. At radius three the counts are $25$ and $49$. These are discrete closed balls for Manhattan distance and Chebyshev distance; an Euclidean distance bound would instead select lattice points inside a Euclidean disk.

The word length is the cost of building a group element from the allowed generators of a group. For a symmetric generating set of a group $S$ of a group $G$, defineThe empty word over an alphabet represents the identity element and has length zero. A representative with this least number of letters labels a shortest graph path from $1$ to $g$ in the Cayley graph. Thus word length minimizes over all representatives, rather than counting the letters in whichever expression we happened to write down.^[ref]

For the additive integers with $S=\{-1,1\}$, the expression $1+1-1$ has three letters but represents $1$, whose word length is one. With $T=\{-2,-1,1,2\}$, the integer $5$ has word length three, realized by $2+2+1$. The Cayley graphs of the integers visualize why these are minimal. A freely reduced word is always shortest in a free group with its free generators and their inverses; free reduction alone need not give a shortest representative in a general group.

Concatenating representatives and reversing their letters with inverse elements giveThese make word length a length function. A finite $S$ gives finite word metric balls, since only finitely many words over an alphabet have length at most a fixed radius. The definition itself also works for infinite symmetric generating sets of a group; the bounded-metric example in equivalence of finite word metrics shows what finiteness adds.

For a word metric from a finite generating set, the stable word length isSubadditivity and the Fekete lemma give the limit. Conjugating $g^n$ changes its length by at most a constant, so stable word length is conjugacy invariant. It satisfies ${\tau }_S(g^k)=|k|{\tau }_S(g)$. Finite-order elements have zero stable word length; in a hyperbolic group, every infinite-order element has positive stable word length.

Changing a finite generating set of a group changes individual distances, but it cannot introduce arbitrarily large relative distortion. For two finite symmetric generating sets of a group $S,T$ of the same group, setEach $S$-letter can be replaced by at most $K$ $T$-letters, and conversely each $T$-letter by at most $L$ $S$-letters. Applying these substitutions to shortest representatives of $g^{-1}h$ givesThus the identity map is a bilipschitz equivalence between the two word metrics, and hence a quasi-isometry. The constants depend on the chosen generating sets of a group.^[ref]

In the Cayley graphs of the integers example, $S=\{-1,1\}$ and $T=\{-2,-1,1,2\}$ give $K=1$ and $L=2$: a unit move costs one in either alphabet, and a move of size two costs two unit moves. This recovers $d_T\le d_S\le 2d_T$. The diamond and square in word metric balls in the integer lattice obey the same comparison, because $\max \{|m|,|n|\}\le |m|+|n|\le 2\max \{|m|,|n|\}$.

Finiteness cannot simply be dropped from this universal statement. For the additive integers, take the infinite symmetric generating set of a group $U=\mathbb{Z}\setminus \{0\}$. Every nonzero displacement is a single allowed move, so $d_U(a,b)=1$ whenever $a\ne b$, whereas $d_S(0,n)=|n|$ for $S=\{-1,1\}$. There is no finite $L$ with $d_S\le L{d}_U$: choosing an integer $n>L$ violates it. This is a counterexample to unrestricted equivalence, not a claim that every infinite generating set of a group fails; two such sets with uniformly bounded generator lengths can still satisfy the same substitution bounds.^[ref]