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
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}$
07.01.2024 19:41
08.01.2024 02:06
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.
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.
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.