If you haven’t seen it before, the polynomial seems to look like any other. And yet, as Euler noted, this polynomial has a curious property — evaluating at the integers gives a new prime each time:

What’s more, since satisfies , the polynomial actually produces primes (with repetition) for all . In other words, the shifted polynomial

returns primes for each of the first 80 non-negative integers. But here’s the real kicker — despite how long we’ve known about , 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 *prime-generating* if the values are all prime. Obviously, this is most interesting in examples where can be taken large (eg. in the case above), which begs the question *`need ** 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 such that is prime for all integers . Then is constant.

*Proof:* Fix and consider the prime . Since

,

it follows that for all and hence since is always prime. But if has infinitely many roots it must be the zero polynomial, which implies that identically.

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 is prime for by the Green-Tao Theorem, and consider the polynomial . This is a degree polynomial (with integer coefficients) that returns prime values for , 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

which satisfies

for each integer . The product divides by definition (and properties) of the binomial coefficient. In particular, we may choose our constants such that is an arbitrary multiple of for each .

Now consider the shifted polynomial , and choose such that the sequence consists of the first primes congruent to . That the residue class 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 before finding primes congruent to 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 in less than a minute and 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 in time . In our case this translates to polynomial production in time , which begins to feel sluggish even for moderate . (Although 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 . And indeed, such a test exists — the Lucas Test, which can test the primality of faster than AKS (at least, on average) but in return requires that we know the prime factors of . (This amounts to knowing the prime factors of , 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:

in which the 101 coefficients 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 .)

**— 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 (with coprime to ) instead of just .

**Exercise 2:** Show that there exists a monic polynomial in of degree that returns distinct primes for each .

Nice proof that polynomials of degree > 1 can have arbitrarily long prime streaks.

It reminds me of choosing k ordered pairs. There must exist a polynomial with degree no greater than k – 1 that intersects all k points.

For instance, (0, 41), (1, 43), (2, 47), and so on through 150 consecutive primes can be fit with a polynomial of degree 149 or lower.

The trouble with this concept is that the polynomial’s degree keeps growing. How many primes can it find besides the primes already known to define it with?

Thus the Bouniakowsky conjecture comes up again. I limit my searching algorithms to degrees not exceeding ten, because I prefer

f(n) for 0<=n<k to find more primes than there are primes < k as k grows without bound. Why not map from integers to integers and get more primes out than you plugged in?

Is that a good strategy, or should I use higher degrees more?

LikeLike