Find all polynomials $P$ with integer coefficients such that all the roots of $P^n(x)$ are integers. (here $P^n(x)$ means $P(P(...(P(x))...))$ where $P$ is repeated $n$ times)
Problem
Source: Iranian Third Round 2020 Number Theory exam Problem2
Tags: number theory, polynomial, integer root
22.11.2020 17:54
should we find all pairs of $(n,P)$ or the statement is holds for any arbitrary $n$?And is the coefficent set $\mathbb{R},\mathbb{C}$ or something else?
22.11.2020 18:16
it holds for every integer $n$. and it can be easily proved that the coefficients are integers.
22.11.2020 19:08
Lemma:if$deg(P) \ge 3$There are finitly many integers $m$ so that $P(x)=m$ has only integer roots. Proof:First note that the case where it has only distinct solutions can take only finitly many $m$(just note that for large enough or small enough $m$ The equation only has $2$ solutions at most.)and if there are duplicate roots the root should satisfy $P'(x)=0$ but this polynomial has finitly many roots so it's roots can produce finitly many $m$'s. Now assume that $P(x)$ has disitinct roots $r_1,r_2,\dots r_k$ then roots of $P(P(x))$ are roots of $P(x)=r_1,P(x)=r_2,\dots ,P(x)=r_k$ and set of roots of any two equations doesn't intersect.note that if any two of these have only one distinct root ($r_1,r_2$ for example)then we will : $P(x)-r_1=(x-t)^l,P(x)-r_2=(x-e)^l$ comparing the coefficients of the second highest degree will give us that $e=t \Rightarrow r_1=r_2$ so the number of distinct integer roots of $P(P(x))$ is more than $P(x)$ repeating the same will give us that the number of distinct roots of $P^n(x)$ increases when $n$ increase.taking a large enough $n$ and noting that roots of $P^{n+1}(x)$ are the situation where $P(x)$ equels to roots of $P^n(x)$ will give us a contradiction according to the first lemma. Note:some case chase is remained will add it later.
22.11.2020 19:10
I have a solution which should work for $deg P>2$. Define $P(x)$ as good if all of its roots are integers Lemma: assume $deg P=n>2$. Then $S_P=\{k\in \mathbb{Z}| P(x)-k \text{is good}\}$ is finite. Proof: basically by using the graph of the function $y=P(x)$, for $|k|$ big enough there at most (depending on $n$ odd or even) $1,2<n$ solutions to $P(x)=k$. Assume at least one of the roots $x_1,...,x_n$ of $P$, wlog $x_1$, is nonzero. If $a(P(x)-x_1)\cdots(P(x)-x_n)$ is good, then $P(x)-x_1$ is good, and so $P(x)-x_1=a(x-t_1)(...)(x-t_n)$ where at least one of the $t_i$, wlog $t_1$, is nonzero (otherwise all coefficients except the first and the last of $P(x)$ should be $0$, but this would cause a contradiction since $ax^n-b$ has nonreal roots for $n>2$). Furthermore $t_1$ can't be $=x_1$, otherwise you would have $P(t_1)=P(x_1)=0$, and not $P(t_1)=x_1$. By the same logic as before, $P(x)-t_1$ is good and is equal to $a(x-u_1)\cdots(x-u_n)$, where $u_1$ is nonzero and different from $x_1$ and $u_1$. Going on with this pattern you have infinitely many $k$s for which $P(x)-k$ is good, so this is a contradiction to our lemma. Therefore all of the roots of $P$ are $0$ and $P(x)=ax^n$
22.11.2020 19:10
Taha1381 wrote: Lemma:if$deg(P) \ge 3$There are finitly many integers $m$ so that $P(x)=m$ has only integer roots. Proof:First note that the case where it has only distinct solutions can take only finitly many $m$(just note that for large enough or small enough $m$ The equation only has $2$ solutions at most.)and if there are duplicate roots the root should satisfy $P'(x)=0$ but this polynomial has finitly many roots so it's roots can produce finitly many $m$'s. Now assume that $P(x)$ has disitinct roots $r_1,r_2,\dots r_k$ then roots of $P(P(x))$ are roots of $P(x)=r_1,P(x)=r_2,\dots ,P(x)=r_k$ and set of roots of any two equations doesn't intersect.note that if any two of these have only one distinct root ($r_1,r_2$ for example)then we will : $P(x)-r_1=(x-t)^l,P(x)-r_2=(x-e)^l$ comparing the coefficients of the second highest degree will give us that $e=t \Rightarrow r_1=r_2$ so the number of distinct integer roots of $P(P(x))$ is more than $P(x)$ repeating the same will give us that the number of distinct roots of $P^n(x)$ increases when $n$ increase.taking a large enough $n$ and noting that roots of $P^{n+1}(x)$ are the situation where $P(x)$ equels to roots of $P^n(x)$ will give us a contradiction according to the first lemma. same solution
25.11.2020 15:44
I dont know that if this counts as a different solution or not but anyways here it goes: first assume that deg $P(x)$ is atleast 2. and assume the leading coefficient of $P$ is positive. consider all of the integer roots of $P^n(x)$for any positive integer n the set A. I’ll prove that A has finitely many members. we know there exists a N such that for any n>N we have $p(n)<p(n+1)$. and cause deg $P$ is atleast 2 there exists a M such that for any m>M we have $P(m)>m$. now if A doesn’t have a bound from above then there is 2 integers in A like r>s>Max(M,N) such that $P^m(r)=0,P^n(s)=0$ and m>n but you can easily see that : $P^m(r)>P^m(s)>P^n(s)=0$ contradiction so A is bounded from above. and similarly we can say A is bounded from below. now just like above we can find out that the distinct roots of $P^{n+1}(x)$ is more than the distinct roots of $P^n(x)$ so A can’t have finitely many members. and we are done.
17.01.2021 13:23
Here is my solution , which did got $\frac{2}{15}$ Assume $deg(p)=m>1$ First we have that if $P(x)$ works then clearly $P^n(x)$ works aswell. Let $a$ be the leading coeficient of $P$ which we have $|a|>1$ hence the leading coeficient of $P^n(x)$ is $a^{\frac{m^n-1}{m-1}}$. clearly in a Polynomial with integer roots and integer coeficients the leading coeficient devide $P(0)$. so we have $$a^{\frac{m^n-1}{m-1}}|(P^{n+1}(0),P^n(0))$$so $$a^{\frac{m^n-1}{m-1}}|P(0)$$making $n$ be large enough we get $$P(0)=0$$assume we have $a_1,...,a_m$ are the roots of $P$. and also $|a_1|>0$ so we have the roots of $$p^n(x)-a_1$$are integers aswell. the leading coeficient is again $a^{\frac{m^n-1}{m-1}}$ so we have $$a^{\frac{m^n-1}{m-1}}|a_1$$which gives contradiction . So all the roots of $P$ are $0$ so we have $$P(x)=ax^n$$so we just go for $|a|=1$. Yet again we have $P^n(x)-a_1$ have all its roots as integers. let $P_n(x)=P^n(x)$ so we have $$P_n(x)-a_1=Q_n(x)$$Assume we have $2^t> |a_1|$. and let $n>t^2+t+10$ at the moment. Lets have $$P_n(x)=u (x-b_1)^{c_1}...(x-b_r)^{c_r}$$we prove $r \le 2$. Assume this is not the case , so $r>2$. and let $h_1,...,h_v$ be the roots of $Q_n$. so we must have $$Q_n(b_i)=a_1$$so Let $$T(i)=|(b_i-h_1)...(b_i-h_v)| =|a_1|$$We also have $v=Deg(P_n)=Deg(P)^n=m^n$, so since $r>2$ by PHP , there is an $i$ such that $$T(i) \ge 2^{\frac{m^n}{3}}$$which is contradiction . Using the same logic $Q$ has $2$ distinct roots atmost. one of the roots of $P$ is $0$ aswell so write $$x^t(x-i)^{m^n-t}+a_1=(x-j)^k(x-l)^{m^n-k}$$WLOG assume $k>\frac{m^n}{2}$ so we must have $|j|=1$ , if $j=1$ then clearly $i=2$ so again $l=-1$, this is easy to reach contradiction now. so let $j=-1$ so it gives $i=-2$ and again $l=1$. This is the same and we are done here aswell. so it is just left to assume $Q_n(x)=(x-i)^{m^n}$ so we have $$x^t(x-j)^{m^n-t}+a_1=(x-i)^{m^n}$$Yet again we have $|i|=1$. if $i=1$ then clearly $j=2$ aswell. so letting $x=y+1$ we have $$y^{m^n}-a_1=(y+1)^t(y-1)^{m^n-t}$$but we all know that $$a_1^{\frac{1}{m^n}}$$is a root which is complex , so we get contradiction here , for $i=-1$ we can get the same contradiction aswell. so we are done by checking $Deg(P)=1$ which gives the liner solutions of $$-x+b,x+b$$
23.01.2021 19:00
Iran Third Round 2020 NT Exam P2 wrote: Find all polynomials $P \in \mathbb{Z}[x]$ such that all the roots of $P^n(x)$ are integers for all $n \in \mathbb{N}$. Splendid problem My solution is too lengthy though. Let $\text{deg} \ P = n$. If $n = 0$, it is immediate that no such solution works. (Note: Here I assume that "all the roots" means that the set of roots is non-empty, and if $P(x) = 0$, then there are infinitely many non-integer roots.) From here onwards, assume $n \ge 1$. Claim 01. If $P(a) = 0$ for some integer $a$, then $P(x) - a$ has $n$ roots (repeated roots are allowed). Proof. To prove this, notice that $P(P(x))$ has $n^2$ integer roots. Let $\{ a_1, a_2, \dots, a_n \}$ be the integer roots of $P$. Suppose that for some $i$, $P(x) = a_i$ has less than $n$ solutions, then by Pigeon Hole Principle, there exists some $1 \le j \le n$ such that $P(x) = a_j$ has at least $n + 1$ solution. However, since $\text{deg} \ P = n$, then we conclude that $P(x) = a_j$ for all $x \in \mathbb{R}$, which means $P$ is a constant, a contradiction. Therefore, we must have $P(x) = a_i$ having exactly $n$ solutions for each $a_i$ being a root of $P$. This also implies that $P(x) - a$ has at least one integer solution for any $a$ root of $P$. Suppose that $n \ge 2$. Let $\mathcal{R}$ be the set of all the roots of polynomial $P^n(x)$ for any $n \in \mathbb{N}$. Claim 02. $\mathcal{R}$ is finite. Proof. Consider a directed graph where all members of $\mathcal{R}$ are denoted as vertex. We draw an edge from $a \to b$ if $P(b) = a$. From the previous claim, every vertex has an outdegree. Now, for the sake of contradiction, we suppose that there are infinitely many members of $\mathcal{R}$, which means that the graph must be an infinite graph. Take an infinite length path in the directed graph: \[ 0 \to v_1 \to v_2 \to v_3 \to \dots \]where $P^i(v_i) = 0$ for all $i \in \mathbb{N}$. WLOG $P$ has a positive leading coefficient. Subclaim. $\mathcal{R}$ has an upper bound. Proof. Suppose otherwise, that $\mathcal{R}$ isn't bounded from above. Since $P$ has a positive leading coefficient, then $P^i(x) > P^i(y)$ for all $x > y > C$ for a particular constant $C$. Now, since $\text{deg} \ P \ge 2$, we have $P(x) > x$ for large enough $x$, which means that $P^k(x) > x$ for large enough $x$ (in particular, for all $x > C_2$ for a constant $C_2$) and any $k \in \mathbb{N}$. Therefore, we could take large $v_i > v_j > \max(C,C_2)$ and $i > j$. Hence, we have \[ 0 = P^i(v_i) > P^i(v_j) > P^j(v_j) = 0 \]which is a contradiction. Subclaim. $\mathcal{R}$ has a lower bound. Proof. Suppose otherwise, that $\mathcal{R}$ isn't bounded from below. If $P$ is of even degree, then the same exact method as before will work. Otherwise, if $P$ is of odd degree, then we have $P^i(x) < P^i(y)$ for all $x < y < C$ for a particular constant $C$. Now, since $\text{deg} \ P \ge 2$, we have $P(x) < x$ for small enough $x$ as $P$ is of odd degree. This also forces $P^k(x) < x$ for small enough $x$ (in particular, for all $x < C_2$ for a constant $C_2$) and any $k \in \mathbb{N}$. Therefore, we could take small $v_i < v_j < \min (C, C_2)$ and $i > j$. Hence, we have \[ 0 = P^i(v_i) < P^i(v_j) < P^j(v_j) = 0 \]which is also a contradiction. Therefore, $\mathcal{R}$ has an upper and lower bound, which forces $\mathcal{R}$ is finite, a contradiction. Claim 03. $P$ has a unique root.
Thus, $P(P(r_i)) = r_i$ for all $1 \le i \le k$. Taking $r_i$ to be the roots of $P(x)$, we have $r_i = P(P(r_i)) = P(0)$, which is unique. Therefore, there is a unique root of $P(x)$. Let $r = P(0)$. We know that $P(x) - r$ has only $0$ as its root, since if there exists $j \not= 0$ such that $P(j) = r$, then $j = P(P(j)) = P(r) = 0$. Hence, we conclude that $P(x) - r = ax^b$ for some $a \in \mathbb{Z}_{\not= 0}$ and $b \in \mathbb{N}_{\ge 2}$. This gives us \[ P(x) = ax^b + r \]However, we know that $P$ only has one root, that is, $r$, then both $P(r) = P'(r) = 0$. \[ ar^b + r = abr^{b - 1} = 0 \]We have $b \ge 2$, so either $a$ or $r$ is $0$. If $a = 0$, then $ar^b + r = 0 \Rightarrow r = 0$. So, in either case, $r = 0$. Hence, $P$ only has $0$ as its root, which means $\boxed{P(x) = ax^b \text{ for any }a \in \mathbb{Z}_{\not= 0} \text{ and } b \in \mathbb{N}_{\ge 2}}$. This indeed works, since $P^n(x) = 0 \Rightarrow a(P^{n - 1}(x))^b = 0 \Rightarrow P^{n - 1}(x) = 0$. Now, we are just left with the case $P$ being linear. Let $P(x) = ax + b$, where $a \in \mathbb{Z}_{\not= 0}$ and $b \in \mathbb{Z}$. Notice that $P(x)$ has an integer root by the condition, so $a \mid b$. Therefore, we could rewrite it as $P(x) = a(x + c)$ for some $c \in \mathbb{Z}$. Now, notice that $P^n(x) = 0$ has $-\frac{c}{a^{n - 1}} - \frac{c}{a^{n - 2}} - \dots - c$ as a root, which is easily proven by induction. Since all roots of $P^n(x)$ is an integer, then \[ \frac{c}{a^{n - 1}} + \frac{c}{a^{n - 2}} + \dots + c \in \mathbb{Z} \]for all $n \in \mathbb{N}$, for a fixed value $c \in \mathbb{Z}, a \in \mathbb{Z}_{\not= 0}$. If $c = 0$, any polynomial $\boxed{P(x) = ax, a \in \mathbb{Z}_{\not= 0}}$ works. For the same reason as above, this polynomial works. Suppose $c \not= 0$. Claim. $a = 1$ or $a = -1$. Proof. Suppose otherwise, then $|a| \ge 2$. Take a large positive integer $N$ such that $a^N > 10c^{100}$. Now, we have \[ \frac{c}{a^{N }} + \frac{c}{a^{N - 1}} + \dots + c \in \mathbb{Z} \ \text{and} \ \frac{c}{a^{N - 1}} + \frac{c}{a^{N - 2}} + \dots + c \in \mathbb{Z} \]Thus, their difference must be an integer, which means $\frac{c}{a^N} \in \mathbb{Z}$, contradicting out choice of $c$. Thus, we must have $|a| =1$. This means that $a = -1$ or $a = 1$, giving $\boxed{P(x) = x + c \ \text{or} \ -x + c, \ \text{for any } c \in \mathbb{Z}}$. To check that this works, note that $P^n(x) = x + nc$ and $P^n(x) = -x + nc$ in both cases, which has $nc$ and $-nc$ as its root, which are obvious integers as well.