``` wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi) riddles >> putnam exam (pure math) >> Integers as sums of two squares (Message started by: Michael Dagg on Sep 15th, 2009, 4:06pm) ``` Title: Integers as sums of two squares Post by Michael Dagg on Sep 15th, 2009, 4:06pm Suppose   a_1 < a_2 < a_3 < ...  are the distinct positive integers expressible as sums of two squares of integers.  Show that for any givenpositive integer  d  the equality  a_{n+1} - a_n = d holds for infinitely many  n  . Title: Re: Integers as sums of two squares Post by Eigenray on Sep 15th, 2009, 9:24pm If d = 2k+1 = (k+1)2-k2 is odd, we can proceed as follows:Let us consider the numbers a with k2 < a < (k+1)2, one at a time.Since a is not a square, we can show using quadratic reciprocity and Dirichlet's theorem that there are infinitely many primes p such that p = 3 mod 4 and  -a is a non-zero quadratic residue mod p.  Pick such a prime distinct from the ones chosen for the other values of a.Now, p | n2+a for precisely 2 values of n mod p.  By Hensel's lemma, there are precisely 2 value of n mod p2 for which p2 | n2+a.  So there are 2p-2 > 0 values of n mod p2 for which n2+a is divisible by p but not p2, and therefore it is not the sum of two squares.Now by the Chinese remainder theorem, there are infinitely many n such that n2+k2+1, ..., n2+(k+1)2-1 are not sums of two squares, while n2+k2 and n2+(k+1)2 obviously are.If d = 4k+2, we can do the same thing for the interval (2n2+2k2, 2n2+2(k+1)2): if 2k2 < a < 2(k+1)2, then 2a is not a square so we can find infinitely many primes p with p = 3 mod 4 and -2a a square mod p, and therefore a whole congruence class mod p2 for which 2n2+a is divisible by p but not p2.But for d divisible by 4 I don't know.  I'm not even sure how to handle d = 4 .... Title: Re: Integers as sums of two squares Post by Eigenray on Sep 16th, 2009, 3:43pm The case where d is divisible by 4 follows from Dickson's conjecture (or more generally Schinzel's hypothesis H) at least:Pick (d-1) distinct primes p1,...,pd-1, all congruent to 3 mod 4, and such that pi does not divide i(d-i).  Pick an integer a such that:a=1 mod 4;  a = pi - i   mod pi2,and setm = 4http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif pi2.The condition on the pi guarantees that (a,m) = (a+d,m) = 1.  This implies that the polynomialsf(n) = mn + a,  g(n) = mn + a+dare such that f*g has no fixed divisor: f*g is always odd, and for a prime p > 2, f,g each have at most one root mod p.  So by Dickson's conjecture, there are infinitely many n such that p = f(n) and q = g(n) are both prime.  Since p and q=p+d are both 1 mod 4, they are sums of two squares.  But for 0 < i < d, p+i = mn+a+i = pi mod pi2, and is therefore not the sum of two squares. Title: Re: Integers as sums of two squares Post by Michael Dagg on Oct 4th, 2009, 3:06pm What I did seems to be too long for one post. So I'll work with the odd d here.Let's write,  "each  s_i  is an  S2S ."The proof gets a little convoluted, so let me start with an example,say  d=5. That is, we need to find infinitely many integers  x  such that x  and x+5  are each a sum of two squares x+1, x+2, x+3, and  x+4  are not.Since  5 = 3^2 - 2^2, let's try looking for  x's  of the formx = y^2 + 2^2 : then obviously both  x  and  x+5 = y^2 + 3^2are sums of two squares.  So we need only find these  x  so thatnone of the intervening four integers is a S2S.One characterization of numbers  n  that are not S2S'sis that they have some prime factor  p  such that (a)  p = 3 mod 4 (b)  p  divides  n  to an odd degree.And one way to ensure THAT is to have  n = p mod p^2  for some such  p.So for example,  x+1 = y^2+5  is not a S2S  if  y^2+5  is congruentto  3 mod 9, i.e. if  y^2 = 7 mod 9. That happens iff  y = +- 4 mod 9.Similarly:x+2 = y^2+6 is not a S2S if y^2+6 =  7 mod  49, i.e. if y = +- 1 mod 49.x+3 = y^2+7 is not a S2S if y^2+7 = 11 mod 121, i.e. if y = +- 2 mod 121.x+4 = y^2+8 is not a S2S if y^2+8 = 19 mod 361, i.e. if y = +- 159 mod 361.So we need only use the Chinese remainder theorem to find a  y  with e.g. y=4 mod 9,  y=1 mod 49,  y=2 mod 121,  y=159 mod 361  .Of course these exist; any  y = 3719542 mod (3.7.11.19)^2  will do.So we have infinitely many choices for  y, and for each of them,we can set  a_n = x = y^2+4  and  a_{n+1} = x+5 = y^2+9 .Now, how close is this method to being a general proof, valid for otherodd  d?  If, say,  d=2k+1, then  d = (k+1)^2 - k^2. It followsthat for any integer  x,  both  x^2 + k^2  and  x^2 + (k+1)^2  are  S2S.We must prove that no intermediate numbers are also S2S.  As above, weneed only find, for each of them, a distinct prime  p=3 mod 4  for whichthere are congruences classes (mod p^2) of integers  x  havingx+k^2+i = p mod p^2.  So let's noteLemma: Suppose  A  is an integer and  P  is an odd prime.Then the solutions to the congruence  X^2 = A mod P^2  are- {X= 0, P, 2P, ... P^2-P} mod P^2,  if A = 0 mod P^2- none, if  A  is any other multiple of P  mod P^2- exactly 2, if  A  is any other quadratic residue mod  P- none, if  A  is any other quadratic nonresidue mod  PCorollary:  The congruence  x+k^2+i = p mod p^2  hassolutions if  -(k^2+i)  is a nonzero quadratic residue mod pIn our problem we would try to solve a set of such congruences,and  k^2+i  would be less than  (k+1)^2.  So -(k^2+i) is certainlynonzero mod  p  as long as  p > (k+1)^2 = ( (d+1)/2 )^2.For p=3 mod 4,  -(k^2+i)  is a residue iff  k^2+i  itselfis a nonresidue, i.e.  iff the Legendre symbol ( k^2+i | p ) = -1 .Well, write  k^2+i = s^2 q1 q2 q3 ...  (q_i = prime divisors of thesquarefree part of  k^2+i ), this Legendre symbol equals \prod (q_j | p) = \prod ( p | q_j ).(-1)^{(q_j - 1)/2}by quadratic reciprocity. The actual value of this last expressionis not of much interest to us except to note that its value dependsonly on the congruence class of  p  modulo  q1 q2 ..., and thathalf of those congruence classes make the Legendre symbolequal 1 and half make it equal -1.  Therefore by (a different!)application of the Chinese Remainder Theorem, and then Dirichlet'stheorem, there will be infinitely many primes  p=3 mod 4such that  -(k^2+i)  is a nonzero quadratic residue mod  p .That means that for each value of  i  in the proof above,we WILL be able to find a new prime  p = 3 mod 4  (larger than((d+1)/2)^2 ) for which  X^2 + (k^2+i) = p mod p^2  is solvable.To return for illustration to my example, we need to examinethis situation for  k=2  and  i=1,2,3,4, i.e. for  k^2+i =5,6,7,8 . The squarefree parts of these are, respectively,5, 2.3, 7, 2 .-- (5|p) = -1  iff  (p|5) = -1  i.e. iff p=2 or 3 mod 5 ;   we also need  p=3 mod 4, so the primes that will do   for us are those congruent to  3 or 7  mod 20. I used p=3.-- (2|p)(3|p)=-1  iff  (-1)^{(p^2-1)/8} . (p|3)(-1)^{(p-1)/2} = -1,   i.e. iff (p|3) =  +1, when p = 5 or 7 mod 8  and  -1  otherwise.   This is true (for p=3 mod 4) iff  p = 7 or 11  mod 24.  I used p=7 .-- (7|p) = -1  iff  (p|7) = (-1)^{(p+1)/2}, i.e. iff  p=1,2,4 mod 7   (and p=3 mod 4). We can use any  p=11,15,23 mod 28;  I used p=11.-- (2|p)=-1  iff  p = 3 or 5 mod 8; to have p=3 mod 4 we need   p=3 mod 8. I used p=19.The point of these exercises is to show several kinds of cases underwhich we can compute the relevant possibilities for  p , and tonote that there ARE always solutions. And there will indeed alwaysbe solutions, as long as there is at least one prime  q_j  dividing(k^2+i)/r^2,  i.e. as long as  k^2+i  is not a perfect square.But indeed the smallest positive value of  i  such that  k^2+i  issquare is  i=2k+1,  and we will only consider smaller values of  i.So we will indeed be able to arrange for enough primes  p  for every  i.(This long-winded paragraph was written after I attempted tostart my illustration not with  5 = 3^2 - 2^2  but rather with15 = 4^2 - 1^2.  The fact that  1  and  16  are not CONSECUTIVEsquares messed things up.)So the "magic" part of the proof for  d=5  can always be accomplished:we can find enough primes to show that each intervening integerx+1, x+2, ..., x+(d-1)  is not a sum of two squares. Title: Re: Integers as sums of two squares Post by Michael Dagg on Oct 4th, 2009, 3:07pm For even  d, let's look for the lower S2S of the form  (y+s)^2+y^2  andthe upper S2S of the form  (y+s+1)^2+(y-1)^2 . These differ by  2s+2 .So in order to keep the intervening integers from being S2S, we want tosee whether we can find enough primes  p=3 mod 4 for which   (y+s)^2+y^2 + i = p_i mod (p_i)^2,    i=1, 2, ..., 2s-1 .Multiply by  2  (that's invertible!)  and the equation becomes (4y +s)^2 = 2 p_i - ( s^2 + 2i )  mod (p_i)^2As I noted last time, this is solvable as long as  -(s^2+2i)  isa nonzero quadratic residue mod  p_i.  By exactly the samereasoning as last time, this will be true for whole congruenceclasses (which thus contain infinitely many primes  p_i)  aslong as  s^2+2i  is not a perfect square.  Well, s^2+2i > s^2,and  s^2+2i  has the same parity as  s^2 ; the next largestsquare after  s^2  having the same parity is  (s+2)^2 =s^2 + 2(2s+2) > s^2 + 2i , so we won't hit any perfect squares.So for example, to get gaps of length 6, let s=2: a_n  =  x  = (y+2)^2 +  y^2  is a S2S a_{n+1} = x+6 = (y+3)^2 + (y-1)^2 is a S2Sbut x+1 =  7 mod  7^2 if y=  9 mod  7^2 (or use any p=7,11 mod 24) x+2 =  3 mod  3^2 if y=  1 mod  3^2 (or use any p=3 mod 8) x+3 = 11 mod 11^2 if y= 26 mod 11^2 (or use any p=7,11,19,23 mod 40) x+4 = 19 mod 19^2 if y=109 mod 19^2 (or use any p=7 mod 12) x+5 = 23 mod 23^2 if y=216 mod 23^2 (or use any p=3,15,19,23,27,39 mod 56)so these are not S2S's, as long as  y = 4525213807  mod (3.7.11.19.23)^2.In other words, you'll get a gap of exactly 6 whenevera_n = (y+2)^2+y^2 =   40955120016227721730 + 184453087310820554688 K + 207684298111031164962 K^2for any  K . Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board