Bump

$\frac {p (n)(x)-p(x)}{p (n-1)(x)-x} $. So it is divided by $(p (x)-x)^2. $ If polynomial $p (x) $ satisfies that. It yields a contradiction$\implies\frac {p (x)-x}{(p (x)-x)^2} .$ Note, $\forall n>1, \deg (p)>1$

Physicsknight wrote: $\frac {p (n)(x)-p(x)}{p (n-1)(x)-x} $. So it is divided by $(p (x)-x)^2. $ If polynomial $p (x) $ satisfies that. It yields a contradiction$\implies\frac {p (x)-x}{(p (x)-x)^2} .$ Note, $\forall n>1, \deg (p)>1$ It is hard to understand your phrases. Can you elaborate this?

Here is the official solution

What is RMM?

Physicsknight wrote: $\frac {p (n)(x)-p(x)}{p (n-1)(x)-x} $. So it is divided by $(p (x)-x)^2. $ If polynomial $p (x) $ satisfies that. It yields a contradiction$\implies\frac {p (x)-x}{(p (x)-x)^2} .$ Note, $\forall n>1, \deg (p)>1$ We know that $R(x) - S(x)|Q(R(x)) - Q(S(x))$ thus $(P(x)-x)^2|P^{n-1}(x)-x|P^n(x)-P(x)$ and $(P(x)-x)^2|P^{n}(x)-x$ so we have $(P(x)-x)^2|P(x)-x$ a contradiction. Is this what you mean? I am not sure if this works for polynomials with complex coefficients...I mean, it seems so easy compared to the official solution...

I also solved by using $A(x)|P(B(x)) - P(C(x))$ for $A(x)|B(x)-C(x)$. I'm sure this statement is true even for complex coefficient cause the proof is just factorization. (So I agree with Physicsknight's proof.) But I'm still suspicious of myself because this is the hardest number for RMM tst in Iran and others' approach. If someone figure out the mistake, please let us know.

Mobashereh wrote: Physicsknight wrote: $\frac {p (n)(x)-p(x)}{p (n-1)(x)-x} $. So it is divided by $(p (x)-x)^2. $ If polynomial $p (x) $ satisfies that. It yields a contradiction$\implies\frac {p (x)-x}{(p (x)-x)^2} .$ Note, $\forall n>1, \deg (p)>1$ We know that $R(x) - S(x)|Q(R(x)) - Q(S(x))$ thus $(P(x)-x)^2|P^{n-1}(x)-x|P^n(x)-P(x)$ and $(P(x)-x)^2|P^{n}(x)-x$ so we have $(P(x)-x)^2|P(x)-x$ a contradiction. Is this what you mean? I am not sure if this works for polynomials with complex coefficients...I mean, it seems so easy compared to the official solution... Why $(P(x)-x)^2\mid P^{n-1}(x)-x$? $n$ is constant.

@Dadgarnia The problem posted says for all $n>1$. Oh you mean, we need to find $p(x)$ for each $n$, right?

bumjoooon wrote: @Dadgarnia The problem posted says for all $n>1$. Oh you mean, we need to find $p(x)$ for each $n$, right? Yes.

