KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

ELTE

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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.ln2(n+1).

(5 points)

Deadline expired on 11 April 2011.


Google Translation (Sorry, the solution is published in Hungarian only.)

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\ge1.

 

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+x2+...+xp-1 polinommal.

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

Az 1+x+x2+...+xp-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,\varepsilon2,...,\varepsilonp-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ó (xp-1)-gyel. Ebből pedig következik, hogy minden 0\ler<p-re az

fr(x)=arxr+ar+pxr+p+ar+2pxr+2p+...

polinom is osztható (xp-1)-gyel, és így fr(1)=0. Mivel az ar,ar+p,ar+2pxr+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 r0 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 r0\ge1 esetén ellentmondásra jutnánk. Tehát r0=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 ec0x, ahol c0 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=2k-1, ez alapján azt is várhatnánk, hogy k\lelog2(n+1). Ez azonban k\ge6 esetén már nem igaz. Azt sem tudjuk, hogy igaz-e a k\lec.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 on problem A. 532.
2 students sent a solution.
5 points:Backhausz Tibor, Nagy 235 János.


  • Problems in Mathematics of KöMaL, March 2011

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley