Consider the integer polynomials with nonnegative coefficients, such as:
$$ 1 + 2x +2x^2 $$ $$ 3 + 3x^4 + 11x^{10}$$ $$ 13 + 7x + x^2 $$
I asm interested in knowing "what is a composition factorization" of any such polynomial. For example,
$$ 13 + 7x + x^2 = 1 + (x+3) + (x+3)^2 = (1 + x + x^2) \leftarrow (x+3) $$
But the that solution I presented is artificial, in that I created it just to show it. Here's my question,
given a polynomial with natural number coefficients, how do I find a chain of compositions for that polynomial such that every element in the chain is factorable into another composition chain.
And in doing so, how do I even determine if a polynomial is primitive or can be expressed in some composition chain?
Note that some composition chains could be nested too for example
$$ (x^2 + x \leftarrow x+1) \leftarrow (x^3 + x^2 \leftarrow x^2 +1) $$
Which describes
$$ (x+1)^2 + (x+1) \leftarrow (x^2 + 1)^3 + (x^2+1)^2 $$
For first order polynomials $ax + k$ there will be compositions into "primitive" (indecomposable) functions as follows:
$$ x + k = g^{k}(x) \;\; \text{ where } g(x) = x+1 $$
and:
$$ ax = f_{p_1}(f_{p_2}(\ldots f_{p_m}(x))) $$
where $a = p_1 p_2 \ldots p_m$ is a prime factorization.