No polynomials work. Preliminary claim: If $r\in \mathbb{C}$ then $(x-r)^n\mid p(r)$ implies $(x-r)^{n-1} \mid p'(r)$; to see this the derivative rules still hold and we can think of it as a derivative in two real variables (real part + imaginary part). Claim: $p(x)-x$ has no square factors. Suppose $(x-r)^2\mid p(x)-x$ This implies $p(r)=r$ and $p'(r)=1$. Then, $(x-r)^2 \mid \frac{d^2}{(dx)^2} p^n(x)$ $\frac{d}{dx} p^n(x) = \prod\limits_{j=0}^{n-1} p'(p^j(x))$. At $x=r$ this is simply 1 $\frac{d}{dx} \prod\limits_{j=0}^{n-1} p'(p^j(x)) |_{x=r}=\sum\limits_{j=0}^{n-1} \frac{d}{dx} p'(p^j(x)) \prod\limits_{k\ne j} p'(p^k(x)) |_{x=r}$ First, note $\prod\limits_{k\ne j} p'(p^k(r)) = \prod\limits_{k\ne j} p'(r)=1$ Therefore, this is $\sum\limits_{j=0}^{n-1} \frac{d}{dx} p'(p^j(x)) = \sum\limits_{j=0}^{n-1} p''(p^j(x)) \frac{d}{dx} p^j(x)|_{x=r}$ Recall $\frac{d}{dx} p^j(x)|_{x=r} = 1$, so $\sum\limits_{j=0}^{n-1} p''(p^j(x))|_{x=r} = \sum\limits_{j=0}^{n-1} p''(r)=np''(r)$ We also know this is 0. We know that if $x-r\mid p''(x) = \frac{d^2 (p(x)-x)}{(dx)^2}$ then $p(x)-x$ is divisible by $(x-r)^3$. In fact, I contend that if $m>1$ and $(x-r)^n\mid p(x)-x$ then $(x-r)^{m+1}\mid p(x)-x$, which implies $p(x)\equiv x$. Let $f(j,k)=p^{(j)}(p^k(x))$. By inductive hypothesis, we know that $f(0,k)|_{x=r}=r, f(1,k)|_{x=r}=1$ and for all $2\le j< m, f(j,k)|_{x=r}=0$. WTS: $f(m,k)|_{x=r}=0$ Note if a summand has terms of the form $f(j,k)$ for $2\le j\le n-1$, we can ignore it because no matter how many derivatives I take, the $j$ cannot exceed $m-1$. This means we eventually only get terms with $\sum\limits_{j=0}^{n-1} f(m,j) \cdot \prod f(1,k)^{a_k}$. This sums to $np^{(m)}(r)$ and is also 0. This implies that $p(x)-x$ has no square factors. (For a concrete example, going fromom 2 to 3, we have a sum $\sum\limits_{j=0}^{n-1} f(2,j) \prod f(1,k)^{a_k}$ and we want to take its derivative. The derivative of $f(2,j) \prod f(1,k)^{a_k}$ at $x=r$ is just $f(3,j) \prod\limits_{l<j} f(1,l)$ because I must take the derivative of one term, but if I do it on $f(1,k)$ I have a $f(2,k)$ term. Since it is in a product, the term vanishes when $x=r$. Knowing $p(x)-x$ has no square factors, the given condition is equivalent to $p(x)-x\mid p'(x)^n-1$; to see this, suppose $x-r\mid p(x)-x$. Since $(x-r)^2\mid p^n(x)-x, x-r\mid \frac{d}{dx} p^n(x) - 1$. Note $\frac{d}{dx} p^n(x)=\prod\limits_{j=0}^{n-1} p'(p^j(x))$. When $x=r, p^j(r)=r$ so $1=p'(r)^n$. Let $q(x)=p(x)-x$. This is also sufficient because if $x-r\mid q'(x), q(x)$ then $(x-r)^2\mid q(x)$. This implies $q'(r_t)=\prod\limits_{j\ne t} (r_t-r_j)$. We also know it is $\omega_n^{e_t}-1$ where $\omega_n=e^{\frac{2\pi i}{n}}$. After a while, I heard it scream LAGRANGE INTERPOLATION (ISL 19 A5 anyone?) !! Claim: $$\sum\limits_{j=1}^m \frac{1}{\prod\limits_{k\ne j} (x_j-x_k)}=0$$ Proof 1, via lagrange interpolation: $$\sum\limits_{j=1}^m \frac{1}{\prod\limits_{k\ne j} (x_j-x_k)}=\sum\limits_{j=1}^m \frac{[x^{m-1}] \prod\limits_{k\ne j} (x-x_k)}{\prod\limits_{k\ne j} (x_j-x_k)}=[x^{m-1}]\sum\limits_{j=1}^m 1\frac{\prod\limits_{k\ne j} (x-x_k)}{\prod\limits_{k\ne j} (x_j-x_k)}$$ Consider a polynomial $A(x)$ with degree $\le m-1$ such that $A(x_1)=\cdots=A(x_m)=1$. We can see $A(x)\equiv 1$. $$[x^{m-1}]\sum\limits_{j=1}^m A(x_j)\frac{\prod\limits_{k\ne j} (x-x_k)}{\prod\limits_{k\ne j} (x_j-x_k)}=[x^{m-1}]A(x)=0$$ Proof 2: We multiply the expression by $\prod\limits_{1\le j<k\le n} (x_j-x_k)$. The new expression has degree $\binom n2 - (n-1)$. Claim: If a multivariate polynomial $P(x_1,\cdots,x_n)$ vanishes whenever $x_i=x_j$ then $x_i-x_j\mid P(x_1,\cdots,x_n)$. Proof: Consider a monomial of largest degree containing $x_i$ but not $x_j$. Make all variables inside this monomial equal and large $\rightarrow \infty$ and all other ones equal and small $\rightarrow \epsilon$. This implies that there is a matching term with $x_j$ that gets subtracted. Therefore, if we show that $x_i-x_j$ is divisible by this polynomial for all $1\le i<j\le n$, we can see that $P$ must be 0 or have degree at least $\binom n2$. By symmetry, we can assume $\{i,j\}=\{m-1,m\}$. If I set $x_1\ge x_2\ge \cdots \ge x_m$, then $sgn(\prod\limits_{j\ne k} (x_k-x_j))=(-1)^{k-1} $ We are computing $$\left( \sum\limits_{j=1}^m \frac{1}{\prod\limits_{k\ne j} (x_j-x_k)} \right) \prod\limits_{1\le k<l \le n} (x_k-x_l)$$ When $x_{m-1}=x_m$. We can see the only two terms that matter are when $j=m-1, j=m$. When $j=m-1$ we have a contribution of $(-1)^{m-1} \prod\limits_{1\le i<j\le m, i,j\ne m-1} (x_i-x_j)$ When $j=m-1$ we have a contribution of $(-1)^{m} \prod\limits_{1\le i<j\le m, i,j\ne m} (x_i-x_j)$ Therefore, it suffices to show that $\prod\limits_{1\le i<j\le m, i,j\ne m-1} (x_i-x_j)=\prod\limits_{1\le i<j\le m, i,j\ne m} (x_i-x_j)$, which is clear because they are both polynomials in $x_m$ or $x_{m-1}$. To finish the problem, note that $0=\sum\limits_{j=1}^k \frac{1}{q'(r_j)}=\sum\limits_{j=1}^k \frac{1}{\omega_n^{e_i}-1}$ Clearly $\omega_n^{e_i}\ne 1$. Note $Re(\frac{1}{\omega_n^{e_i}-1})<0$ because $Re(\omega_n^{e_i}-1)<0$. It follows that $0=Re(\sum\limits_{j=1}^k \frac{1}{\omega_n^{e_i}-1})<0$ when $k\ge 1$, contradiction!