Polynomial decomposition

In mathematics, a polynomial decomposition expresses a polynomial f as the functional composition ${\displaystyle 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,

${\displaystyle f=x^{6}-3x^{3}+1}$

decomposes into

${\displaystyle g=x^{2}-3x+1{\text{ and }}h=x^{3}}$

since

${\displaystyle 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,

${\displaystyle {\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 ${\displaystyle f=g_{1}\circ g_{2}\circ \cdots \circ g_{m}=h_{1}\circ h_{2}\circ \cdots \circ h_{n}}$ where ${\displaystyle g_{i}\neq h_{i}}$ for some ${\displaystyle 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 ${\displaystyle m=n}$, and the degrees of the components are the same, but possibly in different order; this is Ritt's polynomial decomposition theorem.^[1][3] For example, ${\displaystyle x^{2}\circ x^{3}=x^{3}\circ x^{2}}$.

Applications

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

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

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

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

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

${\displaystyle 1\pm 2^{1/6},1\pm {\frac {\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

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

gives the roots^[5]

${\displaystyle 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:

${\displaystyle 2-{\frac {\sqrt {{9\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{2/3}+36\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}+156} \over {\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}}}}{6}}-{{\sqrt {-\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}-{{52} \over {3\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}}}+8}} \over 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/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]