wu :: forums - Print Page


    
      
        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 15^th, 2009, 4:06pm)

Title: Integers as sums of two squares
Post by Michael Dagg on Sep 15^th, 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 15^th, 2009, 9:24pm

If d = 2k+1 = (k+1)²-k² is odd, we can proceed as follows:

Let us consider the numbers a with k² < a < (k+1)², 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 | n²+a for precisely 2 values of n mod p. By Hensel's lemma, there are precisely 2 value of n mod p² for which p² | n²+a. So there are 2p-2 > 0 values of n mod p² for which n²+a is divisible by p but not p², and therefore it is not the sum of two squares.

Now by the Chinese remainder theorem, there are infinitely many n such that n²+k²+1, ..., n²+(k+1)²-1 are not sums of two squares, while n²+k² and n²+(k+1)² obviously are.

If d = 4k+2, we can do the same thing for the interval (2n²+2k², 2n²+2(k+1)²): if 2k² < a < 2(k+1)², 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 p² for which 2n²+a is divisible by p but not p².

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 16^th, 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 p₁,...,p_d-1, all congruent to 3 mod 4, and such that p_i does not divide i(d-i). Pick an integer a such that:

a=1 mod 4; a = p_i - i mod p_i²,

and set

m = 4http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif p_i².

The condition on the p_i 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 = p_i mod p_i², and is therefore not the sum of two squares.

Title: Re: Integers as sums of two squares
Post by Michael Dagg on Oct 4^th, 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 4^th, 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 .