Fall 2015, problem 3
Comments
Guys ... in order to answer do we just use the same coding as Latex ?? the dollar and fractions codes and all that ?? or des this have diffrent coding system ?
Just like latex. To produce $x^n$ type
$x^n$
This must be true for all the infinitely many possible values of y, the polynomials on the LHS and RHS must be the same.
Hi, I'm Hubert from Paris, polynomial $P(x)x^N$ is null ($=0$) because with infinitely many roots.  edited 
What do you mean when you say that this polynomial is "null?"
We have to find real polynomials $P(x)$ such that $(P\circ P)(x)=(P(x))^N$.
Let $Q(x)=x^N$
So now we can write $(P\circ P)(x)=(P(x))^N=(Q\circ P)(x) \implies P(P(x))=Q(P(x)) \implies P(x)=Q(x)=x^N$
Therefore the required polynomial is $P(x)=x^N$
Let's name the degree of P: $deg(P)=n;$ The equation implies that $n²=n.N$ so $n=0$ or $n=N$ : if $n=0$, for each real number $x$, $P(x)=b$ (b is a real number) and $b=b^N$ so $b(b^(N1)1)=0$ ; if $N=0$,then $b=1;$ if $N=1$, then all real numbers satisfies the equation. if $N>=2$, if it is odd then b can be either 0,1 or 1. If it's not, b can be 0 or 1. *if $n=N$, $P(x)=x^N$ is abviously a solution, we will show that it is the only one; First, we show that if $P(x)=a.x^N$ (with a different from 0) then $ a=1$ : Let $P(x)=a.x^N$, the equation gives us that $a.(a.x^N)^N=(a^N)(x^N) $ which implies that $(a1).(a^N)=0 So a=1$. The degree of P has to be $N$, so let's suppose that $P(x)=a.x^N+Q(x)$ where $Q$ is a polynomial of degree $deg(Q)\<N$; And we have: $P(P(x))=a.(a.x^N+Q(x))^N+Q(a.x^N+Q(x))$ and $(P(x))^N=(a.x^N+Q(x))^N$ the equation gives us that $Q(a.x^N+Q(x))=(1a).(a.x^N+Q(x))^N$ We know that $deg(a.x^N+Q(x))=max(N,deg(Q))=N$ ,so these last two equations imply that $N.deg(Q)=N²$ which means that $deg(Q)=N$ (with N different from 0) which is NOT true. If $N=0$, then $n=0$ (because $n=N$) and we get back to the first case :) This prouves that in the case of $n=N$ there is only one solution: $P(x)=x^N$ for each real x.

Let $ P(x)= a_{n}x^{n}+ ... $ As degree $ P(x)=n $, $ deg[P(x)]^{N}=nN $ and $ degP\circ P =n\times n $ and so $ n= N $

As $ P \circ P(x)= a_{n}\times [P(x)]^{n}+... = a_{n}^{n+1}x^{n^{2}}+...$ and $ [P(x)]^{n} = a_{n}^{n}x^{n^{2}} +...$, we have $ a_{n}^{n} = a_{n}^{n+1} $ and so $ a_{n} =1$ Then $ P(x)= x^{n}+... $

