Problem A. 580. (January 2013)

A. 580. Show that for every positive integer k and real number $\varepsilon$ >0 there exists a polynomial p(x)=xⁿ+a_n-1x^n-1+...+a₁x+a₀ with real coefficients such that p(x) is divisible by the polynomial (x-1)^k+1 and

$\sum_{\ell=0}^{n-1} |a_\ell| < 1+\frac{(2+\varepsilon)k^2}{n}.$

(5 pont)

Deadline expired on February 11, 2013.

Sorry, the solution is available only in Hungarian. Google translation

Az A. 574. feladat megoldásában a T_k(x) Csebisev-polinom abszolút értékét 1-gyel becsültük az $\frac{2\ell}{n-1}-1$ alakú helyeken, ahol 0 $\le$ $\ell$ $\le$ n-1 egész szám volt:

$\left|a_\ell T_k\bigg(\frac{2\ell}{n-1}-1\bigg)\right| \le |a_\ell|.$

Ez a becslés csak akkor lehet éles, ha $\frac{2\ell}{n-1}-1$ közel az +1 vagy -1 pontokhoz, vagy pedig a T_k valamelyik lokális szélsőértékéhez, ahol T_k(x) értéke szintén $\pm$ 1 (ez összesen k+1 pont a [-1,1] intervallumban), vagy pedig $|a_\ell|$ kicsi, például 0.

A feladat megoldásához egy "ritka" polinomot fogunk konstruálni, aminek összesen csak k+2 nemnulla együtthatója van. (A polinom foka sokkal nagyobb lesz, mint k.)

Megoldás. Fel fogjuk használni az A. 574. feladat megoldásának több elemét, így a következő lemmát:

1. lemma. Ha a $p(x)=x^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0$ polinom osztható az (x-1)^k+1 polinommal, akkor tetszőleges, legfeljebb k-adfokú q(y) polinomra

$\sum\limits_{\ell=0}^n a_\ell \, q(\ell) = 0.$

(A lemma bizonyítása megtalálható az A. 574. feladat megoldásánál.)

Legyen k és $\varepsilon$ >0 rögzített; ezekhez szeretnénk a p polinomot megkonstruálni. Legyen $\delta$ >0 és n egy nagy pozitív egész; ezeket majd később definiáljuk.

Legyenek $-1=u_0<u_1<\ldots<u_k=1$ azok a pontok, ahol a T_k Csebisev-polinom értéke $\pm$ 1: ekkor T_k(u_i)=(-1)^k-i. (Könnyű ellenőrizni, hogy $u_i=\cos\frac{(k-i)\pi}{k}$ , de erre a képletre nem lesz szükség.) Minden $i=0,1,\ldots,k$ -ra legen d_i az (az egyik) nemnegatív egész szám, ami a legközelebb van $(n-1)\frac{1+u_i}2$ számhoz, azaz

$\left|d_i-(n-1)\frac{1+u_i}2\right|\le\frac12.$

$n>\max_{0\le i<k}\frac2{u_{i+1}-u_i}+1,$

(1)

akkor a d_i értékek különbözők: $0=d_0<d_1<\ldots<d_k=n-1$ . Ezen kívül legyen d_k+1=n. A p(x) polinomot a következő alakban keressük:

$p(x)=b_0x^{d_0}+b_1x^{d_1}+\ldots+b_{k+1}x^{d_{k+1}}$

avagy, a_{d_i}=b_i, és minden $i\not\in\{d_0,d_1,\ldots,d_{k+1}\}$ indexre a_i=0.

2. lemma. (a) A $b_0,b_1,\ldots,b_{k+1}$ valós számokat meg lehet választani úgy, hogy ne legyen mindegyikük nulla, és a p(x) polinom osztható legyen (x-1)^k+1-gyel.

(b) A $b_0,b_1,\ldots,b_{k+1}$ számok egyike sem lehet nulla, és a $(b_0,b_1,\ldots,b_{k+1})$ sorozat biztosan váltakozó előjelű.

Bizonyítás. (a) Legyen minden 0 $\le$ i $\le$ k+1-re az x^d_i polinom osztási maradéka r_i(x). Ez összesen k+2 polinom, mindegyikük foka legfeljebb k. Ezért a maradékok lineárisan összefüggnek: alkalmas $b_0,b_1,\ldots,b_{k+1}$ számokkal, amelyek nem miond nullák, $b_0r_0(x)+\ldots+b_{k+1}r_{k+1}(x)=0$ .

(b) Tegyük fel indirekte, hogy a $(b_0,b_1,\ldots,b_{k+1})$ sorozat nem váltakozó előjelű: valamelyik j indexre b_j és b_j+1 azonos előjelű, vagy egyikük 0. Lehetséges, hogy vannak szomszédos nulla értékek a sorozatban; olyan j-t válasszunk, amikor b_j és b_j+1 valamelyike nem nulla.

Legyen $h(x)=(x-d_0)\ldots(x-d_{j-1})\cdot(x-d_{j+2})\ldots(x-d_{k+1})$ . Ez egy k-adfokú polinom, amire alkalmazhatjuk az 1. lemmát:

$\sum\limits_{i=0}^{k+1} b_i\, h(d_i) = \sum\limits_{i=0}^n a_i\, h(i) = 0.$

A baloldalon kettő kivétellel minden tagban h(d_i)=0. A maradék két tagban h(d_j) és h(d_j+1) egyike sem nulla, és azonos előjelű. A b_j és b_j+1 együtthatók szintén azonos előjelűek, és nem mindettő nulla. Az összegben tehát egy vagy két, azonos előjelű nemnulla tag van, így az összeg nem lehet nulla, ellentmondás. Ezzel a lemmát igazoltuk. $\Box$

