# Uniqueness in Composition of Polynomials

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.

-
The subset criterion is essential, or else $x$ and $x^2$ trivializes everything. –  Steve Huntsman Mar 24 '10 at 17:59
True! I should probably say "nontrivial functions" since the conjecture is obviously false if one of the polynomials is x (the identity under composition). –  Aeryk Mar 24 '10 at 18:04
A related known question is the two polynomials $x+1$ and $x^3$. Publicized by Harvey Friedman some years ago, since if true it would provide a simpler example of something in model theory. Then solved affirmatively by Hans Zassenhaus. But as I recall some question about thst proof was raised even in the preprint form, but Zassenhaus didn't get around to reconsidering it before it was published. I can only read the paper up to the magic phrase "By Kummer theory". –  Gerald Edgar Mar 24 '10 at 19:40
Is the question about $x+1$ and $x^3$ the exact same one? darij grinberg's solution works perfectly in this case - cubes of two polynomials cannot differ by a nonzero constant. –  Sergei Ivanov Mar 24 '10 at 20:34
Informaworld says I have access to Zassenhaus' paper through my university's proxy, but when I try to get the PDF it returns a 0-sized reply... –  darij grinberg Mar 24 '10 at 21:09

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$.

-
This seems to do the trick for my case: Thanks! I don't know if I'm convinced this will work for "uglier" polynomials in $Z[x]$, like say $f(x)=x+7$ and $g(x)=x^2+3x+9$ ... –  Aeryk Mar 24 '10 at 18:33
This argument works for $f(x)=x+const$, the case $f(x)=ax+b$ where $a\ne 1$ is different. –  Sergei Ivanov Mar 24 '10 at 18:37
Thanks, I found the flaw in my proof. It is now fixed to work for the case when $f$ has leading coefficient $1$. The assumptions on $g$ are pretty generic. –  darij grinberg Mar 24 '10 at 20:14

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.

-
Perhaps one needs the condition that $f$ and $g$ have nonzero constant term. –  Michael Lugo Mar 24 '10 at 19:19
This was basically said in the comments to the question. $f$ must send $\left[0,\infty\right)$ to a proper subset of $\left[0,\infty\right)$. –  darij grinberg Mar 24 '10 at 19:19
$f(x)=2x+1$ does. –  Sergei Ivanov Mar 24 '10 at 19:25
I added an example where all coefficients are positive. –  Sergei Ivanov Mar 24 '10 at 20:45

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$.

-

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.

-