# Infinitely many $n$ such that $n^2+1$ is squarefree

How can we show that there are infinitely many positive integers $n$ such that $n^2+1$ is square free? I was thinking we could split it into cases of squares of primes congruent to either 1 or 3 (mod 4).

Even stronger: could we prove that the set of numbers positive integers $m$ such that $m^2+1$ is not squarefree is a set of measure zero?

EDIT: could I get an elementary solution to the first question?

• Sometime ago I and others answered the second question. For example if $x\equiv 7\pmod{25}$ then $x^2+1$ is not square free. And there are bunches of others. So the set of $x$ such that $x^2+1$ is not square free has positive density. – André Nicolas Apr 2 '15 at 22:36
• How would you approach the first one though? – sucre Apr 2 '15 at 22:50
• Presumably, you don't mean measure, but density. – Thomas Andrews Apr 2 '15 at 22:51
• @ThomasAndrews Yeah I realized that error after Andre Nicolas's comment. – sucre Apr 2 '15 at 22:52
• – punctured dusk Sep 26 '15 at 12:29

Let $S(n)$ be the number of squareful numbers of the form $k^2+1$ less than or equal to $n^2+1$. We can bound it from above by counting every time a number is divisible by the square of a prime:

$S(n) \le \sum_{1 \le p \le n}{\sum_{1 \le k \le n, p^2 \vert k^2+1}{1}}$

Since $k^2+1$ is never divisible by $4$ or $9$, this becomes:

$S(n) \le \sum_{5 \le p \le n}{\sum_{1 \le k \le n, p^2 \vert k^2+1}{1}}$

$-1$ has at most two square roots mod $p^2$, so we can write this as:

$S(n) \le \sum_{5 \le p \le n}{(\frac{2 \cdot n}{p^2}+2)}$

And we can separate the constant term to get:

$S(n) \le 2 \cdot \pi(n) + \sum_{5 \le p \le n}{\frac{2 \cdot n}{p^2}}$

Assuming $n \gt 120$:

$S(n) \le \frac{2 \cdot \phi(120) \cdot n}{120} + 2 \cdot n \cdot \sum_{5 \le p \le n}{\frac{1}{p^2}}$

Simplifying and ignoring that the sum is limited to primes:

$S(n) \le \frac{8 \cdot n}{15} + 2 \cdot n \cdot (\frac{\pi^2}{6} - \frac{1}{16} - \frac{1}{9} - \frac{1}{4} - 1)$

Calculating and rounding up:

$S(n) \le 0.54 \cdot n + 0.45 \cdot n$

$S(n) \le 0.99 \cdot n$

So the density of squarefree numbers of the form $k^2+1$ is at least $0.01$, and therefore there are an infinite number of them. I really wasn't expecting to end up with such a narrow margin! It is possible to do better with some obvious improvements.

• Nice! This is more elementary than I would have expected. For the benefit of the OP, it's probably worth defining $\pi(n)$ and $\phi(120)$, as well as explaining that bound, and maybe explaining where $\frac{\pi^2}{6}$ comes from. – Qiaochu Yuan Apr 3 '15 at 1:08
• Thank you! However, is there some purely non-analytic elementary method to solve just the 1st question (infinitely many sqfree of the form n^2+1) using just theory of say quadratic residues, etc.? – sucre Apr 3 '15 at 1:27
• Nothing really analytic here except maybe $\frac{\pi^2}{6}$, but there is apparently an elementary proof of the Basel problem if that counts en.wikipedia.org/wiki/Basel_problem#A_rigorous_elementary_proof. You can use quadratic reciprocity to exclude $4 \cdot k + 3$ primes from the sum to get a tighter bound (but the first improvement would be to exclude composites). I will try to clarify some of the things Qiaochu mentions. – Dan Brumleve Apr 3 '15 at 1:39
• Already noting that the primes used are odd and using a simple telescoping gives us that $\sum_{5\le p\le n}\frac1{p^2}\le \sum_{k=2}^\infty\frac1{(2k+1)^2}\le \sum_{k=2}^\infty\left(\frac1{4k}-\frac1{4(k+1)}\right)\le \frac18$, so we get rid of the need to explain $\frac{\pi^2}6$ while improving the factor $0.45$ to $0.25$. – Hagen von Eitzen Sep 26 '15 at 12:24
• actual density due to Estermann, can be downloaded at gdz.sub.uni-goettingen.de/dms/load/img/… and a recent item in English by Heath-Brown arxiv.org/pdf/1010.6217.pdf that clearly shows the constant (although not including an actual decimal number, rather an infinite product) – Will Jagy Sep 26 '15 at 18:48