For any integer polynomial $f(t) \in \mathbb{Z}[t]$ (with positive leading coefficient), Hardy-Littlewood's Conjecture F provides a conjectural estimate for the number of primes that $f$ assumes less than $n$. To be a bit more specific, we have

$$\#\{k\leq n \mid f(k) \text{ is prime}\} \sim c \cdot \frac{n}{\log n}$$

for some constant $c$ dependent on $f$. In particular, the density of the set $\{k \mid f(k) \text{ is prime}\}$ is zero. Is there a way to prove this last fact without appealing to Conjecture F?

Perhaps the following observation will be helpful: let $p \mid f(k)$ for some prime $p$ and integer $k$. Then $f$ admits a root in $\mathbb{F}_p[t]$, so $p \mid f(k+mp)$ for any integer $m$. As $f$ is increasing (eventually), it follows that $f(k+mp)$ is not prime, for $m \gg 0$. Thus $f$ is not prime on a set of density at least $1/p$. As membership in the sets $p_1\mathbb{N}$ and $p_2\mathbb{N}$ is asymptotically independent (for $p_i$ prime), it follows that $f$ is composite on a set of density

$$1-\prod_{\exists n:\;p \mid f(n)} \left(1-\frac{1}{p}\right)$$

So in this sense, $f$ having too many prime factors actually implies that $f$ has attains prime values on a set of smaller density.


Yes this is true. Without loss of generality assume that $f$ is irreducible. Let $w(n)$ denote the number of prime factors of $n$. Given $\varepsilon > 0$, the following stronger statement holds: $$ \#\{n \leq x: w(f(n)) < (1 - \varepsilon)\log\log x \} = o(x). $$ That is, most $f(n)$ with $n \leq x$ have more than $\log\log x$ prime factors! This result (in fact a stronger result) was originally established by Halberstam in the 50's. A recent account of methods leading to this theorem is available in Granville's and Soundararajan's survey, http://www.dms.umontreal.ca/%7Eandrew/PDF/ErdosKac.pdf .


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.