Integer multiplication below n log n

Follow-up works

• Douglas Colkitt and contributors, integer-mult-bounds ("A sharper exponent for integer multiplication") (GitHub repository, 2026). A community project, explicitly "conditional on the original OpenAI #109 framework", reporting $\kappa=0.001672660197076918$ via new finite constructions and exact certificates, with scoped Lean checks of finite and arithmetic contracts that the README says "do not formalize the whole multiplication algorithm"; the maintainer credits OpenAI Codex assistance.
• Eray Yapağcı, Integer multiplication below n log n: improving κ from 2⁻¹⁸² to 2⁻⁵⁹·³³⁵ (GitHub repository and preprint, 2026-10-07). Reports an improved exponent within the paper's construction, supported by exact verifiers and gate-level network checks; it identifies its constructions, computations and text as produced by Claude Opus 5.5 and describes the work as unrefereed and not Lean-formalized. [AI-generated per source]
• Hrrsmjd, Integer multiplication below n log n: the exponent κ = 2⁻⁷⁴ (GitHub addendum, 2026-10-07). Claims $\kappa=2^{-74}$ through changed axis routing, a smaller address-interchange network and revised precision parameters, relying on the rest of the OpenAI argument; its Lean 4 file IntMulKappa.lean covers network counts, swap-exponent certificates and parameter inequalities but not the machine model, algorithm or structural lemmas.
• Swapnil Jain, integer-mult-kappa (GitHub repository, 2026). A self-described conditional research draft building on the paper and on Colkitt's repository, reporting a witness κ = 6685733/10^10 whose moment certificates and assembly inequalities are checked in Lean 4 (arithmetic only, not the full complexity theorem); the README says it was done "with assistance from Claude (Anthropic)".
• Swapnil Jain, Ceilings and Impossibility Results for Finite Witnesses of Sub-n log n Integer Multiplication (Zenodo, doi:10.5281/zenodo.23265442, v1, 2026-10-09). Proves stated limits on how much exponent saving finite certified witnesses can give in the paper's framework; some of the results depend on a hypothesis (H1) that the abstract flags as unproven.
• Volkan Dağlı, Zerrin Dağlı, Dağhan Dağlı, Bipartite Carrier Compression and Machine-Certified Bounds in Schönhage Trilinear Multiplication Tensors (arXiv:2610.14263, 2026-10-09). A 5-page note in a conditional framework "originating from OpenAI Preprint #109" reporting a carrier-matching improvement to $\kappa\approx4.131076535\times10^{-5}$, with exact arithmetic certificates and a Lean 4 check of the wire-reduction identity.
• Klakocik, below-nlogn (GitHub repository, 2026). An experimental Rust toolbox that implements and tests some of the paper's finite gadgets (motif networks, shear factorization, butterfly layers, Gaussian resampling matrices); the README says the sections it does not implement are documented only.
• Doug Colkitt (@0xdoug), post on X (2026-10-07). Announces an update to the community bound tightening the paper's κ = 2⁻¹⁸² to κ = 2⁻⁷⁸.
• Doug Colkitt (@0xdoug), post on X (2026-10-21). Announces a new community checkpoint κ = 0.00268647 ≈ 2⁻⁸·⁵⁴⁰, i.e. T(n) = O(n(log n)⁰·⁹⁹⁷³¹³⁵³), described as "a 2^173 fold improvement from the OAI result".

Comments and discussion

• Hacker News, Auto Research: Integer multiplication below n log n (HN item 50047664, 2026-10-11). A thread about the agent-driven community effort to raise κ beyond the paper's 2^-182, with debate about cost models and the value of such constant-chasing.
• Olof S (@OSalberger), post on X (2026-10-14). Notes that the companion sub-n log n Fourier result assumed O(1) arbitrary-precision complex arithmetic and asks whether this integer-multiplication result does the same.
• Cairn Commons (@CairnCommons), post on X (2026-10-17). Asks which model of computation a Lean statement of the result fixes, since "sub n log n" depends on it (multitape TM vs circuits vs RAM).

Formalization

