Uniqueness in Composition of Polynomials

Question

The following situation came up in my research:

Suppose two functions $f$ and $g$ map $[0,\infty)$ to (a subset of) itself. The function $f$ is linear and $g$ is quadratic, but $g$ is one-to-one on the interval $[0,\infty)$.

My conjecture/desired property: Any permutation of compositions of these two functions yields a unique polynomial.

The only progress I've made is the easy step of looking at degrees to argue that if two permutations are the same then they must have the same number of $g$'s.

For example, in my specific case $f(x)=x+1$ and $g(x)=x^2+x=x(x+1)$. Looking at length-3 compositions with two $g$'s gives the following different polynomials:

$f\circ g \circ g (x) = 1 + x + 2 x^2 + 2 x^3 + x^4$

$g\circ f \circ g (x) = 2 + 3 x + 4 x^2 + 2 x^3 + x^4$

$g\circ g \circ f (x) = 6 + 15 x + 14 x^2 + 6 x^3 + x^4$

I feel like this is probably easier than I'm making it, so please feel free to just give a reference for dealing with the semigroup(?) of polynomial composition.

Answer 1

Your special case is right. More generally:

Let $f\left(x\right)=x+b$ with $b\neq 0$. Let $g\left(x\right)=cx^2+dx+e$ with $c>0$, $d\in\mathbb R$ and $e\in\mathbb R$.

In fact, it is clear that every composition of $f$'s and $g$'s is a polynomial of positive degree and with positive leading coefficient (since $c>0$).

If we have a polynomial $P\in\mathbb R\left[X\right]$ which is a composition of $f$'s and $g$'s, we can always reconstruct the last step of the composition. Namely, we search for a nonnegative real $u$ such that $P-u=cQ^2+dQ+e$ for some polynomial $Q\in \mathbb R\left[X\right]$ of positive degree and with positive leading coefficient. If the last step has been a $g$, then $u=0$ must work; if the last step was an $f$, but some $g$ occured in the composition, then we must have a solution with $u\neq 0$ (in fact, if the last steps were $g$, $f$, $f$, ..., $f$ in this order, with $f$ occuring $k$ times, then $u$ must be $kb\neq 0$); if the composition consists of $f$'s only, then there is no solution (because $P$ must have degree $1$). The important thing is that the $u$, if it exists, is unique. In fact, if there would be two different $u$'s, then the two corresponding $Q$'s - let's call them $Q_1$ and $Q_2$ - would satisfy $\left(cQ_1^2+dQ_1+e\right)-\left(cQ_2^2+dQ_2+e\right)=w$ for some nonzero real $w$ (here, $w$ is the difference of the two $u$'s). This equation rewrites as $c\left(Q_1-Q_2\right)\left(Q_1+Q_2+1\right)=\left(c-d\right)Q_1-\left(c-d\right)Q_2+w$. Thus, (remembering that $c>0$) we conclude that

$\deg\left(Q_1-Q_2\right)+\deg\left(Q_1+Q_2+1\right)=\deg\left(c\left(Q_1-Q_2\right)\left(Q_1+Q_2+1\right)\right)$ $=\deg\left(\left(c-d\right)Q_1-\left(c-d\right)Q_2+w\right)\leq\max\left\lbrace \deg Q_1,\deg Q_2\right\rbrace$.

But at least one of the two degrees $\deg\left(Q_1-Q_2\right)$ and $\deg\left(Q_1+Q_2+1\right)$ must actually be equal to $\max\left\lbrace \deg Q_1,\deg Q_2\right\rbrace$ (because $Q_1$ and $Q_2$ are linear combinations of $Q_1-Q_2$ and $Q_1+Q_2$), and thus the other one must be zero or $-\infty$ (the degree of the zero polynomial). In other words, one of the polynomials $Q_1-Q_2$ and $Q_1+Q_2+1$ is constant. But the polynomial $Q_1+Q_2+1$ cannot be constant (because $Q_1$ and $Q_2$ have positive degree and positive leading coefficients). Hence, the polynomial $Q_1-Q_2$ is constant.

So let $Q_1-Q_2=k$ for $k\in\mathbb R$. Then, $\left(cQ_1^2+dQ_1+e\right)-\left(cQ_2^2+dQ_2+e\right)=w$ rewrites as $ck\left(Q_1+Q_2\right)+dk=0$ (since $Q_1-Q_2=k$). Hence, the polynomial $ck\left(Q_1+Q_2\right)$ also must be constant, so that $ck=0$ (since the polynomial $Q_1+Q_2$ is not constant, because $Q_1$ and $Q_2$ are two polynomials with positive degree and positive leading terms). Since $c>0$, this yields $k=0$, and thus $Q_1-Q_2=k=0$, so that $Q_1=Q_2$, and therefore $0=\left(cQ_1^2+dQ_1+e\right)-\left(cQ_2^2+dQ_2+e\right)=w$, contradicting $w\neq 0$.

Answer 2

The general conjecture is false. Silly example: if $f(x)=2x$ and $g(x)=x^2$, then $f\circ f\circ g=g\circ f$.

More interesting example: $f(x)=2x+1$ and $g(x)=x^2+2x$. It is obtained from the silly one by conjugation, and the same identity holds.

One can make all coefficients strictly positive. To do so, define $f(x)=f_0(x+10)-10$ and $g(x)=g_0(x+10)-10$ where $f_0$ and $g_0$ are $f$ and $g$ from the first example.

Answer 3

For more general questions on the monoid of (complex) polynomials under composition, e.g. if your chains involve more than one nonlinear polynomial, many of the principle results go back to Ritt's work in the 1920's.

Strangely, I was led to reading these results yesterday by a question here - a reference to Clauwens, Commuting polynomials and $\lambda$-ring structures on ${\mathbb Z}[x]$, J. Pure Appl. Algebra 95 (1994) in Borger-de Smit's paper leads to a classification of the polynomials that commute (the Chebyshev polynomials make a star appearance here). Further references therein, such as Dorey-Whaples Prime and composite polynomials J. Algebra 28 (1974) give nice algebraic proofs of Ritt's results, saying for instance when one can have non-equivalent decompositions $f_1\circ f_2=g_1\circ g_2$.

Answer 4

This is a bit more than what you want, but in MR1438634 (98c:12003), it is shown that f(x)=x+1 and g(x)=x^3 generate a free subgroup of the group of homeomorphisms of R. What you need is a semi-group and sometimes it is easier to find them. There is a bit more general discussion of this question and others in pages 30-31 and 37 of Topics in Geometric Group theory, by Pierre de la Harpe.