Can I express $x(x-1)\ldots(x-34)$ as $p(q(x))$ where $p$, $q$ are polynomials of degree 5 and 7?

Question

To give an easier example, $x(x-1)(x-2)(x-3)$ can be written as $x(x-3) \cdot (x(x-3) + 2)) = q(x)(q(x)+2)$ where $q(x) = x(x-3)$.

In other words, we can write this degree-4 polynomial as $p(q(x))$ where $p$, $q$ are degree-2 polynomials. Note that $2 \cdot 2 = 4$.

This prompts several questions. In decreasing order of generality:

• How can we find out if a degree-$nm$ polynomial can be written as composition of a degree-$n$ and a degree-$m$ polynomial?
• Specifically, is there a general way to write the special degree-$nm$ polynomials $x(x-1)\ldots(x-(nm-1))$ in such a form?
• Even more specifically, is there a solution where $nm \ge 32$ and $n, m < 8$? These are what I need. The possible cases are:
  • $(n, m) = (5, 7)$ or $(7, 5)$, so $nm = 35$
  • $(n, m) = (6, 6)$, so $nm = 36$
  • $(n, m) = (6, 7)$ or $(7, 6)$, so $nm = 42$
  • $(n, m) = (7, 7)$, so $nm = 49$

Answer 1

No, this doesn't happen in general for $\deg q >2$.

Assume $x(x-1)\ldots(x-(nm-1)) = p(q(x))$ with $p,q$ of degrees $n,m$ respectively and $m>2$.

$p \circ q$ has $nm$ roots, and $q$ partitions them, each partition corresponding to a root of $p$ : the numbers $0$ to $nm-1$ must be the preimages (through $q$) of the roots of $p$.

We can assume that $q$ has leading coefficient $1$ and $q(1)=0$ (if not we can scale and translate the output of $q$ and the input of $p$ accordingly to make it true). Then $q(x)$ must have the form $q(x) = x(x-a_1)(x-a_2)\ldots(x-a_{m-1})$ for some distinct integers $a_1 \ldots a_{m-1}$. This forces $q$ to have real coefficients, and then the intermediate value theorem can be applied to $q$ and the roots of $p$ to show that the partitions must be of the form $\{k;2n-1-k;2n+k;4n-1-k;\ldots\}$ for $k \in \{0; \ldots ;n-1\}$
The graph of $q$ must be zigzagging between the minimal root of $p$ and the maximum root of $p$ so that all the roots in-between all have $m$ pre-images by $q$.

So there is no other choice than picking $q(x) = x(x-(2n-1))(x-(2n))(x-(4n-1))\ldots$
But then we have
$|q(1)| = 1 \cdot (2n-2) \cdot (2n-1) \cdot (4n-2) \cdots$ , while
$|q(2n-2)| =(2n-2) \cdot 1 \cdot 2 \cdot (2n+1) \cdots$
The first two factors when taken together are equal but then every factor in $q(2n-2)$ is smaller than the corresponding one in $q(1)$, so $|q(1)| > |q(2n-2)|$. This contradicts what we know about the partitioning of the roots.