# Thread: Gaps in sum of squares

1. ## 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?

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

3. 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 such that $N(t) \sim C \frac{x}{\sqrt {\log x}}$. (See Landau-Ramanujan constant.)

4. Originally Posted by Bruno J.
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.

5. Originally Posted by EinStone
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).

6. Thanks, its clear now.