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 given
positive 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 set

m = 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 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.

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 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.

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  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 .