Lagrange's four-square theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Lagrange's four-square theorem, also known as Bachet's conjecture, states that any natural number can be represented as the sum of four integer squares

p = a_0^2 + a_1^2 + a_2^2 + a_3^2\

where the four numbers a_0, a_1, a_2, a_3 are integers. For illustration, 3, 31 and 310 can be represented as the sum of four squares as follows:

3 = 1^2+1^2+1^2+0^2
31 = 5^2+2^2+1^2+1^2
310 = 17^2+4^2+2^2+1^2.

This theorem was proven by Joseph Louis Lagrange in 1770, and corresponds to Fermat's theorem on sums of two squares.

Historical development[edit]

The theorem appears in the Arithmetica of Diophantus, translated into Latin by Bachet in 1621 but was not proven until 1770 by Lagrange.[1]

Adrien-Marie Legendre improved on the theorem in 1798 with his three-square theorem, by stating that a positive integer can be expressed as the sum of three squares if and only if it is not of the form 4^k(8m+7) for integers k and m. His proof was incomplete, leaving a gap which was later filled by Carl Friedrich Gauss. Later, in 1834, Carl Gustav Jakob Jacobi discovered a simple formula for the number of representations of an integer as the sum of four squares with his own four-square theorem.

The formula is also linked to Descartes' theorem of four "kissing circles", which involves the sum of the squares of the curvatures of four circles. This is also linked to Apollonian gaskets, which were more recently related to the Ramanujan–Petersson conjecture.[2]

Proof using the Hurwitz integers[edit]

One of the ways to prove the theorem relies on Hurwitz quaternions, which are the analog of integers for quaternions.[3] The Hurwitz quaternions consist of all quaternions with integer components and all quaternions with half-integer components. These two sets can be combined into a single formula

\alpha = \frac{1}{2} E_0 (1 + \mathbf{i} + \mathbf{j} + \mathbf{k}) +E_1\mathbf{i} +E_2\mathbf{j} +E_3\mathbf{k} = a_0 +a_1\mathbf{i} +a_2\mathbf{j} +a_3\mathbf{k}

where E_0, E_1, E_2, E_3 are integers. Thus, the quaternion components a_0, a_1, a_2, a_3 are either all integers or all half-integers, depending on whether E_0 is even or odd, respectively. The set of Hurwitz quaternions forms a ring; that is to say, the sum or product of any two Hurwitz quaternions is likewise a Hurwitz quaternion.

The (arithmetic, or field) norm \mathrm N(\alpha) of a rational quaternion \alpha is the nonnegative rational number

\mathrm{N}(\alpha) = \alpha\bar\alpha = a_0^2+a_1^2+a_2^2+a_3^2

where \bar\alpha=a_0 -a_1\mathbf{i} -a_2\mathbf{j} -a_3\mathbf{k} is the conjugate of \alpha. Note that the norm of a Hurwitz quaternion is always an integer. (If the coefficients are half-integers, then using modular arithmetic their squares are numbers equivalent to (1\pmod 4)/4, and the sum of four such numbers is an integer.)

Since quaternion multiplication is associative, and real numbers commute with other quaternions, the norm of a product of quaternions equals the product of the norms:

 \mathrm{N}(\alpha\beta)=\alpha\beta(\overline{\alpha\beta})=\alpha\beta\bar{\beta}\bar{\alpha}=\alpha \mathrm{N}(\beta)\bar\alpha=\alpha\bar\alpha \mathrm{N}(\beta)= \mathrm{N}(\alpha) \mathrm{N}(\beta).

For any \alpha\ne0, \alpha^{-1}=\bar\alpha\mathrm N(\alpha)^{-1}. It follows easily that \alpha is a unit in the ring of Hurwitz quaternions if and only if \mathrm N(\alpha)=1.

The proof of the main theorem begins by reduction to the case of prime numbers. Euler's four-square identity implies that if Langrange's four-square theorem holds for two numbers, it holds for the product of the two numbers. Since any natural number can be factored into powers of primes, it suffices to prove the theorem for prime numbers. It is true for 2=1^2+1^2+0^2+0^2. To show this for an odd prime integer p, represent it as a quaternion (p,0,0,0) and assume for now (as we shall show later) that it is not a Hurwitz irreducible; that is, it can be factored into two non-unit Hurwitz quaternions

p=\alpha\beta.

The norms of p,\alpha,\beta are integers such that

