The question is basically the title itself. It is easy to prove using quadratic reciprocity that non squares are non residues for some prime $p$. I would like to make use of this fact in a proof of quadratic reciprocity though and would like a proof that avoids quadratic reciprocity if possible.

  • $\begingroup$ Hmmm... I once saw such a proof without QR. I'll see if I can find it. $\endgroup$ – punctured dusk Nov 6 '14 at 15:19
  • $\begingroup$ in $p$-adic Numbers by Gouvea, pages 77-78 in the second edition, anyway Proposition 3.5.1, previous section on Hensel's Lemma, this section on Hasse-Minkowski. Finishes section with Legendre's theorem on indefinite ternaries. $\endgroup$ – Will Jagy Nov 6 '14 at 17:17
  • $\begingroup$ This is a very interesting question to me because it seems like something that is taken for granted or even ignored. For example, in algebraic number theory, $\left(\frac{a}{p}\right)$ might tell you whether $p$ is inert or not in $\mathcal{O}_{\mathbb{Q}(\sqrt{a})}$. But if $a$ is a perfect square, then $\mathcal{O}_{\mathbb{Q}(\sqrt{a})}$ is just a pointless layer of abstraction. Along similar lines, if $a$ is squarefree, then all perfect squares are norms in $\mathcal{O}_{\mathbb{Q}(\sqrt{a})}$. $\endgroup$ – Robert Soupe Nov 7 '14 at 4:55

Let $D$ be a nonsquare. Equation (3.3) of Selberg's "An elementary proof of the prime number theorem for arithmetic progressions" states that $$\sum_{p \leq x,\ \left( \frac{D}{p} \right)=1} \frac{\log p}{p} = \frac{1}{2} \log x + O(1).$$ Combined with Mertens' first theorem $$\sum_{p \leq x} \frac{\log p}{p} = \log x + O(1),$$ this clearly implies that $\left( \frac{D}{p} \right)$ is infinitely often $1$ and infinitely often $-1$. As an exercise for myself, I will rewrite the proofs of Mertens' and Selberg's results as cleanly as I can. I learned about Selberg's approach from a beautiful Mathoverflow answer by Vesselin Dimitrov.

We start with the proof of Merten's theorem. Consider $x! = \prod_{n=1}^{x} n$. We estimate the size of $\log x!$ in two ways. On the one hand, $$\log x! \approx \int_{t=1}^x \log t dt = x \log x -x+1 = x \log x + O(x). \quad (1)$$

On the other hand, consider any prime number $p \leq x$. Then $p$ divides $(x/p)+O(1)$ of the terms in $x!$. Ignoring for the moment that some of those terms may be divisible by $p^2$, we get a contribution of $\sum_{p \leq x} \frac{x}{p} \log p + \sum_{p \leq x} O(\log p)$ from those terms. Using Chebyshev's bound $\sum_{p \leq x} \log p = O(x)$, we conclude that $$\log x! = x \sum_{p \leq x} \frac{\log p}{p} + O(x). \quad (2)$$ Including the possibility of $p$ dividing a term more than once only contributes $\sum_{p \leq x} \sum_{k=2}^{\infty} O(\frac{x \log p}{p^k}) = O(x)$, so that doesn't change (2). Combining (1) and (2) gives Merten's first theorem.

We now apply the same idea to prove Selberg's theorem. Fix a bounded convex region $C$ in $\mathbb{R}^2$ of area $1$, containing the origin. Selberg uses a particular parallelogram, but I find that more confusing than helpful. Write $\sqrt{x}C$ for the $\sqrt{x}$-fold dilation of $C$. We will estimate $$P(x) := \prod_{(u,v) \in \sqrt{x} C \setminus \{(0,0) \}} |u^2-D v^2| .$$ in two ways. Since $D$ is not square, the product is not zero. (However, this is not the main use of the fact that $D$ is not square; that is yet to come.)

We can explain the factor of $\sqrt{x}$ by noting that $\sqrt{x} C$ will contain roughly $x \mathrm{Area}(C) = x$ lattice points, so $P(x)$ is like a factorial.

