# Reference request for a proof of the two-square Theorem

One can show (see below for a sketch of a proof) that every odd prime number $$p$$ can be written in exactly $$(p+1)/2$$ different ways as $$p=a\cdot b+c\cdot d$$ with $$a,b,c,d\in\mathbb N$$ satisfying $$\max(c,d)<\min(a,b)$$.

Example for $$p=23$$: $$\begin{matrix} 1\cdot 23+0\cdot 0 & 23\cdot 1+0\cdot 0 \\ 2\cdot 11+1\cdot 1 & 11\cdot 2+1\cdot 1 \\ 3\cdot 7+1\cdot 2 & 3\cdot 7+2\cdot 1 \\ 7\cdot 3+1\cdot 2 & 7\cdot 3+2\cdot 1 \\ 4\cdot 5+1\cdot 3 & 4\cdot 5+3\cdot 1 \\ 5\cdot 4+1\cdot 3 & 5\cdot 4+3\cdot 1 \end{matrix}$$

Klein's Vierergruppe $$\mathbb V$$ acts on all such quadruplets $$(a,b,c,d)$$ by permuting the first two, permuting the last two, or permuting both the first two and the last two elements. So we get an easy proof that every prime $$p$$ congruent to $$1$$ modulo $$4$$ must be a sum of squares: $$(p+1)/2$$ is then odd and the only fixed points under the action of $$\mathbb V$$ are of the form $$(a,a,c,c)$$.

Does somebody know a reference for this proof? It looks a bit like Zagier's proof which also uses a parity argument for a set acted upon by involutions.

Motivation: This is in fact a variation of Arithmetic properties of positively reduced $2\times 2$-matrices .

Sketch of proof Given a solution $$(a,b,c,d)$$ we consider $$u=(a,c),\ v=(-d,b)$$. We associate to $$(a,b,c,d)$$ the sublattice $$\Lambda=\mathbb Zu+\mathbb Zv$$ of index $$p$$ in $$\mathbb Z^2$$. Suppose now $$cd>0$$ and consider the eight open cones of $$\mathbb R^2$$ defined by the complement of the four lines defined by $$xy(x^2-y^2)=0$$. We colour these open cones alternatingly black and white. The four vectors $$\pm u,\pm v$$ are contained in different black cones (colouring the first cone above the halfline $$(\mathbb R_{>0},0)$$ in black).

We say that a sublattice $$\Lambda$$ of finite index in $$\mathbb Z^2$$ has a monochromatic basis if there exists a basis $$b_1,b_2$$ of $$\Lambda=\mathbb Z b_1+\mathbb Z b_2$$ such that all four elements $$\pm b_1,\pm b_2$$ belong to different open cones of the same colour.

(Not every lattice has a monochromatic basis but many do.)

We claim that all monochromatic bases of a lattice (having a monochromatic basis) are of the same colour: If $$b_1,b_2$$ is a black monochromatic basis and $$w_1,w_2$$ is a white monochromatic basis, then $$w_1,w_2$$ belong to two open adjacent cones of $$\mathbb R^2\setminus(\mathbb Rb_1\cup \mathbb R b_2)$$ which is impossible by the following small Lemma:

Lemma: If $$f_1,f_2$$ and $$g_1,g_2$$ are two bases of a lattice $$\Lambda=\mathbb Z f_1+\mathbb Z f_2=\mathbb Z g_1+\mathbb Z g_2$$ such that $$\{\pm f_1,\pm f_2\}$$ and $$\{\pm g_1,\pm g_2\}$$ do not intersect, then $$g_1,g_2$$ or $$g_1,-g_2$$ are contained in a common connected component of $$\mathbb R^2\setminus(\mathbb R f_1\cup \mathbb R f_2)$$. (Otherwise we have up to sign changes and exchanges of indices $$f_1=\alpha b_1+\beta b_2$$ and $$f_2=\gamma b_1-\delta b_2$$ with $$\alpha,\beta,\gamma,\delta$$ strictly positive integers. This implies that $$b_1$$ belongs to the convex hull of $$(0,0),f_1,f_2$$ which is a contradiction.)

Set now $$\Lambda_\mu=\{(x,y)\in\mathbb Z,\ \vert\ x+\mu y\equiv 0\pmod p\}$$. If $$\mu\in \{2,\ldots,p-2\}$$, then $$\Lambda_\mu$$ contains no elements of the form $$(\pm m,0),(0,\pm m),(\pm m,\pm m)$$ with $$m$$ in $$\{1,\ldots,p-1\}$$. This implies that every open black or white cone contains a point with coordinates of absolute value at most $$p-1$$. A reduction algorithm implies the existence of a monochromatic basis. (Start with two arbitrary non-zero elements $$e_1,e_2$$ of $$\Lambda$$ having coordinates of absolute value smaller than $$p$$ which belong to two different consecutive black cones. If the interior of the convex hull spanned by $$\pm e_1,\pm e_2$$ contains a non-zero element in a black cone, we can replace $$e_1$$ or $$e_2$$ and decrease the area of the convex hull spanned by $$\pm e_1,\pm e_2$$. If the interior contains no non-zero elements of $$\Lambda$$ in black cones, we get either a monochromatic basis or the convex hull contains at least four lattice points in four distinct white cones and we switch the working colour to white.)

Moreover, since $$\Lambda_\mu$$ and $$\Lambda_{p-\mu}$$ differ by a horizontal reflection, they have monochromatic bases of different colours. Retaining only lattices with black monochromatic bases, We get $$(p-2-2+1)/2=(p-3)/2$$ such lattices with black monochromatic bases.

