Auditing AI-Generated Lean 4 Proofs: Why the Statement Is the Whole Trust Surface

Lessons from the October 2026 ETH and deterministic factoring formalizations: when an LLM writes 35,000 to 152,000 lines of Lean 4, how to audit the statement, machine model, and crossover constants.

1. The new division of labour: unread proofs, audited statements

In October 2026, three headline complexity formalizations landed in rapid succession: OpenAI’s subexponential k-CNF counting proof, Anthropic’s 152,000-line subexponential 3-SAT proof, and Rudich and Rousseau’s 35,000-line deterministic factoring proof generated by Claude Opus 5.5.

As Rudich and Rousseau stated plainly in their paper, the human authors specified and audited the 13-line Mathlib statement and *"did not read the proof, which is checked by Lean."* That division of labour works only if two conditions hold: the kernel check is replayed cleanly from scratch, and the 13-line formal statement cannot be satisfied by a trivial, restricted, or unintended mathematical object.

2. Four places where an AI-formalized statement and a paper come apart

Across the October 2026 formalizations, independent readers (Toledo, Szeider, Majdoddin, Papex) identified four recurring specification seams:

1. **Weaker formal exponent than the prose headline:** OpenAI’s Lean proof (exact_count_and_sat) formalizes Proposition 6.4 (n(log log n)²/√log n), while the paper’s headline Theorem 1.1 bound (n·log log n/√log n) remains prose only.

2. **Custom machine models and input encodings:** A Turing-machine time bound depends on whether the machine is a custom multitape model over unary words or Mathlib’s FinTM2 over fixed-width binary slots. Closing that gap required Toledo’s explicit Lean bridge theorems (C1 and C2).

3. **Input promises in the theorem signature:** Anthropic’s MainTheorem restricts inputs to k ≥ 1, m ≥ 2, n ≥ 4 with every variable occurring. Reducing general k-CNFs to that promise class is standard in prose, but unformalized.

4. **Galactic existential constants (∃ C):** When a theorem states ∃ C, ∀ n, steps ≤ 2 ^ (C · ...) or ∃ C_k, steps ≤ C_k · 2 ^ (n / k), the kernel checks only that some finite constant exists. As Szeider showed, the proved bounds in the ETH papers only improve on brute force above 2^131071 or 10^10000 variables.

3. How to test an AI-generated formalization with planted wrong variants

Reading custom definitions by eye is error-prone. In his audit of the ETH bridge proofs, Carlos Toledo introduced **planted wrong variants**: deliberate mutations of the statement or bridge definitions that *must* be rejected by the kernel if the specification is tight.

SeamCert automates the first layer of this check for any Lean 4 statement file: it extracts every theorem’s hypotheses and conclusion, flags custom definitions, size promises, and existential constants, and generates Mutants.lean with vacuity probes, perturbed constants, and tightened relations.

Questions & Answers

Sources & References

1. Carlos Toledo, "Two claimed refutations of the Exponential Time Hypothesis: what was decided, and what was only read"
2. Stefan Szeider, "OpenAI's claimed refutation of ETH: exhaustive search below 2^131071" (Zenodo)
3. Papex, "Has the ETH refutation been verified?" (31 October 2026)
4. Isaac Rudich and Louis-Martin Rousseau, "Deterministic Factoring in Time N^o(1)" (Hexagon 2610.00600v1)