## Sunday, August 31, 2014

### Quadratic reciprocity via discrete Fourier analysis

In this post, we give a proof of the law of quadratic reciprocity based on discrete Fourier analysis and more precisely Gauss sums. This celebrated theorem has numerous proofs, but the most elementary ones usually boil down to some tedious combinatorial computations. In particular, after one has derived Gauss' lemma or some similar statement that is usually used in the proof, the big picture may become unclear, and one is left with some combinatorial counting problem. On the other hand, if one uses discrete Fourier analysis to prove the reciprocity law, the structure of the proof is simple, and one works in the context of trigonometric sums instead of solving an isolated combinatorial problem. Moreover, this method generalizes to higher reciprocity laws as well, and similar ideas as in what follows can be applied for example in proving the functional equation of the $L$-functions, the class number formula or the Pólya-Vinogradov inequality. Some of these results will be discussed in later posts.

Reduction of quadratic congruences to those with prime modulus

The theory of quadratic residues concerns the existence of solutions to the congruence $x^2\equiv a \pmod m$. Any quadratic congruence $Ax^2+Bx+C\equiv 0 \pmod m$ can be transformed easily into this form (or into a linear congruence). The number $a$ is called a quadratic residue if the congruence is solvable. The following proposition shows that it is enough to consider the congruence when $m$ is prime or $m=4$.

