Recognizing surface presentations of 3-manifold groups: decidability beyond the two-generator case and Whitehead degree bounds (Null's Questions 4.18 and 4.19)

A finite presentation of the fundamental group of a closed 3-manifold can be read off from a Heegaard diagram, and Null (2011) defined an s-presentation to be a presentation arising this way. The paper proved that deciding whether an arbitrary finite presentation presents a 3-manifold group is undecidable in general, that s-presentation membership is recursively enumerable, and that the two-generator case is decidable. The preprint leaves open, for three or more generators, whether recognizing s-presentations is decidable at all: no a priori bound is known on the geometric degree that must be searched to find an exact surface diagram or to certify that none exists. The problem asks (1) whether such a computable degree bound exists (Question 4.19) — an affirmative answer with a computable bound would yield a terminating decision procedure for s-presentation recognition — and (2) whether a diagram of minimal geometric degree within its Whitehead-homeomorphism class must also have minimal algebraic degree there (Question 4.18).

Background

Every closed 3-manifold $M$ (compact, without boundary) admits a Heegaard splitting: $M$ is obtained by gluing two handlebodies — a handlebody is a thickening of a wedge of circles — along their common boundary, a closed orientable surface $S$ of some genus $g$ . Such a splitting is encoded by a Heegaard diagram $(S; X, Y)$ : the surface $S$ together with two families $X = \{X_1,\dots,X_g\}$ and $Y = \{Y_1,\dots,Y_g\}$ of disjoint simple closed curves, each $X_i$ (respectively $Y_i$ ) bounding a properly embedded disk (a meridian disk) in the first (respectively second) handlebody. Reading how the $Y$ -curves cross the $X$ -curves yields a finite presentation $P(D) = \langle x_1,\dots,x_g : r_1,\dots,r_g \rangle$ of the fundamental group $\pi_1(M)$ : each generator corresponds to an $X$ -curve and each relator records a $Y$ -curve. A group isomorphic to $\pi_1$ of some 3-manifold is called a 3-manifold group. The reverse question — given an arbitrary finite presentation, does it come from a Heegaard diagram? — is a recognition-type form of the Isomorphism Problem for 3-manifold groups. Null (2011) proved (Theorem 1.1 of the preprint) that deciding whether an arbitrary finite presentation presents a 3-manifold group is algorithmically undecidable; the proof reduces the triviality problem, undecidable by a classical theorem of Rabin (1958), using a structure theorem for direct products of 3-manifold groups whose proof requires the Poincaré Conjecture. On the positive side, membership is recursively enumerable (semi-decidable: an algorithm lists every presentation that does arise from a diagram, but need not halt on the others), by systematically inserting trivial pairs $x_i x_i^{-1}$ into relators and testing each unreduced form for realizability by a planar diagram (Lemma 4.7 of the preprint). The framework of the preprint makes the positive side precise. Cut $S$ open along the $X$ -curves; a diagram is an $s$ -diagram when $S - X$ is connected and the corresponding inner boundary $\partial_X M(D)$ — the boundary of the 3-manifold determined by the diagram on the $X$ -side — is empty, so the diagram determines a closed 3-manifold and $P(D)$ naturally presents $\pi_1(M(D))$ ; a presentation determined by some $s$ -diagram is an $s$ -presentation. The geometric degree $\deg_G(D)$ of a diagram is the number of intersection points between the $X$ - and $Y$ -curves; the algebraic degree $\deg_A(P)$ of a presentation is the total length of its relators taken in the preprint's trivially reduced form (adjacent inverse pairs $x x^{-1}$ cancelled, cyclically included). A switchback is a portion of a $Y$ -curve that crosses an $X$ -curve and immediately recrosses it, contributing a subword $x x^{-1}$ that trivially cancels; because of switchbacks, reading a diagram can yield a presentation with $\deg_A(P(D)) < \deg_G(D)$ . When equality holds the diagram is an exact $s$ -diagram and the presentation an exact $s$ -presentation, which is recognizable by direct finite enumeration up to any fixed geometric degree. The engine for improving diagrams comes from automorphisms of the free group $F_g$ (the non-abelian free group on the generators): a Whitehead automorphism is one of a finite explicit generating set of $\operatorname{Aut}(F_g)$ , and Whitehead's classical theorem (1936, refined by Higgins–Lyndon 1974) says that whenever the total length of a tuple of cyclically reduced words can be reduced at all, a single Whitehead automorphism reduces it — so algebraic length can be minimized by a terminating search. Null transports this to the diagram level via Whitehead homeomorphisms — the topological counterparts of Whitehead automorphisms, performed on the curve system of a diagram — and invokes the restatement of Whitehead's theorem due to Rapaport (1958), recorded as Theorem 4.9 of the preprint, to conclude that whenever the algebraic degree of a presentation can be reduced at all, a single Whitehead automorphism reduces it. The difficulty is that this lift is not faithful: Whitehead homeomorphisms can create switchbacks, so geometric and algebraic degree can move in opposite directions, and Examples 4.15–4.17 of the preprint give an explicit sequence of Whitehead homeomorphisms that monotonically decreases geometric degree while failing to decrease algebraic degree monotonically (Table 1 of Section 4.3: $(\deg_G,\deg_A) = (43,15)\to(29,13)\to(15,15)$ ), so that an individual move can decrease geometric degree while increasing algebraic degree. Hence a monotone search in either coordinate has no certificate of termination. What is known: for two-generator presentations the problem is completely solved (Theorem 4.22 and Corollary 4.23 of the preprint), because the geometric intersection graph of a two-curve diagram has only four vertices, its configurations can be classified, and geometric degree can be reduced monotonically without ever introducing switchbacks; consequently every two-generator $s$ -presentation has an exact $s$ -diagram reachable while reducing geometric degree. For three or more generators nothing comparable is known, and the preprint states there is no known universal upper bound on the geometric degree one must search to certify that a presentation is not an $s$ -presentation. For context at the level of manifolds rather than presentations: the homeomorphism problem for closed, oriented, triangulated 3-manifolds has since been proven decidable — indeed elementary recursive, meaning with running time bounded by a fixed tower of exponentials — by Kuperberg (preprint 2015, published 2019) as a corollary of geometrization (the classification of 3-manifolds into geometric pieces, established by Perelman's proof of Thurston's geometrization conjecture), and the class of 3-manifold groups is surveyed post-geometrization by Aschenbrenner–Friedl–Wilton (2013 preprint; published as a book, 2015); these results settle manifold-level classification but provide no procedure recognizing whether an arbitrary finite presentation comes from a Heegaard diagram, and Null's undecidability theorem for that general question stands.

Problem Statement

The problem, posed by Null (arXiv:1108.3881, 2011), is to settle whether recognition of surface presentations of 3-manifold groups can be made effective: its decidability status, together with the two structural questions that govern termination of the known searches. The two components below are each independently decisive: settling the decidability question resolves the problem, and so does settling either structural question, in either direction. Fix the definitions of that preprint: $s$ -diagram, $s$ -presentation, exact $s$ -diagram (an $s$ -diagram $D$ with $\deg_A(P(D)) = \deg_G(D)$ ), geometric degree $\deg_G$ (number of $X$ -/ $Y$ -curve intersections), algebraic degree $\deg_A$ (total relator length after trivial reduction), and Whitehead homeomorphisms of diagrams (topological counterparts of Whitehead automorphisms of the free group).

(1) Decidability and the degree bound (Question 4.19 and the surrounding discussion). Given an arbitrary finite presentation $P$ (of any number of generators $\ge 2$ ; the two-generator case is already settled affirmatively by Theorem 4.22/Corollary 4.23 of the preprint), decide whether $P$ is an $s$ -presentation — that is, whether the set of $s$ -presentations is recursive, not merely recursively enumerable. The concrete obstruction posed as Question 4.19 reads: if $D$ is an $s$ -diagram, is there a bound on the geometric degree of an exact $s$ -diagram $D'$ such that $D'$ differs from $D$ by a sequence of Whitehead homeomorphisms? A bound that depends on the given diagram $D$ alone does not answer the question, since Lemma 4.11 of the preprint proves the weaker statement that, given an $s$ -diagram $D$ , a reachable exact $s$ -diagram $D'$ exists with $\deg_G(D') \le \deg_G(D)$ . Starting from a presentation $P$ alone, Section 4.3 of the preprint observes that "we have no way of knowing when we should stop searching for such presentations, and concluding that $P$ is not an s-presentation", and Section 5 that the recognition algorithm "is still inefficient until an upper bound on geometric degree is determined, indicating when we should stop searching for such a diagram". The bound is therefore required to be computable from the presentation $P$ alone, without prior knowledge that $P$ is an $s$ -presentation; under this reading the question is open. An affirmative answer with such a presentation-computable bound would cut off the enumeration of the semi-decision procedure and yield a decision procedure; a negative answer (no computable bound of this form exists) would not by itself settle decidability, since a decision procedure might proceed by other means. The bound question and the decidability question are nested rather than independent: an affirmative answer to the bound question settles decidability as well, whereas a negative answer leaves it open, so the two need not be settled separately.

