Least quadratic nonresidue modulo a prime

Least quadratic nonresidue 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.

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.

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.

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.

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

• OpenAI, The Quasi-Riemann Hypothesis: A Zero-Free Half-Plane Re (s)>7/8, 2026-09-30; citation key OAI:The-Quasi-Riemann-Hypothesis-September-30-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: cor:nonresidues-square-roots.
• Family 003: Lean scope.
• Comparator DirichletSevenEighths.json.
• Comparator DirichletSevenEighths.lean.
• Comparator HeckeSevenEighths.json.
• Comparator HeckeSevenEighths.lean.
• Comparator QuasiRiemannHypothesis.json.
• Comparator QuasiRiemannHypothesis.lean.
• Comparator SiegelZeros.json.
• Comparator SiegelZeros.lean.
• OpenAI catalogue entry.

Is the least quadratic residue modulo p at most p^(ľ)^( )for any ľ > 0

Definitions and mathematical statement

For an odd prime $p$, a quadratic nonresidue is an integer $a$ not divisible by $p$ for which $x^2\equiv a\pmod p$ has no solution. Let $n_p$ be the least positive such integer. Vinogradov's conjecture in the selected form asserts \[ \forall{\varepsilon}>0\ \exists C_{\varepsilon}>0\ \forall p\text{ odd prime}, \qquad n_p\le C_{\varepsilon} p^{\varepsilon}. \] The constant depends only on ${\varepsilon}$, not on $p$. Equivalently, $n_p=p^{o(1)}$ as primes tend to infinity. The requirement is unconditional, without assuming a Riemann hypothesis. No computable dependence of $C_{\varepsilon}$ on ${\varepsilon}$ or uniform numerical bound is demanded by this notation.

Formulation and concept references: [S1].

Short English statement

Is the least quadratic nonresidue modulo a prime smaller, up to a constant, than every fixed positive power of that prime?

Research attempt

Status: UNRESOLVED. The unconditional bound $n_p=p^{o(1)}$ is not proved. The attempt gives elementary structural facts, derives a square-root character-sum bound, and explains in detail the smooth-number step which improves a Burgess input to the classical exponent $1/(4\sqrt e)$. The latter remains a positive exponent, and the much stronger logarithmic estimate in the cited source is conditional on GRH.

Source audit and exact target.

Let $\chi$ be the quadratic character modulo the odd prime $p$, extended by $\chi(0)=0$, and let $n_p$ be the least positive integer with $\chi(n_p)=-1$. The goal quantifies over every $\varepsilon>0$, with an allowed constant $C_\varepsilon$ depending on $\varepsilon$ but not $p$. A single fixed positive exponent, however small, is insufficient. In [S1], the least-nonresidue estimate of logarithmic-square size is explicitly obtained under the Generalized Riemann Hypothesis. Its Fourier optimization does not remove that hypothesis. I checked this qualification in the primary manuscript on 27 September 2026.

1. Elementary facts and a special square-root bound.

Exactly half the nonzero residues modulo $p$ are squares, since the map $a\mapsto a^2$ on $\mathbb F_p^\times$ is two-to-one. Thus $n_p$ exists and \[ 2\le n_p\le\frac{p+1}{2}. \] The upper bound follows because the integers $1,\ldots,(p+1)/2$ are distinct nonzero residues and cannot all belong to a set of size $(p-1)/2$.

The integer $n_p$ is prime. Otherwise write $n_p=ab$ with $1<a,b<n_p$. Minimality gives $\chi(a)=\chi(b)=1$, contradicting $\chi(n_p)=\chi(a)\chi(b)=-1$. More generally, every positive integer whose prime factors are below $n_p$ and which is not divisible by $p$ is a quadratic residue.

For primes $p\equiv1\pmod4$ there is a short additional argument. Suppose $n=n_p>\sqrt p$, and divide $p=qn+r$ with $0<r<n$. The remainder is nonzero because $n$ is a prime smaller than $p$. Also $1\le q<n$. Thus $\chi(q)=\chi(r)=1$, while $r\equiv-qn\pmod p$ gives \[ 1=\chi(r)=\chi(-1)\chi(q)\chi(n)=-1, \] since $\chi(-1)=1$ in this congruence class. Hence $n_p<\sqrt p$ when $p\equiv1\pmod4$. For $p\equiv3\pmod4$ the same calculation is consistent, rather than contradictory; dropping its sign would be an error.

