Is there a generalization of Dirichlet's theorem along these lines?

If $p(n)$ is a polynomial of degree $k$ with positive integers as coefficients, such that the coefficients are relatively prime, then the sequence $p(1),p(2),p(3),\ldots$ has infinitely many primes?

$k=1$ is the good old Dirichlet's theorem on arithmetic progressions.

If the above is false, is there a trivial example for some degree '$k$'?


This is false as stated. Take, for example, $p(n) = n^2 + n$. The correct condition is that $p$ is irreducible and there exists no $d > 1$ such that $d | p(n)$ for all $n$. With this condition this is a big open problem, the Bunyakovsky conjecture, and it is open for any such polynomial $p$ of degree greater than $1$.

  • $\begingroup$ Thanks. That was helpful. (Though $n^2 + 4n + 3$ would have been a better example since my question want all the coefficients including the constant term to be positive) It makes sense to talk of irreducible polynomials as opposed to polynomials with relatively prime coefficients. $\endgroup$
    – user17762
    May 30 '11 at 19:04

In 1918 Stackel published the following simple observation:

THEOREM If $ p(x)$ is a composite integer coefficient polynomial

then $ p(n) $ is composite for all $|n| > B $, for some bound $B$,

in fact $ p(n) $ has at most $ 2d $ prime values, where $ d = {\rm deg}(p)$.

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, $ p(x) $ is prime (irreducible) if it assumes a prime value for large enough $ |x| $. Conversely Bouniakowski conjectured (1857) that prime $ p(x) $ assume infinitely many prime values (except in trivial cases where the values of $p$ have an obvious common divisor, e.g. $ 2 | x(x+1)+2$ ).

As an example, Polya-Szego popularized A. Cohn's irreduciblity test, which states that $ p(x) \in {\mathbb Z}[x]$ is prime if $ p(b) $ yields a prime in radix $b$ representation (so necessarily $0 \le p_i < b$).

For example $f(x) = x^4 + 6 x^2 + 1 \pmod p$ factors for all primes $p$, yet $f(x)$ is prime since $f(8) = 10601$ octal $= 4481$ is prime.

Note: Cohn's test fails if, in radix $b$, negative digits are allowed, e.g. $f(x) = x^3 - 9 x^2 + x-9 = (x-9)(x^2 + 1)$ but $f(10) = 101$ is prime.

For further discussion see my prior post [1], along with Murty's online paper [2].

[1] 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.

  • $\begingroup$ Thanks Bill. I am unable to open the article by Mott, Joe L.; Rose, Kermit $\endgroup$
    – user17762
    May 30 '11 at 19:09
  • $\begingroup$ @Sivaram It's now a gzipped postscript file, so you'll need a decompression program that handles gzip, and a postscript viewer (e.g. GSView). $\endgroup$ May 30 '11 at 19:12

It is conjectured there are infinitely many primes of the form $n^2 + 1$ but not proven.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy