In mathematics, a polynomial decomposition expresses a polynomial f as the functional composition g ∘ h {\displaystyle g\circ h} 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 called indecomposable polynomials of sometimes prime polynomials.[1] (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.[2]
Examples
In the simplest case, one of the polynomials is a monomial. For example,
\( 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,
\( {\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 \( 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][3] For example, x\( x^{2}\circ x^{3}=x^{3}\circ x^{2}. \)
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 \\ = {} & (x^2 - 2) \circ (x^2) \circ (x^2 + x + 1) \end{align} \)
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.[4] For example, using the decomposition
\( {\begin{aligned}&x^{6}-6x^{5}+15x^{4}-20x^{3}+15x^{2}-6x-1\\={}&(x^{3}-2)\circ (x^{2}-2x+1),\end{aligned}} \)
the roots of this irreducible polynomial can be calculated as
\( 1\pm 2^{{1/6}},1\pm {\frac {{\sqrt {-1\pm {\sqrt {3}}i}}}{2^{{1/3}}}} \).[5]
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{aligned}&x^{4}-8x^{3}+18x^{2}-8x+2\\={}&(x^{2}+1)\circ (x^{2}-4x+1)\end{aligned}}
gives the roots
\( 2\pm {\sqrt {3\pm i}} \)[5]
but straightforward application of the quartic formula gives equivalent results but in a form that is difficult to simplify and difficult to understand:
\( {\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 computer algebra system.[8] That algorithm takes worst-case exponential time but works independently of the characteristic of the underlying field.
More recent algorithms run in polynomial time but with restrictions on the characteristic.[9]
The most recent algorithm calculates a decomposition in polynomial time and without restrictions on the characteristic.[10]
Notes
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
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
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
The examples below were calculated using Maxima.
Where each ± is taken independently.
David R. Barton, Richard Zippel, "Polynomial Decomposition Algorithms", Journal of Symbolic Computation 1:159–168 (1985)
Richard Zippel , "Functional Decomposition" (1996) full text
Available in its open-source successor, Maxima, see the polydecomp function
Dexter Kozen, Susan Landau, "Polynomial Decomposition Algorithms", Journal of Symbolic Computation 7:445–456 (1989)
Raoul Blankertz, "A polynomial time algorithm for computing all minimal decompositions of a polynomial", ACM Communications in Computer Algebra 48:1 (Issue 187, March 2014) full text Archived 2015-09-24 at the Wayback Machine
References
Joel S. Cohen, "Polynomial Decomposition", Chapter 5 of Computer Algebra and Symbolic Computation, 2003, ISBN 1-56881-159-4
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
