Towards computable manifolds
Abstract. In this (exceedingly brief) note, we discuss computability questions in the context of manifold theory. The main observation is that several computabilty issues in classical “set-point (differential) topological” foundations may potentially be overcome when working with manifolds from the higher-categorical perspective of manifold diagrams and tangles.
Introduction
The idea of a manifold is a simple one: a manifold is a space that locally looks “standard” (meaning, for instance, like standard $n$-dimensional euclidean space). The concept of manifolds is as ubiquitous in mathematics as it is in physics (and maybe the latter provides a reason for the former): not only does the world around us appear to be geometric in nature, with spacetime and trajectories in it being describable (at least to some degree of approximation) by manifolds, but even fundamental interaction terms in particle physics can be thought about in terms of (stratified) manifolds such as Feynman diagrams.
One goal of framed combinatorial topology (FCT) is to allow for a combinatorial understanding of (diagrams of) manifolds from the process-oriented lens of higher category theory. A core advantage that this “combinatorial foundation” for studying the geometry of manifolds brings to the table is that computers can understand algebra much better than geometry—and higher category theory is, in essence, algebra (well, higher algebra). As a consequence, a range of computability questions regarding manifolds potentially obtain new and interesting answers. In this note, we discuss some of the issues in the classical theory of manifolds and to which extent they may be resolved when working from a higher-categorically inspired perspective. Formally, the approach is based on theory of manifold diagrams and tame tangles recently introduced in [1].
To compute or not to compute
Let us start by recalling an absolutely minimal amount of computability theory. A basic model of a computer is a Turing machine: a program on a Turing machine is a sequence of instructions that can be executed while reading some binary input, and producing some binary output; the program may a reach a final machine state (called the “halting” state) or it may run forever which is usually considered to be bad (although, Type-II computability is a thing). Not every (partial) function that can be mathematically defined, can be computed by a program on the Turing machine.
An example of such a function is the halting decision problem: this function takes the binary code of a program together with some binary number b and outputs a single bit 1 if the program halts when given b as input, and a single bit 0 if the program runs forever on b. Since any program computing this function must itself be written in a finite amount of code, a diagonal argument shows that such a program cannot exist. Thus, the halting problem cannot be computed by a program—one says it is undecidable.
We will shortly discuss a range of other undecidable “decision problems”, i.e. partial functions to ${0,1}$ that cannot be computed by a program (they are called “decision problems” since 0 and 1 can be thought of as representing the answers “no” and “yes” to a question about the input). In essentially all these cases, undecidability is proven by producing a contradiction: assuming decidability of the problem at hand, one shows that the halting problem becomes decidable.
As an aside, let us mention two cases in which the above proof of the undecidability of the halting problem fails.
- If we allow the algorithm for solving the halting problem to have infinitely many bits of code (which can then contain, for instance, a case distinction over all programs), then such an algorithm may exist.
- If we consider a machine with finitely many states (like every practical computer), than an algorithm solving its halting problem does exist. However, the algorithm must run on a bigger machine.
The above two points illustrate that the halting problem is really a question about size (note also the case of oracles). Indeed, whenever a diagonal argument is at work, “size” is the suspect: a diagonal argument means that some sort of list cannot be produced (in specified way) without necessarily being incomplete. In our case, there is no algorithmic way to produce a list of non-trivial properties of all algorithms (see also Rice’s theorem). Similarly, there’s no set of all sets with some non-trivial property (see Russell’s paradox). Finally, note that from a perspective of (higher) category theory such questions intermix universe hierarchy dimensions, which opens the door to these size issues appearing.
Classical incomputabilities
In classical combinatorial topology a central object of study is that of a simplicial complex $K$. Via the process of geometric realization, such complexes may be thought about in terms of traditional topological spaces $\abs{K}$. Importantly, each simplex has affine linear structure. Maps $F : \abs{K} \to \abs{L}$ that preserve this structure locally (in linear-conical neighborhoods) are called piecewise linear (PL) maps. A PL $n$-manifold is an $n$-manifold whose transition functions are PL maps (with respect to the standard linear structure of euclidean space $\lR^n$). Given a simplicial complex $K$, $\abs{K}$ “being a manifold” is a property (as long as we require charts to be PL maps). The standard PL $n$-sphere is PL manifold obtained as the geometric realization of the simplicial complex $\partial \Delta$ (i.e. the boundary of the standard simplex).
The following fundamental questions are now, unfortunately, undecidable.
-
Given a simplicial complex $K$, is $K$ a PL $n$-manifold? The fact that the question is undecidable follows since it reduces to the next question.
-
Given a simplicial complex $K$, is $K$ a PL $n$-sphere, $n > 4$ (i.e. is $\abs{K}$ PL homeomorphic to the standard PL $n$-sphere)? The proof of this undecidability result roughly proceeds as follows. You can use finite presentations of groups by generators and relations to model computation of a program on an input, such that the program halts if and only if a corresponding representative of a group element represents the identity element of the presented group. Consequently, there are finitely presented groups for which no program can decide whether element representives represent the identity (one says, the group has an undecidable word problem, see [2]). Now, given such a group $G$ and a representative $r$ of one of its element, we can can construct a finitely presented group $G_r$ which is trivial iff $r = 1$. We can also construct a (PL manifold) homology $n$-sphere $H(G_r)$ with fundamental group $G_r$ which is PL homeomorphic to the PL $n$-sphere iff $G_r$ is trivial [3]. This shows that deciding whether a given PL manifold is PL homeomorphic to the sphere cannot be done in general.
-
No algorithm can accomplish the following task: given $k \in \lN$, list all PL manifolds $K$ for which $K$ has up to $k$ vertices. Similarly, we cannot list all $K$ with up to $k$ vertices that are spheres. Note that these undecidability results holds despite there being only finitely many simplicial complexes with up to $k$ vertices to begin with! As a consequence, the set of PL manifolds is not “listable”, i.e. no infinite-time algorithm can produce list of all them.
Importantly, these obstructions to manifold theorem largely remain in place if replace “PL manifold” by some other computer-friendly presentation of manifolds (for instance, via rational algebraic sets, or via Morse functions and handlebodies).
As an aside, let us also mention the following slightly more general undecidability results (and a case in which they can actually be decided).
- Given simplicial complexes $K$ and $L$ the question of whether they are PL homeomorphic is undecidable in general. The question whether $K$ subdivides $L$ (by a PL map) is equally undecidable. Indeed, this follows from the above since $K$ is a PL sphere iff it subdivides the standard simplex boundary.
In contrast the question of geometric subdivision (i.e. a subdivision $K \to L$ which is linear on each simplex in $K$) can be decided. See e.g. [4, Prop. 3.5].
Towards a computable theory
In the previous section we remarked that the foundational computability issues when dealing with manifolds cannot be overcome simply by replacing simplicial complexes with a potentially “better” presentation of manifolds to input into our comptuters—and, in particular, this remark applied to presentations of manifolds by handlebodies derived from ordinary Morse functions. In this section, we claim that these obstruction can be overcome if, in essence, we replace “Morse function” with “$n$-Morse function” (for sufficiently large $n$) in the previous sentence.
Recall that a 1-Morse function is a “stable” smooth function from a manifold to 1-dimensional euclidean space—here, stable may be understood to mean the following: the singularities that a Morse function has are stable under perturbation, namely, it only contains quadratic singularities and perturbing quadratic singularities a little bit yields again a quadratic singularity (up to equivalence). The same stability question can then be asked for “higher” functions, i.e. functions to n-dimensional euclidean space. In low dimensions, this generalization is fairly well understood. To begin, one considers paths of ordinary Morse functions (these are studied e.g. in Morse-Cerf theory): in addition to usual quadratic singularities found in Morse functions, generically, along such paths we may now find cubic singularities which we refer to as “handle cancellations” (these cancel two quadratic singularities); we may also find “non-local exchanges” of quadratic singularities. One dimension up, we may consider “paths of paths of Morse functions”, and these will now generically contain quartic singularities.
This raises the hope that, for higher and higher paths, we will find a nice finite pattern of such perturbation stable singularities. Disappointingly, this is not the case: the differential theory of singularities produces, in high enough dimension regimes, uncountably many classes of singularities that cannot be perturbed to anything stable. (Another way to think about the situation is in terms of stratifications: in the space of functions on a manifold, Morse functions up-to-equivalence are the codimension-0 stratum, cubic singularities up-to-equivalence are codimension-1 strata living between these strata (and thus paths through them are perturbation stable), … continuing to higher and higher codimension, once we reach codimension 5, equivalence classes of singularities fail to produce open strata of the remaining space; instead they produce some sort of foliations as described in work by Arnold [5]).
Still, there are perturbation stable singularities in all codimensions (just that we cannot cover the entire space of functions with the corresponding strata): the list of these singularities includes, firstly, the $A$-series of singularities (which continuous the quadratic, cubic and quartic singularities mentioned above); it also includes the $D$-series (which requires our manifold to be at least of dimension 2, and has quite different flavor from the $A$-series, see [1]); finally, it includes three exceptional singularities often denoted by the letter “$E$”. The resulting “$ADE$ pattern” is an important metapattern in mathematics, see [5]. The fact that there is a deep description of these singularities is satisfying; however, the observation that the description doesn’t cover “all the cases” of differential functions is rather worrying from a foundational perspective. One of the main observations in [1] was that via the notion of tame tangles (defined within the theory of framed combinatorial topology) provides a approach to the study of singularities that is based on an alternative mathematical foundation: in particular, it yields a combinatorial theory of singularities—the resulting “combinatorial singularity theory”, by design, does not suffer from the same complications observed in the classical differential approach.
The questions about comparing the two approaches remain largely open (fully unsurprisingly, since “combinatorial singularity theory” so far has been suggested and outlined, but not really studied to any substantial degree). The expectation, however, as argued heuristically in [1], is that in the appropriate dimensions the two theories are intimately related, and that the stable differential $ADE$ singularities can in particular be translated into stable combinatorial singularities. At the same time the combinatorial theory is, in some sense, much finer than the classical theory, and this leads to new interesting singularities appearing (such as the $D_2$ and $D_3$ singularities [1]).
Understanding perturbation stable (or “elementary”) combinatorial singularities is only the first ingredient in understanding $n$-Morse functions (again, combinatorially). The second ingredient lies with the generalizations of “exchange”-type behaviour as mentioned earlier in the context of Morse-Cerf theory. These non-local objects are called elementary isotopies in [1]. Conditional on the combined understanding of such elementary singularities and elementary isotopies, one could then introduce a notion of “complete” $n$-Morse functions as follows (we assume familiarity with tame tangles, see [1]).
Definition (Complete Morse functions). Given an $m$-manifold $M$, a complete $n$-Morse function is a tame tangle $f : M \into \lR^n$ (for $n > 2m$ we may also speak of a ‘stable $n$-Morse function’) that only contains elementary singularities and elementary isotopies.
(Note, the adjective ‘complete’ merely highlights that $n > m$, so no dimensions of $m$ are being forgotten—this is actually crucial for the last remark below regarding such Morse functions being ‘complete’ characterizations of smooth structures.)
With a notion of $n$-Morse function at hand we finally return to our questions of computability that we set out to resolve—we deal with them in reverse order (relative to the order in the previous section). We will abbreviate the phrase “manifold with a complete Morse function” by “stable tangle”. (Just to be sure, let us emphasize again that the above definition as well as the following points depend on a conjectural classification of elementary combinatorial isotopies and singularities.)
-
There exists an algorithm that lists all stable tangles: the algorithm simply composes elementary isotopies and singularities to form stable tangles (in the sense of higher-categorical composition, using the fact that tame tangles are canonically manifold diagrams and thus higher-categorical pasting diagrams).
-
There may potentially(!) exist an algorithm that decides whether a stable tangles is a sphere (potentially subject to further restrictions; e.g. to codimension-1 tangles): the motivation for this speculation is that the classical counter-argument uses the construction of homology spheres which may not be possible to do effectively in the stable case. A naive algorithm could proceed by inductively performing “higher handle cancellations” (analogous to the handle cancellations in Morse-Cerf theory mentioned earlier, but for higher dimensional singularities; these “cancellations” are themselves described by higher singularities and can thus be conjecturally classified); the algorithm thereby either reaches the standard embedding of the $n$-sphere in $\lR^{n+1}$ (in which case the answer is “yes”) or must stop before it does so (in which case the answer is “no”); however, one quickly realizes that care needs to be taken about what precisely counts as a handle cancellation in order to avoid the algorithm getting “stuck” … .
-
As an aside, but closely related to the previous point, can we use the higher Morse theory of stable tangles to understand homotopy 4-spheres? Note that all homotopy 4-spheres embed in $\lR^5$, and, generically, these embeddings are stable codimension-1 tangles. If we have an algorithm to recognize spheres among codimension-1 homotopy 4-spheres, that algorithm may also distinguish exotic PL 4-spheres from the standard PL 4-sphere. Thus, the framework of stable codimension-1 tangles might shine new light on the PL/smooth Poincare conjecture in dimension 4. Previous approaches only used 1- or 2-Morse theory.
-
Finally, the recognition problem can also be solved in the following sense: given any tame stratification (or, equivalently (by the flat framed Hauptvermutung, see [7]), any stratified flat framed simplicial complex) we may algorithmically decide whether it is a stable tangle.
Studying combinatorial singularities and isotopies is interesting for many reasons, including its connections to dualizability (see e.g. [1]) and smooth structures (see remark below). However, the above (admittedly brief) discussion motivates that this work may, in fact, have a surprising side effect: it may constitute first steps towards a “computable foundation” for the study manifolds, made possible by a combinatorial approach to higher Morse theory. This could be a very exciting prospect.
Remark (Combinatorialization of smooth structures). There is a second important conjectural aspect of passage from ordinary Morse to higher Morse functions: in [1] we conjecture that the latter can capture smooth structures (while it is known that the former cannot, as Milnor showed when constructing his exotic 7-sphere). Since our higher Morse function are combinatorializable, this would in fact enable the combinatorial representation of all smooth structures—a feature that hasn’t previously been achieved (though attempts were made: but, e.g., neither rational algebraic sets nor, say, combinatorial differental manifolds can present all smooth structures).
So where did the uncomputability go? This is an important question, but one that can be answered concisely. What we cannot compute algorithmically are perturbations. That is, we cannot produce a list of all non-stable singularities together with perturbation into stable singularities. In other words, the mathematical proof for the classification of stable singularities will have to be non-algorithmic (or “non-constructive”).
Conclusion
To briefly summarize, there may be a natural and computable, higher-categorically-inspired foundation for the theory of manifolds available—namely, by considering the concept of manifolds in the framework of manifolds diagrams and tame tangles and, more concretely, by combinatorially studying manifold singularities and isotopies that can appear in such tame tangles (or, from a higher-categorical lens, studying the data of coherently dualizable objects).
References
[1] C. Dorn + C. Douglas, 2022, Manifold diagrams and tame tangles
[2] B. Poonen, 2012, Undecidable problems: a sampler
[3] S. Weinberger, 2005, Computers, Rigidity, and moduli
[4] G. Kuperberg, 2015, Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization
[5] Arnold, 1976, Local Normal Forms of Function
[6] T. Gannon, 2006, Moonshine Beyond the Monster
[7] C. Dorn + C. Douglas, 2021, Framed combinatorial topology