Small Cancellation and Dehn Algorithms

Let $N=⟨\text{\hspace{0.17em}⁣}⟨R⟩\text{\hspace{0.17em}⁣}⟩$. Because $N$ is normal by [F1], it contains $r^{-1}$ whenever it contains $r$, and it contains $ur{u}^{-1}$ for every $u\in F(X)$. Hence [L1] implies that every element of $R^{\mathrm{sym}}$ already lies in $N$. Therefore $⟨\text{\hspace{0.17em}⁣}⟨R^{\mathrm{sym}}⟩\text{\hspace{0.17em}⁣}⟩\subseteq N$.

Every relator of $R$ belongs to $R^{\mathrm{sym}}$ by definition, so the normal closure of $R^{\mathrm{sym}}$ contains $R$. By the minimality clause of [F1], $N\subseteq ⟨\text{\hspace{0.17em}⁣}⟨R^{\mathrm{sym}}⟩\text{\hspace{0.17em}⁣}⟩$.

The two containments from steps 1.1 and 1.2 are equalities, so the normal closures agree.

Let $r=p_1\cdots p_n$ be a factorisation of a relator into pieces. Applying [L1] to each $p_i$ gives $\mathrm{\mid }{p}_i\mathrm{\mid }<\lambda \mathrm{\mid }r\mathrm{\mid }$ for every $i$. Summing these inequalities yields $\mathrm{\mid }r\mathrm{\mid }={\sum }_{i=1}^n\mathrm{\mid }{p}_i\mathrm{\mid }<n\lambda \mathrm{\mid }r\mathrm{\mid }\mathrm{.}$

Because every relator is nonempty, $\mathrm{\mid }r\mathrm{\mid }>0$. Thus step 1.1 implies $1<n\lambda$, hence $n>1\mathrm{/}\lambda$. This is exactly the $C(\lambda )$ condition from [L1].

We prove the stronger assertion that every closed edge walk in $D$ has label equal to the identity in the presented group. First suppose there are no faces. This finite connected graph has no cycle, including a loop edge or a two-edge cycle formed by parallel edges. Indeed, given a cycle, map one of its edges once around $\mathbb{R}\mathrm{/}\mathbb{Z}$, with both endpoints sent to $[0]$, and map every other edge to $[0]$. The edge maps agree at vertices and therefore define a continuous map on the graph. The cycle maps to a once-around circle loop, with constant pauses. A contraction of the cycle in the graph would contract that circle loop, contrary to [F2]. Thus the graph is a tree.

If a face remains, let $K$ be the union of the closures of all faces. This is a nonempty compact planar set with nonempty interior; its frontier lies in the finite $1$-skeleton. The frontier contains a point in an edge interior. Otherwise the frontier would be a finite set of vertices: deleting those vertices would separate the nonempty interior of $K$ from its nonempty exterior, whereas any two points of the plane minus finitely many points can be joined by a polygonal path with small detours around those points. At an edge-interior frontier point exactly one of the two planar sides is occupied by a face. Thus that edge $e$ occurs exactly once in the attaching boundary of one face $f$ and in no other face boundary. Two occurrences, even from the same face, would occupy both sides and make the point interior to $K$. This proves the required free-edge assertion locally.

A finite tree with an edge has a leaf: an endpoint of a longest simple path cannot have an additional neighbour off the path, which would extend it, or on the path, which would create a cycle. Each visit to a leaf other than the basepoint of a closed walk immediately returns along the same edge; delete those inverse pairs. If the walk is based at the leaf, its label has the form $aw{a}^{-1}$, where $w$ is the label of a closed walk at the neighbouring vertex; delete internal leaf excursions from that walk first. Induction after deleting the leaf edge makes $w$ trivial and hence also $aw{a}^{-1}$. The remaining one-vertex graph has only the empty edge walk. This proves the assertion in the face-free case.

