we-solve (beta)

CS-117 · computer science · mathematics · Algorithms and data structures · Computational algebra and number theory

Finite-field polynomial multiplication and integer-multiplication lower bounds

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
$\mathbb N$, $\mathbb Z$, $\mathbb Q$, $\mathbb R$, and $\mathbb C$ denote the natural numbers, integers, rationals, reals, and complex numbers, respectively. All additional parameters and hypotheses are specified in the question.
Statement recorded in the supplied source.
Can polynomials of degree less than $d$ over $\mathbb F_p$ be multiplied in $O(d\log p\log(d\log p))$ bit operations uniformly in $d$ and $p$, including $p=2$? The companion integer-multiplication question asks whether the cost $M(n)$ of multiplying $n$-bit integers must be $\Omega(n\log n)$. Both the uniform finite-field upper bound and the integer lower bound belong to this problem.

Formulation references: [S1], [S2].

Short English statement

Can polynomials of degree less than $d$ over $\mathbb F_p$ be multiplied in $O(d\log p\log(d\log p))$ bit operations uniformly in $d$ and $p$, including $p=2$? The companion integer-multiplication question asks whether the cost $M(n)$ of multiplying $n$-bit integers must be $\Omega(n\log n)$. Both the uniform finite-field upper bound and the integer lower bound belong to this problem.

Sources

Catalogue entry

Statement licence: CC-BY-SA-4.0 · Source file

Contributions 1

CS-117-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for CS-117

The integer-multiplication algorithm defeats the bundle's proposed $n\log n$ integer lower bound. Uniform finite-field polynomial multiplication is a different operation in the main clause, and that algorithm does not settle it.

Finite-field polynomial multiplication and integer-multiplication lower bounds

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 →