Monochromatic bases of a lattice $$\Lambda_\mu$$ are not unique but in finite number. It remains to show that exactly one black monochromatic basis of a lattice $$\Lambda_\mu$$ has the form $$u=(a,c),v=(-d,b)$$ as required for a solution of $$p=ab+cd$$ (with $$\min(a,b)>\max(c,d)$$ and $$0\leq c,d$$). We call such a basis a reduced monochromatic basis. First observe that every lattice with a black monochromatic basis $$b_1,b_2$$ (where we suppose $$b_1\in\mathbb N^2$$ and $$b_2$$ in $$(-\mathbb N)\times\mathbb N$$) has a reduced black monochromatic basis: Replace $$b_1$$ by $$b_1-kb_2$$ with $$k$$ maximal for monochromaticity. Replace then $$b_2$$ by $$b_2+sb_1$$ with $$s$$ maximal for monochromaticity. The resulting black monochromatic basis is reduced.

Observing that the two lattices $$\mathbb Z(p,0)+\mathbb Z(1,\pm 1)$$ contain no vectors $$u,v$$ (associated to a solution $$(a,b,c,d)$$ such that ...) and adding the two trivial solutions $$(p,1,0,0),(1,p,0,0)$$ (corresponding to the lattices $$\mathbb Z(p,0)+\mathbb Z(0,1)$$ and $$\mathbb Z(1,0)+\mathbb Z(0,p)$$) we get a total number of at least $$(p-3)/2+2=(p-1)/2$$ solutions and we are done after showing that every lattice with a black monochromatic basis contains only one reduced monochromatic basis (also using the fact that sublattices of prime index $$p$$ are in one-to-one correspondence with points of the projective line over $$\mathbb F_p$$).

Supose now that $$u=(a,c),v=(-d,b)$$ is a reduced black basis and let $$u'=(a',c'),v'=(-d',b')$$ be a second reduced black basis giving rise to two distinct solutions $$(a,b,c,d)$$ and $$(a',b',c',d')$$. Since $$u$$ and $$v$$ determine each other uniquely in a reduced black basis, we can assume that $$u'\not=u$$ and $$v'\not=v$$.

The two vectors $$u',v'$$ are thus contained in the four open cones defined by $$\mathbb R^2\setminus(\mathbb R u\cup\mathbb R v)$$.

The lemma used previously shows that they can not belong to two adjacent cones of $$\mathbb R^2\setminus(\mathbb R u\cup\mathbb R v)$$.

We suppose now that $$u',v'$$ belong to $$\mathcal C\cup (-\mathcal C)$$ for $$\mathcal C$$ a cone (onnected component) of $$\mathbb R^2\setminus(\mathbb R u\cup \mathbb R v)$$. If $$u'$$ and $$v'$$ belong to two opposite cones, we exchange the basis $$u,v$$ with the basis $$u',v'$$. We can now assume that both vectors $$u'$$ and $$v'$$ belong to the open cone $$(0,+\infty)u+ (0,+\infty)v$$ spanned by $$u$$ and $$v$$. We have thus $$u'=\alpha u+\beta v$$ and $$v'=\gamma u+\delta v$$ with $$\alpha,\beta,\gamma,\delta$$ strictly positive integers. Reducedness of the black monochromatic basis $$u,v$$ implies that $$v+u$$ is either white or belongs to the black cone $$\mathcal C_u$$ containing $$u$$. If $$u+v$$ is white, we get a contradiction by observing that it is contained in the convex hull of $$(0,0),u',v'$$ (which contains no other points of $$\Lambda$$). The point $$u+v$$ is thus in the black cone $$\mathcal C_u$$ containing $$u$$. Geometric considerations imply now $$\delta\geq 3$$ and the impossible inequalities $$p\geq (3 b+c)a/2>(3ab+ac)/2>ab+a(b+c)/2>ab+cd=p\ .$$

Indeed, since $$u$$ and $$u+v$$ belong both to $$\mathcal C_u$$, the line $$u+\mathbb Rv$$ of slope $$<-1$$ intersects the white cone separating $$\mathcal C_u$$ from the black cone $$\mathcal C_v$$ containing $$v$$ in a segment containing at least one lattice-point of $$\Lambda$$. This implies $$\delta\geq 3$$ and the second coordinate of $$v'$$ is thus at least equal to $$3b+c$$. On the other hand, the first coordinate of $$u'$$ has to be at least equal to the first coordinate of the intersection $$u+\mathbb Rv \cap \mathbb R(1,1)$$ which is $$\geq a/2$$ (since $$v$$ has slope $$<-1$$).

• I learned recently that, although I am sure I have only ever heard Viergruppe, it is apparently Vierergruppe. \\ The not-very-difficult starting fact is too difficult for me. Does it go too far afield to sketch a proof? Oct 5 at 21:47
• As explained by Mathologer, Zagier's proof can be thought of as boiling down to showing that for primes $p \equiv 1\pmod{4}$, the equation $p = x^2 + 4yz$ has an odd number of positive integer solutions $(x,y,z)$. So it seems to be not quite the same proof. You might look at Christian Elsholtz's paper, A combinatorial approach to sums of two squares and related problems, to see if your proof is implicitly in there somewhere. Oct 6 at 1:43
• @LSpice : Viergruppe corrected to Vierergruppe. I have added a slightly sketchy proof. Oct 6 at 6:56
• Regardless of whether new or not, this is a real neat proof, Roland. Oct 6 at 10:16
• A quite recent proof by A. David Christopher (A partition-theoretic proof of Fermat's two squares theorem. Discrete Math. 339 (2016), no. 4, 1410–1411) also splits p into such a sum of products of two factors, $a_1 f_1+ a_2 f_2$. Oct 6 at 15:34