Proofs of Jacobi's four-square theorem What are the nicest proofs of Jacobi’s four-square theorem you know? How much can they be streamlined? How are they related to each other?
I know of essentially three aproaches.


*

*Modular forms, as in, say, Zagier’s notes in “The 1-2-3 of Modular Forms”. The key facts here are that (a) the theta function is a modular form, (b) the space of modular forms of given weight and level is finite-dimensional (indeed 2-dimensional for the small level that is involved here). I feel reasonably certain that I can pare this down to fit my constraints without too much loss.

*Elliptic functions. This, I understand, is the route originally chosen by Jacobi himself; it is also the one I have seen most often. There are many variants. Most of the time one proves Jacobi’s triple product identity first (good: see the constraints above) and then derives the theorem from it in several pages of calculations involving at least one miraculous-looking identity. My concerns here are two-fold. First – all of these identities (triple-product included) really rest on the same fact, namely, the low-dimensionality of the space of elliptic functions with given multipliers (or whatever they are called). However, even when this is said, this is not really fully and directly exploited in the proofs I’ve seen. Second – while some proofs of Jacobi’s triple product identity I’ve seen are reasonably streamlined, what comes thereafter always comes through as computational and very ad-hoc. Can any of this be helped?
– A variant of this approach is Ramanujan’s proof in Hardy-Wright. It’s concise, but I’d really like to see what it really rests on. Can it be made clearer, a little longer and a little less elementary?

*Uspensky’s elementary proof, based on an identity of Liouville’s; there is an exposition of this in Moreno-Wagstaff. Liouville’s identity feels like a bit of magic to me – I feel there is really something about elliptic functions being snuck here, though I do not know exactly what.


What is your take on this? How are these approaches related? (I feel they have to be, in several ways. In particular, a Jacobi theta function is both an elliptic function and a modular form, depending on which variable you are varying.) What would be some ways of making the elliptic-function approach more streamlined and conceptual, without much in the way of calculations?
 A: Hardy & Wright have an elementary g.f. proof (but not very short).  There is a slick two page proof by Michael Hirschhorn, with a revealing title "A Simple Proof of Jacobi's Four-Square Theorem" (available here). It uses only Jacobi triple product identity which itself has several short proofs (see here and bijective proofs here).  A combined proof is accessible to undergraduates. 
P.S.  There is also a curious proof by Andrews and Zeilberger: "A Short Proof of Jacobi's Formula for the Number of Representations of an Integer as a Sum of Four Squares".  The story behind this proof is also interesting, but I can't remember if it's written anywhere or just something George Andrews told me.  
A: A bit long for a comment. Steve Milne of Ohio State sent me his article, the entirety of The Ramanujan Journal, volume 6, number 1, March 2002. 143 pages. Title is Infinite Families of Exact Sums of Squares Formulas, Jacobi Elliptic Functions, Continued Fractions, and Schur Functions. In the Abstract he begins 

In this paper we derive infinitely
  many infinite families of explicit
  exact formulas involving either
  squares or triangular numbers, two of
  which generalize Jacobi's 4 and 8
  squares identities to $4 n^2$ or
  $4n(n+1)$ squares, respectively,
  without using cusp forms.  

