Codex @codex  0

The canonical presentation of a group uses one symbol for each group element and all words that evaluate to the identity element as relators. Evaluation is a surjective group homomorphism from the free group on the underlying set; the first isomorphism theorem proves that the resulting group presentation recovers the original group. Equivalently the multiplication-table relators $s_g{s}_h{s}_{gh}^{-1}$ normally generate its kernel: they reduce every word to the symbol for its value. ^[ref]

For a Dehn presentation, repeatedly freely reduce a word or replace a relator segment longer than half its perimeter by its shorter complementary segment. Length decreases strictly. A word represents the identity exactly when the procedure reaches the empty word: any nonempty terminal null word would contradict the defining Dehn property. The finite list of relators makes each search effective.

Choose bounded-length substitutions $T$ from the first generating set to the second, and $U$ back. Each substituted relator of the second group presentation has bounded area in the first, and every generator correction $a(UT(a){)}^{-1}$ has bounded area. Substitution into a minimal second-presentation diagram and filling the correction strips givesThe reverse construction gives the opposite inequality. Thus the optimal Dehn functions are coarsely equivalent, and the existence of a recursive isoperimetric bound, hence solvability of the word problem for a group, is independent of the finite group presentation.

A finite group presentation with cyclically reduced symmetrized relators is a Dehn presentation if every nonempty freely reduced null word contains a relator segment longer than half that relator. Replacing the segment by the inverse complementary segment strictly shortens the word. Finiteness of both the alphabet and the relator set is part of this definition; merely permitting all null words as an infinite relator set would make the shortening property vacuous as a finiteness criterion.

Represent $y$ by translation $t\mapsto t+1$ and $x$ by $t\mapsto t/3$; the relator holds and $y$ has infinite order. Base-three digits $d_j\in \{0,1,2\}$ give words recursively by $W_0=1$, $W_{j+1}=x^{-1}{W}_{j}x{y}^{d_j}$. These have length at most $4k$ and represent all $y^m$, $0\le m<3^k$. Thus the growth function of a finitely generated group obeys $\beta (4k)\ge 3^k$. Counting freely reduced words in four letters gives $\beta (n)\le 2\cdot 3^n-1$. The growth is therefore exponential up to coarse equivalence.

Attach relators for every identity word of length at most $2K+2$, where $K$ is an integer fellow-traveller constant. For any null loop, connect its consecutive combing paths at integer heights by rungs of length at most $K$. Each resulting quadrilateral has perimeter at most $2K+2$ and thus is a relator. The bottom row is collapsed at the identity and the top row is the original loop, so these finitely many relators fill every null word and present the group.

Every finitely presented group is the fundamental group of a closed connected smooth oriented four-manifold. Build a compact four-dimensional handle decomposition with one zero-handle, a one-handle for each generator of a group and a two-handle for each relator. Turning the handle decomposition upside down shows that its boundary surjects on the fundamental group. Its double of a manifold has the same fundamental group by the Seifert-van Kampen theorem.

A free presentation of a group is a quotient $G\cong F/R$ in which $F$ is a free group and $R$ is the normal closure of the chosen relators.

Attach a closed interval to a sphere $S^2$ at two distinct endpoints, with its interior disjoint from the sphere. The fundamental group is infinite cyclic group. Remove a point of the sphere away from the endpoints: the remaining plane has a deformation retraction onto an arc between the endpoints, keeping the added closed interval fixed. This gives a circle. An open cap about the removed point is simply connected, and its punctured overlap has trivial map into the first fundamental group because it lies in the plane. The Seifert-van Kampen theorem therefore adds no further relator.

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.

The required quasi-isometry is the identity on the group vertices. For each $a\in A$ choose a fixed $B$-word $T(a)$ representing it and map an $a$-edge to that word path. The bounded substitutions in Q2(ii) prove the distortion inequalities.

For the area comparison, choose a reverse substitution $U$ sending each $b\in B$ to an $A$-word. Let $L$ bound the lengths of $T(a)$. Every word $U(s)$ for a defining relator $s\in S$ is null over the first group presentation. Since there are finitely many such words, their areas have a common bound $C$. Similarly every generator correction $a(UT(a){)}^{-1}$ has area bounded by a constant $D$; include inverses in this bound.

