Elmo calls a monic polynomial with real coefficients tasty if all of its coefficients are in the range $[-1,1]$. A monic polynomial $P$ with real coefficients and complex roots $\chi_1,\cdots,\chi_m$ (counted with multiplicity) is given to Elmo, and he discovers that there does not exist a monic polynomial $Q$ with real coefficients such that $PQ$ is tasty. Find all possible values of $\max\left(|\chi_1|,\cdots,|\chi_m|\right)$. Proposed by Carl Schildkraut
Problem
Source: ELMO SL 2018 A4
Tags: algebra, polynomial
02.07.2018 11:21
We claim that the answer is $A=(1,\infty )$. First, we show that $A\subseteq (1,\infty)$. In other words, If $|z_1|,|z_2|,...,|z_m|<1$, then there exist tasty polynomial $R\in \mathbb{R}[x]$ that is a multiple of $$(x-z_1)(x-z_2)\cdots (x-z_m).$$For each $z_i=r_i\mathrm{cis} (\theta_i )$ where $r_i\in \mathbb{R},\theta_i \in [0,2\pi )$, we'll define polynomial $f_{i,n}\in \mathbb{R}[x]$ by $$f_{i,n}=\begin{cases} x^{2n}-r_i^{2n} &,\text{ if }\theta_i \in \{ 0,\pi \}\\ x^{2n}-2r_i^n\cos (n\theta_i )x^n+r_i^{2n} &,\text{ otherwise.}\end{cases}$$Note that $|r_i|\leq 1$ and $(x-z_i)$ is a factor of $f_{i,n}$ for all $n\in \mathbb{Z}^+$. In case that $\theta_i \not\in \{ 0,\pi \}$, it's not hard to see that there exists arbitrary large $n$ that $|\cos (n\theta_i )|\leq \frac{1}{2}$. (To prove the above claim, one may analyze possible positions of $n\theta_i$ on the unit circle and use discrete continuity.) Anyway, we conclude that there exists arbitrary large (and so infinitely many) $n$ that $f_{i,n}$ is tasty. To construct our tasty polynomial $R$, simply use induction on $m$. For case case, we can directly use $f_{1,n}$ that is tasty. For inductive step, multiply the tasty polynomial $R_m$ from inductive hypothesis by the tasty $f_{m+1,n}$ where $n$ is large enough (so that the terms created by multiplying terms from $f_{m+1,n}$ and $R_m$ not have the same power), obvious that the coefficients still have absolute value at most one. So, our induction is done. Now, we will show that $(1,\infty )\subseteq A$. In other words, for every $a>1$, there exists $z_1,z_2,...,z_m$, all have absolute values at most $a$, such that there's no tasty polynomial that is a multiple of $$(x-z_1)(x-z_2)\cdots (x-z_m).$$Choose $z_1,z_2,...,z_m$ that $(x-z_1)(x-z_2)\cdots (x-z_m)=x^m-a^m$ where $m$ is a positive integer that $a^m=N>100$. Suppose there exists $Q(x)=x^n+b_{n-1}x^{n-1}+...+b_1x+b_0\in \mathbb{R}[x]$ that $(x^m-a^m)\cdot Q$ is tasty. Let $s=\lfloor n/m\rfloor $. Compare the coefficients of $$(x^m-N)\cdot ( x^n+b_{n-1}x^{n-1}+...+b_1x+b_0).$$We get that $b_{n-m}-N,b_{n-(i+1)m}-b_{n-im}N$ all have absolute values at most one for all $i=1,2,...,s-1$. Using induction, we can prove that, for all $i=1,2,...,s-1$, $$|b_{n-(i+1)m}|\in [N^{i+1}-N^i-N^{i-1}-...-1,N^{i+1}+N^i+N^{i-1}+...+1].$$But, consider the $x^{n-sm}$-term, we get that $-Nb_{n-sm}$ has absolute value at most one too. This is clearly impossible since $|b_{n-sm}|>N^s-\sum_{i=0}^{s-1}{N^i}>1$, done.
30.05.2022 06:24
The answer is $(1,\infty)$. First, I prove if $|\chi_j|\le 1$ for all $j$ then Elmo can construct monic $Q$ such that $ P(x)Q(x)$ is tasty. Let the real roots of $P$ be $r_1,\cdots,r_n$ and the nonreal roots be $x_1, \overline{x_1}, x_2, \overline{x_2}, \cdots, x_t, \overline{x_s}$ Let $A_j(x)=x-r_j$. For each $1\le k\le t$, if $x_k$ is a root of unity and $x_k^{c_k}=1$ then $B_{k,t}(x)=x^{tc_k}-1$. If $|x_k|<1$, let $B_{k,t}(x)=(x^{mt}-x_k^{mt})(x^{mt}-\overline{x_k}^{mt})$ for some sufficiently large $m \times t$. Since $|x_k|<1$, it follows for sufficiently large $t$, $|x_k|^{mt}<\frac 12$ If $x_k=e^{i\theta}$ where $\frac{\theta}{\pi}\notin \mathbb{Q}$ then $\{\frac{n\theta}{\pi}\}$ can get arbitrarily close to $\frac 12$. Suppose $\{ \frac{n\theta}{\pi} \} =\frac 12 + \epsilon$ then $B_{k,t}(x)=(x^{nt}-x_k^{nt})(x^{nt}-\overline{x_k}^{nt})=x^{2n} +(2\cos \theta) x^n+ 1$. Note $\epsilon$ is chosen later such that $|2\cos tn\theta|<1$. Now, define positive integers $a_1, a_2, \cdots, a_n, b_1, \cdots, b_s$ such that $\frac{a_j}{a_{j-1}}$ is an integer greater than $\deg A_{j-1}$ for all $2\le j\le n$, $\frac{b_j}{b_{j-1}}$ is an integer greater than $\deg B_{j-1}$ and $\frac{b_1}{a_n}$ is an integer greater than $\deg A_n$. This guarantees $F(x)=\prod\limits_{j=1}^n A_{j,a_j}(x) \prod\limits_{k=1}^s B_{k,b_k}(x)$. Picking $\epsilon<\frac{1}{10000b_n}$, this guarantees the expansion of $F(x)$ has one term that is the product of a bunch of numbers with modulus at most 1. Since $F(x)$ is divisible by $\prod\limits_{j=1}^n (x-r_j) \prod\limits_{k=1}^s (x-x_k)(x-\overline{x_k})$, $Q(x)$ exists. Since $F(x)\in \mathbb{R}[x], Q(x)\in \mathbb{R}[x]$ by polynomial division. Suppose $\max\left(|\chi_1|,\cdots,|\chi_m|\right)=c>1$. Consider $P(x)=x^n-c^n$ where $c^n>2$. Suppose $P(x)Q(x)$ is tasty. Let $g(x)=x-c^n$ and $Q(x)=Q_0(x^n)+xQ_1(x^n)+\cdots+x^{n-1}Q_{n-1}(x^n)$. This means the collection of $x^{tn}$ coefficients of $P(x)Q(x)$ is merely $g(x^n)Q_0(x^n)$ is a tasty polynomial, so $g(x)Q_0(x)$ is tasty. However, if a polynomial $f(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_0$ is tasty and monic and $r\ge 2$ st $f(r)=0$ then $r^n=a_{n-1}x^{n-1}+\cdots+a_0$. So $|r|^n \le |a_{n-1}| |r|^{n-1} + \cdots + |a_0|\le |r|^{n-1}+\cdots+|r|^0$, absurd if $|r|\ge 2$! It follows that $g(c^n)\ne 0$, the end!
31.05.2022 07:05
Amazing problem and solutions
06.11.2024 02:44
Fool forgets $x^n - c^n$ exists, saved by maximum modulus principle. Claim: This is possible if the value is at most $1$. Proof. We define $B_{i}$ as follows. Let $r_i = |\chi_i|$ If $\chi_i$ is a root of unity, then $B_i(x) = x^{k_iN_i} - 1$ for some $k_i$. If $\chi_i$ is not a root of unity, we define $B_i(x) = x^{2N_i} - (\chi_i^N + \chi_i^{-N}) \cdot r_i^N x^{N_i} + r_i^{2N_i}$ where Then define \[ P \cdot Q = \prod_{i=1}^N B_i(x) \]where $N_i$ are taken such that $1434 N_i < N_{i+1}$. Then no coefficients combine and as such all are in $[-1, 1]$. $\blacksquare$ Claim: Let $P$ be a nonconstant monic polynomial of degree $n$. Then for any real $r$, there exists a $z$ such that $|z| = r$ and $|P(z)| \ge r^n$. Proof. Define $q(z) = z^n \cdot P\left(\frac{r^2}{z}\right)$. Then $q(0) = r^{2n}$ so \[ r^{2n} \le \max_{|z| = r} |q(x)| = r^n \cdot \max_{|z| = r} \left|P\left(\frac{r^2}{z}\right)\right| = r^n \cdot \max_{|z| = r} \left|P(z)\right| \]implies the result by the maximum modulus principle. $\blacksquare$ Claim: There exists a counterexample if the value $r$ is more than $1$. Proof. Take $K$ such that $r^K > \frac{1}{r - 1} + \frac{1}{1434r}$. Let $\Gamma$ be the complex circle $|z| = r$. Let $F$ be a polynomial of degree $K$. Then the set of possible $F$ is uniformly equicontinuous. Take large $N > K$ such that $|x - y| < \frac{2\pi r}{N} \implies |F(x) - F(y)| < \frac{1}{1434}$. Take $P(z)$ to have $N$ roots evenly distributed about $\Gamma$. Now, let $f$ be a tasty polynomial of degree $n$. FTSOC suppose $P$ divides $f$. Then $n > \deg P > K$ so there is some $F$ such that \[ f(x) = F(x) \cdot x^{n-K} + a_{n-k-1} x^{n-K-1} + \dots + a_1 x + a_0 \]Then by the above lemma, there's a point $p$ on $\Gamma$ such that $|F(p)| \ge |r|^{K}$. This means that there is some root $p_0$ of $P(z)$ such that $|F(p)| \ge |r|^{K} - \frac{1}{1434}$. Then \begin{align*} |f(p_0)| &\ge |F(p) \cdot p_0^{n-K}| - |a_{n-K-1} x^{n-K-1} + \dots + a_1 x + a_0| \\ &\ge r^{n-K} |F(p)| - r^{n-K} |r^{-1} + r^{-2} + \dots + \dots + r^{K-n}| \\ &\ge r^{n-K} \cdot \left(r^{K} - \frac{1}{1434} - \frac{1}{r - 1}\right) > 0. \end{align*}which gives a contradiction. $\blacksquare$