Delete the open face $f$ and the open edge $e$, retaining all other cells, and call the resulting subcomplex $D^{\mathrm{\prime }}$. It is a deformation retract of $D$. To see this without assuming that the whole diagram is a disc, parameterize the characteristic polygon of this one face as the triangle $0\le x\le 1$, $0\le y\le \min (x,1-x)$, with the free edge as its base. The homotopy $(x,y)\mapsto (x,(1-t)y+t\min (x,1-x))$ fixes the complementary two sides and moves the triangle onto them at $t=1$. It descends through every identification on the complementary attaching walk because those points stay fixed; the open base has no other attachments by step 1.2. For a monogon, the complementary walk is a single vertex: instead contract its characteristic disc linearly to that boundary vertex. Extend either homotopy by the identity on all other cells. Consequently $D^{\mathrm{\prime }}$ is still finite, connected, planar and simply connected, and has one fewer face. Repeated vertices or edges in the complementary walk cause no difficulty.

Orient $e$ from $u$ to $v$, and let $p$ be the complementary attaching walk from $u$ to $v$ around $f$. The closed walk $e{p}^{-1}$ reads a cyclic conjugate of a specified relator or its inverse. It is therefore trivial in the presented group, so the labels of $e$ and $p$ agree there; their inverse labels agree as well. This uses normal closure, not a supposition that the specified relator set is closed under cyclic conjugation.

In any given closed edge walk, replace each occurrence of $e$ by $p$, and each inverse occurrence by $p^{-1}$. This gives a closed walk in $D^{\mathrm{\prime }}$ with the same group label. Induction on the finite number of faces, using steps 1.1 and 2.1 as the base and step 2.2 for the smaller diagram, makes its label trivial. Thus every closed edge walk in $D$ has trivial label. The finite choices of edges and paths used here require no axiom of choice.

The literal outer boundary walk is one such closed walk. Its bridges, repeated vertices, starting point and orientation do not affect the conclusion. Its label is therefore the identity in the presented group, equivalently an element of the normal closure of the relators in the free group.

If $w$ is the boundary label of a finite van Kampen diagram, then [L1] says that $w$ represents the identity in $G$.

Conversely, suppose that $w$ represents the identity in $G$. Then its free-group element lies in the normal closure of $R$, so [F1] gives an equality in the free group $[w]={\prod }_{k=1}^m[u_k{r}_k^{{\epsilon }_k}{u}_k^{-1}]$ with $r_k\in R$ and ${\epsilon }_k\in \{\pm 1\}$. Choose finite word representatives $u_k$; let $v$ be the literal concatenation of the displayed conjugate words. Thus $v$ and $w$ are freely equivalent by [F2], but need not be identical strings. Factors whose specified relator word is empty, or freely trivial, may be omitted without changing the free-group product.

We record the elementary boundary surgery that converts one free cancellation without creating a face. Suppose the literal outer word contains consecutive inverse letters, read on boundary edge occurrences $e:A\to B$ then $f:B\to C$. If these are the two traversals of one edge, they bound an exterior spur; erase it. Otherwise the edges are distinct. In a narrow collar of the exterior sector at $B$, fold $e$ against $f$, matching their labels and identifying $A$ with $C$. The face sides adjacent to these edges now lie on opposite sides of the folded edge. If $A$ and $C$ were distinct vertices, the collar surgery identifies two adjacent boundary sides of a planar disc neighbourhood of the complex; cutting open along the folded edge recovers that disc, so the surviving complex remains embedded, connected and simply connected. If $A=C$, the pair cuts off a closed planar petal (possibly pinched at $A$); its face-filled part becomes a sealed sphere under the fold. Delete that sealed part before drawing the surviving complex in the plane. Any outside component meets the petal only at $A$, since the sector between $e$ and $f$ at $B$ was exterior; hence deletion leaves the other outer-boundary edge occurrences and their order intact. This can lower, but cannot raise, the number of faces. In both cases the new literal outer word is the old one with exactly these adjacent letters deleted. If no edge remains, retain a base vertex. Conversely, to insert an inverse pair at a specified position, attach a new pendant edge in that exterior sector; its outward and return traversals insert precisely the two letters and no face. This also covers the two orientations of a cancellation and cut vertices.