• Prove2Me, Integer Multiplication Below n log n campaign (Prove2Me, viewed 2026-10-21). A Lean 4 campaign page that lists completed missions labelled κ = 1/2^182 ("OpenAI manuscript construction"), 1/2^154 and 1/2^129, plus a best formalized bound of κ ≥ 3.6 × 10^-5; the page does not specify which parts of the asymptotic theorem these missions cover.
• platypii and contributors, Integer multiplication in Lean (GitHub, accessed 2026-10-21; statement file). The README reports a completed unconditional proof on Mathlib's Turing.FinTM2 with $\kappa=127238784/2^{46}$; the public statement specifies a fixed finite multi-stack machine computing natural-number multiplication in worst-case $O(n(\log n)^{1-\kappa})$ time, with $n$ the total encoded input length.
• Kenny Daniel (@platypii), post on X (2026-10-22). Reports a Lean-proved improvement to κ = 2^-14.0246 and work toward the stronger community bound of 2^-8.37 from Colkitt's repository.

Related prior literature mentioned by others

• David Harvey and Joris van der Hoeven, Integer multiplication in time O(n log n) (Annals of Mathematics 193, 2021). Julian Henry's exposition identifies this paper's Gaussian-resampling and synthetic-transform construction as the framework retained by the OpenAI manuscript, including its use as the multiplier for smaller polynomial products.

Possibly relevant literature (found by the agent, not checked)

• Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen, Lower Bounds for Multiplication via Network Coding (arXiv:1902.10935, 2019). Shows that, assuming a network-coding conjecture, constant-degree Boolean circuits for multiplication need size Ω(n lg n); this is relevant to the paper's lower-bound scope discussion (Section 1, "Lower-bound scope"), which concerns the multitape model rather than circuits.
• M. Dietzfelbinger, W. Maass, G. Schnitger, The complexity of matrix transposition on one-tape off-line Turing machines (Theoretical Computer Science 82(1), 113–129, 1991). Gives transposition lower bounds in a restricted Turing-machine model; relevant to the paper's corollary on k×k binary matrix transposition in O(k^2 (lg k)^(1-κ)) time.
• Raphael Clifford, Markus Jalsenius, Tight Cell-Probe Bounds for Online Integer Multiplication and Convolution (arXiv:1101.0768, 2011). Proves tight Θ((d/w) log n) per-digit cell-probe bounds for online multiplication; relevant to delimiting the paper's offline multitape claim against known online lower bounds.

Digests and expositions

• Julian Henry, On Multiplication, Vol. V: Below n log n (blog, 2026-10-08). Explains the address and butterfly networks, the origin of the small exponent saving, the distinction from the companion exact-DFT model, and the conditional community improvements.
• Max Severance, Integer Multiplication Below n log n: Mining the Constants, and Why the Real Saving Is Cubic (locals.tf, 2026-10-11). Examines the cost inequalities and coupled parameter losses behind $\kappa$, proposes alternative constants and describes unsuccessful attempts to reduce address-exchange costs.

News and blogs

• FindGoodAI (AI Outpost), OpenAI put multiplication and Fourier transforms below n log n. Here is what I find remarkable (2026-10-07). An unsigned personal reading of this paper and the companion exact-DFT manuscript, focusing on the size of κ and on the absence of a Lean link.
• Yash Thakker (explainx.ai), OpenAI Math Results: 8 Claims, Lean Status, Expert Views (2026-10-07, updated through 2026-10-15). Has a section on this paper describing it as having the thinnest verification trail of the eight results covered, and tracks the community κ improvements.
• Max Severance, The Turing Machine Is Not a CPU: OpenAI's n log n Multiplication on AVX2 (locals.tf, 2026-10-11). Reports AVX2 experiments inspired by the paper's primitives and discusses the distinction between its tape-model asymptotics and practical processor costs.
• Proofs and Prompts, Trackers for progress on Quasi-Riemann and integer multiplication (newsfeed entry, 2026-10-13). Discusses the paper's small positive exponent saving and points readers to the community effort tracking improvements to $\kappa$.
• Craig Citro (@craigcitro), post on X (2026-10-22). Recommends David Harvey's note on understanding the o(n log n) result, both for its technical content and for its reflections on math and AI.
• Yash Chaudhary (@YashChaudharyAI), post on X (2026-10-22). Summarizes David Harvey's note as calling the claim plausible after checking "the core gadget only", with κ = 2^-182 and no practical speedup.