New York Journal of Mathematics

New York J. Math. 13 (2007) 89–96.

Commuting polynomials and self-similarity

Karl Zimmermann

Abstract. Let F be an algebraically closed field of characteristic 0 and f(x) a polynomial of degree strictly greater than one in F [x]. We show that the number of degree k polynomials with coefficients in F that commute with f (under composition) is either zero or equal to the number of degree one polynomials with coefficients in F that commute with f. As a corollary, we obtain a theorem of E. A. Bertram characterizing those polynomials commuting with a Chebyshev polynomial.

Contents

1. Introduction and summary of results 89 2. Commuting polynomials 91 References 96

1. Introduction and summary of results

In the early 1920s, G. Julia [5] and J. F. Ritt [6] used topological and algebraic methods to study complex rational functions in one variable and in particular, those that commute under composition of functions. Even though their results are difficult to prove, the theorem classifying those polynomials that commute under composition is relatively easy to state and understand. We begin with a review of the ideas necessary to state the classification theorem. The review will provide context for our main results, most of which are related to the Julia–Ritt theorem but are obtained here using elementary techniques. Even though some of the results and definitions to follow make sense in a more general setting, for clarity of exposition, we make the assumption throughout the paper, that F is an algebraically closed field of characteristic 0, for example, the field of complex numbers.

Recall that the Chebyshev polynomials of the first kind, T_{n}(x) where n ≥ 1, are defined via

T_{n}(x) = cos n(cos^{−1}(x)).

In particular,

89^{ISSN 1076-9803/07}

Received October 1, 2006.

Mathematics Subject Classification. 12Y05.

Key words and phrases. Polynomial, commute, field, root of unity, Chebyshev polynomial.

T_{1}(x) = x
T_{2}(x) = 2x^{2} − 1
T_{3}(x) = 4x^{3} − 3x
⋮
T_{n}(x) = 2xT_{n−1}(x) − T_{n−2}(x).

Using the defining equation above, it is easy to verify that T_{n} ∘ T_{m} = T_{m} ∘ T_{n} for all m, n ≥ 1. Note also that the recursion formula shows that T_{n} has degree n, leading coefficient 2^{n−1} (for n ≥ 1), and that T_{n} is a sum of odd (respectively, even) powers of x when n is odd (respectively, even). This last clause can be restated: as a function on [−1, 1], T_{n} is an odd function when n is odd, an even function when n is even.

Conjugation by a degree one polynomial will prove to be a useful tool in studying commuting polynomials. Note that it is precisely the polynomials λ(x) = ax + b ∈ F [x], a ≠ 0 that are invertible in F [x] under composition.

Definition 1.1. Let P (x), Q(x) ∈ F [x]. Then P is similar to Q if and only if there exists λ(x) = ax + b ∈ F [x], a ≠ 0 so that Q(x) = λ^{−1}(P (λ(x))). If f(x) ∈ F [X] is similar to itself via λ(x) ∈ F [x] then λ is said to be a self-similarity of f. We let S_{f} denote the set of self-similarities of f.

Some easy consequences of the definition of similarity are:

(1) Similarity is an equivalence relation

(2) If P is similar to Q then deg(P) = deg(Q)

(3) If f commutes with P, then λ^{−1}(f(λ(x))) commutes with λ^{−1}(P (λ(x)))

(4) S_{f} is a group under the operation of composition.

Like the set of Chebyshev polynomials, the set {P_{n}(x) = x^{n}}_{n≥1} of monic mononomials, consists of pairwise commuting polynomials. These two sets play a major role in the classification theorem of Ritt and Julia.

Theorem 1.2 (Ritt–Julia). Let P (x) and Q(x) be nonlinear, nonconstant polynomials with coefficients in the complex numbers that commute under composition. Then one of the following holds:

(1) P and Q are similar, via the same map λ, to Chebyshev polynomials.

(2) P and Q are similar, via the same map λ, to monomials.

