we-solve (beta)

Math-1500 · mathematics · Graph theory

O15 — Polynomial roots modulo a prime

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

For a prime $p$, let $\mathbb F_p=\mathbb Z/p\mathbb Z$. The input consists of $p$ in binary and a polynomial \[ f(X)=a_0+a_1X+\cdots+a_dX^d\in\mathbb F_p[X], \] encoded by its full coefficient list with representatives $0\le a_i<p$. The input is promised to have a root in $\mathbb F_p$. A valid output is an integer $u\in\{0,\ldots,p-1\}$ for which $f(u)=0$ in that field.

Can this search be performed by a deterministic classical algorithm in time polynomial in the dense input length, equivalently polynomial in $(d+1)\log(2p)$? Both the prime and the polynomial degree are variable parameters. The zero polynomial may be assigned the answer zero; a nonzero constant polynomial is outside the root-existence promise.

The algorithm need only output one root. It is not required to factor the entire polynomial, enumerate all roots, or recognize when no root exists. Repeated roots are allowed, and a root need not be simple. No factorization or splitting field representation is supplied with the coefficients.

Scanning every element of $\mathbb F_p$ is a finite procedure but can be exponential in $\log p$. Likewise, polynomial time in the numerical value of $p$ is not the requested bound. The statement uses dense coefficient input deliberately: a sparse or circuit encoding would define a different complexity problem when the degree is exponentially large relative to the encoding.

Short English statement

Can one root of a polynomial over a prime field be found deterministically in polynomial time whenever a root exists?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

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

OpenAI claim summary for Math-1500

The result supplies the conclusion in this problem with its displayed hypotheses and quantifiers. The broader statements and applications in the manuscript are kept separate from the particular question above. The supporting result is manuscript 1 (family 142; 2026-10-04). The manuscript also gives additional strength beyond the requested conclusion; that excess is not required for this problem's solved-claim label.

O15 — Polynomial roots modulo a prime

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 142; 2026-10-04), the asserted result is that dense polynomials over binary-specified prime fields have uniform deterministic complete factorization in bit time polynomial in degree and $\log p$, using the cited Hecke zero-free input.

Mathematical statement of the claimed result

Manuscript 1.
For any binary-encoded prime $p$ and nonzero densely encoded $f\in\mathbb F_p[x]$ of degree $n$, a uniform deterministic algorithm is claimed to output \[ f=c\prod_i g_i^{e_i} \] with $c$ the leading coefficient, distinct monic irreducible $g_i$ and positive integer multiplicities, in $O(((n+1)\lceil\log_2p\rceil)^{10^{12}})$ bit operations. Constants have an empty factor list. The computation is unconditional and deterministic; it receives neither an integer-factorization service nor a primitive-root oracle.

The separate algebraic reduction sets $L=\lceil\log_2p\rceil$, $B=20+(n+1)(L+1)$. If $p>B^{200000}$ and $n\ge2$, supply for every prime $q\le n$ a prime $\ell_q\notin\{2,3,p,q\}$ with \[ \ell_q\equiv1\pmod{12q},\qquad p^{(\ell_q-1)/q}\not\equiv1\pmod{\ell_q}. \] That reduction has bit cost $O((B+E)^C)$ for absolute $C$, where $E=\max(2,\max_q\ell_q)$, and $E=2$ when no such primes are required. This bound depends on the numerical size of the auxiliary primes; the full theorem additionally constructs sufficiently small primes.

Outline of the argument

For manuscript 1 (family 142; 2026-10-04), primary generators and norm equations reduce splitting to an odd-degree separator. Lifted ramification classes are filtered to keep extension degrees polynomial, and divisors at infinity distinguish roots; the analytic input bounds the auxiliary primes required by the finite algebraic algorithm.

Formal verification

No Lean formalization is listed at this snapshot for manuscript 1 (family 142; 2026-10-04).

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 →