Permutable polynomials

Two polynomials p(x) and q(x) are said to be permutable if

p(q(x)) = q(p(x))

for all x. It's not hard to see that Chebyshev polynomials are permutable.

First,

T_n(x) = cos (n arccos(x))

where T_n is the nth Chebyshev polyomial. You can take this as a definition, or if you prefer another approach to defining the Chebyshev polynomials it's a theorem.

Then it's easy to show that

T_m(T_n(x)) = T_mn (x).

because

cos(m arccos(cos(n arccos(x)))) = cos(mn arccos(x)).

Then the polynomials T_m and T_n must be permutable because

T_m(T_n(x)) = T_mn (x) = T_n(T_m(x))

for all x.

There's one more family of polynomials that are permutable, and that's the power polynomials x^k. They are trivially permutable because

(x^m)ⁿ = (xⁿ)^m.

It turns out that the Chebyshev polynomials and the power polynomials are essentially [1] the only permutable sequence of polynomials.

• Generalization of power polynomials
• Product of Chebyshev polynomials
• The Brothers Markov

[1] Here's what essentially" means. A set of polynomials, at least one of each positive degree, that all permute with each other is called a chain. Two polynomials p and q are similar if there is an affine polynomial

(x) = ax + b

such that

p(x) = ^-1( q( (x) ) ).

Then any permutable chain is similar to either the power polynomials or the Chebyshev polynomials. For a proof, see Chebyshev Polynomials by Theodore Rivlin.

The post Permutable polynomials first appeared on John D. Cook.