Infinitely many solutions leads to existence of a polynomial
Solution 1:
There is an article called The Diophantine Equation $f(x) = g(y)$ by Todd Cochrane which provides a Theorem that guarantees existence of a rational polynomial $R(x)$. Specifically let $$ 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{*} $$ then following is true (you can find the proof in the referrenced article):
Suppose that $m \mid n$ and that $(a_n/b_m)$ is the $m$th power of a rational number. Then either
- $P(x)=Q(R(x))$ for some polynomial $R(x)$ with rational coefficients taking integral values at infinitely many integers; or
- equation $(*)$ has at most finitely many integral solutions.
In our case $a_n/b_m=1$ is $m$th power of rational number ($1$), and by assumptions we have infinitely many solution of equation $(*)$, so the Theorem gives us $P(x)=Q(R(x))$ with $R(x)$ over rationals. Furthermore since $Q(x)$ is a monic polynomial $R(x)$ cannot have non-integral coefficient, because that would either force some of the coefficients of $P(x)$ to be non-integral as well (for this 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.