Tag Archives: sum of squares

Sum of squares

Standard

In the past few posts, I have talked about representing integers as a sum of squares:

In this post, I would like to state Lagrange’s four-square theorem following section 6.4 of Niven-Zuckerman-Montgomery’s An introduction to the theory of number.

Firstly, by applying Hensel’s lemma to the result from the earlier post we get (Theorem 5.14):

Proposition: Let a,b,c be arbitrary integers. Then the congruence ax^2+by^2+cz^2\equiv 0\pmod{p} has a non-trivial solution modulo any prime p.

The theorem stated in the earlier post establishes that there is no need for any condition modulo primes p not dividing abc. The above proposition, application of Hensel’s lemma, just demonstrates it more explicitly by telling that the equation is solvable everywhere locally (i.e. modulo every prime).

Secondly, we need following result from Geometry of numbers (Theorem 6.21):

Minkowski’s Convex Body Theorem for general lattices: Let A be a non-singular n\times n matrix with real elements, and let \Lambda = A\mathbb{Z}^n=\{A\mathbf{s}\in \mathbb{R}^n: \mathbf{s}\in \mathbb{Z}^n\} be a lattice. If \mathcal{C} is a set in \mathbb{R}^n that is convex, symmetric about origin \mathbf{0}, and if \text{vol}(\mathcal{C})> 2^n |\det(A)|, then there exists a lattice point \mathbf{x}\in\Lambda such  that \mathbf{x}\neq 0 and \mathbf{x}\in \mathcal{C}.

Now we are ready to state the theorem (for the proof see Theorem 6.26):

Lagrange’s four-square theorem: Every positive integer n can be expressed as the sum of four squares, n=x_1^2+x_2^2+x_3^2+x_4^2, where x_i are non-negative integers.

Advertisements

Happy Birthday Ramanujam

Standard

Today is 129th birthday of Srinivasa Ramanujam Iyengar. Let’s see some properties of the number 129:

♦  It is sum of first ten prime numbers. [Tanya Khovanova’s “Number Gossip”]

\displaystyle{2+3+5+7+11+13+17+19+23+29 = 129}.

♦  It is the smallest number that can be written as the sum of 3 squares in 4 ways. [Erich Friedman’s “What’s Special About This Number?”]

\displaystyle{11^2+2^2+2^2 = 10^2+5^2+2^2 = 8^2+8^2+1^2 = 8^2+7^2+4^2 = 129}.

Though the first property appears like a coincidence (to me!), but the second fact is connected to a well-known theorem in number theory.

Legendre’s three-square theorem: A non-negative integer n can be represented as sum of three squares of integers if and only if n is NOT of the form 4^a (8b+7) for some integers a and b.

Therefore, to make sure that a number can be written as sum of three squares or not, we just need to check its divisibility with 4 and 8. Since 129 is a small number (and a multiple of 3) we can easily factorize it as 129 = 3 \times 43.  Now, since 4 is not a factor, we get a=0 and just need to check 8b+7= 129 = 8\times 16 + 1, but no integer b can satisfy this condition. Completing the verification of our example.

It’s not difficult to prove that no integer n=4^a(8b+7) can be sum of three squares. But, it’s difficult to prove the converse of this statement. Till now I didn’t know the complete proof of this theorem. Interestingly, the two available proofs use some deep results like:

◊  quadratic reciprocity law + Dirichlet’s theorem on arithmetic progressions + equivalence class of the trivial ternary quadratic form.

◊  quadratic reciprocity law + Minkowski’s theorem on lattice points contained within convex symmetric bodies + Fermat’s theorem on sums of two squares

I would prefer proving this result using second approach, since proving Dirichlet’s theorem is very difficult (as compared to the main theorem we wish to prove). The proof using second approach was given by Nesmith . C. Ankeny, in  “Sums of Three Squares,” Proceedings of the American Mathematical Society, vol. 8, no. 2, p. 316, Apr. 1957. Also, note that Ankeny prove the three-square theorem only when n is square-free because it’s easy to prove that

Lemma: If an integer is a sum of squares of three positive integers, so is its square.

For proof see this article by Alexander Bogomolny, “Sum of Three Squares” from Interactive Mathematics Miscellany and Puzzles

Now, what remains to determine is the number of ways we can write a non-negative integer which satisfies Legendre’s three-square theorem as sum of three squares. Interestingly, this is a research level problem if we are talking about a formula to calculate the number of presentations of a given number as sum of three squares. Indeed, there is a (very long) paper by Paul T. Bateman titled “On the Representations of a Number as the Sum of Three Squares”, Transactions of the American Mathematical Society, Vol. 71, No. 1 (Jul., 1951), pp. 70-101. Though I didn’t have patience to read this paper, this MathOverflow discussion gives an overview of the Sum of Squares Function. The output of this function is available as A005875: Number of ways of writing a nonnegative integer n as a sum of 3 squares (zero being allowed) but it is useless since it counts the “tuples”. For example, 129 can be represented by 144 =  (3+6+6+3)8 tuples because we are allowed to replace positive by negative integers before squaring them (hence multiplied by 8).

So, we will have to “manually” check the number of ways we can write the non-negative integers less than 129 as sum of three squares (A000408: Numbers that are the sum of three nonzero squares). As of now, I don’t know how to find the distinct representations. Will try to answer this question in future.