g\circh
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]
In the simplest case, one of the polynomials is a monomial. For example,
f=x6-3x3+1
decomposes into
g=x2-3x+1andh=x3
since
f(x)=(g\circh)(x)=g(h(x))=g(x3)=(x3)2-3(x3)+1,
using the ring operator symbol ∘ to denote function composition.
Less trivially,
\begin{align} &x6-6x5+21x4-44x3+68x2-64x+41\\ ={}&(x3+9x2+32x+41)\circ(x2-2x). \end{align}
A polynomial may have distinct decompositions into indecomposable polynomials where
f=g1\circg2\circ … \circgm=h1\circh2\circ … \circhn
gi ≠ hi
i
Joseph Ritt proved that
m=n
x2\circx3=x3\circx2
A polynomial decomposition may enable more efficient evaluation of a polynomial. For example,
\begin{align} &x8+4x7+10x6+16x5+19x4+16x3+10x2+4x-1\\ ={}&\left(x2-2\right)\circ\left(x2\right)\circ\left(x2+x+1\right) \end{align}
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} &x6-6x5+15x4-20x3+15x2-6x-1\\ ={}&\left(x3-2\right)\circ\left(x2-2x+1\right), \end{align}
the roots of this irreducible polynomial can be calculated as[5]
1\pm21/6,1\pm
\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
\begin{align} &x4-8x3+18x2-8x+2\\ ={}&(x2+1)\circ(x2-4x+1) \end{align}
gives the roots[5]
2\pm\sqrt{3\pmi}
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:
2-{
| ||||||
33/2 |
+72\right)2/3+36\left(
8\sqrt{10 | |
i}{3 |
3/2
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]