# Distribution of moduli of quadratic residues

Let $D$ be a fixed positive squarefree integer. For a positive integer $x$, define

$S(D,x) = \{ q < x : D \text{is a quadratic residue} \pmod q \}$.

Here $q$ can be any integer, not necessarily a prime. Are elements of $S(D,x)$ evenly distributed? In other words, let $0 < a < b < 1$ be constants and consider an interval $I = [ax,bx]$. Ideally I would like to see some result that says that the number of elements of $S(D,x)$ in $I$ is proportional to the length of $I$ on the average as $x$ goes to infinity (is this true?).

I am aware of classical 1917-1918 results of Vinogradov and Polya (and some later developments) about distribution of quadratic residues, which in particular imply that quadratic residues modulo a fixed prime $p$ are evenly distributed in the interval $[0,p]$ in the same sense as I described above. What I need, however, is a result on the distribution of moduli with respect to which a fixed integer is a quadratic residue, and I cannot find anything like this in the literature.

In other words, I am wondering how the divisors of $x^2-D$ are distributed on the average as $x$ goes to infinity. It is a well-known fact that for an arbitrary integer $y$, there are unproportionally many (on the average) small and large divisors of $y$ as $y$ goes to infinity, i.e., divisors are not uniformly distributed. But what if we take $y$ in the special form $x^2-D$?

Any thoughts on the subject are much appreciated!

• If you were to restrict to $q$ prime then for $D\gt 1$, quadratic reciprocity, the Chinese remainder theorem, and the equidistribution of primes in residue classes (Vallée-Poussin) give you equidistribution. For example, suppose $D=6$. $2$ is a quadratic residue mod $q \gt 2$ iff $q = \pm 1 \mod 8$, and $3$ is a quadratic residue iff $q = \pm 1 \mod 12$, so $6$ is a quadratic residue when $q = 1, 5, 19, 23 \mod 24$, and it's a quadratic nonresidue when $q = 7,11,13,17 \mod 24$. – Douglas Zare Jul 12 '13 at 8:13
• Here’s a guess: $D$ is a square modulo a random prime (or prime power) with probability 1/2, hence it is a square modulo a random number with $k$ prime factors with probability $2^{-k}$. Since a random integer below $n$ has $k\approx\log\log n$ prime factors on average, which is in particular nonconstant, I’d expect that $\lim_{x\to\infty}\frac{|S(D,x)\cap[ax,bx]|}{|[ax,bx]|}=0$. – Emil Jeřábek Jul 12 '13 at 11:27
• @EmilJeřábek Your initial argument suggests that $|S(D,x)|$ is asymptotic to $x/(\log x)^{\log 2}$, no? If that holds with a reasonable error term (which is not clear at all) then $|S(D,bx)| - |S(D,ax)|$ will be asymptotic to $(a-b)|S(D,x)|$. – Felipe Voloch Jul 12 '13 at 11:43
• @FelipeVoloch: The OP asked for it to be proportional to the length of $I$, not to $|S(D,x)|$. Anyway, I’d be very cautious with such calculations. For one thing, that the average order of $k$ is $\log\log x$ does not mean that the average order of $2^{-k}$ is $(\log x)^{-\log 2}$. In fact, for constant $k$, there are $\sim\frac{x(\log\log)^{k-1}}{(k-1)!\log x}$ numbers in $[1,x]$ with $k$ prime factors, which would rather suggest that $|S(D,x)|$ is of order $x/\sqrt{\log x}$. It’s still unclear to me whether this is the right exponent, and whether $|S(D,x)|\sqrt{\log x}/x$ actually converges. – Emil Jeřábek Jul 12 '13 at 14:13

For $D=-1$, Landau proved that $$\# S(-1, x) \sim K \frac{x}{\sqrt{\log x}}$$ where $K = \frac{1}{\sqrt{2}} \prod_{p \equiv 3 \bmod 4} \frac{1}{\sqrt{1-p^{-2}}}$. This shows that, for fixed $0<a<b$, $$\# S(-1,x) \cap [ax,bx] \sim K \left( \frac{bx}{\sqrt{\log(bx)}} - \frac{ax}{\sqrt{\log(ax)}} \right)$$ and $$K \left( \frac{bx}{\sqrt{\log(bx)}} - \frac{ax}{\sqrt{\log(ax)}} \right) = K \left( \frac{bx}{\sqrt{\log x + \log b}} - \frac{ax}{\sqrt{\log x + \log a}} \right)$$ $$= K \left( \frac{bx}{\sqrt{\log x}} +O\left( \frac{x}{(\log x)^{3/2}} \right) - \frac{ax}{\sqrt{\log x}} - O\left( \frac{x}{(\log x)^{3/2}} \right) \right) \sim K \frac{(b-a)x}{\sqrt{\log x}}$$
So they are equidistributed in that $\frac{\#(S(-1,x) \cap [ax,bx])}{\#S(-1,x)}$ approaches $b-a$ but, if you ask for the denominator to be $x$, then the limit just goes to zero.
I believe the same should be true for any nonsquare $D$. Let $$Z_D(s) = \prod_{\left( \frac{D}{p} \right) = 1} \frac{1}{1-p^{-s}} = \sum_{D \ \mbox{is a square modulo}\ n} \frac{1}{n^s}.$$ The proof of Landau's theorem in Leveque's "Topics in number theory" comes down to analyzing the behavior of $Z_D(s)$ on $Re(s)=1$. The key facts are that $Z_{-1}(s) = C (s-1)^{1/2} + \cdots$ and $Z_{-1}(s)$ is otherwise bounded on $Re(s)=1$. These results hold for any nonsquare $D$. Let $\zeta_D(s)$ be the zeta function of $\mathbb{Q}(\sqrt{D})$. Then $$\frac{Z_D(s)^2}{\zeta_D(s)} =\left( \mbox{factors for primes dividing}\ 2D \right) \times \prod_{\left( \frac{D}{p} \right) = -1} \left( 1- \frac{1}{p^{2s}} \right) .$$ The right hand side is clearly convergent to the right of $Re(s)=1/2$, and $\zeta_D(s)$ is well known to have a simple pole at $s=1$ and no other poles on the line $Re(s)=1$.
• David, great -- thank you very much! In fact, Gang Yu pointed out to me that this result can be obtained by an argument entirely analogous to the proof of the main theorem in: James, R. D.; The Distribution of Integers Represented by Quadratic Forms. Amer. J. Math. 60 (1938), no. 3, 737–744 jstor.org/discover/10.2307/… Here your function $Z_D(s)$ is the first product in the formula for $f(s)$ in Lemma 3 of James' paper. – Lenny Fukshansky Jul 15 '13 at 21:35