Sidon-sorozatnak vagy Sidon-halmaznak nevezzük természetes számoknak egy véges vagy végtelen sorozatát, ha az elemeiből képzett valamennyi kéttagú ö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 számok, és egy még be nem bizonyított sejtés szerint a természetes számok ötödik hatványainak 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 , így , 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.. Addendum , 19 (1944), 208. 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 , és J. Singer konstrukciójával alsó korlátot adtak a maximális Sidon-sorozat hosszára: .

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:

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 minden x-re. Ajtai Miklós, Komlós János és Szemerédi Endre megjavította ezt az eredményt,. ahol

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

Erdős Pál és Rényi Alfréd bebizonyította,. hogy van olyan végtelen a0,a1,... sorozat, amiben minden n természetes számra legfeljebb c megoldása van az ai+aj=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)=x5+[cx4] függvény értékkészlete Sidon-sorozat, ahol [.] az egészrészt jelöli.

Jegyzetek

Kategória:Kombinatorika Kategória:Additív számelmélet