The supplementary quadratic-reciprocity law gives $\chi(2)=-1$ for $p\equiv3,5\pmod8$, and then $n_p=2$. These elementary classes leave infinitely many primes untreated by a uniform small bound, and do not approach an arbitrary $p^\varepsilon$ estimate.

2. Derive a character-sum bound by finite Fourier analysis.

Put $e_p(t)=\exp(2\pi it/p)$ and \[ \tau=\sum_{a\bmod p}\chi(a)e_p(a). \] For $t\not\equiv0\pmod p$, changing variables $a\mapsto t^{-1}a$ gives \[ \sum_{a\bmod p}\chi(a)e_p(ta)=\chi(t)\tau. \] The same Fourier coefficient is zero for $t=0$, because the nonzero residues split equally into squares and nonsquares. Parseval's identity for the finite Fourier transform therefore gives \[ (p-1)|\tau|^2 =p\sum_{a\bmod p}|\chi(a)|^2=p(p-1), \qquad |\tau|=\sqrt p. \] Fourier inversion expresses the interval sum $S(H)=\sum_{n=1}^{H}\chi(n)$, for $1\le H<p$, as a sum of these coefficients against geometric progressions. For $1\le t\le p-1$, \[ \left|\sum_{n=1}^{H}e_p(tn)\right| \le\frac1{|\sin(\pi t/p)|} \le\frac{p}{2\min(t,p-t)}. \] The final inequality follows from $\sin(\pi x)\ge2x$ on $0\le x\le1/2$. Hence \[ |S(H)|\le\sqrt p\sum_{j=1}^{(p-1)/2}\frac1j \le\sqrt p\,(1+\log p). \] For $H=n_p-1$, every summand is one, so \[ n_p\le1+\sqrt p\,(1+\log p). \] This proof identifies exactly where the square-root scale enters: the nontrivial Fourier coefficients have magnitude $\sqrt p$, and the interval transform has a harmonic tail. It does not provide cancellation between those Fourier terms on much shorter intervals.

3. The Burgess input and the quarter-power barrier it crosses.

Use the classical Burgess character-sum estimate as an external analytic theorem. In a form sufficient here, for a fixed positive integer $r$ and any fixed $\eta>0$, \[ |S(H)|\ll_{r,\eta} H^{1-1/r}p^{(r+1)/(4r^2)+\eta},\qquad 1\le H\le p. \] The harmless $p^\eta$ absorbs logarithmic factors; no proof of Burgess is claimed in this attempt. If $H$ is of order $p^\alpha$ with $\alpha>1/4$, divide by $H$. The power of $p$ becomes \[ -\frac\alpha r+\frac{r+1}{4r^2}+\eta. \] First choose $r$ so that $(r+1)/(4r)<\alpha$, and then choose $\eta$ sufficiently small. This power is negative, giving $S(H)=o(H)$ as $p\to\infty$.

If one used only $S(n_p-1)=n_p-1$, this would locate the least nonresidue at approximately the quarter-power scale. The standard improvement uses multiplicativity to create many additional known residues beyond $n_p$. The next paragraph makes that step explicit and tracks its limitation.

4. Smooth numbers and the factor $\sqrt e$.

Assume for contradiction that every positive integer at most $y$ is a residue. Let $\Psi(x,y)$ count the positive integers at most $x$ whose prime factors are at most $y$. For $x<p$, all these integers have character one. Every other integer in the range has character at least minus one, so \[ S(\lfloor x\rfloor)\ge2\Psi(x,y)-\lfloor x\rfloor. \] Fix $1<u<2$ and set $x=y^u$, with $y\to\infty$. An integer at most $x$ can have at most one prime factor greater than $y$, counted with multiplicity, because two such factors would have product exceeding $y^2>x$. Thus the exact counting identity is \[ \Psi(x,y)=\lfloor x\rfloor- \sum_{y<q\le x\atop q\ \mathrm{prime}}\left\lfloor\frac{x}{q}\right\rfloor. \] The floor error is at most $\pi(x)=o(x)$. The standard reciprocal-prime asymptotic gives \[ \sum_{y<q\le y^u}\frac1q=\log u+o(1), \qquad \frac{\Psi(y^u,y)}{y^u}=1-\log u+o(1). \] The prime-number and reciprocal-prime estimates used here are classical external inputs; the combinatorial counting identity is exact and has been proved above. Consequently, \[ \frac{S(\lfloor y^u\rfloor)}{y^u} \ge1-2\log u+o(1). \] This lower bound stays positively separated from zero when $u<\sqrt e$.

