Return to Answer

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 < s_{k+1} < \cdots < s_d$. Thus, $(k,N_k)$ is the most negative point on the Newton polygon; we abbreviate $N_k = -b$ and $N_d = a$.

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

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.

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_d(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_d(x) - \theta_j$ has valuation $\geq 0$. Therefore, the upward sloping parts of the Newton polygons of $f_d(x)$ and of $f_d(x) - \theta_j$ are the same, so the list of slopes of Newton polygon of $f_d(x)$ 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_d(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$.

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 )}$, 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$

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

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$