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?
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?
Nice problem!
Let $\displaystyle q_0,\dots, q_n$ be distinct primes of the form $\displaystyle 4n+3$, and let $\displaystyle P=q_0\dots q_n$; using the Chinese Remainder Theorem, we can solve the congruences
$\displaystyle x+j\equiv 0 \mod q_j\ \ \ (0 \leq j \leq n)$
simultaneously. Now suppose $\displaystyle q_j^2 \mid x+j$ for $\displaystyle j \in S$ where $\displaystyle S \subset \{0,\dots,n\}$, and $\displaystyle q_j^2 \nmid x+j$ for $\displaystyle j \in \overline S$ where $\displaystyle \overline S = \{0,\dots,n\}-S$. Let $\displaystyle x' = x+mP$ where
$\displaystyle m=\prod_{j \in \overline S}q_j$
(set $\displaystyle m=1$ if $\displaystyle \overline S = \emptyset$). I claim that $\displaystyle q_j^2 \nmid x'+j$ for all $\displaystyle j \in \{0,\dots,n\}$. First, suppose $\displaystyle q_j^2 \mid x'+j = x+j+mP$ for some $\displaystyle j \in S$; since $\displaystyle q_j^2 \mid x+j$, we must have $\displaystyle q_j^2 \mid mP$ which is clearly false. On the other hand, if $\displaystyle q_j^2 \mid x'+j = x+j+mP$ for some $\displaystyle j \in \overline S$, since we have $\displaystyle q_j^2 \mid mP$ we must have $\displaystyle q_j^2 \mid x+j$ which is also false.
Thus the $\displaystyle n+1$ consecutive integers $\displaystyle \{x', x'+1, \dots, x'+n\}$ are each divisible by a prime of the form $\displaystyle 4n+3$ only once, and hence none of them is a sum of two squares. By taking $\displaystyle n$ to be as large as we wish, we solve the problem.
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 $\displaystyle x'=x'(n)$ which is the first term of a sequence of $\displaystyle n+1$ consecutive integers none of which is the sum of two squares.
Let $\displaystyle N(t)$ be the number of sums of two squares less than $\displaystyle t$. Then there is a constant $\displaystyle 0<C<1$ such that $\displaystyle N(t) \sim C \frac{x}{\sqrt {\log x}}$. (See Landau-Ramanujan constant.)
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 $\displaystyle 4n+3$. So I constructed a sequence of $\displaystyle n+1$ integers, each of which is divisible by a prime of the form $\displaystyle 4n+3$ only once.
Once we have the solution $\displaystyle x$ to the original system of congruences, we obtain $\displaystyle n+1$ consecutive integers, each of which is divisible by a prime of the form $\displaystyle 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 $\displaystyle x'$ to the system. Remember that any solutions of a system of the type I gave is determined only modulo the product $\displaystyle P$ of the moduli of the equations. So we translate the given solution by $\displaystyle mP$. The choice of $\displaystyle m$ is crucial if we want to make sure that $\displaystyle q_j^2 \nmid x_j$ for all $\displaystyle 0 \leq j \leq n$; we partition the set of primes $\displaystyle \{q_0,\dots,q_n\}$ as $\displaystyle \{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 $\displaystyle 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 $\displaystyle m$ yields a solution to the problem.
Note also that I suppose that there are infinitely many primes of the form $\displaystyle 4n+3$ (which is a very specific case of Dirichlet's theorem on primes in arithmetic progressions).