VibeMathedMath problems solved with AI
Sign in

The Schonhage-Strassen conjecture that n log n is optimal for integer multiplication on multitape Turing machines

Schonhage and Strassen (1971) showed that two nn-bit integers can be multiplied in O(nlog⁡nlog⁡log⁡n)O(n\log n\log\log n) time on a multitape Turing machine and proposed nlog⁡nn\log n as the optimal order of growth. Successive improvements (Furer; De-Kurur-Saha-Saptharishi; Harvey, van der Hoeven and Lecerf) culminated in the unconditional O(nlog⁡n)O(n\log n) algorithm of Harvey and van der Hoeven, matching the conjectured optimum. Is nlog⁡nn\log n optimal in this model, that is, does every fixed multitape Turing machine computing the product of two nn-bit integers need time Ω(nlog⁡n)\Omega(n\log n)?

Result
Disproved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Algorithms; bit complexity of integer multiplication
Posed by
A. Schonhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing 7 (1971), Section 1
Year posed
1971
Years open
55y
Solved
2026-09-23
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Unreviewed
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
48 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: one fixed deterministic multitape Turing machine multiplies two nn-bit integers exactly in worst-case time O(n(lg⁡n)1−κ)O(n(\lg n)^{1-\kappa}) with κ=2−182\kappa=2^{-182}, for every nn, so T(n)/(nlg⁡n)→0T(n)/(n\lg n)\to0 and the nlog⁡nn\log n lower bound fails in this model. Corollaries: exact division and integer square root in the same time, and (with Harvey-van der Hoeven's reduction) transposition of k×kk\times k binary matrices in O(k2(lg⁡k)1−κ)O(k^2(\lg k)^{1-\kappa}). Not shown: any practical algorithm (constants are astronomically large), or anything about Boolean circuit size or other machine models; the true complexity of multiplication remains open.

What the AI did

Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems, published in the openai/math release (pinned commit adc7f12). The release README says the vast majority of results used one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result; this result is not among the README's stated exceptions (the Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscript is authored as OpenAI with no human author named. No Lean formalization accompanies it, and the README cautions that unformalized results could have issues.

Verification

No independent mathematician has checked this yet. Checked here: abstract, introduction (Theorem 1.1) and the history section's lower-bound scope subsection of the TeX source, read against the conjecture as the manuscript cites it. The manuscript makes the model explicit: one deterministic Turing machine with a fixed finite alphabet and a fixed number of one-dimensional tapes, exact for every input length, worst-case time. It notes that Schonhage's linear-time storage-modification-machine result and Groff's unit-cost RAM result are in other models. The algorithm and its 11 sections of tape and precision analysis were not refereed. No Lean formalization. The README cautions that unformalized results could have issues.

Sources

Changelog1 change

Discussion