Integer multiplication below n log n

Source and verification

This article explains family 109 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Exact multiplication in a bit model

Let $x,y$ be binary strings of length $n$, allowing leading zeroes. Exact multiplication must output their nonnegative integer product as a padded string of length $2n$. The model in this manuscript is one deterministic Turing machine with a fixed finite alphabet and a fixed finite number of one-dimensional tapes. Moving a tape head and reading or writing a symbol are charged operations.

This model differs from counting unit-cost arithmetic operations on arbitrarily large integers. Even rearranging an array may be expensive because data must travel on the tapes. Write $\lg n=\max \{\lceil {\log }_{2}n\rceil ,1\}$.

Manuscript statement

There is a single machine computing every such product in worst-case time

$$\begin{array}{c}T(n)=O(n(\lg n{)}^{1-\kappa }),\\ \kappa =2^{-182}.\end{array}$$

The bound holds through all input lengths. The constants and asymptotic threshold are extremely large. (OpenAI, 2026)

Since $(\lg n{)}^{-\kappa }\to 0$, this is a strict asymptotic improvement on $n\log n$. Its very small exponent saving does not provide a practical performance claim. The unavoidable output length still gives a linear lower bound in this model.

🏷️ Digits, convolution, and exact recovery

Choose a radix $B=2^b$ and write the inputs as digit polynomials evaluated at $B$:

$$X=\sum _i{a}_i{B}^i,Y=\sum _j{b}_j{B}^j.$$

Their product has uncarried coefficients

$$c_k=\sum _{i+j=k}{a}_i{b}_j.$$

This is a convolution. Once the integer $c_k$ are known, carrying recovers the binary product. For example, in base four,

$$\begin{array}{rl}& (3+2\cdot 4)(1+3\cdot 4)\\ & =3+11\cdot 4+6\cdot 4^2.\end{array}$$

Carrying gives digits $(3,3,0,2)$ from least to most significant, representing $143$. The intermediate coefficient $11$ need not be a radix digit.

Fourier transforms diagonalize convolution, but a tape implementation must charge coefficient precision, roots of unity, permutations, and carries. Approximating every recovered $c_k$ with error strictly below $1/2$ is enough for exact integer rounding; merely obtaining small relative transform error would not be enough without a bound on coefficient scale.

🏷️ Two operations that must both improve

A conventional transform has order $\log n$ layers. Scanning a stored volume of order $n$ bits at every layer already costs order $n\log n$. Saving scalar arithmetic while retaining all those scans would miss the claimed bound.

The source therefore proves two tape procedures. The first interchanges two disjoint contiguous address fields of $u$ bits, on an array with a complete Cartesian-product address set, at cost $O(V{u}^{\tau })$ for some fixed $\tau <1$. Here $V$ is the stored bit volume. Although the final action is a permutation, intermediate states contain XOR combinations of records. It is not a procedure that only routes indivisible data items.

The second applies normalized butterflies

$$H_0(a,b)=((a+b)/2,(a-b)/2)$$

simultaneously along selected coordinate bits in up to $d$ equal-width address chunks, at cost $O(V{d}^{{\lambda }^{\prime }})$ for a fixed ${\lambda }^{\prime }<1$. Records contain fixed-point complex polynomial coefficients. Intermediate arithmetic is exact on dyadic real and imaginary parts; truncation occurs after the completed contractive layer.

The normalized butterfly does not enlarge the maximum norm: both $|(a+b)/2|$ and $|(a-b)/2|$ are at most $\max \{|a|,|b|\}$. This helps organize error budgets, although the complete transform still needs scaling and accumulated-error estimates.

🏷️ Linear frames and the recursive saving

Both procedures use a fixed finite linear network exchanging banks of values and restoring its auxiliary values. A role’s stored array may be expressed in a changing invertible linear frame $D_v$. Along an edge from $u$ to $v$, the implementation applies $D_v{D}_u^{-1}$.

At a pointwise linear gate $G$, all its incident roles use the same frame. Linearity then gives

$$\begin{array}{rl}& G(D_v{g}_1,\dots ,D_v{g}_t)\\ & =D_{v}G(g_1,\dots ,g_t).\end{array}$$

Intermediate frames cancel, leaving the prescribed endpoint transformation. For the bit routine this is an address shear, followed by simple updates completing the swap. For the numerical routine it becomes the simultaneous butterfly after phase and dyadic-scaling operations. The common-frame requirement is what makes cancellation valid at a gate.

The finite network has $W$ roles and a parameter scale $m$. It implements a parameter-$mf$ operation by $s$ smaller parameter-$f$ calls, each on volume $V/W$, with the strict inequality $s<Wm$. The idealized normalized recurrence illustrates the gain:

$$t(mf)\le (s/W)t(f)+O(1).$$

A power bound $t(f)=O(f^{\tau })$ is compatible with this recurrence whenever $\max \{0,{\log }_m(s/W)\}<\tau <1$. The strict inequality leaves room for the constant overhead. The actual proof separately charges padding, tape scans, address corrections, and numerical precision; the recurrence alone does not establish the final multiplication theorem.

The source’s finite network uses auxiliary wires to cancel unwanted intersection coefficients. Arbitrary initial auxiliary values are restored. Thus the construction cannot assume clean zero-filled scratch values without paying for them.

🏷️ Completing the transform pipeline

The manuscript places radix digits on cyclic product coordinates, applies Gaussian resampling to obtain power-of-two transforms, and converts these through a chirp identity to convolution. One coordinate is represented by a polynomial modulo $y^r+1$; multiplication by a power of $y$ is a signed coefficient shift. The address and butterfly routines accelerate the resulting synthetic transforms.

