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.