Let $p(x)$ be a polynomial, $p(x) \in \mathbb{Q}[x]$, and $p^{(m+1)}(x)=p(p^{(m)}(x))$ for any positive integer $m$.  

If $p^{(2)}(x) \in \mathbb{Z}[x]$ it's not possible to say that $p(x) \in \mathbb{Z}[x]$.  

Is it possible to conclude that $p(x) \in \mathbb{Z}[x]$ if $p^{(2)}(x) \in \mathbb{Z}[x]$ and $p^{(3)}(x) \in \mathbb{Z}[x]$?


More general, suppose there exist positive integers $k\_1 <k\_2$, such that $p^{(k\_1)}(x) \in \mathbb{Z}[x]$ and $p^{(k\_2)}(x) \in \mathbb{Z}[x]$. Does it follow that $p(x) \in \mathbb{Z}[x]$?



$m$-fold composite $p^{(m)}(x) \in \mathbb{Z}[x]$ implies $p(x) \in \mathbb{Z}[x]$
$\newcommand\ZZ{\mathbb{Z}}\newcommand\QQ{\mathbb{Q}}$The statement is true.


**Notation**: I'm going to change the name of the polynomial to $f$, so that $p$ can be a prime. Fix a prime $p$, let $\QQ\_p$ be the $p$-adic numbers, $\ZZ\_p$ the $p$-adic integers and $v$ the $p$-adic valuation.
Let $\QQ\_p^{alg}$ be an algebraic closure of $\QQ\_p$, then $v$ extends to a unique valuation on $\QQ\_p^{alg}$, which we also denote by $v$.


We recall the notion of a Newton polygon: Let $f(x) = f\_0 + f\_1 x + \cdots + f\_d x^d$ be a polynomial in $\QQ\_p[x]$.
The Newton polygon of $f$ is the piecewise linear path from $(0, v(f\_0))$ to $(d, v(f\_d))$ which is the lower convex hull of the points $(j, v(f\_j))$.
We let the Newton polygon pass through the points $(j, N\_j)$, for $0 \leq j \leq d$, and we set $s\_j = N\_j - N\_{j-1}$; the $s\_j$ are called the slopes of the Newton polygon. Since the Newton polygon is convex, we have $s\_1 \leq s\_2 \leq \cdots \leq s\_d$.


There are two main Facts about Newton polygons: (Fact 1) Let $f$ and $\bar{f}$ be two polynomials and let the slopes of their Newton polygons be $(s\_1, s\_2, \ldots, s\_d)$ and $(\bar{s}\_1, \bar{s}\_2, \ldots, \bar{s}\_{\bar{d}})$ respectively. Then the slopes of $f \bar{f}$ are the list $(s\_1, s\_2, \ldots, s\_d, \bar{s}\_1, \bar{s}\_2, \ldots, \bar{s}\_{\bar{d}})$, sorted into increasing order. (Fact 2) Let $\theta\_1$, $\theta\_2$, ... $\theta\_d$ be the roots of $f$ in $\QQ\_p^{alg}$. Then, after reordering the roots appropriately, we have $v(\theta\_j) = -s\_j$.


Here is the lemma that does the main work:


**Lemma**: Let $f$ be a polynomial in $\QQ\_p[x]$ which is not in $\ZZ\_p[x]$, and suppose that the constant term $f\_0$ is in $\ZZ\_p$. Then $f^{(2)}$ is not in $\ZZ\_p[x]$.


**Remark**: An instructive example with $f\_0 \not\in \ZZ\_p$ is to take $p=2$ and $f(x) = 2 x^2 + 1/2$, so that $f(f(x)) = 8 x^4 + 4 x^2+1$. You might enjoy going through this proof and seeing why it doesn't apply to this case.


**Proof**: We use all the notations related to Newton polygons above. Note that the leading term of $f^{(2)}$ is $f\_d^{d+1}$, so if $f\_d \not\in \ZZ\_p$ we are done; we therefore assume that $f\_d \in \ZZ\_p$.
So $v(f\_0)$ and $v(f\_d) \geq 0$, but (since $f \not\in \ZZ\_p[x]$), there is some $j$ with $v(f\_j) < 0$. Thus the Newton polygon has both a downward portion and an upward portion.
Let the slopes of the Newton polygon be $s\_1 \leq s\_2 \leq \cdots \leq s\_k \leq 0 \leq s\_{k+1} \leq \cdots \leq s\_d$. Thus, $(k,N\_k)$ is the most negative point on the Newton polygon; we abbreviate $N\_k = -b$ and $N\_d = a$.


Let $\theta\_1$, ..., $\theta\_d$ be the roots of $f$, numbered so that $v(\theta\_j) = - s\_j$.
We have $f(x) = f\_d \prod\_j (x-\theta\_j)$ and so $f^{(2)}(x) = f\_d \prod\_j (f(x) - \theta\_j)$. We will compute (part of) the Newton polygon of $f^{(2)}$ by merging the slopes of the Newton polygons of the polynomials $f(x) - \theta\_j$, as in Fact 1.


