NO ALGORITHM CAN RECOGNISE SOME FOUR-DIMENSIONAL SHAPES

Some questions have no recipe. Not because nobody has found one yet, but because it is proven that no algorithm — no step-by-step procedure, however long, run on any computer — can answer them correctly every time. Cameron McA. Gordon, at the University of Texas at Austin, adds two such questions about four-dimensional shapes.

Is this the same shape?

Mathematicians call these shapes 4-manifolds: spaces that, seen up close, look like ordinary four-dimensional space everywhere. To hand them to a computer, the paper assumes they are built from flat pieces glued together (“piecewise linear”, or PL), so that each can be described by a finite list of data. The basic question is then: given two such shapes, are they the same, up to continuous deformation?

In 1958, A. A. Markov showed that this question has no algorithm. Markov’s proof turns the shape problem into a problem about groups: there exist groups — collections of operations that can be chained and undone — defined by finitely many rules, for which no algorithm can decide whether a given combination of their elements, called a “word”, equals the identity, the element that does nothing — the “word problem”. From such a group, one can build shapes that an algorithm could tell apart only by solving that impossible problem.

Counting down to seven

Markov’s argument even pins the difficulty to particular shapes. Take S², the surface of an ordinary ball, and form the product S² × S², a four-dimensional shape. Glue k copies of it together (a “connected sum”, written #k). For some k, no algorithm can decide whether a given shape is #k(S² × S²). Which k?

The paper traces the countdown. A group with an unsolvable word problem and 12 rules, found by Borisov in 1969, gave 14 copies. Gordon brought it to 12 in 2022. M. Tancer found a new route, through Freedman’s classification of four-dimensional shapes, and reached 9 in the “topological” version, where shapes need not be built from flat pieces. An earlier version of this work reached 8. Then Kegel, Li and Ren built a much smaller unsolvable group — 3 generators and 9 rules — reaching 7 in the topological version and 9 in the flat-piece one.

Gordon makes Tancer’s route work for shapes built from flat pieces too, and proves:

There is no algorithm to decide whether a given 4-manifold is the same, piece for piece, as the connected sum of 7 copies of S² × S².

The core of the proof is a dictionary. For every word w in Kegel, Li and Ren’s group, Gordon builds a four-dimensional shape. If w equals the identity, a sequence of allowed moves on the rules — the Andrews-Curtis moves, which rewrite the description without changing the shape — shows that the shape is exactly seven copies of S² × S². If it does not, the shape contains loops that cannot be tightened to a point — which never happens in seven copies of S² × S² — so it cannot be those seven copies. An algorithm that recognised #7(S² × S²) would therefore solve the word problem, which is impossible.

Knotted spheres

The second question is about knots. An ordinary knot is a circle tied up in three-dimensional space, and deciding whether a knot can be undone is possible: there is an algorithm, due to Haken. One dimension up, a two-dimensional sphere can be knotted inside four-dimensional space. In higher dimensions, the corresponding problem is known to have no algorithm. For two-dimensional spheres in the four-dimensional sphere S⁴, nobody knows.

Gordon proves that inside #7(S² × S²), there is no algorithm to decide whether a two-dimensional sphere — or any surface, two-sided or one-sided — is unknotted. Along the way, the paper builds a sphere in that shape whose surrounding space has a group with an unsolvable word problem, and, in 12 copies of S² × S², a sphere whose group contains a copy of every group that can be described by a computer.

The prize: zero copies

The paper states the goal plainly: bring the number of copies down to zero. Zero copies means the four-dimensional sphere S⁴ itself. In five dimensions and more, no algorithm can recognise the sphere; in two and three dimensions, one can. Four dimensions remain open — and so does the question of whether knotted spheres in S⁴ can be detected. Each copy removed brings both questions closer.