PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (34)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: Very low
[parent] proof of Lagrange's four-square theorem (Proof)

The following proof is essentially Lagrange's original, from around 1770. First, we need three lemmas.

Lemma 1   For any integers $ a,b,c,d,w,x,y,z$,
$\displaystyle (a^2+b^2+c^2+d^2)(w^2+x^2+y^2+z^2)$ $\displaystyle =$ $\displaystyle (aw+bx+cy+dz)^2$  
  $\displaystyle +$ $\displaystyle (ax-bw-cz+dy)^2$  
  $\displaystyle +$ $\displaystyle (ay+bz-cw-dx)^2$  
  $\displaystyle +$ $\displaystyle (az-by+cx-dw)^2.$  

This is the Euler four-square identity, q.v., with different notation.
Lemma 2   If $ 2m$ is a sum of two squares, then so is $ m$.
Proof. Say $ 2m=x^2+y^2$. Then $ x$ and $ y$ are both even or both odd. Therefore, in the identity
$\displaystyle m=\Big(\frac{x-y}{2}\Big)^2 + \Big(\frac{x+y}{2}\Big)^2,$
both fractions on the right side are integers. $ \qedsymbol$
Lemma 3   If $ p$ is an odd prime, then $ a^2+b^2+1=kp$ for some integers $ a,b,k$ with $ 0<k<p$.
Proof. Let $ p = 2n + 1$. Consider the sets
$\displaystyle A:=\lbrace a^2 \mid a=0,1,...,n\rbrace$    and $\displaystyle \quad B:=\lbrace -b^2-1 \mid b=0,1,...,n \rbrace.$
We have the following facts:
  1. No two elements in $ A$ are congruent mod $ p$, for if $ a^2\equiv c^2 \pmod p$, then either $ p\mid (a-c)$ or $ p\mid (a+c)$ by unique factorization of primes. Since $ a-c, a+c \le 2n< p$, and $ 0\le a,c$, we must have $ a=c$.
  2. Similarly, no two elements in $ B$ are congruent mod $ p$.
  3. Furthermore, $ A\cap B=\varnothing$ since elements of $ A$ are all non-negative, while elements of $ B$ are all negative.
  4. Therefore, $ C:=A\cup B$ has $ 2n+2$, or $ p+1$ elements.
Therefore, by the pigeonhole principle, two elements in $ C$ must be congruent mod $ p$. In addition, by the first two facts, the two elements must come from different sets. As a result, we have the following equation:
$\displaystyle a^2+b^2+1=kp$
for some $ k$. Clearly $ k$ is positive. Also, $ p^2 = (2n + 1)^2 > 2n^2 + 1 \ge a^2+b^2+1 = kp$, so $ p > k$. $ \qedsymbol$

Basically, Lemma 3 says that for any prime $ p$, some multiple $ 0<m<p$ of $ p$ is a sum of four squares, since $ a^2+b^2+1=a^2+b^2+1^2+0^2$.

Proof. [Proof of Theorem] By Lemma 1 we need only show that an arbitrary prime $ p$ is a sum of four squares. Since that is trivial for $ p=2$, suppose $ p$ is odd. By Lemma 3, we know
$\displaystyle mp=a^2+b^2+c^2+d^2$
for some $ m,a,b,c,d$ with $ 0<m<p$. If $ m=1$, then we are done. To complete the proof, we will show that if $ m>1$ then $ np$ is a sum of four squares for some $ n$ with $ 1\le n<m$.

If $ m$ is even, then none, two, or all four of $ a,b,c,d$ are even; in any of those cases, we may break up $ a,b,c,d$ into two groups, each group containing elements of the same parity. Then Lemma 2 allows us to take $ n = m/2$.

Now assume $ m$ is odd but $ >1$. Write

$\displaystyle w$ $\displaystyle \equiv$ $\displaystyle a\pmod{m}$  
$\displaystyle x$ $\displaystyle \equiv$ $\displaystyle b\pmod{m}$  
$\displaystyle y$ $\displaystyle \equiv$ $\displaystyle c\pmod{m}$  
$\displaystyle z$ $\displaystyle \equiv$ $\displaystyle d\pmod{m}$  

where $ w,x,y,z$ are all in the interval $ (-m/2, m/2)$. We have
$\displaystyle w^2+x^2+y^2+z^2 < 4\cdot \frac{m^2}{4} = m^2$
$\displaystyle w^2+x^2+y^2+z^2\equiv 0\pmod{m}.$
So $ w^2+x^2+y^2+z^2 = nm$ for some integer non-negative $ n$. Since $ w^2+x^2+y^2+z^2 < m^2$, $ n<m$. In addition, if $ n=0$, then $ w=x=y=z=0$, so that $ a\equiv b\equiv c\equiv d \equiv 0 \pmod m$, which implies $ mp=a^2+b^2+c^2+d^2=m^2q$, or that $ m\vert p$. But $ p$ is prime, forcing $ m=p$, and contradicting $ m<p$. So $ 0<n<m$. Look at the product $ (a^2+b^2+c^2+d^2)(w^2+x^2+y^2+z^2)$ and examine Lemma 1. On the left is $ nm^2p$. One the right, we have a sum of four squares. Evidently three of them
$\displaystyle ax-bw-cz+dy=(ax-bw)+(dy-cz)$
$\displaystyle ay+bz-cw-dx=(ay-cw)+(bz-dx)$
$\displaystyle az-by+cx-dw=(az-dw)+(cx-by)$
are multiples of $ m$. The same is true of the other sum on the right in Lemma 1:
$\displaystyle aw+bx+cy+dz \equiv w^2+x^2+y^2+z^2 \equiv 0\pmod{m}.$
The equation in Lemma 1 can therefore be divided through by $ m^2$. The result is an expression for $ np$ as a sum of four squares. Since $ 0<n<m$, the proof is complete. $ \qedsymbol$

Remark: Lemma 3 can be improved: it is enough for $ p$ to be an odd number, not necessarily prime. But that stronger statement requires a longer proof.



"proof of Lagrange's four-square theorem" is owned by CWoo. [ full author list (3) | owner history (3) ]
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: odd number, expression, product, forcing, implies, interval, parity, groups, squares, sum, multiple, positive, equation, addition, pigeonhole principle, negative, congruent, prime, side, right, fractions, identity, odd, even, sum of two squares, Euler four-square identity, integers
There is 1 reference to this entry.

This is version 10 of proof of Lagrange's four-square theorem, born on 2003-01-04, modified 2008-01-23.
Object id is 3871, canonical name is ProofOfLagrangesFourSquareTheorem.
Accessed 14124 times total.

Classification:
AMS MSC: 11P05 (Number theory :: Additive number theory; partitions :: Waring's problem and variants)
Pending Errata and Addenda
None.
[ View all 4 ]
Discussion
Style: Expand: Order:
forum policy
? by openthedoor754 on 2005-12-24 18:50:28
I do not understand how if
2m=x^2+y^2,
then
m=((x-y)/2)^2+((x+y)/2)^2.
Does anyone want to explain?
[ reply | up ]
  • Re: ? by mathwizard on 2005-12-25 09:27:43
  • Re: ? by Professorpineapple on 2006-02-26 19:43:09
  • Re: ? by intravenous on 2006-05-13 05:59:42

Interact
post | correct | update request | add example | add (any)