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.



Uniqueness in Composition of Polynomials
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$.


