Polynomial decomposition

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

:$f\; =\; x^6\; -\; 3\; x^3\; +\; 1$

decomposes into

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

since

:$f(x)\; =\; (g\; \backslash 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{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}

A polynomial may have distinct decompositions into indecomposable polynomials where $f\; =\; g\_1\; \backslash circ\; g\_2\; \backslash circ\; \backslash cdots\; \backslash circ\; g\_m\; =\; h\_1\; \backslash circ\; h\_2\; \backslash circ\; \backslash cdots\backslash circ\; h\_n$ where $g\_i\; \backslash 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.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}} For example, $x^2\; \backslash circ\; x^3\; =\; x^3\; \backslash circ\; x^2$.

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. This technique is used in many computer algebra systems.The examples below were calculated using Maxima. 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 asWhere each ± is taken independently.

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

& 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

:$2\; \backslash pm\; \backslash sqrt\{3\; \backslash 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:

:$2-\{\; \backslash frac\{\backslash sqrt\{\{\{\; 9\; \backslash left(\backslash frac\{8\; \backslash sqrt\{10\}\; i\}\{3^\{3/2\}\}\; +\; 72\backslash right)^\{2/3\}\; +\; 36\; \backslash left(\backslash frac\{8\; \backslash sqrt\{10\}\; i\}\{3^\{3/2\}\}\; +\; 72\backslash right)^\{1/3\}\; +\; 156\}\; \backslash over\; \{\backslash left(\{\backslash frac\{8\; \backslash sqrt\{10\}\; i\}\{3^\{3/2\}\}\}\; +\; 72\backslash right)^\{1/3\}\}\}\}\}\; 6\}-\{\{\backslash sqrt\{-\backslash left(\backslash frac\{8\; \backslash sqrt\{10\}\; i\}\{3^\{3/2\}\}\; +\; 72\backslash right)^\{1/3\}-\{\{52\}\backslash over\{3\; \backslash left(\backslash frac\{8\; \backslash sqrt\{10\}\; i\}\{3^\{3/2\}\}\; +72\backslash right)^\{1/3\}\}\}\; +\; 8\}\}\backslash over\; 2\}\; .$

The first algorithm for polynomial decomposition was published in 1985,{{cite journal |author=David R. Barton, Richard Zippel |title=Polynomial Decomposition Algorithms |journal=Journal of Symbolic Computation |volume=1 |pages=159–168 |year=1985|issue=2 |doi=10.1016/S0747-7171(85)80012-2 }} though it had been discovered in 1976,Richard Zippel, [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.3154 Functional Decomposition], 1996. and implemented in the Macsyma/Maxima computer algebra system.See the [https://maxima.sourceforge.io/docs/manual/maxima_76.html#index-polydecomp polydecomp function]. 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.{{cite journal |author=Kozen |first1=Dexter |author-link1=Dexter Kozen |last2=Landau |first2=Susan |author-link2=Susan Landau |year=1989 |title=Polynomial Decomposition Algorithms |journal=Journal of Symbolic Computation |volume=7 |issue=5 |pages=445–456|doi=10.1016/S0747-7171(89)80027-6 |citeseerx=10.1.1.416.6491 }}

A 2014 algorithm calculates a decomposition in polynomial time and without restrictions on the characteristic.{{cite journal |author=Raoul Blankertz |title=A polynomial time algorithm for computing all minimal decompositions of a polynomial |journal=ACM Communications in Computer Algebra |volume=48 |pages=1 |issue=187 |year=2014 |url=http://www.sigsam.org/bulletin/articles/187/Polynomial_time_decomposition_pp13-23.pdf}} {{webarchive|url=https://web.archive.org/web/20150924101735/http://www.sigsam.org/bulletin/articles/187/Polynomial_time_decomposition_pp13-23.pdf |date=2015-09-24 }}

{{reflist|colwidth=30em}}

• {{cite book |author=Joel S. Cohen |chapter=Chapter 5. Polynomial Decomposition |title=Computer Algebra and Symbolic Computation: Mathematical Methods |year=2003 |isbn=1-56881-159-4}}

Category:Polynomials

Category:Computer algebra