Prime-Generating Polynomials

pgp25

(A prime-generating interpolating polynomial of degree 25.)

If you haven’t seen it before, the polynomial p(n)=n^2+n+41 seems to look like any other. And yet, as Euler noted, this polynomial has a curious property — evaluating p(n) at the integers 0 \leq n \leq 39 gives a new prime each time:

\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c} n & 0 & 1 & 2 & 3 & 4 & \cdots & 35 & 36 & 37 & 38 & 39\\ \hline p(n) & 41 & 43 & 47 & 53 & 61& \cdots &1301 & 1373 & 1447 & 1523 & 1609 \end{array}

What’s more, since p(n) satisfies p(n) = p(-n-1), the polynomial p(n) actually produces primes (with repetition) for all n \in [-40,39]. In other words, the shifted polynomial

p(n-40) = n^2 - 79n+1601

returns primes for each of the first 80 non-negative integers. But here’s the real kicker — despite how long we’ve known about p(n), despite how simple it looks, this record of 80 consecutive primes has never been beaten by a quadratic polynomial with integer coefficients. In fact, it doesn’t appear that this record has ever been beaten by any polynomial with integer coefficients, of any degree!

 — THE LIMITS OF PRIME-GENERATING POLYNOMIALS  —

To fix a bit of notation, we call a polynomial p(n) prime-generating if the values p(0),\,p(1),\,\ldots,\,p(M) are all prime. Obviously, this is most interesting in examples where M can be taken large (eg. M=79 in the case above), which begs the question `need M even be finite?’

This question was resolved in the positive by the German mathematician Goldbach, who proved the following theorem.  (The proof given here is more similar to a proof given by Frobenius in 1896.)

Theorem (Goldbach, 1752): Fix f(x) \in \mathbb{Z}[x] such that f(n) is prime for all integers n \geq 0. Then f(x) is constant.

Proof: Fix n_0>0 and consider the prime p=f(n_0). Since

f(n_0+pk) \equiv f(n_0) \!\! \mod p,

it follows that p \mid f(n_0+pk) for all k\in \mathbb{Z} and hence f(n_0+pk)=p since f(n) is always prime. But if f(n)-p has infinitely many roots it must be the zero polynomial, which implies that f(n)=p identically.  \square

Nevertheless, we can ask whether there exist integer polynomials that remain prime for arbitrarily many consecutive inputs.

A similar question about `arbitrarily many consecutive prime values’ was answered by Green and Tao in the case of linear polynomials in the famous Green-Tao Theorem:

Theorem (Green-Tao, 2004): The set of primes contains arbitrarily long arithmetic progressions.

The Green-Tao theorem is not an easy result, but assuming it leads to a remarkably slick solution to our question about (non-linear) prime-generating polynomials. Indeed, suppose that a+bn is prime for n \in [0, M^k] by the Green-Tao Theorem, and consider the polynomial f(n)=a+bn^k. This is a degree k polynomial (with integer coefficients) that returns prime values for n \in [0,M], which proves our claim.

Remark — This claim about prime-generating polynomials has traditionally been discussed as a consequence of the Hardy-Littlewood k-tuple Conjecture. It appears that this `unconditional’ proof is new.

One advantage of the proof above is that we obtain arbitrarily many prime values without sacrificing the size of our degree. If we’re willing to enlarge the degree, we can also attack this problem using interpolating polynomials.

Unfortunately, the `obvious’ attack on this problem via interpolating polynomials fails because polynomials of this form typically require rational coefficients. The way past this obstruction is due to Chang and Lih in their 1977 paper Polynomial Representation of Primes, and proceeds as follows:

Consider the polynomial

\displaystyle f(x):=\sum_{n=0}^M \frac{a_n}{x-n}\prod_{j=0}^M (x-j),

which satisfies

f(m) = a_m m! (M-m)! (-1)^{M-m}

for each integer m \in [0,M]. The product m! (M-m)! divides M! by definition (and properties) of the binomial coefficient. In particular, we may choose our constants a_m such that f(m) is an arbitrary multiple of M! for each m \in [0,M].

Now consider the shifted polynomial f(x)+1, and choose a_m such that the sequence \{f(m)+1 : m \in [0,M]\} consists of the first M+1 primes congruent to 1\!\! \mod M!. That the residue class 1\!\! \mod M! contains sufficiently many primes is a consequence of Dirichlet’s Theorem on primes in arithmetic progressions.

— BREAKING RECORDS BECAUSE WHY NOT —

The thing I find most curious about Chang and Lih’s paper is that they feel no need to smash the world record for prime-generating polynomials using their construction. Nor does it appear that anyone else has.

So how large can we make M before finding M primes congruent to 1\!\! \mod M! becomes computationally infeasible? I’m not sure what the answer was in 1977 but it’s certainly a lot larger than 80 now.

If we’re content with verifying the primality of our outputs probabilistically (eg. with Miller-Rabin) we can produce examples with M \approx 250 in less than a minute and M \approx 500 in 30 minutes. (Runtimes will vary depending on implementation and your desired probability of failure.)

On the other hand, rigorously proving that the values returned by our polynomial are prime using deterministic tests can take a fair bit longer. For example, most implementations of AKS check primality of n in time O((\log n)^6). In our case this translates to polynomial production in time O(M \cdot M^6 \log(M)^6), which begins to feel sluggish even for moderate M. (Although M \approx 100 is still quite reasonable.)

What we really want is a primality test that exploits the special nature of the numbers we’re testing, numbers of the form n=k \cdot M! +1. And indeed, such a test exists — the Lucas Test, which can test the primality of n faster than AKS (at least, on average) but in return requires that we know the prime factors of n-1. (This amounts to knowing the prime factors of k, which is easy.) But I think a fast implementation of the Lucas Test is a task for another day and another post.

For now, let’s be happy with a record polynomial of moderate size:

\displaystyle f_{100}(x) = 1+\sum_{n=0}^{100} \frac{a_n(-1)^n}{x-n} \binom{100}{n}\prod_{j=0 }^{100} (x-j),

in which the 101 coefficients a_n are (in increasing order)

15, 120, 139, 166, 180, 194, 231, 392, 413, 451, 478, 487, 494, 523, 626, 731, 757, 807, 885, 888, 894, 918, 926, 960, 988, 1015, 1036, 1053, 1138, 1169, 1201, 1211, 1259, 1325, 1352, 1488, 1498, 1501, 1561, 1562, 1566, 1570, 1713, 1762, 1771, 1798, 1814, 1834, 1893, 1934, 1980, 2025, 2036, 2168, 2177, 2313, 2335, 2348, 2358, 2369, 2396, 2401, 2616, 2694, 2830, 2885, 2998, 3033, 3095, 3154, 3232, 3238, 3268, 3291, 3335, 3352, 3393, 3467, 3531, 3552, 3555, 3595, 3616, 3817, 3850, 3881, 3998, 4038, 4050, 4197, 4206, 4224, 4262, 4360, 4366, 4439, 4467, 4487, 4518, 4555, 4623.

(This polynomial has been verified to produce prime values using the deterministic primality test in Mathematica’s ProvablePrimeQ[] and returns primes for n\in [0,100].)

— EXERCISES —

Exercise 1: Verify that we don’t need to rely on Dirichlet’s Theorem on primes in arithmetic progressions to prove our result on interpolating polynomials by considering slightly generalized polynomials of the form f(x)+c (with c coprime to M!) instead of just f(x)+1.

Exercise 2: Show that there exists a monic polynomial in \mathbb{Z}[x] of degree M that returns distinct primes for each x \in [0,M-1].

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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