we-solve (beta)

Math-1499 · mathematics · Graph theory

O14 — Square roots modulo a prime

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $p$ be a prime and $a\in\mathbb F_p$, represented by an integer $0\le a<p$. The input is promised to satisfy $a=x^2$ for at least one $x\in\mathbb F_p$. A valid output is any representative $x\in\{0,\ldots,p-1\}$ with \[ x^2\equiv a\pmod p. \] For $a=0$ the answer is zero, and for $p=2$ the answer is immediate. When $p$ is odd and $a\ne0$, either of the two opposite roots is acceptable.

Is there a deterministic classical algorithm that produces such a root on every promised input using a number of bit operations bounded by a fixed polynomial in $\ell(p)+\ell(a+1)$? The prime and the residue vary together; in particular, an algorithm for one fixed modulus does not supply the required uniform result.

No quadratic nonresidue, factorization of $p-1$, or other preprocessing specific to $p$ is included in the input. Any work to obtain useful auxiliary data must be counted. Verifying a candidate root is efficient, but verification is distinct from constructing one. The target is a worst-case unconditional deterministic bound, so a random trial procedure or an algorithm whose analysis assumes an unproved hypothesis does not by itself settle the question. The requested output is one root, rather than a symbolic description of all possible roots.

Short English statement

Can a square root of every promised quadratic residue modulo a prime be constructed deterministically in polynomial time?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

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

OpenAI claim summary for Math-1499

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 results are manuscript 2 (family 142; 2026-10-04), manuscript 1 (family 003; 2026-09-30). The manuscript also gives additional strength beyond the requested conclusion; that excess is not required for this problem's solved-claim label.

O14 — Square 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 003; 2026-09-30), the asserted result is that zeta, Dirichlet $L$-functions, and finite-order Hecke $L$-functions for $\mathbb Q(\sqrt{-3})$ have no zeros with real part greater than $7/8$, with poles excluded; In manuscript 2 (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 every finite-order Hecke character of $F=\mathbb Q(\sqrt{-3})$, every Dirichlet character and the zeta function, the principal claim is \[ \operatorname{Re}s>7/8\quad\Longrightarrow\quad L(s)\ne0, \] where a principal character's pole at $s=1$ is allowed. The weaker displayed $11/12$ theorem follows within this scope. The cited arithmetic consequence gives absolute $A,C>0$ such that every odd prime $p$ has least positive quadratic nonresidue \[ n(p)\le C(\log p)^A. \] Thus $n(p)\ll_{\delta} p^{\delta}$ for each fixed $\delta>0$. Given binary $p$ and $a\in\mathbb F_p$, a deterministic algorithm of time polynomial in $\log p$ is further claimed to return a square root of $a$ or correctly declare it nonexistent. The half-plane assertion leaves zeros between the critical line and $7/8$ untreated.
Manuscript 2.
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 003; 2026-09-30), smoothed character sums are estimated in two ways: directly by large-sieve and recursive moment bounds, and through a Mellin transform involving the reciprocal of an $L$-function. Poisson summation and sextic residue characters align the two expressions so that their savings force continuation of the reciprocal.

For manuscript 2 (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

For manuscript 1 (family 003; 2026-09-30), OpenAI lists Lean statements for this assertion: zeta, Dirichlet $L$-functions, and finite-order Hecke $L$-functions for $\mathbb Q(\sqrt{-3})$ have no zeros with real part greater than $7/8$, with poles excluded.

This coverage does not establish a formal proof of the complete problem as stated here.

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

The linked family Comparator checks are DirichletSevenEighths.lean, HeckeSevenEighths.lean, QuasiRiemannHypothesis.lean, SiegelZeros.lean.

Their named declarations include OAI.DirichletCharacter.LFunction_ne_zero_of_seven_eighths_lt_re, OAI.SevenEighths.HeckeFamily.LFunction_ne_zero_of_seven_eighths_lt_re, OAI.SiegelZeros.WeightedTorusJets.dirichletRealZeroBound_proof, OAI.SiegelZeros.WeightedTorusJets.exists_absolute_real_zero_gap, OAI.riemannZeta_ne_zero_of_seven_eighths_lt_re.

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 →