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. 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 (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}-3x^{3}+1$

decomposes into

$g=x^{2}-3x+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{aligned}&x^{6}-6x^{5}+21x^{4}-44x^{3}+68x^{2}-64x+41\\={}&(x^{3}+9x^{2}+32x+41)\circ (x^{2}-2x).\end{aligned}}$

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 \,...\,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.

Applications

A polynomial decomposition enables more efficient evaluation of the polynomial.

A polynomial decomposition enables calculation of symbolic roots (using radicals) of some irreducible polynomials.

Algorithms

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

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

References

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