Integer multiplication below n log n
Integer multiplication below n log n is the subject of a manuscript dated 23 September 2026 in OpenAI's public mathematics collection (github.com/openai/math). Schönhage and Strassen proposed in 1971 that n log n is the optimal order of growth for multiplying two n-bit integers, and Harvey and van der Hoeven reached that order unconditionally. The manuscript claims a strict saving in the logarithmic factor on a multitape Turing machine. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.
The original result
- Claim. One deterministic Turing machine, with a fixed finite alphabet and a fixed finite number of one-dimensional tapes, computes the exact product of two n-bit integers for every n in worst-case time O(n(lg n)1−κ) with κ = 2−182. The manuscript states that this refutes an eventual Ω(n log n) lower bound for every fixed multiplication machine in this model, and that its constants and thresholds are "extremely large".
- Stated consequences. Exact division and integer square root in the same time bound. Combined with the reduction of Harvey and van der Hoeven, a fixed multitape machine that transposes a row-major k × k binary matrix in O(k2(lg k)1−κ) time.
- Method, as described in the paper's introduction. The algorithm starts from Harvey and van der Hoeven's Gaussian-resampling reduction and uses Nussbaumer's synthetic polynomial transforms. Two tape procedures save both data movement and arithmetic: an interchange of two address fields whose intermediate steps form XOR combinations of data, and simultaneous butterfly layers. Both come from fixed finite linear networks built on the three-element subsets of a 100-element set, whose attached subspaces give a strict deficit in the number of smaller recursive calls; this deficit is the source of the power saving.
- Source. Integer multiplication below n log n in the openai/math repository (commit
adc7f12). The collection's index lists no Lean formalization for this result. - Earlier results, as summarized in the paper. Schönhage and Strassen (1971): O(n log n log log n). Harvey and van der Hoeven, Integer multiplication in time O(n log n) (Annals of Mathematics, 2021). Harvey and van der Hoeven, Integer multiplication is at least as hard as matrix transposition (arXiv:2503.22848, FOCS 2025): an Ω(m log m) lower bound for transposition on every fixed machine would imply the corresponding lower bound for multiplication. The manuscript notes that its address procedure computes XOR combinations, so it lies outside models restricted to moving data.
- Companion result. The same finite complex network is used in a separate manuscript in the collection, An explicit power saving for the exact discrete Fourier transform (25 September 2026), which claims O(n(log n)1−10−13) operations in an exact complex-arithmetic model. That is a different model, not a bit-complexity consequence.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 14 October 2026) |
|---|---|---|---|---|
| 2026-10-07 | D. Colkitt (maintainer) and contributors, CrocSwap/integer-mult-bounds (GitHub; A sharper exponent for integer multiplication; README at commit bce54fb, 13 October 2026) |
Extension (conditional) | A community project that improves the exponent while assuming the manuscript's framework. Its current reviewed result (pull request #1094) is κ = 836330098538459/5·1017 ≈ 0.0016727. Earlier patches against the unmodified source are kept, among them 2−129 with the original network and a sharper recurrence comparison. The project reports exact certificates, independent audits and Lean packages for stated finite and arithmetic contracts. | The README states that "the original #109 framework and retained all-size interfaces remain assumptions" and that the project "is not full formal verification, independent human peer review, a worldwide priority claim, or a practical multiplication benchmark". The maintainer reports OpenAI Codex assistance. |
| 2026-10-08 | odepoint/intmultspam (GitHub; a fork of the preceding project) | Extension (conditional, experimental) | AI-generated notes and exact-arithmetic scripts report conditional values κ ≈ 5.93·10−10 (a "pair-star" complex network) and κ ≈ 1.48·10−9 (assembly refinements), both depending on the complete upstream theorem. | The repository description calls it "entirely unverified"; the README calls it "a hobby project, not a research paper". |
Notes
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
- The exponents above are improvements of a theoretical bound, not measured running times.