3

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.

hardmath
  • 37,015
Sidharth Ghoshal
  • 16,771
  • So if we bar the use of the identity function since any polynomial can P can be expressed as $x \leftarrow P$ and vice versa, then consider:any constant C, it can be expressed as $x + C \leftarrow 0$ and we can deconstruct the $x + C$ repeatedly until we get the expression $$ x + 1 \leftarrow x+1 \leftarrow ... \leftarrow x +1 \leftarrow 0 $$. So then an example of a prototypical primitive polynomial is $x+1$. Is there a way to make that polynomial, using the composition of other polynomials with natural number coefficients (excluding the identity and itself)? – Sidharth Ghoshal Jul 18 '15 at 23:01
  • If you find some good example of why the notion isn't well founded I would like to read it, as I may be overlooking some detail. But all i'm asking is a factorization of the polynomial using other polynomials involving natural number coefficients that doesn't include the polynomial itself. – Sidharth Ghoshal Jul 18 '15 at 23:03
  • I think in case of high powers of x, the one choice can be determining the simple roots. and then deviding – Cardinal Jul 18 '15 at 23:23
  • Letting $p(x) = x+2$ and $q(x) = x-1$ we can express $x+1 = q(p(x))$, so some restriction beyond excluding the identity and the polynomial itself is needed to develop a notion of undecomposable. – hardmath Jul 18 '15 at 23:24
  • @Charles found a good reference in this previous Question, Polynomial Composition. – hardmath Jul 18 '15 at 23:40
  • 1
    @hardmath x-1 is not a valid polynomial in my list. Since -1 isn't a natural number – Sidharth Ghoshal Jul 19 '15 at 00:36
  • @hardmath suggest that the OP type in a complete answer for $ax+b$ and $a x^2 + bx+c,$ as i have no idea what is being discussed – Will Jagy Jul 19 '15 at 21:37
  • 1
    @WillJagy: I sketched the first order cases in the Question, the additive part of which is copied from the OP's first Comment. The quadratic polynomials are probably an interesting threshold case. – hardmath Jul 19 '15 at 22:29
  • An older paper, by J.F. Ritt (1922), Prime and Composite Polynomials, discusses unique lengths of composition sequences but in a broader context than as here. – hardmath Jul 19 '15 at 22:51

0 Answers0