(3) There exists a polynomial G(x) = xR(x^{r}) where R(x) is a polynomial, such that P and Q are similar, via the same λ, to ϵ_{1}G^{a}(x) and ϵ_{2}G^{b}(x) where ϵ_{1} and ϵ_{2} are r^{th} roots of unity and G^{a} = G ∘ G ∘ ⋯ ∘ G, the a-fold iterate of G under composition.

Julia replaces (3) above with:

(3′) There exist positive integers ν and μ such that P^{ν} = Q^{μ}.

For more about the statement of the above theorem and the relationship of commuting polynomials to Julia sets, please see [1].

A set of pairwise commuting polynomials containing one polynomial of each positive degree is called a chain. It is a consequence of Theorem 1.2 that up to similarity, there are exactly two chains, namely the Chebyshev polynomials and the monic monomials. Since the proof of the Ritt–Julia theorem is rather difficult, it is worth noting that in 1951, H. D. Block and H. P. Thielman [3] gave an elementary proof of this result for chains defined over an integral domain containing the integers. In 1955, E. J. Jacobsthal [4] also gave an elementary proof.

Given a polynomial, it is natural to ask about the set of polynomials with which it commutes. To be more precise, we make the following definition.

Definition 1.3. Let k ≥ 1. For f(x) ∈ F [x], we let C_{k}(f) denote the set of degree k polynomials in F [x] that commute with f.

Our main result describes a relationship between C_{k}(f), k ≥ 1 and C_{1}(f) = S_{f}, the group of self-similarities of f.

Theorem 2.9. Let f(x) be a polynomial of degree strictly greater than one in F [x] and suppose that C_{k}(f) is nonempty for some k ≥ 1. Then the number of elements in C_{k}(f) is the order of the group S_{f}.

Theorem 2.9 follows from a more general theorem relating commuting polynomials and self-similarities.

Theorem 2.7. Let f(x) be a polynomial in F [x] of degree n > 1 and assume P, Q ∈ C_{k}(f) for some k ≥ 1. Then Q = λ_{f} ∘ P where λ_{f} ∈ S_{f}.

Using Theorem 2.9, we also obtain an easy proof of the known result that a polynomial of degree n > 1 with coefficients in F can commute with at most n − 1 polynomials of fixed degree k ≥ 1 with coefficients in F (Corollary 2.10). To illustrate Corollary 2.10 and motivate our final result, note that the monomial P_{n}(x) commutes with R_{k,j}(x) = ρ^{j}x^{k}, j = 1, …, n−1, where ρ is a primitive (n−1)^{st} root of unity. By Corollary 2.10, there can be no other degree k polynomials commuting with P_{n}. For the Chebyshev polynomials, it is clear that T_{n}(x) commutes with ±T_{k}(x) if n is odd, and T_{k}(x) if n is even, but it is not immediately obvious whether or not there are other polynomials of degree k with which T_{n} commutes. It turns out that there are no others, and Bertram [2] gives an elementary proof of this fact using a differential equation satisfied by the Chebyshev polynomials. Below, we give a different proof of Bertram’s theorem (our Theorem 2.15), which follows as a corollary to Theorem 2.9 and Corollary 2.14.

Corollary 2.14. Let f(x) be a polynomial in F [x] of degree strictly greater than one and let m > 1 be an integer. Then S_{f} has m elements if and only if f is similar to a polynomial of the form xg(x^{m}) with g(x) ∈ F [x] but not similar to any polynomial of the form xh(x^{r}) where h(x) ∈ F [x] and r > m.

2. Commuting polynomials

We begin with the observation that if f is similar to g via the similarity λ, then for k ≥ 1, there is a mapping, Φ_{k} : C_{k}(f) → C_{k}(g) defined by Φ_{k}(P) = λ^{−1} ∘ P ∘ λ, where P ∈ C_{k}(f). For each k ≥ 1, Φ_{k} is easily seen to be a bijection. Moreover, Φ_{1} : C_{1}(f) → C_{1}(g) is an isomorphism of groups; in other words, the self-similarity groups S_{f} and S_{g} are isomorphic.

This observation will be particularly useful when used in conjunction with the following definition and proposition.