On the one hand, we can justify approximating $\log P(x)$ by the integral $$ \log P(x) \approx \int_{(u,v) \in \sqrt{x} C} \log |u^2 - D v^2| du dv. $$ Putting $u_2=u/\sqrt{x}$ and $v_2=v/\sqrt{x}$, this is $$ \int_{(u_2, v_2) \in C} (\log x + \log |u_2^2-D v_2^2|) (\sqrt{x} du_2) (\sqrt{x} dv_2) = \int_{(u_2, v_2) \in C} (x \log x) du_2 dv_2 +O(x) $$ $$ = (x \log x) \mathrm{Area}(C)+O(x) = x \log x + O(x). \quad (3)$$ You can compare this to our earlier formula $\log x! = x \log x + O(x)$, also obtained by integration.

On the other hand, consider a prime $p$ and think about how many times it can divide $P(x)$. If $\left( \frac{D}{p} \right)=-1$, then the only way for $p$ to divide $u^2-D v^2$ is for $p$ to divide both $u$ and $v$. So the number of times this happens is $\# (\sqrt{x} C) \cap (p \mathbb{Z}^2) \approx \frac{\mathrm{Area}(\sqrt{x} C)}{p^2} = x/p^2$. As before, $\sum \frac{x \log p}{p^2} = O(x)$, so this is unimportant.

Now suppose that $p$ is odd, not dividing $D$, and $\left( \frac{D}{p} \right) = 1$. Then there are two square roots, $\pm \mu$, of $D$ in $\mathbb{Z}/p \mathbb{Z}$. We define two lattices $\Lambda^p+$ and $\Lambda^p_-$ by $\Lambda^p_{\pm} = \{ u \equiv \pm \mu v \bmod p \} \subset \mathbb{Z}^2$. Then $p$ divides $u^2-D v^2$ if and only if $p$ is in either $\Lambda^p_+$ or $\Lambda^p_-$. The fundamental domains of the $\Lambda^p_{\pm}$ both have area $p$. So the rough number of $p$ for which this happens is $2 \frac{\mathrm{Area}(\sqrt{x} C)}{p} = \frac{2x}{p}$, and we get $P(x) \approx \sum_{p \leq x,\ \left( \frac{D}{p} \right) = 1} \frac{2x}{p} \log p$. One can show that the contributions from $p$ dividing $u^2-D v^2$ more than once, and from $p$ dividing $D$ or equal to $2$ are negligible, and wind up with the conclusion $$\log P(x) = 2x \sum_{p \leq x,\ \left( \frac{D}{p} \right) = 1} \frac{\log p}{p} + O(x). \quad (4)$$

Comparing (3) and (4), we deduce Selberg's equation. QED, but we are not quite done.

We need to justify that the number of points in $\sqrt{x} C \cap \Lambda^p_{\pm}$ is well approximated by $\frac{\mathrm{Area}(\sqrt{x} C)}{\det \Lambda^p_{\pm}}$, where $\det \Lambda$ is the area of a fundamental domain for $\Lambda$. This requires us to show that $\Lambda^p_{\pm}$ is not too crazy. (We also need a similar claim for $p \mathbb{Z}^2$, but that is similar and easier.) Specifically, we will need

Lemma All nonzero vectors in $\Lambda_{\pm}$ have length at least $\sqrt{p/|D|} = \sqrt{\det \Lambda^p_{\pm}}/\sqrt{|D|}$.

Proof Let $(u,v) \in \Lambda^p_{\pm}$. Then $u^2 - D v^2 \equiv 0 \bmod p$. But, since $D$ is not square, $u^2-D v^2 \neq 0$ and we know that $|u^2-D v^2| \geq p$. Then $u^2+v^2 \geq \frac{|u^2-D v^2|}{D} \geq p/d$, as required. $\square$

We now turn to proving a bunch of Lemmas about integer points in Lattices.

Specifically, we show:

Key lattice lemma Let $C$ be as above. Fix a constant $c>0$, and let $\Lambda \subset \mathbb{R}^2$ be lattice in which each vector has length $\geq c \sqrt{\det \Lambda}$. Then, for $R>0$, $$ \#((RC) \cap \Lambda) = \frac{R^2}{\det \Lambda} + O(R/\sqrt{\det \Lambda}) .$$

