# I would like to determine if exists a polynomial $R$ with integer coefficients such that $P(x)=Q(R(x))$.

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.

• Not sure if helpful at all but some ideas here. (1) Let the coefficient be $p_1,p_2,...,p_n$ and $q_1,q_2,...q_d$ respectively, then if we treat these coefficients as variables we essentially have $n+d$ unknowns but infinitely many equations. This could make use of the infinite pairs condition. (2) For the construction thing, it could be helpful to define $Q^{-1}$ in some way, and indeed that is true in some small cases where $Q^{-1}$ is calculable, but I wasn't able to proceed any further than that. Aug 9, 2020 at 16:57
• Lastly, the divisibility condition is necessary. $P(x)=x^3$ and $Q(x)=x^2$ will give a counter example: no $R$ exists and infinitely many integer pairs $P(n^2)=Q(n^3)$ exist. Aug 9, 2020 at 17:00
• I think that by Faltings' theorem, the curve $P(x)=Q(y)$ must have genus $\le1$. By Siegel's theorem the same holds in genus $1$. That leaves genus zero. Don't know for sure, but I suspect this to be true, the function field is rational after all, and that should/could help. Hmm. I should look at the curve one component at a time. And let's keep in mind Carl's (now deleted) answer as well. Aug 14, 2020 at 12:42
• I checked out old suggestions to the Pearl Dive. This question was endorsed by Will Jagy. Unfortunately I forgot to act on it in a timely manner. Apr 24, 2022 at 6:19
• Anyway, interesting related contributions are all eligible for the bounty. Sil's answer may be difficult to beat, but let's have a jam session. Apr 24, 2022 at 6:20

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):
Suppose that $$m \mid n$$ and that $$(a_n/b_m)$$ is the $$m$$-th power of a rational number. Then either
1. $$P(x)=Q(R(x))$$ for some polynomial $$R(x)$$ with rational coefficients taking integral values at infinitely many integers; or
2. equation $$(*)$$ has at most finitely many integral solutions.
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.