NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/sci/math/17470

Internet Message Format | 1992-12-29 | 1.9 KB

Path: sparky!uunet!ogicse!das-news.harvard.edu!husc-news.harvard.edu!husc.harvard.edu!kedlaya
From: [e-mail] (Kiran Kedlaya)
Newsgroups: sci.math
Subject: Re: Composition-commuting polynomials
Keywords: Polynomials commuting composition
Message-ID: <[e-mail]>
Date: 28 Dec 92 22:14:07 GMT
Article-I.D.: husc.kedlaya.725580847
References: <[e-mail]>
Lines: 39
Nntp-Posting-Host: husc8.harvard.edu

Yes, in fact, if f(x^2 + 1) = f(x)^2 + 1, then for some n
         f(x) = g[n](x),
where g1(x) = x^2 + 1 and g[n] denotes the n-th composition.
(Under this notation, g[0](x) = x.)

First notice that f(x)^2 = f(x^2 + 1) - 1
                         = f((-x)^2 + 1) - 1
                         = f(-x)^2.
Hence either f(x) = f(-x) or f(x) = -f(-x) is a polynomial identity.
In other words, f is either even or odd, and clearly f is even
iff deg(f) is.

If f is even, let x = y^2 + 1. Now
   f(x) = f(y^2 + 1) = f(y)^2 + 1
and furthermore, f(y), being even, can be expressed as a polynomial
in y^2, and hence as a polynomial in x, which we call h(x).
In other words, f(x) = g(h(x)). Furthermore,
   h(y^2 + 1) = h(x) = f(y) = g(h(y))
so h commutes with g as well. Observe that the degree of h is
half that of f.

We can repeat this process k times, where k is the highest power
of 2 dividing deg(f), and deduce that f(x) = g[k](h(x)), where
h is odd and commutes with g. Note that since h is odd, h(0) = 0.
Define the sequence x_n recursively as follows: x_0 = 0, and
x_{n+1} = x_n^2 + 1. By induction h(x_n) = x_n for all n, so
that h(x) = x identically, and f(x) = g[k](x), as desired.

This generalizes (it would appear) to g(x) = x^2 + c for any
nonzero c.

And I do believe this was a Putnam problem (though I don't remember
offhand when. Anyone?)

Kiran Kedlaya
Harvard University
"Lo \'unico peor que la mala salud es la mala fama."
      -Gabriel Garc\'ia M\'arquez,
         from "El amor en los tiempos de c\'olera"