**Case** 1: $1 \leq j \leq k$. Then $v(\theta\_j) = - s\_j \geq 0$. Using our assumption that $f\_0 \in \ZZ\_p$, the constant term of $f(x) - \theta\_j$ has valuation $\geq 0$. Therefore, the upward sloping parts of the Newton polygons of $f(x)$ and of $f(x) - \theta\_j$ are the same, so the list of slopes of Newton polygon of $f(x) - \theta\_j$ ends with $(s\_{k+1}, s\_{k+2}, \ldots, s\_d)$. Thus, the height change of the Newton polygon from its most negative point to the right end is $s\_{k+1} + s\_{k+2} + \cdots + s\_d = a+b$.


**Case** 2: $k+1 \leq j \leq d$. Then $v(\theta\_j) < 0$, so the left hand point of the Newton polygon of $f(x) - \theta\_j$ is $(0, v(\theta\_j)) = (0, -s\_j)$, and the right hand point is $(d, v(f\_d)) = (d, a)$. We see that the total height change over the entire Newton polygon is $a+s\_j$ and thus the height change of the Newton polygon from its most negative point to the right end is $\geq a+s\_j$.


The right hand side of the Newton polygon of $f^{(2)}$ is at height $v(f\_d^{d+1}) = (d+1) a$. Since we shuffle the slopes of the factors together (Fact 1), the Newton polygon of $f^{(2)}$ drops down from its right endpoint by the sum of the height drops of all the factors. So the lowest point of the Newton polygon of $f^{(2)}$ is at least as negative as
$$(d+1) a - k(a+b) - \sum\_{j=k+1}^d (a+s\_j).$$
We now compute
$$(d+1) a - k(a+b) - \sum\_{j=k+1}^d (a+s\_j) = (d+1) a - k(a+b) - (d-k) a - \sum\_{j=k+1}^d s\_j$$
$$ = (d+1) a - k(a+b) - (d-k) a- (a+b)= -(k+1)b < 0 .$$


Since this is negative, we have shown that the Newton polygon goes below the $x$-axis, and we win. $\square$


We now use this lemma to prove the requested results.


**Theorem** 1: Let $g \in \QQ\_p[x]$ and suppose that $g^{(2)}$ and $g^{(3)}$ are in $\ZZ\_p[x]$. Then $g \in \ZZ\_p[x]$.


**Proof**: Note that $g(g(0))$ and $g(g(g(0)))$ are in $\ZZ\_p$. Put
$$f(x) = g{\big (}x+g(g(0)){\big )} - g(g(0)).$$
Then $f^{(2)}(x) = g^{(2)}{\big (} x+g(g(0)) {\big )} - g(g(0))$, so $f^{(2)}$ is in $\ZZ\_p[x]$.
Also, $f(0) = g^{(3)}(0) - g^{(2)}(0) \in \ZZ\_p$. So, by the contrapositive of the lemma, $f(x) \in \ZZ\_p[x]$ and thus $g(x) \in \ZZ\_p[x]$. $\square$


We also have the stronger version:


**Theorem** 2: Let $h \in \QQ\_p[x]$ and suppose that $h^{(k\_1)}$ and $h^{(k\_2)}$ are in $\ZZ\_p[x]$ for some relatively prime $k\_1$ and $k\_2$. Then $h \in \ZZ\_p[x]$.


**Proof**: Since $GCD(k\_1, k\_2) = 1$, every sufficiently large integer $m$ is of the form $c\_1 k\_1 + c\_2 k\_2$ for $c\_1$, $c\_2 \geq 0$, and thus $h^{(m)}$ is in $\ZZ\_p[x]$ for every sufficiently large $m$.
Suppose for the sake of contradiction that $h(x) \not\in \ZZ\_p[x]$. Then there is some largest $r$ for which $h^{(r)}(x) \not\in \ZZ\_p[x]$. But for this value of $r$, we have $h^{(2r)}$ and $h^{(3r)}$ in $\ZZ\_p[x]$, contradicting Theorem 1. $\square$.




---


From [this question on math.SE](https://math.stackexchange.com/questions/3997372/if-fx-in-mathbb-qx-and-ffx-fffx-in-mathbb-zx-prove-that-fx), I have recently learned that this question is from the [2019 Japanese Math Olympiad](https://www.imojp.org/archive/mo2019/selection_camp/problems/2019.pdf). (Fortunately, this question was asked in 2020.) I can't read Japanese, but if anyone is able to track down and translate the official solution; I'd be interested. Back when I was training for Olympiads in the late 90's, I remember that the Japanese solutions were always very clever and surprising.


