Polynomial decomposition

In mathematics, a polynomial decomposition expresses a polynomial f as the functional composition $g \circ h$ of polynomials g and h, where g and h have degree greater than 1.^[1] Algorithms are known for decomposing polynomials in polynomial time.

Polynomials which are decomposable in this way are composite polynomials; those which are not are prime or indecomposable polynomials^[2] (not to be confused with irreducible polynomials, which cannot be factored into products of polynomials).

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.$

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 \cdots \circ g_m = h_1 \circ h_2 \circ \cdots\circ h_n$ where $g_i \neq 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, but possibly in different order; this is Ritt's polynomial decomposition theorem.^[2][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 \\ = {} & (x^2 - 2) \circ (x^2) \circ (x^2 + x + 1) \end{align}$

can be calculated with only 3 multiplications using the decomposition, while Horner's method would require 7.

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 \\ = {} & (x^3 - 2) \circ (x^2 - 2 x + 1) \end{align}$,

the roots of this irreducible polynomial can be calculated as

$1 \pm 2^{1/6}, 1 \pm \frac{\sqrt{-1 \pm \sqrt{3}i}}{2^{1/3}}$.^[5]

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

$2 \pm \sqrt{3 \pm i}$^[5]

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

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

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 computer algebra system.^[8] That algorithm took worst-case exponential time but worked independently of the characteristic of the underlying field.

More recent algorithms ran in polynomial time but with restrictions on the characteristic.^[9]

The most recent algorithm calculates a decomposition in polynomial time and without restrictions on the characteristic.^[10]

Notes

1. Composition of polynomials may also be thought of as substitution of one polynomial as the value of the variable of another.
2. J.F. Ritt, "Prime and Composite Polynomials", Transactions of the American Mathematical Society 23:1:51-66 (January, 1922) doi:10.2307/1988911 JSTOR 1988911
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) doi:10.1016/0022-4049(90)90086-W
4. The examples below were calculated using Maxima.
5. Where each $\pm$ is taken independently.
6. David R. Barton, Richard Zippel, "Polynomial Decomposition Algorithms", Journal of Symbolic Computation 1:159–168 (1985)
7. Richard Zippel , "Functional Decomposition" (1996) full text
8. Available in its open-source successor, Maxima, see the polydecomp function
9. Dexter Kozen, Susan Landau, "Polynomial Decomposition Algorithms", Journal of Symbolic Computation 7:445–456 (1989)
10. Raoul Blankertz, "A polynomial time algorithm for computing all minimal decompositions of a polynomial", ACM Communications in Computer Algebra 48:1 (Issue 187, March 2014) full text

References

• Joel S. Cohen, "Polynomial Decomposition", Chapter 5 of Computer Algebra and Symbolic Computation, 2003, ISBN 1-56881-159-4