(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₁ o u₂ 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ⁿ 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₂(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₁ o u₂ o ... o u_r  into indecomposables  u_i,  the sequence of permutation groups (G(u₁),...,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₁),...,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