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?’
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
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 .