For each remaining factor take one polygonal face with the specified boundary word $r_k^{{\epsilon }_k}$ and attach to a chosen face vertex a path labelled by the literal word $u_k$, from a common basepoint. Put these face-and-path complexes in disjoint planar sectors meeting only at that basepoint, in the order of the factors. Each path is a bridge traversed outward and back by the outer walk, so the resulting finite connected simply connected planar complex has literal boundary word $v$ and exactly $m$ faces. If $m=0$, use the one-vertex diagram with empty boundary word. A relator of length one gives a monogon; omitted empty or freely trivial relators need no face.

By [F2] there is a finite sequence of free cancellations and reverse insertions carrying $v$ to the specified literal word $w$. Apply step 1.3 to each word in that sequence. The result is a finite van Kampen diagram with boundary label exactly $w$ and at most $m$ faces. This also covers a freely trivial $w$: start at the one-vertex diagram and insert the required exterior spurs.

Steps 1.1 and 3.1 prove both directions of the equivalence, for arbitrary specified relator words and the literal boundary-label convention.

Let $D$ be any van Kampen diagram for $w$ with $m$ faces. We show by induction on $m$ that $[w]$ is a product of at most $m$ conjugates of defining relators or their inverses in the free group. For $m=0$, $D$ is a tree by the graph argument in [L2]'s cited proof; its outer walk freely reduces to the empty word, including the one-vertex case.

Conversely, let $[w]={\prod }_{k=1}^m[u_k{r}_k^{{\epsilon }_k}{u}_k^{-1}]$ be an algebraic expression with $m$ minimal as in [F1]. The converse construction in [L1] produces a diagram whose literal boundary word is $w$ and whose face count is at most $m$. Therefore the minimal diagram area is at most the algebraic relator area.

Suppose $m>0$. A generic ray from an interior point of the finite union of face closures to infinity crosses edge interiors and avoids vertices. At its last exit from that union it crosses an edge $e$ with one face on its inner side and the unbounded complementary region on its other side, so $e$ occurs once in the outer walk. Collapse that face across $e$ as in [L2], obtaining a planar simply connected diagram $D^{\mathrm{\prime }}$ with $m-1$ faces. Write the old outer word from the fixed basepoint as $aeb$, with $e$ denoting its oriented label, and let $p$ be the complementary face-boundary walk joining the same edge endpoints. The new outer walk reads $apb$ (including any bridge traversals). Consequently $[aeb][apb{]}^{-1}=[ae{p}^{-1}{a}^{-1}]$, a conjugate of the cyclic face label, hence of a defining relator or its inverse. By induction $[apb]$ needs at most $m-1$ factors, so $[w]$ needs at most $m$. Thus the algebraic area is at most every diagram area.

Steps 1.1 and 2.1 give one inequality between the two minima and step 1.2 gives the reverse inequality. Therefore the two minimal areas are equal.

Suppose $D$ were not reduced. Then by [L1] there would be two adjacent 2-cells whose common edge can be cancelled. Delete those two faces and glue together the remaining boundary arcs.

The surgery of step 1.1 does not change the outer boundary word, but it removes exactly two 2-cells. By [F1], the new diagram therefore has strictly smaller area than $D$.

This contradicts the assumed minimality of $D$. Hence $D$ is reduced.

Interpret $D$ with the toolkit conventions. For a fixed prefix $p$, a literal word has a unique suffix after $p$, so the distinct pairs $(r,u)$ and $(s,v)$ in the original piece definition are distinct exactly when $r\mathrm{\ne }s$. Thus the piece conditions agree. Reversing one face orientation across a shared edge also identifies the two definitions of a cancellable face pair. The diagrams and their outer walks are identical, not replacements by minimum-area diagrams. If the symmetrised set contains the empty word, discard it: it labels no polygonal face and contains no nonempty piece, so this changes none of the hypotheses on $D$.

Choose an end disc block using [F5]. If the block tree has just one block, it is a disc because $D$ has a face. Otherwise a finite tree has at least two ends, as seen from the endpoints of a longest simple path. An end bridge gives a spur, whose incoming and outgoing boundary occurrences are inverse. Freely reducedness excludes such a pair unless it straddles the chosen start of the literal boundary word. Only the spur at that starting vertex can do this, so there is at most one end bridge. Some other end is therefore a disc block. This argument permits a whisker at the starting vertex; freely reduced does not mean cyclically reduced.

