Polynomial decomposition explained

g \circ h of polynomials g and h, where g and h have degree greater than 1; it is an algebraic functional decomposition. Algorithms are known for decomposing univariate polynomials in polynomial time.

Polynomials which are decomposable in this way are composite polynomials; those which are not are indecomposable polynomials or sometimes prime polynomials^[1] (not to be confused with irreducible polynomials, which cannot be factored into products of polynomials). The degree of a composite polynomial is always a composite number, the product of the degrees of the composed polynomials.

The rest of this article discusses only univariate polynomials; algorithms also exist for multivariate polynomials of arbitrary degree.^[2]

Examples

In the simplest case, one of the polynomials is a monomial. For example,

f = x ^{6} - 3 x ^{3} + 1

decomposes into

g = x ^{2} - 3 x + 1 and h = x ^{3}

since

f(x) = (g \circ h)(x) = g(h(x)) = g(x ^{3)} = (x ^{3)} ^{2} - 3 (x ^{3)} + 1 ,

using the ring operator symbol ∘ to denote function composition.

Less trivially,

\begin{align} & x ^{6-6} x ^{5+21} x ^{4-44} x ^{3+68} x ^{2-64} x +41 \\ = {} & (x ^{3+9} x ^{2+32} x +41 ) \circ (x ^{2-2} x). \end{align}

Uniqueness

A polynomial may have distinct decompositions into indecomposable polynomials where

f = g _{1} \circ g _{2} \circ … \circ g _{m} = h _{1} \circ h _{2} \circ … \circ h _{n} where g _{i} ≠ h _{i} for some i . The restriction in the definition to polynomials of degree greater than one excludes the infinitely many decompositions possible with linear polynomials.

Joseph Ritt proved that

m = n , and the degrees of the components are the same up to linear transformations, but possibly in different order; this is Ritt's polynomial decomposition theorem.^{[1] [3]} For example, x ^{2} \circ x ^{3} = x ^{3} \circ x ^{2} .

Applications

A polynomial decomposition may enable more efficient evaluation of a polynomial. For example,

\begin{align} & x ^{8} + 4 x ^{7} + 10 x ^{6} + 16 x ^{5} + 19 x ^{4} + 16 x ^{3} + 10 x ^{2} + 4 x - 1 \\ = {} & \left(x ^{2} - 2 \right) \circ \left(x ^{2\right)} \circ \left(x ^{2} + x + 1 \right) \end{align} can be calculated with 3 multiplications and 3 additions using the decomposition, while Horner's method would require 7 multiplications and 8 additions.

A polynomial decomposition enables calculation of symbolic roots using radicals, even for some irreducible polynomials. This technique is used in many computer algebra systems.^[4] For example, using the decomposition

\begin{align} & x ^{6} - 6 x ^{5} + 15 x ^{4} - 20 x ^{3} + 15 x ^{2} - 6 x - 1 \\ = {} & \left(x ^{3} - 2 \right) \circ \left(x ^{2} - 2 x + 1 \right), \end{align}

the roots of this irreducible polynomial can be calculated as^[5]

1 \pm 2 ^{1/6} , 1 \pm (\sqrt{ -1 \pm \sqrt{ 3)/(i}}{ 2) ^{1/3} }.

Even in the case of quartic polynomials, where there is an explicit formula for the roots, solving using the decomposition often gives a simpler form. For example, the decomposition

\begin{align} & x ^{4} - 8 x ^{3} + 18 x ^{2} - 8 x + 2 \\ = {} & (x ^{2} + 1 ) \circ (x ^{2} - 4 x + 1 ) \end{align}

gives the roots^[5]

2 \pm \sqrt{ 3 \pm i}

but straightforward application of the quartic formula gives equivalent results but in a form that is difficult to simplify and difficult to understand; one of the four roots is:

2- { (\sqrt{{{ 9 \left( (8 \sqrt{ 10)/(i))/(3 ^{3/2}) + 72 \right) ^{2/3} + 36 \left( (8 \sqrt{ 10)/(i}{ 3) ^{3/2} } + 72\right)^ + 156} \over }}} 6}- .

Algorithms

The first algorithm for polynomial decomposition was published in 1985,^[6] though it had been discovered in 1976,^[7] and implemented in the Macsyma/Maxima computer algebra system.^[8] That algorithm takes exponential time in worst case, but works independently of the characteristic of the underlying field.

A 1989 algorithm runs in polynomial time but with restrictions on the characteristic.^[9]

A 2014 algorithm calculates a decomposition in polynomial time and without restrictions on the characteristic.^[10]

References

• Book: Joel S. Cohen . Chapter 5. Polynomial Decomposition . Computer Algebra and Symbolic Computation . 2003 . 1-56881-159-4.

Notes and References

1. [Joseph Ritt|J.F. Ritt]
2. Jean-Charles Faugère, Ludovic Perret, "An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography", Journal of Symbolic Computation, 44:1676-1689 (2009),
3. Capi Corrales-Rodrigáñez, "A note on Ritt's theorem on decomposition of polynomials", Journal of Pure and Applied Algebra 68:3:293–296 (6 December 1990)
4. The examples below were calculated using Maxima.
5. Where each ± is taken independently.
6. David R. Barton, Richard Zippel . Polynomial Decomposition Algorithms . Journal of Symbolic Computation . 1 . 159–168 . 1985. 2 . 10.1016/S0747-7171(85)80012-2 .
7. Richard Zippel, Functional Decomposition, 1996.
8. See the polydecomp function.
9. Kozen . Dexter . Dexter Kozen . Landau . Susan . Susan Landau . 1989 . Polynomial Decomposition Algorithms . Journal of Symbolic Computation . 7 . 5 . 445–456. 10.1016/S0747-7171(89)80027-6 . 10.1.1.416.6491 .
10. Raoul Blankertz . A polynomial time algorithm for computing all minimal decompositions of a polynomial . ACM Communications in Computer Algebra . 48 . 1 . 187 . 2014 .