🔢 mathematics

The least quadratic residue and integers represented by quadratic forms

This paper establishes nearly optimal bounds for the least non-trivial reduced quadratic residue modulo $n$ , constructs moduli where this value is unexpectedly large, and applies these findings to determine the rate at which binary quadratic forms with bounded discriminant represent all positive integers up to $N$ .

Original authors: Kannan Soundararajan, João C. C. Vargas

Published 2026-08-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kannan Soundararajan, João C. C. Vargas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Great Number Hunt: Finding the First "Good" Square

Imagine you are a detective trying to crack a secret code. In the world of mathematics, specifically a branch called Number Theory, numbers aren't just for counting; they have personalities and hidden relationships. One of the most famous puzzles involves "quadratic residues." Think of these as numbers that can be "squared" to fit perfectly into a specific pattern. If you take a number, square it (multiply it by itself), and divide it by a secret modulus (a big number $n$ ), the remainder is a quadratic residue. It's like finding a key that fits a specific lock.

The big question mathematicians have been asking for a long time is: How big do you have to look before you find the first key that fits? In other words, what is the smallest number you have to check to find a square that works? This isn't just a game; understanding these "least" numbers helps us understand how numbers are distributed, which is crucial for things like cryptography (the math behind internet security) and understanding the deep structure of the universe of numbers. For decades, mathematicians had good guesses, but they wanted to know if there were any "tricky" locks that required you to search an unexpectedly huge area before finding a single working key.

The Paper's Big Discovery: The "Unlucky" Locks

In this paper, K. Soundararajan and Jo˜ao C. C. Vargas tackle the mystery of the least quadratic residue. They define a special number, let's call it $\ell(n)$ , which is the smallest "square-free" integer (a number that isn't divisible by any perfect square like 4, 9, or 16) that acts as a quadratic residue for a given number $n$ .

The authors prove two main things that might seem contradictory at first, but together they tell a fascinating story about the limits of our knowledge.

1. The Safety Net (The Upper Bound)
First, they prove that you never have to look too far. No matter how complicated your number $n$ is, there is a mathematical "ceiling" on how large the first working key ( $\ell(n)$ ) can be. They show that if $n$ has $k$ different prime factors, the smallest working key is guaranteed to be smaller than a specific formula involving $2^{4k}$ . It's like saying, "Even in the most confusing maze, you will find the exit before you take $2^{4k}$ steps." This part is a straightforward application of the Pigeonhole Principle—a logic trick that says if you have more pigeons than holes, at least one hole must hold two pigeons. Here, the "pigeons" are numbers and the "holes" are patterns of remainders.

2. The Surprise (The Lower Bound)
Here is where it gets exciting. While the authors proved there is a ceiling, they also discovered that for certain specially crafted numbers, the first working key is much, much larger than anyone expected.
Usually, if a pattern appears in about 1 out of every $2^k$ numbers, you'd expect to find a match after checking roughly $2^k$ numbers. But the authors constructed specific numbers $n$ where the first match doesn't appear until you check numbers as large as $4^k$ (minus a small correction).
To put this in perspective: If you were looking for a needle in a haystack, you'd expect to find it after searching a few bales. These authors built a haystack so tricky that you might have to search a mountain of hay before finding the needle. They achieved this by using ideas from error-correcting codes (the math used to fix corrupted data in space missions and CDs), showing that the "bad luck" of these numbers is actually a deliberate, constructed feature.

3. The "What If" Scenario (The Riemann Hypothesis)
The paper also explores what would happen if a famous, unproven guess called the Generalized Riemann Hypothesis (GRH) is true. If GRH is correct, the "tricky" numbers aren't quite as bad as the authors' constructed examples. Under this assumption, the smallest key would be found much sooner, roughly around $e^{C \log n \log \log n}$ . However, since we don't know for sure if GRH is true, the authors' constructed "worst-case" examples remain the best proof we have that these numbers can be surprisingly large.

Why Does This Matter?

