Overview

A polynomial u(x) is called a composite polynomial if there are polynomials v(w) and w(x), both with degree greater than one, such that u is represented by the functional composition u(x)=v(w(x)). The composite expression v(w(x)) is also called a decomposition of u in terms of the components v(w) and w(x), and the process for finding v and w is called decomposing a polynomial. For example,

is a composite polynomial with decomposition given by

Decomposition plays an important role in the solution of polynomial equations. For example, to solve

first solve the equation for w(x)= x ² to obtain x ²=2, 3, and then solve these equations to obtain . Most computer algebra systems apply decomposition as part of the solution of polynomial equations.

It is easy to recognize that u(x) in Equation (5.1) is a composite polynomial. With more involved examples, however, a decomposition may not be apparent or even possible. For example,

can be decomposed as

while u(x)+ x cannot be decomposed at all.

How can we determine if a polynomial can be decomposed? Surprisingly, there are some simple algorithms that do the job. In Section 5.1 we describe the basic theoretical concepts of polynomial decomposition, and in Section 5.2 we describe an algorithm that either finds a decomposition for u(x) (if one exists) or determines that no such decomposition is possible.

5.1 Theoretical Background

In this...