Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


By posting your answer, you agree to the privacy policy and terms of service.

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