Integer multiplication below n\log n

1 · The essentials

Multiplying two large whole numbers is the task at the center of this manuscript. The manuscript claims a method that returns the exact answer for every input length. It measures the size of each input by its number of binary digits, called $n$ . Its claimed running-time bound grows more slowly than $n lo g n$ , a proposed limit on how fast multiplication could be done in the computing model considered. The improvement is expressed by an extremely small change in an exponent, so this claim alone does not establish a useful speedup for everyday calculations. The claim concerns one fixed machine with a fixed amount of computing equipment, rather than a different machine for each input size. The main result is not formalized in Lean and has not been formally verified.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine comparing two instructions for multiplying numbers written on strips of paper, while keeping the same small set of work surfaces. The manuscript claims instructions whose work grows more slowly as the numbers get longer; this image does not capture the precise counting of machine steps or establish which instructions would be faster on ordinary-sized examples.

Why it matters

The source identifies the $n lo g n$ optimality conjecture of Schönhage and Strassen as the proposed barrier being challenged. If the manuscript's claim holds, that barrier is not an optimal bound in the ordinary multitape bit model. The significance is a change in the claimed theoretical limit, not a demonstrated practical performance gain.

2 · Going further

The precise task is to multiply two $n$ -bit integers exactly. The manuscript claims a deterministic worst-case running time of $O (n (l g n)^{1 - κ})$ , where $κ = 2^{- 182}$ . The computation takes place on one fixed finite-alphabet Turing machine with a fixed finite number of one-dimensional tapes. Exactness is asserted for every input length, not merely for selected lengths.

Because $κ$ is positive, the claimed bound grows asymptotically more slowly than $n lo g n$ . The repository summary and abstract describe this as a disproof of the Schönhage–Strassen $n lo g n$ optimality conjecture in this model. This conclusion is a manuscript claim, not a formally verified result; the very small exponent change also does not by itself supply a practical speed comparison.

The supplied abstract states the algorithm's claimed performance but gives no construction or main idea of the argument. Consequently, the mechanism behind the improvement cannot be explained from this source alone. Only the main manuscript is supplied, so no relationship to companion manuscripts can be described.

Useful notions

Binary representation and bit length
Logarithms and asymptotic growth
Big-O running-time bounds
Deterministic worst-case computation
Multitape Turing machines

What was known before / what is new

Before

The source names the Schönhage–Strassen conjecture that $n lo g n$ is optimal for integer multiplication in the model under discussion. It does not provide a chronology, earlier algorithmic bounds, or the reasoning that motivated that conjecture.

New

The manuscript claims exact integer multiplication in deterministic worst-case time $O (n (l g n)^{1 - 2^{- 182}})$ . It asserts this on one fixed finite-alphabet machine with a fixed finite number of one-dimensional tapes, with exact answers at every input length. The source presents this as contradicting the named optimality conjecture in the ordinary multitape bit model.

Limits and assumptions

The claim is specifically about multiplying two n-bit integers on the stated fixed multitape Turing machine, under a deterministic worst-case time bound. The supplied text gives no algorithmic details, argument, hidden constants, or practical benchmarks. The main result is not formalized in Lean and has not been formally verified. The source does not identify further open problems or state an ultimate optimal running time for multiplication.

Mini glossary

Bit length: The number of binary digits used to represent an input integer.
Deterministic algorithm: An algorithm whose prescribed steps do not depend on random choices.
Worst-case running time: A time bound that covers every input of a given length.
Big-O bound: An upper bound on growth that allows a fixed multiplicative constant for sufficiently large inputs.
Multitape Turing machine: The computing model used here, with a fixed finite collection of one-dimensional tapes and a finite alphabet of symbols.

Keywords : Integer multiplication · Asymptotic complexity · Multitape Turing machines

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Multiplies two n-bit integers exactly at every input length in deterministic worst-case time $O (n (lo g n)^{1 - κ})$ , with $κ = 2^{- 182}$ , on one fixed finite-alphabet Turing machine with finitely many one-dimensional tapes. This disproves the Schönhage–Strassen $n lo g n$ optimality conjecture in the ordinary multitape bit model.

To be verified: the proof is written in the manuscript, but no software has checked it and no validation by independent mathematicians is established. It may contain errors.

Manuscripts in this family

★

Integer multiplication below n log n

23/09/2026

To be verified

We give a deterministic algorithm that multiplies two n-bit integers in $O (n (l g n)^{1 - κ})$ worst-case time, with $κ = 2^{- 182}$ , on one fixed finite-alphabet Turing machine with a fixed finite number of one-dimensional tapes. The algorithm is exact for every input length and disproves the $n lo g n$ optimality conjecture of Schönhage and Strassen in this model.

PDF GitHub folder