Chaitanya's Random Pages

June 18, 2011

More on the sums of squares

Filed under: mathematics — ckrao @ 1:49 pm

In my previous mathematical post I took a look at the classical result that an odd prime can be written as the sum of two squares if and only if it is 1 modulo 4. One of the proofs used unique factorisation in the Gaussian integers, and this approach in fact shows that the prime’s representation as the sum of two squares is unique (up to sign and ordering). As an example, take p = 13. In the Gaussian integers its factors (3 + 2i) and (3 – 2i) are irreducible since their norm 13 is prime. To see this, if 3+2i = ab where a and b are Gaussian integers each with norm > 1, then taking norms of both sides leads to a contradiction that a prime number is the product of two integers greater than 1. Hence 3+2i (and similarly 3-2i) is irreducible. (By unique factorisation, the factors are also prime.) Hence 13 only factors as (3+2i)(3-2i) (up to multiplication by units) leading to the unique representation 13 = 3^2 + 2^2.

If we want to find representations of a number as the sum of two squares we can factorise it in the Gaussian integers, and then separate the factors into two piles so that a factor and its complex conjugate are not in the same pile. Then multiply out the factors in each pile. If there are many factors, then many ways of forming the piles may be possible. If however you see powers of 2, there is no need to permute its factors (1+i) and (1-i) as the difference between multiplication by (1+i) and by (1-i) is simply a 90 degree rotation in the complex plane.

To illustrate this, suppose we wish to write 130 as the sum of two squares in all possible ways.

Firstly we have

\begin{array} {lcl} 130 = 2.5.13 &=& (1+i)(1-i)(2 + i)(2-i)(3+2i)(3-2i)\\ &=& [(1+i)(2+i)(3+2i)][(1-i)(2-i)(3-2i)]\\ &=& (-3 + 11i)(-3-11i)\\ &=& 3^2 + 11^2.\end{array}

Then if we try

2.5.13 = [(1-i)(2+i)(3+2i)][(1+i)(2-i)(3-2i)] = (11 + 3i)(11-3i) = 11^2 + 3^2,

we arrive at the same solution as before.

Instead anchor the (1-i), (1+i) factors and permute the others. There is only one other possibility in this example:

2.5.13 = [(1+i)(2-i)(3+2i)][(1-i)(2+i)(3-2i)] = (7 + 9i)(7 - 9i) = 7^2 + 9^2

This helps explain the formula for the number of ways that n can be decomposed into the sum of two squares (given at the end of the previous related post) and why it did not depend on the power of 2 in its prime factorisation. It can be shown that the number of ways of writing n = a^2 + b^2 with a > 0, b \geq 0 is also given by the interesting formula

\displaystyle \sum_{\substack {d|n\\ d \equiv 1 \bmod 4}} 1 - \sum_{\substack {d|n\\ d \equiv 3 \bmod 4}} 1 .

That is, it is the number of divisors of n congruent to 1 modulo 4 minus those congruent to 3 modulo 4. See [1, p279] for a proof using Dirichlet multiplication, but try proving it yourself first if interested.

Going beyond a^2 + b^2

