gpt 6 astra ultra attempt on Math-321

Unknotting Problem

Definitions and mathematical statement

A knot diagram is a finite planar projection of an embedded circle, with transverse double points and an over/under choice at each crossing. Its encoding records the planar combinatorics and crossing information; let $n$ be the bit length of that encoding. The unknot is the ambient-isotopy class of a round circle in $S^3$. The task is to decide whether there exist a deterministic algorithm and constants $C,k$ such that, on every valid diagram $D$, the algorithm correctly decides \[ D\text{ represents the unknot} \] in at most $C(n+1)^k$ steps. The complexity concerns the finite diagram input, not real coordinates with unit-cost exact operations. Certificates, special families of diagrams, and practical heuristics do not by themselves supply a polynomial-time decision algorithm for all diagrams.

Formulation and concept references: [S1].

Short English statement

Is there a deterministic algorithm that recognizes the unknot from any knot diagram in time polynomial in the diagram's encoding length?

Research attempt: certificates, search bounds, and a polynomial subcase

Status and computational convention. No deterministic polynomial-time algorithm for all valid knot diagrams is established here. Input size means the bit length of a finite combinatorial planar diagram encoding. In particular, a short description of a very large integer is not permission to perform an amount of work proportional to that integer at unit cost.

The source audit on 27 September 2026 found relevant new work as well as older certificate results. Lackenby's July 2026 manuscript [E3] gives a hierarchy-based recognition algorithm and polynomially verifiable certificates for certain boundary-pattern assertions. Its introduction and theorem statements do not supply the selected polynomial-time bound for general unknot recognition. The February 2026 paper [E2] gives polynomial Reidemeister-move bounds for each fixed link type and explicitly draws an NP conclusion. These claims must not be converted into a deterministic polynomial-time search algorithm.

The combinatorial input. One convenient encoding records the four half-edges at each crossing, their cyclic order in the plane, the pairing into edges, and the over/under information. Labels use $O(\log(c+2))$ bits for a diagram with $c$ crossings. The valid-input promise supplies planarity and a single link component; alternatively these can be checked by standard finite graph operations on the rotation system. The exceptional zero-crossing circle is encoded separately. Thus $c$ is bounded by a polynomial, in fact linearly up to representation conventions, in the input length $n$.

A Reidemeister move is local in the embedded diagram. A certificate can specify the few half-edges and face incidences involved and the move type. A verifier checks that the required small disk configuration exists and performs the local modification. Graph relabeling and rotation-system comparison can be performed in polynomial time; no geometric coordinates of arbitrary precision are required.

Lemma 317.1 (short moves give short certificates). If every $c$-crossing unknot diagram admits a sequence of at most $p(c)$ Reidemeister moves to the circle, for a polynomial $p$, then unknottedness has certificates verifiable in polynomial time in the diagram input length.

Proof. A Reidemeister move changes the crossing number by at most two. Thus a sequence of length $L\leq p(c)$ has at most $c+2L$ crossings at any stage. Record all intermediate encoded diagrams and the local moves, with explicit identifications of unchanged half-edges if necessary. There are polynomially many stages, each of polynomial size, so the whole record has polynomial bit length. Check each local modification and the final zero-crossing circle. A valid sequence preserves the knot type, proving soundness. The assumed bound gives completeness for unknots. $\square$

Lackenby's established theorem [E1] supplies a bound $p(c)=(236c)^{11}$, with an additional polynomial bound on intermediate crossing counts. Thus the hypothesis of the lemma is known. The proof above only explains its certificate consequence; it does not claim to rediscover the topological bound.

The search gap is quantitative. Suppose each stage has at most $M=c+2p(c)$ crossings. There are at most a polynomial in $M$ possible local move descriptions, using a deliberately coarse bound obtained by choosing finitely many half-edges and a move type. Enumerating sequences of length at most $p(c)$ therefore has an upper bound of the shape \[ \left(M^C+C\right)^{p(c)+1} =\exp\left(O(p(c)\log(M+2))\right) \tag{317.1} \] for an absolute constant $C$. This is a finite deterministic decision procedure when the known move bound is used, but the bound obtained this way is exponential in a polynomial in the input length. A polynomial depth for a branching search tree is not a polynomial bound on its number of nodes.

The same distinction applies to a compressed normal surface. If a vector has $O(n)$ nonnegative integer coordinates each at most $2^{O(n)}$, then its binary description has polynomial length. It may nonetheless describe exponentially many normal disks. A procedure that expands all disks is not polynomial-time in the compressed input. Moreover, a short valid vector, or an efficiently verifiable hierarchy, is not necessarily findable by an efficiently bounded deterministic search. The missing construction or search bound must be proved separately.