Now let $\theta>1/(4\sqrt e)$. It suffices to consider $\theta<1/4$, since a bound with a smaller exponent implies one with a larger exponent after adjusting constants. Choose a fixed $u$ with \[ 1<u<\sqrt e,\qquad \theta u>1/4. \] Put $y=\lfloor p^\theta\rfloor$ and $x=y^u$. Then $x<p$ for large $p$ and $x=p^{\theta u+o(1)}$. If $n_p>y$, the smooth-number argument gives $S(\lfloor x\rfloor)\ge c_u x$ for some $c_u>0$ and all sufficiently large $p$. Burgess gives $S(\lfloor x\rfloor)=o(x)$, a contradiction. Thus \[ n_p\ll_\theta p^\theta \quad\text{for every }\theta>\frac{1}{4\sqrt e}. \] The finitely many small primes are absorbed into the constant. This reconstructs the classical exponent from a named Burgess input; it is not a new result. The two strict inequalities on $u$ explain why it does not yield exponent zero: one needs enough smooth integers to force a positive character average and an interval long enough for the available cancellation estimate.

5. Least nonresidues cannot be bounded by one absolute integer.

Fix an integer $H\ge2$ and let \[ Q=8\prod_{3\le q\le H\atop q\ \mathrm{prime}}q. \] By Dirichlet's theorem on primes in arithmetic progressions, there are infinitely many primes $p\equiv1\pmod Q$. For all such primes exceeding $H$, the supplementary law makes 2 a residue. For every odd prime $q\le H$, quadratic reciprocity and $p\equiv1\pmod4$ give \[ \left(\frac qp\right)=\left(\frac pq\right) =\left(\frac1q\right)=1. \] Multiplicativity then makes every integer $1\le n\le H$ a residue, so $n_p>H$. This proves that the least nonresidue is unbounded as $p$ ranges over primes, using Dirichlet's theorem as external input.

There is no conflict with $n_p=p^{o(1)}$. The argument chooses a possibly enormous prime after fixing $H$ and gives no lower bound of the form $n_p\ge p^\varepsilon$ for a fixed $\varepsilon>0$. Interchanging these quantifiers would turn a correct elementary construction into a false refutation of the target.

6. Exact diagnostics and the remaining analytic gap.

The offline checks enumerate odd primes through $200000$, find their least nonresidues by Euler's criterion, and verify that each least nonresidue is prime. For the smaller primes through $2000$, direct enumeration of the nonzero square residues provides a second implementation. The special bound $n_p^2<p$ for $p\equiv1\pmod4$ is checked by integers. Character autocorrelation identities are checked for primes through 101, and smooth-number counts are compared with the exact large-prime-factor identity in ranges with $x<y^2$. These are finite arithmetic checks; they do not numerically establish a uniform exponent or GRH.

To complete the conjecture one needs a mechanism forcing a nonresidue below $C_\varepsilon p^\varepsilon$ for every positive $\varepsilon$. The Fourier estimate has a square-root scale. Burgess plus the explicit smooth-number argument reaches a smaller but fixed positive exponent. The source's logarithmic-square estimate depends on GRH. Removing these restrictions is exactly the missing work; no step here supplies the requisite unconditional short-interval cancellation or an alternative argument of comparable strength.

Sources

• S1 E. Carneiro, M. B. Milinovich, E. Quesada-Herrera and A. P. Ramos, "Fourier optimization, the least quadratic non-residue, and the least prime in an arithmetic progression", arXiv:2404.08380 [math.NT], version dated 13 August 2025. https://arxiv.org/pdf/2404.08380. Formulation source.