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.

Advertisements

Refining (Pseudo-)Derivatives of Integer Polynomials

In the past couple posts, polynomials have taken on some new presentations.  This time, I’ll construct some values of a polynomial using only its values at x=0 of p(x) and all of its pseudo-derivatives.

In particular, I’ve established that p`(x)=p(x+1)-p(x).  This means that p(x+1)=p(x)+p`(x).  This has an expansion matching Pascal’s Triangle, because p(x+2) = p(x)+2p`(x)+p“(x), and p(x+3) = p(x)+3p`(x)+3p“(x)+p“`(x).

This pattern continues across all possible values of p(x).  In fact, it is possible to express every value of p(x) as p(0) + ap`(0) + bp“(0) + … where a, b, … coefficients are the entries of the xth row of Pascal’s Triangle.

Extending Integer Polynomial Pseudo-Derivative Results

Last time, I demonstrated my own definition of an integer polynomial pseudo-derivative and how it can be used to construct the results of the polynomial using only sums.  Now I wish to look closer at some of the columns in the pseudo-derivative tree of the same polynomial: p(x) = ax^3 + bx^2 + cx + d.

Looking back at the previous post, there are four columns in the result portion of the pseudo-derivative tree (the supplied “x” variable is not counted as a result column).

Column 4 is the final nonzero pseudo-derivative for this polynomial, and the column has only 6a in every entry.  Column 3 is more interesting, as it begins with 6a+2b and each successive entry is increased by 6a.  Column 2 is the one I wish to focus on now, and in particular the “a” term of each entry.  After reducing to just the “a” term, the column looks like this:

a

7a

19a

37a

The differences between these terms have already been demonstrated, but now let’s look at the similarities.  In particular, subtract a from all terms, then divide all terms by 6a:

0

1

3

6

The term after 37a is 61a, which reduces to 10 in the final listing.  This further reinforces what is probably obvious:  this sequence is “diagonal row 2” of Pascal’s Triangle, with generating formula k(k+1)/2, which is also the famous set of Triangle numbers.  In fact, column 3 corresponds to “diagonal row 1” of Pascal’s Triangle, and if p(x) were degree 4, we would have a column which corresponds to “diagonal row 3” of Pascal’s Triangle.

This correspondence continues through the entire range of Pascal’s Triangle given polynomials of increasing degree.

Integer Polynomial (Pseudo-)Derivatives

In much of the “common literature”, it is customary to define an “integer polynomial derivative” using the same conventions as the usual sense of “derivative”.  Just like with the customary definition of derivative/anti-derivative, there are other options.

The definition I will use is one I came up with at age 10.  Yes, it is a very simple definition.

Let the “pseudo-derivative” of an integer polynomial p (i.e., a polynomial with integer coefficients and supplied with an integer variable) be defined as p(x+1) – p(x).  Let p`(x) (read “p back-tick of x”) be the representation of the pseudo-derivative of p(x), i.e., p`(x) = p(x+1)-p(x).

This definition allows for certain features that the traditional derivative cannot claim, at least not without modifications beyond this scope.

In particular, when p`(x) is used, it is possible to construct the value of p(x) for any given x using only a sum based on the pseudo-derivatives of p(x) up to the point where p(x)^[n] = 0 (under the convention that x^[n] is the nth pseudo-derivative of x).

Under this definition of pseudo-derivative, many of the same rules apply as to the proper derivative, such as constant multiples pass through unchanged, pseudo-derivative of a sum is the sum of the pseudo-derivatives, however the product rule is no longer effective.  Here it is for proper derivatives:

d/dx(p(x)q(x)) = p'(x)q(x) + p(x)q'(x) + p'(x)q'(x)

Under the usual definition, the third term becomes 0 in the limit that is applied, but here there is no limit.

Other rules are probably different as well, let the reader make note of any that are of interest.

Here’s an example of how this derivative works out:

p(x) = ax^3 + bx^2 + cx +d

x | p(x) | ——————– p(x+1) – p(x) | p`(x+1) – p`(x) | p“(x+1) – p“(x)

0 – d

——————————| a + b + c

1 – a + b + c + d ———————————-| 6a + 2b

——————————| 7a + 3b + c ———————| 6a

2 – 8a + 4b + 2c + d —————————–| 12a + 2b

——————————| 19a + 5b + c ——————-| 6a

3 – 27a + 9b + 3c + d —————————-| 18a + 2b

——————————| 37a + 7b + c

4 – 64a + 16b + 4c + d

The above pseudo-derivative tree applies to any cubic equation; equations of higher degree will have similar trees.  Note that the final column (the nth derivative of an n-degree polynomial) will always be constant, and will have the value a*n!, where a is the coefficient of the highest-degree term.

Using this tree, it is possible to construct any later value in it based only upon the first term in each pseudo-derivative column and the value of p(0).  Simply add the next constant term (in this case, 6a), then add that to the last value in the column next to it (24a + 2b), then repeat the process back through the columns and down in rows until you reach your desired value.