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?

  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Apr 2 '15 at 22:36
  • $\begingroup$ How would you approach the first one though? $\endgroup$ – sucre Apr 2 '15 at 22:50
  • 2
    $\begingroup$ Presumably, you don't mean measure, but density. $\endgroup$ – Thomas Andrews Apr 2 '15 at 22:51
  • $\begingroup$ @ThomasAndrews Yeah I realized that error after Andre Nicolas's comment. $\endgroup$ – sucre Apr 2 '15 at 22:52
  • 1
    $\begingroup$ Related: $x^2+1$ is almost always square free $\endgroup$ – 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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Apr 3 '15 at 1:08
  • $\begingroup$ 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.? $\endgroup$ – sucre Apr 3 '15 at 1:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Dan Brumleve Apr 3 '15 at 1:39
  • 1
    $\begingroup$ 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$. $\endgroup$ – Hagen von Eitzen Sep 26 '15 at 12:24
  • 1
    $\begingroup$ 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) $\endgroup$ – Will Jagy Sep 26 '15 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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