Claimed AI-led

Integer multiplication below n log n, against the Schönhage–Strassen optimality conjecture

An OpenAI manuscript gives a deterministic algorithm that multiplies two $n$ -bit integers in time $O(n (\log n)^{1-\kappa})$ with $\kappa = 2^{-182}$ on a multitape Turing machine, which would beat the $O(n \log n)$ algorithm of Harvey and van der Hoeven and disprove Schönhage and Strassen's 1971 conjecture that $n \log n$ is optimal; David Harvey calls the claim plausible but says he has not checked it.

Lab: OpenAI
Model: Unreleased internal OpenAI model, not named in the release
Field: Computer science
Date: 2026-10-06
Problem posed: 1971 · open 55 yrs

Sources

Original work

GitHubOpenAI: Integer multiplication below n log n (PDF)↗

Independent commentary

web.maths.unsw.edu.auDavid Harvey: On the recently proposed o(n log n) integer multiplication algorithm (PDF)↗

What was found

Schönhage and Strassen conjectured in 1971 that multiplying $n$ -bit integers needs on the order of $n \log n$ bit operations, and Harvey and van der Hoeven reached that bound in 2021. Family 109 of OpenAI's release claims an algorithm running in $O(n (\log n)^{1-\kappa})$ with $\kappa = 2^{-182}$ , exact at every input length on one fixed finite-alphabet Turing machine with finitely many one-dimensional tapes. The manuscript is dated 23 September 2026 and was published with the release of 6 October. Harvey's note of 20 October describes three closely related manuscripts, says the work builds directly on the 2021 algorithm, and reports that others had already lowered the exponent of $\log n$ to about 0.9983. He argues that the size of $\kappa$ is beside the point, since saving a power of $\log n$ is exponentially larger than any earlier improvement in this line.

Novelty check

arXiv, 2026-10-29: abs:"integer multiplication" AND abs:"log n" returned 13 records, none before the release claiming a bound below $n \log n$ . Harvey, coauthor of the 2021 record, treats the claim as new. Within this registry the release is recorded at 2026-10-06-openai-math-collection, whose headline list does not name this family; the matrix multiplication entries concern a different problem.

Caveats and known objections

Entered at claimed: the catalogue links no Lean formalization for family 109, and Harvey says that as far as he can tell none exists. His is the only expert assessment found, and it is explicitly tentative: he writes that he has not actually read the paper, that he tried and gave up, and that he instead asked Claude Fable 5.1 to explain it, reaching after two weeks of questions the tentative belief that the main result is possibly correct. He stresses that he has not checked the proof in any serious level of detail and that his confidence would rise greatly with a formalization whose statement a Lean expert had checked. That is a domain expert's informed reading through an AI intermediary, not a check of the proof. The claim is for the multitape Turing model, and Harvey notes that Boolean-circuit and Turing-machine versions of the exponent may differ. The reliability of the surrounding collection is part of the context: OpenAI withdrew three manuscripts from it on 7 October 2026 over a sign error and revised 14 others. Autonomy is ai-led on the strictest defensible reading, as for the other families split from this release: the README attributes the results to an unreleased internal model following a single procedure, while humans chose the problems and ran the release, and no human author is named.

No independent check is recorded on this entry yet.

Reading the primary source closely enough to say whether it supports the claim counts as a check, and you are credited on the entry.

Submit a check Challenge the grade

Or on GitHub: submit a check challenge the grade send a correction or send a pull request

Entry history (1 event)

2026-10-29AddedEntered the registry graded Claimed and AI-led.

Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.

Graded claimed for verification and ai-led for autonomy. What these mean.

Cite this entry

Plain text

whataifound.org. (2026). Integer multiplication below n log n, against the Schönhage–Strassen optimality conjecture. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-10-06-integer-multiplication-below-n-log-n

BibTeX

@misc{whataifound-openai-2026-n,
  title        = {Integer multiplication below n log n, against the Schönhage–Strassen optimality conjecture},
  author       = {{whataifound.org}},
  year         = {2026},
  howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
  note         = {Result by OpenAI. Verification: Claimed. Autonomy: AI-led.},
  url          = {https://whataifound.org/finding/2026-10-06-integer-multiplication-below-n-log-n}
}

Related findings

Formally verifiedMatrix multiplication exponent bounded by 9/4OpenAI · 2026-10-06 ClaimedLower bound of 21 multiplications for 3×3 matrix multiplication over every field, with a Lean proofIndependent · 2026-10-12 Formally verifiedMatrix multiplication exponent below 2.3710449, machine-checked over every commutative ringIndependent · 2026-10-07

algorithms complexity integer-multiplication argument

← All computer science findings in the registry