prove this $x^{m+1}|f^{(m)}(x)-x$

Solution 1:

Consider the space $A = t\Bbb C[[t]] = \{a_1t + a_2t^2 + a_3t^3 + \ldots \mid a_i \in \Bbb C\}$.

$A$ can be equipped with the composition law $\circ$ which is linear in the first argument
( $f \circ h + g \circ h = (f+g) \circ h$ and $(\lambda f) \circ g = \lambda (f \circ g)$ for $\lambda \in \Bbb C$).

Thus for any $g \in A$, we get a linear endomorphism $\rho_g(f) = f \circ g$.

If $g = b_1t + b_2t^2 + b_3t^3 + \ldots$, then $\rho_g(t^k) = g(t)^k = b_1^k t^k + \ldots$.
This shows that the "matrix" of $\rho_g$ is triangular (in particular, $\rho_g$ is compatible with the $t$-adic topology) and the coefficients on the diagonal are the sequence $(b_1^n)$.

Restricting modulo $t^{n+1}$ gives you a linear map $\rho_g^{[n]} : A_n \to A_n$ (where $A_n = t\Bbb C_{n-1}[t]$ has dimension $n$) defined by $\rho_g^{[n]}(f) = \rho_g(f) \pmod {t^{n+1}}$ whose matrix is simply the $n \times n$ submatrix in the topleft corner of the infinite matrix of $\rho_g$. Its eigenvalues are the $b_1^k$ for $k=1 \ldots n$.

Now suppose you are looking at a $g$ whose $b_1$ is a primitive $n$th root of unity $\zeta_n$.
Then $\rho_g^{[n]}$ has eigenvalues $\zeta_n^k$ for $k=1 \ldots n$, and since they are all distinct this is diagonalisable, and since their $n$th power is $1$, $(\rho_g^{[n]})^n$ is the identity of $A_n$.

Going back to $A$, this proves that the topleft $n \times n$ block in the matrix of $\rho_g^n$ is $I_n$, and so that for any $f \in A$, $f \circ g^{\circ n} \equiv f \pmod {t^{n+1}}$

Applying this to $t \in A$ you get $g^{\circ n} \equiv t \pmod {t^{n+1}}$

Solution 2:

Attention [2016-11-20]: This answer is not correct as it is based upon a wrong assumption \begin{align*} x^\color{blue}{m}\left|f(x)-\zeta_m x\right.\qquad\qquad m>1 \end{align*} instead of \begin{align*} x^\color{blue}{2}\left|f(x)-\zeta_m x\right.\qquad\qquad m>1 \end{align*}

I have offered a bounty for compensation in order to support a correct answer to OPs question.

Let $m>1$ be a positive integer and $f(x)$ a polynomial with complex coefficients and degree $n\geq m$. We denote with $\zeta_m$ the following $m$-th root of unity $$\zeta_m=\exp\left(\frac{2\pi i}{m}\right)$$

Claim: The following is valid for $m>1$

\begin{align*} x^m\left|f(x)-\zeta_m x\right.\qquad\implies\qquad x^{m+1}\left|f^{(m)}-x\right.\tag{1} \end{align*}

with \begin{align*} f^{(m)}(x)&:=f^{(m-1)}\left(f(x)\right)\qquad m>1\\ f^{(1)}(x)&:=f(x)\\ f^{(0)}(x)&:=x\\ \end{align*}

We introduce some more settings for convenience. Since $x^m|f(x)-\zeta_m x$ there is a polynomial $$q(x)=\sum_{j=0}^{n-m}a_jx^j$$ of degree $n-m$ with \begin{align*} x^mq(x)&=f(x)-\zeta_m x\\ \text{resp.}\qquad\qquad\\ f(x)&=x^mq(x)+\zeta_m x\tag{2} \end{align*}

Approach: The idea is to repeatedly apply (2) and so reduce $m$ in $f^{(m)}$ until we see that (1) is valid. In order to keep the calculation manageable we will consequently simplify expressions modulo $x^{m+1}$.

We do not go the shortest way, but add some intermediate steps to easier see what is going on and to motivate the claim (9) which is central for proving the answer.

Step: $m\rightarrow (m-1)$

We obtain \begin{align*} f^{(m)}(x)-x&=f^{(m-1)}\left(f(x)\right)-x\\ &=f^{(m-1)}\left(x^mq(x)+\zeta_m x\right)-x\tag{3}\\ &\equiv f^{(m-1)}\left(x^ma_0+\zeta_m x\right)-x&\pmod{x^{m+1}}\tag{4}\\ \end{align*}

