This section involves extremely fiddly, annoying (or, put another way, marvellously creative, beautiful) mathematics. We need to be ready to get ours hands dirty, constructing bijections/partitions/relations between residue classes based on obscure/unwieldy properties. Good practice for tripos questions, I guess.
Lemma 1.1 There are exactly $\frac{p-1}{2}$ quadratic residues $\mod p$.
Proof: Take a primitive element, $g$. The quadratic residues are exactly the even powers of $g$.
Proof 2: $(-a)^2=a^2 \mod p$, so there are at most $\frac{p-1}{2}$ quadratic residues. $x^2 \equiv y^2 \mod p$ implies that $x \equiv \pm y \mod p$ (integral domain), so there are at least $\frac{p-1}{2}$ quadratic residues. $\square$
Theorem 1.2 (Euler's criterion) $a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \mod p$.
Proof: We will combine both proofs of the above lemma. We can assume $a$ coprime to $p$, as otherwise the claim is obvious (both sides are $0$).
First, note that $a^{p-1}\equiv 1 \mod p$ by Fermat's little theorem. Since we are working in an integral domain, $a^{\frac{p-1}{2}} \equiv \pm 1 \mod p$.
Let $g$ be a primitive element $\mod p$. Then $a=g^i$ for some $i$. If $i=2j$, then $a^{\frac{p-1}{2}}\equiv g^{(p-1)j} \equiv 1 \mod p$. Similarly, if $i$ is odd, then $a^{\frac{p-1}{2}} \equiv -1 \mod p$. Thus we have established that:
$$a^{\frac{p-1}{2}} = \left\{\begin{array}{ll} +1 & \text{if } a \text{ is an even power of } g \\ -1 & \text{if } a \text{ is an odd power of } g \end{array}\right.$$
From proof 1 above, this corresponds exactly to the value of the Legendre symbol $\left(\frac{a}{p}\right)$. $\square$
Proposition 1.3 (Gauss's lemma)
We introduce least absolute value notation for a residue class mod $p$: write $\langle a \rangle$ for the unique integer congruent to $a \mod p$ lying in $[-p/2,p/2]$.
If $p$ is an odd prime, and $a$ is coprime to $p$, then $\left(\frac{a}{p}\right) = (-1)^\gamma$, where $\gamma = \#\{k \in \{1,2,\ldots,\frac{p-1}{2}\} \mid \langle ka \rangle < 0 \}$.
We introduce least absolute value notation for a residue class mod $p$: write $\langle a \rangle$ for the unique integer congruent to $a \mod p$ lying in $[-p/2,p/2]$.
If $p$ is an odd prime, and $a$ is coprime to $p$, then $\left(\frac{a}{p}\right) = (-1)^\gamma$, where $\gamma = \#\{k \in \{1,2,\ldots,\frac{p-1}{2}\} \mid \langle ka \rangle < 0 \}$.
Proof: Observe that $\langle a \rangle, \langle 2a \rangle, \ldots, \langle \frac{p-1}{2}a\rangle$ are $\pm 1, \pm 2, \ldots, \pm \frac{p-1}{2}$ in some order, for some (fixed) choices of sign.
Hence, $(\frac{p-1}{2})!a^{\frac{p-1}{2}} \equiv \langle a \rangle \langle 2a \rangle \dots \langle (\frac{p-1}{2})a \rangle \equiv (-1)^\gamma (\frac{p-1}{2})! \mod p$.
By cancelling, $a^{\frac{p-1}{2}} \equiv (-1)^\gamma \mod p$. By Euler's criterion, $\left(\frac{a}{p}\right) \equiv (-1)^\gamma \mod p$. Since $(-1)^\gamma$ and $\left(\frac{a}{p}\right)$ are in $\{-1,1\}$, congruence implies equality. $\square$
Theorem 1.4 (Quadratic reciprocity)
Let $p$ and $q$ be odd primes. Then $\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{p}{q}\right)$.
If we assume $p$ and $q$ to be distinct, we can reformulate as $\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$.
Let $p$ and $q$ be odd primes. Then $\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{p}{q}\right)$.
If we assume $p$ and $q$ to be distinct, we can reformulate as $\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$.
Proof: To prove quadratic reciprocity, we use Gauss's lemma to rephrase the above assertion as the geometric problem of counting lattice points (points with integer coefficients in the plane) within specific regions of interest.
By the lemma, $\left(\frac{q}{p}\right)=(-1)^\gamma$, where $\gamma$ is as defined above.
We need to count how many of $\langle q \rangle, \langle 2q \rangle, \ldots, \langle \frac{p-1}{2} q \rangle$ are negative. (Note: we are working mod $p$.)
Observe that setting $\langle kq \rangle = kq - lp$ determines $l$ uniquely.
Thus, $\gamma$ corresponds to the number of lattice points $(k,l)$ within the region $-\frac{p}{2} < kq - lp < 0$. [more justification required]
Analagously, writing $\left(\frac{p}{q}\right)=(-1)^\beta$, Gauss's lemma says that $\beta$ corresponds to the number of lattice points $(k,l)$ within the region $-\frac{q}{2}< lp-kq < 0$.
Drawing the three (parallel) lines $kq-lp=-\frac{p}{2}$, $kq-lp=0$, and $kq-lp=\frac{q}{2}$ splits up the rectangle $0<k<p/2$, $0<l<q/2$ into four regions. From top left to bottom right, let's call them $A$ (a triangle), $B$ and $C$ (rhombuses), and $D$ (a triangle).
The total number of lattice points in the rectangle is $\frac{p-1}{2}\frac{q-1}{2}$ (recall that we are using strict inequality, so excluding those that fall on the axes). To prove quadratic reciprocity, we need the number of lattice points in $B$ and $C$ combined to have the same parity as $\frac{p-1}{2}\frac{q-1}{2}$.
We need two observations to see that this is true.
- There is a bijection between $A$ and $D$.
- None of the lattice points are on any of the three lines that we drew. The lecturer totally failed to discuss this point, but it is crucial - given that we are considering strict inequality, if a lattice point was on one of the lines it wouldn't be counted in any of the regions (and if we were considering non-strict inequality, it would be counted twice). Luckily, this can't happen as $p$ and $q$ are prime.
Combining these two observations means that $|B|+|C|+2|A| = \frac{p-1}{2}\frac{q-1}{2}$, and so $|B| + |C|$ and $\frac{p-1}{2}\frac{q-1}{2}$ have the same parity. From Gauss's lemma, above, we showed that $\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^\gamma(-1)^\beta=(-1)^{|B|+|C|}$, and the statement of quadratic reciprocity is $\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$, so we are done.
Let's prove 2 first. Suppose a point $(k,l)$ is on the line $kq-lp=0$, and that $k$ is an integer. Then $l=k\frac{q}{p}$, so $l$ isn't an integer. Similarly, if $k$ is an integer, then $l=k\frac{q}{p}+\frac{1}{2}$ isn't, and neither is $l=\frac{q}{p}(k-\frac{1}{2})$. Phew.
For 1, the required bijection is given by $(k,l) \leftrightarrow \left(\frac{p+1}{2}-k, \frac{q+1}{2}-l\right)$ (the same formula works both ways, from $A$ to $D$ and from $D$ to $A$). Visually, you pick up the bottom right triangle, rotate it 180 degrees, and slap it back onto the top right triangle. It doesn't fit together exactly, but instead overlaps egregiously, so it's really quite remarkable that this works. The lecturer left it as an exercice to prove that this bijection indeed does the job (I'm getting the impression that this proof is unlikely to come up in the exam).
The map is clearly injective from the above observation that the formula is self-inverse, i.e. applying it twice recovers the same point. So we only need to check that this map is well-defined, i.e. maps $C$ into $D$, and is surjective. Well-definedness is easy to obtain from definition-chasing. There is no extra work in obtaining surjectivity - it follows from well-definedness in the other direction. So we are done. $\square$
For 1, the required bijection is given by $(k,l) \leftrightarrow \left(\frac{p+1}{2}-k, \frac{q+1}{2}-l\right)$ (the same formula works both ways, from $A$ to $D$ and from $D$ to $A$). Visually, you pick up the bottom right triangle, rotate it 180 degrees, and slap it back onto the top right triangle. It doesn't fit together exactly, but instead overlaps egregiously, so it's really quite remarkable that this works. The lecturer left it as an exercice to prove that this bijection indeed does the job (I'm getting the impression that this proof is unlikely to come up in the exam).
The map is clearly injective from the above observation that the formula is self-inverse, i.e. applying it twice recovers the same point. So we only need to check that this map is well-defined, i.e. maps $C$ into $D$, and is surjective. Well-definedness is easy to obtain from definition-chasing. There is no extra work in obtaining surjectivity - it follows from well-definedness in the other direction. So we are done. $\square$
No comments:
Post a Comment