Polynomial decomposition

Short description: Factorization under function composition

In mathematics, a polynomial decomposition expresses a polynomial f as the functional composition [math]\displaystyle{ g \circ h }[/math] 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,

[math]\displaystyle{ f = x^6 - 3 x^3 + 1 }[/math]

decomposes into

[math]\displaystyle{ g = x^2 - 3 x + 1 \text{ and } h = x^3 }[/math]

since

[math]\displaystyle{ f(x) = (g \circ h)(x) = g(h(x)) = g(x^3) = (x^3)^2 - 3 (x^3) + 1, }[/math]

using the ring operator symbol ∘ to denote function composition.

Less trivially,

[math]\displaystyle{ \begin{align} & x^6-6 x^5+21 x^4-44 x^3+68 x^2-64 x+41 \\ = {} & (x^3+9 x^2+32 x+41) \circ (x^2-2 x). \end{align} }[/math]

Uniqueness

A polynomial may have distinct decompositions into indecomposable polynomials where [math]\displaystyle{ f = g_1 \circ g_2 \circ \cdots \circ g_m = h_1 \circ h_2 \circ \cdots\circ h_n }[/math] where [math]\displaystyle{ g_i \neq h_i }[/math] for some [math]\displaystyle{ i }[/math]. 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 [math]\displaystyle{ m = n }[/math], 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, [math]\displaystyle{ x^2 \circ x^3 = x^3 \circ x^2 }[/math].

Applications

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

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

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. For example, using the decomposition

[math]\displaystyle{ \begin{align} & x^6 - 6 x^5 + 15 x^4 - 20 x^3 + 15 x^2 - 6 x - 1 \\ = {} & \left(x^3 - 2\right) \circ \left(x^2 - 2 x + 1\right), \end{align} }[/math]

the roots of this irreducible polynomial can be calculated as

[math]\displaystyle{ 1 \pm 2^{1/6}, 1 \pm \frac{\sqrt{-1 \pm \sqrt{3}i}}{2^{1/3}}. }[/math]

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

[math]\displaystyle{ \begin{align} & x^4 - 8 x^3 + 18 x^2 - 8 x + 2 \\ = {} & (x^2 + 1) \circ (x^2 - 4 x + 1) \end{align} }[/math]

gives the roots

[math]\displaystyle{ 2 \pm \sqrt{3 \pm i} }[/math]

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:

[math]\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} . }[/math]

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. ISBN 1-56881-159-4.