$ P\circ P(x)= [P(x)]^{n}+Q(x)$, by one hand.But $ P\circ P = P^{n}, $ and then $ Q(x)\equiv 0 $.
So $ P(x) = x^{N} $
First of all we will try to prove that in order for the equality to hold, the degree of $P(x)$ MUST BE $N$. This is trivial. Let's assume the degree of $P(x)$ is $k$, so the degree of $P(P(x))$ is $k^2$ and the degree of ${P(x)}^N$ is $kN$ therefore $k=N$. Now ${P(P(x))}={{P(x)^N}}$, so taking the derivative on both sides would yield $=>$ ${P^{'}(P(x))P^{'}(x)}={NP(x)^{N1}P^{'}(x)}$ so ${P^{'}(P(x))}={NP(x)^{N1}}$ . Now if we repeat this procedure $N$ times we end up with ${P^{N}(P(x))}={N!}$ So this means that the leading coefficient $a$ of the $P(x)$ is equal to one ( if not we would have a contradiction ). Therefore ${P(x)}={x^N+Q(x)}$ where $Q(x)$ is a polynomial and $deg(Q)$ is strictly smaller than $N$ . $=>$ ${P(P(x))}={P(x)^N + Q(P(x))}$=${P(x)^N}$ $=>$ ${Q(P(x))}={0}$ so we have two cases. First case is $P(x)$ being a constant polynomial, which is not possible because the equation would not be true then. Second case is $Q(x)$ being a null polynomial. so the second case is the only possible case therefore ${Q(x)}={0}$ for all $x$. Finally the only possible polynomial that satisfies the equation is ${P(x)}={x^N}$.
$k²=k.N$ does Not mean that $k=N$ : if $k=0$ the value of $N$ does not realy matter, co to solve this kind of equations we write $k(kN)=0$ and the solutions will be $k=0$ or $k=N$, so, if $N=1$ $P(x)=x$ is a solution but you did forgot about $k=0$: $P(x)=c$ with c is a random real number satisfies the given equation.However, it's a very nice move to take the derivative in these cases.
There is another way to proof the statement with derivatives. Let $ R (x) := x^n$ and say $ P$ is not constant, so $ P' (a) \neq 0$ for some fixed $ a$. Then by repeatedly differentiating the equation $ P(P(x))=R(P (x)) $ at point $a$ as you did, you actually show that $P^{(n)}(P (a)) =R^{(n)}(P (a))$ for all $ n=0,1,2... $. So $ P=R$, because if two polynomials agree in all their derivatives at one point (at $ P (a) $ in this case), they are equal.
Yes ! I know what you mean, that's why I did not mention the constant case ( where $N$ is 0 because they r trivial. I kinda rushed through my proof cuz I had bunch of other stuff to do !! Anyways , thanks for correcting. Nelix, yea I used that method to prove that the leading coefficient is 1. BTW , r u guys Purdue undergrads ?
Me, no, i'm an Algerian student.
Hi I'm Pavan By Hypothesis assume that P(x)=x As per the given condition (P o P)(x)=(P(x))^N this can be taken as P(P(x))= (P(x))^N Substituting the hypothesis it becomes P(x)=(x)^N This contradicts our preassumed hypothesis that P(x)=x. This fails our hypothesis. Similarly if P(x) if chosen to be any function having the dependency in the variable x then preassumed hypothesis result in contradiction than the later obtained result. So it shows that there is no such function for the Polynomials P(x) to be this brings to the choice of Polynomial P(x) to be a constant Polynomial whose values can be either 0 or 1 P(x)=0 or P(x)=1.
Hello_kitty is right for the most part (and takes home the prize for getting to the point :) ). Just filling in the gaps.
Of course, the constant polynomials $ P(x)=1$ and $ P(x)=0$ are solutions. So is $ P(x)=1$ if $ N$ is odd. And that's it for the constant ones.
But say $ P$ assumes at least two different values. Then by continuity $ P $ also assumes any value in between these two. In particular $ P$ has infinitely many values. Now call $ P(x) =: y$. Our equation then reads $ P (y) =y^N$. Since this must be true for all the infinitely many possible values of $ y$, the polynomials on the LHS and RHS must be the same.
So $ P (x)= x^N$ for all $ x$.
Used without proof: If $ P$ and $ Q$ are polynomials over the reals with $ P (x)= Q (x) $ for infinitely many choices of $x$, then $ P =Q$.
The problem  and the answer  admit a slight generalization: If $ P$ and $Q$ are polynomials over the reals and $(P \circ P)(x) = Q (P (x)) $ for all $ x$ then either $ P$ is constant or $ P=Q$.