Sidon-sorozat

A Wikipédiából, a szabad enciklopédiából

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 Sidon Simon magyar matematikus, aki a Fourier-sorok tanulmányozása közben vezette be a fogalmat.

Példák[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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 , és J. Singer konstrukciójával alsó korlátot adtak a maximális Sidon-sorozat hosszára: .

Végtelen Sidon-sorozatok[szerkesztés]

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,[3] ahol

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

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

Források[szerkesztés]

  1. Erdős, P. & Turán, P. (1941), "On a problem of Sidon in additive number theory and on some related problems", J. London Math. Soc. 16: 212–215, doi:10.1112/jlms/s1-16.4.212, <http://www.renyi.hu/~p_erdos/1941-01.pdf>. Addendum, 19 (1944), 208.
  2. O'Bryant, K. (2004), "A complete annotated bibliography of work related to Sidon sequences", Electronic Journal of Combinatorics 11: 39, <http://www.emis.ams.org/journals/EJC/Surveys/ds11.pdf>.
  3. Ajtai, M.; Komlós, J. & Szemerédi, E. (1981), "A dense infinite Sidon sequence", European Journal of Combinatorics 2 (1): 1–11, Sablon:MR.
  4. Ruzsa, I. Z. (1998), "An infinite Sidon sequence", Journal of Number Theory 68: 63–71, Sablon:MR, DOI 10.1006/jnth.1997.2192.
  5. Erdős, P. & Rényi, A. (1960), "Additive properties of random sequences of positive integers", Acta Arithmetica 6: 83–110, Sablon:MR, <http://www.renyi.hu/~p_erdos/1960-02.pdf>.