(Megjegyzés. Az is igaz, hogy a p(x) polinom konstans szorzótól eltekintve egyértelmű, de erre szintén nem lesz szükségünk.)

Most már van egy p(x) polinomunk, ami osztható a (x-1)^k+1 polinommal. A p(x) polinomot végigosztva b_k+1-gyel elérhetjük, hogy a_n=b_k+1=1 legyen. A váltakozó előjel miatt ekkor $b_k,b_{k-2},\ldots$ pozitív, $b_{k-1},b_{k-3},\ldots$ pedig negatív lesz.

Az A. 574. feladat hasonlóan legyen

$q(x) = T_k\left(\frac2{n-1}x-1\right).$

Az 1. lemma szerint

$\sum\limits_{i=0}^{k+1} b_i q(d_i) =\sum\limits_{i=0}^n a_i\, q(i) =0,$

avagy, átrendezve,

$\sum\limits_{i=0}^k (-b_i q(d_i)) = b_{k+1}q(d_{k+1}) = q(n).$

(*)

A d_i számokat azért választottuk így, hogy q(d_i) "közel" legyen (-1)^k-i-hez. Ezt most pontosabban megbecsüljük.

Az i=0 és i=k esetekben q(d₀)=q(0)=T_k(-1)=(-1)^k, illetve q(d_k)=q(n-1)=T_k(1)=1.

$n> \frac1{\min(\vartheta_1,\ldots,\vartheta_{k-1})}+1,$

(2)

akkor

$\left|\Big(\tfrac2{n-1}d_i-1\Big)-u_i\right| = \tfrac2{n-1} \left| d_i-(n-1)\tfrac{1+u_i}2 \right| \le \tfrac2{n-1} \cdot \tfrac12 = \tfrac1{n-1} < \vartheta_i,$

és

$\big|q(d_i)-(-1)^{k-i}\big| = \left| T_k\Big(\tfrac2{n-1}d_i-1\Big)-T_k(u_i)\right| \le \delta \left| \Big(\tfrac2{n-1}d_i-1\Big)-u_i \right| < \tfrac{\delta}{n-1}.$

n>1+ $\delta$ ,

(3)

akkor |q(d_i)-(-1)^k-i|<1 minden i-re, ezért $q(d_0),q(d_1),\ldots,q(d_k)$ sorozat váltakozó előjelű, és

$|q(d_i)| > 1-\tfrac{\delta}{n-1}.$

Még szükségünk lesz q(d_k+1)=q(n) felső becslésére is. Az A. 574. feladat megoldásából is tudjuk, hogy T_k(1)=1 és T_k'(1)=k². Ezért van olyan $\psi$ >0, hogy 1 $\le$ x $\le$ 1+ $\psi$ esetén T_k(x)<1+(1+ $\delta$ )k²(x-1). Ha

$n>1+\frac2\psi,$

(4)

akkor tehát

$q(n) = T_k\left(1+\frac2{n-1}\right) < 1 + (1+\delta)k^2\cdot\tfrac2{n-1}.$

Az (*) azonosság baloldalát alulról, a jobboldalt felülről becsüljük. A baloldalon minden tag pozitív, ezért

$\sum\limits_{i=0}^k (-b_i q(d_i)) = \sum\limits_{i=0}^k |b_i|\cdot |q(d_i)| \ge \Big(1-\tfrac{\delta}{n-1}\Big) \sum_{i=0}^k |b_i| = \Big(1-\tfrac{\delta}{n-1}\Big) \sum_{i=0}^{n-1} |a_i|,$

illetve

$q(n) < 1 + (1+\delta)k^2\cdot\tfrac2{n-1}.$

Tehát

$\sum_{i=0}^{n-1} |a_i| < \frac1{1-\tfrac{\delta}{n-1}} \sum\limits_{i=0}^k (-b_i q(d_i)) = \frac1{1-\tfrac{\delta}{n-1}} q(n) < \frac{1 + (1+\delta)k^2\cdot\tfrac2{n-1}}{1-\tfrac{\delta}{n-1}}.$

Már csak a feladatbeli alakra kell rendeznünk ezt a becslést.

$\frac{1 + (1+\delta)k^2\cdot\tfrac2{n-1}}{1-\tfrac{\delta}{n-1}} = \frac{(n-1) + 2(1+\delta)k^2}{n-1-\delta} = 1 + \frac{2(1+\delta)k^2+\delta}n \cdot\left(1+\frac{1+\delta}{n-1-\delta}\right)$

Válasszuk $\delta$ -t olyan kicsinek, hogy

$2(1+\delta)k^2+\delta \le (2+\tfrac\varepsilon2)k^2$

teljesüljön, például legyen

$d=\frac{k^2\varepsilon}{k^2+1}.$

Ezután válasszuk n-et olyan nagynak, hogy

$1+\frac{1+\delta}{n-1-\delta} < \frac{2+\varepsilon}{2+\tfrac\varepsilon2},$

is érvényes legyen. Ezt is elérhetjük, ha

$n > (1+\delta)\left(\frac4\varepsilon+2\right).$

(5)

Ekkor tehát

$\sum_{i=0}^{n-1} |a_i| < 1 + \frac{2(1+\delta)k^2+\delta}n \cdot\left(1+\frac{1+\delta}{n-1-\delta}\right) < 1 + \frac{(2+\tfrac\varepsilon2)k^2}{n} \cdot \frac{2+\varepsilon}{2+\tfrac\varepsilon2} = 1 + \frac{(2+\varepsilon)k^2}{n}.$

A becsléseink akkor érvényesek, ha (1)-(5) mindegyike teljesül. Ez csak véges sok, csak a k-tól függő alsó korlát az n-re.

Statistics:

0 student sent a solution.

Problems in Mathematics of KöMaL, January 2013

Already signed up?
New to KöMaL?