Sidon-sorozat

Sidon-sorozatnak vagy Sidon-halmaznak nevezzük természetes számoknak egy ${\displaystyle A=\{a_{0},a_{1},a_{2},\dots \}}$ véges vagy végtelen sorozatát, ha az ${\displaystyle A}$ elemeiből képzett valamennyi kéttagú ${\displaystyle a_{i}+a_{j}(i\leq j)}$ összeg különböző. A sorozatok névadója Szidon Simon magyar matematikus, aki a Fourier-sorok tanulmányozása közben vezette be a fogalmat.

Példák

Sidon-sorozatot alkotnak a ${\displaystyle \{1,2,5,7\}}$ számok, és egy még be nem bizonyított sejtés szerint a természetes számok ötödik hatványainak ${\displaystyle \{0,1,32,243,\dots \}}$ halmaza is.

Kapcsolat a Golomb-vonalzóval

A Golomb-vonalzó egész számok egy sorozata, ahol az egyes pozíciók közötti összes távolság különböző.

Minden véges Golomb-vonalzó véges Sidon-sorozat, és fordítva, minden véges Sidon-sorozat Golomb-vonalzó. Ez belátható indirekt úton:

Tegyük fel indirekt, hogy S véges Sidon-sorozat, de nem Golomb-vonalzó. Ezért van négy eleme, amire ${\displaystyle a_{i}-a_{j}=a_{k}-a_{l}}$, így ${\displaystyle a_{i}+a_{l}=a_{k}+a_{j}}$, ami ellentmond annak, hogy S Sidon-sorozat. Ezért minden véges Sidon-sorozat Golomb-vonalzó.

Hasonlóan érvelve bizonyítható, hogy a véges Golomb-vonalzók Sidon-sorozatok.

A véges Sidon-sorozatok hossza

Erdős Pál és Turán Pál felvetette azt a kérdést, hogy hány eleme lehet egy Sidon-sorozatnak, ha az összes tagja nem nagyobb egy adott x-nél.^[1] Bár sokan foglalkoztak vele, a kérdés még ma is nyitott.^[2]

Erdős és Turán belátta, hogy ha A egy x-ig terjedő Sidon-sorozat elemeinek száma legfeljebb ${\displaystyle {\sqrt {x}}+O({\sqrt[{4}]{x}})}$, és J. Singer konstrukciójával alsó korlátot adtak a maximális Sidon-sorozat hosszára: ${\displaystyle {\sqrt {x}}(1-o(1))}$.

Végtelen Sidon-sorozatok

Ellenben, ha A egy végtelen Sidon-sorozat, és A(x) jelöli az x-ig terjedő szelet hosszát, akkor Erdős Pál eredményei szerint:

${\displaystyle \liminf {\frac {A(x){\sqrt {\log x}}}{\sqrt {x}}}\leq 1}$

f azaz a végtelen sorozatok ritkábbak a végesekre kapott felső korlátnál.

A másik irányban, S. Chowla és Mian megfigyelte, hogy mohó algoritmussal készíthető végtelen Sidon-sorozat, amire ${\displaystyle A(x)>c{\sqrt[{3}]{x}}}$ minden x-re. Ajtai Miklós, Komlós János és Szemerédi Endre megjavította ezt az eredményt,^[3] ahol

${\displaystyle A(x)>{\sqrt[{3}]{x\log x}}.}$

A legjobb alsó becslést Ruzsa Imre adta,^[4] aki kimutatta, hogy van Sidon-sorozat, amire

${\displaystyle A(x)>x^{{\sqrt {2}}-1-o(1)}}$

Erdős Pál és Rényi Alfréd bebizonyította,^[5] hogy van olyan végtelen a₀,a₁,... sorozat, amiben minden n természetes számra legfeljebb c megoldása van az a_i+a_j=n egyenletnek.

Erdős egy sejtése szerint van nem konstans egész együtthatós polinom, ami Sidon-sorozatot ad a természetes számokon. Speciálisan, azt is felvetette, hogy vajon az ötödik hatványok halmaza Sidon-sorozat-e? Ruzsa közel jutott ehhez, amikor megmutatta, hogy van egy 0<c<1 irracionális szám, hogy az f(x)=x⁵+[cx⁴] függvény értékkészlete Sidon-sorozat, ahol [.] az egészrészt jelöli.

Források

• Kevin O’Bryant: A Complete Annotated Bibliography of Work Related to Sidon Sequences (PostScript). The Electronic Journal of Combinatorics, 2004. július 26. [2011. május 13-i dátummal az eredetiből archiválva]. (Hozzáférés: 2010. január 29.)