The least quadratic residue and integers represented by quadratic forms

Jo\~ao C. C. Vargas; Kannan Soundararajan

REVIEW 1 major objections 4 minor 12 references

The least quadratic residue and integers represented by quadratic forms

T0 review · 1 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Given n with k odd prime factors, the least square-free quadratic residue can be as large as 4^{k-o(k)} yet never exceeds C k² 4^k, and the same bounds determine which binary quadratic forms of small discriminant represent every integer up

desk verdict A genuinely new finite-field construction drives the lower bound for the least quadratic residue, and the transfer to binary quadratic forms is real progress; the unconditional part rests on an imported zero-density estimate that a referee should check precisely. read the letter →

arxiv 2607.29566 v1 pith:NUKT4WFE submitted 2026-07-31 math.NT

Kannan Soundararajan , João C. C. Vargas This is my paper · ORCID

classification math.NT MSC 11A1511E1611M2611N05

keywords leastquadraticresidueresiduesmoduloncompletelymultiplicativefunctionsfinitefieldF2[x]binaryformsfundamentaldiscriminantszerodensityestimatesLegendresymbol

topics The Riemann Hypothesis The Twin Prime Conjecture

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Let ℓ(n) be the smallest square-free integer r>1 with r≡x² mod n for some x and gcd(r,n)=1. The paper proves that this least quadratic residue is governed by powers of 4: for every n with k odd prime factors, ℓ(n) ≤ C k² 4^k, and for every k≥2 there are infinitely many n for which ℓ(n) ≥ 4^{k−Ck/log k}. Since the number of distinct prime factors of n is at most about log n/log log n, the upper bound becomes ℓ(n) ≤ exp((log 4+O(1/log log n)) log n/log log n), while the constructions give matching lower bounds in terms of n, with a stronger exponent conditional on the Generalized Riemann Hypothesis. Because a modulus n can be arranged so that many small fundamental discriminants are non-residues modulo its prime factors, these bounds translate directly into statements about binary quadratic forms: with discriminant around exp((log 4+o(1)) log N/log log N), every integer up to N is represented by some indefinite form, and there are integers up to N that resist all forms with even slightly smaller discriminants. The interest is that the answer is exponential in k—rather than the 2^k that the density of quadratic residues would naively suggest—and is now known up to the secondary terms.

What carries the argument

The lower bound in Theorem 1.1 is carried by a finite-field encoding: primes are assigned irreducible polynomials over F₂[x], and each polynomial's roots in the algebraic closure define a completely multiplicative function f_j(p)=±1. Lemma 2.2, proved through Newton's identity in characteristic 2, says that if z_1,...,z_n are distinct nonzero elements and all odd power sums z_1^{2j−1}+...+z_n^{2j−1} vanish for j=1..k, then n>2^k; applying this to the roots contributed by the prime factors of r forces 2^k < (log r)/log 2 + O(ω(r)), which is exactly why the least r with all f_j(r)=1 must sit near 4^k. For Theorem 1.2 the machinery is instead analytic: fundamental discriminants are partitioned

What would settle it

Fix Δ=10^6, implement Section 3's shell partition, and count how many fundamental discriminants with 1<|D|≤Δ lie in each shell; if any shell contains more than C exp(C e_j) discriminants with the paper's constants, the unconditional N(Δ) bound does not follow. Equivalently, for the square-free n the construction produces, check every fundamental D with |D|≤Δ: a single D with χ_D(p)=1 for all p|n would be a direct counterexample to that instance of Theorem 1.2.

Watch

Extended reading notes

Core claim

The core claim is that the least quadratic residue modulo n has exponential order 4^k in the number k of odd prime factors, and that this phenomenon is stable enough to transfer to binary quadratic forms. Theorem 1.1 supplies the two sides: a pigeonhole argument shows ℓ(n) ≤ C k² 4^k, while a finite-field construction, translating primes into irreducible polynomials over F₂[x], produces moduli n for which any r with ℓ(n)=r must carry more than 2^k distinct algebraic roots, forcing log r ≥ k log 4 − O(k/log k). Theorem 1.2 sharpens this into a discriminant statement: for any Δ one can build an odd square-free n with log n ≤ C log Δ (log log Δ)² (and under GRH log n ≤ C log Δ log log Δ) such t

