What's the probability that k + n^2 is squarefree, for fixed k? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T05:02:10Z http://mathoverflow.net/feeds/question/16792 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16792/whats-the-probability-that-k-n2-is-squarefree-for-fixed-k What's the probability that k + n^2 is squarefree, for fixed k? Michael Lugo 2010-03-01T22:25:36Z 2010-03-01T22:53:46Z <p>While playing around with <a href="http://mathoverflow.net/questions/16780/square-free-sum-of-two-squares" rel="nofollow">this question</a> (when is the sum of two squares squarefree?), from some experimental computations (and bolstered by the fact that the density of squarefree positive integers is known to exist), I came up with the following conjecture: the asymptotic density of squarefree numbers in the sequence $(k+1^2, k+2^2, k+3^2, \ldots)$, for fixed k, exists and depends on k.</p> <p>To give an example of what I mean, consider numbers of the form $1 + n^2$. 895 of the numbers $1+1^2, 1+2^2, \ldots, 1+1000^2$ are squarefree; 897 of the next thousand are; 895 of the third thousand; 896 of the fourth thousand. 891 of the numbers $1+1000001^2, \ldots, 1+1001000^2$ are squarefree, as are 895 of the numbers $1+2000001^2, \ldots, 1+2001000^2$. So there seems to be some constant $C_1$, probably between 0.89 and 0.90, such that $1+k^2$ has probability'' $C_1$ of being squarefree. The same thing seems to happen if we replace 1 with other integers, although with other constants.</p> <p>Are such constants known to exist? If they are, how can they be computed?</p> http://mathoverflow.net/questions/16792/whats-the-probability-that-k-n2-is-squarefree-for-fixed-k/16798#16798 Answer by Bjorn Poonen for What's the probability that k + n^2 is squarefree, for fixed k? Bjorn Poonen 2010-03-01T22:48:02Z 2010-03-01T22:53:46Z <p>More generally, suppose that $f(x) \in \mathbf{Z}[x]$ has no repeated factors. For each prime $p$, let $c_p$ be the number of integers <code>$x \in \{0,1,\ldots,p^2-1\}$</code> satisfying $f(x) \equiv 0 \pmod{p^2}$. Heuristically, the probability that a random integer $x$ is such that $f(x)$ is not divisible by $p^2$ equals $1-c_p p^{-2}$, and these conditions should be independent by the Chinese remainder theorem, so one would conjecture that the fraction of integers $x$ in <code>$\{1,2,\ldots,N\}$</code> such that $f(x)$ is squarefree should tend to $\prod_p (1-c_p p^{-2})$, where the product is taken over all primes $p$. For large $p$, we have $c_p \le \deg f$, so this product converges.</p> <p>This guess has been proved for $\deg f \le 3$ (the case $\deg f=3$ is a nontrivial result of C. Hooley). In particular, this answers your question for $f(x)=x^2+k$. There is no $f$ of degree $4$ or greater for which the density is known to exist (except in cases when the density is $0$ because some $c_p$ equals $p^2$). On the other hand, A. Granville proved that the $abc$ conjecture implies that the density exists and equals the predicted value for $f$ of any degree. For further references and a generalization to multivariable polynomials, see the papers cited in the references below.</p> <p>C. Hooley, On the power free values of polynomials, <em>Mathematika</em> <strong>14</strong> (1967), 21-26.</p> <p>A. Granville, $ABC$ allows us to count squarefrees, <em>Internat. Math. Res. Notices</em> <strong>1998</strong>, no. 19, 991-1009.</p> <p>B. Poonen, <a href="http://www-math.mit.edu/~poonen/papers/sqfree.pdf" rel="nofollow">Squarefree values of multivariable polynomials</a>, <em>Duke Math. J.</em> <strong>118</strong> (2003), no. 2, 353-373.</p>