Proposition 1. Let $m=2^{d}p_1^{\alpha_1}...p_k^{\alpha_k}$, where $p_i$ are distinct odd primes. Then the congruence $x^2\equiv a \pmod m$ has a solution if and only if each of the congruences $x^2\equiv a \pmod{p_i}$, $i=1,...,k$ and $x^2\equiv a \pmod{2^{d'}}$ has a solution. Here $d'=2$ if $d\geq 2$, $d'=1$ if $d=1$ and $d'=0$ otherwise.

Proof. The only if part is trivial, so we prove the if part. By the Chinese remainder theorem, $x^2\equiv a \pmod m$ has a solution if and only if each of the congruences $x^2\equiv a \pmod{p_i^{\alpha_i}}$, $x^2\equiv a \pmod{2^d}$ has a solution. First let $p$ be odd. Now if $x^2\equiv a \pmod p$ has a solution, so does $x^2\equiv a \pmod{p^{\alpha}}$. To see this, we use induction on $\alpha$; the case $\alpha=1$ is trivial. Let $x_0^2\equiv a \pmod{p^{\alpha-1}}$. Now $(x_0+kp^{\alpha-1})^2\equiv x_0^2+2kp^{\alpha-1}\pmod{p^{\alpha}}.$ We have $x_0^2=a+r\cdot p^{\alpha-1}$ for some integer $r$, so it suffices to choose $k$ such that $2k\equiv -r \pmod p$, which is possible as $p$ is odd.

Next let $p=2$. We show that if $x^2\equiv a \pmod 4$ is solvable, then so is $x^2\equiv a\pmod{2^{\alpha}}$. We use induction and assume $x_0^2\equiv a \pmod{2^{\alpha-1}}$. We may assume $x_0=a+r\cdot 2^{\alpha-1}$, where $r$ is odd, as otherwise we are done. Now $(x_0+2^{\alpha-2})^2\equiv a+(r+1)2^{\alpha-1}+2^{2\alpha-2}\equiv a \pmod{2^{\alpha}}$ since $\alpha\geq 2$. ■

Now the study of quadratic congruences has been reduced to solving $x^2\equiv a \pmod p$ where $p$ is a prime. To study this, we define the Legendre symbol, which makes determining the solvability of quadratic congruences much easier.

Definition. Let $a$ be an integer and $p$ an odd prime. Then we define the Legendre symbol as
$\begin{eqnarray}\left(\frac{a}{p}\right)=\begin{cases}1\quad \text{if}\quad x^2\equiv a \pmod p\quad \text{for some}\quad x\not \equiv 0\pmod p,\\0 \quad \text{if}\quad p\mid a,\\-1\quad\text{otherwise.}\end{cases}\end{eqnarray}$
Euler's criterion shows that the symbol is multiplicative.

Theorem 2 (Euler's criterion). We have $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p$.

Proof. Suppose $a\neq 0\pmod p$, since that case is trivial. If $a\equiv x^2\pmod p$, then clearly both sides are $1\pmod p$. Since $a^{p-1}\equiv 1 \pmod p,$ we have $a^{\frac{p-1}{2}}\equiv \pm 1\pmod p$. The congruence $a^{\frac{p-1}{2}}\equiv 1$ holds for the $\frac{p-1}{2}$ numbers $1^2,2^2,...,\left(\frac{p-1}{2}\right)^2$, so it cannot hold for any more numbers by Lagrange's theorem. Therefore $a^{p-1}\equiv -1 \pmod p$ if $a$ is not a square $\pmod p.$

Now we have $\left(\frac{ab}{p}\right)= \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$, so in order to determine $\left(\frac{a}{p}\right)$ for any $a$, it suffices to know $\left(\frac{q}{p}\right)$, $\left(\frac{2}{p}\right)$ and $\left(\frac{-1}{p}\right)$ for all odd primes $q$. By Euler's criterion, $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$. The law of quadratic reciprocity determines the symbol $\left(\frac{q}{p}\right)$. The symbol $\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$ could be computed with a similar argument.

Gaussian sums and quadratic reciprocity

We are now in a position to state the law of quadratic reciprocity.

Theorem 3. Let $p$ and $q$ be distinct odd primes. Then
$\begin{eqnarray}\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}.\end{eqnarray}$

As mentioned, the proof is based on considering the Gauss sums
$\begin{eqnarray}G_q=\sum_{m=1}^{q-1}\left(\frac{m}{q}\right)e^{\frac{2\pi i m}{q}}.\end{eqnarray}$
This is the discrete Fourier transform of the numbers $\left(\frac{m}{q}\right)$. The basic idea of the proof is the based on the general principle that if we obtain enough information about a generating function (which to us is this discrete Fourier transform), then we can extract information about its coefficients. We will compute two quantities, and then combine the results to get the quadratic reciprocity law.

Lemma 4. Let $\chi(n)=\left(\frac{n}{q}\right)$ where $q$ is a prime (this is called a real Dirichlet character). Then $\chi$ has the discrete Fourier series
$\begin{eqnarray}\chi(n)G_{q}=\sum_{n=1}^{q-1} \chi(m)e^{\frac{2\pi i mn}{q}}.\end{eqnarray}$
Proof. First suppose $q\nmid n,$ and denote by $\mathbb{Z}_q^{\times}$ the invertible residue classes $\pmod q$. In this case the lemma follows from
$\begin{eqnarray}\sum_{m=1}^{q-1}\chi\left(m\right)e^{\frac{2\pi i mn}{q}}&=&\sum_{m\in \mathbb{Z}_q^{\times}} \chi\left(m\right)e^{\frac{2\pi i mn}{q}}\\&=&\sum_{k\in\mathbb{Z}_q^{\times}} \chi\left(kn^{-1}\right)e^{\frac{2\pi i k}{q}} \quad (\text{denoting} \quad k=mn)\\&=&\chi\left(n^{-1}\right)G_q=\chi\left(n\right)G_q\end{eqnarray}$
Then let $q\mid n.$ In that case the identity follows from $0=\sum_{n=1}^{q-1}\left(\frac{n}{q}\right),$ which is true since there are exactly $\frac{q-1}{2}$ quadratic residues $\pmod q$. ■

Lemma 5. For any odd integer $q$, we have $G_q^2=(-1)^{\frac{p-1}{2}}p$.

Proof. We apply the previous lemma to get
$\begin{eqnarray}G_q^2&=&G_q\sum_{n\in \mathbb{Z}_q}\chi(n)e^{\frac{2\pi i n}{q}}\\&=&\sum_{n\in \mathbb{Z}_q}\sum_{m\in \mathbb{Z}_q} \chi(m)e^{\frac{2\pi i mn}{q}} e^{\frac{2\pi i n}{q}}\\&=&\sum_{m\in \mathbb{Z}_q}\chi(m)\sum_{n\in \mathbb{Z}_q} e^{\frac{2\pi i (m+1)n}{q}}.\end{eqnarray}$
If $m\neq -1$ (in $\mathbb{Z}_q$), the inner sum is zero, and otherwise it is $q$. Therefore,
$\begin{eqnarray}G_q^2=\chi(-1)q=(-1)^{\frac{q-1}{2}}q\end{eqnarray}$
since $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$ by Euler's criterion. ■

Lemma 6. For any distinct odd primes $p$ and $q$, we have $G_p^{q-1}=\left(\frac{q}{p}\right),$ where the equality is in a finite field $F$ containing $\mathbb{Z}_q$ and the $p$th roots of unity (it cannot be an equality in $\mathbb{C}$ since by Lemma 5 the number $G_p$ has absolute value $\sqrt{p}$).

Since the field $F$ contains $\mathbb{Z}_q$, it has characteristic $q$ (that is, $qx=0$ for $x\in F$), so the binomial formula gives $(a+b)^q=a+b$ for all $a,b\in F$. Let $\zeta_p$ be a primitive $p$th root of unity in $F$. We get
$\begin{eqnarray}G_p^{q}=\sum_{m=1}^{p-1}\left(\frac{m}{p}\right)\zeta_p^{qm}.\end{eqnarray}$
Let $m=q'n$ where $qq'\equiv 1 \pmod p$. Then
$\begin{eqnarray}G_p^{q}=\sum_{n=1}^{q-1}\left(\frac{nq'}{p}\right)\zeta_p^{n}=\left(\frac{q'}{p}\right)G_p=\left(\frac{q}{p}\right)G_p,\end{eqnarray}$
since $q$ is a quadratic residue if and only if its reciprocal $q'$ is. By Lemma 5, $G_p\neq 0$, so we may divide by it. ■

Now we can finish the proof of the law of quadratic reciprocity. We compute
$\begin{eqnarray}G_p^q=(G_p^2)^{\frac{q-1}{2}}G_p=p^{\frac{q-1}{2}}(-1)^{\frac{(p-1)(q-1)}{4}}G_p\end{eqnarray}$
by Lemma 5. On the other hand, by Lemma 6, the result in $F$ is $\left(\frac{q}{p}\right)G_p$. Comparing the quantities, we see that
$\begin{eqnarray}p^{\frac{q-1}{2}}(-1)^{\frac{(p-1)(q-1)}{4}}=\left(\frac{q}{p}\right),\end{eqnarray}$
and by Euler's criterion $\left(\frac{p}{q}\right)=p^{\frac{q-1}{2}}$, which completes the proof. ■