Integer Multiplication Below n log n: Mining the Constants, and Why the Real Saving Is Cubic

#

OpenAI’s October 2026 mathematics release contains a proof that two n-bit integers can be multiplied below n log n on a fixed-tape Turing machine. The proof works, but its constants are so conservative that roughly 2^62 of the improvement is lying on the table for free. Pulling the paper apart, the interesting story is that the final exponent is a product of three coupled slacks, and the one number that actually controls everything — the rank deficit of a finite linear network — is only ~1.5×10⁻¹¹. It gets cubed.

TL;DR

#

• OpenAI’s “Sharing AI progress in mathematics” (Oct 6, 2026) is a 372-family dump of LLM-produced proofs. One of them, “Integer multiplication below n log n”, claims an exact, deterministic fixed-tape Turing machine computing the product of two n-bit integers in O(n (lg n)^(1−κ)), κ = 2⁻¹⁸², disproving the Schönhage–Strassen optimality conjecture in that model.
• I pulled the PDF and the LaTeX source from the openai/math repo. The proof is real, self-contained, 73 pages, with an explicit cost table and an exact-arithmetic recovery argument. It is not Lean-formalized.
• The whole n log n → n (log n)^(1−κ) improvement reduces to one inequality: a finite linear network can exchange two banks of values using s < W·m sub-operations instead of W·m.
• The paper picks its constants “deliberately conservative; no optimization is claimed.” The final exponent is κ = ½·min(g₁…g₇), a min over seven slacks, and the binding one is a product of three independently tiny numbers.
• The three are coupled to the same quantity a = 1−τ (the rank deficit exponent), so κ ∼ a³.
• Solving the constraint system: with the same proof and the same deficit, κ goes from 2⁻¹⁸² to ≈ 2⁻¹²⁰·²⁵ — a factor ~2⁶², for free, by changing eight constants.
• The real lever is the rank deficit itself, because the final κ ≈ a³ is effectively three copies of the same deficit — every capped sub-operation (the recursion, the axis count, the chunk width) reduces to a chunk interchange at deficit a.
• Attack on (b) — cheaper contiguous address-chunk exchange (failure report): the primitive is a strided transpose, and by Harvey–van der Hoeven transposition is equivalent to multiplication, so it can’t be improved in isolation. I tried three routes to decouple the chunk width c from a (wider/one-shot layout, adjacent block swaps, reversal-pass transposes); all fail, and the failure is structural: c is capped from both sides by the same deficit. The κ ~ 2⁻⁸¹ I hoped for is a hypothetical that no admissible algorithm reaches.

Background: what actually got proven

#

Integer multiplication has a clean history of barriers falling:

• Karatsuba (1962): O(n^1.585), breaking the schoolbook n².
• Toom–Cook, then Schönhage–Strassen (1971): O(n log n log log n), and a conjecture that n log n is optimal.
• Fürer (2007): n log n · 2^(O(log* n)).
• Harvey–van der Hoeven (2019): matched the conjecture exactly, O(n log n), via Gaussian resampling + synthetic (Nussbaumer) transforms.

For six years it looked like n log n was the floor. Then, on October 6, 2026, OpenAI published a repository of 372 result families produced by an internal frontier model, and one of them claims to go below n log n.

I’m deliberately not taking the claim on faith — the repo’s own README says “Some of the unformalized results could have issues”, and I checked lean/formalization.yaml: the matrix-multiplication papers (complex_omega_le_nine_quarters, complex_rectangle_omega_lt_523_div_250, …) have Lean entries. This one does not. So what follows is an analysis of a manuscript, not of a machine-checked proof.

The statement

#

Theorem 1 (OpenAI, Sept 23 2026).  There is one deterministic Turing machine A,
with a fixed finite alphabet and a fixed finite number of 1-D tapes, computing
the exact product of two n-bit integers in

    T_A(n) = O( n (lg n)^(1-kappa) ),    kappa = 2^-182,

for every n >= 1.  It refutes any eventual Omega(n log n) lower bound in this model.

Two things to notice:

1. It is a power saving inside the log factor: n log n becomes n (log n)^{0.999…}. The leading n is untouched (it must be; you have to read the input).
2. The exponent deficit is 2⁻¹⁸² — the kind of number you only write when you need it to be > 0.

The paper is github.com/openai/math/tree/main/preprints/Integer-multiplication-below-n-log-n-September-23-2026, and its build/ directory has the full LaTeX source, which is what I actually read.

The algorithm, in one diagram

#

The construction is Harvey–van der Hoeven’s entire framework, with the movement/layout subroutines surgically replaced by slightly cheaper ones:

      x (n bits) ─┐
                  ├─►┌──────────────────────────────────┐
      y (n bits) ─┘  │  radix-2^b digit split            │──► digit convolution
                     │  x = Σ x_i · 2^(b·i),  x·y = Σ c_k 2^(b·k) │
                     └──────────────────────────────────┘
                                       │
                                       ▼
                ┌────────────────────────────────────────────┐
                │  CRT map onto distinct prime axes s_1..s_m  │   (convolution preserved)
                └────────────────────────────────────────────┘
                                       │
                                       ▼
     ┌───────────────────────────────────────────────────────────────┐
     │  cyclic convolution on the prime axes                          │
     │     Gaussian resampling  →  power-of-two axes t_1..t_d         │
     │     Bluestein chirp      →  normalize to cyclic convolution    │
     └───────────────────────────────────────────────────────────────┘
                                       │   last coordinate → phase twist
                                       ▼
     ┌───────────────────────────────────────────────────────────────┐
     │  convolution over C[y]/(y^r + 1)                               │
     │     synthetic (Nussbaumer) transforms   +   signed packing     │
     │     pointwise products via the KNOWN O(n log n) multiplier ◄───┼── subroutine
     └───────────────────────────────────────────────────────────────┘
                                       │   invert normalizations; error < 1/2
                                       ▼
                     ┌──────────────────────────────────┐
                     │  round → carry propagate          │──►  x·y  (2n bits, exact)
                     └──────────────────────────────────┘

The already-known O(n log n) multiplier is invoked only as a subroutine on records of length O(rp) = o(n) (the boxed arrow above) — so there is no circularity in using it inside a proof that beats it.

Where the saving actually lives

#

Here is the crucial structural point that makes the whole paper possible.

On a fixed-tape Turing machine, the transform has Θ(log n) layers, and each layer naively scans Θ(n) stored bits. That alone is Θ(n log n) before any arithmetic is counted. So to beat n log n you must make the per-layer movement sublinear per stored bit.

The paper does this with two fixed tape procedures:

• Address-chunk interchange. Exchange two disjoint contiguous address chunks of u bits, in an array whose addresses form a complete Cartesian product, at cost O(V u^τ) for a fixed τ < 1 — instead of the naive O(V·u). Its net effect is an exact permutation, but its intermediate steps are XOR combinations of data. That’s the trick: it is not a pure permutation algorithm, so permutation lower bounds don’t apply (this is exactly the distinction Harvey–van der Hoeven flag in their §1.4).
• Simultaneous synthetic butterfly layers. Apply H₀(u,v) = ((u+v)/2, (u−v)/2) on selected coordinate bits of complex fixed-point arrays, cost O(V d^{λ’}) with λ' < 1.

Both come from a fixed finite linear network that exchanges two banks of values with prescribed signs and restores every auxiliary value. Split the array into W roles; represent the stored array at each vertex by an invertible linear “frame”; frames cancel along routes, reducing everything to an endpoint operator per role. The frames are chosen recursively so every edge is a smaller call to the same procedure.

The decisive inequality lives in §3: nested subspaces of a fixed m-dimensional space are attached to gates; the change in subspace dimension on an edge counts how many smaller operations that edge needs. Using a Franklin–Wilson / Alon 3-subset intersection gadget, the total number s of smaller calls satisfies

s < W * m                                   (the "strict total rank deficit")

  one recursion level -- exchanging two banks of fields:

      H = [h_1 h_2 ... h_m] ──┐                     ┌──► [h_1+d_1 ... h_m+d_m]
                              │  fixed linear net   │
      D = [d_1 d_2 ... d_m] ──┘  (W wires, m-dim)   └──► [d_1 ... d_m]
                                                         two linear-cost shears then
                                                         finish the swap:  (H,D)→(D,H)

      naive   : move W·m field-differences
      network : only s sub-interchanges, with s < W·m      ◄── strict rank deficit