An exact polynomial-time subcase: explicitly given two-strand braids. Suppose the input is an ordinary, uncompressed word of length $m$ in the two-strand braid generator $\sigma$ and its inverse, together with its standard closure. The two-strand braid group is infinite cyclic, so the braid is $\sigma^e$, where \[ e=\#\{\sigma\}-\#\{\sigma^{-1}\}. \] Computing this signed count uses $O(m\log(m+2))$ bit operations by elementary binary arithmetic. The closure is a knot precisely when $e$ is odd, since the induced permutation of the two strands is the transposition to the power $e$.

For odd $e$, the closure is an unknot exactly when $|e|=1$. The sufficiency follows by canceling inverse adjacent braid generators and removing the single crossing of the closure by a Reidemeister move. To prove necessity without presupposing a classification of torus knots, evaluate its bracket invariant as follows.

In the two-strand bracket algebra let $I$ be the straight pairing and $E$ the cap-cup pairing. They satisfy \[ E^2=\delta E,\qquad \delta=-A^2-A^{-2}, \qquad \sigma=A I+A^{-1}E. \] Closing the diagram sends $I$ to $\delta$ and $E$ to $1$. Choose a complex number $A$ of modulus one with $A^{-4}=-1$. Then $\delta=0$, so $E^2=0$. For every integer $e$, including negative ones, the binomial identity for a square-zero element gives \[ (A I+A^{-1}E)^e=A^e I+eA^{e-2}E. \] For negative exponents this follows directly from $(I+uE)^{-1}=I-uE$, then induction. Closure gives bracket $eA^{e-2}$. The writhe-normalizing factor also has modulus one, so \[ |V_{\widehat{\sigma^e}}(-1)|=|e|. \tag{317.2} \] The unknot has invariant one. Therefore $|e|>1$ is a rigorous certificate of nontriviality, proving the criterion.

This algorithm solves a promised representation class. It does not say that an arbitrary diagram can be converted in polynomial time to a two-strand braid when such a representation exists, or that every knot has braid index two. A presentation promise cannot be removed without another algorithm.

Invariant computation is a different bottleneck. The Jones state sum on a general $c$-crossing diagram contains $2^c$ states. Its final Laurent polynomial has only $O(c)$ possible degree positions and coefficients of $O(c)$ bits, by the elementary state-count bound, but a compact output does not imply an efficient way of obtaining it. Further, using the equality $V_K=1$ as a complete decision criterion would additionally require the Jones unknot-detection conjecture, which is a separate assertion. The two-strand argument above avoids that conjecture: a value of modulus greater than one proves nontriviality, and explicit moves prove the remaining $|e|=1$ cases trivial.

Likewise, a procedure that always simplifies some easy unknots but occasionally stops at a diagram with no immediately reducing move is not complete. The polynomial-move theorem permits intermediate increases in crossing number. A proof that forbids such increases would need a separate theorem and cannot be obtained just from the existence of some bounded sequence.

A precise possible route to the full algorithm. To improve $317.1$, one could seek a polynomially computable rule that selects a polynomial number of promising successor diagrams while guaranteeing that at least one selected path reaches the circle whenever the input is an unknot. Another route would construct, in polynomial time, a compressed spanning disk or hierarchy and verify it without expanding exponentially many pieces. In either case two obligations remain: the total number of candidates or construction steps must be polynomial, and every intermediate integer or combinatorial object must have polynomial bit length. Neither obligation follows from NP membership alone.

Diagnostics and outcome. The exact accompanying script enumerates small two-strand words, compares free cancellation with the signed exponent, and evaluates the bracket recurrence over integer Laurent polynomials. It verifies $317.2$ through the square-zero specialization and checks the $|e|=1$ criterion throughout the finite sample. It does not implement the full normal-surface or hierarchy algorithms of [S1] and [E3].

The attempt gives an explicit polynomial algorithm for the two-strand input class and proves why polynomial Reidemeister certificates do not by themselves bound deterministic search. The first missing step in the general case is a polynomial-time way to locate suitable topological simplifications or compressed witnesses. The selected polynomial-time decision problem remains unresolved here.

Sources

• S1 Burton and Ozlen, arXiv:1211.1079, 2012; revised 2014. https://arxiv.org/abs/1211.1079. Formulation source.
• E1 Marc Lackenby, A polynomial upper bound on Reidemeister moves, Annals of Mathematics 182 $2015$, 491--564; arXiv:1302.0180. https://arxiv.org/abs/1302.0180. Primary source consulted 27 September 2026 for the polynomial move bound, used only with its certificate consequence.
• E2 Marc Lackenby, A polynomial upper bound on Reidemeister moves for each link type, arXiv:2602.09923 $2026$. https://arxiv.org/abs/2602.09923. Primary source consulted 27 September 2026; fixed-link-type move bounds and NP membership are not deterministic polynomial-time recognition.
• E3 Marc Lackenby, Incompressible surfaces, hierarchies and unknot recognition, arXiv:2607.23350v1, submitted 25 July 2026. https://arxiv.org/html/2607.23350v1. Primary source consulted 27 September 2026, including the introduction and efficient hierarchy-certificate statements.