The authors didn't just stop at finding these tricky numbers; they used their findings to solve a related puzzle about binary quadratic forms. These are mathematical expressions like $ax^2 + bxy + cy^2$ that can be used to generate other numbers.
The paper asks: "How big does the discriminant (a specific number defining the shape of the form) need to be to ensure that every positive integer up to a certain size $N$ can be represented?"
Using their new bounds on $\ell(n)$ , the authors show:

Unconditionally (without assuming GRH): There are integers up to $N$ that cannot be represented by any quadratic form with a discriminant smaller than a certain massive limit.
Conditionally (assuming GRH): If the Riemann Hypothesis is true, the limit is much smaller, meaning we can represent almost all numbers with much simpler forms.

The Takeaway

This paper is a masterclass in balancing "best-case" and "worst-case" scenarios. It confirms that while there is a theoretical limit to how hard it is to find a quadratic residue, the universe of numbers contains "traps" where the search is significantly longer than simple probability would suggest. The authors didn't just guess; they mathematically constructed these traps and proved they exist. They also showed that if a major mathematical conjecture (GRH) is true, these traps are less treacherous than they appear, but until that conjecture is proven, we must assume the worst.

In the end, this work refines our understanding of how numbers hide and reveal themselves, proving that sometimes, the smallest key to a lock is hidden in a place you'd never think to look without a very clever map.

Technical Summary: The Least Quadratic Residue and Integers Represented by Quadratic Forms

Problem Statement
This paper investigates $\ell(n)$ , defined as the least non-trivial reduced quadratic residue modulo $n$ . Specifically, $\ell(n)$ is the smallest square-free integer $r > 1$ such that $\gcd(r, n) = 1$ and $r \equiv x^2 \pmod n$ for some integer $x$ . The authors seek to establish bounds for $\ell(n)$ in terms of both the magnitude of $n$ and its number of prime factors, $\omega(n)$ . A secondary objective is to apply these results to determine the rate at which families of binary quadratic forms with bounded discriminant represent all positive integers up to a large bound $N$ .

Methodology
The authors employ a combination of combinatorial arguments, analytic number theory, and algebraic structures over finite fields.