Load-bearing premise

The unconditional half of Theorem 1.2 relies on the imported bound that each zero-free shell of fundamental discriminants has size at most C exp(C e_j); if that exponential density estimate were ever exceeded, the constructed small modulus n could have a larger size than claimed.

Editorial extensions

If this is right

Every n satisfies ℓ(n) ≤ exp((log 4+O(1/log log n)) log n/log log n), so the growth is exponential in log n/log log n with constant log 4.
There exist n with ℓ(n) ≥ exp(c log n/(log log n)²), so the least quadratic residue can be far larger than any fixed power of log n.
Under GRH, some n have ℓ(n) ≥ exp((log 2/2+o(1)) log n/log log n), narrowing the gap between upper and lower exponential constants.
Every positive integer up to N is representable by a primitive non-degenerate indefinite binary quadratic form of discriminant Δ = exp((log 4+o(1)) log N/log log N); with GRH the same holds for positive-definite forms.
There are integers n≤N that no primitive non-degenerate binary quadratic form with |D| ≤ exp(c log N/(log log N)²) can represent; under GRH this obstruction persists for |D| ≤ exp((log 2/2−ε) log N/log log N).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the finite-field lower bound is genuinely optimal, the eventual answer for general n is ℓ(n) = exp((log 4+o(1)) log n/log log n), meaning the gap to the GRH lower bound reflects the difficulty of the least-nonresidue problem for all characters rather than the true order of ℓ(n).
The construction's resemblance to error-correcting codes suggests a search for explicit moduli n with extremely large ℓ(n) by taking products of primes whose associated F₂ polynomials form a code with large minimum distance; the L(k) values computed in Section 5 are the first few data points.
The same 'kill every small discriminant' strategy could be applied to other families of characters (e.g., cubic or higher-order residues) to produce moduli where the least character value is large, though the binary-quadratic setting exploits that ℓ(n) is itself a fundamental discriminant.
A natural next test is computational: for small Δ, the shell construction can be implemented directly, and the predicted N(Δ) compared with the minimal n found by search, giving a finite check of whether the exponential shell bounds are numerically believable.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Plain verdict: this is a results paper. The finite-field construction in Proposition 2.1 — using irreducible polynomials over F2[x] and Hayes-type characters to make ℓ(n) nearly as large as 4^k — is the genuinely new piece. The pigeonhole upper bound in Theorem 1.1 is elementary and correctly handled. The transfer to binary quadratic forms in Theorem 1.3 is a real application, not decoration.

The GRH-conditional half of Theorem 1.2 is a clean standard argument: character sums, a contradiction, and a zero-free-region lemma. The unconditional half is sound if you accept estimate (9). I agree with the stress-test note: (9) is the one place where a deep external theorem is doing real work. It is standard and properly cited, but the strength of Theorem 1.2 is exactly the strength of Gallagher's log-free bound, with no extra log factor. A referee should ask the authors to state the precise version and to show it applies to fundamental discriminants in shells of exactly that form. That is a clarification, not a flaw.

Soft spots, in increasing order: - Section 3's notation is mangled in the arXiv rendering (β_j, e_j, x_j), making the shell partition hard to verify without reconstruction. - Section 5 reports exact values L(4)=570 and L(5)=2679 with no proof or code. These are optional addenda and should be labelled as such or supported. - The gap between the unconditional and GRH-conditional exponents is large; the paper does not oversell it, but a reader should be warned.

The citation pattern is fine. [7] and [8] are used for motivation and comparison; the main theorems do not depend on the authors' earlier work. There is no circularity.

Who it is for: analytic number theorists working on least residues, characters, and binary quadratic forms. It deserves a serious referee. I would send it out.

Referee Report

1 major / 4 minor