Evidently available as a hardcover book from Kluwer. I understand that the material was a decade or so in the making, so Milne developed some well known theorems first although they were published first by others.
A: There is a very nice and readable little book by Hurwitz from 1919 (Adolf Hurwitz, Vorlesungen über die Zahlentheorie der Quaternionen, Springer Verlag 1919) in which he describes the properties of the integer quaternions (later called Hurwitzian quaternions): the subring of the Hamiltonian quaternions of the form a + bi + cj + dk where a, b, c, and d are either all integers or all half-integers (like 3/2). Basically the point of the book is that this ring behaves pretty much like any other UFD, except that it is not commutative. So there are prime elements and unique factorization into them etc, when using the right notion of uniqueness to take care of the left/rigth business. Towards the end of the book he starts considering the finite quotients obtained by modding out the two sided ideals generated by these primes and doing a lot of counting inside these rings he deduces the four square theorem. It is not the most beautiful part of the book because there is a lot of 'administration' to keep track of, but it is a nice elementary proof of the theorem. I hope I can find the title.
A: I thought I would write out the quaternion proof, because it is really quite elegant if you have good algebraic terminology. One note: I won't be proving quite the right result. Let $r(n)$ be the number of quadruples $(a,b,c,d)$ with $n=a^2+b^2+c^2+d^2$ such that either $a$, $b$, $c$ and $d$ are all in $\mathbb{Z}$, or are all in $(1/2) + \mathbb{Z}$. The formula I'll be proving is 
$$r(n) = 24 \sum_{\begin{matrix} d|n \\ d \ \mathrm{odd} \end{matrix}} d \quad \mathrm{for}\ n>0$$
The question of allocating the terms between $\mathbb{Z}$ and $(1/2) + \mathbb{Z}$ is a bit messier.
Let $H$ be the ring of quaternions of the form $a+bi+cj+dk$, with $(a,b,c,d)$ as above.
The following lemmas are proved in many sources on the quaternion proof of the Lagrange theorem:
$\bullet$ Every right ideal of $H$ is principal.
$\bullet$ The right ideal $(a+bi+cj+dk) H$ has index $(a^2+b^2+c^2+d^2)^2$ in $H$.
Let $q(n)$ be the number of right ideals of $H$ that have index $n^2$. Since the unit group of $H$ has size $24$, we have $r(n) = 24 q(n)$. So we concentrate on computing $q(n)$.
Let $I = (a+bi+cj+dk)H$ be a right ideal of $H$ with index $n^2$. Then $(a+bi+cj+dk)(a-bi-cj-dk) = n \in (a+bi+cj+dk)H$. So $I/nH$ is an index $n^2$ ideal in the ring $H/nH$. We see that $q(n)$ is the number of index $n^2$ ideals in $H/nH$.
Now, by the Chinese remainder theorem, if $m$ and $n$ relatively prime, then $H/mnH \cong H/mH \times H/nH$. So $q(n)$ is multiplicative, and we are reduced to proving the claim for $n$ a prime power. 

We start in the case $n = p^r$ for $p$ odd. Let $\mathbb{Z}_p$ be the $p$-adic integers and let $H_p := H \otimes \mathbb{Z}_p$. We will start by showing that the number of index $p^{2r}$ ideals in $H_p$ is $p^r+p^{r-1} + \cdots + p+1$. We then check that all of those ideals contain $p^r H$, so this is also the number of ideals in $H/p^r H$.
The point is that $H_p \cong \mathrm{Mat}_{2 \times 2}(\mathbb{Z}_p)$ (again, for $p$ odd). By a standard pigeon hole argument, we can find $u$ and $v$ with $u^2+v^2 + 1 \equiv 0 \mod p$; by Hensel's lemma, we can find $u$ and $v$ in $\mathbb{Z}_p$ with $u^2+v^2+1=0$. Let 
$$I = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} \quad 
J = \begin{pmatrix} u & v \\ v & -u \end{pmatrix} \quad 
K = \begin{pmatrix} v & -u \\ -u & -v \end{pmatrix}.$$ 
Then $I$, $J$ and $K$ obey the quaternion relations, and we get a map $H_p \to \mathrm{Mat}_{2 \times 2}(\mathbb{Z}_p)$. We claim that this map is bijective. It is a map between two free $\mathbb{Z}_p$-modules of rank four, so we just need to check that the determinant of this map is a unit of $\mathbb{Z}_p$. This determinant is $-4(u^2+v^2)=4$. Since $p$ is odd, we are fine.
So, set $E_p := \mathrm{Mat}_{2 \times 2}(\mathbb{Z}_p)$. Let's count index $p^{2r}$ right ideals $E_p$. Let $M$ be the $E_p$-module $\mathbb{Z}_p^2$. As a module over itself, $E_p \cong M^{\oplus 2}$. Right ideals is another word for submodules, so we want to count index $p^{2r}$ submodules of $M^{\oplus 2}$. Since $E_p$ is Morita equivalent to $\mathbb{Z}_p$, we know that $E_p$ submodules of $M^{\oplus 2}$ are in bijection with $\mathbb{Z}_p$-submodules of $\mathbb{Z}_p^{\oplus 2}$. A quick check shows that being index $p^{2r}$ in $M^{\oplus 2r}$ corresponds to being index $p^r$ in $\mathbb{Z}_p^{\oplus 2}$. Moreover, every index $p^r$ submodule of $\mathbb{Z}_p^{\oplus 2}$ is contained in $p^r \mathbb{Z}_p^{\oplus 2}$, so every index $p^{2r}$ submodule of $M^{\oplus 2}$ is contained in $p^r M^{\oplus 2}$, fulfilling an earlier promise, and allowing us to shift our attention to the finite problem of counting index $p^r$ submodules in $(\mathbb{Z}/p^r)^{\oplus 2}$.
We are reduced to showing that the number of index $p^r$ submodules of $(\mathbb{Z}/p^r)^{\oplus 2}$ is $p^r + p^{r-1} + \cdots p+1$. Proof by induction on $r$. Let $N$ be such a submodule. There are two cases:
(1) $N$ is not contained in $p (\mathbb{Z}/p^r \mathbb{Z})^{\oplus 2}$. In this case, $N$ is generated by a single element. The number of elements of $(\mathbb{Z}/p^r)^{\oplus 2}$ which generate a submodule of index $p^r$ is $p^{2r} - p^{2r-2}$. Two such elements give the same submodule if their ratio is a unit of $\mathbb{Z}/p^r$; the number of such units is $p^r-p^{r-1}$. So the number of $N$ in this case is $(p^{2r}-p^{2r-2})/(p^r - p^{r-1}) = p^r+p^{r-1}$.
(2) $N$ is contained in $p (\mathbb{Z}/p^r \mathbb{Z})^{\oplus 2}$. In this case, $N$ is an index $p^{r-2}$ submodule of $p (\mathbb{Z}/p^r \mathbb{Z})^{\oplus 2} \cong (\mathbb{Z}/p^{r-1} \mathbb{Z})^{\oplus 2}$. By induction, the number of options for such an $r$ is $p^{r-2} + p^{r-3} + \cdots p+1$.
Adding the two cases together, we are done.

