Fun with Newton polynomials
by t0rajir0u, Dec 10, 2007, 1:59 AM
The standard method of representing a polynomial 
is with coefficients attached to terms of the form 
, like so:
.
Such a representation of a polynomial is very useful if one wants to do calculus or apply Vieta's formulas to find out something about the roots, but there are number-theoretic reasons we might prefer a different representation.
- A polynomial which returns integer values at integer arguments need not have integer coefficients. For example,
is integer at integer values of 
.
- The forward difference operator
is useful for problems that only give values for 
at integers, but it is messy to calculate using the above representation. (More generally, in an interpolation problem we do not necessarily want to invert a Vandermonde matrix.)
So what to do? In the language of vector spaces, we are using
as a basis for the space of polynomials over some ring (the "standard basis"). This basis makes representing the derivative (as a linear operator) fairly straightforward. We would like a correspondingly straightforward representation of the forward difference operator for solving certain problems.
The answer is to use a different basis. For a given non-negative integer
, denote 
(where 
, the empty product). These are binomial coefficients with a general argument (which are used in the General Binomial Theorem), or the Newton polynomials. We can use
as a polynomial basis, which addresses both of the concerns we had above.
Lemma 1: Given a polynomial
in "Newton form," is integer for integer values of if and only if 
is an integer for 
.
Proof: The left direction is easy. If is integer then so is 
(for integer ). To prove the right direction, it suffices to consider 
and work inductively. We claim by strong induction that is an integer for . When 
,
so our base case is true. Suppose we have shown that
are integers. Then
and since the first terms of the expression are integers, 
is an integer. This concludes the proof.
The next lemma makes dealing with polynomials that take integer values at integer arguments even easier.
Lemma 2: If, then
Proof: This is an immediate consequence of the combinatorial identity
, which can be proven for general algebraically.
Now for some problems.
Problem 1: Find a closed formula for
for a particular small .
Solution: A demonstration for
. Other small cases follow similarly.
Our goal is to write
in the form 
. To do so, it's enough to consider 
and apply a similar process as in the proof of Lemma 1.
.
.
.
.
.
Hence
and
by the Hockeystick identity (which can be viewed as a corollary of Lemma 2).
Remark: In general, the coefficients of in Newton form are given by
where
are the Stirling numbers of the second kind. This gives the identity
which is given in Engel; compare with Faulhaber's formula.
Problem 2: A polynomial of degree 
satisfies 
for 
. Find 
.
Solution: If we try to calculate the coefficients of in Newton form, we might recall the identity 
. Indeed, verify that
is the unique polynomial that satisfies the problem conditions. (When
, the later terms cancel to zero.) Thus
.
Alternately, if we attempt to generally find a polynomial
such that 
, noting that 
makes a proof by induction quite simple.
Remark: All we really did in this problem was interpolate. It was the choice of Newton polynomials rather than the standard basis that made the interpolation easy to calculate. Note that Lagrange interpolation would've taken much longer to simplify.
Practice Problem (USAMO 1984): A polynomial of degree 
satisfies
and
. Find all possible values of 
.
is with coefficients attached to terms of the form 
, like so:
.Such a representation of a polynomial is very useful if one wants to do calculus or apply Vieta's formulas to find out something about the roots, but there are number-theoretic reasons we might prefer a different representation.
- A polynomial which returns integer values at integer arguments need not have integer coefficients. For example,
is integer at integer values of 
.- The forward difference operator
is useful for problems that only give values for 
at integers, but it is messy to calculate using the above representation. (More generally, in an interpolation problem we do not necessarily want to invert a Vandermonde matrix.)So what to do? In the language of vector spaces, we are using
as a basis for the space of polynomials over some ring (the "standard basis"). This basis makes representing the derivative (as a linear operator) fairly straightforward. We would like a correspondingly straightforward representation of the forward difference operator for solving certain problems.The answer is to use a different basis. For a given non-negative integer
, denote 
(where 
, the empty product). These are binomial coefficients with a general argument (which are used in the General Binomial Theorem), or the Newton polynomials. We can use
as a polynomial basis, which addresses both of the concerns we had above.
Lemma 1: Given a polynomial
in "Newton form," is integer for integer values of if and only if 
is an integer for 
.Proof: The left direction is easy. If
is integer then so is 
(for integer ). To prove the right direction, it suffices to consider 
and work inductively. We claim by strong induction that is an integer for . When 
,
so our base case is true. Suppose we have shown that
are integers. Then
and since the first
terms of the expression are integers, 
is an integer. This concludes the proof.The next lemma makes dealing with polynomials that take integer values at integer arguments even easier.
Lemma 2: If
, then
Proof: This is an immediate consequence of the combinatorial identity
, which can be proven for general algebraically.Now for some problems.
Problem 1: Find a closed formula for
for a particular small .Solution: A demonstration for
. Other small cases follow similarly.Our goal is to write
in the form 
. To do so, it's enough to consider 
and apply a similar process as in the proof of Lemma 1.
.
.
.
.
.Hence
and
by the Hockeystick identity (which can be viewed as a corollary of Lemma 2).
Remark: In general, the coefficients of
in Newton form are given by
where
are the Stirling numbers of the second kind. This gives the identity
which is given in Engel; compare with Faulhaber's formula.
Problem 2: A polynomial
of degree 
satisfies 
for 
. Find 
.Solution: If we try to calculate the coefficients of
in Newton form, we might recall the identity 
. Indeed, verify that
is the unique polynomial that satisfies the problem conditions. (When
, the later terms cancel to zero.) Thus
.Alternately, if we attempt to generally find a polynomial
such that 
, noting that 
makes a proof by induction quite simple.Remark: All we really did in this problem was interpolate. It was the choice of Newton polynomials rather than the standard basis that made the interpolation easy to calculate. Note that Lagrange interpolation would've taken much longer to simplify.
Practice Problem (USAMO 1984): A polynomial
of degree 
satisfies
and
. Find all possible values of 
.
as a basis for the space of polynomials over some ring"... It should be Field, not Ring. Because, you would then speak in the language of modules. 
April 2009
March 2009