analytics

Friday, November 4, 2011

Tell if a series is generated by a Polynomial with integer coefficents

Theorem: A series of integers is generated by a polynomial P(x) with integer coefficients if for every choice of x:
m mod P(x) = m mod P(x+m)
Proof: Consider the polynomials:
P(x) = a*x^n + b*x^(n-1) + ... + k
P(x+m) = a*(x+m)^n + b*(x+m)^(n-1)+...+k
When P(x+m) is expanded, there are two types of terms, those that do not contain m and those that do. The collection of terms that do not contain m are exactly those terms found in P(x). The rest we said all divide m. Therefore:
P(x+m) = P(x) + m*(B(x)) for some polynomial B(x) with integer coefficients.
So whatever the remainder of P(x) when divided by m is, because m*(B(x)) divides m evenly and B(x) is an integer at any x,  P(x+m) will have the same remainder when divided by m.

In practice what that means is if you look at a series of integers, and then the remainders when divided by for example 3, if it produces a pattern that repeats over and over again every 3 remainders it is produced by a polynomial with integer coefficients.
  For example:
 3*x^3 + 2*x^2 + x + 4 for x from 1 to 10 has remainders when divided by 3 of:


1,2,1,1,2,1,1,2,1

This pattern repeats every 3 as it should.

Try a random series:
5,12,21,27,35,45
The remainders when divided by 3:
2,0,0,0,2,0
Since this pattern does not repeat every 3 it can't be formed by any polynomial with integer coefficents. Of course there is a polynomial going through these 6 points for x from 0 to 6 but it is:
 5-(7/6)*x+(5/3)*x^4+(43/3)*x^2-(185/24)*x^3-(1/8)*x^5
It doesn't have all integer coefficients.

Now I'm not sure if this result has ever been discovered before, thanks to Dr. Rose for the idea for the proof that I've tried to generalize here.

No comments:

Post a Comment