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\le 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:

$\mathrm{lim\; inf}\frac{A(x)\sqrt{\log x}}{\sqrt{x}}\le 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.

Jegyzetek

• 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.)