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; 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][3][4]

Examples

In the simplest case, one of the polynomials is a monomial. For example,

f(x) = x^6 - 3 x^3 + 1

decomposes into g \circ h, where

g(x) = x^2 - 3 x + 1 \text{ and } h(x) = x^3

since

f(x) = (g \circ h)(x) = g(h(x)) = g(x^3) = (x^3)^2 - 3 (x^3) + 1,

using the ring operator symbol \boldsymbol{\circ} to denote function composition. We write that as

x^6 - 3 x^3 + 1 = (x^2 - 3 x + 1) \circ (x^3)

treating the polynomials implicitly as functions of x.

Less trivially,

\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}

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 \cdots\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.[1][5] For example, x^2 \circ x^3 = x^3 \circ x^2. In fact, only three kinds of position swap are possible: between monomials; between Chebyshev polynomials T_i(x); and between \left(x^{k}\,u\left(x\right)^{p} , x^{p}\right)\leftrightarrow \left(x^{p} , x^{k}\,u\left(x^{p}\right)\right)— summarized as "Every polynomial can be written as a composition of indecomposables, uniquely up to permutations and units."[6] For example:

x^{14}\, \left(x^{98}+1\right)^2 = \left( x\,\left(x^7+1\right)^2 \right) \circ \left( x^7 \right) \circ\left( x^2 \right) = \left(x^2 \right) \circ \left(x\,\left(x^{14}+1\right)\right) \circ \left(x^7\right)
T_2(x) \circ T_3(x) = T_3(x) \circ T_2(x) = 32\,x^6-48\,x^4+18\,x^2-1

Applications

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

\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}

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 of degree greater than 4. This technique is used in many computer algebra systems.[7] For example, using the decomposition

\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}

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

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

In the case of quartic polynomials, if there is a decomposition, it can give a simpler form than the general formula. For example, the decomposition

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

gives the roots[8]

2 \pm \sqrt{3 \pm i}

but straightforward application of the quartic formula gives a form that is difficult to simplify and difficult to understand; one of the four roots is:

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,[9] though it had been discovered in 1976,[10] and implemented in the Macsyma/Maxima computer algebra system.[11] 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.[12]

A 2014 algorithm calculates a decomposition in polynomial time and without restrictions on the characteristic.[13]

Notes

  1. ^ J.F. Ritt, "Prime and Composite Polynomials", Transactions of the American Mathematical Society 23:1:51–66 (January, 1922) doi:10.2307/1988911 JSTOR 1988911
  2. ^ Jean-Charles Faugère, Ludovic Perret, "An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography", Journal of Symbolic Computation, 44:1676-1689 (2009), doi:10.1016/j.jsc.2008.02.005
  3. ^ Zhao, Shangwei; Feng, Ruyong; Gao, Xiao-Shan (2012-04-01). "On functional decomposition of multivariate polynomials with differentiation and homogenization". Journal of Systems Science and Complexity. 25 (2): 329–347. doi:10.1007/s11424-012-1144-8. ISSN 1559-7067
  4. ^ von zur Gathen, Joachim & Ziegler, Konstantin (2015), "Survey on Counting Special Types of Polynomials", Computer Algebra and Polynomials: Applications of Algebra and Number Theory, Gutierrez, Jaime (ed.), Cham: Springer International Publishing, pp. 50–75, doi:10.1007/978-3-319-15081-9_3. ISBN 978-3-319-15081-9, retrieved 2025-07-14
  5. ^ Capi Corrales-Rodrigáñez, "A note on Ritt's theorem on decomposition of polynomials", Journal of Pure and Applied Algebra 68:3:293–296 (6 December 1990) doi:10.1016/0022-4049(90)90086-W
  6. ^ Medvedev, Alice & Scanlon, Thomas (August 31, 2018). "Ritt's Theorem and refinements". DART XI (Differential Algebra and Related Topics)
  7. ^ The examples below were calculated using Maxima.
  8. ^ Where each ± is taken independently.
  9. ^ David R. Barton, Richard Zippel (1985). "Polynomial Decomposition Algorithms". Journal of Symbolic Computation. 1 (2): 159–168. doi:10.1016/S0747-7171(85)80012-2
  10. ^ Richard Zippel, Functional Decomposition, 1996.
  11. ^ See the polydecomp function.
  12. ^ Kozen & Landau, Susan (1989). "Polynomial Decomposition Algorithms". Journal of Symbolic Computation. 7 (5): 445–456. CiteSeerX 10.1.1.416.6491. doi:10.1016/S0747-7171(89)80027-6
  13. ^ Raoul Blankertz (2014). "A polynomial time algorithm for computing all minimal decompositions of a polynomial". ACM Communications in Computer Algebra. 48 (187): 1. Archived 2015-09-24 at the Wayback Machine

References

  • Joel S. Cohen (2003). "Chapter 5. Polynomial Decomposition". Computer Algebra and Symbolic Computation: Mathematical Methods. ISBN 1-56881-159-4.