Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

9.6. Sidon-sorozatok

9.6. Sidon-sorozatok

Sidon-sorozatoknak a természetes számok olyan a1<a2<… véges vagy végtelen részsorozatait nevezzük, amelyeknél az ai+aj összegek (vagy ami ugyanaz: az aiaj, ij különbségek) mind különbözők. Az alábbiakban csak véges Sidon-sorozatokkal foglalkozunk.

Maximálisan hány eleme lehet egy Sidon-sorozatnak az [1,n] intervallumban? Bebizonyítjuk, hogy ez a maximum „körülbelül” n  Ez két állítást jelent: egyrészt azt, hogy 1 és n között valóban előfordul körülbelül n elemszámú Sidon-sorozat (alsó becslés a maximális elemszámra), másrészt azt, hogy az adott határok között ennél lényegesen hosszabb Sidon-sorozat már nem létezik (felső becslés a maximális elemszámra).

A kérdéskör vizsgálatában kiemelkedő érdemei vannak az 1996 szeptemberében elhunyt zseniális magyar matematikusnak, Erdős Pálnak. Turán Pállal közösen 1941-ben megmutatták, hogy a keresett maximum legfeljebb n1/2+2n1/4. Ezt később B. Lindström más módszerrel n1/2+n1/4+1-re javította, de ugyanez az eredmény az Erdős-Turán-bizonyítás pontosabb végigszámolásával is kiadódik (9.6.4 Tétel). J. Singer egy eredményének felhasználásával Erdős és tőle függetlenül S. Chowla 1944-ben azt is igazolták, hogy elég nagy n-re n1/2n5/16 elemszámú Sidon-sorozat valóban meg is adható n-ig (9.6.3 Tétel). Ez a két eredmény együtt azt jelenti, hogy az [1,n] intervallumban a Sidon-sorozatok maximális elemszáma nagyon pontos aszimptotikával n  Máig is megoldatlan azonban a még jobb hibatagok kérdése. Az sejthető, hogy a maximális elemszámnak n-től való eltérése egy n-től független korlát alatt marad. Ennek igazolásáért vagy cáfolásáért korábban Erdős Pál összesen 1000 dollárt ajánlott fel.

Jelöljük s=s(n)-nel az n-ig megadható leghosszabb Sidon-sorozat elemszámát. Próbáljunk először egyszerű felső becslést keresni s-re. Mivel egy 1 és n közötti Sidon-sorozatban az ai+aj összegek mind különbözők, 2 és 2n közé esnek és számuk s+12 így s+12<2n azaz s<2n  Rögtön jobb becslést kapunk, ha az aiaj>0 különbségeket vizsgáljuk; ezek is mind különbözők, n-nél kisebbek, és számuk s2  így s2<n azaz s<2n+1 A felső becslésnél tehát azonnal adódott a n-es nagyságrend, „csak” a n együtthatóját kell 1-re leszorítani.

„Alulról nézve” sokkal kevésbé világos, hogyan érhető el a n-es nagyságrend. A kettőhatványok példája csak log2n-et ad, és a mohó algoritmussal is csak n3 biztosítható (lásd a 9.6.1 feladatot). Egy szintén Erdőstől származó nagyon szép elemi konstrukcióval már n/2 hosszú Sidon-sorozatot kapunk (lásd a 9.6.2 feladatot), és mint említettük, a n együtthatója „feltornázható” 1-re.

Lássunk akkor hozzá nagy elemszámú Sidon-sorozatok konstrukciójához. Ezt először bizonyos típusú n-ekre végezzük el, és ezek segítségével térünk majd át tetszőleges n-re.

9.6.1 Tétel

Legyen p tetszőleges prímszám. Ekkor n=p2+p+1-re létezik olyan Sidon-sorozat az [1,n] intervallumban, amelynek n =p+1 eleme van.❶

A 9.6.1 Tétel helyett egy jóval élesebb és önmagában is nagyon érdekes és meglepő állítást igazolunk.

9.6.2 Tétel

Legyen p tetszőleges prímszám. Ekkor létezik p+1 darab olyan ai, amelyekre az aiaj, ij különbségek (nemcsak hogy különbözők, hanem ráadásul) páronként inkongruensek modulo p2+p+1.❶

Megjegyzés: A 9.6.2 Tételben szereplő különbségek száma p2+p, és modulo p2+p+1 éppen ennyi nemnulla maradék van. Vagyis az aiaj különbségek minden maradékot előállítanak, éspedig mindegyiket pontosan egyszer.

Nyilvánvaló, hogy a 9.6.2 Tételben az ai-k maguk is páronként inkongruensek kell hogy legyenek, tehát választhatók 1 és n=p2+p+1 közöttieknek, és így valóban azonnal adódik a 9.6.1 Tétel.

