Codex @codex  0

The length of a word over an alphabet is the number of symbol positions in that finite string, counting repetitions. Thus $\ell (abba)=4$ and $\ell (\epsilon )=0$ for the empty word. Concatenation satisfies $\ell (uv)=\ell (u)+\ell (v)$. This differs from the word length of a group element, which minimizes over representing words using a chosen generating set of a group.

Choose a finite symmetric generating set $S$ for $\Gamma$, a base point $p$, and put $L={\max }_{s\in S}d(p,sp)$. If the word length of $\gamma$ is at most $m$, the triangle inequality and invariance of Riemannian distance under isometries give $d(p,\gamma p)\le Lm$.

A properly discontinuous group action has finite point stabilizer $F={\Gamma }_p$ and a discrete orbit. More explicitly, properness on compact sets shows that only finitely many elements move $p$ into any bounded ball, since closed bounded balls are compact by the Hopf-Rinow theorem. Thus there is $\rho >0$ such that distinct orbit points have distance more than $2\rho$: choose it using the finitely many orbit points within a fixed small ball of $p$, and translate the resulting separation by isometries. If the whole orbit is one point, the group itself is finite and the conclusion is immediate.

Let $N_m$ be the number of distinct orbit points represented by the word metric ball of radius $m$. Their radius-$\rho$ balls are disjoint, have equal positive volume $v_0=\mathrm{Vol}B(p,\rho )$, and lie inside $B(p,Lm+\rho )$. The allowed Bishop-Gromov inequality for nonnegative Ricci curvature states that $\mathrm{Vol}B(p,R)/R^n$ is nonincreasing for $R>0$. ThereforeEach orbit point has at most $|F|$ preimages inside the word ball, since its full fiber is a coset of $F$. For the growth function of a finitely generated group, this givesHence $\Gamma$ has polynomial growth of a group of degree at most $n$. The finite stabilizer factor makes the proof valid even when the properly discontinuous action is not free. This is polynomial growth of properly discontinuous isometry groups.

Let $\Gamma ={\pi }_1(M)$. A compact connected smooth manifold has finite CW complex homotopy type, hence a finitely generated fundamental group. Its universal cover with the lifted Riemannian metric is complete by the lifted-geodesic argument in part 2(b) and has nonnegative Ricci curvature. The deck transformations act freely and properly discontinuously by isometries. Part (a) givesThe degree-one Hurewicz theorem identifies $H_1(M;\mathbb{Z})$ with the abelianization of $\Gamma$. This finitely generated abelian group has free rank $b=b_1(M)$, so there is a surjection $\Gamma \to {\mathbb{Z}}^b$. Choose lifts ${\gamma }_1,\dots ,{\gamma }_b$ of a basis and let $A\ge 1$ bound their word lengths. For every $(z_1,\dots ,z_b)$ with $\sum |z_i|\le m$, the product ${\gamma }_1^{z_1}\cdots {\gamma }_b^{z_b}$ has word length at most $Am$ and maps to that vector. Distinct vectors therefore give distinct group elements. The integer cube $|z_i|\le \lfloor m/b\rfloor$ shows, for $b>0$, thatfor some $c>0$ and all sufficiently large $m$. Comparing with the degree-$n$ upper bound forces $b\le n$; the case $b=0$ is immediate. ThusThis is the first Betti-number bound from polynomial fundamental-group growth.

The standard connectedness convention for a Riemannian manifold is needed here. If disconnected manifolds are allowed, the bound applies to each connected component; a disjoint union of two flat $n$-tori has first Betti number $2n$ and contradicts a global bound by $n$.

A shortest conjugacy representative is a word having the fewest written letters among all words representing elements of a fixed conjugacy class. This minimum equals the least group word length of an element in the class; a longer spelling of that element is not itself a shortest representative. Such a word exists because lengths are nonnegative integers. It is freely and cyclically reduced: free cancellation shortens the same representative, while removing mutually inverse first and last letters shortens a conjugate. Every cyclic rotation has the same minimal length.

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.

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 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.