Okay, so what about $2^r$? What one wants to show is that there is only one index $2^{2r}$ ideal in $H$.
I haven't found a ring theory way to do this, but a direct proof isn't hard. Notice that, if $a^2+b^2+c^2+d^2$ is even, then $(a,b,c,d)$ must be integers, and an even number of $(a,b,c,d)$ must be odd. So we can write $a+b+cj+dk = \epsilon + 2 (a' + b'i+c'j+d'k)$ which $\epsilon$ is one of $0$, $1+i$, $1+j$, $1+k$, $i+j$, $i+k$, $j+k$ or $1+i+j+k$. Each option for $\epsilon$ is divisible by $(1+i)$, and we also have $2=(1+i)(1-i)$. So we have shown that, if $a^2+b^2+c^2+d^2$ is even, then $1+i$ divides $a+bi+cj+dk$. By induction, then, $a^2+b^2+c^2+d^2 = 2^r$, then $a+bi+cj+dk$ is a unit times $(1+i)^r$.
A: If you are interested only in Jacobi's formula for odd integers, there is an elementary proof based on the convolution formula $r_4(n)=\sum_{r+s=n}r_2(r)r_2(s)$, due to Dirichlet (Sur l'\'equation $t^2+u^2+v^2+w^2=4m$, J. Maths Pures et Appliqu\'ees 1 (1856), 210-214), and advocated by A. Weil (Sur les sommes de trois et quatre carr\'es (1974), Oeuvres Scientifiques Vol III, Springer-Verlag, 1979). We took this proof in our book with G. Davidoff and P. Sarnak, see section 2.4 of "Elementary number theory, group theory, and Ramanujan graphs", London Math. Soc. Students texts 55, Cambridge Univ. Press, 2003.
A: Added: Thanks to Noam Elkies for pointing out that I mixed up Legendre and Jacobi (j'adresse `a leurs patries respectives mes plus plates excuses): My answer yields only a proof of Legendre's theorem.
A bit of a cheat: Check that it holds for all integers up to 15 and use Conway's fifteen Theorem (https://en.wikipedia.org/wiki/15_and_290_theorems).
