Suppose $f$ and $g$ are polynomials with integral coefficients and $f(\mathbb Z)\subset g(\mathbb Z)$. Is there any relation between $f$ and $g$?
For instance, this happens if $f=g\circ h$ for some third integral polynomial $h$. In the particular case that $f$ takes on only square values, we could deduce that the converse is true: $f$ is a square, so $f=g\circ h$ where $h$ is some polynomial and $g(x)=x^2$. Does something like this hold more generally?
The suggestion from the comments to use Siegel's Theorem about integral points on algebraic curves is vast overkill. The by far easier Hilbert's Irreducibility Theorem is sufficiently strong here:
Suppose that $f(\mathbb Z)\subseteq g(\mathbb Z)$. Write $f(X)-g(Y)=A_1(X,Y)A_2(X,Y)\cdots A_r(X,Y)$ with polynomials $A_i(X,Y)\in\mathbb Q[X,Y]$ which are irreducible over $\mathbb Q$. By Hilbert's Irreducibility Theorem, there is an infinite set $H$ of integers such that $A_i(h,Y)$ is irreducible for each $h\in H$ and each $i$. On the other hand, for each integer $h$ there is an integer $u$ such that $f(h)=g(u)$. So $f(h)-g(Y)$ and therefore some $A_i(h,Y)$ has an integral root. Running through $h\in H$, we see that there is some $i$ such that $A_i(h,Y)$ has an integral root for infinitely many $h\in H$.
So for this index $i$ there are infinitely many $h\in H$ such that $A_i(h,Y)$ is irreducible and has a rational root. So $A_i(X,Y)$ has degree $1$ in $Y$.
We obtain $f(X)-g(Y)=A(X,Y)(b(X)-Yc(X))$ for $A\in\mathbb Q[X,Y]$ and $b,c\in\mathbb Q[X]$. Setting $Y=b(X)/c(X)$ yields $f(X)=g(b(X)/c(X))$. Looking at poles shows that $c(X)$ actually is a constant. So $f(X)=g(b(X))$ for a polynomial $b(X)$ with rational coefficients.
