$m$-fold composite $p^{(m)}(x) \in \mathbb{Z}[x]$ implies $p(x) \in \mathbb{Z}[x]$

Question

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]$?

Answer 1

$\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, I have recently learned that this question is from the 2019 Japanese Math Olympiad. (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.

Answer 2

The result is true for polynomials (or more generally, power series) of the form $p(x) = x + ax^2 + bx^3 + \cdots$ with $a,b \ldots \in \mathbb{Q}$.

Let $p(x) = x + \sum_{n \geq 2} a_n x^n \in \mathbb{Q}[[x]]$ such that $p^{(2)}$ and $p^{(3)}$ belong to $\mathbb{Z}[[x]]$. We will show by induction on $n$ that $a_n \in \mathbb{Z}$. Let $n \geq 2$ such that $a_k \in \mathbb{Z}$ for all $k<n$.

We have $p(x) = x + q(x) + a_n x^n + O(x^{n+1})$ with $q(x) = \sum_{k=2}^{n-1} a_k x^k \in \mathbb{Z}[x]$. Then \begin{align*} p^{(2)}(x) & = p(x) + q(p(x)) + a_n p(x)^n + O(x^{n+1}) \\ & = x + q(x) + a_n x^n + q(p(x)) + a_n x^n + O(x^{n+1}). \end{align*} Now in the power series $q(p(x)) + O(x^{n+1})$, the coefficient $a_n$ does not appear, so that this power series has coefficients in $\mathbb{Z}$. It follows that $2a_n \in \mathbb{Z}$. The same computation shows that $p^{(3)}$ is of the form \begin{equation*} p^{(3)}(x) = x + r(x) + 3a_n x^n + O(x^{n+1}) \end{equation*} with $r(x) \in \mathbb{Z}[x]$. Therefore $3a_n \in \mathbb{Z}$, and thus $a_n \in \mathbb{Z}$.

Remark. In the case considered here, $0$ is a fixed point of $p$. In general, we could try to use the fact that any non-constant polynomial $p(x)$ fixes the point $\infty$. Let $\varphi(x)=1/x$ be the standard chart at $\infty$. Then $q := \varphi^{-1} \circ p \circ \varphi$ is a power series of the form \begin{equation*} q(x) = a_d^{-1} x^d + O(x^{d+1}), \end{equation*} where $d=\mathrm{deg}(p)$ and $a_d$ is the leading coefficient of $p$. Assuming $p$ is monic, it suffices to generalize the result above for power series with arbitrary valuation.

Answer 3

The following is proved (independently?) in [1] and [2]: Every polynomial decomposition over $\mathbb Q$ is equivalent to a decomposition over $\mathbb Z$.

Specifically it says that if $g\circ h \in \mathbb Z [x]$ with $g,h\in \mathbb Q[x]$ then there exists a linear polynomial $\varphi\in \mathbb Q[x]$ such that $g\circ \varphi^{-1}$ and $\varphi\circ h$ are both in $\mathbb Z[x]$ and $\varphi\circ h(0)=0$.

[1] I. Gusic, On decomposition of polynomials over rings, Glas. Mat. Ser. III 43 (63) (2008), 7–12

[2] G. Turnwald, On Schur’s conjecture, J. Austral. Math. Soc. Ser. A (1995), 58, 312–357

---

Now suppose that $f(x)$ satisfies $f^{(2)}, f^{(3)}\in \mathbb Z[x]$. Then, as in David's answer, the polynomial $F(x)=f(x+f(f(0)))-f(f(0))$ satisfies $F^{(2)}, F^{(3)}\in \mathbb Z[x]$ and $F(0)\in \mathbb Z$.

Let's write $F(x)=a_nx^n+\cdots +a_0$. Assume that there exists some prime $p$ for which $v_p(a_i)<0$. From the statement quoted above, there exists $\varphi(x)=a(x-F(0))$ such that $\varphi\circ F\in \mathbb Z[x]$. This means that $v_p(a)>0$. We will also have $F\circ \varphi^{-1}\in \mathbb Z[x]$ so $F(\frac{x}{a}+F(0))\in \mathbb Z[x]$.

Suppose that $k$ is the largest index for which $v_p(a_k)-kv_p(a)<0$. This must exist because $v_p(a_i)-iv_p(a)<0$. Then we see that all coefficients coming from $a_r\left(\frac{x}{a}+F(0)\right)^r$ for $r>k$ have $v_p>0$. This means that the coefficient of $x^k$ in $F(\frac{x}{a}+F(0))$ must have $v_p<0$, which is a contradiction. Thus we must have $F(x)\in \mathbb Z[x]$ and therefore also $f(x)\in \mathbb Z[x]$.

Answer 4

For every polynomial $f(x) \in \mathbb{Q}[x]$, let $\mathcal{R}(f) := \{ \alpha \in \mathbb{C} \mid p(\alpha) = 0 \} \subseteq \overline{\mathbb{Q}} \subseteq \mathbb{C}$ be its set of roots.

Then $\mathcal{R}(p) = p^{(2)}(\mathcal{R}(p^{(3)}))$. Suppose that $p(x) \in \mathbb{Q}[x]$ is monic and $p^{(2)}, p^{(3)} \in \mathbb{Z}[x]$. Then $\mathcal{R}(p^{(3)}) \subseteq \overline{\mathbb{Z}}$ because $p^{(3)}$ will be monic as well. Since $p^{(2)} \in \mathbb{Z}[x]$ by assumption, this implies that $\mathcal{R}(p) \subseteq \overline{\mathbb{Z}}$, which in turn implies that $p(x) \in \mathbb{Z}[x]$ because $p$ was assumed to be monic.

The same argument works to show more generally that $p(x) \in \mathbb{Z}[x]$ under the assumptions that $p(x) \in \mathbb{Q}[x]$ is monic, and $p^{(k_1)}(x), p^{(k_2)}(x) \in \mathbb{Z}[x]$ for some $k_1, k_2 \in \mathbb{N}$ such that $\gcd(k_1,k_2) = 1$.

I don't know how to treat the case when $p(x)$ is not monic. Of course, if $p^{(k_1)}(x), p^{(k_2)}(x) \in \mathbb{Z}[x]$ for some $k_1, k_2 \in \mathbb{N}$ such that $\gcd(k_1,k_2) = 1$, then it is immediate to show that the leading coefficient of $p(x)$ has to be an integer, but I can't go any further.

Answer 5

$\def\QQ{\mathbb Q}\def\ZZ{\mathbb Z}$Here is a more elementary proof of the key Lemma in the very nice @Dávid E. Speyer’s answer, pasted here for convenience.

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]$.

