Legyen p tetszőleges prímszám. Ekkor n=p²+p+1-re létezik olyan Sidon-sorozat az [1,n] intervallumban, amelynek $\sqrt{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.

Legyen p tetszőleges prímszám. Ekkor létezik p+1 darab olyan a_i, amelyekre az a_i–a_j, i≠j különbségek (nemcsak hogy különbözők, hanem ráadásul) páronként inkongruensek modulo p²+p+1.❶

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

Nyilvánvaló, hogy a 9.6.2 Tételben az a_i-k maguk is páronként inkongruensek kell hogy legyenek, tehát választhatók 1 és n=p²+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 p³ elemű T₃ véges testet, és ebben a p elemű T₁ résztestet. Legyen Δ a T₃ test multiplikatív csoportjának generáló eleme, azaz

(1)

A T₁-beli nemnulla elemek T₃ multiplikatív csoportjának részcsoportját alkotják, amelynek generátoreleme nyilván Δⁿ, ahol n=(p³–1)/(p–1)=p²+p+1. Vagyis

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

(2)

A keresett a_i egészeket ezután a következőképpen adjuk meg. Vegyünk egy tetszőleges $\theta T_3\backslash T_1$ elemet és legyenek T₁ elemei γ₁,…, γ_p. Írjuk fel a Θ+γ_i elemeket

(3)

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

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

Tegyük fel, hogy a_i+a_j≡a_k+a_l (mod p²+p+1). Ekkor (2) és (3) alapján

adódik valamely $\gamma T_1$ elemmel. Mivel Θ harmadfokú a T₁ 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ő a_i-k is egyenlők, ami éppen a bizonyítandó állítás volt.

A bizonyítás ugyanígy megy akkor is, ha a_p+1=0 is szerepel a szóban forgó a_i-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).

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

Bizonyítás: Vegyük azt a legnagyobb p prímszámot, amelyre p²+p+1≤n, és p²+p+1-re készítsük el az előző (p+1 elemű) konstrukciót. Mivel n^1/2–n^5/16 és n^1/2 között elég nagy n-re mindig van prímszám, ezért p>n^1/2–n^5/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+m^c között elég nagy m-re mindig van prímszám, akkor a tételünkben a hibatag n^c/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 $~ \sqrt{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+m^c] 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.

Az [1,n] intervallumba eső bármely Sidon-sorozatnak legfeljebb n^1/2+n^1/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 A₁, A₂,…, A_n+t. Ekkor nyilván

(4)

Számoljuk össze multiplicitással azokat az {a_i, a_j}, 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 a_i–a_j különbség d, akkor ez az elempár pontosan t–d 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=⌊n^{3/4}⌋+1$ értéket választjuk, akkor a tétel állítását kapjuk.❷

Második bizonyítás: Most bizonyos a_i–a_j 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/r²-tel történő szorzás után a w²<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=⌊n^{1/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 $\sqrt[3]{n}$ 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 $\sqrt[3]{n}$ 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 $c\sqrt[ 3]{n\log n}$ eleme van, ahol c alkalmas pozitív konstans. 1997-ben Ruzsa Imre ezt $c{n}^{\sqrt{2}-1-\epsilon }$-ra javította, azonban még ez az eredmény is igen messze van az Erdős által sejtett n^1/2–ε-os nagyságrendtől.

9.6.2 Legyen p prímszám és $a_i=1+2ip+〈i^2\mathrm{m}\mathrm{o}\mathrm{d} p〉 i=0, 1,\dots , p-1$ ahol $〈i^2\mathrm{m}\mathrm{o}\mathrm{d} p〉$ az i² legkisebb nemnegatív maradékát jelöli modulo p. Lássuk be, hogy így n=2p²-re egy $\sqrt{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 a_i, amelyekre az a_i+a_j összegek (nemcsak hogy különbözők, hanem ráadásul) páronként inkongruensek modulo p²–1.

Megjegyzés: Az előzővel nyilván ekvivalens, hogy i≠j-re az a_i–a_j különbségek (nemcsak hogy különbözők, hanem ráadásul) páronként inkongruensek modulo p²–1. A szereplő különbségek száma p²–p, és modulo p²–1 összesen csak p²–2 darab nemnulla maradék van. Vagyis az a_i–a_j 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 a_i, amelyekre az a_i–a_j, i≠j különbségek (nemcsak hogy különbözők, hanem ráadásul) páronként inkongruensek modulo p²–p.

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 $\left(1/\sqrt{2}-\epsilon \right)\sqrt{n}$ eleme van (vö. a 9.6.1 feladat utáni megjegyzéssel).

Megjegyzés: Megoldatlan, hogy ugyanez $1/\sqrt{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” n^1/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)n^1/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 n^1/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≤a₁<…<a_s≤n, és tegyük fel, hogy a különböző a_i-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+⌊{log}_{2}n⌋$

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

M**c) A b)-beli felső becslést javítsuk s≤log₂n+(log₂log₂n)/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–log₂n eltérés n növekedésével korlátos marad-e. Megjegyezzük, hogy $\max s\ge ⌊{\log }_{2}n⌋+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)+2n^2/3.

Megjegyzés: Belátható, hogy a maximális elemszámnak a π(n)-től való eltérése $\sqrt{n}/\log n$ 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/e^{c\sqrt{\log n}}$ 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.