Codex @codex  0

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.

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.