The above factorisation idea can be used when writing a positive integer n in the form a^2 + 2b^2 or a^2 + 3b^2. Instead of working in the Gaussian integers, we now factorise n in the rings \mathbb{Z}[\sqrt{-2}] or \mathbb{Z}[\omega = e^{2\pi i /3}] (the Eisenstein integers consisting numbers of the form a + b\omega) respectively. The identity (a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2 (multiplication in \mathbb{Z}[i]) generalises to

\displaystyle (a^2 + kb^2)(c^2 + kd^2) = (ac - kbd)^2 + k(ad + bc)^2    (multiplication in \mathbb{Z}[\sqrt{-k}]).

Hence it is enough to decompose n into a product of primes and then rearrange terms as before. For example 99 can be written in the form x^2 + 2y^2 in three ways (ignoring sign), since

\begin{array}{lcl}99 = 3^2.11 &=& (1 + \sqrt{-2})^2 (1 - \sqrt{-2})^2(3 + \sqrt{-2})(3 - \sqrt{-2})\\&=&[(1 + \sqrt{-2})^2(3 + \sqrt{-2})][(1 + \sqrt{-2})^2(3 + \sqrt{-2})] = (-7 + 5\sqrt{-2})(-7 - 5\sqrt{-2}) = 7^2 + 2.5^2\\&=&[3(3 + \sqrt{-2})][3(3 - \sqrt{-2})] = 9^2 + 2.3^2\\&=&[(1 + \sqrt{-2})^2(3 - \sqrt{-2})][(1 - \sqrt{-2})^2(3 + \sqrt{-2})] = (1+ 7 \sqrt{-2})(1-7\sqrt{-2}) = 1^2 + 2.7^2.\end{array}

It turns out that a prime p can be written in the form a^2 + 2b^2 if and only if p=2 or p is congruent to 1 or 3 modulo 8. Also a prime can be written in the form a^2 + 3b^2 if and only if p = 3 or p is congruent to 1 modulo 6. Factorisation in the Eisenstein integers can also be used to show that a prime can be written in the form a^2 + ab + b^2 if p is congruent to 1 modulo 3. The representation is not unique, since if (a,b) is a solution, so is (-a, a+b) or (a+b, -b) (and with their signs reversed). However, if these types of solutions are regarded as equivalent, then the solution is unique.

For similar results, see [2].

The factorisation method cannot be applied more generally to finding representations of the form a^2 + kb^2. We know that if a prime divides x^2 + y^2 or x^2 + 2y^2, then it necessarily has this form. However this is not true for x^2 + 5y^2 (e.g. 3 divides 21 = 1^2 + 5.2^2 but 3 is not of the form x^2 + 5y^2). The lack of unique factorisation in \mathbb{Z}[\sqrt{-5}] (for example 6 = 2.3 = (1 + \sqrt{-5})(1 + \sqrt{-5})) results in things breaking down.

In general, finding whether a prime can be written in the form p = a^2 + kb^2 (assuming p is odd and is not a factor of the discriminant of p) is equivalent to the following two conditions being satisfied:
(i) -k is a quadratic residue modulo p,
(ii) a polynomial congruence f(a) \equiv 0 \bmod p is satisfied modulo p. (It is also required that p is not a divisor of the discriminant of the polynomial f.)

To prove this for all k requires some high-powered maths (i.e. class field theory, then complex multiplication and modular functions to construct f). Condition (i) results from the fact that

a^2 + kb^2 \equiv 0 \bmod p  implies (a/b)^2 \equiv -k \bmod p.

In the above simpler cases, for k = 2 and 3 only condition (i) is needed (the modulo 8 and modulo 6 results follow from quadratic reciprocity), while for k=27 for example, it turns out that f(x) = x^3 - 2. See [3] for further details.

Further notes:

  • It is known that if c and d are given natural numbers, there is at most one representation of the prime p in the form cx^2 + dy^2 where x and y are natural numbers. A proof may be found in [4].
  • If n is large, there are non-brute-force computational algorithms for solving the Diophantine equation cx^2 + dy^2 = n, for example Cornacchia’s algorithm and the Hardy-Muscat-Williams algorithm [5].

The sum of squares is a special case of a binary quadratic form, about which there is a wealth of theory which I hope to learn to some extent in the coming months.

References and further reading

[1] K. Ireland, M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, 1990.

[2] Weisstein, Eric W. “Diophantine Equation–2nd Powers.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/DiophantineEquation2ndPowers.html

[3] D. A. Cox, Primes of the form x² + ny², John Wiley & Sons, 1989.

[4] http://math.stackexchange.com/questions/33125/factoring-numbers-of-the-binary-quadratic-form-in-two-different-ways

[5] K. Hardy, J. B. Muskat, K. Williams, A deterministic algorithm for solving n = ƒu² + gv² in coprime integers u and v, Math. Comp. 55 (1990), 327-343. Available here in pdf form.

[6] Q. Yuan, Annoying Precision blog entries: (1) From Gauss to Eisenstein,  (2) Three approaches to sums of squares

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: