Let $P$ and $Q$ be monic polynomials with integer coefficients and degrees $n$ and $d$ respectively, where $d\mid n$. Suppose there are infinitely many pairs of positive integers $(a,b)$ for which $P(a)=Q(b)$.
I would like to determine if exists a polynomial $R$ with integer coefficients such that $$P(x)=Q(R(x))$$
The second half of polynomials such that $P(k)=Q(l)$ for all integer $k$ is related though the condition here is weaker. I suspect the answer is yes (for polynomials, I've seen often that if some property occurs infinitely often then it occurs always).
My guess would be that we somehow construct a polynomial related to $P$ and $Q$ that ends up having infinitely many roots because of the infinitely many pairs $(a,b)$, so that we can force $P$ to conform to some sort of polynomial in $Q$. I'm not quite sure what to make of the $d\mid n$ condition; perhaps this could be strengthened? I haven't been able to find a counterexample that forces the divisibility.
Todd Cochrane's article The Diophantine Equation $f(x) = g(y)$ provides a theorem which guarantees existence of a rational polynomial $R(x)$. Specifically if \begin{align} P(x) \equiv a_nx^n&+a_{n-1}x^{n-1}+\dots+a_0\\ &=b_my^m+b_{m-1}y^{m-1}+\dots+b_0 \equiv Q(y),\tag{*} \end{align} then the following is true (proof can be found in the article):
In our case $a_n/b_m=1$ is $m$-th power of rational number $1$. Also by assumption, we have infinitely many solutions of equation $(*)$, so the above gives us $P(x)=Q(R(x))$ with $R(x)$ over rationals. Furthermore since $Q(x)$ is monic, $R(x)$ cannot have a non-integral coefficient - that would either force some of the coefficients of $P(x)$ to be non-integral as well (see this nice proof from Doctor Who), or $Q(x)$ to be a constant polynomial (in which case we can trivially choose any $R(x)$ anyway).
So in any case, under given conditions existence of desired polynomial $R(x)$ over integers follows.