Apply [F3] and [F4] to this block, keeping the original word lengths. The block has the same face words and cancellation condition as in $D$, hence the same strict piece bounds. A one-face block is a zero-shell. For a multi-face block, [F4] supplies a shell with at most three internal arcs whose exterior arc avoids its attachment vertex internally. If the block is all of $D$, mark the boundary word's starting vertex instead and use the same two-shell argument. No minimum-area replacement is made.

Expand the suppressed vertices. The selected face remains the same face of $D$; its exterior arc is contiguous in the full outer walk by the attachment qualification in [F4]. Other blocks attach only at the selected block's attachment vertex, not along an edge, so its internal arcs remain internal arcs of $D$. That vertex is not internal to any such arc. Expansion therefore gives at most three maximal internal arcs of $D$, as required. In the zero-shell case the full face circuit is the contiguous excursion at the attachment.

If $D$ had no faces, [F1] would make it a tree. Every nontrivial closed walk in a tree has immediate backtracking, contradicting the freely reduced nontrivial boundary word. Thus $D$ has a face, and by [L1] some boundary face $f$ of $D$ is a shell whose inner boundary is a concatenation $q_1\cdots q_i$ of maximal internal arcs with $0\le i\le 3$. (For $i=0$, this is the empty concatenation.) Let $p$ be the complementary outer arc of $\mathrm{\partial }f$ lying on $\mathrm{\partial }D$.

If $i=0$, the sum of the inner-arc lengths is $0<\mathrm{\mid }\mathrm{\partial }f\mathrm{\mid }\mathrm{/}2$. If $1\le i\le 3$, each internal arc $q_j$ is a piece by [L2], including a possible self-incident arc. The strict $C^{\mathrm{\prime }}(1\mathrm{/}6)$ bound in [L2] gives $\mathrm{\mid }{q}_j\mathrm{\mid }<\mathrm{\mid }\mathrm{\partial }f\mathrm{\mid }\mathrm{/}6$, and hence $\mathrm{\mid }{q}_1\mathrm{\mid }+\cdots +\mathrm{\mid }{q}_i\mathrm{\mid }<i\frac{\mathrm{\mid }\mathrm{\partial }f\mathrm{\mid }}{6}\le \frac{\mathrm{\mid }\mathrm{\partial }f\mathrm{\mid }}{2}\mathrm{.}$ Thus in every case the total inner-arc length is less than half of $\mathrm{\mid }\mathrm{\partial }f\mathrm{\mid }$.

Since $\mathrm{\partial }f$ is the disjoint union of the outer arc $p$ and the inner arcs $q_1,\dots ,q_i$, step 2.1 gives $\mathrm{\mid }p\mathrm{\mid }=\mathrm{\mid }\mathrm{\partial }f\mathrm{\mid }-(\mathrm{\mid }{q}_1\mathrm{\mid }+\cdots +\mathrm{\mid }{q}_i\mathrm{\mid })>\frac{\mathrm{\mid }\mathrm{\partial }f\mathrm{\mid }}{2}\mathrm{.}$ Thus $f$ contributes more than half of its boundary to the outer boundary of $D$.

By [L1], the Dehn replacement sends $w=ausb$ to $w^{\mathrm{\prime }}=a{v}^{-1}sb$ before free reduction. Because $\mathrm{\mid }u\mathrm{\mid }>\mathrm{\mid }v\mathrm{\mid }$, one has $\mathrm{\mid }{w}^{\mathrm{\prime }}\mathrm{\mid }=\mathrm{\mid }w\mathrm{\mid }-\mathrm{\mid }u\mathrm{\mid }+\mathrm{\mid }v\mathrm{\mid }<\mathrm{\mid }w\mathrm{\mid }$.

Free reduction can only delete inverse pairs, never add letters. So the freely reduced form of $w^{\mathrm{\prime }}$ is no longer than $w^{\mathrm{\prime }}$, hence still strictly shorter than $w$.

