Polynomial functors VI. An elementary question about polynomials When does there exist a natural transformation between two polynomial functors P and Q? This question is motivated by the usefulness of polynomial functors for functional programming. However, this question can be formulated as a question about multivariate polynomials, with no reference to functional programming or category theory.
For our present consideration, we only admit polynomials with
natural (positive integer!) coefficients, using a countably infinite set of variables a, b, c, ..., x, y, z, ...
The usual algebraic rules hold, e.g. (x+y)z = xz+yz, x+y=y+x, xy=yx, etc. This is the usual commutative semiring of polynomials, except that all coefficients must be natural integers.
For example, 1 + axy + 2bz is an admissible polynomial. Examples of inadmissible polynomials are 3/2 + y (non-integer coefficient), 0 (non-positive coefficient), and 1 - x (negative coefficient).
We define a relation between polynomials that we call "transformability". A polynomial P is
transformable into a polynomial Q (written P ~> Q) if one of these cases hold:
1. P is any polynomial while Q is a constant polynomial (containing only a positive integer and no variables). For example, P ~> 1 for any P, and also P ~> 2, P ~> 3, etc.
2. If either R ~> Q or S ~> Q then R*S ~> Q.
3. If both R ~> Q and S ~> Q then R+S ~> Q.
4. x ~> x (the same variable).
5. P is a monomial (no sum), and either P ~> R or P ~> S, then P ~> R + S.
6. P ~> R and P ~> S, then P ~> R*S.
I'd like to be able to characterize in a visual and simple way all the polynomials P and Q for which P ~> Q. So far I was able to find specific cases of this.
For example, x ~> x*x (rules 4 and 6). However, we do not have 1+x ~> x because we do not have 1 ~> x, which would be required by rule 3.
More generally, P ~> x iff P = x*R where R is another polynomial. Also, x ~> P iff P = x^n + R (where x^n = x*x*...*x, the factor x being repeated zero or more times). Furthermore, obviously P ~> P for any P.
The relation P ~> Q is superficially similar to "P is divisible by Q", in the sense of polynomial division; but it is not an equivalent condition. If P is divisible by Q, i.e. if P = Q*A, then we have P ~> Q by rule 2. But the converse does not hold: P ~> Q does not imply that P is divisible by Q.
How can we characterize all the polynomials P and Q for which P ~> Q holds?
Here's a more intuitive explanation of what P ~> Q means:
We need the notion of "having a value of type P". If P is a constant such as 4, we always have a value of type P. If P is a sum such as P = A + B then we have a value of type P if we have a value of type A or a value of type B. If P is a product such as P = A*B then we have a value of type P if we have both a value of type A and a value of type B. If P=x,
a priori we do not have a value of type x.
Now, P ~> Q means that we can compute a value of type Q if we have a value of type P. For example,
1 + x ~> 1 + x*x
Given a value of type 1+x, we are required to produce a value of type 1 + x*x, which means we are required to either produce a value of type 1 or a value of type x*x. We are given a value of type 1+x, which means either we have a value of type 1 or a value of type x. If we have a value of type 1, we can certainly produce 1. If we have a value of type x, we can produce x*x (by just duplicating the value of type x that we have).