VibeMathedMath problems solved with AI

Deterministic integer factoring in time No(1)N^{o(1)}

Every deterministic integer factoring algorithm with a proved running time has had a fixed positive exponent: trial division N1/2+o(1)N^{1/2+o(1)}, Lehman N1/3+o(1)N^{1/3+o(1)}, Pollard and Strassen N1/4+o(1)N^{1/4+o(1)}, Hittmeir N2/9+o(1)N^{2/9+o(1)}, and Harvey's N1/5+o(1)N^{1/5+o(1)} (2021), improved only by logarithmic factors since. The rigorous subexponential methods (Dixon, Lenstra-Pomerance) are randomized, and the deterministic sieves rest on unproved heuristics. Is there one deterministic algorithm that factors every positive integer NN in time No(1)N^{o(1)}, that is, in time O(Nε)O(N^{\varepsilon}) for every ε>0\varepsilon>0?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Computational number theory; integer factoring
Posed by
—
Year posed
—
Years open
—
Solved
2026-10-29
Model
Claude Opus 5.5
Vendor
Anthropic
Collaborators
Isaac Rudich, Louis-Martin Rousseau
Verification
Lean-checked, statement unaudited
Publication
Preprint
Significance
38 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1 (in Lean): one deterministic Turing machine (Mathlib's TM2 model, every alphabet finite, input and output in binary) outputs the smallest prime factor of NN and, for every k≥1k\ge1, halts within Ck2n/kC_k2^{n/k} steps on nn-bit inputs, so in time 2o(n)=No(1)2^{o(n)}=N^{o(1)}. Theorem 2 (not in Lean, a few lines): applying it at most log⁡2N\log_2N times gives the complete factorization in time No(1)N^{o(1)}. The algorithm is galactic and slower than the heuristic sieves; what is new is a proved deterministic No(1)N^{o(1)} bound.

What the AI did

Per the paper and its Hexagon provenance statement, all the ideas were AI-generated: the reduction to counting divisors with prescribed leading bits, the choice of method (a re-proved part of the counting engine of Anthropic's 3-SAT preprint) and the whole 36,000-line Lean proof were produced by Claude Opus 5.5 agents, which also drafted the exposition. The two authors posed the questions, designed and audited the 13-line formal statement, and edited the text; they say they did not read the proof.

Verification

No independent mathematician has checked this yet. Lean-checked on this site's ladder, not Lean-verified. Checked here on 15 November 2026: the Hexagon paper 2610.00600v1 and its provenance page, which carry the AI disclosure. Palomar entry PALOMAR-2026-10-28-000015 v1 read: source IsaacRudich/SubexponentialDeterministicFactoring at commit 5f5ff8f, Lean v4.35.0, Comparator theorem Factoring.subexponentialRate, permitted axioms propext, Quot.sound and Classical.choice, kernel replays by Palomar (nanoda, con-ron). Challenge.lean (79 lines, Mathlib imports only) was read in full: factoring is Nat.minFac; the machine is a Mathlib TM2ComputableInTime with binary encodeNat on input and output; every stack alphabet must be finite, which closes the infinite-alphabet loophole in Mathlib's model; time is the step bound as a function of input bit length; and one machine comes before every k, with a constant per k. That is the headline, stated faithfully, for the smallest prime factor; full factorization is a short argument outside Lean. A grep of all 146 Lean files (about 36,000 lines) found no sorry outside the challenge stub and no axiom, admit, native_decide, implemented_by, extern or unsafe. Not rebuilt here, and the repository has no CI. No independent formal statement (Formal Conjectures or a tracker) was found.

Sources

Submitted by MellowGander562 on

Changelog2 changes

Discussion