Sidon-sorozat

Sidon-sorozatnak vagy Sidon-halmaznak nevezzük természetes számoknak egy $A=\{a_{0},a_{1},a_{2},\dots \}$ véges vagy végtelen sorozatát, ha az $A$ elemeiből képzett valamennyi kéttagú $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 $\{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 $\{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 $a_{i}-a_{j}=a_{k}-a_{l}$, így $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. Bár sokan foglalkoztak vele, a kérdés még ma is nyitott.

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

$\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 $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, ahol

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

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

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

Erdős Pál és Rényi Alfréd bebizonyította, 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.)