Results 1 to 6 of 6

Math Help - Gaps in sum of squares

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    169

    Gaps in sum of squares

    Show that there are arbitrarily long intervals of positive integers that cannot be expressed as sums of two squares.

    I know already the result of Fermat's theorem on sums of two squares - Wikipedia, the free encyclopedia

    Anyone has a proof?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Nice problem!

    Let q_0,\dots, q_n be distinct primes of the form 4n+3, and let P=q_0\dots q_n; using the Chinese Remainder Theorem, we can solve the congruences

    x+j\equiv 0 \mod q_j\ \ \ (0 \leq j \leq n)

    simultaneously. Now suppose q_j^2 \mid x+j for j \in S where S \subset \{0,\dots,n\}, and q_j^2 \nmid x+j for j \in \overline S where \overline S = \{0,\dots,n\}-S. Let x' = x+mP where

    m=\prod_{j \in \overline S}q_j

    (set m=1 if \overline S = \emptyset). I claim that q_j^2 \nmid x'+j for all j \in \{0,\dots,n\}. First, suppose q_j^2 \mid x'+j = x+j+mP for some j \in S; since q_j^2 \mid x+j, we must have q_j^2 \mid mP which is clearly false. On the other hand, if q_j^2 \mid x'+j = x+j+mP for some j \in \overline S, since we have q_j^2 \mid mP we must have q_j^2 \mid x+j which is also false.

    Thus the n+1 consecutive integers \{x', x'+1, \dots, x'+n\} are each divisible by a prime of the form 4n+3 only once, and hence none of them is a sum of two squares. By taking n to be as large as we wish, we solve the problem.
    Last edited by Bruno J.; March 22nd 2010 at 06:33 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    It should be noted that one would expect this to hold also for sums of two cubes, for examples. Given that the cubes are less dense than the squares, such sequences would be even more common than in our case. However, a completely different method would be required to prove it.

    Note also that a little bit of extra work can easily yield an (albeit bad) maximum bound on the size of the smallest x'=x'(n) which is the first term of a sequence of n+1 consecutive integers none of which is the sum of two squares.

    Let N(t) be the number of sums of two squares less than t. Then there is a constant 0<C<1 such that N(t) \sim C \frac{x}{\sqrt {\log x}}. (See Landau-Ramanujan constant.)
    Last edited by Bruno J.; March 22nd 2010 at 07:40 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2009
    Posts
    169
    Quote Originally Posted by Bruno J. View Post
    Now suppose q_j^2 \mid x+j for j \in S where S \subset \{0,\dots,n\}, and q_j^2 \nmid x+j for j \in \overline S where \overline S = \{0,\dots,n\}-S.
    I tried but I dont understnad the proof. What is S, is it an arbitrary subset of the first n integers? And you suppose something here, but where do you contradict it, or where do you handle the case if its false?
    Please tell me the general idea as well, as your proof looks quite nice.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by EinStone View Post
    I tried but I dont understnad the proof. What is S, is it an arbitrary subset of the first n integers? And you suppose something here, but where do you contradict it, or where do you handle the case if its false?
    Please tell me the general idea as well, as your proof looks quite nice.
    First, recall that an integer is a sum of two squares if and only if its squarefree part is divisible by no prime of the form 4n+3. So I constructed a sequence of n+1 integers, each of which is divisible by a prime of the form 4n+3 only once.

    Once we have the solution x to the original system of congruences, we obtain n+1 consecutive integers, each of which is divisible by a prime of the form 4n+3. However we want to make sure that the squares of these primes do not divide the given integers; so we find another solution x' to the system. Remember that any solutions of a system of the type I gave is determined only modulo the product P of the moduli of the equations. So we translate the given solution by mP. The choice of m is crucial if we want to make sure that q_j^2 \nmid x_j for all 0 \leq j \leq n; we partition the set of primes \{q_0,\dots,q_n\} as \{q_j : j \in S\} \cup  \{q_j : j \in \overline{S}\} , where the primes in the first of the two sets are those which are problematic (those for which q_j^2 \mid x+j, which we don't want to happen). You can convince yourself by reading my proof again that the choice of m yields a solution to the problem.

    Note also that I suppose that there are infinitely many primes of the form 4n+3 (which is a very specific case of Dirichlet's theorem on primes in arithmetic progressions).
    Last edited by Bruno J.; March 23rd 2010 at 12:39 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2009
    Posts
    169
    Thanks, its clear now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime gaps between primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 18th 2010, 06:11 AM
  2. Prime gaps of particular lengths
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 11th 2009, 03:30 PM
  3. Replies: 4
    Last Post: November 13th 2009, 06:12 PM
  4. Generating function (with gaps)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 3rd 2009, 11:12 AM
  5. gaps between square free
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 23rd 2008, 07:19 PM

Search Tags


/mathhelpforum @mathhelpforum