12
$\begingroup$

Let $f(x)$ is polynomial with complex coefficients,such $$x^2|f(x)-e^{\frac{2\pi i}{m}}\cdot x$$ where $m>1$ be give postive integers,and define $$f^{(1)}(x)=f(x),f^{(2)}(x)=f(f(x)),f^{(3)}(x)=f(f(f(x))),\cdots,f^{(m)}(x)=f(f^{(m-1)}(x))$$ show that $$x^{m+1}|f^{(m)}(x)-x$$

I try to use mathematical induction to prove.But there is no proof

$\endgroup$
4
  • $\begingroup$ It's difficult to use induction, because you would have to take with you the condition that $x^2\mid f(x)-e^{\frac{2\pi i}{m}}\cdot x$ from one case to the next. The $m$ in there looks to me like it makes it very unpractical, perhaps impossible to prove the induction step. $\endgroup$
    – Arthur
    Nov 9 '16 at 11:57
  • 1
    $\begingroup$ Interesting problem. May I ask where it comes from? $\endgroup$
    – dxiv
    Nov 11 '16 at 5:10
  • $\begingroup$ Experimentation with Mathematica shows that if $f(x)=w x+\sum_{k=2}^m a_kx^k$ then $f^{(m)}(x)=w^mx+\frac{1-w^m}{1-w}\cdot \sum_{k=2}^mP_kx^k+O(x^{m+1})$, where $P_k$ are polynomials in $w$ and $a_j$. $\endgroup$
    – Negan
    Nov 19 '16 at 19:19
  • 1
    $\begingroup$ @Inequality: I suggest to remove the acceptance mark of my answer, since a bounty question which is not already accepted might attract more user. $\endgroup$
    – epi163sqrt
    Nov 20 '16 at 11:30
10
+100
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Instructive approach! Most of the creative work here is finding a proper framework to formulate the problem. If this is done the answer can be seen at a glance. Very nice! (+1) $\endgroup$
    – epi163sqrt
    Nov 24 '16 at 7:27
  • $\begingroup$ wonderful proof ! $\endgroup$
    – Marsan
    Nov 26 '16 at 15:33
3
+50
$\begingroup$

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*}

$\endgroup$
5
  • $\begingroup$ Do I understand it correctly that you did prove the claim only for functions of the type $f(x)=x^mq(x)+\zeta_m x$ and in fact this answer is only partial? $\endgroup$
    – Negan
    Nov 20 '16 at 6:53
  • $\begingroup$ @inequality: Many thanks for accepting my answer and granting the bounty! :-) $\endgroup$
    – epi163sqrt
    Nov 20 '16 at 6:56
  • $\begingroup$ Please can you answer my question? $\endgroup$
    – Negan
    Nov 20 '16 at 7:00
  • $\begingroup$ Yes, but OPs condition was that $x^2|f(x)-\zeta_m x$ not $x^m|f(x)-\zeta_m x$. $\endgroup$
    – Negan
    Nov 20 '16 at 7:13
  • 1
    $\begingroup$ @Nemo: Oh! Yes, you're right! I've misread the claim. Thanks for pointing at it. I've offered a bounty for compensation. $\endgroup$
    – epi163sqrt
    Nov 20 '16 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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