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 '18 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 '18 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 '18 at 19:18
  • 2
    $\begingroup$ Possible duplicate of Bateman-Horn conjecture, continued $\endgroup$ – Felipe Voloch Apr 22 '18 at 8:58

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

| cite | improve this answer | |

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

| cite | improve this answer | |

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.