Start by freely reducing $w$. Whenever the current freely reduced word contains a relator subword longer than half of a defining relator, perform the corresponding Dehn replacement and freely reduce again. By [L1], each such cycle strictly decreases word length, so no infinite run is possible. Thus the algorithm terminates.

Each replacement uses a relation $uv=1$ in the group and swaps $u$ for $v^{-1}$, so every step preserves the group element represented by the current word. Therefore if the algorithm reaches the empty word, the original input represented the identity.

Conversely, suppose the input represents the identity. After each iteration the current word is freely reduced and still represents the identity by step 2.1. If the current word were nonempty when the algorithm stopped, it would be Dehn-reduced by construction, contradicting the defining property of a Dehn presentation. Therefore the algorithm cannot stop before reaching the empty word, and termination from step 1.1 forces the final output to be empty.

Steps 2.1 and 3.1 prove correctness, and step 1.1 proves termination. Therefore Dehn's algorithm decides the word problem for the presentation.

By [L1], every nonempty freely reduced trivial word has the required long relator subword in its original linear reading. Thus the symmetrised finite $C^{\mathrm{\prime }}(1\mathrm{/}6)$ presentation is a Dehn presentation in the sense of [F1].

Apply [L2] to that Dehn presentation. The resulting Dehn algorithm decides triviality of words.

Freely reduce $w$ to a word $u$. Because free reduction does not change the represented group element, $u$ is still null, and $\mathrm{\mid }u\mathrm{\mid }\le \mathrm{\mid }w\mathrm{\mid }$. If $u$ is the empty word, then the null diagram with no faces has area $0$, so the claim is immediate. Otherwise let $D$ be a minimal-area van Kampen diagram for $u$. By [L2], the diagram $D$ is reduced, so [L1] applies.

By [L1], some face $f$ of $D$ contributes a contiguous outer boundary arc $p$ with $\mathrm{\mid }p\mathrm{\mid }>\mathrm{\mid }\mathrm{\partial }f\mathrm{\mid }\mathrm{/}2$. Write $u=apb$ as a literal word from the chosen boundary basepoint, and orient the relator boundary of $f$ as $pq$. Its complementary arc $q$ has $\mathrm{\mid }q\mathrm{\mid }<\mathrm{\mid }p\mathrm{\mid }$. The word $a{q}^{-1}b$ represents the same group element as $u$, since $pq$ is a conjugate of a defining relator; let $u^{\mathrm{\prime }}$ be its free reduction. Then $u^{\mathrm{\prime }}$ is null and $\mathrm{\mid }{u}^{\mathrm{\prime }}\mathrm{\mid }\le \mathrm{\mid }a\mathrm{\mid }+\mathrm{\mid }q\mathrm{\mid }+\mathrm{\mid }b\mathrm{\mid }<\mathrm{\mid }u\mathrm{\mid }$. In the free group, $[u]=[a(pq)a^{-1}][a{q}^{-1}b]$, so the algebraic relator area of $u$ is at most one plus that of $u^{\mathrm{\prime }}$. By [F1], diagram and algebraic relator areas agree for both words; hence $\mathrm{Area}(u)\le \mathrm{Area}(u^{\mathrm{\prime }})+1$.

Induct on the freely reduced boundary length. Step 1.1 gives the base case $\mathrm{\mid }u\mathrm{\mid }=0$. For $\mathrm{\mid }u\mathrm{\mid }>0$, step 2.1 yields a shorter freely reduced null word $u^{\mathrm{\prime }}$. By the induction hypothesis, $\mathrm{Area}(u)\le \mathrm{Area}(u^{\mathrm{\prime }})+1\le \mathrm{\mid }{u}^{\mathrm{\prime }}\mathrm{\mid }+1\le \mathrm{\mid }u\mathrm{\mid }\mathrm{.}$ Because $\mathrm{\mid }u\mathrm{\mid }\le \mathrm{\mid }w\mathrm{\mid }$, this is a linear isoperimetric inequality.

Finally, [F1] identifies van Kampen area with algebraic relator area, so the same linear bound holds in the algebraic formulation.