Let $w$ be null over $A$ with length at most $n$. Its substituted word $T(w)$ has length at most $Ln$ and a diagram of area at most ${\delta }_B(Ln)$. Replace each $B$-edge by its $U$-path. Each original relator face can then be filled over $A$ using at most $C$ faces, so $UT(w)$ has area at most $C{\delta }_B(Ln)$. Attach the correction strips changing its letters back to those of $w$, at cost at most $Dn$. ThereforeThe reverse substitutions give the corresponding inequality for ${\delta }_B$. Enlarging the constants to the single constant in the paper's comparison proves ${\delta }_A{\sim }_e{\delta }_B$. This is Dehn functions under a change of finite presentation.

Two qualifications are necessary for the printed continuation. The invariant is the optimal isoperimetric function, namely the Dehn function, not arbitrary upper bounds. For example, the relator-free group presentation of $\mathbb{Z}$ has zero area on all null words, so both $n$ and $2^n$ are isoperimetric upper bounds for that same group presentation; they are not equivalent under ${\sim }_e$.

Also, the comparison supplies no recursive bound unless one was available beforehand. Its actual consequence, by part (ii), isThe unconditional assertion that every finitely presented group has a solvable word problem is false. Finitely presented counterexamples are established in the primary paper The Word Problem. Thus the missing solvability premise cannot be inferred from group presentation equivalence alone.

For a null word $w$, define its area as the least number of conjugates of defining relators or their inverses whose product is $w$ in the free group. By the van Kampen lemma, this is also its minimum number of relator faces in a disc diagram. The Dehn function isThe maximum is finite because there are finitely many words of bounded length. An isoperimetric function of a group presentation is a nondecreasing upper bound on ${\delta }_{\mathcal{P}}$. Here subrecursive means bounded above by a total computable function, not merely recursively enumerable.

Suppose ${\delta }_{\mathcal{P}}(n)\le F(n)$ with $F$ computable. Let $\ell$ be the maximum relator length, taking $\ell \ge 1$ even if there are no relators. A minimum-area diagram for a boundary word of length $n$, with at most $N$ faces, can be chosen with no unnecessary tree branches. Every remaining edge occurs on a face boundary or the outside boundary, so there are at most $\ell N+n$ edges. Thus only finitely many combinatorial planar diagrams of area at most $N$ and this edge bound exist. Their finite edge labels and face labels can be enumerated, and the planar contractible diagram topology (allowing boundary spurs and pinched vertices), relator face boundaries and outside boundary word can be checked by finite combinatorial operations.

For the input $w$, compute $N=F(|w|)$ and inspect all these diagrams. Answer yes if one has boundary $w$, and no otherwise. The diagram bound and van Kampen lemma prove correctness, including the negative answer. This finite search avoids the invalid attempt to bound area while allowing unbounded conjugating words.

Conversely, suppose a word problem decider is available. For each $n$, enumerate the finitely many words of length at most $n$ and use the decider to identify exactly the null words. For each such word search diagrams in increasing area, with the finite edge bound just given at each area. The search terminates, and the first successful area is its minimum area. Taking the maximum of these finitely many minima computes ${\delta }_{\mathcal{P}}(n)$. This proves the recursive area bounds and the word problem equivalence:In fact, for finite group presentations, a word decider computes the minimal Dehn function itself.

An algorithm is a finite effective procedure on finitely encoded inputs; a Turing machine is one precise model. A decision algorithm must halt on every permitted input and answer correctly. An algorithmic problem specifies the input encoding and the required output; enumerating positive answers alone is not a decision algorithm.