A 9.6.2 Tétel bizonyítása: A bizonyítás a véges testek segítségével történik, az ezek szerkezetére vonatkozó alapvető tételek (lásd az A.8 pontot) és egy kevés lineáris algebra felhasználásával.

Tekintsük a p3 elemű T3 véges testet, és ebben a p elemű T1 résztestet. Legyen Δ a T3 test multiplikatív csoportjának generáló eleme, azaz

(1)

A T1-beli nemnulla elemek T3 multiplikatív csoportjának részcsoportját alkotják, amelynek generátoreleme nyilván Δn, ahol n=(p3–1)/(p–1)=p2+p+1. Vagyis

Tekintsük most T3-at mint T1 feletti vektorteret. Az előzőek alapján kapjuk, hogy T3 két eleme, Δi és Δj pontosan akkor lineárisan összefüggő T1 felett, ha

(2)

A keresett ai egészeket ezután a következőképpen adjuk meg. Vegyünk egy tetszőleges θT3\T1 elemet és legyenek T1 elemei γ1,…, γp. Írjuk fel a Θ+γi elemeket

(3)

alakban. Az (1) alapján ez megtehető, és így kijelöltünk p darab ai egész számot, a p+1-ik pedig legyen ap+1=0.

Megmutatjuk, hogy ezek eleget tesznek a feltételnek, azaz az aiaj különbségek, vagy ami ugyanaz, az ai+aj összegek páronként különböző maradékot adnak modulo p2+p+1.

Tegyük fel, hogy ai+ajak+al (mod p2+p+1). Ekkor (2) és (3) alapján

adódik valamely γT1 elemmel. Mivel Θ harmadfokú a T1 test felett, ezért nem lehet gyöke egy legfeljebb másodfokú polinomnak. Vagyis csak γ=1 és {γi, γj}={γk, γl} lehetséges, így a megfelelő ai-k is egyenlők, ami éppen a bizonyítandó állítás volt.

A bizonyítás ugyanígy megy akkor is, ha ap+1=0 is szerepel a szóban forgó ai-k között.❷

Megjegyzés: A 9.6.2 Tétel és a bizonyítás ugyanúgy érvényes akkor is, ha p egy prímszám hatványa. Mindez szoros kapcsolatban van a véges projektív síkokkal (lásd az A.8.13 feladatot).

9.6.3 Tétel

Minden elég nagy n-re megadható olyan Sidon-sorozat az [1,n] intervallumban, amelynek legalább n1/2n5/16 eleme van.❷

Bizonyítás: Vegyük azt a legnagyobb p prímszámot, amelyre p2+p+1≤n, és p2+p+1-re készítsük el az előző (p+1 elemű) konstrukciót. Mivel n1/2n5/16 és n1/2 között elég nagy n-re mindig van prímszám, ezért p>n1/2n5/16, amivel a tételt tetszőleges n-re igazoltuk.❷

Megjegyzés: A tetszőleges n-re történő áttérésnél azt használtuk fel, hogy a prímek elég „sűrűn” helyezkednek el. Ha tudjuk, hogy m és m+mc között elég nagy m-re mindig van prímszám, akkor a tételünkben a hibatag nc/2 nagyságrendűnek vehető. A jelenleg bizonyított legjobb érték c≈0,54, ennek alapján tehát a hibatag kitevője 0,27-nek is vehető. (A tételben csak c=5/8-dal dolgoztunk.) Ezek igen mély prímszámelméleti eredmények. Ha „csak” a prímszámtételre támaszkodnánk, akkor a 9.6.3 Tétel helyett csak annak ~ n aszimptotikus változatát kaptuk volna hibatag nélkül, ugyanis c értékét „pusztán” a prímszámtétel segítségével nem tudnánk 1 alá szorítani. A c≈0,54 „világrekord” tehát nem kis teljesítmény. Ugyanakkor jól tükrözi tudásunk korlátait is, ugyanis elérhetetlen messzeségben van tőle még az alábbi ártalmatlannak látszó és minden bizonnyal igaz állítás is: bármely két szomszédos négyzetszám közé esik prímszám. Ez lényegében a c=1/2 esetnek felel meg, és még az ún. Riemann-sejtésből sem következik. Ráadásul a c=1/2 sem határ, hanem minden valószínűség szerint c értéke akármilyen kicsinek választható, hogy az [m,m+mc] intervallum elég nagy m-re még mindig tartalmazzon prímszámot. Ez a sejtés azonban már végképp abba a kategóriába tartozik, amelyre Erdős azt szokta mondani, hogy biztosan igaz, de sohasem fogják tudni bebizonyítani. A 9.6.3 Tétel más bizonyításaira nézve lásd a 9.6.3 és 9.6.4 feladatot.