Comment:

• In (3) we substitute the RHS of (2) for $f(x)$.

• In (4) we note that \begin{align*} f(x)&=x^mq(x)+\zeta_m x\\ &=x^m\left(a_0+a_1x+\cdots+a_{n-m}x^{n-m}\right)+\zeta_m\\ &\equiv x^m(a_0)+\zeta_m&\pmod{x^{m+1}} \end{align*} This behaviour is also valid, when we consider compositions of $f$. This will become more obvious when we calculate the next steps.

Step: $(m-1)\rightarrow (m-2)$

We obtain from (4)

\begin{align*} f^{(m)}&(x)-x\\ &\equiv f^{(m-2)}\left(f\left(x^ma_0+\zeta_m x\right)\right)-x&\pmod{x^{m+1}}\\ &\equiv f^{(m-2)}\left(\left(x^ma_0+\zeta_m x\right)^mq\left(x^ma_0+\zeta_m x\right)\right.\\ &\qquad\qquad\quad +\left.\zeta_m\left(x^ma_0+\zeta_m x\right)\right)-x&\pmod{x^{m+1}}\tag{5}\\ &\equiv f^{(m-2)}\left(x^m q\left(x^m a_0+\zeta_m x\right)+\zeta_m x^m _0+\zeta_m^2 x\right)-x&\pmod{x^{m+1}}\tag{6}\\ &\equiv f^{(m-2)}\left(x^m a_0+\zeta_m x^m a_0+\zeta_m^2 x\right)-x&\pmod{x^{m+1}}\tag{7}\\ \end{align*}

Comment:

• In (5) we note the only contribution of $\left(x^ma_0+\zeta_m x\right)^m\pmod{x^{m+1}}$ is $\zeta_m^m x^m$ and since $\zeta_m^m=1$ we get $x^m$.

• In (6) we note the only contribution of $x^mq\left(x^m a_0+\zeta_m x\right)\pmod{x^{m+1}}$ is the constant part $a_0$ of $q$ multiplied with $x^m$.

Observation: When looking at (4) and (7) we might see a pattern, but to be sure we add one step more.

Step: $(m-2)\rightarrow (m-3)$

We obtain from (7) and continue in the same way as in the step before \begin{align*} f^{(m)}&(x)-x\\ &\equiv f^{(m-3)}\left(f\left(x^ma_0+\zeta_m x^m a_0+\zeta_m^2 x\right)\right)-x\qquad\qquad\quad\pmod{x^{m+1}}\\ &\equiv f^{(m-3)}\left(\left(x^ma_0+\zeta_m x^m a_0+\zeta_m^2 x\right)^mq\left(x^ma_0+\zeta_m x^m a_0+\zeta_m^2 x\right)\right.\\ &\qquad\quad\quad +\left.\zeta_m\left(x^ma_0+\zeta_m x^m a_0+\zeta_m^2 x\right)\right)-x\qquad\qquad\pmod{x^{m+1}}\\ &\equiv f^{(m-3)}\left(x^m q\left(x^ma_0+\zeta_m x^m a_0+\zeta_m^2 x\right)\right)\\ &\qquad +\zeta_m\left(x^ma_0+\zeta_m x^m a_0+\zeta_m^2 x\right)-x\qquad\qquad\qquad\ \pmod{x^{m+1}}\\ &\equiv f^{(m-3)}\left(x^m a_0+\zeta_m x^m a_0+\zeta_m^2 x^m a_0+\zeta_m^3 x\right)-x\qquad\pmod{x^{m+1}}\tag{8}\\ \end{align*}

We see from (4),(7) and (8) a pattern which we will prove next. In fact we could start the answer with the next step.

Step: $(m-k)\rightarrow (m-k-1)$

We show the following is valid for $1\leq k \leq m-1$: \begin{align*} f^{(m-k)}&\left(a_0 x^m\sum_{j=0}^{k-1} \zeta_m^j+\zeta_m^k x\right)\\ &\equiv f^{(m-k-1)}\left(a_0 x^m\sum_{j=0}^{k} \zeta_m^j+\zeta_m^{k+1} x\right)&\pmod{x^{m+1}}\tag{9} \end{align*}