(2) The monotonicity question (Question 4.18). If $D$ is a diagram of minimal geometric degree within its equivalence class up to Whitehead homeomorphisms, must $D$ also have minimal algebraic degree among all diagrams in that class? A refutation consists of an explicit diagram $D$ of minimal geometric degree in its Whitehead class together with a diagram $D''$ in the same class with $\deg_A(P(D'')) < \deg_A(P(D))$ , including a proof of the minimality of $\deg_G(D)$ over the class; a confirmation is a proof of the implication. Question (2) is the structural question that governs whether the monotone searches of (1) can be made to terminate, and an answer to it in either direction is an independent resolution of the problem.

References

Karoline P. Null, Sufficient Conditions for Recognizing a 3-manifold Group, arXiv preprint (submitted 19 August 2011). DOI: 10.48550/arXiv.1108.3881, https://arxiv.org/abs/1108.3881
Greg Kuperberg, Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization, Pacific Journal of Mathematics 301 (2019), no. 1, 189–241. DOI: 10.2140/pjm.2019.301.189, https://doi.org/10.2140/pjm.2019.301.189 (preprint arXiv:1508.06720, v1 2015, v4 2017, https://arxiv.org/abs/1508.06720)
Matthias Aschenbrenner, Stefan Friedl, Henry Wilton, 3-Manifold Groups, EMS Series of Lectures in Mathematics, European Mathematical Society, 2015. ISBN 978-3-03719-154-5. DOI: 10.4171/154, https://doi.org/10.4171/154 (preprint arXiv:1205.0202, https://arxiv.org/abs/1205.0202)
J. H. C. Whitehead, On Certain Sets of Elements in a Free Group, Proceedings of the London Mathematical Society (2) 41 (1936), 48–56. DOI: 10.1112/plms/s2-41.1.48, https://doi.org/10.1112/plms/s2-41.1.48
P. J. Higgins and R. C. Lyndon, Equivalence of Elements under Automorphisms of a Free Group, Journal of the London Mathematical Society (2) 8 (1974), 254–258. DOI: 10.1112/jlms/s2-8.2.254, https://doi.org/10.1112/jlms/s2-8.2.254
M. O. Rabin, Recursive Unsolvability of Group Theoretic Problems, Annals of Mathematics (2) 67 (1958), 172–194. DOI: 10.2307/1969933, https://doi.org/10.2307/1969933
E. S. Rapaport, On Free Groups and Their Automorphisms, Acta Mathematica 99 (1958), 139–163. (Cited as [Rap58] in arXiv:1108.3881; source of the restatement of Whitehead's theorem recorded there as Theorem 4.9)