Definition 2.1. The polynomial f(x) = ∑_{k=0}^{n} a_{k}x^{k} is centered if a_{n} ≠ 0 and a_{n−1} = 0.

In the proof below, we use the notation O(x^{k}) to denote any polynomial with degree less than or equal to k.

Proposition 2.2. Let f(x) be a polynomial in F [x] of degree n > 1. Then f is similar to a monic, centered polynomial.

Proof. Let f(x) = ∑_{j=0}^{n} a_{j}x^{j} and let g be similar to f via λ(x) = ax + b. A compu-

tation shows

g(x) = a^{n−1}a_{n}x^{n} + a^{n−2}(na_{n}b + a_{n−1})x^{n−1} + O(x^{n−2}).

For g to be monic, let a be an (n − 1)^{st} root of a_{n}^{−1}. For g to be centered, let

b = −\frac{a_{n−1}}{na_{n}} .  □

The following proposition and corollary focus on polynomials that commute with a centered polynomial.

Proposition 2.3. Let f(x) be a polynomial in F [x] of degree n > 1 and P an element of C_{k}(f) for some k ≥ 1. Assume f is monic and centered and P (x) = ∑_{i=0}^{k} b_{i}x^{i}. Then:

(1) For some j = 1, 2, …, n − 1, b_{k} = ρ^{j} where ρ is a primitive (n − 1)^{st} root of unity.

(2) b_{k−1} = 0.

Proof. The first result follows easily by comparing the degree kn coefficients in f ∘ P = P ∘ f. Using this result and comparing the degree kn − 1 coefficients yields the second. □

Corollary 2.4. Let f(x) be a polynomial in F [x] of degree n > 1 and P (x) ≠ x an element of C_{k}(f) for some k ≥ 1. Then f is centered if and only if P is centered.

Proof. Assume f is centered. By the proof of Proposition 2.2, f is similar to a monic polynomial via λ(x) = ax. Such a similarity does not affect centering, so without loss of generality, we may assume f is centered and monic. Then P is centered by part (2) of Proposition 2.3.

A similar argument proves the converse unless deg(P) = 1, that is, unless P (x) = bx, where b ≠ 0, 1. However, if f(x) = a_{n}x^{n} + a_{n−1}x^{n−1} + O(x^{n−2}), and a_{n} ≠ 0 and a_{n−1} ≠ 0 then f(bx) = bf(x) yields b^{n} = b = b^{n−1} which implies b = 0, 1. Thus, f must be centered. □

Corollary 2.5. Let f(x) be a monic, centered polynomial in F [x] of degree n > 1. Then any self-similarity λ of f, is of the form λ(x) = ρ^{j}x where ρ is a primitive (n − 1)^{st} root of unity.

Proof. Since f commutes with λ, this follows immediately from Proposition 2.3. □

Corollary 2.6. Let f(x) be a polynomial in F [x] of degree n > 1. Then the order of S_{f} is less than or equal to n − 1.

Proof. By Proposition 2.2, f is similar to a monic, centered polynomial g. The result follows since the order of S_{f} equals the order of S_{g} which is less than or equal to n − 1 by Corollary 2.5. □

This sets the stage for the main results of the paper.

Theorem 2.7. Let f(x) be a polynomial in F [x] of degree n > 1 and assume P, Q ∈ C_{k}(f) for some k ≥ 1. Then Q = λ_{f} ∘ P where λ_{f} ∈ S_{f}.

Proof. By Proposition 2.2, f is similar to a monic, centered polynomial g via a similarity λ(x) ∈ F [x]. If g(x) = x^{n} + ∑_{m=0}^{n−2} a_{m}x^{m} and P̂ = λ^{−1}P λ and Q̂ = λ^{−1}Qλ, then, using Proposition 2.3, we see that

P̂(x) = ρ^{i}x^{k} + ∑_{m=0}^{k−2} b_{m}x^{m} and

Q̂(x) = ρ^{j}x^{k} + ∑_{m=0}^{k−2} c_{m}x^{m},

where all coefficients of the polynomials are in F and ρ is a primitive (n − 1)^{st} root of unity. Let α = j − i; we will show that Q̂ = ρ^{α}P̂ and that λ_{g}(x) = ρ^{α}x is a self-similarity of g.

