TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck passverified 2026-10-22 (gpt-6.1-sol)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Bracket state-sum exponential bound

Statement

Let $D$ be a nonempty oriented link diagram with $c$ crossings and $m \geq 1$ components. The state-sum portion of the normalized bracket computation visits exactly $2^{c}$ smoothing states; computing the writhe correction requires one pass over the $c$ crossing signs. Its exact normalized output $f_{D} (A) = (- A^{3})^{- wr (D)} ⟨ D ⟩$ has absolute Laurent degree at most $6 c + 2 m - 2$ and signed coefficient-bit size at most $m + 2 c + 1$ . For a knot diagram, these output bounds are linear in $c + 1$ .

Using the indexed endpoint-pairing input and dense signed binary-array implementation of the exact bracket bit-growth theorem, together with the $c$ crossing signs supplied as bits, the normalized bracket can be computed in $O (2^{c} (c + m + 1)^{4})$ elementary bit steps. This is $O (2^{c} (c + 1)^{4})$ for knots. Input records are assumed to describe the given typed diagram; arbitrary literal-code reading and parsing, extra padding or labels, and geometric-coordinate processing are outside this implementation bound. The finite computations are choice-free. Under the Axiom of Countable Choice, $f_{D}$ is an invariant of the ambient-isotopy class of the oriented link. No polynomial-time Jones evaluation is asserted.

Statement references

Encoded diagram size and exact output

Kauffman bracket state sum

Kauffman bracket state-sum procedure properties

Exact bracket output bit-growth bound

The normalized bracket is an oriented link invariant

The Axiom of Countable Choice ( ${A C}_{ω}$ )

Kauffman, Combinatorial Knot Theory and the Jones Polynomial (2022), §2

Roberts, Knots Knotes (1999), §4.3

Calegari, Introduction to Knot Theory (2025), §5.1

Facts & Assumptions

Given: A nonempty regular oriented link diagram $D$ with $c$ crossings, $m \geq 1$ components, and $A$ an indeterminate.

[A1]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): ${A C}_{ω}$ is the axiom of countable choice.

[F1]

Encoded diagram size and exact output: the crossing count is $c$ , the component count is $m$ , and Laurent coefficient-bit size uses the signed-magnitude convention.

[F2]

Kauffman bracket state sum: every state contributes $A^{a (S) - b (S)} (- A^{2} - A^{- 2})^{∣ S ∣ - 1}$ to the exact Laurent polynomial.

[F3]

Kauffman bracket state-sum procedure properties: the state-sum procedure visits exactly the $2^{c}$ smoothing assignments and returns the displayed bracket.

[F4]

Exact bracket output bit-growth bound: the raw bracket has absolute Laurent degree at most $3 c + 2 m - 2$ and signed coefficient-bit size at most $m + 2 c + 1$ . Its specified indexed endpoint-pairing and dense binary-array implementation takes $O (2^{c} (c + m + 1)^{4})$ elementary bit steps, excluding arbitrary literal-code parsing.

[F5]

The normalized bracket is an oriented link invariant: with crossing signs $sgn (c) \in {+ 1, - 1}$ and $wr (D) = \sum_{c} sgn (c)$ , the normalization $(- A^{3})^{- wr (D)} ⟨ D ⟩$ is unchanged under oriented Reidemeister moves and is an ambient-link invariant under ${A C}_{ω}$ .

Proof

1.1F2F3F5givenconstruct

By [F3], the state-sum procedure visits every map from the $c$ -element crossing set to ${A, B}$ exactly once, so it makes exactly $2^{c}$ state visits. The writhe is the sum of one sign from each of the $c$ crossings by [F5], so a direct scan computes it in one pass. These finite operations use no choice principle.

1.2F1F4F5algebra

Each crossing sign is $+ 1$ or $- 1$ , so $∣ wr (D) ∣ \leq c$ . Multiplication by $(- A^{3})^{- wr (D)}$ shifts every Laurent exponent of the raw bracket by $- 3 wr (D)$ and multiplies coefficients only by a sign. Thus the absolute degree increases by at most $3 c$ , giving $6 c + 2 m - 2$ by [F4], while coefficient-bit size is unchanged and remains at most $m + 2 c + 1$ . For $m = 1$ both bounds are linear in $c + 1$ .

2.1F1F4F5step 1.2constructalgebra

Put $q = c + m + 1$ . By [F4], compute the raw bracket in $O (2^{c} q^{4})$ bit steps in the specified representation. Summing the supplied sign bits uses an $O (\log (q + 1))$ -bit signed counter and $O (c \log (q + 1))$ bit steps, rather than unit-cost unbounded arithmetic. The factor $(- A^{3})^{- wr (D)}$ has sign $(- 1)^{wr (D)}$ and exponent $- 3 wr (D)$ . Allocate a dense output array with exponents from $- 6 q$ to $6 q$ and the same $O (q)$ -bit signed coefficient slots as in [F4]. For each raw slot, copy its value to the position shifted by $- 3 wr (D)$ and toggle the sign when necessary. There are $O (q)$ slots. Linear lookup or writing scans at most $O (q^{2})$ tape cells per slot, including binary index counters, so even this naive normalization costs $O (q^{3})$ bit steps. Step 1.2 ensures every shifted exponent and coefficient fits the array. This cost is absorbed in $O (2^{c} q^{4})$ , and for $m = 1$ it is $O (2^{c} (c + 1)^{4})$ . No arbitrary code parser or black-box arithmetic operation is assigned a false constant bit cost.

3.1A1F5step 1.1step 1.2step 2.1∎

Under [A1], [F5] identifies the normalized output with an invariant of the ambient-isotopy class of the oriented link. The state count, writhe pass, degree shift, coefficient estimate, and specified bit implementation in steps 1.1, 1.2, and 2.1 remain choice-free. The running-time estimate is exponential in the crossing count, and makes no polynomial-time Jones evaluation claim.

Sources

Encoded diagram size and exact output

Kauffman bracket state sum

Kauffman bracket state-sum procedure properties

Exact bracket output bit-growth bound

The normalized bracket is an oriented link invariant

The Axiom of Countable Choice ( ${A C}_{ω}$ )

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

22 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Louis H. Kauffman, Combinatorial Knot Theory and the Jones Polynomial, arXiv:2204.12104v2, §2 (standard reference, not scraped)
Justin Roberts, Knots Knotes, Edinburgh course notes (1999), §4.3, pp. 24–25 (standard reference, not scraped)
Danny Calegari, Introduction to Knot Theory, University of Chicago course notes (2025), §5.1, pp. 38–41 (standard reference, not scraped)