\mathrm N(p)=p^2=\mathrm N(\alpha\beta)=\mathrm N(\alpha)\mathrm N(\beta)

and \mathrm N(\alpha),\mathrm N(\beta) > 1. This shows that both \mathrm N(\alpha) and \mathrm N(\beta) are equal to p (since they are integers), and p is the sum of four squares

p=\mathrm N(\alpha)=a_0^2+a_1^2+a_2^2+a_3^2.

If it happens that the \alpha chosen has half-integer coefficients, it can be replaced by another Hurwitz quaternion. Choose \omega = (\pm 1\pm\mathbf{i}\pm\mathbf{j} \pm\mathbf{k})/2 in such a way that \gamma \equiv \omega + \alpha has even integer coefficients. Then

p=(\bar\gamma-\bar\omega)\omega\bar\omega(\gamma-\omega)=(\bar\gamma\omega-1)(\bar\omega\gamma-1).

Since \gamma has even integer coefficients, (\bar\omega\gamma-1) will have integer coefficients and can be used instead of the original \alpha to give a representation of p as the sum of four squares.

As for showing that p is not a Hurwitz irreducible, Lagrange proved that any odd prime p divides at least one number of the form u=1+l^2+m^2, where l and m are integers.[3] This can be seen as follows: since p is prime, a^2\equiv b^2\pmod p can hold for integers a,b, only when a\equiv\pm b\pmod p. Thus, the set X=\{0^2,1^2,\dots,((p-1)/2)^2\} of squares contains (p+1)/2 distinct residues modulo p. Likewise, Y=\{-(1+x):x\in X\} contains (p+1)/2 residues. Since there are only p residues in total, and |X|+|Y|=p+1>p, the sets X and Y must intersect.

The number u can be factored in Hurwitz quaternions:

1+l^2+m^2=(1+l\;\mathbf{i}+m\;\mathbf{j})(1-l\;\mathbf{i}-m\;\mathbf{j}).

The norm on Hurwitz quaternions satisfies a form of the Euclidean property: for any quaternion  \alpha=a_0+a_1\mathbf{i}+a_2\mathbf{j}+a_3\mathbf{k} with rational coefficients we can choose a Hurwitz quaternion  \beta=b_0+b_1\mathbf{i}+b_2\mathbf{j}+b_3\mathbf{k} so that  \mathrm{N}(\alpha-\beta)<1 by first choosing  b_0 so that  |a_0-b_0| \leq 1/4 and then  b_1, b_2, b_3 so that  |a_i-b_i| \leq 1/2 for  i= 1,2,3. Then we obtain

 \mathrm{N}(\alpha-\beta)=(a_0-b_0)^2+(a_1-b_1)^2+(a_2-b_2)^2+(a_3-b_3)^2 \leq \left(\frac{1}{4} \right)^2+\left(\frac{1}{2}\right)^2+\left(\frac{1}{2}\right)^2+\left(\frac{1}{2}\right)^2=\frac{13}{16}<1.

It follows that for any Hurwitz quaternions \alpha,\beta with \alpha \neq 0, there exists a Hurwitz quaternion \gamma such that

\mathrm N(\beta-\alpha\gamma)<\mathrm N(\alpha).

The ring H of Hurwitz quaternions is not commutative, hence it is not an actual Euclidean domain, and it does not have unique factorization in the usual sense. Nevertheless, the property above implies that every right ideal is principal. Thus, there is a Hurwitz quaternion \alpha such that

\alpha H = p H + (1-l\;\mathbf{i}-m\;\mathbf{j}) H.

In particular, p=\alpha\beta for some Hurwitz quaternion \beta. If \beta were a unit, 1-l\;\mathbf{i}-m\;\mathbf{j} would be a multiple of p, however this is impossible as 1/p-l/p\;\mathbf{i}-m/p\;\mathbf{j} is not a Hurwitz quaternion for p>2. Similarly, if \alpha were a unit, we would have

(1+l\;\mathbf{i}+m\;\mathbf{j})H = (1+l\;\mathbf{i}+m\;\mathbf{j})p H+(1+l\;\mathbf{i}+m\;\mathbf{j})(1-l\;\mathbf{i}-m\;\mathbf{j})H \subseteq p H

