Problem A. 532. (March 2011)

A. 532. Prove that there exist a real number c>0 such that whenever each of the numbers $a_0,a_1,\ldots,a_n$ are 1 or -1 and the polynomial (x-1)^k divides the polynomial $a_0+a_1x+\ldots+a_nx^n$ then k<c^.ln²(n+1).

(5 pont)

Deadline expired on April 11, 2011.

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

Megoldásvázlat. Legyen $f(x)=a_0+a_1x+\ldots+a_nx^n=(x-1)^kg(x)$ , ahol g egy egész együtthatós polinom. Feltételezzük, hogy k $\ge$ 1.

1. lemma. Ha p olyan prímszám, amire $\frac{p-1}{\ln p}<\frac{k}{\ln(n+1)}$ , akkor f(x) osztható az 1+x+x²+...+x^p-1 polinommal.

Bizonyítás. A Schönemann-Eisenstein kritérium jól ismert következménye, hogy az 1+x+x²+...+x^p-1 polinom irreducibilis. Ezért elég annyit igazolni, hogy a két polinomnak van közös gyöke.

Az 1+x+x²+...+x^p-1 polinom gyökei az 1-től különböző komplex p-edik egységgyökök. Legyen $\varepsilon=e^{2\pi i/p}$ ; ekkor

$1+x+x^2+\dots+x^{p-1} = \prod_{j=1}^{p-1} (x-\varepsilon^j),$

és elég azt igazolni, hogy $\prod_{j=1}^{p-1} g(\varepsilon^j)=0$ . Tegyük fel indirekten, hogy $\prod_{j=1}^{p-1} g(\varepsilon^j)\ne0$ . A $\prod_{j=1}^{p-1} g(\varepsilon^j)$ szorzat egy valós egész szám, mert ha a szorzatot kibontjuk, az $\varepsilon$ , $\varepsilon$ ²,..., $\varepsilon$ ^p-1 számok ugyanannyiszor szerepelnek. Ezért $\left|\prod_{j=1}^{p-1} g(\varepsilon^j)\right|\ge1$ , és

$(n+1)^{p-1} \ge \prod_{j=1}^{p-1} \big|f(\varepsilon^j)\big| = \prod_{j=1}^{p-1} \big|(\varepsilon^j-1)^k g(\varepsilon^j)\big| = \left|\prod_{j=1}^{p-1} (\varepsilon^j-1)\right|^k \cdot \left|\prod_{j=1}^{p-1} g(\varepsilon^j)\right| \ge p^k \cdot 1.$

Ez viszont ellentmond a feltételnek. Ezzel a lemmát igazoltuk.

2. lemma. Ha p olyan prímszám, amire $\frac{p-1}{\ln p}<\frac{k}{\ln(n+1)}$ , akkor n+1 osztható p-vel.

Bizonyítás. Az 1. lemma egyszerű következnénye, hogy f(x) osztható (x^p-1)-gyel. Ebből pedig következik, hogy minden 0 $\le$ r<p-re az

f_r(x)=a_rx^r+a_r+px^r+p+a_r+2px^r+2p+...

polinom is osztható (x^p-1)-gyel, és így f_r(1)=0. Mivel az a_r,a_r+p,a_r+2px^r+2p együtthatók mind páratlanok, ez csak úgy lehetséges, ha az r,r+p,r+2p,... indexek közül páros sok esik az [0,n] intervallumba, tehát $\left[\frac{n+p-r}{p}\right]$ minden r-re páros.

Legyen r₀ az n+1 szám maradéka p-vel osztva. Mivel $\left[\frac{n+p-(r_0-1)}{p}\right]=\frac{n+1-r_0}{p}+1$ és $\left[\frac{n+p-r_0}{p}\right]=\frac{n+1-r_0}{p}$ , az $\left[\frac{n+p-r_0}{p}\right]$ és az $\left[\frac{n+p-(r_0-1)}{p}\right]$ szám nem lehet egyszerre páros. Ebből r₀ $\ge$ 1 esetén ellentmondásra jutnánk. Tehát r₀=0, és p|n+1.

Végül felhasználjuk azt a szintén ismert tényt, hogy tetszőleges x>2 valós számra az x-nél kisebb prímszámok szorzata nagyobb, mint e^c₀x, ahol c₀ pozitív szám.

Ha $p<\ln2\cdot\frac{k}{\ln(n+1)}$ , akkor teljesül a két lemma feltétele, és p|n+1. Tehát n+1 osztható az összes $\ln2\cdot\frac{k}{\ln(n+1)}$ -nél kisebb prímmel és ezen prímek szorzatával. Ezért, ha $\ln2\cdot\frac{k}{\ln(n+1)}>2$ , akkor

$e^{c_0\cdot\ln2\cdot\frac{k}{\ln(n+1)}} < \prod_{p<\ln2\cdot\frac{k}{\ln(n+1)}}p \le n+1$

$c_0\cdot\ln2\cdot\frac{k}{\ln(n+1)} < \ln(n+1)$

$k < \frac1{c_0\cdot\ln2} \ln^2(n+1).$

Ha $\ln2\cdot\frac{k}{\ln(n+1)}\le2$ , akkor a fenti becslés nem alkalmazható. De ilyenkor $k\le\frac{2}{\ln 2}\ln(n+1)$ , és ez a feltétel erősebb, mint az állítás.

Megjegyzések. 1. Pontosabb számolással a becslés $k<c\frac{\ln^2 n}{\ln\ln n}$ -re javítható.

2. Az $f(x)=\prod_{j=0}^{k-1}(1-x^{2^j})$ példában n=2^k-1, ez alapján azt is várhatnánk, hogy k $\le$ log₂(n+1). Ez azonban k $\ge$ 6 esetén már nem igaz. Azt sem tudjuk, hogy igaz-e a k $\le$ c^.ln (n+1) becslés valamilyen pozitív c konstanssal.

Bővebben itt: D. W. Boyd: On a problem of Byrnes concerning polynomials with restricted coefficients, Math. Comp. 66 (1997) 1697–1703

Statistics:

2 students sent a solution.

5 points: Backhausz Tibor, Nagy 235 János.

Problems in Mathematics of KöMaL, March 2011

2 students sent a solution.
5 points:	Backhausz Tibor, Nagy 235 János.

Already signed up?
New to KöMaL?