Because $g$ is a nontrivial torsion element in the stated symmetrised $C^{\mathrm{\prime }}(1\mathrm{/}6)$ presentation, [F2] applies. It supplies a cyclic conjugate $r^{\mathrm{\prime }}=vu$ of a defining word $r=uv$ and a word root $c$ of $r^{\mathrm{\prime }}$ such that $g$ is conjugate to a power of the image of $c$. In the symmetrised relator set, $r^{\mathrm{\prime }}$ is itself a defining relator; equivalently $r^{\mathrm{\prime }}$ and $r$ are conjugate in the free group. Thus this is a power of a root of a defining relator as claimed.

Powers are interpreted as in [F1], so step 1.1 is exactly the claimed conclusion.

The identity has finite order and needs no argument. Suppose for a contradiction that $g\mathrm{\ne }1$ is a torsion element. By [L1], $g$ is conjugate to $v^k$, where some defining relator has the form $v^m$.

The no-proper-power hypothesis forces $m=1$. Thus the root word $v$ is itself a defining relator and represents the identity in the presented group, so every power $v^k$ is trivial by [F1]. Hence $g=1$, contradicting step 1.1.

Since no nonidentity torsion element exists, the group is torsion-free.

The reduced subword $ab$ appears twice inside $r$, namely in positions $1$ through $2$ and $3$ through $4$. So it is certainly a repeated subword of one relator.

The cyclic conjugates of $r$ are only $abab$ and $baba$, while the cyclic conjugates of $r^{-1}$ start with inverse letters. Among these symmetrised occurrences, $ab$ is an initial segment only of $abab$, and in that word the continuation is always the same suffix $ab$. Therefore there is no second distinct ordered pair $(s,v)$ with $s=abv$, so [L1] says that $ab$ is not a piece.

So a repeated interior subword need not be a piece. The statement is false.

In the displayed one-relator presentation, the symmetrised relator set has no nontrivial piece: distinct cyclic conjugates begin with different letters, and the inverse cyclic conjugates do as well. Hence the $C^{\mathrm{\prime }}(1\mathrm{/}6)$ condition holds vacuously by [L1].

The unique defining relator has length $7$, which is strictly greater than $6$.

So a $C^{\mathrm{\prime }}(1\mathrm{/}6)$ presentation can have relators longer than $6$. The statement is false.

The relator $ab{a}^{-1}{b}^{-1}$ and its cyclic conjugates have long overlaps, so the presentation does not satisfy the $C^{\mathrm{\prime }}(1\mathrm{/}6)$ hypothesis required by [L1].

In the square grid van Kampen diagrams for commutator powers in ${\mathbb{Z}}^2$, every face can meet the outer boundary in exactly two of its four edges, never in more than half. Thus the characteristic Greendlinger conclusion fails for these null words.

Therefore Greendlinger's lemma does not extend to arbitrary finite presentations. The statement is false.

The word $x_1{x}_2{x}_3{x}_4{x}_5{x}_6{x}_7$ is freely reduced, because no adjacent inverse letters occur.

Nevertheless [L1] applies to the whole word: it is itself a relator and is longer than half of that relator, so one Dehn move replaces it by the empty word.

Thus a word can admit a Dehn reduction while admitting no free reduction. The two notions are different, so the statement is false.

Neither relator $a{b}^2$ nor $a^{2}b$ is a proper power: each is cyclically reduced of length $3$ and is not a repetition of a shorter cyclic word.

From $a{b}^2=1$ one gets $a=b^{-2}$, and substituting this into $a^{2}b=1$ gives $b^{-4}b=1$, hence $b^3=1$ in the sense of [F1]. Moreover, if $C_3=⟨t\mid t^3=1⟩$, then the assignment $a\mapsto t$, $b\mapsto t$ satisfies both relators, so it induces a surjective homomorphism $G\to C_3$. Therefore the image of $b$ is nontrivial and $G$ contains a nontrivial torsion element.

Therefore the absence of proper-power relators alone does not force torsion-freeness. By [L1], the missing small-cancellation hypothesis is load-bearing.