Prime Polynomials

Primes are of interest. Indeed, I would go so far as to say they are the stereotypical Object of Interest people think of when they think about mathematics.

When writing posts like these, I’m never really sure how basic to go. I’ve been tempted at times to define what functions are, for example. One of my goals in writing about math is to make it as accessible as possible, and I’m pretty sure I fail a lot at that, but then again I don’t want to go so basic I can’t talk about anything of interest.

The point is, it will satisfy me enough to say, primes are integer numbers that are only divisible by themselves and 1. 2, 3, 5, 7, 101 are classic examples, while 10 is very much not prime.

Primes are of interest for many reasons, but they tickle the fancy of many due to their rather inexplicable nature. For example, the distribution of primes, where they fall on the number line, while being highly structured, seems largely without form or pattern. We can’t really predict what numbers are prime, where they are, or how many there are in a certain range.

Something that would be nice would be a function that generates just prime numbers. Now, given a set of prime numbers, like 2, 3, 5, 7, you can construct, for example, a polynomial f(x) such that f(1) = 2, f(2) = 3, f(3) = 5, f(4) = 7, and so on. An excellent example of such a thing is f(n) = n² + n + 41, which produces primes for n = 0 to n = 40. Do you see why f(41) is not prime, though?

So the question is, in general, can you construct a polynomial that only gives prime numbers on integer inputs?

f(41) is not prime because 41² + 41 + 41 is clearly divisible by, at the very least, 41.

As it turns out, any polynomial that returns primes for integer inputs must be a constant. That is, f(n) = p for all values of n.

Consider the following arbitrary polynomial, of degree n.

f(x) = a_n*xⁿ + a_n-1*x^n-1 + … + a₁*x + a₀

Notice, importantly, that there are a finite number of terms. We’re dealing strictly with finite polynomials, though I might as well address infinite polynomials. All in due time.

Now, we assume that f(x) gives primes for integer inputs. So, we’ll say that f(1) = p, for some prime p. Another way of looking at that statement is to say that p evenly divides the terms of the sum when x is evaluated at 1.

Now we have f(1) = p. Plugging in x = 1 to our polynomial expression, this says

f(1) = a_n + a_n-1 + … + a₁ + a₀ = p

So, consider f(1 + m*p), for some integer m.

f(1 + m*p) is a sum of terms of the form a_i*(1 + m*p)ⁱ. Notice though, that (1 + m*p)ⁱ, when divided by p, gives a remainder of 1. If you don’t see this right off, notice that multiplying out 1 + m*p that many times yields something of the form 1 + M_i*p, for some horrendously complicated value of M_i. You may also want to see this post.

As (1 + m*p)ⁱ gives a remainder of 1 when divided by p, we can write it in the form, as I said, 1 + M_i*p, for some complicated value of M_i. Then consider,

a_i*(1 + m*p)ⁱ = a_i*(1 + M_i*p)

a_i*(1 + m*p)ⁱ = a_i + M_i*p*a_i

a_i*(1 + m*p)ⁱ = a_i + M’_i*p

The point being that a_i*(1 + m*p)ⁱ is a_i plus some multiple of p.

f(1 + m*p) can then be written as

f(1 + m*p) = (a_n + M’_n*p) + … + (a₁ + M’₁*p) + (a₀ + M’₀*p)

We can then simplify this to

f(1 + m*p) = (a_n + … + a₀) + p*(M’_n + … + M’₀)

But remember, the sum of the a_i’s is just f(1)! Thus, and combining all those M’s into one big M’,

f(1 + m*p) = f(1) + p*M’

But we said that f(1) = p! Thus,

f(1 + m*p) = p + p*M’

Quite clearly then, for any integer m, f(1 + m*p) is divisible by p. But, if we assumed that f(x) is prime, and thus not divisible by anything but itself and 1, it must be the case that f(1 + m*p) = p.

Since this is true for any integer m, f(x) = p an infinite number of times at every p’th integer from x = 1. If f(x) is of finite degree, as we said it was, this is a contradiction, requiring that f(x) in fact be of infinite degree, unless f(x) = p for -all- values of x.

Therefore, any polynomial that generates only primes on the integers, must be constant, generating the same prime each time. So ends the lesson?

Now, one of the things this proof relied upon was that f(x) be of finite degree. Polynomials of infinite degree can achieve a single value an infinite number of times. Sin(x) could be thought of as an infinite degree polynomial, and Sin(x) = 0 an infinite number of times, for example. However, I believe you can show that if f(x) is of infinite degree, and generates only primes on the integers, it must generate a finite number of prime numbers, repeating them over and over again. For example, (1/2)( Cos(Pi*n) + 5 ) generates, for integer n, 2, 3, 2, 3, etc. This will require a bit of Diophantus, I believe. Something to think about. But now, there’s work to be done elsewhere.