Polynomial decomposition

In mathematics, a polynomial decomposition expresses a polynomial f as the functional composition 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]

Examples

edit

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

 

decomposes into

 

since

 

using the ring operator symbol to denote function composition.

Less trivially,

 

Uniqueness

edit

A polynomial may have distinct decompositions into indecomposable polynomials where   where   for some  . 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  , 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.[1][3] For example,  .

Applications

edit

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

 

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

 

the roots of this irreducible polynomial can be calculated as[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

 

gives the roots[5]

 

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:

 

Algorithms

edit

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]

Notes

edit
  1. ^ a b 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. ^ 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
  4. ^ The examples below were calculated using Maxima.
  5. ^ a b Where each ± is taken independently.
  6. ^ 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.
  7. ^ Richard Zippel, Functional Decomposition, 1996.
  8. ^ See the polydecomp function.
  9. ^ Kozen, Dexter; 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.
  10. ^ Raoul Blankertz (2014). "A polynomial time algorithm for computing all minimal decompositions of a polynomial" (PDF). ACM Communications in Computer Algebra. 48 (187): 1. Archived 2015-09-24 at the Wayback Machine

References

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