Summary. The paper studies ℓ(n), the least squarefree non-trivial quadratic residue modulo n. Theorem 1.1 gives the upper bound ℓ(n) ≤ C k^2 4^k, where k is the number of odd prime factors of n, and constructs infinitely many n with exactly k odd prime factors for which ℓ(n) ≥ 4^{k − Ck/log k}. Theorem 1.2 constructs, for a given Δ, an odd squarefree modulus n of size at most exp(C logΔ (loglogΔ)^2) such that every fundamental discriminant D with 1 < |D| ≤ Δ has χ_D(p) = −1 for some prime p | n; under GRH the bound improves to exp(C logΔ loglogΔ) for every C > 2/log2. This yields lower bounds for ℓ(n) in terms of n. Theorem 1.3 converts these results into statements about binary quadratic forms: positive results on the discriminant needed to represent every integer up to N, and a negative result for discriminants up to roughly Δ = exp(c log N/(loglog N)^2), with a GRH exponent improvement. The proofs combine a pigeonhole argument, a finite-field construction using irreducible polynomials over F2, a GRH/zero-density shell argument, and classical facts on binary quadratic forms.

Significance. If correct, this is a substantial advance. The lower bound in Theorem 1.1 is striking: although the density of quadratic residues is about 2^{−k}, the authors construct moduli for which ℓ(n) is about 4^{k−o(k)}. The finite-field Lemma 2.2 gives an elegant and nearly sharp mechanism for this. The unconditional Theorem 1.2 is exactly as strong as the imported log-free zero-density estimate (9); with that standard input, the shell argument is internally coherent. The applications in Theorem 1.3 are nontrivial and appear to be correct, with the right constants in the GRH-conditional part. The proofs are self-contained apart from the cited zero-density estimate and standard analytic lemmas; I found no load-bearing mathematical error beyond the missing definition noted below.

major comments (1)

[§3, unconditional part] The shell parameter e_j appears immediately after 'Put J = ...' in the definition of β_j, and is then used in the density estimate (9), in x_j = Δ^{j/e_{j−1}}, and in the bound (10), but it is never defined in the manuscript as written. From J = ceil(log((1/2)logΔ)) and the factor e·j in (10), I infer that the intended definition is e_j = e^j. With that definition the inequalities in Lemma 3.2 and the final bound log n ≤ C logΔ (loglogΔ)^2 check out; for example, the j = 1 shell works because log 10 < e. However, as printed the proof of the unconditional part of Theorem 1.2 cannot be checked. Please define e_j explicitly and clarify that the 'e·j' in (10) is Euler's number times j.

minor comments (4)

[§2, Proposition 2.1] The illustrative sentence says that 5, 7, and 11 are associated to 'the three irreducible polynomials of degree 3'. Over F2 there are only two irreducible cubics; the next available irreducibles are the three irreducible quartics. The proof is unaffected, but the example should be corrected.
[§3, Lemma 3.2] The passage from (7) to (8) is compressed: (7) is the Mellin integral, which equals log x times the weighted prime sum, and the final bound for Σ_p (log p/p)χ_D(p)w(...) requires dividing the bound for the zero sum by log x. The final estimate is correct, but this division should be made explicit for readability.
[§3, after Theorem 1.2] When deriving the lower bound for ℓ(n), the authors note that either ℓ(n) or 4ℓ(n) is fundamental. If ℓ(n) ≡ 3 mod 4, the fundamental discriminant is 4ℓ(n), and the construction only directly rules out 4ℓ(n) ≤ Δ. This changes Δ by at most a factor of 4 and is absorbed into constants, but the text should state this.
[§5, Further questions] The claims L(4) = 570 and L(5) = 2679 are stated without proof or a description of the verification method. Since these values are not needed for the main results, please either provide a short certificate or explicitly label them as computational observations.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the main results are derived from the prime number theorem, finite-field combinatorics, GRH, and an external zero-density estimate; the self-citations are motivational, not load-bearing.

full rationale

