Four Squares Theorem

Lecture 22 Four Squares Theorem Pell-Brahmagupta Equation (continued) - x2 − dy 2 = 1, √ 6= d ∈ N, √if (x, y) and (z, w) solutions then x < z ⇒ y < w if and only if x + dy < z + dw. Theorem 78. If (x1 , y1 ) is the least positive solution of x2 −dy 2√= 1 where  6=√d ∈ N, then all positive solutions are given by (xn , yn ) where xn + dyn = (x1 + dy1 )n for n = 1, 2, 3 . . . Proof. First see that (xn , yn ) is a solution. We know that (x1 , y1 ) is a solution x21 − dy12 = 1. √ √ (x1 + dy1 )(x1 − dy1 ) = 1 √ √ xn + dyn = (x1 + dy1 )n √ √ taking conjugates, xn − dyn = (x1 − dy1 )n √ √ √ √ (xn + dyn )(xn − dyn ) = (x1 + dy1 )n (x1 − dy1 )n √ √ √ x2n − dyn = ((x1 + dy1 )(x1 − dy1 ))n = 1n = 1 So (xn , yn ) is indeed a solution. Why are these all the positive solutions? Suppose√ that (s, t) is a positive solution not of the form (x√ n , yn ) for any n. Then s + t d is a positive (> 1) real number. Not that {xn + dyn } is a sequence of positive real numbers which increase to infinity, since  n √ √ xn + dyn = x1 + dy1  | {z } >1 √ √ √ So pick n such that xn + yn d < s√+ t d < xn+1 + yn+1 d. Multiply the sequence of √ inequalities by xn − yn d (it’s a positive real number because it 1 equals xn − dyn = x +√ ). We see dy n n √ √ dyn )(xn + dyn ) √ √ < (xn − dyn )(s + t d) | {z } √ 1 = (xn − a+b d, a,b∈Z √ √ dyn )(xn+1 + dyn+1 ) √ √ = (x1 − dy1 )n (x1 + dy1 )n+1 √ = (x1 + dy1 ) < (xn − 1 and so √ √ 1 < a + b d < x1 + dy1 We’ll see a, b ∈ N, then it will contradict minimality of (x1 , y1 ) √ √ √ 1 √ > 1 and a + b d > 1, so 0 < a − b d < 1 a−b d= a+b d > 0 which means that a ≥ 1. Also, b > a√−1 ≥ d √ 0 ⇒ (a, b) is a positive integer solution. Why is a + b d a solution? √ √ √ √ √ √ (a + b d)(a − b d) = (xn − dyn )(s + t d)(xn + dyn )(s − t d) Adding 1 + 0 < 2a gives a > 1 2 a2 − b2 d = (x2n − dyn2 )(s2 − dt2 ) = 1  P-B equation is quite useful in many diophantine equations. Eg. Putnam asked, can we find infinitely many triples of consecutive integers, each of which is a sum of 2 squares? Yes. Suppose we choose n−1, n, n+1 where we set n = x2 ⇒ n = x2 +02 , n+1 = x2 + 12 , x2 − 1 = n − 1 = sum of 2 squares y 2 + y 2 , so we need to find infinitely many (x, y) such that x2 − 2y 2 = 1. P-B, so ok. Proposition 79. Let N ∈ Z, d ∈ N, d 6= . If x2 − dy 2 = N has one solution, it has infinitely many. √ √ Proof. Let (x1 , y1 ) be a solution, so (x1 + dy1 )(x1 √ − dy1 ) = N √. Let (sn , tn ) be 2 infinitely many solutions to x − dy = 1 ⇒ (s + dt )(s − dtn ) = 1. Then n n n √ √2 √ 2 if we let xn + dyn = (x1 + dy1 )(sn + dtn ) it’s easy to see xn − dyn2 = N and that these are all distinct. So we get infinitely many solutions.  Eg. Prove that n2 + (n + 1)2 is a perfect square for infinitely many values of n. Proof. n2 + n2 + 2n + 1 = 2n2 + 2n + 1 = m2 4n2 + 4n + 2 = 2m2 (2n + 1)2 + 1 = 2m2 Let l be 2n + 1 ⇒ get a solution of l2 + 1 = 2m2 . Conversely, if l2 + 1 = 2m2 then 2 2 2 l is odd, so n = l+1 2 is an integer, and m = n + (n + 1) . (Just want to show 2 2 that l − 2m = −1 has infinitely many solutions. We know it has an obvious solution (l, m) = (1, 1) ⇒ it has infinitely many.)  2 Theorem 80 (Four Squares Theorem). Every non-negative integer is a sum of 4 integer squares. Proof. Just like how we use complex numbers in the proof of the two squares theorem to establish that (a2 + b2 )(c2 + d2 ) = (ac − bd)2 + (ad + bc)2 , we’ll use quaternions now Q = {a + bi + cj + dk : a, b, c, d, ∈ R} i, j, k are ”imaginary” where i2 = j 2 = k 2 = ijk = −1 ji = −k kj = −i ik = −j ij = k jk = i ki = j Multiplication in Q is non-commutative (but associative - x1 (x2 x3 ) = (x1 x2 )x3 , etc). Addition is component-wise. If z = a + bj + cj + dk, define conjugate z = a − bi − cj − dk. Norm is kzk = zz = a2 + b2 + c2 + d2 . Note that zw = w · z. It suffices to check things like −k = k = ij = j · i = (−j)(−i) so kzwk = zwzw = zwwz = z(ww)z = (zz)(ww) = kzkkwk So (a2 + b2 + c2 + d2 )(e2 + f 2 + g 2 + h2 ) = (ae − bf − cg − dh)2 + 3 other similar terms ⇒ product of sum of 4 squares is a sum of 4 squares. So enough to show n is a sum of 4 squares for the case that n = 0, 1, or prime. 0 = 02 + 02 + 02 + 02 , 1 = 12 + 02 + 02 + 02 , 2 = 12 + 12 + 02 + 02 , so enough to show that any odd prime p is a sum of 4 squares. Lemma 81. There’s a positive integer m < p such that mp is a sum of 4 squares. Proof. Recall that if p is an odd prime then x2 + y 2 + 1 = 0 mod p has a solution (by pigeonhole principle). Let’s suppose that we’ve produced x, y mod p so |x|, |y| < p2 . So  p 2 p2 x2 + y 2 + 1 < 2 +1= + 1 < p2 2 2 So x2 + y 2 + 12 + 02 = mp for some 0 < m < p.  Let m be the smallest positive integer such that mp is a sum of 4 squares. We’ve showed m < p. If m = 1 done. So assume m > 1 and we’ll get a contradiction 3 by producing a smaller value of m. If m is even, mp = x2 + y 2 + z 2 + w2 is even, so the number of odd elements of {x, y, z, w} is even. We can pair these up, say, as {x, y} and {z, w} such that x and y have same parity and z, w have same parity, so x+y x−y z+w z−w , , , ∈Z 2 2 2 2  2  2  2  2 x+y x−y z+w z−w x2 + y 2 + z 2 + w2 + + + = 2 2 2 2 2 m = p (decreasing m) 2 So suppose l is some prime dividing m, necessarily odd. Write m = gl, so x2 + y 2 + z 2 + w2 = glp ≡ 0 mod l. Note l < p because l|m, m < p. Reduce x, y, z, w to x0 , y 0 , z 0 , w0 mod l (ie., x ≡ x0 mod l, etc.) such that |x0 |, |y 0 |, |z 0 |, |w0 | < 2l . If x0 , y 0 , z 0 , w0 are all 0, then x, y, z, w are also 0 mod l, and  x 2 l and g l +  y 2 l +  z 2 l +  w 2 l = glp gp = 2 l l < gl = m reducing m. So we may assume x0 , y 0 , z 0 , w0 are not all 0. x + yi + zj + wk = x0 + y 0 i + z 0 j + w0 k mod l Let ρ = x + yi + zj + wk σ = x0 + y 0 i + z 0 i + w 0 k Then kσk = kσk = x02 + y 02 + z 02 + w02 | {z } positive 2 2 ≡ x + y + z 2 + w2 ≡ 0 mod l mod l So it’s a multiple of l, say hl. Since |x|, |y|, |z|, |w| < 2l , x2 + y 2 + z 2 + w 2 < 4  2 l = l2 2 So 0 < h < l. Also ρσ = ρρ mod l ≡ x2 + y 2 + z 2 + w2 = 0 mod l, so the components of 4 quaternion ρσ are all divisible by l. Let β = ρσ l . ρσ l 1 = kρkkσk l 1 = 2 (x2 + y 2 + z 2 + w2 )(x02 + y 02 + z 02 + w02 ) {z } | {z } l | kβk = glp hl (glp)(hl) = l2 = (gh)p Note that m = gl and gh < gl since h < l, so we have a sum of 4 squares which is a smaller multiple of p.  5