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. Its follow-ups are listed on Exact Fourier transforms below n log n.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 14–16 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-07 | dysfunctor/network-coding-counterexample (GitHub; write-up Swap, Don't Route; latest commit 2ad45b0, 8 October 2026) |
Use (consequence in network coding) | Claims counterexamples to the undirected network coding conjecture of Li and Li (2004): a network with 33 vertices on which an XOR code achieves rate 1 while the maximum concurrent multicommodity flow is at most 149/150, and a 32-vertex variant with flow at most 125/126. The construction is derived from the XOR swap at the core of the manuscript's bit network; the write-up states that the counterexample does not rely on the multiplication result being correct. It also states that the network refutes Theorem 6.3 of Xiahou, Li, Wu and Huang (IEEE Transactions on Information Theory, 2014) on layered networks. | GitHub repository; the README states that all content is AI generated. It provides exact checkers using only Python's standard library and a Lean 4 formalization of the 33-vertex case, which the README describes as free of sorry.
|
| 2026-10-07 | erayyap/integer-multiplication-kappa (GitHub) | Extension | Improves the exponent from κ = 2−182 to κ = 2−59.335, with a manuscript, exact verifiers and gate-level network checkers. | The README states that the results were produced by Claude Opus 5.5 working as an agent directed by the repository owner, are computer-assisted, have not been refereed and are not formalized in Lean. |
| 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". |
| 2026-10-08 | Swapnil Jain, Swapnil-jain/integer-mult-kappa (GitHub; Ceilings and Impossibility Results for Finite Witnesses of Sub-n log n Integer Multiplication, version 1 on Zenodo, 10.5281/zenodo.23265442) | Extension (conditional) | In the manuscript's model, a conditional witness κ = 6685733/1010 ≈ 6.69·10−4. It builds on the manuscript and on the CrocSwap project, and uses results from open pull requests there. The repository also lists routes that were tried and do not improve κ. | The README calls it a conditional research draft. It states that a corrected version 2 was posted on ResearchGate on 11 October 2026, and that the work was done with assistance from Claude (Anthropic). |
| 2026-10-08 | pranavbalakri/integer-mult-bounds-improvement (GitHub) | Extension (conditional) | A proposed conditional value κ = 0.000036942, building on Swapnil Jain's round-six construction, with a linear exact-arithmetic precision guard. | GitHub repository, presented as a proposed extension. |
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.