Say we have a polynomial $f(n)$ with integer coefficients, and we want to know the probability that $f(m)$ is prime for $m<n$, as $n$ goes to infinity. The prime number theorem treats the case $f(n) = n$. Has any work been done on this question for more general polynomials, for example quadratics?

  • $\begingroup$ Your < was probably being interpreted as an escape character for an html code. What sort of result are you expecting to find? This will depend very heavily on what the specific polynomial is. For example $f(n)=n^2+n+2$ is never prime. $\endgroup$ – JMoravitz Mar 6 '16 at 2:29
  • $\begingroup$ I'm not expecting any kind of general theory-- obviously this question is very sensitive to individual polynomials. $\endgroup$ – Vik78 Mar 6 '16 at 2:43
  • $\begingroup$ As an aside, $f(x)=x^2-x+41$ has the property that $f(1),f(2),\dots,f(40)$ are all prime numbers. $\endgroup$ – JMoravitz Mar 6 '16 at 2:59

There are no proven results of strength comparable to the Prime Number Theorem, except for degree $1$ polynomials which are covered by PNT-AP. For instance, we don't know a single polynomial of degree $>1$ which provably takes infinitely many prime values, even though we believe this should be true as long as the polynomial is irreducible and doesn't have any obvious reason to not be prime (i.e. being divisible by a fixed prime). But there is a heuristic expectation for what the correct probability should be, which is given precisely by the Bateman-Horn conjecture:


For linear polynomials, the situation is pretty well understood. If $(a,b)>1$, then the polynomial $an+b$ obviously takes only finitely many prime values (at most one, in fact), so the probability is either $0$ or $1/n$. Otherwise, $a$ and $b$ are relatively prime, and the asymptotic probability of $an+b$ being prime is

$$P(am+b \text{ prime} \mid m \le n) \sim \frac{a}{\phi(a) \log n}.$$

(Here $a$ and $b$ are assumed to be fixed so the rate of convergence is allowed to depend on $a$ and $b$.)

  • $\begingroup$ Really? Not even a single higher degree polynomial is known to be prime infinitely many times? Wow. It would be quite surprising if every higher degree polynomial was only prime a finite number of times over the positive integers. $\endgroup$ – Vik78 Mar 6 '16 at 3:16
  • $\begingroup$ Do you know of any results on the asymptotic probability that a linear polynomial takes on a prime value? $\endgroup$ – Vik78 Mar 6 '16 at 3:23
  • $\begingroup$ @Vik78 Yes, linear polynomials are classical and proved essentially at the same time as the Prime Number Theorem itself. $\endgroup$ – Erick Wong Mar 6 '16 at 3:23
  • $\begingroup$ Okay, I know that they take on prime values an infinite number of times, but what is the probability a given linear polynomial will be prime? $\endgroup$ – Vik78 Mar 6 '16 at 3:30
  • $\begingroup$ @Vik78 See my updated answer. $\endgroup$ – Erick Wong Mar 8 '16 at 19:34

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.