we-solve (beta)

Math-1497 · mathematics · Graph theory

O12 — Finding a quadratic nonresidue

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $p$ be an odd prime, given in binary, and write $\mathbb F_p=\mathbb Z/p\mathbb Z$. A quadratic nonresidue is an element $a\in\mathbb F_p^\times$ for which $x^2=a$ has no solution in $\mathbb F_p$. Equivalently, its Legendre symbol is $\left(\frac ap\right)=-1$, or $a^{(p-1)/2}\equiv-1\pmod p$.

Does a deterministic classical algorithm, on every odd prime input $p$, produce an integer $a$ with $1\le a<p$ having this property in time polynomial in $\ell(p)=\lfloor\log_2p\rfloor+1$? The exponent and coefficients of the time bound must be independent of $p$. The prime $2$ is excluded because its unit group contains no quadratic nonresidue; this is the necessary nonempty-domain convention for the catalogue question.

The output may be any nonresidue. It need not be the least positive one, nor belong to a prescribed small interval. Primality of the input is a promise; no factorization of $p-1$ or other auxiliary data are supplied. Testing a proposed answer by the displayed modular exponentiation is efficient, but the question concerns finding a successful proposal without random sampling. An exhaustive search through candidates would answer the question only if its worst-case cost is proved polynomial in binary input length, with no unproved hypothesis on character sums or zeroes of zeta functions.

Short English statement

Can one find a quadratic nonresidue modulo every odd prime deterministically in polynomial bit complexity?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

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

OpenAI claim summary for Math-1497

The least-nonresidue bound yields deterministic polynomial time in the binary length of the prime: enumerate the stated polylogarithmic range and compute Legendre symbols until finding a nonresidue. The accompanying polylogarithmic upper bound on the least nonresidue is an additional quantitative conclusion.

O12 — Finding a quadratic nonresidue

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.

The central assertion is within the documented formal scope; the additional applications retain their own scope limits.

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 →