Maths Olympiad Prep

Library / /79 of 91

Algebra Difficulty 7.4 National Olympiad, round 2 Prove it India

Let r>0r > 0 be a real number. We call a monic polynomial with complex coefficients rr-good if all of its roots have absolute value at most rr. We call a monic polynomial with complex coefficients primordial if all of its coefficients have absolute value at most 1.

a. Prove that any 1-good polynomial has a primordial multiple.

b. If r>1r > 1, prove that there exists an rr-good polynomial that does not have a primordial multiple.

Solution

First, we show that if all roots of QQ have absolute value at most 11, then QQ has a primordial multiple. We use induction on degQ\deg Q.

If QQ is linear, then it is clearly primordial, so we are done.

Now assume degQ>1\deg Q > 1, and let aa be a root of QQ, and write Q(x)=(xa)Q1(x)Q(x) = (x - a)Q_1(x). By induction hypothesis, Q1Q_1 has some primordial multiple P1P_1, say of degree dd. Then, xaxd+1ad+1x - a \mid x^{d+1} - a^{d+1}, so the polynomial (xd+1ad+1)P1(x)=xd+1P1(x)ad+1P1(x)(x^{d+1} - a^{d+1})P_1(x) = x^{d+1}P_1(x) - a^{d+1}P_1(x) is a multiple of QQ, and it is primordial: Indeed, coefficients of both xd+1P1(x)x^{d+1}P_1(x) and ad+1P1(x)a^{d+1}P_1(x) have absolute values at most 11 (since a<1|a| < 1), and the polynomials have no terms in common, so their difference is also primordial. So we are done by induction.

Now we show that r>1r > 1 doesn't work. Choose a positive integer dd such that rd>2r^d > 2, and consider Q(x)=xdrdQ(x) = x^d - r^d. All roots of QQ have absolute value exactly rr. Suppose QQ has a primordial multiple P(x)=xn+an1xn1++a0P(x) = x^n + a_{n-1}x^{n-1} + \dots + a_0, and let an=1a_n = 1 for convenience. Let ω\omega be the primitive ddth root of unity. Consider the quantity

i=0d1ωniP(ωix)d=j=0najxj(1+ωjn+ω2(jn)++ω(d1)(jn))d=0jnjn(modd)ajxj, \frac{\sum_{i=0}^{d-1} \omega^{-ni} P(\omega^i x)}{d} = \sum_{j=0}^{n} a_j x^j \cdot \frac{(1 + \omega^{j-n} + \omega^{2(j-n)} + \dots + \omega^{(d-1)(j-n)})}{d} = \sum_{\substack{0 \le j \le n \\ j \equiv n \pmod d}} a_j x^j,

by standard roots of unity filter. Hence, if ll is the remainder that nn leaves upon division by dd, the above polynomial is xlP0(xd)x^l P_0(x^d) for some primordial polynomial P0(t)=tm+bm1tm1++b0P_0(t) = t^m + b_{m-1}t^{m-1} + \dots + b_0. But, since ωir\omega^{ir} are roots of QQ for 0id10 \le i \le d-1, they are roots of PP, so P0(rd)=0P_0(r^d) = 0 (because r0r \ne 0). But then,

rmd=bm1r(m1)db1rdb0r(m1)d++rd+1=rmd1rd1<rmd1 \begin{aligned} r^{md} &= | - b_{m-1}r^{(m-1)d} - \dots - b_1r^d - b_0 | \\ &\le r^{(m-1)d} + \dots + r^d + 1 \\ &= \frac{r^{md} - 1}{r^d - 1} \\ &< r^{md} - 1 \end{aligned}

since rd>2r^d > 2, contradiction! Hence QQ does not have a primordial multiple, as required.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.