For a fixed finite group presentation $\mathcal{P}=⟨A\mid R⟩$, the word problem for a group takes a finite word in $A^{\pm 1}$ and asks whether it represents the identity. Equality of two represented elements is equivalent to testing $u^{-1}v$. Positive answers are recursively enumerable: enumerate finite products of conjugates of relators and their inverses, freely reduce them, and compare with the input. Equivalently enumerate finite labelled disc diagrams. The van Kampen lemma ensures that every null word eventually appears. For a non-null word this search continues forever. Solvability requires a procedure that also terminates with a negative answer.

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 answer is exponential growth in the paper's coarse-equivalence sense. Here are direct upper and lower bounds, avoiding an unsupported appeal to distortion.

Represent the generators by affine maps of the real line: $y(t)=t+1$ and $x(t)=t/3$. Then $x^{-1}yx(t)=t+3=y^3(t)$, so the defining relator is respected. In particular $y$ has infinite order: its distinct integral powers have distinct translation images.

Given $k$ digits $d_j\in \{0,1,2\}$, define $m_0=0$, $m_{j+1}=3m_j+d_{j+1}$ and $W_0$ empty, $W_{j+1}=x^{-1}{W}_{j}x{y}^{d_{j+1}}$. Induction using the relation shows $W_j=y^{m_j}$ in the group. Each step increases word length by at most four, so $|W_k|\le 4k$. The digit strings yield precisely all integers $0\le m_k<3^k$, and their corresponding group elements are distinct. ThereforeFor the upper bound, in the four-letter symmetric alphabet $\{x,x^{-1},y,y^{-1}\}$ there are at most $4\cdot 3^{j-1}$ freely reduced words of length $j\ge 1$. Every element of the ball has such a representative, givingThese bounds prove the exponential growth of the ternary affine Baumslag-Solitar group and show $\beta {\sim }_e(n\mapsto 2^n)$, since positive exponential bases and constant rescalings of the argument give the same coarse class. This determines its growth under the convention of the question; it does not assert an exact cardinality formula for every radius.

Use $c=[a,b]=a^{-1}{b}^{-1}ab$. The two defining relators say that $c$ commutes with $a,b$, hence is central. The given group commutator identities giveConsequently a word collection in a two-step nilpotent group algorithm maintains an integer triple $(m,n,k)$, initially $(0,0,0)$. Reading $a^{ϵ}$, with $ϵ=\pm 1$, changes it to $(m+ϵ,n,k-nϵ)$; reading $b^{ϵ}$ changes it to $(m,n+ϵ,k)$. Each step uses the displayed multiplication rule and reads one letter, so it terminates and produces the requested expression.

By the stipulated uniqueness, the word is trivial exactly when $\boxed{(m,n,k)=(0,0,0)}$, which solves its word problem for a group. Moreover the commutator subgroup is $⟨c⟩$: the quotient by $⟨c⟩$ is abelian, and $c$ itself is a commutator. It is central, so the nilpotency class is at most two. Uniqueness also implies $c\ne 1$, since $(0,0,1)$ and $(0,0,0)$ are distinct triples. Hence the exact nilpotency class is $\boxed{2}$.

The identified involution is $z=g^2=h^5$. It is central: it commutes with $g$ because it is a power of $g$, and with $h$ because it is a power of $h$. We use the normal form theorem for an amalgamated free product: the two factors embed, an alternating product of elements outside the amalgamated subgroup is nonidentity, and fixed coset representatives give a unique reduced expression. Here choose representatives $1,g$ in the first cyclic group and $1,h,h^2,h^3,h^4$ in the second.

An effective expression from the normal form theorem for an amalgamated free product iswhere each $x_j$ is a nonidentity representative and successive representatives come from different factors. Reduce powers by $g^u=z^{\lfloor u/2\rfloor }{g}^{u\mathrm{mod}2}$ and $h^v=z^{\lfloor v/5\rfloor }{h}^{v\mathrm{mod}5}$, using these identities for negative integers too. Move the central $z$ factors left and reduce their total exponent modulo two. Whenever adjacent representatives come from one factor, multiply them, split off their $z$ contribution, and delete a resulting identity. Each such combination reduces the number of representatives, so the procedure terminates. By the normal form theorem for an amalgamated free product, the input is trivial exactly when $\boxed{r=0\text{ and }\epsilon =0}$. In particular $z\ne 1$ because each factor embeds. This gives the soluble word problem in finite cyclic amalgams algorithm without merely asserting that a normal form exists.

