8
$\begingroup$

It is well-known that there are infinitely many square-free numbers of the form $n^2+1,n\in\mathbb{Z}$.

Question: Are there infinitely many square-free numbers of the form $n^2+1$, each with all its prime factors $\leq n$?

$\endgroup$
  • 3
    $\begingroup$ Interesting question. I bet the answer is affirmative, but a highly non-trivial application of sieve methods is required. Obviously a number $m$ cannot have more than one prime factor greater than $\sqrt{m}$, so a good idea may be to look for such $n$s by imposing that the first small primes of the form $4k+1$ ($5,13,17,\ldots$) do not divide $n^2+1$, then apply a sieve to such set. $\endgroup$ – Jack D'Aurizio Sep 13 '15 at 15:14
  • 1
    $\begingroup$ On the one hand, the density of squarefree values of $n^2+1$ is computable and positive. On the other hand, the set of $n$-smooth values of $n^2+1$ is known to have positive lower density by a result of Dartyge. So one approach, similar to what Jack suggests, would be to obtain a lower bound on $n$-smooth values of similar quality (we only really need upper density bounded away from $0$) while restricting $n$ to a particular congruence class. Then the squarefree density can likely be brought arbitrarily close to $1$ by choosing an appropriate congruence class, so they'd intersect. $\endgroup$ – Erick Wong Sep 13 '15 at 15:47
  • 1
    $\begingroup$ Fortunately if we just want infinitude, rather than positive density, an elementary argument suffices. See my answer below. $\endgroup$ – Noam D. Elkies Sep 22 '15 at 21:02
8
+100
$\begingroup$

Yes, there are infinitely many such $n$.

One way to prove this is to start from a quadratic polynomial $N(x)$ with integer coefficients such that there's a factorization $N^2+1=AB$ into two quadratics; let's use $$ N(x) = 5x^2+x-1, \quad N(x)^2 + 1 = (5x^2-4x+1) (5x^2+6x+2) = A(x) B(x). $$ Now substitute suitable positive integers for $x$, and try $n=N(x)$. One of $A,B$ is already smaller than $N$, and the other can be made to have all its prime factors smaller than $N$ by choosing $x$ in some congruence class; in our case $A<N$, and $B$ works as long as $x$ is even $-$ which fortunately is still consistent with $N^2+1$ being squarefree in our case. (NB $n^2+1$ could never be divisible by $4$ however $n$ was chosen.) I claim that as $X \to \infty$ a positive fraction of even choices of $x<2X$ make $n^2+1$ squarefree. Indeed let $S_p$ be the number of even $x < 2X$ for which $p^2 | N(x)^2 + 1$. Then $S_p=0$ if $p>10X$ or $p \neq 1 \bmod 4$, and otherwise $S_p < 4X/p^2 + 4$ (there are $4$ congruence classes for $x \bmod p^2$ that must be excluded). The sum of $4X/p^2$ over all $p \equiv 1 \bmod 4$ converges to $cX$ for some $c<1$ (in fact $c < 1/4$ if I computed right) and the sum of $4$ over $p<10X$ is $O(X/\log X)$. Hence $\sum_p S_p = (c+o(1)) X$ for large $X$, and we conclude that the number of choices of $x$ that make $n^2+1$ squarefree is at least $(1-c-o(1))X \to \infty$, QED.

$\endgroup$
  • $\begingroup$ Thank you so much, Prof. Elkies! I guess that the density should be $c_n(1-\log 2)$(where $c_n$ is the density of square free $n^2+1$) , but it might be very hard to prove such a result. $\endgroup$ – zy_ Sep 22 '15 at 23:20

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.