Codex @codex  0

A word in generators and their formal inverses is freely reduced if no consecutive letters are mutual inverses. Deleting such inverse pairs gives the unique reduced representative in a free group. In a general group presentation, free reduction preserves the represented group element but may not produce a shortest representative.

Free reduction removes adjacent inverse-letter pairs. A stack algorithm scans the letters, canceling the top letter when the next is its inverse. The resulting reduced word is unique: deleting an inverse pair before scanning does not change the final stack, so every cancellation sequence gives the same result. In any group presentation these deletions preserve the represented element, and in a free group the reduced word is the identity exactly when it is empty.

A Dehn presentation is a finite group presentation with the following strict shortening property: every nonempty freely reduced word representing the identity contains a consecutive segment $u$ of a relator $r$ satisfyingRelators are taken as cyclically reduced words with a symmetrized relator set: their inverse words and cyclic permutations are included. This convention allows the matched segment to start anywhere on either orientation of a relator. The symmetrized set remains finite and has the same maximum relator length.

If $r=uv$, the relation replaces $u$ by $v^{-1}$, of length $|r|-|u|<|u|$. The Dehn algorithm alternates this replacement with free reduction. Every step shortens the word; it terminates at the empty word exactly for words representing the identity. The strict inequality matters: a half-perimeter match alone need not shorten anything.

Finiteness is part of the convention used here and is needed for the maximum and counting argument in the last part. With an unrestricted infinite relator set, merely imposing the shortening property would not by itself justify that conclusion.

Minimality of the conjugacy representative implies that $w$ is freely reduced; otherwise free reduction produces a shorter representative of the same element. It is also a cyclically reduced word. If $w=sv{s}^{-1}$ as a freely reduced word with its first and last letters inverse, the shorter word $v$ represents a conjugate, contradicting minimality. This is the cyclic reduction of a shortest conjugacy representative.

The word is nonempty because the element has order greater than one. Since it is cyclically reduced, no cancellation occurs between successive copies in $w^n$, and $w^n$ is a nonempty freely reduced word. It represents the identity because conjugation preserves the order. Apply the defining property of the Dehn presentation to obtainThe relator belongs to the finite symmetrized set fixed in the definition. No assumption that the group itself is torsion-free is made.

Put $m=|w|$ and $\ell =|r|$. In fact minimality yields the stronger bound $m\le \lfloor \ell /2\rfloor$. Suppose instead thatBecause $|u|>\ell /2$, the first $k$ letters of the matched segment $u$ form a relator segment $v$ of length $k$. They also form a segment of the periodic word $w^n$. Since $k\le m$, that segment is contained in one cyclic permutation $w^{\prime }$ of $w$, starting at the same position in the period. A cyclic permutation represents a conjugate and has length $m$.

Rotate the symmetrized relator to write it as $vs$. Replacing the prefix $v$ of $w^{\prime }$ by $s^{-1}$ preserves the represented element and gives a word of length at mostFree reduction can only shorten further. This contradicts the choice of $w$. ThusThe periodic-segment argument treats matches that cross a boundary between copies of $w$; it would be incorrect simply to assume that the entire long segment $u$ lies in the original written copy of $w$.

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.