Polynomial decomposition

Short description: Factorization under function composition

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; 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 (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.

Examples

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

$f(x)=x^6-3x^3+1$

decomposes into $g\circ h$, where

$g(x)=x^2-3x+1\text{ and }h(x)=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 $\circ$ to denote function composition. We write that as

$x^6-3x^3+1=(x^2-3x+1)\circ (x^3)$

treating the polynomials implicitly as functions of $x$.

Less trivially,

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

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\ne 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. For example, $x^2\circ x^3=x^3\circ x^2$. In fact, only three kinds of position swap are possible: between monomials; between Chebyshev polynomials $T_i(x)$; and between $(x^{k}u{\left(x\right)}^p,x^p)\leftrightarrow (x^p,x^{k}u\left(x^p\right))$— summarized as "Every polynomial can be written as a composition of indecomposables, uniquely up to permutations and units." For example:

$x^{14}{(x^{98}+1)}^2=\left(x{(x^7+1)}^2\right)\circ \left(x^7\right)\circ \left(x^2\right)=\left(x^2\right)\circ \left(x(x^{14}+1)\right)\circ \left(x^7\right)$

$T_2(x)\circ T_3(x)=T_3(x)\circ T_2(x)=32x^6-48x^4+18x^2-1$

Applications

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

$\begin{array}{rl}& x^8+4x^7+10x^6+16x^5+19x^4+16x^3+10x^2+4x-1\\ =& (x^2-2)\circ \left(x^2\right)\circ (x^2+x+1)\end{array}$

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 of degree greater than 4. This technique is used in many computer algebra systems. For example, using the decomposition

$\begin{array}{rl}& x^6-6x^5+15x^4-20x^3+15x^2-6x-1\\ =& (x^3-2)\circ (x^2-2x+1),\end{array}$

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

In the case of quartic polynomials, if there is a decomposition, it can give a simpler form than the general formula. For example, the decomposition

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

gives the roots

$2\pm \sqrt{3\pm i}$

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

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

Algorithms

The first algorithm for polynomial decomposition was published in 1985, though it had been discovered in 1976, and implemented in the Macsyma/Maxima computer algebra system. 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.

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

References

• Joel S. Cohen (2003). "Chapter 5. Polynomial Decomposition". Computer Algebra and Symbolic Computation: Mathematical Methods. ISBN 1-56881-159-4.