# Proving existence of a square-free sequence

I found this problem and a solution sketch in a MathOverflow answer, and I thought it was nice enough to deserve more attention and a properly written solution.

Problem:

Prove that for each natural number $n$, there is some natural number $r$ for which the $n$ integers $r+1^2,r+2^2,…r+n^2$ are all square-free.

-
The sketch there does an inadequate job of treating the small primes. –  Greg Martin May 14 '13 at 16:49
@GregMartin Indeed. I thought it should have a complete solution. –  Potato May 14 '13 at 19:00

Let $p_1, p_2, \cdots , p_k$ be all the prime numbers less than $n^2$ (for some $k$). For any $K > k$, let $p_{k+1}, p_{k+2}, \cdots , p_K$ be the next prime numbers after that (larger than $n^2$).

For $1 \le i \le k$, there is at least one value of $r$ $\pmod {p_i^2}$ that satisfies $r + 1^2, r+2^2, \cdots , r+n^2 \not \equiv 0$ (i.e. there is at least one viable possible remainder for $r$.) To see this, note that the squares modulo $p_i^2$ do not include $p_i$ itself, thus setting $r \equiv -p_i$ is sufficient.

For $k+1 \le i \le K$, the numbers $1^2, 2^2, \cdots , n^2$ are all distinct $\pmod {p_i}$, because $p_i > p_{k+1} > n^2$. Therefore, there are exactly $(p_i^2 - n)$ viable possibilities for $r \pmod {p_i}$.

Now let $N = p_1^2p_2^2p_3^2\cdots p_K^2$. By the Chinese remainder theorem, there are at least $$(1)(1) \cdots (1)(p_{k+1}^2 - n)(p_{k+2}^2 - n)\cdots (p_{K}^2 - n)$$

viable options for $r$ modulo $N$ (by which we mean values of $r$ modulo $N$ that cause $r + 1^2, r + 2^2, \cdots r+n^2$ to be free from squares of all the primes $p_1, \cdots ,p_K$). For any $K$, we define $$x_K := \frac{\text{Number of viable options for } r \text{ mod } N}{N}$$ which evaluates to $$\frac{(p_{k+1}^2 - n)(p_{k+2}^2 - n)\cdots (p_{K}^2 - n)}{p_1^2p_2^2p_3^2\cdots p_K^2} = \frac{1}{p_1}\frac{1}{p_2} \cdots \frac{1}{p_k} \left(1 - \frac{n}{p_{k+1}^2}\right)\cdots \left(1 - \frac{n}{p_K^2}\right)$$

The infinite product $\lim_{K \to \infty} \left(x_K \right)$ converges to a positive number, and the viable options for $r$ modulo $N$ for the first $K+1$ primes are a subset of the viable options for $r$ modulo $N$ for the first $K$ primes for any $K$. Therefore, there are infinitely many values of $r$ which work for every $K$. In particular, there is at least one positive integer $r$ such that $r + 1^2, r+2^2, \cdots r+n^2$ are squarefree.

-
As a learning moment: the phrase "and the viable options for $r$ modulo $N$ for the first $K+1$ primes are a subset of the viable options for $r$ modulo $N$ for the first $K$ primes for any $K$" is, in my opinion, the most important part of the proof. Density arguments alone can't establish the result; something about the structure of the omitted residue classes must be used. By contrast, consider the set of positive integers not in the residue class $k \pmod {p_k^2}$ for $k=1,2,\dots$; the product of the local densities is $6/\pi^2$ as for squarefree numbers, but this set is actually empty. –  Greg Martin May 15 '13 at 7:22