Combinatorial and Pigeonhole Principles: The upper bound for $\ell(n)$ is derived using the pigeonhole principle. By considering primes in arithmetic progressions and their Legendre symbol values, the authors demonstrate the existence of a product of two primes that satisfies the necessary quadratic residue conditions.
Algebraic Construction (Lower Bounds): To construct moduli $n$ with unexpectedly large $\ell(n)$ , the authors utilize a correspondence between prime numbers and irreducible polynomials over the field $\mathbb{F}_2$ . They define completely multiplicative functions $f_j: \mathbb{N} \to \{-1, 1\}$ based on the roots of these polynomials in the algebraic closure of $\mathbb{F}_2$ . A key lemma involving power sums of distinct elements in $\mathbb{F}_2$ (related to Newton's identities) is used to prove that if a square-free integer $r$ satisfies $f_j(r) = 1$ for all $j$ , then $r$ must be large.
Analytic Number Theory and Zero-Density Estimates: The construction of $n$ $n$ relies on finding a set of primes such that for every fundamental discriminant $D$ $D$ in a given range, at least one prime in the set is a quadratic non-residue modulo $D$ $D$ .
- Conditional on GRH: The Generalized Riemann Hypothesis (GRH) is used to bound character sums over primes, ensuring the existence of such a set of primes with size roughly $\exp(C \log \Delta \log \log \Delta)$ .
- Unconditional: Without assuming GRH, the authors utilize zero-density estimates for Dirichlet $L$ -functions. They partition the set of discriminants based on the location of their zeros (zero-free regions) and apply a weighted sum argument involving a specific weight function $w(t)$ to establish the existence of the required primes.
Application to Quadratic Forms: The results are applied to the representation of integers by binary quadratic forms $f(x,y) = ax^2 + bxy + cy^2$ . The authors utilize the fact that an integer $n$ is represented by a form of discriminant $D$ if and only if $D$ is a square modulo $4n$ (for proper representations).

Key Contributions and Results

Bounds for $\ell(n)$ in terms of prime factors:
- Upper Bound: If $k$ is the number of odd prime factors of $n$ , $\ell(n) \le C k 2^{4k}$ for an absolute constant $C$ .
- Lower Bound: For each $k \ge 2$ , there exist infinitely many odd integers $n$ with exactly $k$ distinct prime factors such that $\ell(n) \ge 4^{k - C k / \log k}$ . This result is surprising given that the density of quadratic residues is $\asymp 2^{-k}$ , suggesting one might expect $\ell(n)$ to be closer to $2^k$ .
Bounds for $\ell(n)$ in terms of magnitude $n$ :
- The authors construct an odd square-free integer $n \le N(\Delta)$ such that for every fundamental discriminant $D$ with $1 < |D| \le \Delta$ , there is a prime factor $p$ of $n$ with $\left(\frac{D}{p}\right) = -1$ .
- Unconditional: $N(\Delta)$ can be chosen as $\exp(C \log \Delta (\log \log \Delta)^2)$ .
- Conditional on GRH: $N(\Delta)$ can be chosen as $\exp(C \log \Delta \log \log \Delta)$ for any $C > 2/\log 2$ .
- Consequently, $\ell(n)$ can be as large as $\exp\left(c \frac{\log n}{(\log \log n)^2}\right)$ unconditionally, and $\exp\left(\left(\frac{\log 2}{2} + o(1)\right) \frac{\log n}{\log \log n}\right)$ under GRH.
Representations by Binary Quadratic Forms:
- Indefinite Forms: Every positive integer up to $N$ can be represented by some primitive, non-degenerate, indefinite binary quadratic form with discriminant $1 < D_f \le \Delta$ , where $\Delta = \exp\left((\log 4 + o(1)) \frac{\log N}{\log \log N}\right)$ .
- Positive Definite Forms (Conditional): Assuming GRH, every positive integer up to $N$ can be represented by a primitive, positive definite binary quadratic form with discriminant $|D_f| \le \Delta$ (with the same $\Delta$ as above).
- Limitations: There exists a positive integer $n \le N$ that cannot be represented by any primitive non-degenerate binary quadratic form with $|D_f| \le \Delta$ if $\Delta = \exp(c \log N / (\log \log N)^2)$ . Under GRH, this threshold improves to $\exp((\frac{\log 2}{2} - \epsilon) \frac{\log N}{\log \log N})$ .

Significance and Claims
The paper claims to establish "nearly optimal bounds" for the least quadratic residue, both in terms of the modulus size and its number of prime factors. The construction of moduli with large $\ell(n)$ is motivated by ideas from error-correcting codes and represents a significant advancement over probabilistic expectations, showing that $\ell(n)$ can be significantly larger than the inverse of the density of quadratic residues.

The authors position their work as a variant of the classical problem of finding the least prime $p$ such that $\chi(p) = -1$ for a primitive quadratic character $\chi$ . While the classical problem is well-understood under GRH, this paper extends the scope to composite moduli and provides unconditional results that are only slightly weaker than the conditional ones.

Furthermore, the paper provides precise quantitative progress on the problem of covering all integers up to $N$ using binary quadratic forms with bounded discriminant. While previous work (Green and Soundararajan) addressed covering "almost all" integers, this paper addresses the more difficult problem of covering "all" integers, establishing explicit thresholds for the discriminant required to guarantee representation.

Finally, the authors note a connection to the work of Hanson, Vaughan, and Zhang regarding the least $N$ required for all sign sequences of length $k$ to appear as Legendre symbol vectors, suggesting a broader context for the combinatorial methods employed.

The Great Number Hunt: Finding the First "Good" Square

The Paper's Big Discovery: The "Unlucky" Locks

Why Does This Matter?

The Takeaway

More like this