Integer Polynomial Lattice

We now know that any integer polynomial specified by a vector _a_ in Z^n as

(1) p(x) = a_(n-1) x^(n-1) + a_(n-2) x^(n-2) + … + a_2 x^2 + a_1 x + a_0

can also be specified by a vector _b_ in Z^n as

(2) p(x) = b_0 + b_1 x + b_2 (x | 2) + b_3 (x | 3) + … + b_(n-2) (x | n-2) + b_(n-1) (x | n-1)

where b_i = p^[i](0), the value at zero of the i-th pseudo-derivative of p(x).  It is also possible to demonstrate integer polynomials for any given _b_ for which there is no corresponding _a_, for example, _b_ = [0, 0, 1] in Z^3, i.e., p(x) = (x | 2) = x(x-1)/2.

Now we shall construct a polynomial lattice to demonstrate some of the continuity between polynomials of degree n and polynomials of the next higher or lower degree.

Begin with a given vector _b_ in Z^n, specifying a polynomial p(x) as in (2) above.  We further specify some new notation as follows:

_b`_ (read as “vector b downshift”) is a vector shift notation with values as follows: b`_0 = b_1, b`_1 = b_2, …, b`_n-3 = b_n-2, b`_n-2 = b_n-1, b`_n-1 = 0.

_b^(-k)_ (read as “vector b chopped by k”) contains values as follows: b^(-k)_0 = b_0, b^(-k)_1 = b_1, …, b^(-k)_n-k-1 = b_n-k-1, b^(-k)_n-k = 0, b^(-k)_n-k+1 = 0, …, b^(-k)_n-2 = 0, b^(-k)_n-1 = 0

With the _b`_ notation, we will also apply the _b^[i]_ notation to denote the i-th vector-shift of _b_.

The _b`_ or _b^[i]_ and _b^(-k)_ notations may be used simultaneously as _(b^[i])^(-k)_.  The order does not matter, the last k elements will be chopped to 0 prior to the downshift.

Let p(x; _a_, b, c) be an integer polynomial in x parametrized by _a_, b and c which is specified as follows:

p(x; _a_, b, c) = a_0 + a_1 (x | 1) + a_2 (x | 2) + … + a_n-2 (x | n-2) + a_n-1 (x | n-1) + b(c | n)

We use p(x; _b_, 0, 0) as the starting point of the lattice.

First, we have r(x; y) = p(x, _b^(-1)_, b_n-1, y) is the set of polynomials such that for any given x_0, p(x_0; _b_, 0, 0) = r(x_0; x_0).  This creates one axis of our lattice.

Next, we choose a value k to parametrize a second axis as follows:

q(x; k) = p(x; _b_ + (k | 1) _(b^[1])^(-1)_ + (k | 2) _(b^[2])^(-1)_ + … + (k | k-2) _(b^[k-2])^(-1)_ + (k | k-1) _(b^[k-1])^(-1)_ + _(b^[k])^(-1)_, 0, 0)

This specification identifies q(x; k) as having the same value as r(x+k; x).

Given these definitions, it is possible to identify every value of p(x; _b_, 0, 0) using polynomials of degree n-2, namely r(x; y), and it is further possible to specify the values of each of those polynomials by the values of q(x; k).  r(x; y) is degree n-2 and q(x; k) is degree n-1, demonstrating that the two sets of polynomials cover the result set differently, but in the end they both cover exactly the same result space.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s