Most rátérünk a Sidon-sorozatok elemszámának a(z éles) felső becslésére.

9.6.4 Tétel

Az [1,n] intervallumba eső bármely Sidon-sorozatnak legfeljebb n1/2+n1/4+1 eleme van.❶

Első bizonyítás: Legyen t később alkalmasan megválasztandó egész szám, és toljunk végig egy t–1 hosszúságú szakaszt a [0,n] intervallumon, azaz tekintsük a [–t+1,0], [–t+2,1],…,[n,n+t–1] intervallumokat. Tegyük fel, hogy az s elemű Sidon-sorozat elemszáma az egyes intervallumokban A1, A2,…, An+t. Ekkor nyilván

(4)

Számoljuk össze multiplicitással azokat az {ai, aj}, i>j elempárokat, amelyek egy-egy ilyen intervallumba esnek, azaz mindegyik elempárt annyiszor vegyük, ahány intervallum azt tartalmazza. Legyen D ezek együttes száma. Ekkor nyilván

(5)

Másrészt, ha egy ilyen elempárban az aiaj különbség d, akkor ez az elempár pontosan td intervallumba esik bele. A Sidon-tulajdonság miatt minden d legfeljebb egyszer fordulhat elő, így

(6)

Az (5) és (6) alapján

(7)

adódik. A számtani és négyzetes közép közötti egyenlőtlenség valamint (4) felhasználásával (7) bal oldalát a következőképpen becsülhetjük alulról:

(8)

Így (7) és (8) összekapcsolásával azt nyerjük, hogy

Ezt a másodfokú egyenlőtlenséget megoldva

adódik. Ha most t-nek a t=n3/4+1 értéket választjuk, akkor a tétel állítását kapjuk.❷

Második bizonyítás: Most bizonyos aiaj különbségek összegét fogjuk két oldalról megbecsülni. Legyen

(9)

ahol r-et később alkalmasan megválasztjuk. A Sidon-tulajdonság miatt a (9)-beli összeg tagjai között nincs két azonos különbség, számuk

ahol

(10)

így K legalább akkora, mint az első rw darab pozitív egész összege, azaz

(11)

Másrészt a (9)-beli összegnek része pl.

és számos más teleszkopikus összeg, amelyek hasonlóképpen becsülhetők felülről. Ezek általános alakja

Sőt az egész K ilyen teleszkopikus részösszegekre bontható, amelyeket úgy kapunk, hogy az indexek befutják az összes olyan 1 és s közötti (tovább már nem bővíthető) számtani sorozatot, amelynek differenciája legfeljebb r. Mivel μ differenciájú számtani sorozat éppen μ darab van, így a teleszkopikus részösszegek száma 1+2+…+r=r(r+1)/2, és mindegyik részösszeg értéke legfeljebb n, tehát

(12)

Egybevetve (11)-et és (12)-t, 2/r2-tel történő szorzás után a w2<n+n/r egyenlőtlenséget nyerjük. Innen gyökvonással és (10) felhasználásával kapjuk, hogy

Ha most r-nek az r=n1/4+1 értéket választjuk, akkor a tétel állítását kapjuk.❷

Feladatok

9.6.1 Mutassuk meg, hogy a mohó algoritmussal 1 és n között egy legalább n3 elemű Sidon-sorozatot kapunk.

Megjegyzés: A mohó algoritmussal ily módon egy olyan végtelen hosszú Sidon-sorozatot is nyerhetünk, amelynek minden n-re n-ig legalább n3 eleme van. Meglepő, hogy ezt a nagyságrendet sokáig egyáltalán nem sikerült megjavítani. Csak 1981-ben igazolták Ajtai Miklós, Komlós János és Szemerédi Endre, hogy létezik olyan végtelen Sidon-sorozat, amelynek minden (elég nagy) n-re n-ig legalább cnlogn 3 eleme van, ahol c alkalmas pozitív konstans. 1997-ben Ruzsa Imre ezt cn2-1-ε-ra javította, azonban még ez az eredmény is igen messze van az Erdős által sejtett n1/2–ε-os nagyságrendtől.

9.6.2 Legyen p prímszám és ai=1+2ip+i2mod p   i=0, 1,, p-1  ahol i2mod p az i2 legkisebb nemnegatív maradékát jelöli modulo p. Lássuk be, hogy így n=2p2-re egy n/2 elemszámú Sidon-sorozatot kapunk az [1,n] intervallumban.

M*9.6.3 Legyen p tetszőleges prímszám. Ekkor létezik p darab olyan ai, amelyekre az ai+aj összegek (nemcsak hogy különbözők, hanem ráadásul) páronként inkongruensek modulo p2–1.

