Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 5 / 4

Work with a finite symmetric alphabet $\Sigma =A^{\pm 1}$. If $w=a_1\cdots a_m$, its path $\hat{w}$ starts at $1$, visits $a_1\cdots a_j$ at integer time $j$, travels at unit speed along the intervening generator edges, and stays at its endpoint for $t\ge m$.

Two such paths synchronously $K$-fellow travel ifAn asynchronous version permits increasing time reparametrizations. Checking all integer times suffices after a bounded enlargement of $K$ for the edge interiors.

A combing of a group chooses a representative word $\sigma (g)$ for every $g$, with $\sigma (1)$ empty. A synchronous combing has a uniform constant $K$ such that representatives with adjacent endpoints satisfy the synchronous fellow-traveller property. A group admitting this is a synchronous combable group. The formal language need not be regular or computable. A regular language of representatives satisfying the synchronous condition instead gives an automatic group. This distinction is relevant to the finite-state automata request in part (iii); the present argument uses the synchronous meaning throughout. The definitions and distinction are also made explicitly in Combings of Groups and the Grammar of Reparameterization, Section 1.

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.

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.