as p divides 1+l\;\mathbf{i}+m\;\mathbf{j}, which again contradicts the fact that 1/p-l/p\;\mathbf{i}-m/p\;\mathbf{j} is not a Hurwitz quaternion. Thus, p is not Hurwitz irreducible, as claimed.

Generalizations[edit]

Lagrange's four-square theorem is a special case of the Fermat polygonal number theorem and Waring's problem. Another possible generalisation is the following problem: Given natural numbers a,b,c,d, can we solve

n=ax_1^2+bx_2^2+cx_3^2+dx_4^2

for all positive integers n in integers x_1,x_2,x_3,x_4? The case a=b=c=d=1 is answered in the positive by Lagrange's four-square theorem. The general solution was given by Ramanujan. He proved that if we assume, without loss of generality, that a\leq b\leq c\leq d then there are exactly 54 possible choices for a,b,c,d such that the problem is solvable in integers x_1,x_2,x_3,x_4 for all n. (Ramanujan listed a 55th possibility a=1,b=2,c=5,d=5, but in this case the problem is not solvable if n=15.[4])

Algorithms[edit]

Michael O. Rabin and Jeffrey Shallit[5] have found randomized polynomial-time algorithms for computing a single representation n=x_1^2+x_2^2+x_3^2+x_4^2 for a given integer n, in expected running time \mathrm{O}((\log n)^2).

The following piece of Python code returns all possible integers a,b,c,d such that 0\leq a\leq b\leq c\leq d and a^2+b^2+c^2+d^2=n in approximately \mathrm O(n) time:[6]

   def Four_Squares(N):
 
      M = [[] for T in range(N+1)]
         ## Element T of M will be populated with all pairs [a,b] such that a, b < sqrt(N) and a*a + b*b = T
 
      for a in range(0,int(sqrt(N//2)) + 1):
         for b in range(a,int(sqrt(N)) + 1):
            T = a*a + b*b
            if T <= N:
               M[T].append([a,b])
            else:
               break
 
      P = []
         ## P will be populated with all lists [a,b,c,d] such that 0 <= a <= b <= c <= d whose squares sum to N
 
      for i in range(0,N//2 + 1):
         if len(M[N-i]) == 0:
            break
         for j in range(0,len(M[i])):
            for k in range(0,len(M[N-i])):
               X = [M[i][j][0], M[i][j][1],
                    M[N-i][k][0], M[N-i][k][1]]
               if X[1] <= X[2];
                  P.append(X)
 
      return P

Uniqueness[edit]

The sequence of positive integers whose representation as a sum of four squares is unique (up to order) is:

1, 2, 3, 5, 6, 7, 8, 11, 14, 15, 23, 24, 32, 56, 96, 128, 224, 384, 512, 896 ... (sequence A006431 in OEIS).

These integers consist of the seven odd numbers 1, 3, 5, 7, 11, 15, 23 and all numbers of the form 2(4^k),6(4^k) or 14(4^k).

The sequence of positive integers which cannot be represented as a sum of four non-zero squares is:

1, 2, 3, 5, 6, 8, 9, 11, 14, 17, 24, 29, 32, 41, 56, 96, 128, 224, 384, 512, 896 ... (sequence A000534 in OEIS).

These integers consist of the eight odd numbers 1, 3, 5, 9, 11, 17, 29, 41 and all numbers of the form 2(4^k),6(4^k) or 14(4^k).

See also[edit]

References[edit]

  1. ^ Ireland and Rosen (1990). A Classical Introduction to Modern Number Theory. Springer-Verlag. ISBN 0-387-97329-X. 
  2. ^ The Ramanujan Conhecture and some Diophantine Equations, Peter Sarnak, lecture at Tata Institute of Fundamental Research, of the ICTS lecture series. Bangalore, 2013 via youtube.
  3. ^ a b Stillwell J (2003). Elements of Number Theory. New York: Springer-Verlag. pp. 138–157. ISBN 0-387-95587-9. 
  4. ^ Myung-Hwan Kim REPRESENTATIONS OF BINARY FORMS BY QUINARY QUADRATIC FORMS
  5. ^ M. O. Rabin, J. O. Shallit, Randomized Algorithms in Number Theory, Communications on Pure and Applied Mathematics 39 (1986), no. S1, pp. S239–S256. doi:10.1002/cpa.3160390713
  6. ^ http://cs.stackexchange.com/questions/2988/how-fast-can-we-find-all-four-square-combinations-that-sum-to-n

External links[edit]