Show that there exists a degree $58$ monic polynomial $$P(x) = x^{58} + a_1x^{57} + \cdots + a_{58}$$such that $P(x)$ has exactly $29$ positive real roots and $29$ negative real roots and that $\log_{2017} |a_i|$ is a positive integer for all $1 \leq i \leq 58$.
Problem
Source: China TSTST 3 Day 2 Problem 1
Tags: algebra, polynomial
18.03.2017 05:46
Does this work? Lemma: We can choose $n$ positive real roots $r_i$ and $n$ negative real roots $s_i$ such that the coefficients of $\prod_{i=1}^{n}(x-r_i)(x-s_i)$ are not zero. Proof: We use induction on $n$. Trivial for $n=1$. Assume true for $n$. We prove it true for $n+1$. Consider $\prod_{i=1}^{n+1}(x-r_i)(x-s_i) = (x-r_{n+1})(x-s_{n+1})\prod_{i=1}^{n}(x-r_i)(x-s_i) = (x^2-(r_{n+1}+s_{n+1})x+r_{n+1}s_{n+1})(x^{2n} + a_1x^{2n-1} + \cdots + a_{2n})$. Note that the coefficient of $x^k$ is $a_{k-2}-a_{k-1}(r_{n+1}+s_{n+1})+a_kr_{n+1}s_{n+1}$. Since, by the induction hypothesis, all $a_i$'s are nonzero, we can vary the $r_i$'s and $s_i$'s so that all coefficients are nonzero (e.g. vary them one at a time as necessary, which works since the coefficients are linear equations in terms of the coefficients). The Lemma is proved. By the Lemma, we can choose $29$ positive real roots $r_i$ and $29$ negative real roots $s_i$ such that the coefficients of $\prod_{i=1}^{29}(x-r_i)(x-s_i)$ are not zero. We can scale each of the $r_i$'s and $s_i$'s by the same common factor, so that the coefficients are scaled by a factor, so by increasing the scale, we can make the coefficients have a magnitude larger than 1, i.e. $\log_{2017} |a_i|$ is a positive real for all $1 \leq i \leq 58$.
18.03.2017 09:30
This kills problem (I think) Descart rule...
18.03.2017 21:21
There seems to be a translation issue. In the exam the logs are required to be positive integers.
18.03.2017 21:59
fattypiggy123 wrote: $\log_{2017} |a_i|$ is a positive integer for all $1 \leq i \leq 58$.
18.03.2017 22:55
The problem becomes easy if one is familiar with this Putnam problem: https://artofproblemsolving.com/community/c7h616738p3674025
07.09.2017 14:19
Let us prove a more general claim. For any $a\in\mathbb{R}\,,\, a> 1$ and every $n\in \mathbb{N}$, there exists a monic polynomial $P(x)=x^n+a_1x^{n-1}+\dots+a_n $ , for which coefficients holds $|a_i|=a^{k_i}\,,\, k_i\in \mathbb{ N}\,,\, i=1,2,\dots, n$ , such that all its roots are real and different, and the number of its negative and positive roots are equal (or almost equal) to $n/2$. (It means if $n$ is odd and $n=2n_1+1$, there exists such polynomials with $n_1$ negative and $n_1+1$ positive roots and also with $n_1+1$ negative and $n_1$ positive roots). Proof goes by induction on $n$. It's trivial for $n=1$. The induction step slightly differs depending to the parity of $n$. Let's consider first $n$ is even, i.e. $\text{even}\to \text{odd}$. We take a monic polynomial $Q(x)$ of degree $n$ with $n/2$ negative and $n/2$ positive different roots. Let $x_1<x_2<\dots<x_{n/2}<x_{n/2+1}<0$ and $y_1>y_2>\dots>y_{n/2}>y_{n/2+1}>0$ be two sequences of negative (corr. positive) points where the sign of $Q$ of alternatively changes as $+,-,+,-,\dots$ . Consider $P(x) := x^{n+1} + a^k Q(x)$, where $k\in \mathbb{N}$. Taking $k$ large enough, we can ensure that the sign of $P(x_i), P(y_i)$ is the same as the sign correspondingly of $Q(x_i), Q(y_i)$ , since for large enough $k$, $Q$ will dominate in these points. Since the degree of $P$ is odd $\lim_{x\to-{\infty}}=-\infty, \lim_{x\to{\infty}}=+\infty $ , implying $P$ has $n/2+1$ negative and $n/2$ positive roots. Similarly, considering $P(x) := x^{n+1} - a^k Q(x)$ , yields $P$ has $n/2$ negative and $n/2+1$ positive roots. The inductive step $n=\text{odd}\to \text{even}$: As above, we take $Q$ to have $\lfloor n\rfloor$ negative and $\lfloor n\rfloor +1$ positive roots and consider $P(x) := x^{n+1} + a^k Q(x)$ for large enough $k$.
07.09.2017 17:51
Dear dgrozev , please what do you refer to by magnitudes powers ? thank you
07.09.2017 21:22
I meant the magnitude of each of its coefficients equals some power of $a$. I edited it to be more readable.
19.03.2022 02:38
Let $n=29$. The idea is to consider $P(x)=-x^{2n}P(-\frac 1x)$ such that $P(x)$ has $n$ positive roots, because if $P(x)=0$ then $P(-\frac 1x)=0$. This means $P(x)=(x^{2n}-1)+a_{n-1}(x^{2n-1}-x)+\cdots+a_0x^n$. The idea: for $j=0,\cdots,n$, make $a_j$ have the same sign as $(-1)^{n-j}$ and $P(b^{4j})$ have the same sign as $(-1)^{n-j}$ because $a_{j}(b^{4j})^{n+j}$ dominates all the other terms. To see what $j$ makes $a_jb^{4j}$ maximized, consider a concave hull: consider the lines on a plane $y_j(x)=c_j+4jx$ where $c_j=\log_{b}|a_j|$ (i.e. $a_j=(-1)^j b^{c_j}$). When $x\in [t-\frac 12, t+\frac 12]$, $y_t(x)$ is line on the top. This means $y_j(j-\frac 12)=y_{j-1}(j-\frac 12)$ so $c_{j-1}-c_j=4j(j-\frac 12)-4(j-1)(j-\frac 12)=4j-2$. We furthermore have $c_n=0$. This means when expanding $P(b^{4m})$, we can see that the term $a_{m}(b^{4m})^{m+n}$ is the dominating term, being at least $b^2$ times greater than all other terms. To see this, note we only have to compare this term with the two neighbouring terms. Note $a_{m}(b^{4m})^{n+m} / a_{m-1}(b^{4m})^{n+m-1}=b^{c_{m}-c_{m-1} + 4m}=b^2$ and $a_{m}(b^{4m})^{n+m} / a_{m+1}(b^{4m})^{n+m+1}=b^{c_{m}-c_{m+1} - 4m}=b^2$ using $c_m-c_{m+1}=4m+2, c_{m-1}-c_m=4m$. Since this term is $b^2$ times the other terms, its modulus is greater than the sum of moduli of other terms, so $P(b^{4m})$ has the same sign as $(-1)^{n+m}$ when $m=0,1,\cdots,n$. Therefore, $P(x)$ has at least $n$ positive real roots, so it has $n$ positive and $n$ negative real roots, as needed.
29.08.2022 06:30
angiland wrote: The problem becomes easy if one is familiar with this Putnam problem: https://artofproblemsolving.com/community/c7h616738p3674025 How to elaborate further if this is applied, please?
06.09.2022 19:20
dgrozev wrote: $P(x)=x^n+a_1x^{n-1}+\dots+a_n $ , for which coefficients holds $|a_i|=a^{k_i}\,,\, k_i\in \mathbb{ N}\,,\, i=1,2,\dots, n$ Dear @dgrozev, can you elaborate where you use this assumption?
08.09.2022 11:20
This is included in the inductive assumption. Given a polynomial $Q(x)$ of degree $n,$ the induction step constructs a new polynomial $$P(x) := x^{n+1} \pm a^k Q(x)$$of degree $n+1$ which satisfies the requirements for $n+1.$ So, its coefficients are again of the form $|a_i|=a^{k_i}\,,\, k_i\in \mathbb{ N}\,,\, i=1,2,\dots, n+1.$
18.05.2024 15:19
Induction and simple estimation.