In the last post we showed that:
If \(n\) is 1 or 2 mod 4 and there is a finite projective plane of order \(n\), then \(n\) can be written as the sum of two squares of rational numbers.
The objective now is to show that if a prime \(p=3\bmod 4\) divides \(n\) to an odd power (ie the highest power of \(p\) which divides \(n\) is odd) then \(n\) cannot be written as the sum of two squares of rational numbers.
Putting these two together gives immediately, that if \(n\) is 1 or 2 mod 4 and has a prime factor \(p=3\bmod 4\) which divides it to an odd power, then there is no finite projective plane of order \(n\), which is the celebrated Bruck-Ryser theorem.
So suppose \(n=r^2+s^2\) with \(r,s\) rational. Then multiplying through by a suitable positive integer \(c\), such as the lowest common multiple of the denominators of \(r\) and \(s\) we get $$c^2n=a^2+b^2$$
Now suppose that the highest power of \(p=3\bmod 4\) dividing \(nc^2\) is \(2k+1\). Then we have \(a^2+b^2=0\bmod p\).
Lemma 3
If \(p=3\bmod 4\) is a prime and divides \(a^2+b^2\), then \(a,b\) are both multiples of \(p\).
We use the fact that the residues \(G=\{1,2,\dots,p-1\}\) form a group under multiplication \(\bmod p\). So if \(a\) is not a multiple of \(p\) then we can find \(c\in G\) such that \(ac=1\bmod p\) and hence \(0=(a^2+b^2)c^2=1+b^2c^2\bmod p\), so \((bc)^2=-1\bmod p\) and hence \(bc\) has order 4. But \(|G|=p-1=2\bmod 4\), so 4 does not divide \(|G|\). Contradiction. \(\Box\)
So we can divide through \(c^2n=a^2+b^2\) by \(p^2\). After repeating another \(k-1\) times we end up with $$N=A^2+B^2$$
with \(N=c^2n/p^{2k},A=a/p^k,B=b/p^k\), and \(N\) divisible by \(p\) but not \(p^2\). But the Lemma still gives \(A,B\) divisible by \(p\) and hence \(N\) divisible by \(p^2\). Contradiction.
That completes the proof of Bruck-Ryser, except for the two Lemmas in the earlier post. The first (Lemma 1) was to show that any positive integer is the sum of four (or fewer squares). That is a well-known result proved by Lagrange (1736-1813) in 1770.
The second (Lemma 2) was to show explicitly that if two integers \(m,n\) can each be expressed as a sum of four squares (some of which may be zero), then so can their product \(mn\). The proof there is just a question of multiplying out the formulae stated in the Lemma.
Using Lemma 2, we see that to prove Lemma 1 it is sufficient to prove it for any prime. The case 2 is obvious: \(2=1^2+1^2\).
So now suppose \(p\) is any odd prime. We show first that we can find integers \(a,b\) such that \(a^2+b^2+1=kp\) with \(0\lt k\lt p\). Put \(m=(p-1)/2\). The \(m+1\) numbers \(0,1^2,\dots,m^2\) must all be incongruent \(\bmod p\). For \(a^2-b^2=(a-b)(a+b)\) and \(0\lt a+b\le 2m\lt p\), so \(a+b\) cannot be divisible by \(p\), whilst \(-m\le a-b\le m\) and \(a-b\ne 0\) so \(a-b\) cannot be divisible by \(p\). Hence the \(m+1\) numbers \()-1,-1-1^2,\dots,-1-m^2\) must also be incongruent \(\bmod p\). But there are only \(2m+1\) incongruent numbers \(\bmod p\) so the two sets must overlap, giving \(a,b\) such that \(a^2+b^2+1=0\bmod p\). But \(0\lt a^2+b^2+1\le 2m^2+1\lt 2m(2m+1)\lt p^2\).
So let \(h\) be the smallest positive integer such that \(a^2+b^2+c^2+d^2=hp\) for some integers \(a,b,c,d\). \(h\) cannot be even for then an even number of \(a,b,c,d\) must be odd, so rearranging so that both or neither of \(a,b\) are odd, and both or neither of \(c,d\) are odd, we have \(\left({\frac {a+b}2}\right)^2+\left({\frac {a-b}2}\right)^2+\left({\frac {c+d}2}\right)^2+\left({\frac {c-d}2}\right)^2=\left({\frac h2}\right)p\), which contradicts the minimality of \(h\).
Suppose \(h\) is odd and greater than 1. Take \(A=a\bmod h,B=b\bmod h\), \(C=c\bmod h,D=d\bmod h\) and \(-h/2\lt A,B,C,D\lt h/2\). Then \(A^2+B^2+C^2+D^2\lt h^2\) and \(A^2+B^2+C^2+D^2=0\bmod h\), so \(A^2+B^2+C^2+D^2=h’h\) with \(0\le h’\lt h\). If \(h’=0\) then \(A=B=C=D=0\) so \(a,b,c,d\) are all multiples of \(h\) and hence \(h^2\) divides \(a^2+b^2+c^2+d^2=hp\). So \(h\) divides \(p\), which is impossible since \(1\lt h\lt p\) which is prime. Hence \(h’\ne 0\). Now following Lemma 2 put:
\(\alpha=aA+bB+cC+dD\)
\(\beta=-bA+aB+dC-cD\)
\(\gamma=-cA-dB+aC+bD\)
\(\delta=-dA+cB-bC+aD\)
then \(\alpha^2+\beta^2+\gamma^2+\delta^2=hph’h\)
But \(-bA+aB=dC-cD=0\bmod h\), so \(\beta=0\bmod h\). Similarly, \(-cA+aC=-dB+bD=0\bmod h\), so \(\gamma=0\bmod h\) and similarly \(\delta=0\bmod h\). Thus four of the five terms in \(\alpha^2+\beta^2+\gamma^2+\delta^2=hph’h\) are divisible by \(h^2\), so the fifth, \(\alpha^2\) must also be divisible by \(h^2\) and we can divide by \(h^2\) to get four squares with sum \(h’p\), contradicting the minimality of \(h\). Hence \(h=1\) and \(p\) is a sum of four squares. \(\Box\)
The precursor to Lagrange’s result was a result of Pierre Fermat (born early 1600s, died 1665):
Lemma 4
An odd prime \(p\) can be written as a sum of two squares (of integers) if and only if it is \(1\bmod 4\). For example, \(29=2^2+5^2\) and \(29=7\cdot 4+1\).
The “only if” is almost obvious: \((2k)^2=4k^2=0\bmod 4\) and \((2k+1)^2=4k^2+4k+1=1\bmod 4\), so any square is 0 or \(1\bmod 4\), and hence a sum of two squares must be 0, 1 or 2 mod 4.
To prove the “if”, let \(p=4k+1\) be prime and define \(S\), a set of the triples of positive integers, as follows: \(S=\{(a,b,c):a^2+4bc=p\}\).
Notice that if \(a=b-c\) then \(a^2+4bc=(b+c)^2\) which is not prime, and if \(a=2b\) then \(a^2+4bc=4b(b+c)\) which is not prime, so no such triples can belong to \(S\), and hence \(S\) can be partitioned into three disjoint subsets: \(L=\{(a,b,c):a\lt b-c\},M=\{(a,b,c):b-c\lt a\lt 2b\}\) and \(N=\{(a,b,c):2b\lt a\}\). Define \(f\) on \(S\) by \(f(a,b,c)=(a+2c,c,b-c-a)\) for \((a,b,c)\in L\), \((2b-a,b,a-b+c)\) for \((a,b,c)\in M\), and \((a-2b,a-b+c,b)\) for \((a,b,c)\in N\).
It is easy to check that \(f(L)\subseteq N,f(M)\subseteq M,f(N)\subseteq N\) and that \(f(f(a,b,c))=(a,b,c)\). Any fixed point with \(f(a,b,c)=(a,b,c)\) must lie in \(M\) and hence satisfy \(a=2b-a,b=b,c=a-b+c\). So any fixed point must have the form \(a,a,c\). Since it lies in \(S\) is must also satisfy \(p=a^2+4ac=a(a+4c)\). Hence the unique fixed point is \((1,1,k)\). That means that \(S\) must have an odd number of elements, because the triples that are not fixed points form pairs \(T,T’\) with \(f(T)=T’,f(T’)=T\) and \(T\ne T’\).
But now define \(g\) on \(S\) by \(g(a,b,c)=(a,c,b)\). Its fixed points are all triples \((a,b,b)\) such that \(a^2+4b^2=p\). As with \(f\), since \(g(g(T))=T\) the triples which are not fixed form pairs, so since there are an odd number of triples in \(S\), there must be an odd number of fixed points, and hence at least one. \(\Box\)
[This approach is often known as Don Zagier's "one-line proof". Some line! Of course, if you just give the function \(f(S)\), that is maybe enough, but it is a fairly obscure hint, unless people are familiar with the basic idea.]
Problems
To round off this area you might like to look at two harder problems:
1. Which squares can be represented as a sum of three non-zero squares?
2. Which positive integers can be represented as a sum of three (or fewer) squares?