The derivation chain is internally coherent. Theorem 1.1's upper bound follows from the pigeonhole principle plus the prime number theorem, and its lower bound from Proposition 2.1, which constructs completely multiplicative functions using irreducible polynomials over F_2[x], together with Lemma 2.2 and Dirichlet's theorem. No fitted quantity is renamed as a prediction. Theorem 1.2 conditional on GRH explicitly assumes GRH and counts discriminants via standard character-sum bounds; the unconditional version partitions fundamental discriminants into zero-free shells and uses Lemma 3.1 and Lemma 3.2. The only imported deep input is Eq. (9), the log-free zero-density estimate |D_j| ≤ C1 exp(C2 e_j), cited to Gallagher [4]. That is an external theorem, not a result proved in this paper nor a self-citation, so using it as a premise is not circular. Theorem 1.3 follows from Theorems 1.1-1.2 and classical facts on binary quadratic forms cited to Buell. The self-citations [6,7] are used for motivation and context; the present proofs do not assume the conclusions of those papers to establish the main theorems. The numerical δ2 example in Section 5 is an optimization illustration, not a fitted parameter disguised as a prediction. Overall, the paper's central claims have independent mathematical content; the only concern is the strength of the external Gallagher estimate, which is a correctness/rigor consideration, not circularity.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

No new physical or mathematical entities are postulated. The completely multiplicative functions f_j are constructed objects, not free entities. The only fitted numbers are the Section 5 optimization parameters, which do not affect the main theorems. The substantial theorems rest on standard background results (PNT, Dirichlet, zero-density estimates, and GRH where explicitly flagged).

free parameters (2)

α = 2.521469...
Chosen by numerical optimization in Section 5 to construct the upper-bound example for δ2; not used in any main theorem.
β = 2.796705...
Same numerical optimization as α, defining the threshold x^{1/(αβ)} in the δ2 example; not used in any main theorem.

assumptions (6)

standard math Prime number theorem
Used for the upper bound in Theorem 1.1 and for deg Q_p = log p/log 2 + O(1) in Proposition 2.1.
standard math Dirichlet's theorem on primes in arithmetic progressions
Used in Section 2 to realize the constructed functions f_j as Legendre symbols (p/q_j) at arbitrarily large primes q_j.
domain assumption Log-free zero-density estimate |D_j| ≤ C1 exp(C2 e_j) from Gallagher [4]
Equation (9) in Section 3; this external estimate is load-bearing for the unconditional construction in Theorem 1.2.
domain assumption Generalized Riemann Hypothesis (GRH)
Explicitly assumed for the conditional parts of Theorem 1.2 and for Theorems 1.3(2) and the GRH version of Theorem 1.3(3).
domain assumption Classical theory of binary quadratic forms (Buell [3])
Used in Section 4: forms of discriminant Dt^2 descend to forms of discriminant D, and n is properly represented by a form of discriminant D iff D is a square mod 4n.
standard math Mellin inversion and Hadamard factorization for Dirichlet L-functions
Used in Lemma 3.2 and in the GRH character-sum estimate, standard tools in analytic number theory.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The least quadratic residue and integers represented by quadratic forms." pith.science (2026). https://pith.science/paper/NUKT4WFE

@misc{pith2026260729566,
  author       = {Pith},
  title        = {Pith review of: The least quadratic residue and integers represented by quadratic forms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NUKT4WFE}},
  note         = {Machine review of arXiv:2607.29566}
}

abstract

Let $\ell(n)$ denote the least non-trivial reduced quadratic residue modulo $n$; that is, $\ell(n)$ denotes the smallest square-free integer $r>1$ with $(r,n)=1$ and $r\equiv x^2 \bmod {n}$. We establish nearly optimal bounds for $\ell(n)$, both in terms of the magnitude of $n$ and of its number of prime factors $\omega(n)$. In particular, we construct moduli $n$ for which $\ell(n)$ is unexpectedly large. As an application of our results, we prove bounds for the rate at which binary quadratic forms with bounded discriminant represent all positive integers up to $N$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references

[7]

Ben Green and Kannan Soundararajan,Covering integers byx 2 +dy 2, J. Inst. Math. Jussieu24(2025), no. 3, 847–889. MR4891407

2025
[8]

Vaughan, and Ruixiang Zhang,The least number with prescribed Legendre symbols and representation by binary quadratic forms of small discriminant, J

Brandon Hanson, Robert C. Vaughan, and Ruixiang Zhang,The least number with prescribed Legendre symbols and representation by binary quadratic forms of small discriminant, J. Number Theory179 (2017), 3–16. MR3657151

2017
[1]

