Print Story Halving sums of squares
Diary
By Alan Crowe (Thu Apr 23, 2009 at 05:10:28 PM EST) fermat (all tags)

My previous diary entry concerned multiplying the sums of squares. Now I try to go the other way, factoring sums of squares. Since this is harder I make little progress, but make an interesting detour to visit the quarter-square multiplier.



Given natural numbers x and y both expressed as the sums of squares of two natural numbers x=a²+b² and y=c²+d² we may wonder about the product. Must there be two more natural numbers e and f such that xy= e²+f²? Yes.

xy = (a²+b²)(c²+d²)
=a²c² +a²d² +b²c² +b²d²
=a²c² -2abcd +b²d² +a²d² +2abcd +b²c²
=(ac-bd)² +(ad+bc
What about going the other way? If a number is the sum of two squares, must its factors also be the sums of two squares?

There are some definite noes such as 45 = 6²+3². When we split it, 45 = 3×15 we see that neither factor is the sum of two squares. But there are lots of yesses for example 40

  • 1×40=(1²+0²)(6²+2²)
  • 2×20=(1²+1²)(4²+2²)
  • 4×10=(2²+0²)(3²+1²)
  • 5×8=(2²+1²)(2²+2²)
It is nearly true and we have to wonder what is going on with the exceptions.

Nearly true is a slippery concept. I'm going to try to nibble off a little part of the problem, which I think I can prove. If an even number is the sum of two squares, 2n=a²+b² then obviously the first factor, the two, is the sum of two squares. I think that the second factor, the n is also the sum of two squares

Now for a little digression to one of my favourite bits of algebra, the quarter-square multiplier. Thirty years ago, an ordinary computer multiplied numbers by shifting and adding. If you were designing special computers for doppler radars for fast jet fighters this was too slow. Could one design a big circuit with lots of AND and OR gates that would do the multiplication in one go? It seemed to need an awful lot of AND and OR gates. Large programmable read only memories were starting to become available. What about a look up table? If you wanted to multiply n bit numbers you would need a look up table with 2n address bits. That was too many. If you just wanted to look up squares of numbers you only had 2n entries, which was possible. That raised the question: what really is the difference between squaring and multiplying? Was there any way to use a table of squares to do multiplication?

(a+b)²=a²+2ab+b²
(a-b)²=a²-2ab+b²
Subtracting
(a+b)²-(a-b)² = 4ab
ab = ¼{(a+b)²-(a-b)²}
That may be familiar as the polarization identity on inner product spaces.

Now I'm going to mess up the derivation, adding when I'm supposed to subtract. In school getting it wrong is always bad. In real life it is sometimes interesting. When I add it is the cross terms, 2ab, that cancel not the squares.

(a+b)²+(a-b)² =2a²+2b²
a²+b² =½(a+b)² +½(a-b
so if we have say 45=6²+3² we also have
45 = ½(6+3)²+½(6-3)²=40½+4½
which is a bit useless, even for pure mathematics.

Undaunted we look at even numbers that are the sum of two squares. Now the sum of an even number and an odd number is always odd so if 2n=a²+b² then either both a² and b² are even or both a² and b² are odd.

Squaring a generic odd number (2r+1)²=4r²+4r+1 we get one more than a multiple of four, which is undoubtably odd. Since the square of an odd number is odd, an even square is not the square of an odd number. Since the square of an even number is even, an odd square is not the square of an even number. We can sumarise thus

is even ⇒ a is even
is odd ⇒ a is odd
This lets us strip out the squaring from our analysis of 2n. If 2n=a²+b² then either both a and b are even or both a and b are odd. Either way both a+b and a-b are even, so their squares are even and our halves are whole numbers

It is not immediately obvious what this gives us. 74 = 7²+5² = ½(7+5)²+½(7-5)²= ½12²+½2². We have taken an even number that is the sum of two squares and expressed it as the average of two squares. So what?

The missing insight is that 2 is a prime number. If it divides a product it divides one or other factor. If it divides a square, dividing one factor implies dividing the other. 2|a² ⇒ 2|a ⇒ 4|a² We can write

½(a²+b²) = ¼(a+b)²+¼(a-b
=(½(a+b))²+(½(a-b))²
When we see that the sum of two squares is even we know that we can half it and still have a sum of two squares. ½74=37=6²+1²

That seems like a good place to stop for the week. I've already seen that there is trouble with three. What about five? If 5n is a sum of two squares is n the sum of two squares? It seems to work quite well. Even 45 works. Dividing out the 5 leaves 9 = 3²+0². Also 65 = 5 × (3²+2²) but from skimming my book I know there is trouble ahead. Exercise for the reader: find it.

< Positive/Negative | Early in the morning >
Halving sums of squares | 0 comments ( topical, 0 hidden) | Trackback