we-solve (beta)

Math-1517 · mathematics · Graph theory

O36 — Integer multiplication in linear bit complexity

Status Partially solved · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $a,b$ be positive integers represented by their ordinary binary expansions, with lengths $m$ and $n$. Set $L=m+n$. Their product is to be output exactly in binary, including every digit; its length is at most $L$. Since $L$ differs from $\log_2(ab)$ by a bounded additive amount, linear time in $L$ is the intended meaning of the source's $O(\log(ab))$ bound.

Does a deterministic classical algorithm multiply every such pair in at most $CL$ elementary bit operations for some absolute constant $C$? Use the standard multitape Turing-machine bit model, or a comparably explicit bit-cost model in which processing arbitrarily long integer words is not a single free operation. The algorithm must be uniform over all input lengths.

The requirement covers unbalanced lengths as well as equal-length inputs; padding reduces these conventions to equivalent linear bounds. It asks for the exact full product, not a residue, a numerical approximation, or only its leading digits. Reading the inputs and writing the answer count as computation.

An algorithm whose cost includes an unbounded factor such as $\log L$ does not by itself establish the stated linear bound, however slowly that factor grows. Conversely, an impossibility result would need to address the stated bit model rather than a more restricted multiplication procedure. The computational model is essential to making the linear-time target unambiguous.

Short English statement

Can exact multiplication of binary integers be performed in time linear in their total number of bits?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1517-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-1517

The factor $(\log n)^{1-2^{-182}}$ still grows with the bit length. The improvement below $n\log n$ therefore does not attain the linear-bit-time bound asked here.

O36 — Integer multiplication in linear bit complexity

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 109; 2026-09-23), the asserted result is that exact multiplication on a fixed multitape finite-alphabet Turing machine takes $O(n(\log n)^{1-2^{-182}})$ worst-case time.

Mathematical statement of the claimed result

Manuscript 1.
For every $n\ge1$ and two binary words of length $n$, the claim supplies one fixed deterministic Turing machine, with fixed finite alphabet and fixed number of one-dimensional tapes, that outputs the exact product of their nonnegative integer values in worst-case time \[ O(n(\lg n)^{1-\kappa}),\qquad\kappa=2^{-182}. \] The convention is $\lg n=\max\{\lceil\log_2n\rceil,1\}$. In the same time scale, fixed machines produce quotient and remainder for a nonzero divisor and the integer square root, with padded binary outputs of length $n$ allowed. These are bit-operation bounds, not unit-cost real arithmetic.

Outline of the argument

For manuscript 1 (family 109; 2026-09-23), two finite linear networks exchange data banks while restoring all auxiliary values. Subspace labels make representation changes cheap on array wires, and the rank saving survives recursive transforms; exact reconstruction and tape-stream accounting give the bit-time improvement.

Formal verification

No Lean formalization is listed at this snapshot for manuscript 1 (family 109; 2026-09-23).

This site has not executed the Lean code. Described statement coverage is not an independent proof check.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources

Go to contribution →