Polynomial decomposition

In mathematics, a polynomial decomposition expresses a polynomial "f" as the functional composition formula_1 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 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,
decomposes into
since
using the ring operator symbol ∘ to denote function composition.
Less trivially,
Uniqueness.
A polynomial may have distinct decompositions into indecomposable polynomials where formula_6 where formula_7 for some formula_8. 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 formula_9, 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. For example, formula_10.
Applications.
A polynomial decomposition may enable more efficient evaluation of a polynomial. For example,
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. For example, using the decomposition
the roots of this irreducible polynomial can be calculated as
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
gives the roots
but straightforward application of the quartic formula gives equivalent results but in a form that is difficult to simplify and difficult to understand:
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 takes worst-case exponential time 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.