Unrolling the recurrence — this is the whole trick:

      F(e) ≤ (s/W)·F(e/m) + O(1)          F = time / volume,  e = chunk width
        │                                 k = log_m e levels deep
        └─► F(e) ≲ (s/W)^k · F(1) = e^{ log_m(s/W) }

      s/W < m^τ    ⟹    F(e) = O(e^τ),    τ = 1 − a < 1
                                                 └── a = 1−τ  ("the deficit")

A call at parameter m·f uses s calls at parameter f, each on volume V/W. Cost normalized by volume multiplies by s/W < m on each scale-up. That strict inequality is the entire source of the power saving. Everything else is bookkeeping.

Why the answer is 2⁻¹⁸²: a min over seven slacks

#

You don’t get (log n)^{1−κ} for free. Every normalized cost in the accounting table must land below 1, and the paper defines the margin of each of the seven dominant terms:

g1 = 1 - eps*(1+c)          g2 = eps*c*(1-tau)        g3 = eps*(1-lam')
g4 = 1 - tau - eps*(2-tau)  g5 = 1/4 - delta - 3*eps/2 g6 = 1 - delta - eps
g7 = eps

kappa = (1/2) * min(g1,...,g7)

with the constants (§9.1, eq. 38):

tau = sigma = 1 - 2^-50     beta = 1/2       delta = 1/16
lam = 1 - 2^-52             c    = 2^-56     lam' = 1 - 2^-54
C1 = 20                     eps  = 2^-75     kappa = 2^-182

Substituting gives g1 > 1/2, g2 = 2⁻¹⁸¹, g3 = 2⁻¹²⁹, g4 > 2⁻⁵¹, g5 > 1/8, g6 > 1/2, g7 = 2⁻⁷⁵. So min = g2 = 2⁻¹⁸¹ = 2κ, hence κ = 2⁻¹⁸²:

   slack            value     size (log scale)               note
   ─────────────────────────────────────────────────────────────────────────
   g1 1−ε(1+c)      ~1        ██████████████████████████
   g2 εc(1−τ)       2^-181    ▏                            ◄── min = 2κ  ⟹ κ=2^-182
   g3 ε(1−λ')       2^-129    ███████
   g4 1−τ−ε(2−τ)    2^-50     ███████████████████
   g5 ¼−δ−3ε/2      ~1/4      ██████████████████████████
   g6 1−δ−ε         ~1        ██████████████████████████
   g7 ε             2^-75     ███████████████

The binding term is g2 = ε·c·(1−τ). It is a product of three independently tiny numbers. And ε, c, (1−τ) are all free-ish — but they are not independent.

The optimization: κ is a product of three coupled slacks

#

Let me write the hard inputs and the free choices separately.

Hard (non-negotiable) inputs — the motif exponents, from §3.6:

eta_b = 339/22587335000000  ~ 1.5008e-11     (bit/address motif  -> tau)
eta_c = 73/19906842167500   ~ 3.6671e-12     (complex/layer motif -> sigma)

with the requirement s/W = m(1−eta) < m^tau, i.e.

1 - tau  <  -ln(1 - eta_b) / ln m ,        m < 2^20

Everything else is a free engineering constant, subject to (Prop. 5.3, §5.3, §9.1):

0 < tau,sigma < 1 ;   max{tau,sigma} < lam < 1 ;   tau*(1+c/beta) < lam
max{lam, sigma+beta*(1-sigma)} < lam' < 1
eps < 1/12 ;   eps*C1 < 1 ;   eps*(2-tau) < 1-tau
3/4 + delta + 3*eps/2 < 1 ;   eps*(1+c) < 1 ;   eps + delta < 1

Now the diagnosis. Two structural couplings force the ceilings:

• g4 = a − ε(1+a) > 0 ⟹ ε ≲ a where a := 1−τ. The CRT/axis-layout row costs p^{τ + ε(2−τ)}; the surplus axes you expose have to be paid for by the deficit saving.
• τ(1+c/β) < λ < 1 ⟹ c ≲ βa. The chunk width K = d^c enters the inner address-swap cost V K^τ; for the layer recursion to converge, K^τ must stay below the growth rate.

So all three factors in g2 are bounded by the same small number a:

   the three factors of g2 are all capped by the SAME deficit  a = 1 − τ :

        ε    ≲  a        (g4:  CRT / axis-layout row)
        c    ≲  βa       (the layer change-of-basis recursion)
        1−τ  =  a        (the rank deficit itself)
                    │         │         │
                    └────┬────┴────┬────┘
                         ▼         ▼
        g2 = ε · c · (1−τ)  ~  a · a · a  =  a³
                                             │
                                     κ = ½·g2  ~  a³

kappa  ~  a^3        (more precisely kappa* = a^3 / 2)

Maximizing over the free parameters (I wrote a small numerical optimizer, and cross-checked against the analytic balance ε = a(1−a), c = a, which gives g2 = g4 = a³):

a* = -ln(1 - eta_b) / ln(2^20) = 1.0826e-12 = 2^-39.749      (the deficit ceiling)

kappa* = a*^3 / 2 = 6.345e-37 = 2^-120.25

Versus the paper’s 2⁻¹⁸² = 3.11e-55. A factor of 2^61.75 ≈ 4×10¹⁸, for free.

Two-step view of the headroom

#

Note that in the paper ε = 2⁻⁷⁵ while a = 2⁻⁵⁰: ε is set 10²⁵× below its permitted value, and c = 2⁻⁵⁶ is 10¹²× below its permitted value. None of that was necessary.

A drop-in improved constant set

#

Replacing eq. (38) with (using the paper’s own conservative ln m < 20, so a* ≥ η_b/20):

tau = 1 - 2^-40        # bit motif   (1-tau = 2^-40 < eta_b/20)
sigma = 1 - 2^-42      # complex motif (tighter ceiling: eta_c/20 = 2^-42.8)
beta = 1 - 2^-37       # beta -> 1 is allowed; only beta < 1 is required
c = 2^-40              # saturates the layer-recursion bound c < beta*a/(1-a)
eps = 2^-40 - 2^-80    # = a*(1-a), balancing g2 against g4
lam = 1 - 2^-77 ;  lam' = 1 - 2^-79
delta = 2^-80

giving g2 = εca ≈ 2⁻¹²⁰, g4 = a − ε(1+a) = 2⁻¹²⁰, g3 ≈ 2⁻¹¹⁹, and κ ≈ 2⁻¹²¹.

Why this is legitimate

#

Everything in the paper after §9.1 is parameter-agnostic: the running-time analysis only ever uses the inequalities, never the specific numbers. So this is a drop-in substitution of constants. The only new obligations are (i) re-verifying the finitely many numeric inequalities, and (ii) checking m^{1−a} > m(1−η_b) with the exact deficit — a fixed integer comparison. That is precisely the optimization the paper declines to do.

The real lever: κ scales cubically in the rank deficit

#

Since κ ≈ a³/2 and a = −ln(1−η_b)/ln m, the master parameter is the rank deficit η_b ≈ 1.5×10⁻¹¹ — a fixed combinatorial constant from the §3 subset-intersection construction. Because it is cubed, improving the construction dominates any amount of constant tuning:

deficit eta    a = -ln(1-eta)/ln m    kappa ~ a^3/2
1.5e-11        1.08e-12               2^-120.2      (today)
1e-8           7.2e-10                2^-92.1
1e-6           7.2e-08                2^-72.2
1e-4           7.2e-06                2^-52.2
1e-3           7.2e-05                2^-42.3
1e-2           7.3e-04                2^-32.3
0.1            7.6e-03                2^-22.1
0.3            2.6e-02                2^-16.8

Even a perfect deficit doesn’t run away, because of two caps: ε < 1/20 and g4’s ε ≲ a. So the ceiling of this architecture is κ ~ (a/ln m)³ with a < 1 — small unless η is close to 1. The candidates, in order:

1. Improve the deficit η (§3), or reduce m. κ ~ a³ and a = −ln(1−η)/ln m, so this is the master lever and it is cubically rewarded; both are self-contained (η is a combinatorial construction, m is a network dimension). This is the only lever with real content.
2. Break the cube (structural) — but this fails. It is tempting to decouple ε or c from a (each cap comes from a different row: the CRT/axis-layout row p^{τ+ε(2−τ)}, and the layer’s per-node (eK)^τ). I tried, and it does not work: both caps are the deficit, because each capped sub-operation is itself a chunk interchange at deficit a. See the (b) section for the full post-mortem.

Attack (b): cheaper exchange of contiguous address chunks

#

This is the one the prompt asked me to push on, so let me be precise about what “cheaper chunk exchange” would buy and why it is hard.

What the primitive is

#

Lemma 12 (arbitrary-width interchange): for V = P·G·B·2^{2u}, the array on [P]×[2^u]×[G]×[2^u]×[B] is permuted by

(p, h, g, d, z)  ->  (p, d, g, h, z)

   before:   [ p ][   h   ][ g ][   d   ][ z ]     h,d = u-bit address chunks
   after:    [ p ][   d   ][ g ][   h   ][ z ]     g    = gap field
                                                    p,z  = prefix / suffix spectators

in O(V u^τ) steps. So: swap two u-bit coordinate axes, with a spectator field g between them and prefix/suffix spectators outside. That is a (strided) transpose of a 2^u × 2^u grid, not a contiguous block swap. And the exponent is τ = 1−a, with a the rank deficit.

Where the cap on c comes from

#

In Lemma 16 (the transform layout), the positional reorder is a D × q transpose of K-bit chunks, done with ≤ Dq−1 individual chunk exchanges, each costing O(Tp K^τ); with Dq = O(p/K) this is

O(Tp * p * K^(tau-1))     ==>  margin g2 = eps * c * a ,   K = d^c = p^(eps*c)

So the width of the chunks is what buys the saving: K^{τ−1} shrinks as K grows. That makes it look like the whole game is to force K up — and my first draft of this post claimed exactly that: a one-shot layout with K ≈ ℓ decouples c and gives κ ~ 2⁻⁸¹. That claim was wrong. Here is what happens when you actually try it.

The attempt: widen the chunks — failed

#

The cap on c is two-sided. c (equivalently K = d^c) appears in two rows of the cost table with opposite signs:

• g2 = εca increases with c — wider chunks make the positional layout cheaper.
• g3 = ε(1−λ') decreases with c: the layer recursion in §5.3 gives λ' > τ(1+c/β), hence 1−λ' < a − (c/β)(1−a), hence g3 ≲ ε(a − (c/β)(1−a)).

Maximizing min(g2, g3) over c balances the two at c ≈ βa, giving κ ~ βa³/2 — the paper’s regime. Forcing the layout cheaper (g2 → ∞) does not remove the cap: it moves the optimum to c → 0, where g3 → εa and κ ~ a²/2. So the ~2⁻⁸¹ exists only if the layout is genuinely free — i.e. if the array is already in the layer’s chunk-major format, which is the very thing being paid for. And c → 0 is the opposite of “use bigger chunks”: the one-shot-layout idea was backwards.

Why the layout can’t be made free (three routes, all dead)

#

1. Bigger, fewer exchanges. A balanced recursive block transpose pays exactly the same V p K^{τ−1}. It is a fixed point of the recurrence, because the top level always swaps two blocks of p/2 bits and the deficit cost of an L-bit chunk interchange is L^τ.
2. Adjacent block swaps. A truly contiguous AB → BA is indeed O(V) (three reversals), but the layout swaps strided chunks, and the permutation is a genuine transpose — it swaps the two halves of the chunk-index bits. It is not a product of O(1) contiguous block swaps. (Checked on a 2×2: the reversal composition is the identity, not the transpose.)
3. Reversal-pass / bit-permutation transposes. A fixed bit-permutation can be routed in O(log V) full passes, and here log V = Θ(p) = Θ(log n), so this costs O(V log V) = O(V p) — normalized p, margin 0. That is exactly break-even n log n. The paper’s V p K^{τ−1} = V p^{1−εca} is better than that (1−εca < 1 for εca > 0). So the paper’s chunk layout is already faster than any pure-movement transpose; there is no reversal trick hiding in it.

And the cap is the deficit, not bookkeeping. The layer’s per-node overhead is the cost of a change-of-basis chunk swap on slots of width eK (the packed-rectangle lemma); its sublinearity in the node size e is what forces K < e^{(1−τ)/τ}. A change-of-basis swap is a chunk interchange; a chunk interchange is the transpose primitive; by Harvey–van der Hoeven the transpose primitive is pinned to a. So g2, the c-cap in g3, and the deficit are the same number. c is capped by a not for accounting reasons but because it is a.

Corrected summary

#

So (b) has no independent content. Every factor I hoped to decouple (c, and ε) is capped by the same deficit, because each capped sub-operation is literally a chunk interchange at deficit a. The architecture’s κ ~ a³ is three copies of one number — which is a less exciting conclusion than the 2⁻⁸¹ in my first draft, but it is the correct one. It also says something clean: constants aside, the entire result is a function of the single scalar η_b ≈ 1.5×10⁻¹¹.

What I Learned

#

1. Read the cost table before the theorem. A result stated as O(n (log n)^{1−κ}) tells you almost nothing until you find what κ is the minimum of. Here κ is ½·min of seven slacks, and the binding slack is a product — so the “result” was hiding two free factors.
2. “No optimization claimed” is an invitation. Three of the eight constants (ε, c, and the choice of τ) were 10¹²–10²⁵ below their permitted values. Filling them in needs no new mathematics; it is a drop-in substitution because the proof is parameter-agnostic. That is ~2⁶² of headline improvement sitting in a footnote.
3. Diagnose the coupling, not the value. The reason the paper is conservative isn’t laziness — ε, c, and a are coupled by two other rows of the cost table (g4 and the layer recursion). Seeing the coupling immediately tells you the exponent is cubic in a, which tells you where to spend effort.
4. The lever is usually the ugliest number. η_b ≈ 1.5×10⁻¹¹ is buried in §3.6 as a fraction 339/22587335000000, and it is the only thing that actually sets the scale. The deficit is also where the whole n log n barrier was broken in the first place.
5. Know when a primitive is a named hard problem in disguise — and give up when it is. “Cheaper contiguous chunk exchange” is transposition, and transposition is equivalent to multiplication (HvdH, Theorem 1.2). That doesn’t make it hopeless, but it does mean the exponent can’t be improved locally. I chased the other direction (widen the chunks) and it also failed, because the same deficit caps the chunk width from the other side. Sometimes the honest deliverable is a clean negative result.
6. Check the sign of every term before you optimize one. My first draft optimised g2 (wider chunks ⇒ cheaper layout) and forgot that g3 moves the other way. A one-sided optimisation of a two-sided problem is how you manufacture a phantom 2³⁹. Two minutes plotting min(g2(c), g3(c)) kills it.
7. Don’t trust the tempting linear-time reversal trick until you draw the strides. (h,g,d) → (d,g,h) looks like three contiguous block swaps and an O(V) cost. It isn’t, because the “block swaps” are strided axis transposes. Five minutes with index arithmetic saved me from writing a confidently wrong paragraph.
8. A fixed point is a tell. When every way you recurse the same operation gives the same cost, you are looking at the intrinsic cost of the operation, not an artifact of your method. The transpose cost V · (#chunks) · (chunk width)^τ is such a fixed point.

Everything above is analysis of a manuscript, not a verified proof. The κ ≈ 2⁻¹²⁰ upgrade is a constants change to the paper’s own constraint system; it inherits whatever correctness the original proof has, no more. The (b) attack is a model-level argument about the cost table; the three routes I tried failed for reasons I’ve tried to state precisely, and I’d welcome a correction if one of them can be made to work. If anyone wants to push further, the deficit construction in §3 is where the (cubic) leverage is.

Sources: OpenAI — Sharing AI progress in mathematics · the preprint repo · Harvey–van der Hoeven, Integer multiplication in time O(n log n) · Hacker News discussion