Michael E. Zieve and Peter Müller:

**On Ritt's polynomial decomposition
theorems**,

submitted for publication.
(Prior to publication, this paper should be cited as
arXiv:0807.3578.)

In a classic
paper from 1922,
Ritt
studied the functional decomposition of a univariate complex polynomial
*g* into prime (indecomposable) polynomials,
*g* = *u*_{1} o *u*_{2} o ... o *u*_{r}. His main achievement was a procedure for
obtaining any decomposition of *g* from any other by repeatedly
applying certain transformations. However, Ritt's results provide no control
on the number of times one must apply the basic transformations, which makes
his procedure unsuitable for many theoretical and algorithmic applications.
We solve this problem by giving a new description of the collection of all
decompositions of a polynomial. Our results have been used by
Ghioca, Tucker and Zieve to describe the polynomials
*g,h* having orbits with infinite intersection; they have
also been
used by Medvedev and Scanlon
to describe the affine varieties invariant under a coordinatewise polynomial action.

In particular, we describe a canonical decomposition of any polynomial
*g*, from which one can read off all other decompositions at
a glance. We also give an effective procedure for finding this canonical
decomposition. One consequence of our results is as follows:
if *g* has degree *n*>1 but *g* is not conjugate
by a linear polynomial to either *X*^{n} or *±T*_{n}
(with *T*_{n} the Chebychev polynomial), and if the composition
*a* o *b* of polynomials *a,b* is the
*k*-th iterate of *g* for some
*k* > log_{2}(*n*+2), then either
*a* = *g* o *c* or
*b* = c o *g* for some polynomial *c*.

We also show that, for any decomposition
*g* = *u*_{1} o *u*_{2} o ... o *u*_{r}
into indecomposables *u*_{i}, the sequence of permutation groups
(*G*(*u*_{1}),...,*G*(*u*_{r})) is
determined up to permutation by *g*, where
*G*(*u*)
is the Galois group of *u*(*X*)-*t*
over **C**(*t*).
This generalizes `Ritt's first theorem', which asserts that the sequence
(deg(*u*_{1}),...,deg(*u*_{r})) is determined up
to permutation by *g*, and it also generalizes an invariant discovered by
Beardon
and Ng, which turns out to be equivalent to the subsequence of
cyclic groups among the *G*(*u*_{i}).

*Michael Zieve*:
home page
publication list