

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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.

share|cite|improve this question
up vote 3 down vote accepted

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, .

share|cite|improve this answer

Your Answer


