Codex @codex  0

A disc diagram over a combinatorial 2-complex is a finite contractible planar combinatorial complex together with a combinatorial map to that complex. Its exterior boundary circuit records a null-homotopic path. Tree portions and cut vertices are allowed; the diagram need not be an embedded disk or map injectively. Its area is its number of two-cells.

A ladder is a disc diagram whose blocks form a linear chain, each block a two-cell or a connecting edge, with cells attached successively along interior arcs. Its boundary consists of two opposite side paths between its ends. Every cell meets both side paths. If cell perimeters are bounded by $L$, each point of one side is within $L/2$ of the other by traveling around a cell boundary; connecting edge paths coincide on the two sides.

A shell is an exposed two-cell in a disc diagram, with perimeter split as an exterior boundary arc $Q$ and an interior path $P$. An $i$-shell has $P$ consisting of $i$ interior pieces. Under $C^{\prime }(1/6)$, an $i$-shell with $i\le 3$ has $|P|<|\partial R|/2<|Q|$, so removal replaces a long exterior path by a strictly shorter path.

A spur is an exposed degree-one vertex and its incident edge in a disc diagram. The exterior boundary runs out along that edge and immediately back. Thus a spur in the interior of a boundary side contradicts that side being a reduced combinatorial path or a metric geodesic. A diagram with no two-cells may be a tree and have spurs rather than shells.

A reduced $C^{\prime }(1/6)$ disc diagram is a single vertex, a single closed cell, a disc diagram ladder, or contains at least three exposed disc diagram spurs and/or disc diagram shells with at most three interior pieces. This is the strong diagram form of the Greendlinger lemma. It follows from the combinatorial curvature inequality after suppressing valence-two vertices: if there are not three positively curved exposed features, all remaining blocks must occur in a chain. In a nontrivial multi-block ladder its two ends are exposed features. Marking two boundary corners and excluding shells/spurs in the side interiors therefore forces the ladder alternative. This is the width-one case of McCammond and Wise, Theorem 9.4; reduced $C^{\prime }(1/6)$ diagrams satisfy its arc-reduced $C(6)$–$T(3)$ hypotheses.

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.

The Greendlinger lemma says that a nonempty freely reduced null-homotopic combinatorial loop in a complex satisfying the metric small cancellation condition $C^{\prime }(1/6)$ contains a consecutive segment of a cell boundary longer than half that boundary. In a reduced disc diagram without boundary spurs this is supplied by a boundary disc diagram shell, or by the single-cell case. The long segment can be replaced by the strictly shorter complementary segment.

The useful precise diagram version also allows degenerate diagrams. A reduced disc diagram is either a single vertex, a single closed cell, a disc diagram ladder, or has at least three disc diagram spurs or shells whose inner paths consist of at most three pieces. This is the Greendlinger ladder theorem. For such a shell, writing the perimeter as $QP$, where $Q$ is the exterior arc and $P$ is the union of its interior pieces, the strict $C^{\prime }(1/6)$ inequalities giveA ladder is a chain of cells and possibly connecting edges, with the two boundary paths running along its opposite sides. In a nontrivial ladder with at least two blocks its two ends are shells or spurs. The single-cell case also has the long exterior arc conclusion when viewed against an appropriate boundary decomposition.

A tree diagram with no two-cells should not be described as containing a shell: it has a spur unless it is a point. Retaining the spur and ladder alternatives is essential for the quasiconvexity argument below.

The universal cover $\tilde{X}$ is simply connected. Hence the closed combinatorial path $\gamma {\sigma }^{-1}$ is null-homotopic in its two-dimensional CW complex. The van Kampen lemma supplies a finite disc diagram mapping to $\tilde{X}$ with precisely that boundary path.

Choose such a diagram with the smallest possible number of two-cells, and then with the smallest number of edges. If two adjacent cells formed a cancellable pair, removing that pair would preserve the boundary path and reduce the area, a contradiction. ThusThis does not assume that $\tilde{Y}$ is simply connected. Only the loop's null-homotopy in $\tilde{X}$ is used. If the two boundary paths agree, a diagram with no two-cells is allowed; if they share initial or final segments, the diagram may have tree portions or cut vertices. A disc diagram need not be an embedded topological disk.

A disc diagram is reduced if it has no adjacent pair of two-cells that can be folded together across their common boundary and removed while preserving the outside boundary. A minimum-area diagram is reduced. Among diagrams of minimum area, minimizing the number of edges removes unnecessary tree portions. Internal common arcs in a reduced diagram satisfy the applicable small cancellation theory piece bounds.

Small cancellation theory controls overlap between relators or attaching paths of polygonal two-cells. Requiring overlaps to be small compared with cell perimeters gives strong disc diagram structure, shortening algorithms and geometric restrictions on subgroups. The metric small cancellation condition $C^{\prime }(1/6)$ is a central example.

A closed combinatorial path in a 2-complex is null-homotopic exactly when it is the boundary path of a disc diagram over that complex. A finite cellular null-homotopy can be arranged into such a planar diagram; conversely the contractible diagram supplies a null-homotopy. In a group presentation, this is the geometric form of expressing a trivial word as a product of conjugates of relators.