Megjegyzés: Az előzővel nyilván ekvivalens, hogy ij-re az aiaj különbségek (nemcsak hogy különbözők, hanem ráadásul) páronként inkongruensek modulo p2–1. A szereplő különbségek száma p2p, és modulo p2–1 összesen csak p2–2 darab nemnulla maradék van. Vagyis az aiaj különbségek majdnem minden maradékot előállítanak. A bizonyításból leolvasható, hogy éppen a p+1-gyel osztható maradékok maradnak ki. — A feladatból a 9.4.3 Tétel hasonló módon vezethető le, mint ahogyan a 9.4.2 Tételből következett (ugyanez érvényes a következő feladatra is).

M*9.6.4 Legyen p tetszőleges prímszám. Ekkor létezik p–1 darab olyan ai, amelyekre az aiaj, ij különbségek (nemcsak hogy különbözők, hanem ráadásul) páronként inkongruensek modulo p2p.

9.6.5 Végtelen Sidon-sorozat. Mutassuk meg, hogy bármely ε>0-hoz található olyan végtelen Sidon-sorozat, amelynél végtelen sok n-re igaz, hogy n-ig legalább 1/2-εn eleme van (vö. a 9.6.1 feladat utáni megjegyzéssel).

Megjegyzés: Megoldatlan, hogy ugyanez 1/2 helyett 1-gyel is igaz-e.

9.6.6 Többtagú összegek. Legyen h≥2 rögzített természetes szám, és az [1,n] intervallumban tekintsünk most olyan sorozatokat, ahol az elemekből képezett h-tagú összegek mind különbözők. (A h=2 eset éppen a Sidon-sorozatokat jelenti.)

*a) Mutassuk meg, hogy van olyan sorozat, amelynek „körülbelül” n1/h eleme van.

b) Lássuk be, hogy van olyan csak a h-tól függő c=c(h) konstans, hogy minden ilyen sorozatnak legfeljebb c(h)n1/h eleme van.

Megjegyzés: Megoldatlan probléma, hogy c(h) vajon 1+ε-ra csökkenthető-e, azaz bármely h-ra igaz-e, hogy a h=2 esethez hasonlóan a maximális elemszám aszimptotikusan n1/h. A 9.6.4 Tétel bizonyítása azért nem vihető át, mert h≠2-re a feltételt nem lehet összegekről különbségekre átjátszani.

9.6.7 Minden összeg különböző. Legyen 1≤a1<…<asn, és tegyük fel, hogy a különböző ai-kból képezett akárhány tagú összegek mind különbözők.

a) Adjunk meg olyan sorozatot, amelynek elemszáma s=1+log2n

b) Lássuk be, hogy bármely sorozat elemszámára

M**c) A b)-beli felső becslést javítsuk s≤log2n+(log2log2n)/2+2-re.

Megjegyzés: Meglepő módon az alsó becslés is javítható; az 1 helyett (elég nagy n-re) 2 írható. Erdős korábban 500 dollárt ajánlott fel annak eldöntésére, vajon a max s–log2n eltérés n növekedésével korlátos marad-e. Megjegyezzük, hogy maxslog2n+c bizonyításához (ahol c konstans) elég csak egyetlen n=2ν-re ilyen elemszámú megfelelő sorozatot találni, ugyanis ezt 2μ-vel megszorozva és a 2ν-ig terjedő kettőhatványokkal kiegészítve egy kívánt elemszámú sorozatot kapunk n=2ν+μ-ig. Könnyen lehet azonban, hogy az említett alsó becslés már éles, vagyis c értéke már 2-ről 3-ra sem javítható.

**9.6.8 Szorzatok. Az [1,n] intervallumban tekintsünk most olyan sorozatokat, ahol az elemekből képezett akárhány tényezős szorzatok mind különbözők. A prímek nyilván megfelelnek, tehát az elemszám lehet π(n), az n-ig terjedő prímek száma. Mutassuk meg, hogy bármely ilyen sorozat elemszáma legfeljebb π(n)+2n2/3.

Megjegyzés: Belátható, hogy a maximális elemszámnak a π(n)-től való eltérése n/logn nagyságrendű.

M**9.6.9 Számtani sorozatok. Mutassuk meg, hogy minden elég nagy n-re megadható 1 és n között n/eclogn olyan egész szám (ahol c>0 alkalmas konstans), amelyek között nem fordul elő háromtagú számtani sorozat.

M*9.6.10 Egyszínű számtani sorozatok. Mutassuk meg, hogy az 1,2,…,2000 számok kiszínezhetők pirossal és kékkel úgy, hogy ne forduljon elő egyszínű 18-tagú számtani sorozat.