Prime-Generating Polynomials

(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]$ .

2 responses to “Prime-Generating Polynomials”

Cooper Gates May 1, 2018 at 11:18 pm · · Reply →

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
Oscar Lanzi April 18, 2022 at 9:08 pm · · Reply →

Your list of n²+n+41 primes gives 609 for n=39. But the true value at that value if n is 1601 (which us prime).

LikeLike

a. w. walker

mathematics and miscellany

Prime-Generating Polynomials

2 responses to “Prime-Generating Polynomials”

Leave a Reply Cancel reply

Share this:

Like this:

2 responses to “Prime-Generating Polynomials”

Leave a Reply Cancel reply