To that end, let r(x) = ρ^{α}P̂(x) − Q̂(x), and note that deg(r(x)) = t < k or r(x) = 0. Then, setting a_{n} = 1 and a_{n−1} = 0, we have

r(g(x)) = ρ^{α}P̂(g(x)) − Q̂(g(x)) = ρ^{α}g(P̂(x)) − g(Q̂(x))

= ρ^{α} ∑_{m=0}^{n} a_{m}(P̂(x))^{m} − ∑_{m=0}^{n} a_{m}(Q̂(x))^{m}

= a_{n}(ρ^{α}(P̂(x))^{n} − (Q̂(x))^{n}) + O(x^{k(n−2)})

= (ρ^{α}P̂(x) − Q̂(x))( ∑_{s=0}^{n−1}(ρ^{α}P̂(x))^{n−1−s}(Q̂(x))^{s}) + O(x^{k(n−2)}).

Note that

deg [ ∑_{s=0}^{n−1}(ρ^{α}P̂(x))^{n−1−s}(Q̂(x))^{s}] = k(n − 1),

since the leading coefficient, that is, the degree k(n − 1) coefficient, is

∑_{s=0}^{n−1}(ρ^{α})^{n−1−s}(ρ^{i})^{n−1−s}(ρ^{j})^{s} = ∑_{s=0}^{n−1}(ρ^{j})^{n−1−s}(ρ^{j})^{s} = ∑_{s=0}^{n−1} 1 = n.

Comparing degrees in the two sides of the equation for r(g(x)), we see that tn = deg(r(g(x))) = t + k(n − 1), which implies that t = k. This is a contradiction since t < k, and therefore r(x) = 0 and Q̂ = ρ^{α}P̂.

To see that λ_{g}(x) = ρ^{α}x is a self-similarity of g, observe that g(Q̂(x)) = Q̂(g(x)) implies

g(ρ^{α}P̂(x)) = ρ^{α}P̂(g(x)) = ρ^{α}g(P̂(x)).

Letting P̂(x) = u, we have g(ρ^{α}u) = ρ^{α}g(u) as desired.

We define λ_{f} = λ ∘ λ_{g} ∘ λ^{−1} = Φ_{1}^{−1}(λ_{g}) where λ is the similarity chosen at the beginning of the proof and Φ_{1} : S_{f} → S_{g} is the isomorphism described at the beginning of this section. Thus, λ_{f} ∈ S_{f} and λ_{g} = Φ_{1}(λ_{f}) = λ^{−1} ∘ λ_{f} ∘ λ. It follows that

Q̂ = λ_{g} ∘ P̂
λ ∘ Q̂ ∘ λ^{−1} = λ ∘ λ_{g} ∘ P̂ ∘ λ^{−1}
λ ∘ λ^{−1} ∘ Q ∘ λ ∘ λ^{−1} = λ ∘ λ^{−1} ∘ λ_{f} ∘ λ ∘ λ^{−1} ∘ P ∘ λ ∘ λ^{−1}
Q = λ_{f} ∘ P

which completes the proof. □

The idea of the proof above is similar to that used by Rivlin [7, Theorem 4.2, page 194] to prove that a degree 2 polynomial with coefficients in the real numbers can commute with at most one polynomial of a given degree. The generalization of this result to polynomials of arbitrary degree greater than one follows as an easy corollary to Theorem 2.9 below.

Lemma 2.8. Let f(x) and λ(x) be polynomials in F [x] with deg(f) > 1 and deg(λ) = 1. Assume P ∈ C_{k}(f) for some k ≥ 1. Then λ ∘ P ∈ C_{k}(f) if and only if λ ∈ S_{f}.

Proof. Assume λ ∘ P ∈ C_{k}(f), that is, λ ∘ P ∘ f = f ∘ λ ∘ P. Composition with λ^{−1} yields P ∘ f = λ^{−1} ∘ f ∘ λ ∘ P and so

f ∘ P = P ∘ f = λ^{−1} ∘ f ∘ λ ∘ P.

