The least quadratic nonresidue of a prime 3 mod 4 bounds k(p) from below

../

_proof: A term u of the block with all prime factors below q would be a quadratic residue, and so would p-u, which is below q; then -1 would be a residue, which fails for p = 3 (mod 4).

---

This result is recorded by Plasma AI as a specialization of an argument that Granville gives after his Conjecture 4.4.2 (A. Granville, Smooth numbers: computational number theory and beyond, in Algorithmic Number Theory, MSRI Publications 44 (2008), 267--323, section 4.4, printed p. 300), where it is stated for $k$-th power nonresidues and smooth integers in intervals of length $x^\varepsilon$. It places Problem 962, whose upper bounds for k(n) it shows to be at least as hard as bounds for the least quadratic nonresidue next to a classical open problem.

Meaning of the statement

The block $p-q+1,\ldots,p-1$ has length $q-1$, and every term has a prime factor greater than $q-1$; so it is a block of the kind Problem 962 counts, starting at $m=p-q\le p$. Hence an upper bound $k(n)\le An^\theta$, valid for all large $n$, gives $q\le Ap^\theta+1$ for the least quadratic nonresidue $q$ of every large prime $p\equiv3\pmod4$.

The classical unconditional bound for the least quadratic nonresidue is $q\ll_\varepsilon p^{1/(4\sqrt e)+\varepsilon}$, from Burgess's character sum estimate (D. A. Burgess, Mathematika 4 (1957), 106--112) with Vinogradov's device; Granville (2008, section 4.4, with the proof in section 6.4) reports it in this form. So a proof of $k(n)\ll n^\theta$ with any $\theta<1/(4\sqrt e)=0.1516\ldots$ would improve that bound for the primes $p\equiv3\pmod4$. The displayed question of Problem 962, $\log k(n)\le(\log n)^{1/2+o(1)}$, would give $\log q\le(\log p)^{1/2+o(1)}$ for these primes. Under the generalized Riemann hypothesis $q=O((\log p)^2)$ (N. C. Ankeny, Ann. of Math. 55 (1952), 65--72), so the implication conflicts with no standard conjecture; it measures difficulty and is not an obstruction to the truth of either statement. The inequality $k(p)\ge q-1$ alone gives no improvement to the uniform lower bound for $k(n)$ on the problem page: such an improvement would require a sufficiently strong lower bound for $q$, not the upper bound just cited.

Standing and verification

Tier 0, author-recorded, with a complete elementary proof; reading it is the verification procedure. Nothing remains open within the stated scope. The comparison with Burgess's exponent above cites the literature for context and is not part of the statement.

Context

The research sketch on smooth integers in every short interval uses this statement to separate the exponent waypoints, where L253 reaches every exponent above 38/97, from the regime below $1/(4\sqrt e)$, where an upper bound would also strengthen that classical estimate for quadratic nonresidues.