Author 
Topic: Integers as sums of two squares (Read 8726 times) 

Michael Dagg
Senior Riddler
Gender:
Posts: 500


Integers as sums of two squares
« on: Sep 15^{th}, 2009, 4:06pm » 
Quote 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 15^{th}, 2009, 4:09pm by Michael Dagg » 
IP Logged 
Regards, Michael Dagg



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Integers as sums of two squares
« Reply #1 on: Sep 15^{th}, 2009, 9:24pm » 
Quote Modify

If d = 2k+1 = (k+1)^{2}k^{2} is odd, we can proceed as follows: Let us consider the numbers a with k^{2} < 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 nonzero quadratic residue mod p. Pick such a prime distinct from the ones chosen for the other values of a. Now, p  n^{2}+a for precisely 2 values of n mod p. By Hensel's lemma, there are precisely 2 value of n mod p^{2} for which p^{2}  n^{2}+a. So there are 2p2 > 0 values of n mod p^{2} for which n^{2}+a is divisible by p but not p^{2}, and therefore it is not the sum of two squares. Now by the Chinese remainder theorem, there are infinitely many n such that n^{2}+k^{2}+1, ..., n^{2}+(k+1)^{2}1 are not sums of two squares, while n^{2}+k^{2} and n^{2}+(k+1)^{2} obviously are. If d = 4k+2, we can do the same thing for the interval (2n^{2}+2k^{2}, 2n^{2}+2(k+1)^{2}): if 2k^{2} < 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 p^{2} for which 2n^{2}+a is divisible by p but not p^{2}. But for d divisible by 4 I don't know. I'm not even sure how to handle d = 4 ....

« Last Edit: Sep 15^{th}, 2009, 9:56pm by Eigenray » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Integers as sums of two squares
« Reply #2 on: Sep 16^{th}, 2009, 3:43pm » 
Quote Modify

The case where d is divisible by 4 follows from Dickson's conjecture (or more generally Schinzel's hypothesis H) at least: Pick (d1) distinct primes p_{1},...,p_{d1}, all congruent to 3 mod 4, and such that p_{i} does not divide i(di). Pick an integer a such that: a=1 mod 4; a = p_{i}  i mod p_{i}^{2}, and set m = 4 p_{i}^{2}. 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}^{2}, and is therefore not the sum of two squares.


IP Logged 



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Integers as sums of two squares
« Reply #3 on: Oct 4^{th}, 2009, 3:06pm » 
Quote 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^2P} 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 .  (5p) = 1 iff (p5) = 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.  (2p)(3p)=1 iff (1)^{(p^21)/8} . (p3)(1)^{(p1)/2} = 1, i.e. iff (p3) = +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 .  (7p) = 1 iff (p7) = (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.  (2p)=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 longwinded 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+(d1) is not a sum of two squares.

« Last Edit: Oct 4^{th}, 2009, 3:06pm by Michael Dagg » 
IP Logged 
Regards, Michael Dagg



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Integers as sums of two squares
« Reply #4 on: Oct 4^{th}, 2009, 3:07pm » 
Quote 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+(y1)^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, ..., 2s1 . 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 + (y1)^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 4^{th}, 2009, 3:11pm by Michael Dagg » 
IP Logged 
Regards, Michael Dagg



