HOME

TheInfoList



OR:

In mathematics, a polynomial decomposition expresses a
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
''f'' as the
functional composition In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
g \circ h of polynomials ''g'' and ''h'', where ''g'' and ''h'' have
degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathematics ...
greater than 1; it is an algebraic
functional decomposition In mathematics, functional decomposition is the process of resolving a functional relationship into its constituent parts in such a way that the original function can be reconstructed (i.e., recomposed) from those parts by function composition. ...
.
Algorithms In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...
are known for decomposing
univariate polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
s in
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
. Polynomials which are decomposable in this way are composite polynomials; those which are not are indecomposable polynomials or sometimes prime polynomials J.F. Ritt, "Prime and Composite Polynomials", ''Transactions of the American Mathematical Society'' 23:1:51–66 (January, 1922) (not to be confused with
irreducible polynomial In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted ...
s, which cannot be factored into products of polynomials). The degree of a composite polynomial is always a
composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
, 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 In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered: # A monomial, also called power product, is a product of powers of variables with nonnegative integer exponent ...
. For example, :f = x^6 - 3 x^3 + 1 decomposes into :g = x^2 - 3 x + 1 \text h = 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 ∘ to denote
function composition In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
. Less trivially, : \begin & 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


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 Joseph Fels Ritt (August 23, 1893 – January 5, 1951) was an American mathematician at Columbia University in the early 20th century. He was born and died in New York. After beginning his undergraduate studies at City College of New York, Rit ...
proved that m = n, 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, 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 & 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 can be calculated with 3 multiplications and 3 additions using the decomposition, while
Horner's method In mathematics and computer science, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation. Although named after William George Horner, this method is much older, as it has been attributed to Joseph-Louis Lagrange by Hor ...
would require 7 multiplications and 8 additions. A polynomial decomposition enables calculation of symbolic roots using radicals, even for some
irreducible polynomial In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted ...
s. This technique is used in many
computer algebra systems A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The de ...
. For example, using the decomposition : \begin & 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 the roots of this irreducible polynomial can be calculated asWhere each ± is taken independently. :1 \pm 2^, 1 \pm \frac. Even in the case of
quartic polynomial In algebra, a quartic function is a function (mathematics), function of the form :f(x)=ax^4+bx^3+cx^2+dx+e, where ''a'' is nonzero, which is defined by a polynomial of Degree of a polynomial, degree four, called a quartic polynomial. A ''qua ...
s, where there is an explicit formula for the roots, solving using the decomposition often gives a simpler form. For example, the decomposition : \begin & x^4 - 8 x^3 + 18 x^2 - 8 x + 2 \\ = & (x^2 + 1) \circ (x^2 - 4 x + 1) \end gives the roots : 2 \pm \sqrt but straightforward application of the
quartic formula In algebra, a quartic function is a function of the form :f(x)=ax^4+bx^3+cx^2+dx+e, where ''a'' is nonzero, which is defined by a polynomial of degree four, called a quartic polynomial. A ''quartic equation'', or equation of the fourth degr ...
gives equivalent results but in a form that is difficult to simplify and difficult to understand; one of the four roots is: : 2-- .


Algorithms

The first algorithm for polynomial decomposition was published in 1985, though it had been discovered in 1976,Richard Zippel
Functional Decomposition
1996.
and implemented in the
Macsyma Macsyma (; "Project MAC's SYmbolic MAnipulator") is one of the oldest general-purpose computer algebra systems still in wide use. It was originally developed from 1968 to 1982 at MIT's Project MAC. In 1982, Macsyma was licensed to Symbolics and ...
/ Maxima
computer algebra system A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The de ...
. That algorithm takes exponential time in worst case, but works independently of the characteristic of the underlying
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
. 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.


Notes


References

* {{cite book , author=Joel S. Cohen , chapter=Chapter 5. Polynomial Decomposition , title=Computer Algebra and Symbolic Computation , year=2003 , isbn=1-56881-159-4 Polynomials Computer algebra