27
$\begingroup$

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

$\endgroup$
8
  • 9
    $\begingroup$ The answer is no for the last statement because if $p^{(2)}(x) \in \mathbb{Z}[x]$ then $p^{(4)}(x) \in \mathbb{Z}[x]$ $\endgroup$
    – wlad
    Dec 19, 2020 at 13:46
  • 11
    $\begingroup$ For the last question one should assume $(k_1,k_2)=1$, otherwise the polynomials $p(x)=x+1/d$ give counterexamples. $\endgroup$ Dec 19, 2020 at 14:34
  • 2
    $\begingroup$ I proved some related lemmas at mathoverflow.net/questions/314251 . I'm not sure about the answer to this one, though. $\endgroup$ Dec 19, 2020 at 15:35
  • 1
    $\begingroup$ Another remark is there exist polynimials which always take integer value when $x \in \mathbb{Z}$ but the coefficients of it is not integer. e.g. $\quad\left(\begin{array}{c}x \\ r\end{array}\right)=\frac{x(x-1) \cdots(x-r+1)}{r !}$. $\endgroup$
    – katago
    Dec 19, 2020 at 16:33
  • 3
    $\begingroup$ A remark: If $p^{(2)}$ and $p^{(3)} \in \mathbb{Z}[x]$, then $p(0) \in \mathbb{Z}$. I have not found an example of a polynomial where $p^{(2)} \in \mathbb{Z}[x]$ and $p(0) \in \mathbb{Z}$ but $p \not\in \mathbb{Z}[x]$. Does anyone have one? $\endgroup$ Dec 21, 2020 at 3:01

6 Answers 6

26
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Nice argument. Small typos: $f_d(x)$ should be $f(x)$, and there should be $-g(g(0))$ at the end of the expression of $f^{(2)}(x)$. Also, could a similar argument work for power series in $x \mathbb{Q}_p[[x]]$? $\endgroup$ Dec 21, 2020 at 15:24
  • 1
    $\begingroup$ @FrançoisBrunault Fixed, thanks! I'll comment on the more interesting question when I have a bit more of a chance to think. $\endgroup$ Dec 21, 2020 at 15:38
  • $\begingroup$ @FrançoisBrunault I spent a bit of time on the power series case and didn't get it. I can't decide whether this is for a fundamental reason or if I'm just missing a basic trick. $\endgroup$ Dec 22, 2020 at 3:22
  • 2
    $\begingroup$ A few thoughts about power series: Note that $4x+x^2$ has a compositional square root in $x Q_2[[x]]$, it starts $2 x + x^2/6 - x^3/90 + x^4/720 - (7 x^5)/32400+ \cdots$. Some experimentation suggests that the power of $2$ in the denominator of the coefficient of $x^n$ is growing like $2^n$, so it probably has radius of convergence about $1/2$. If we are going to follow a strategy like my answer then, we need to replace "$f(f(x)) \in Z_p[x]$ and $f(0) \in Z_p$" with "$f(f(x)) \in Z_p[[x]]$ and something" and the "something" must be more restrictive than positive radius of convergence. $\endgroup$ Dec 22, 2020 at 16:14
  • $\begingroup$ I’ve added an (hopefully correct) elementary proof of the Lemma in an answer below. $\endgroup$ Nov 17, 2021 at 12:40
16
$\begingroup$

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.

$\endgroup$
9
  • 2
    $\begingroup$ I think that this argument be adapted to the case of iterates $p^{(k_1)}(x)$ and $p^{(k_2)}(x)$ with $k_1$ and $k_2$ relatively prime: $p^{(k_1)}(x) = x + r_1(x) + k_1 a_n x^n + O(x^{n + 1})$ and $p^{(k_2)}(x) = x + r_2(x) + k_2 a_n x^n + O(x^{n + 1})$ with $r_1(x), r_2(x) \in \mathbb Z[x]$. $\endgroup$
    – LSpice
    Dec 19, 2020 at 17:13
  • 2
    $\begingroup$ @LSpice Right, same argument for me :) $\endgroup$ Dec 19, 2020 at 17:16
  • 2
    $\begingroup$ Yup, since the same argument you give shows that $p^{(k + 1)}(x) = p^{(k)}(x + q(x) + a_n x^n + O(x^{n + 1}) = x + q(x) + a_n x^n + q_k(x + q(x)) + k a_n x^n + O(x^{n + 1})$. $\endgroup$
    – LSpice
    Dec 19, 2020 at 17:22
  • 2
    $\begingroup$ It is a good idea, but is this true for $n=0$, when I check for $p(x)=a_0+a_1x$, the outcome is $a_0+a_1a_0$ and $a_0+a_1a_0+a_1^2a_0$ with this two in hand it seems we can not prove $a_0\in \mathbb{Z}$. $\endgroup$
    – katago
    Dec 19, 2020 at 17:23
  • 5
    $\begingroup$ @katago, in this argument $a_0 = 0$. $\endgroup$
    – LSpice
    Dec 19, 2020 at 17:27
12
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ The monic case can also follows from the lemmas that David linked above: There exists an $N$ such that $p^{(n)}\in \mathbb Z [x]$ for all $n\geq N$. Therefore $p(p^{(N)})\in \mathbb Z[x]$ with $p^{(N)}$ very primitive. By David's lemma this implies $p\in \mathbb Z[x]$. $\endgroup$ Dec 21, 2020 at 0:52
  • 1
    $\begingroup$ I wonder whether your argument or Gjergji's argument can be extended to the case of power series of the form $p(x)=x^d+O(x^{d+1})$ with $d>1$. $\endgroup$ Dec 21, 2020 at 9:36
5
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Perhaps, this is essentially the same argument an Gjergji Zaimi’s answer... $\endgroup$ Nov 17, 2021 at 14:09
  • $\begingroup$ @GjergjiZaimi's answer referenced above. $\endgroup$
    – LSpice
    Nov 18, 2021 at 0:55
  • $\begingroup$ Thanks,I have read this Lemma proof and add David E,Speyer's Theorem 1 solution,This problem is also solve it,But this lemma use Newton polygons,My students are high school students, there is no learning this content, I want to tell students to this problem,so I want looking for The high school students can understand, because it is now that is a contest questions, I think the official answer must be elementary, thank you $\endgroup$
    – math110
    Mar 27, 2023 at 15:29
2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ I tried but this doesn't seem easy. $\endgroup$ Dec 21, 2020 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.