wu :: forums
« wu :: forums - Integers as sums of two squares »

Welcome, Guest. Please Login or Register.
Nov 26th, 2021, 4:07pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Icarus, Grimbal, Eigenray, SMQ, william wu, towr)
   Integers as sums of two squares
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Integers as sums of two squares  (Read 8599 times)
Michael Dagg
Senior Riddler
****






   


Gender: male
Posts: 500
Integers as sums of two squares  
« on: Sep 15th, 2009, 4:06pm »
Quote Quote Modify Modify

Suppose   a_1 < a_2 < a_3 < ...  are the distinct  
positive integers expressible as sums of two  
squares of integers.  Show that for any given
positive integer  d  the equality  
 
a_{n+1} - a_n = d  
 
holds for infinitely many  n  .
« Last Edit: Sep 15th, 2009, 4:09pm by Michael Dagg » IP Logged

Regards,
Michael Dagg
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Integers as sums of two squares  
« Reply #1 on: Sep 15th, 2009, 9:24pm »
Quote Quote Modify Modify

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 ....
« Last Edit: Sep 15th, 2009, 9:56pm by Eigenray » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Integers as sums of two squares  
« Reply #2 on: Sep 16th, 2009, 3:43pm »
Quote Quote Modify Modify

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 set
 
m = 4 pi2.
 
The condition on the pi guarantees that (a,m) = (a+d,m) = 1.  This implies that the polynomials
 
f(n) = mn + a,  g(n) = mn + a+d
 
are 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.
IP Logged
Michael Dagg
Senior Riddler
****






   


Gender: male
Posts: 500
Re: Integers as sums of two squares  
« Reply #3 on: Oct 4th, 2009, 3:06pm »
Quote Quote Modify Modify

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 form
x = y^2 + 2^2 : then obviously both  x  and  x+5 = y^2 + 3^2
are sums of two squares.  So we need only find these  x  so that
none of the intervening four integers is a S2S.
 
One characterization of numbers  n  that are not S2S's
is 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 congruent
to  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 other
odd  d?  If, say,  d=2k+1, then  d = (k+1)^2 - k^2. It follows
that 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, we
need only find, for each of them, a distinct prime  p=3 mod 4  for which
there are congruences classes (mod p^2) of integers  x  having
x+k^2+i = p mod p^2.  So let's note
 
Lemma: 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  P
 
Corollary:  The congruence  x+k^2+i = p mod p^2  has
solutions if  -(k^2+i)  is a nonzero quadratic residue mod p
 
In 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 certainly
nonzero 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  itself
is 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 the
squarefree 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 expression
is not of much interest to us except to note that its value depends
only on the congruence class of  p  modulo  q1 q2 ..., and that
half of those congruence classes make the Legendre symbol
equal 1 and half make it equal -1.  Therefore by (a different!)
application of the Chinese Remainder Theorem, and then Dirichlet's
theorem, there will be infinitely many primes  p=3 mod 4
such 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 examine
this 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 under
which we can compute the relevant possibilities for  p , and to
note that there ARE always solutions. And there will indeed always
be 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  is
square 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 to
start my illustration not with  5 = 3^2 - 2^2  but rather with
15 = 4^2 - 1^2.  The fact that  1  and  16  are not CONSECUTIVE
squares 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 integer
x+1, x+2, ..., x+(d-1)  is not a sum of two squares.
« Last Edit: Oct 4th, 2009, 3:06pm by Michael Dagg » IP Logged

Regards,
Michael Dagg
Michael Dagg
Senior Riddler
****






   


Gender: male
Posts: 500
Re: Integers as sums of two squares  
« Reply #4 on: Oct 4th, 2009, 3:07pm »
Quote Quote Modify Modify

For even  d, let's look for the lower S2S of the form  (y+s)^2+y^2  and
the 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 to
see 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)^2
As I noted last time, this is solvable as long as  -(s^2+2i)  is
a nonzero quadratic residue mod  p_i.  By exactly the same
reasoning as last time, this will be true for whole congruence
classes (which thus contain infinitely many primes  p_i)  as
long 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 largest
square 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 S2S
but
 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 whenever
 
a_n = (y+2)^2+y^2 =
   40955120016227721730 + 184453087310820554688 K + 207684298111031164962 K^2
for any  K .
« Last Edit: Oct 4th, 2009, 3:11pm by Michael Dagg » IP Logged

Regards,
Michael Dagg
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board