# When is the image of an integral polynomial contained in the image of another?

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?

• What about $f(x) = x(x+1)$ and $g(y) = 2y$? – Jason Starr Jul 20 '15 at 19:53
• The curve $f(x)=g(y)$ will have infinitely many integral points so will be reducible or have genus zero. Google irreducibility of $f(x)-g(y)$ for many papers on this. – Felipe Voloch Jul 20 '15 at 20:41
• In particular, a paper of Bilu and Tichy (Acta Arith, XCV 2000) is relevant. – Felipe Voloch Jul 20 '15 at 20:43
• See mathoverflow.net/questions/105304/… for more on Voloch's comment. – David E Speyer Jul 21 '15 at 3:51
• I think that using the suggested results will only lead to complicated issues of rationality and a lengthy case-by-case analysis on the pairs in the paper of Bilu and Tichy. See Theorem 1 in: H. Davenport, D. J. Lewis, A. Schinzel, Polynomials of certain special types. Acta Arith. 9 (1964), 107-116 for a result better suited for this problem. – Pasten Jul 21 '15 at 17:32

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.
• Great answer! I think you need to say something a little more sophisticated that "$A_i(h,Y)$ has an integral root for infinitely many $h \in H$ ... this implies that $A_i(h,Y)$ has degree $1$ in $Y$." The polynomial $h^2 - 2 y^2 - 1$ has an integer root for infinitely many $h$. But I agree that making some statement about positive upper density should make the argument work. – David E Speyer Jul 22 '15 at 14:53
• @David: I tried to clarify my argument. The point is that for some fixed $i$, $A_i(h,Y)$ is irreducible and at the same time has a rational root for infinitely many integers $h$. And this of course implies $Y$-degree $1$. – Peter Mueller Jul 22 '15 at 15:10