41 Followers & A Remarkable Polynomial
I was surprised to get a modest burst of new followers overnight (thanks, rebloggers!) so here’s another little celebration post.
The polynomial $$P(n):= n^2 + n + 41$$ is special. Here’s a little table of values:
$$n \;|\; P(n)$$
$$0 \;|\; 41$$
$$1 \;|\; 43$$
$$2 \;|\; 47$$
$$3 \;|\; 53$$
$$4 \;|\; 61$$
Notice anything interesting? These values of P(n) are all prime! Does this go on?
You can check for yourself (preferably with Mathematica) that P(n) is prime for n = 0 up to 39, but ruh-roh! The pattern breaks at n = 40. This number is one less than the constant term of the polynomial…I would stake my life that this is not just a coincidence. However, the reason this polynomial does what it does is beyond me, and supposedly involves deep algebraic number theory. It’s not at all just that 41 is prime.
It’s impossible for a polynomial with integer coefficients to give prime values for every natural number input (see the article on Prime-Generating Polynomials at Wolfram). This seems slightly spooky to me, as it’s pretty easy to visualize a nice, continuous curve C(t) that always passes through primes for integral x-values. There are even such curves for which C(n) is the nth prime. Fact is, no such curve is a polynomial. But the Stone-Weierstrass Theorem tells us that any continuous curve at all can be approximated to arbitrary precision by a polynomial, if the domain of that curve is restricted to a compact set. I find this one of the most beautiful results in analysis, and it might be a clue as to why you can’t find a polynomial that hits every prime. But just maybe, you could use the constructive version of the SWT (which employs things called Bernstein Polynomials) to find even more impressive prime-generating polynomials than the one above.
Thinking about it a little more, maybe we shouldn’t be so surprised that no polynomial can hit every prime. Consider this: the spacings between the primes get very large, growing (on average) at the same pace as the natural log function, which is an unbounded function. So for example, there are two consecutive primes whose distance apart exceeds a billion. On the other hand, sometimes huge primes can be right by each other, and if the Twin Prime Conjecture is true, that kind of behavior happens again and again. Therefore, a curve C(t) which passes through every point of the form (n,p) - n a natural number, p a prime - typically features constantly changing acceleration for all time, sometimes leaping or plunging a huge distance from t = n to n + 1, and other times staying at nearly the same level. Polynomials just don’t do this; eventually their leading term “dominates” all the lower-order terms, and they take on monotonic behavior. Unfortunately this thought experiment doesn’t quite rule out hypothetical polynomials which could just “get lucky” and keep hitting prime values after this monotonicity kicks into action. The distance from one of these prime values to the next would necessarily be growing much faster than the natural log function, so they couldn’t possibly hit every consecutive prime. Easiest case down!
