Correction to Polynomial Lattice

In a previous posting, I created a “polynomial lattice” out of structures found within the Pascal Triangle.  I have found some errors and boundary gaps within the definition I created.

Rather than post differences between the two, I claim that this post has Precedence.  The previous posting is now superseded.

Given a polynomial p(x) specified by a vector _b_ in Z^n as p(x) = b_0 + b_1(x | 1) + b_2(x | 2) + … + b_n-2(x | n-2) + b_n-1(x | n-1), the integer polynomial lattice surrounding p(x) is simply specified as q(x; y) = p`(x) + p(y); r(x; z) = p(x) + p`(z).  This lattice is simple, covers all the necessary bases, and achieves exactly what is required of it:  it is a lattice interleaving one set of polynomials with another; the balance of a polynomial and its parallels and the lattice-pairing of each of these is perfect; no gaps are admitted within the given parameters of the lattice, including boundaries such as when _b_ is an almost-zero vector.

The previous lattice definition allowed for many possibilities of error, and was also incorrectly specified.  Under this definition, it is possible to have _b_ = {0, 0, …, 0, 0, 1}, and to also have a viable lattice useful for determining many properties of p(x).

Advertisements

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.

The Pseudo-Anti-Derivative

Like Calculus, these “finite difference” methods also apply in the reverse direction, i.e., there is also a “pseudo-anti-derivative” which is the reverse of the “pseudo-derivative” process.

Given an integer polynomial p(x), let the pseudo-anti-derivative of p be marked as ‘p(x).  The value of ‘p(x) is unknown, since we must know the value of ‘p(0) to determine it.  This fits nicely with how our other methods operate, so use ‘p(0) to denote this unknown value.  Also, let (x/k) be my representation of the binomial term “x choose k”:

‘p(x) = ‘p(0) + p(0)*(x/1) + p`(0)*(x/2) + …

To show that this is a correct “pseudo-anti-derivative,” we calculate ‘p(x+1) – ‘p(x):

‘p(x+1)-‘p(x) = p(0)(((x+1)/1) – (x/1)) + p`(0)*(((x+1)/2) – (x/2)) + …

= p(0)*1 + p`(0)*(x/1) + p“(0)*(x/2) + …

Note that ((x+1)/k) – (x/k) = (x/(k-1)).  Since this is what the above proof is based on, here is why it’s true:

((x+1)/k) – (x/k) = (x+1)x(x-1)(x-2)…(x-k+2)/k! – x(x-1)(x-2)(x-3)…(x-k+1)/k! = (x+1 – (x-k+1)) * x(x-1)(x-2)…(x-k+2)/k! = kx(x-1)(x-2)…(x-k+2)/k! = (x/(k-1)).

This form of “anti-derivative” creates polynomials with all-integer results, but does not have the restriction that all coefficients are integers.  For example, if p(x) = x + 1, p(0) = p`(0) = 1, then:

‘p(x) = ‘p(0) + x + x(x-1)/2 = ‘p(0) + x/2 + x^2/2.

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.