Prime-Generating Polynomials?

Going through some old number theory notes, I came across a result concerning generating prime numbers that I (embarrassingly) had forgotten. It would be a great topic to present to my students–if I were still teaching…sigh. As with many of my posts, we begin with a question.

Does there exist a function whose set of values consists of only primes and all the primes? The answer is yes, but the result is computationally involved and I will postpone any further commentary on such a function until the end. However, there does not exist a polynomial which

The first result is due to Christian Goldbach, who showed that there does not exist a univariate polynomial which returns a prime for all but finitely many values. I do not know the exact publication of this result, but more than one author states that he demonstrated this result in 1752. The exposition of the proof is adapted from G. Everest and Thomas Ward, An Introduction to Number Theory

Proposition 1. 

  1. If f\in\mathbb{Z}[x] has the property that f(n) is prime for all n\geq1, then f is constant.
  2. If f\in\mathbb{Z}[x] has the propery that f(n) is prime for all n\geq N, for some natural number N, then f is constant.

Proof. We first prove statement (2), as it implies statement (1). Let f=a_{0}+a_{1}x+\cdots+a_{k}x^{k} be a polynomial of degree k with integer coefficients such that f(n) is prime, for all n\geq N.

Suppose that f(N)=p is prime. Since the polynomial f(x)-p has at most k roots, we can find an integer r\geq1 such that f(N+rp)\neq p. By the binomial theorem,

\begin{array}{lcl}\displaystyle q=f(N+rp)&=&a_{0}+a_{1}(N+rp)+\cdots+a_{n}(N+rp)^{k}\\[2 em]&=&f(N)+a_{1}rp+\cdots+a_{n}\sum_{i=1}^{k}{k\choose i}(rp)^{i}N^{k-i}\end{array}

is prime with q>p. But p divides both terms of the right-hand side, which contradicts the primality of q. \Box

The second result, which I believe is also due to Goldbach, is that there does not exist a polynomial P in two or more variables whose set of values is only the primes. The proof of this result constructs a univariate function f from P, which returns infinitely many composite values.

Proposition 2. Let P\in\mathbb{Z}[x_{1},\ldots,x_{k}] be a polynomial in k\geq2 variables with integer coefficients. Define a function f:\mathbb{N}\rightarrow\mathbb{Z} by

\displaystyle f(n)=P\left(n,2^{n},\ldots,k^{n}\right)

and assume that f(n)\rightarrow\infty as n\rightarrow\infty. Then f(n) is composite for infinitely many values of n.

Proof. Fix n\geq1. Since we can rewrite a factor of the form c_{i_{1}\cdots i_{k}}n^{i_{1}}(2^{n})^{i_{2}}\cdots(k^{n})^{i_{k}} as

\displaystyle c_{i_{1}\cdots i_{k}}n^{i_{1}}(2^{i_{2}}\cdots k^{i_{k}})^{n}

Enumerate the terms 2^{i_{2}}\cdots k^{i_{k}} in ascending order by

\displaystyle1\leq a_{1}<\cdots<a_{m}

Allowing for zero coefficients c_{j,l}, we can rewrite f(n) as

\displaystyle f(n)=\sum_{l=1}^{m}\left(\sum_{j=1}^{r_{l}}c_{l,j}n^{j}\right)a_{l}^{n}

Since the terms of f(n) are arranged in ascending order, we see that c_{m,r_{m}}n^{r_{m}}a_{m}^{n} dominates all the terms of f(n) as n\rightarrow\infty. Suppose that f(n) is prime for all sufficiently large n. Then the coefficient c_{m,r_{m}} is necessarily positive. Since f(n)\rightarrow\infty, by hypothesis, as n\rightarrow\infty, we see that there exists a positive integer n such that

\displaystyle f(n)=p>a_{m}

For positive integers k and s,

\displaystyle\left(n+kp(p-1)\right)^{s}\equiv n^{s}\pmod{p}

By Fermat’s little theorem, a_{l}^{p-1}\equiv1\pmod{p}, for 1\leq l\leq m. Hence,

\displaystyle a_{l}^{n+kp(p-1)}\equiv a_{l}^{n}\pmod{p}

for all positive integers k and 1\leq l\leq m. Hence,

\displaystyle\left(n+kp(p-1)\right)^{s}a_{l}^{n+kp(p-1)}\equiv a_{l}^{n}n^{s}\pmod{p}

Substituting in this result, we conclude that

\displaystyle f\left(n+kp(p-1)\right)\equiv f(n)\equiv 0\pmod{p}

for all positive integers k. This result is a contradiction as the hypothesis that f(n)\rightarrow\infty as n\rightarrow\infty implies that there exists a k such that f(n+kp(p-1))=q>p, where q is a prime. \Box

The second result shows that multivariable integer polynomial P cannot be used to efficiently generate primes either. Without further testing, we do not know if a given value of P is prime or composite.

According to Hardy and Wright, it is possible to construct an integral polynomial R(x_{1},\ldots,x_{k}) in several variables such that the positive values assume all the primes and only the primes; however, its negative values are composite. Davis, Matijasevic, Putnam, and Robinson showed that with k=42, the degree of the poylnomial R need not be more than 5. Hardy and Wright state that the minimal value of k for such a polynomial R is k=10; however, the degree of R in this case is 15905. The interested reader can consult Jones, Sato, Wada, and Wiens, American Math. Monthly 83 (1976), 449-65.

This entry was posted in math.NT and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s