From: kubo@jacobi.math.brown.edu (Tal Kubo)
Newsgroups: sci.math
Subject: Re: commuting polynomials
Date: 26 Feb 1998 04:45:00 GMT

David Spear <spear@empty.set> wrote:
>Which pairs of polynomials f,g commute uder composition?

In characteristic 0 the basic possibilities are: (a) powers of X,
(b) Chebyshev polynomials, (c) some iterate of f = some iterate of g.
This is up to linear changes of variable and some (restricted) rescalings
such as multiplying the powers of X by appropriate roots of unity. 

If you allow rational functions there are also examples coming
from  elliptic curves (i.e., multiplication-by-N maps considered
as rational functions of X when the curve is written Y^2=f(X) ).

In characteristic p>0 there are other possibilities (Frobenius, 
Dickson polynomials) but no classification as far as I know.

>
>Is this a well known problem?

Yes and no. It was solved by the old fathers, and the 
powers-or-Chebyshev alternative is famous, but there's
no "well known" source where the full classification of
possible  f,g  pairs is stated explicitly.  If I remember
correctly it's mentioned in Rivlin's book on Chebyshev 
polynomials and you may be able to locate a reference there.

==============================================================================

From: boyd@mahler.math.ubc.ca (David Boyd)
Newsgroups: sci.math
Subject: Re: commuting polynomials
Date: 26 Feb 1998 21:44:00 GMT

In article <6d2s0c$22s@cocoa.brown.edu>,
Tal Kubo <kubo@jacobi.math.brown.edu> wrote:
>
>
>>Is this a well known problem?
>
>Yes and no. It was solved by the old fathers, and the 
>powers-or-Chebyshev alternative is famous, but there's
>no "well known" source where the full classification of
>possible  f,g  pairs is stated explicitly.  If I remember
>correctly it's mentioned in Rivlin's book on Chebyshev 
>polynomials and you may be able to locate a reference there.
>

The result is due to J.F. Ritt, ``Permutable rational
functions'', Trans. Amer. Math. Soc. 25 (1923), 399--448, and
involves a consideration of the possible branch points of certain 
Riemann surfaces.   The crucial point about  x^n  is that it
has only one critical level, i.e. 0  while the Chebyshev 
polynomials have only two critical levels, i.e. 1 and -1.

For a more elementary approach but a less complete result,
see Block and Thielman, ``Commutative polynomials'', Quart. J.
Math. Oxford Ser. (2) v.2 (1951), 241--243.
  
David Boyd