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.

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.

Divisibilty Among Polynomials

In the previous post, I demonstrated the beginnings of “divisibility theory”.  Here are some more formal ideas to support the example shown there.

First, it is necessary to establish some definitions.

Let _x_ be the representation of a vector called x.  For a variable c specified as a constant (or a literal constant, e.g. 0), let _c_ = [c, c, c, …, c] or _0_ = [0, 0, 0, …, 0].  Let the context supply the size of such a vector, such as “a polynomial p in k variables” followed by a reference to “p(_x_)” would imply that _x_ is of size k.

“Divisible under n” – the reasons for this term will become more clear with examples; an integer polynomial p in k variables (where k > 1) may be said to be “divisible under n” for a given integer n > 1 if and only if the only point where p(_x_) == 0 (mod n) is exactly when _x_ == _0_ (mod n).

(1) For every n such that n is prime or square-free, there exists a polynomial p in k variables such that p is divisible under n.

(2) For a given n, if a polynomial p exists such that there is exactly one solution p(_x_) == 0 (mod n) but _x_ != _0_ (mod n), then a polynomial q exists which is divisible under n.  It can be shown that q is a linear transform of p along each variable represented in _x_.

(3) For a given n, if a polynomial p exists such that there is exactly one solution p(_x_) == u (mod n), then p(_x_) – u (mod n) is a polynomial satisfying (2).

Functional Encoding of Images

Given a source of data in k-dimensional form, it is possible to construct a modular function which represents the data.

For example, let k=2.  It is possible to take any image with any color depth and write a function which generates the image by supplying coordinates as the parameters of the function.  Here is a simple “image”, shown as color values at coordinate locations:

x \ y | 0 1 2 3 4

———————-

0      | 1 1 1 1 1

1      | 1 0 0 0 1

2      | 1 0 0 0 1

3      | 1 0 0 0 1

4      | 1 1 1 1 1

Using a prime modulus is the only way to ensure that the entire image can be encoded correctly; this modulus applies both to the “color depth”, i.e., the range of values that can appear at each coordinate location, and to the “width” and “height” of the image created by the function.

The “image” shown above can be encoded to a function as follows:

For a 5×5 image with all “colors” having value <= 5, use 5 as the modulus.  To get zeroes in the center, use (x-1)(x-2)(x-3)(y-1)(y-2)(y-3).  The remaining challenge is to force the outer ring to be all ones.  If x=0 or x=4, then (x-1)(x-2)(x-3) is -6 or +6, which is -1 or +1 mod 5.  Similarly, if y=0 or y=4, then (y-1)(y-2)(y-3) is -1 or +1 mod 5.  So the simplest solution is to square our previous result, which will force all values to 1 mod 5:

f(x,y) = ((x-1)(x-2)(x-3)(y-1)(y-2)(y-3))^2 (mod 5) is the 5×5 square with boundary size 1.

Clearly this was a very simple image to create a function for, but it serves to demonstrate the basic principles in operation.  It is also probably obvious that expanding this polynomial to coefficient-exponent form will yield some terms with exponent > 4, which can be reduced modulo 5.

Non-prime moduli can be used, but it may be more difficult or in many cases impossible to generate arbitrary images.

One usage for this particular approach to images is as a tiling procedure; since the basic operation is “modulus” there is no need to “copy and paste” to create a tiling effect, the image will simply repeat naturally as a consequence of the function.