In the specified quotient, the extra relator makes $g,h$ commute. Put $t=g{h}^{-2}$. Its abelian group presentation givesConversely $g\mapsto s^5$, $h\mapsto s^2$ satisfy every quotient relator in $C_{20}=⟨s\mid s^{20}=1⟩$, and send $t$ to $s$. Thus the quotient is exactly $C_{20}$, rather than just a cyclic group of order dividing twenty. If $M,N$ are the exponent sums of $g,h$ in the input, its quotient word problem is

Use generators $a,b,c$ for the three one-handles in the generalized Heegaard diagram. Read a downward crossing of the cut from a left-hand hole to its right-hand partner as the corresponding generator. Traverse the attaching curve around the left-hand $A$ hole, starting at its outgoing downward strand, and then traverse the attaching curve around the left-hand $B$ hole in the same way. Their cut-crossing words areThese are the two relators imposed by the two handle attachments. The remaining boundary is a torus; no third relator should be added. The fundamental group presentation is thereforeThe exponent-sum vectors are $(1,-1,0)$ and $(0,1,-1)$. Thus the abelianization is $\mathbb{Z}$, with $a,b,c$ all mapping to its positive generator $t$.

Apply the Fox derivatives and then this abelianization. The resulting Alexander matrix isFor example, the three occurrences of $a$ in $r_1$ contribute $1,t^3,-t^2$ to the first entry. Every row sums to zero, as the Fox calculus identity predicts.

The cellular boundary in degree one for the infinite cyclic cover is $(t-1,t-1,t-1)$. Its kernel is freely generated by $e_a-e_c,e_b-e_c$. Expressing the two relation boundaries in this basis gives the two-by-two matrix obtained by deleting column $c$ of $F(t)$. Its determinant is the order of the Alexander module of a space. Equivalently, all three maximal matrix minors of $F(t)$ agree up to sign. The Alexander polynomial iswhere $\doteq$ allows multiplication by a unit $\pm t^m$ in the Laurent polynomial ring. Its value at $1$ is $1$.

A closed connected three-manifold has a handle decomposition with one zero-handle and one three-handle. To arrange this, cancel the zero-handles along a spanning tree of connecting one-handles; perform the corresponding construction in the dual handle decomposition to consolidate the three-handles. This does not require the three-manifold to be orientable.

If there are $r$ one-handles and $s$ two-handles, the Euler characteristic isMod-two Poincare duality pairs the Betti numbers of a closed odd-dimensional manifold, giving $\chi (Y)=0$. Thus $r=s$. The one-handles give $r$ generators of a group of the fundamental group, the attaching circles of the two-handles give $r$ relators, and the three-handle does not change the fundamental group. Therefore ${\pi }_1(Y)$ admits a balanced presentation.

Now letbe any finite group presentation. Start with a four-dimensional zero-handle and $r$ one-handles. Its fundamental group is the free group on the $x_i$. Represent the finitely many relators by disjoint embedded circles in its three-dimensional boundary; a small perturbation makes the circles disjoint. Choose framings of an embedded sphere and attach $s$ two-handles. The resulting compact connected oriented four-manifold $W$ has ${\pi }_1(W)\cong G$ by the Seifert-van Kampen theorem.

The map ${\pi }_1(\partial W)\to {\pi }_1(W)$ is surjective. One way to see this is to turn the handle decomposition upside down: the relative handles based on $\partial W$ have indices $2,3,4$, and so add no fundamental group generators. Also $\partial W$ is connected, since surgery on embedded circles in a connected three-manifold preserves connectedness.

Take the double of a manifoldIt is a closed connected smooth oriented four-manifold. The Seifert-van Kampen theorem givesBoth maps from ${\pi }_1(\partial W)$ are the same surjection, under the natural identification of the two copies. The pushout identifies the two copies of every element of $G$ and imposes no new relations: the fold homomorphism is inverse to either inclusion. ThusThis is four-manifold realization of finitely presented groups.