# On composition of polynomials

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))?$$

-
Since the comments to an earlier (now deleted) answer contained relevant information, I summarize them here. First, presumably the OP intended to require $h_u$ and $h_r$ nonconstant (please correct me if I'm wrong about this). Second, irreducibility isn't important, since adding the same constant to both $f_u$ and $f_r$ does not affect whether $h_u$ and $h_r$ exist, but does affect reducibility. – Michael Zieve Aug 17 '13 at 15:20

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.

-
Fried considered the case $h_{u}(f_{u}(x)) = h_{r}(f_{r}(x))$ (which is reverse of here) and it seems there are solutions there for some constraints. – Turbo Aug 17 '13 at 14:46
@JAS: to which paper of Fried's are you referring? The reversed equation $h_u\circ f_u=h_r\circ f_r$ is much easier, and was essentially solved by Ritt in the 1920's. Here $(f_u,f_r)$ is either $(\mu\circ x^n\circ h, \nu\circ x^i g(x^n)\circ h)$ or $(\mu\circ D_m(x,a)\circ h, \nu\circ D_n(x,a)\circ h)$, where $\mu,\nu\in\mathrm{Q}[x]$ have degree one, $h\in\mathrm{Q}[x]$ is arbitrary, $a\in\mathrm{Q}$, and $D_n(x,a)$ is the degree-$n$ Dickson polynomial with parameter $a$, which is determined by the functional equation $D_n(y+a/y,a)=y^n+(a/y)^n$. – Michael Zieve Aug 17 '13 at 15:02
(cont'd...) You can find this in Schinzel's book "Polynomials with Special Regard to Reducibility", or alternately by combining Theorems 3.1 and 5.1 in my paper with Bob Beals and Joe Wetherell "Polynomials with a common composite". – Michael Zieve Aug 17 '13 at 15:05
In order to determine which pairs $(f_u,f_r)$ of polynomials in some particular restricted class (like "falling factorial" polynomials $x(x-1)(x-2)...(x-k)$) satisfy the conclusion of the result in my Answer above, one needs to determine all $h$ for which we can write $f_u=h\circ g_u$ and $f_r=h\circ g_r$. That is often nontrivial, but there are methods for doing that. If the OP or anyone else has some particular class of polynomials for which they'd like to solve this, please feel free to email me. – Michael Zieve Aug 17 '13 at 15:23