Coordinate order is tracked throughout. Both forward transforms retain the same frequency order for their pointwise product, and the inverse-sign transform consumes that order. Known source permutations cancel across the full convolution calculation. Executing each as a separate full sort would lose the saving the proof is trying to obtain.

Small polynomial products use signed packing and an established $O(n\log n)$ integer multiplier as a subroutine. The new upper bound is obtained by the way these calls are sized and organized, not by assuming the faster multiplier recursively before proving it. The final accounting removes all digit scales and normalizations, bounds coefficient error below $1/2$, and propagates carries.

🏷️ Division and square roots

The manuscript also derives exact integer quotient and remainder for a positive divisor, and the integer square root, within the same time order. Newton approximation uses geometrically increasing precisions, followed by exact checks of the final remainder or square.

The cost summation is compatible with the multiplication bound. For precisions of order $n/2^j$,

$$\begin{array}{rl}& \sum _{j\ge 0}\frac{n}{2^j}(\lg (n/2^j){)}^{1-\kappa }\\ & \le 2n(\lg n{)}^{1-\kappa },\end{array}$$

with the sum stopped once precision reaches a constant. Implementing Newton iteration on fixed tapes and guaranteeing exact correction still require the source’s additional arguments. No running-time experiment or independent verification of the finite networks was performed here.

🏷️ Key steps and proof outlines

Converting matrix rank into a number of tape interchanges

“Faster interchange of address chunks” begins with an elimination procedure tailored to physical tape order. A fixed rational matrix $A$ of rank $a$ is factored as $A=E_1\Pi E_2$, where both $E_i$ are invertible lower triangular and $\Pi$ is a partial permutation matrix with $a$ ones. Choose the topmost nonzero row and its rightmost pivot, clear entries to its left by column operations and below it by row operations, then repeat on the remaining indices. These operations preserve the required triangular direction. (OpenAI, 2026)

Let $H$ and $D$ be two groups of address fields, with $H$ physically earlier. Lower triangular changes can be executed by descending-coordinate updates using still-unchanged earlier fields. The expensive shear $H\leftarrow H+AD$ is reduced to one update for each one of $\Pi$. Each elementary shear uses exactly one interchange:

$$\begin{array}{rl}(h,d)& ⟼(h,d+h)\\ & ⟼(d+h,h)\\ & ⟼(d+h,d).\end{array}$$

The first and last updates target the later field and are streamable. Thus the recursive cost is the rank $a$, rather than the number of nonzero matrix entries. A fixed prime avoiding the finitely many rational denominators lets the same identities operate modulo powers of that prime.

The frame invariant proves the global permutation

Each role of the finite network stores an entire array. For a matrix $M$, let ${\Phi }_M$ permute its addresses by $(H,D)\mapsto (H+MD,D)$. Then ${\Phi }_{M^{\prime }}{\Phi }_M={\Phi }_{M^{\prime }+M}$. Assign one matrix to each network gate and terminal; an edge performs the difference between its endpoint matrices.

At a pointwise gate, the common address permutation commutes with the gate, because the same logical address is transformed on every incident role. Consequently all intermediate frames cancel. If the terminal matrix difference is the identity, each output role contains exactly ${\Phi }_I$ applied to its corresponding input role. Restoring the role order gives the desired shear on every row, including rows temporarily serving as auxiliary wires.

This supplies correctness independently of the cost estimate. The cost uses the additional strict inequality $s<Wm$, where $s$ is the sum of edge ranks, $W$ the number of role streams, and $m$ the chunk subdivision factor. At recursion depth $k$, splitting rows among roles makes each child volume $V/W$, so normalized costs obey

$$F_k\le (s/W)F_{k-1}+C.$$

Choose $0<\tau <1$ with $s/W<m^{\tau }$. The geometric sum is $O(m^{k\tau })$, including the case $s/W\le 1$. Since the chunk width is $m^k$, this is the promised sublinear power of width.

Why a recursive tape schedule does not add another depth factor

At a child call, inactive role streams are parked on a stack tape, the active stream is copied to reusable child tapes, and a short descriptor records the parent program position. On return the inactive streams are restored in reverse stack order. The stack head stays at the current top; restoring a child does not scan through parked ancestors. Each call therefore pays only a constant multiple of its own logical volume, as required by the recurrence. A scheme that rescanned all ancestor data at each return could invalidate the saving.

The numerical routine needs an analogous invariant plus error control. For normalized butterflies, a perturbation of size at most $\eta$ in each input produces output perturbations at most $\eta$. If completed stages introduce truncation errors ${\eta }_j$, contraction bounds the final normalized error by ${\sum }_j{\eta }_j$. The assembly proof then accounts for all subsequent scale factors before requiring absolute error below $1/2$ in each integer convolution coefficient.

Finally, carrying is exact: at coefficient $c_i$ with incoming carry $u_i$, output the remainder of $c_i+u_i$ modulo the radix and set $u_{i+1}=\lfloor (c_i+u_i)/B\rfloor$. Approximation has already ended before this operation. The strict half-unit recovery condition is what allows the transform pipeline to terminate in the exact integer product rather than merely a close real approximation.

See Also

• Matrix multiplication gives arithmetic-operation exponents; the present result charges individual bits and data movement.
• Logarithmic-space derandomization also depends on accounting for numerical precision and the full implementation rather than just an abstract recurrence.

🏷️ Manuscripts and verification scope

• Integer multiplication below n log n — pinned manuscript and companion source.

No family scope page was present at lean/docs/109.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Integer multiplication below n log n.