Thus, f = λ^{−1} ∘ f ∘ λ, and λ ∈ S_{f}.

Conversely, assume λ ∈ S_{f}. Then

f ∘ λ ∘ P = λ ∘ λ^{−1} ∘ f ∘ λ ∘ P
= λ ∘ f ∘ P
= λ ∘ P ∘ f

as desired. □

Theorem 2.9. Let f(x) be a polynomial of degree strictly greater than one in F [x] and suppose that C_{k}(f) is nonempty for some k ≥ 1. Then the number of elements in C_{k}(f) is the order of the group S_{f}.

Proof. Let P ∈ C_{k}(f) and define Ψ : S_{f} → C_{k}(f) by Ψ(λ) = λ∘P. By Lemma 2.8, Ψ(λ) ∈ C_{k}(f), and since P is nonconstant, it follows easily that Ψ is injective. That Ψ is a surjection, follows immediately from Theorem 2.7. □

Theorem 2.9 and Corollary 2.6 now give the following:

Corollary 2.10. Fix an integer k ≥ 1 and let f(x) be a polynomial in F [x] of degree n > 1. Then there are at most n − 1 polynomials of degree k that commute with f.

It is natural to ask exactly which polynomials f ∈ F [x] admit a nontrivial self-similarity group S_{f}. The answer is based on an obvious generalization of odd polynomials. Recall that a polynomial f ∈ F [x] is odd if and only if f(−x) = −f(x); that is, if and only if λ(x) = −x is a self-similarity of f.

Definition 2.11. Let f(x) ∈ F [x] and m > 1 an integer. Then f is m-odd if f(ωx) = ωf(x) where ω is a primitive m^{th} root of unity.

Said another way, f is m-odd if and only if λ(x) = ωx is a self-similarity of f. Recall that f is an odd polynomial if and only if f(x) = xg(x^{2}) where g(x) ∈

F [x]. Similarly, it is easy to show that f is m-odd if and only if f(x) = xh(x^{m}) where h(x) ∈ F [x]. Thus, a polynomial is odd if and only if it is 2-odd. Moreover, any mk-odd polynomial is also m-odd.

Lemma 2.12. Let r > 1 and m > 1 be integers with least common multiple t. Assume f ∈ F [x]. Then f is r-odd and m-odd if and only if f is t-odd.

Proof. Assume f is both r-odd and m-odd. Then

\frac{f(x)}{x} = g(x^{m}) = h(x^{r}).

Thus, nonzero coefficients of f(x)/x may occur only in terms of degree a nonnegative multiple of both m and r, that is, in terms of degree a multiple of t. Therefore,

\frac{f(x)}{x} = p(x^{t}).

The converse follows immediately. □

In order to characterize those polynomials with nontrivial self-similarity group, we first note that by the proof of Proposition 2.2, it follows that a similarity between centered polynomials must be of the form λ(x) = ax where a is a nonzero element of F. Thus, if f and g are similar centered polynomials, the nonzero coefficients of f correspond precisely to the nonzero coefficients of g. But m-odd polynomials are centered. Therefore, a given centered polynomial h is similar to an m-odd polynomial if and only if h is m-odd.

Theorem 2.13. Let f(x) be a polynomial in F [x] of degree strictly greater than one and let m > 1 be an integer. Then f is similar to an m-odd polynomial but not an mk-odd polynomial for any k > 1 if and only if S_{f} has m elements.

Proof. By the remarks preceding the theorem, we may assume that f is monic, centered and m-odd (but not mk-odd). Therefore, f(ωx) = ωf(x) where ω is a primitive m^{th} root of unity, which implies

S_{f} ⊇ {λ_{j}(x) = ω^{j}x | j = 1, 2, …, m}.

Now let λ(x) = ρx ∈ S_{f} where ρ is an r^{th} root of unity. Then f is m-odd and r-odd and so by Lemma 2.12 it is t-odd, where t is the least common multiple of r and m. By assumption, we must have t = m whence r divides m and ρ = ω^{j} for some j = 1, 2, …, m. Thus, S_{f} has m elements.

