For each polynomial $P(x)$, define $$P_1(x)=P(x), \forall x \in \mathbb{R},$$$$P_2(x)=P(P_1(x)), \forall x \in \mathbb{R},$$$$...$$$$P_{2024}(x)=P(P_{2023}(x)), \forall x \in \mathbb{R}.$$Let $a>2$ be a real number. Is there a polynomial $P$ with real coefficients such that for all $t \in (-a, a)$, the equation $P_{2024}(x)=t$ has $2^{2024}$ distinct real roots?
Problem
Source: 2024 Vietnam National Olympiad - Problem 5
Tags: algebra, polynomial
pco
07.01.2024 15:00
wassupevery1 wrote: For each polynomial $P(x)$, define $$P_1(x)=P(x), \forall x \in \mathbb{R},$$$$P_2(x)=P(P_1(x)), \forall x \in \mathbb{R},$$$$...$$$$P_{2024}(x)=P(P_{2023}(x)), \forall x \in \mathbb{R}.$$Let $a>2$ be a real number. Is there a polynomial $P$ with real coefficients such that for all $t \in (-a, a)$, the equation $P_{2024}(x)=t$ has $2^{2024}$ distinct real roots? Yes, choose for example $P(x)=\frac{2x^2}a-a$ $P_{2024}(x)=t$ has exactly $2^{2024}$ distinct real roots :$x_k=a\times\cos\frac{\arccos\frac ta+2k\pi}{2^{2024}}$ where $k=1,2,...,2^{2024}$
wassupevery1
07.01.2024 19:41
The answer to this is $\boxed{\text{Yes}}$.
First, let's extend the definition of $P_n(x)$ to any positive integer $n$.
Consider the polynomial $P(x)=Cx(x-1)$ for $C \geq 4a$ and $C+2>2\sqrt{1+\dfrac{4a}{C}}$. This choice of $C$ is possible, since when $C$ tends to go to infinity, $C+2$ tends to go to $\infty$ while $2\sqrt{1+\dfrac{4a}{C}}$ tends to go to $2$.
We claim that the equation $P_n(x)=t$ has all $2^n$ real roots for all $t \in (-a, a)$.
We prove this by induction.
For $n=1$, the equation $x(x-1)=\frac{t}{C}$ has the discriminant $\Delta = 1+ \frac{4t}{C}=\frac{C+4t}{C}>0$ (since $C \geq 4a$, $C+4t>4a-4a=0$), so the equation $P_1(x)=0$ has two roots, namely $x_1 = \frac{1-\sqrt{1+ \dfrac{4t}{C}}}{2}$ and $x_2 = \frac{1+\sqrt{1+ \dfrac{4t}{C}}}{2}$.
Now assume that our claim holds true for $1, 2, \ldots, n$.
Define a sequence $(u_n)$ as $u_0=t$ and for each $1 \leq i \leq n-1$, let $u_i$ denote the greatest root, among the $2^{i-1}$ roots of the equation $P_i(x)=0$. It is trivial that $u_n>0$ for all $n>1$.
The equation $Cx(x-1)=k$, for some real number $k>-\frac{C}{4}$, has two solutions, namely $x=\frac{1+\sqrt{1+\dfrac{4k}{C}}}{2}$ and $x=\frac{1-\sqrt{1+\dfrac{4k}{C}}}{2}$. So when $k$ increases, the larger roots also increases, and the smaller root decreases. (1)
This means $u_{n+1} = \frac{1+\sqrt{1+\dfrac{4u_n}{C}}}{2}$ for all non-negative integers $n$.
Since $t<a$ and $C>4a$, it follows that $u_1 = \frac{1+\sqrt{1+ \dfrac{4t}{C}}}{2} < \frac{1+\sqrt{1+ \dfrac{4a}{4a}}}{2}<a.$
We then induct, with base case $n=0, 1$, to prove that $u_n<a$ for all positive integers $n$.
Now, the equation $Cx(x-1)=u_{n-1}$ has two roots, which are $x_1=\frac{1+\sqrt{1+\dfrac{4u_{n-1}}{C}}}{2}$ and $x_2=\frac{1-\sqrt{1+\dfrac{4u_{n-1}}{C}}}{2}$. Since $u_{n-1}$ is the largest root among the $2^{n-1}$ root, with (1) it follows that $x_1, x_2$ are the largest and smallest root among the $2^{n}$ roots of the equation $P_n(x)=t$ respectively.
Now consider the equation $Cx(x-1)=x_2$, equivalently $x(x-1)=\frac{x_2}{C}$. The discriminant of this is then $1+\frac{4x_2}{C} = \frac{1}{C} \left( C+2 \left( 1-\sqrt{1+\dfrac{4u_{n-1}}{C}} \right) \right) > \frac{1}{C} \left( C+2-2\sqrt{1+\dfrac{4a}{C}} \right)>0.$
This means the equation $Cx(x-1)=x_2$ has two distinct roots. And since $x_2$ is the smallest root among the $2^n$ roots of $P_n(x)=t$, it follows that for each of these $2^n$ roots, let's say $y$, the equation $Cx(x-1)=y$ has two distinct roots. So there are a total of $2 \cdot 2^n = 2^{n+1}$ roots, and so the equation $P_{n+1}(x)=t$ has $2^{n+1}$ roots. In addition, since the degree of $P_{n+1}(x)$ is $2^{n+1}$, it follows that the equation has exactly $2^{n+1}$ roots.
So the induction is complete, and the problem is solved.
phungthienphuoc
08.01.2024 02:06
If we let $a=2$, we will obtain another problem. Basically, we can mimic the idea of the attached problem to solve this problem.
Amiralizakeri2007
29.04.2024 23:40
Nice problem! The idea is to consider a transformation of Chebyshev polynomials in general: Let $T_{n}(x)$ be the n-th chebyshev polynomial with coefficients $(a_{i_{1}},a_{i_{2}},...,a_{i_{k}})$ where we have $[x^{i_{t}}]=a_{i_{t}}$. We Now let $T'_{k}(x)$ to be the polynomial with monomials $x^{i_{t}}$ same as $T_{n}(x)$ but with coefficients $(\frac{a_{i_{1}},}{a^{i_{1}-1}},\frac{a_{i_{2}}}{a^{i_{2}-1}},...,\frac{a_{i_{k}}}{a^{i_{k}-1}})$ where $\frac{a_{i_{t}}}{a^{i_{t}-1}}$ is the coefficient of $x^{i_{t}}$ Now we have the property that: $$T'_{n}(acos(x))=acos(nx)$$And: $$T'^{2024}_{n}(acos(x))=acos(n^{2024}x)$$With the above form we want exactly $2^{2024}$ real solutions to $acos(n^{2024}x)=t$ for $t\in(-a,a)$ which implies that we have to find $n$ such that $cos(n^{2024}x)$ intersects $y=\frac{t}{a} \in (-1,1)$ at exatcly $2^{2024}$ points for which $n=2$ works and we are done.
OronSH
10.10.2024 20:22
The answer is yes. We choose $P(x)=x^2-a$. We prove by induction that $P^{(n)}(x)$ has $2^{n-1}$ local minima and $2^{n-1}-1$ local maxima, all alternating and with absolute value at least $a$, which implies the desired. The claim clearly holds for $n=1$. Suppose it is true for some $n$. Notice that $P(x)\ge -a$ so $P^{(n+1)}(x)=-a$ at exactly the $2^n$ roots of $P^{(n)}(x)$, which must be local minima. Next, all of the $2^n-1$ local extrema of $P^{(n)}(x)$ are local maxima of $P^{(n+1)}(x)$, and they must be $>a$ since $|P^{(n)}(x)|\ge a$ implies $P^{(n+1)}(x)\ge a^2-a>a$. Finally, the maxima and minima alternate since the roots and extrema of $P^{(n)}(x)$ must alternate as well, completing the induction.
pikapika007
11.11.2024 19:17
Yes. The idea is just to force cosine roots because double angle is easy to encode as a polynomial. Consider the polynomial $P(x) = \frac{2x^2 - a^2}{a}$. Note that if we set $x = a\cos(\theta)$ then $P(a\cos(\theta)) = a\cos(2\theta)$, thus $P^{2024}(a\cos(\theta)) = a\cos(2^{2024}\theta) = t$. But this has $2^{2024}$ solutions, of the form $\theta = \frac{\cos^{-1}(\frac ta) + 2k\pi}{2^{2024}}$ across integers $1 \le k \le 2^{2024}$. Each of these produces a valid real root of $P(x)$, so we're done.