N. C. Ankeny,The least quadratic non residue, Ann. of Math. (2)55(1952), 65–72. MR45159

1952
[2]

R. C. Bose and D. K. Ray-Chaudhuri,On a class of error correcting binary group codes, Information and Control3(1960), 68–79. MR112768 12 K. SOUNDARARAJAN AND JO ˜AO C. C. V ARGAS

1960
[3]

Buell,Binary quadratic forms, Springer-Verlag, New York, 1989

Duncan A. Buell,Binary quadratic forms, Springer-Verlag, New York, 1989. Classical theory and modern computations. MR1012948

1989
[4]

P. X. Gallagher,A large sieve density estimate nearσ= 1, Invent. Math.11(1970), 329–339. MR279049

1970
[5]

Ann.376(2020), no

Ofir Gorodetsky and Will Sawin,Correlation of arithmetic functions overFq[T], Math. Ann.376(2020), no. 3-4, 1059–1106. MR4081110

2020
[6]

Soundararajan,The spectrum of multiplicative functions, Ann

Andrew Granville and K. Soundararajan,The spectrum of multiplicative functions, Ann. of Math. (2) 153(2001), no. 2, 407–470. MR1829755

2001

Show all 12 references

[9]

Hayes,The distribution of irreducibles inGF[q, x], Trans

David R. Hayes,The distribution of irreducibles inGF[q, x], Trans. Amer. Math. Soc.117(1965), 101–

1965
[10]

Hocquenghem,Codes correcteurs d’erreurs, Chiffres2(1959), 147–156

A. Hocquenghem,Codes correcteurs d’erreurs, Chiffres2(1959), 147–156. MR109766

1959
[11]

Montgomery,Ten lectures on the interface between analytic number theory and harmonic anal- ysis, CBMS Regional Conference Series in Mathematics, vol

Hugh L. Montgomery,Ten lectures on the interface between analytic number theory and harmonic anal- ysis, CBMS Regional Conference Series in Mathematics, vol. 84, Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI...

1994
[12]

Montgomery and Robert C

Hugh L. Montgomery and Robert C. Vaughan,Multiplicative number theory. I. Classical theory, Cam- bridge Studies in Advanced Mathematics, vol. 97, Cambridge University Press, Cambridge, 2007. MR2378655 Department of Mathematics, Stanford University, Stanford, CA 94305, USA Depa...

2007

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [7]

Ben Green and Kannan Soundararajan,Covering integers byx 2 +dy 2, J. Inst. Math. Jussieu24(2025), no. 3, 847–889. MR4891407

2025

[2] [8]

Vaughan, and Ruixiang Zhang,The least number with prescribed Legendre symbols and representation by binary quadratic forms of small discriminant, J

Brandon Hanson, Robert C. Vaughan, and Ruixiang Zhang,The least number with prescribed Legendre symbols and representation by binary quadratic forms of small discriminant, J. Number Theory179 (2017), 3–16. MR3657151

2017

[3] [1]

N. C. Ankeny,The least quadratic non residue, Ann. of Math. (2)55(1952), 65–72. MR45159

1952

[4] [2]

R. C. Bose and D. K. Ray-Chaudhuri,On a class of error correcting binary group codes, Information and Control3(1960), 68–79. MR112768 12 K. SOUNDARARAJAN AND JO ˜AO C. C. V ARGAS

1960

[5] [3]

Buell,Binary quadratic forms, Springer-Verlag, New York, 1989

Duncan A. Buell,Binary quadratic forms, Springer-Verlag, New York, 1989. Classical theory and modern computations. MR1012948

1989

[6] [4]

P. X. Gallagher,A large sieve density estimate nearσ= 1, Invent. Math.11(1970), 329–339. MR279049

1970

[7] [5]

Ann.376(2020), no

Ofir Gorodetsky and Will Sawin,Correlation of arithmetic functions overFq[T], Math. Ann.376(2020), no. 3-4, 1059–1106. MR4081110

2020

[8] [6]

Soundararajan,The spectrum of multiplicative functions, Ann

Andrew Granville and K. Soundararajan,The spectrum of multiplicative functions, Ann. of Math. (2) 153(2001), no. 2, 407–470. MR1829755

2001