We obtain \begin{align*} f^{(m-k)}&\left(a_0 x^m\sum_{j=0}^{k-1} \zeta_m^j+\zeta_m^k x\right)\\ &\equiv f^{(m-k-1)}\left(f\left(a_0 x^m\sum_{j=0}^{k-1} \zeta_m^j+\zeta_m^k x\right)\right)&\pmod{x^{m+1}}\\ &\equiv f^{(m-k-1)}\left(\left(a_0 x^m\sum_{j=0}^{k-1} \zeta_m^j+\zeta_m^k x\right)^mq\left(xa_0 x^m\sum_{j=0}^{k-1} \zeta_m^j+\zeta_m^k x\right)\right.\\ &\qquad\qquad\quad +\left.\zeta_m\left(a_0 x^m\sum_{j=0}^{k-1} \zeta_m^j+\zeta_m^k x\right)\right)&\pmod{x^{m+1}}\\ &\equiv f^{(m-k-1)}\left(x^mq\left(xa_0 x^m\sum_{j=0}^{k-1} \zeta_m^j+\zeta_m^k x\right)\right.\\ &\qquad\qquad\quad+\left(\zeta_m\left(a_0 x^m\sum_{j=0}^{k-1} \zeta_m^j+\zeta_m^k x\right)\right)&\pmod{x^{m+1}}\\ &\equiv f^{(m-k-1)}\left(x^ma_0 +\zeta_m\left(a_0 x^m\sum_{j=0}^{k-1} \zeta_m^j+\zeta_m^k x\right)\right)&\pmod{x^{m+1}}\\ &\equiv f^{(m-k-1)}\left(a_0 x^m\sum_{j=0}^{k} \zeta_m^j+\zeta_m^{k+1} x\right)&\pmod{x^{m+1}}\\ \end{align*} and the claim follows.

Putting all together

With the help of (9) we can show OPs claim (1).

We obtain \begin{align*} f^{(m)}&(x)-x\\ &\equiv f^{(m-1)}\left(x^ma_0+\zeta_m x\right)-x\qquad\qquad\qquad\qquad\qquad\ \ \pmod{x^{m+1}}\tag{10}\\ &\equiv f^{(1)}\left(a_0 x^m\sum_{j=0}^{m-2} \zeta_m^j+\zeta_m^{m-1} x\right)-x\qquad\qquad\qquad\quad\pmod{x^{m+1}}\tag{11}\\ &\equiv \left(a_0 x^m\sum_{j=0}^{m-2} \zeta_m^j+\zeta_m^{m-1} x\right)^m q\left(a_0 x^m\sum_{j=0}^{m-2} \zeta_m^j+\zeta_m^{m-1} x\right)\\ &\qquad\qquad\quad+\zeta_m\left(a_0 x^m\sum_{j=0}^{m-2} \zeta_m^j+\zeta_m^{m-1} x\right)-x\qquad\quad\pmod{x^{m+1}}\tag{12}\\ &\equiv x^m q\left(a_0 x^m\sum_{j=0}^{m-2} \zeta_m^j+\zeta_m^{m-1} x\right)\\ &\qquad\qquad\quad+\zeta_m\left(a_0 x^m\sum_{j=0}^{m-2} \zeta_m^j+\zeta_m^{m-1} x\right)-x\qquad\quad\ \pmod{x^{m+1}}\tag{13}\\ &\equiv x^m a_0+\zeta_m\left(a_0 x^m\sum_{j=0}^{m-2} \zeta_m^j+\zeta_m^{m-1} x\right)-x\qquad\qquad\quad\pmod{x^{m+1}}\\ &\equiv a_0 x^m\sum_{j=0}^{m-1} \zeta_m^j+\zeta_m^{m} x-x\qquad\qquad\qquad\qquad\qquad\qquad\ \pmod{x^{m+1}}\tag{14}\\ &\equiv 0\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\pmod{x^{m+1}}\tag{15}\\ \end{align*} and the claim follows.

Comment:

• In (10) we apply the result (4) of the first step to derive $f^{(m-1)}$ from $f^{(m)}$.

• In (11) we apply the main result (9) $m-2$ times to reduce $f^{(m-1)}$ to $f^{(1)}=f$.

• In (12) we apply (2), the representation $f(x)=x^mq(x)+\zeta_m x$.

• In (13) to (14) we do simplifications $\pmod{x^{m+1}}$ similarly to the steps before.

• In (15) we note $\zeta_m^m=1$ so that $\zeta_m^{m} x-x=0$ and we also use \begin{align*} \sum_{j=0}^{m-1} \zeta_m^j=\frac{1-\zeta_m^{m}}{1-\zeta_m}=0 \end{align*}