This section amounts to me unpacking the phrases "it is easily shown" and "hence" in the paragraph at the bottom of Selberg's page 71.

Lemma Let $\Lambda$ be any lattice in $\mathbb{R}^2$. Then $\Lambda$ has a basis $v_1$, $v_2$ for which the angle between $v_1$ and $v_2$ is between $\pi/3$ and $2 \pi/3$.

Proof Let $v_1$ be the shortest nonzero vector in $\Lambda$. Rotating and rescaling, we may assume that $v_1 = (1,0)$. Let $w=(a,b)$ be an arbitrary other vector which forms a basis together with $v_1$. Then $w+k v_1 = (k+a, b)$ also forms a basis together with $v_1$. Suppose, for the sake of contradiction, that the angle between $v_1$ and $w+k v_1)$ never lies between $\pi/3$ and $2 \pi/3$. Then there is some $k$ where $\angle(v_1, w+k v_1) > 2 \pi/3$ and then $\angle(v_1, w+(k+1) v_1) < \pi/3$. But, also, $w+k v_1$ and $w+kv_2$ lie outside the unit circle, since we choose $v_1$ minimal. It is impossible to find two points which are the endpoints of a horizontal line segment of length $1$ so that both lie outside the unit circle, with one at angle $<\pi /3$ from horizontal and the other at angle $>2 \pi/3$. $\square$

From now on, let $\Lambda$ obey the condition that all vectors have length at least $c \sqrt{\det \Lambda}$.

Lemma $\Lambda$ has a basis $v_1$ and $v_2$ where both $v_i$ have length $\leq 2 \sqrt{\det \Lambda}/c$.

Proof Choose the basis from the previous Lemma, and let $\theta$ be the angle between $v_1$ and $v_2$. Then $\det \Lambda = |v_1 \times v_2| = |v_1| \ |v_2| \ |\sin \theta| \geq |v_1| \ |v_2|/2$. Since $|v_1| \geq c \sqrt{\det \Lambda}$, we deduce $|v_2| \leq 2 \sqrt{\det \lambda}/c$, and vice versa. $\square$

Now, apply a change of basis to make $v_1$, $v_2$ into the standard basis $(1,0)$ and $(0,1)$. Let $C'$ be the image of $C$ under this change of basis. So we are counting ordinate lattice points in $RC'$. The area of $RC'$ is $R^2/\det \Lambda$. The perimeter of $RC'$ is $O(R/\sqrt{\det \Lambda})$, because the fact that $v_1$ and $v_2$ are roughly the same length and form an angle not too far from $\pi/2$ means that our linear transformation can't distort $C$ too badly.

Now the Key Lattice Lemma follows from Lemma 2.1.1 of Huxley on counting points of $\mathbb{Z}^2$ in a convex region. (I can't believe I couldn't find a more elementary reference than Huxley, but it works, and this particular lemma is explained in a very clear and elementary way.) Now we get to write QED.

  • $\begingroup$ This is very interesting and quite surprising. When I asked the question, I thought that there would be a relatively easy algebraic proof but none were forthcoming and the first answer I get is very analytic! I would still be interested in a purely algebraic proof but will accept this after going through it once more when I have some more time. $\endgroup$ – Asvin Jul 25 '15 at 18:47
  • 1
    $\begingroup$ @Asvin I think a purely algebraic proof will be hard. You can give a mixed algebraic and analytic proof: If $D$ is not square, then the zeta function of $\mathbb{Q}(\sqrt{D})$ will have a simple pole at $s=1$. But this $\zeta$ function is $Z(s) = \prod_{p} \frac{1}{(1-p^{-s})(1-\left( \frac{D}{p} \right) p^{-s})}$ so, if $\left( \frac{D}{p} \right)$ is always $1$ (or finitely often $0$), you basically get $\zeta(s)^2$, with a double pole. But you still need some analysis to set up $\zeta$ functions. I decided to go to the other extreme and give a purely analytic proof. $\endgroup$ – David E Speyer Jul 26 '15 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.