Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
2  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.