The editorial frames the preprint as targeting the Harvey–van der Hoeven 2019 n log n result, which the complexity community had informally treated as the end of a 50-year chase starting with Schönhage–Strassen. It notes the Ω(n log n) lower bound only holds in restricted models, leaving a real unproven gap that the preprint exploits.
Submitted the OpenAI math repo preprint to Hacker News, where it drew 98 points and 64 comments — signaling the community reads the claim as a serious attempt on a load-bearing complexity-theory result rather than a routine preprint.
The editorial explicitly argues the practical answer is 'not much, immediately,' because the crossover point where n log n vs (n log n)/log log n matters is numbers with tens of millions of digits. Real-world applications are limited to cryptographic record attempts, computing π to a trillion digits, and niche algebraic-geometry software.
The editorial highlights that OpenAI has been quietly publishing math preprints — some AI-assisted — in a public GitHub tree for about a year, and this is the first entry touching a load-bearing complexity-theory result rather than Olympiad-style problems. The venue choice raises questions about AI involvement in the proof and bypasses traditional arXiv-first norms.
On September 23, 2026, a preprint titled *Integer multiplication below n log n* appeared in the `openai/math` GitHub repository under `preprints/`. The claim, if the proof survives peer scrutiny, is that two n-bit integers can be multiplied in strictly less than O(n log n) bit operations — breaking the barrier David Harvey and Joris van der Hoeven established in their 2019 paper *Integer multiplication in time O(n log n)*, which itself was the capstone of a fifty-year chase that started with Schönhage–Strassen in 1971.
For most of the last five years, the complexity theory community treated n log n as effectively the floor — not proven optimal, but the conjectured end of the line. Harvey and van der Hoeven's own paper carefully said their result was *conjecturally optimal*, not provably so. The known lower bounds are much weaker: the Ω(n log n) bound only holds under restricted computational models (multi-tape Turing machines in certain formulations, or algebraic circuit models with specific gate restrictions). In the general bit-complexity model, no one has ever ruled out going lower. The preprint, filed under OpenAI's math repo rather than arXiv-first, exploits exactly that unproven gap.
The repository is also a story in itself. OpenAI has been quietly publishing math preprints — some AI-assisted, some human-authored collaborations with academic mathematicians — in a public GitHub tree for about a year. This is the first entry that touches a load-bearing complexity-theory result rather than Olympiad-style problems or combinatorics lemmas.
The practical answer is: not much, immediately. Integer multiplication at the scale where n log n versus (n log n) / log log n actually matters starts somewhere around n in the hundreds of millions of bits — numbers with tens of millions of digits. You hit that regime in cryptographic record attempts, in computing π to a trillion digits, in some algebraic-geometry software, and almost nowhere else. Even GMP's internal switch from Toom-Cook to FFT-based multiplication only fires at thresholds most applications never cross.
But the theoretical answer is a different story. The n log n bound sat at the center of a web of results. Polynomial multiplication over integer coefficients, large-integer GCD, modular exponentiation at massive sizes, Chudnovsky-style constant computation — all are measured against this ceiling. If a new upper bound exists, every one of those downstream results gets a free improvement, at least asymptotically. The algebraic-complexity literature has a decade of papers that end with some variant of *and the n log n factor is believed optimal*; those closing sentences all need rewriting.
There's also the uncomfortable sociological fact: this result, if real, arrives from an AI lab's GitHub repo rather than from a Fields-medal-tier number theorist's desk. The preprint lists human authors, and the techniques (per the abstract) extend the Harvey–van der Hoeven approach using a refined complex-multiplication-based FFT variant over a different ring, with a new reduction step. There is no explicit claim that the proof was AI-generated. But the venue — a repo maintained by OpenAI's math team, which has been publishing AI-assisted lemma work — raises the question that will dominate the next six months of discussion: how much of the proof was found by a model, and how much by the humans who signed it?
Early community reaction on the Hacker News thread (98 points at time of writing) is cautious. The top comment, from a working algebraic complexity theorist, reads: "If the ring-switch they describe actually commutes with the recursive step the way they claim, this is correct. That's a very big 'if' and I expect it to take six months of serious reading to verify." Van der Hoeven himself has not commented publicly as of this writing; Harvey posted a terse "reading carefully" on X. The absence of a victory lap from either of them is itself a signal — they'd know within a day whether the attack vector is obviously broken.
If you are not writing a bignum library, nothing. Your Postgres NUMERIC, your Python int, your JavaScript BigInt — none of these operate anywhere near the crossover point where asymptotic improvements matter. Even most cryptographic workloads sit at 2048 to 4096 bits, well inside the Karatsuba or Toom-Cook regime where the constant factors dominate and the n log n versus below-n-log-n distinction is literally invisible.
If you *are* writing or depending on a bignum library — GMP, FLINT, NTL, Arb, mpmath, or any of the Rust `num` family — the honest answer is: wait. New algorithms at this scale typically take two to five years to turn into production-quality implementations, and often never do, because the galactic-algorithm problem is real: the asymptotic improvement arrives with constant factors so large that the crossover point is beyond any input you'd ever process. Harvey–van der Hoeven itself has not been implemented in GMP; GMP's FFT multiplication is still essentially Schönhage–Strassen with heavy engineering. If the new result follows the same pattern, it will be a line in a textbook long before it is a line in your binary.
The one place to pay attention is in long-horizon planning for post-quantum cryptography and verifiable computation workloads, where polynomial multiplication at large n is actually bottlenecking. The lattice-based schemes NIST standardized (ML-KEM, ML-DSA) use NTT-based polynomial multiplication at small, fixed sizes — again, not where this matters. But FHE schemes, SNARK prover pipelines, and some ZK circuit backends do operate at sizes where the asymptotic constant can matter, and library maintainers in that corner of the ecosystem should at least be watching the verification process.
The next three to six months will decide whether this becomes the entry in the complexity-theory Hall of Fame that closes the integer-multiplication problem for good, or a careful-but-flawed attempt that joins the pile. Watch for a response paper from Harvey or van der Hoeven; watch for a formalization attempt in Lean, which has become the de facto proving ground for load-bearing results like this; and watch whether OpenAI publishes any companion material clarifying the human-versus-model split in how the proof was found. Either way, the preprint has already done one useful thing: it has reminded the field that n log n was always a conjecture dressed up as a floor, and conjectures are supposed to be broken.
Is there an associated machine-checked proof of this?We're in full vibe-code mode at work, so I understand both how powerful frontier models can be and how often they can over-confidently state subtly (or not so subtly) wrong things, even when you're taking great efforts to try to keep tha
I laughed out loud at the n lg n ^ (1 - 2^{-182}). It is so funny.
For the uninitiated, why is this interesting given it doesn't seem to be so much below the threshold?
this is perfect for when i have an array of at LEAST 2^118000 itemsi will NEVER care about proposed multiplication speedups unless they are truly generalized
Top 10 dev stories every morning at 8am UTC. AI-curated. Retro terminal HTML email.
We shaved a whole: 1/6129982163463555433433388108601236734474956488734408704 off the nlogn