# Polynomials representing primes

Suppose over $\mathbb{Z}$ we are given an irreducible polynomial $p(x)$.

Can we say that $p(x)$ at least represents a prime as $x$ runs through integers?

-
Have you seen this? – J. M. Jul 10 '12 at 14:27
I could be wrong but I think the question is..."Does every irreducible polynomial over $\mathbb{Z}$ represent at least one prime?" – fretty Jul 10 '12 at 17:03

No, e.g. irreducible $\rm\ f(x)\, =\, x(x+1)+4\$ is even but $\rm\:f(x) \ne \pm 2.$

However, such fixed divisors of all values of $\rm\,f\,$ are essentially the only known obstruction to prime values. As motivation, let's start with a converse result. In $1918$ Stackel published the following simple observation:

Theorem If $\rm\, f(x)\,$ is a composite integer coefficient polynomial then $\rm\, f(n)\,$ is composite for all $\rm\,|n| > B,\,$ for some bound $\rm\,B.\,$ In fact $\rm\, f(n)\,$ has at most $\rm\, 2d\,$ prime values, where $\rm\, d = {\rm deg}(f)$.

The simple proof can be found online in Mott & Rose [3], p. 8. I highly recommend this delightful and stimulating $27$ page paper which discusses prime-producing polynomials and related topics.

Contrapositively, $\rm\, f(x)\,$ is prime (irreducible) if it assumes a prime value for large enough $\rm\, |x|\,$. As an example, Polya-Szego popularized A. Cohn's irreduciblity test, which states that $\rm\, f(x) \in \mathbb Z[x]\,$ is prime if $\rm\, f(b)\,$ yields a prime in radix $\rm\,b\,$ representation (so necessarily $\rm\,0 \le f_i < b).$

For example $\rm\,f(x) = x^4 + 6\, x^2 + 1 \pmod p\,$ factors for all primes $\rm\,p,\,$ yet $\rm\,f(x)\,$ is prime since $\rm\,f(8) = 10601\rm$ octal $= 4481$ is prime. Cohn's test fails if, in radix $\rm\,b,\,$ negative digits are allowed, e.g. $\rm\,f(x)\, =\, x^3 - 9 x^2 + x-9\, =\, (x-9)\,(x^2 + 1)\,$ but $\rm\,f(10) = 101\,$ is prime.

Conversely Bouniakowski conjectured $(1857)$ that prime $\rm\, f(x)\,$ assume infinitely many prime values (excluding cases where all the values of $\rm\,f\,$ have fixed common divisors, e.g. $\rm\, 2\: |\: x(x+1)+2\, ).$ However, except for linear polynomials (Dirichlet's theorem), this conjecture has never been proved for any polynomial of degree $> 1.$

Note that a result yielding the existence of one prime value extends to existence of infinitely many prime values, for any class of polynomials closed under shifts, viz. if $\rm\:f(n_1)\:$ is prime, then $\rm\:g(x) = f(x+ n_1\!+1)\:$ is prime for some $\rm\:x = n_2\in\Bbb N,\:$ etc.

For further detailed discussion of Bouniakowski's conjecture and related results, including heuristic and probabilistic arguments, see Chapter 6 of Ribenboim's The New Book of Prime Number Records.

[1] Bill Dubuque, sci.math 2002-11-12, On prime producing polynomials.

[2] Murty, Ram. Prime numbers and irreducible polynomials.
Amer. Math. Monthly, Vol. 109 (2002), no. 5, 452-458.

[3] Mott, Joe L.; Rose, Kermit. Prime producing cubic polynomials.
Ideal theoretic methods in commutative algebra, 281-317.
Lecture Notes in Pure and Appl. Math., 220, Dekker, New York, 2001.

-

Let $P(x)$ be a polynomial of degree $\ge 1$, with integer coefficients, such that no $d \gt 1$ divides all the coefficients.

If $P(x)$ has degree $1$, then $P$ represents at least one prime. This is a consequence of Dirichlet's Theorem on primes in arithmetic progression (and easily implies that Theorem).

As has been pointed out, for degree $\ge 2$, irreducibility is not enough to ensure that a polynomial represents a prime. For some irreducible polynomials $P(x)$, there exists a $d \gt 1$ such that $d$ divides $P(n)$ for every integer $n$.

However, that can only happen for relatively simple congruential reasons. So let us focus attention on polynomials $P(x)$ for which there is no such universal $d$. Unfortunately, it is an open problem whether such a polynomial must necessarily represent at least one prime.

Example: There is a good deal of evidence that there are infinitely many primes of the form $x^2+1$. However, whether or not there are infinitely many is a long-standing open problem, often called the Hardy-Littlewood Conjecture. If we could show that for all $a\ne 0$, (or even infinitely many $a$) there exists $x$ such that $(2ax)^2+1$ is prime, that would settle the Hardy-Littlewood Conjecture. (Conversely, the Hardy-Littlewood Conjecture implies that there are infinitely many such $a$.)

So the question you raised seems to be extremely difficult even for polynomials of degree $2$!

-