Given two irreducible polynomials $f\_{u}(x),f\_{r}(x) \in \Bbb Q[x]$, can one find two polynomials or rational functions $h\_{u}(x),h\_{r}(x) \in \Bbb Q[x]$ or $\Bbb Q(x)$ respectively such that:$$f\_{u}(h\_{u}(x)) = f\_{r}(h\_{r}(x))?$$


Cross Posted: <https://math.stackexchange.com/questions/469190/on-composition-of-polynomials>



On composition of polynomials
Here is a description of all pairs $(f,g)$ of nonconstant polynomials in $\mathbf{Q}[x]$ for which there exist nonconstant $p,q\in\mathbf{Q}(x)$ such that $f(p(x))=g(q(x))$. This is a consequence of my work last summer with Alex Carney, Thao Do, Jared Hallett, Xiangyi Huang, Yuwei Jiang, Qingyun Sun, Yuhou Xia, Ben Weiss, and Elliot Wells.


First note that, if $(f,g)$ is a solution, then also $(h\circ f\circ\mu, \, h\circ g\circ\nu)$ is a solution for any nonconstant $h\in\mathbf{Q}[x]$ and any degree-one $\mu,\nu\in\mathbf{Q}[x]$: for, if $f\circ p = g\circ q$, then
$$
h\circ (f\circ\mu)\circ (\mu^{-1}\circ p) = h\circ (g\circ\nu)\circ (\nu^{-1}\circ q),
$$
where $\mu^{-1}$ and $\nu^{-1}$ are the degree-one polynomials which satisfy $\mu\circ\mu^{-1}=x=\nu\circ\nu^{-1}$. Also, of course if $(f,g)$ is a solution then $(g,f)$ is a solution.


Via the above methods for building new solutions from old solutions, all solutions $(f,g)$ are obtained from the following four types of fundamental solutions $(f,g)$:


1. $f=x^a (x-1)^b$ and $g=\gamma x^a (x-1)^b$ where $\gamma\in\mathbf{Q}^\*$ and $a,b$ are coprime nonnegative integers.
2. $f=x^n$ and $g$ is either $x^a h(x)^n$ or $x^a (x-1)^{n-a} h(x)^n$, where $h\in\mathbf{Q}[x]$, and $a$ is an integer coprime to $n$ such that $0<a<n$.
3. $f=T\_n(x)$, the normalized degree-$n$ Chebyshev polynomial, which is uniquely determined by the functional equation $T\_n(y+y^{-1})=y^n+y^{-n}$.
4. both $f$ and $g$ have degree at most $18$.


In the first case we have $f\circ p=g\circ q$ for
$$ p = \frac{\gamma^r x^a-1}{\gamma^{r+s} x^{a+b}-1} \quad\text{ and }\quad q=\gamma^s x^b p = \frac{\gamma^{r+s} x^{a+b} - \gamma^s x^b}{\gamma^{r+s} x^{a+b}-1},$$
where $r,s\in\mathbf{Z}$ satisfy $br-as=1$. Likewise, in the second case we have
$$ x^n \circ x^a h(x^n) = x^a h(x)^n \circ x^n \quad\text{ and }\quad
x^n \circ \frac{x^a h(\frac{x^n}{x^n-1})}{x^n-1} = x^a (x-1)^{n-a} h(x)^n \circ \frac{x^n}{x^n-1}.$$
In the fourth case we have a long and unenlightening list of all $f,g\in\mathbb{Q}[x]$ of degree at most $18$ for which there exist nonconstant $p,q\in\mathbb{Q}(x)$ such that $f\circ p=g\circ q$. This includes several isolated pairs $(f,g)$ and also some parametrized families of pairs $(f,g)$.


This leaves case $3$, when $f=T\_n(x)$. Here there are two types of solutions. One is that $g=T\_m(x)$, where we can choose $p=g$ and $q=f$. The other occurs when $g(x)$ is a solution to a polynomial Pell equation $g(x)^2+r(x)s(x)^2=4$ with $r,s\in\mathbf{Q}[x]$ where $r(x)$ is squarefree of degree $4$ and $n\mid\text{deg}(g)$. All such $g$'s can be written as $\pm T\_m\circ g\_0$ where $g\_0$ solves the same type of Pell equation and has degree at most $16$, and we have an explicit list of all such $g\_0$.


Edit: I remark that our proof is quite difficult and relies on many ingredients, including the classification of possible Galois groups of $f(x)-t$ over $\mathbf{Q}(t)$, where $f(x)$ is a polynomial in $\mathbf{Q}[x]$ which cannot be written as the composition of two polynomials of strictly smaller degree. This classification is due to Peter Mueller (in his 1993 paper "Primitive monodromy groups of polynomials"), and its proof relies on the classification of finite simple groups.