Set $v_i=v(f_i)$; choose an index $t$ minimizing $v_t(<0)$; if there are several minimal values, take the maximal $t$. By the assumptions, we have $t>0$. Performing such choice for the polynomial $F_r(x)=f_rf(x)^r$, we get the index $rt$ with the valuation $v_r+rv_t$ (one way to see it is, again, via Newton polygons, but these inequalities can be easily written down explicitly).

Choose now an index $s$ minimizing $M=v_s+sv_t$, taking again the maximal index given a multiple choice. We have $M\leq v_t+tv_t<0$; therefore, $s>0$, since $v_0\geq0$. Then $M$ is the minimal valuation of a coefficient in all the $F_i$; moreover, such valuation appears in the coefficient of $x^{st}$ exactly once —that is, in $F_s(x)$. Therefore, in $f^{(2)}(x)$ the coefficient of $x^{st}$ also has valuation $M<0$.

Answer 6

It is easy to see this result for power series of the form $p(x)=x+ax^2+bx^3+\cdots$ with $a,b,\dots\in\mathbb{Q}$. More generally, let $i_1,\dots, i_k$ be relatively prime integers. The set of all power series of the form $x+ax^2+bx^3+\cdots\in\mathbb{Q}[[x]]$ form a group under composition. Such power series with integer coefficients form a subgroup. In any group $G$ and $g\in G$, the group generated by $g^{i_1},\dots, g^{i_k}$ contains $g$, and the proof follows.

Can this argument be modified to solve the stated problem?