To prove the converse, let S_{f} have m elements and let g be a monic, centered polynomial similar to f. Then g has exactly m self-similarities, and all must be of the form λ(x) = ρx where ρ is a root of unity. Since the order of the group S_{g} equals the order of S_{f} which is m, we must have ρ^{m} = 1 for all elements of S_{g}. Thus g is m-odd. If g were mk-odd, where k > 1, then S_{g} and S_{f} would have more than m elements, a contradiction. □

This result can be written in a slightly different form.

Corollary 2.14. Let f(x) be a polynomial in F [x] of degree strictly greater than one and let m > 1 be an integer. Then S_{f} has m elements if and only if f is 96 Karl Zimmermann

similar to a polynomial of the form xg(x^{m}) with g(x) ∈ F [x] but not similar to any polynomial of the form xh(x^{r}) where h(x) ∈ F [x] and r > m.

The question of which f have nontrivial self-similarity groups S_{f} becomes more interesting when f is a rational function and S_{f} is a subgroup of PGL_{2}(F) = Aut(P^{1}). In this situation, the groups that appear are the classical symmetry groups of the regular solids (see [8]).

We now apply the above results to the Chebyshev polynomials.

Theorem 2.15 (Bertram). Let {T_{n}}_{n>1} be the sequence of nonlinear Chebyshev polynomials, and let P (x) ∈ F [x] with deg(P) = k > 1. If P commutes with at least one T_{n}, then P = T_{k} if n is even, and P = ±T_{k} if n is odd.

Proof. Each polynomial in the sequence {T_{n}}_{n>1} is centered. Observe that if n is even, then T_{n} is not m-odd for any m and by the remarks preceding Theorem 2.13, not similar to an m-odd polynomial for any m. Thus T_{n} admits no nontrivial selfsimilarities and P = T_{k}. If n is odd, T_{n} is 2-odd and again, by the remarks above, not similar to an m-odd polynomial for any m > 2. Thus S_{T_{n}} = {x, −x} which implies P = ±T_{k}. □

Acknowledgements. The author extends sincere thanks to Andrew Browder, Joseph Silverman, and the referee for their very helpful comments.

References

[1] Atela, P.; Hu, J. Commuting polynomials with the same Julia set. International Journal of Bifurcation and Chaos 6 (1996), no. 12A, 2427–2432.

[2] Bertram, E. A. Polynomials which commute with a Tchebycheff polynomial. Amer. Math. Monthly 78 (1971), no. 6, 650–653. MR0288104 (44 #5302), Zbl 0213.32103.

[3] Block, H. D.; Thielman, H. P. Commutative polynomials. Quart. J. Math. Oxford Ser. (2) 2 (1951), 241–243. MR0045250 (13,552f), Zbl 0044.00803.

[4] Jacobsthal, Ernst. Über vertauschbare Polynome. Math. Z. 63 (1955) 243–276. MR0074373 (17,574a), Zbl 0065.24903.

[5] Julia, Gaston. Mémoire sur la permutabilité des fractions rationnelles. Ann. Sci. École Norm, Sup. (3) 39 (1922), 131–215. MR1509242, JFM 48.0364.02.

[6] Ritt, J. F. Permutable rational functions. Trans. Amer. Math. Soc. 25 (1923), no. 3, 399– 488. MR1501252, JFM 49.0712.02. Errata Trans. Amer. Math. Soc. 26 (1924), no. 4, 494. MR1500495.

[7] Rivlin, Theodore J. Chebyshev polynomials. From approximation theory to algebra and number theory. Second edition. Pure and Applied Mathematics (New York). John Wiley & Sons, Inc., New York, 1990. MR1060735 (92a:41016), Zbl 0734.41029.

[8] Silverman, Joseph H. The field of definition for dynamical systems on P^{1}. Compositio Math. 98 (1995), no. 3, 269–304. MR1351830 (96j:11090), Zbl 0849.11090.

Department of Mathematics, Union College, Schenectady, NY 12308, USA zimmermk@union.edu

This paper is available via http://nyjm.albany.edu/j/2007/13-5.html.