Let $p(n)$ be a polynomial with integer coefficients. Define $\Delta( p(n) )$, the prime density of $p(n)$, to be the limit of the ratio with respect to $n$ of the number of primes $p(k)$ generated when the polynomial is evaluated at the natural numbers $k=1,2,\ldots,n$: $$ \Delta( p(n) ) \;=\; \lim_{n \to \infty} \frac{ \textrm{number of } p(k), k \le n, \textrm{that are prime}} {n} $$ For example, Euler's polynomial $p(n)=n^2+n+41$ starts out with ratio $1$, but then diminishes beyond $n=39$:

And it continues to diminish ...
... and by $n=10^7$ has reached $\Delta=0.22$.

Q. What is the largest known $\Delta( p(n) )$ over all polynomials $p(n)$?

In particular, are there any polynomials known to have $\Delta > 0$?

Maybe these questions can be answered assuming one or more conjectures?

  • 5
    $\begingroup$ For degree $1$ and co-prime coefficients $\Delta>0$ (Dirichlet's theorem, Chebotarev density theorem). For degree >1 (and any irreducible $p$), it is an open problem . $\endgroup$
    – user6976
    Apr 21, 2018 at 12:56
  • 14
    $\begingroup$ @MarkSapir That would be true if he were multiplying the density by $\log n$, but he isn't, so in fact every polynomial has density zero. $\endgroup$
    – Will Sawin
    Apr 21, 2018 at 13:59
  • 2
    $\begingroup$ @WillSawin: Yes, of course. But I thought that log was just missing. Clearly one needs to divide by the number of primes $\le n$ and not by $n$. $\endgroup$
    – user6976
    Apr 21, 2018 at 19:18
  • 2
    $\begingroup$ Possible duplicate of Bateman-Horn conjecture, continued $\endgroup$ Apr 22, 2018 at 8:58

2 Answers 2


It is known (it follows from Brun's sieve, or more modern sieves) that for any fixed polynomial $p$, there exists a constant $c_p$ such that $$ \# \{ n\le x\colon p(n) \text{ is prime} \} < c_p \frac x{\log x}. $$ In particular, your density $\Delta$ equals $0$ for any polynomial (as Will Sawin commented).

For irreducible polynomials without obvious obstructions (such as all the values being even), it is conjectured that $\# \{ n\le x\colon p(n) \text{ is prime} \} \sim s_p \frac x{\log x}$ for some constant $s_p$ as $x\to\infty$; but this is an open problem for any polynomial $p$ of degree greater than $1$.


This has been asked multiple times before (with three variations by yours truly), so is a mega-duplicate, if you will:

Bateman-Horn, continued even further

Bateman-Horn conjecture, continued

Unexpectedly prime rich cubic polynomial

And even resulted in a preprint:

Some experiments on Bateman-Horn

I Rivin - arXiv preprint arXiv:1508.07821, 2015 - arxiv.org


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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