The improvement is so small that rounding it casually would erase it. The mathematical claim is large enough to challenge a conjecture that has stood since 1971.
OpenAI integer multiplication research claims an exact, deterministic algorithm for multiplying two (n)-bit integers in less than (n\log n) asymptotic time. The saving sits in the exponent of the logarithm, with an original value of (\kappa=2^{-182}). If correct, the result overturns the Schönhage–Strassen conjecture that (n\log n) is the optimal growth rate in the ordinary multitape bit model.
This isn’t a demonstrated upgrade for your calculator. The manuscript describes enormous constants and thresholds, and complete independent verification has not been established by the public materials reviewed here.
The interesting question is how the algorithm crosses that boundary, and whether its ideas can survive scrutiny and become something stronger.
Table of Contents
1. What OpenAI Integer Multiplication Actually Claims
The OpenAI integer multiplication paper, titled Integer Multiplication Below n log n, is dated September 23, 2026. OpenAI included it in its October 6 mathematics release as result family 109.
Here, (n) measures the length of each input in binary. Two numbers with thousands of bits are different workloads from multiplying two ordinary machine integers. The algorithm must return their exact product, represented with (2n) bits, including leading zeros when necessary.
OpenAI Integer Multiplication: Key Claims, Limits and Verification
| Key Fact | What the Paper Says |
|---|---|
| Problem | Multiply any two n-bit integers exactly |
| Claimed Bound | O(n(log n)1−κ), with κ = 2−182 |
| Guarantee | Deterministic, worst-case, correct at every input length |
| Computation Model | One fixed machine, finite alphabet, fixed number of one-dimensional tapes |
| Mathematical Significance | Challenges the conjectured n log n optimum in that model |
| Practical Status | Extremely large constants and thresholds, no demonstrated production speedup |
| Verification Status | Preprint, with no full Lean formalization listed for this manuscript as of October 8, 2026 |
The fixed-machine requirement matters. The construction cannot quietly acquire more tapes, a richer alphabet, or unlimited arithmetic instructions as inputs grow. Reading, writing and moving through stored bits all cost time.
2. From Karatsuba To Harvey–Van Der Hoeven
Large integer multiplication has been getting asymptotically cheaper for decades. Schoolbook multiplication pairs digits individually, producing quadratic work. Karatsuba showed that clever reuse of partial products could beat that pattern.
Later methods moved toward polynomial evaluation and Fourier transforms. Schönhage and Strassen’s 1971 algorithm reached (O(n\log n\log\log n)), and subsequent work narrowed the remaining overhead.
OpenAI Integer Multiplication: Algorithm Complexity Comparison
| Algorithm or Method | Familiar Complexity Bound | How to Read the Comparison |
|---|---|---|
| Schoolbook | O(n2) | Straightforward digit-by-digit baseline |
| Karatsuba | O(nlog2 3), approximately O(n1.585) | Fewer recursive partial products |
| Schönhage–Strassen | O(n log n log log n) | Transform-based multiplication |
| Harvey–van der Hoeven | O(n log n) | Established theoretical bit-complexity benchmark |
| OpenAI Preprint |
O(n(log n)1−κ), κ = 2−182 | Claimed improvement below the conjectured optimum |
This table compares growth rates, not stopwatch results. It also compresses a history whose earliest results were expressed using circuits and related models.
The Harvey van der Hoeven algorithm was announced in 2019 and published in 2021. OpenAI’s claim doesn’t contradict its theorem. An upper bound says an algorithm can achieve a certain cost. Another algorithm can improve that bound without making the earlier result false.
The disputed claim is optimality: whether every multiplication algorithm must eventually pay at least a constant times (n\log n) in this model.
3. Why The Tiny Exponent Matters
The new bound changes the logarithmic factor, not the exponent on (n). That distinction is easy to lose in screenshots.
Ignoring unknown constant factors, compare the proposed growth term with the previous benchmark:
[ \frac{n(\log n)^{1-\kappa}}{n\log n} =\frac{1}{(\log n)^\kappa}. ]
For every fixed positive (\kappa), this ratio tends to zero as (n) grows without bound. Mathematically, that is a strict asymptotic improvement. With (\kappa=2^{-182}), it happens painfully slowly.
The OpenAI integer multiplication claim therefore changes the answer to “Can this boundary be crossed at all?” It doesn’t establish a useful speedup at an input size anyone can conveniently store.
Nor does it establish linear-time multiplication. The logarithmic exponent remains positive, and the extra factor keeps growing. The ultimate optimum remains unsettled.
Finally, (n\log n) was a conjectured lower bound here, not a universal law of computation. Other tasks and computation models have different limits. A multiplication result doesn’t undo the lower bound for comparison-based sorting.
4. How Multiplication Becomes Convolution
Consider (123\times45). Write the numbers as polynomials in a placeholder (x):
[ A(x)=3+2x+x^2,\qquad B(x)=5+4x. ]
Their polynomial product is
[ A(x)B(x)=15+22x+13x^2+4x^3. ]
These coefficients collect every digit pair contributing to the same position. That operation is convolution. Set (x=10), handle carries, and the result becomes 5535.
FFT multiplication uses a transform to reorganize this calculation. It transforms coefficient arrays, multiplies corresponding transformed values, and applies an inverse transform. Rather than explicitly accumulating every pair separately, it exploits the structure of convolution.
OpenAI’s construction starts from the more sophisticated framework of Harvey and van der Hoeven. Gaussian resampling converts the required transforms into multidimensional transforms with power-of-two axis lengths. Polynomial representations make certain operations behave like signed shifts.
Those inherited tools matter. The proposed advance comes from reducing expensive work inside an established multiplication framework. It doesn’t replace the basic relationship between digits, convolution and carries.
5. Where The Algorithm Finds Its Saving
A transform involves arithmetic and data movement. Improving one while leaving the other at (n\log n) can leave the total cost unchanged. The paper develops separate procedures for both bottlenecks.
5.1. Rearranging Data Through Intermediate Computation
On tapes, reaching a location requires moving a head through intervening cells. Rearranging an array can therefore be expensive even when the final operation merely changes positions.
The proposed address procedure forms intermediate XOR combinations of data. These combinations eventually cancel, leaving the exact intended permutation and restoring auxiliary values.
Its cost has the form (O(Vu^\tau)), where (V) is stored bit volume, (u) measures address-field width and (\tau<1). The saving comes from computing during rearrangement rather than treating records as objects that can only be moved intact.
An analogy is sending combinations of messages that a receiver can later disentangle, rather than forwarding every message separately. The analogy explains why mixing data might help. The proof must still show that the original bits arrive at exactly the intended addresses, with every intermediate operation charged.
5.2. Applying Butterfly Operations In Batches
Butterfly operations combine pairs of values through sums and differences. The construction organizes simultaneous layers using fixed linear networks and carefully managed representations.
The recursive work grows more slowly than straightforward repetition would require. The key inequality says the network uses fewer smaller calls than the corresponding unsaved construction.
This is the conceptual engine of the integer multiplication algorithm. Turning it into a theorem requires accounting for padding, coefficient widths, addressing, cleanup and exceptional cases. The improvement survives only if those costs also fit below the target bound.
The construction also calls the established (O(n\log n)) multiplier on smaller packed polynomial problems. That isn’t circular reasoning: those calls use an already available algorithm, not the improved theorem being proved. Their aggregate cost must fit within the new overall budget.
6. How Approximate Calculations Produce An Exact Answer
The presence of complex numbers doesn’t automatically imply infinite-precision hardware. The integer theorem uses finite representations and charges for their bit costs.
Intermediate values include Gaussian dyadics, complex numbers whose real and imaginary components have power-of-two denominators. The construction uses controlled truncation and tracks how errors propagate through transforms and products.
After reversing the relevant scales, the paper bounds each recovered coefficient’s error strictly below (1/2). Because the true coefficient is an integer, rounding to the nearest integer identifies it uniquely. Carry propagation then recovers the binary product.
For intuition, an approximation of 37.2 identifies the integer 37 when the error is known to be below half a unit. Without the error guarantee, the same decimal tells you much less.
This addresses a common objection to OpenAI integer multiplication: approximate intermediate arithmetic can support an exact final result. The important question is whether the proof correctly establishes the precision guarantee and includes its computational cost.
7. What Has Actually Been Verified?
OpenAI released many mathematical manuscripts together, with different verification statuses. Some have Lean formalizations. That does not make every result in the collection machine-checked.
As of October 8, 2026, the public formalization catalogue lists no full Lean development for this integer-multiplication manuscript. The reviewed materials also do not establish complete independent verification of its argument.
Lean can check a formally stated theorem and its proof. The scope of that theorem still matters. Verifying a finite algebraic identity or a parameter inequality is different from verifying the complete multiplication algorithm, its correctness and its running time.
Likewise, reproducible numerical certificates and tests can catch mistakes without establishing every claim for arbitrarily large inputs. They are useful evidence with defined limits.
This is particularly important for a result about running time. A program can return correct products in every test while its implementation fails the claimed asymptotic bound. Correctness and complexity require separate arguments, and both must match the precise machine model.
The right way to assess OpenAI integer multiplication is to inspect the proof obligations: the recursive savings, layout invariants, precision analysis and complete cost accounting. A preprint deserves neither automatic acceptance because AI produced it nor automatic rejection for the same reason.
8. Why Your Software Won’t Suddenly Multiply Faster
Big-O notation hides constant factors and says little about manageable inputs when thresholds are enormous. A slower-growing expression can still describe a slower implementation across every workload you encounter.
The manuscript explicitly presents its algorithm as a bit-complexity construction. Below a fixed cutoff, it uses schoolbook multiplication, ensuring that one machine handles every input length. Correctness at every length doesn’t imply superior speed at every length.
Searching for the fastest integer multiplication algorithm therefore requires a second question: fastest under which conditions? Theoretical asymptotics, library performance and CPU instruction latency are different comparisons.
For developers, the OpenAI integer multiplication result currently offers a research direction rather than a reason to replace working arithmetic code. Meaningful adoption would require an implementation, benchmarks, memory analysis and comparisons against optimized alternatives.
There is no justified practical crossover size to report from the available evidence. The proof describes an algorithm, so this is more than a bare existence assertion. A deployable implementation remains a separate engineering task.
For an implementation study, input sizes, representation formats and memory traffic would be essential measurements. A benchmark should expose those conditions rather than presenting the exponent alone as a performance forecast.
9. What The Follow-Up Refinements Claim
The original exponent is already attracting attempts to tighten the construction. Douglas Colkitt’s follow-up repository records witnesses including (2^{-78}) and (2^{-59}).
As of October 8, 2026, its strongest supplied conditional witness is
[ \kappa=\frac{83}{10^{12}}=8.3\times10^{-11}>2^{-34}. ]
The draft changes how compact control fields are moved and adjusts parts of the network and precision accounting. Its claims depend on the original manuscript and its own written extensions. The repository explicitly states that independent mathematical review and full formal verification have not been supplied.
The distinction matters when discussing OpenAI integer multiplication updates. A large increase in (\kappa) measures a larger asymptotic exponent saving. It does not mean multiplication runs millions of times faster on existing hardware.
These extensions offer concrete arguments to examine. Until their dependencies and new proof obligations are checked, they should be reported as conditional refinements.
10. Implications Beyond Multiplication
The paper’s consequences reach other computations, but each requires attention to its assumptions.
10.1. Division, Square Roots And Transposition
The manuscript claims matching asymptotic bounds for exact integer division, including quotient and remainder, and for the integer square root. Classical Newton-style reductions perform arithmetic at increasing precisions, with the final stage controlling the overall multiplication cost.
It also derives a faster fixed-tape procedure for binary matrix transposition. This connects arithmetic complexity to the cost of reorganizing stored information. Its use of intermediate XOR computation places it outside models that restrict algorithms to moving intact records.
10.2. The Fourier Result Uses Different Rules
A companion manuscript claims an exact discrete Fourier transform below (n\log n), using a logarithmic exponent of (1-10^{-13}).
That theorem counts exact complex-field operations at unit cost, permits unrestricted coefficients, and supplies a specified Fourier root. It is not the same bit-complexity claim as the integer theorem, and it does not establish a numerically stable floating-point FFT improvement.
Multiplication also isn’t factorization. Finding factors of a large integer is a different problem. This result does not provide an algorithm that suddenly breaks encryption.
11. What This Says About AI-Assisted Discovery
OpenAI attributes its mathematics release to an unreleased internal frontier model. That provides context for the work, but it doesn’t identify the model as a particular public ChatGPT product.
The distinctive feature of OpenAI integer multiplication is its attempt to connect finite algebraic constructions with tape layouts, transform arithmetic and precision management. The proposed saving depends on those pieces working together.
This also changes what useful participation can look like. Researchers can check the central construction, improve its exposition, challenge a cost estimate, formalize a lemma or explore a stronger network. Follow-up work can matter even before practical software appears.
The next milestone should be a clearer, independently checked understanding of the argument. Stronger exponents would be welcome, but claims accumulate value only when their foundations remain sound.
For builders watching AI research, this is a reason to track mathematical methods and verification, alongside the headline numbers.
12. The Crack Matters, If It Holds
The original improvement is microscopic. The proposed change to our understanding of computational limits is substantial. A conjectured optimum, if overturned, becomes a starting point for new questions about what the true limit is.
OpenAI integer multiplication deserves attention for its mechanism, its theoretical implications and the scrutiny still required. The paper provides something specific to inspect, while the practical claims remain limited.
For now, read the theorem, distinguish the computation models and follow independent checks before treating refinements as established records.
Follow Binary Verse AI for clear explanations of AI research, the ideas behind new proofs, and what changes when the evidence becomes stronger.
1. What is the fastest integer multiplication algorithm?
Harvey–van der Hoeven’s algorithm established the peer-reviewed theoretical benchmark of (O(n\log n)) bit operations. OpenAI’s 2026 preprint claims a smaller asymptotic bound, with further conditional refinements proposed afterward. The fastest algorithm in practice depends on input size, hardware and implementation; a better theoretical bound does not automatically deliver faster software.
2. Why does OpenAI’s tiny improvement over n log n matter?
Its significance is crossing a conjectured boundary. For any fixed positive (\kappa), (n(\log n)^{1-\kappa}) grows asymptotically more slowly than (n\log n). If the proof is correct, it disproves the Schönhage–Strassen optimality conjecture in the stated model, even though the original saving is far too small to establish useful practical performance.
3. Does OpenAI’s integer multiplication algorithm require infinite precision?
The integer-multiplication claim uses finite bit representations on a fixed multitape Turing machine. The paper controls approximation errors tightly enough to recover exact integer coefficients through rounding and carry propagation. Its companion Fourier-transform result uses a different exact-arithmetic model, so the two claims should not be treated as interchangeable.
4. Has OpenAI’s integer multiplication proof been verified?
As of 8 October 2026, the result is a preprint, and no full Lean formalization is listed for this manuscript in the public catalogue. Full independent verification has not been established by the sources reviewed here. Reproducible calculations, parameter certificates and finite tests support checking the work, but do not verify the complete theorem.
5. Will this breakthrough make computers faster or break encryption?
The paper does not demonstrate an immediate speedup for everyday computers or cryptographic software. Its extremely large constants and thresholds limit practical conclusions. Faster multiplication also does not provide a fast integer-factorization algorithm. The immediate implications concern computational limits and research techniques, with practical applications requiring further work.