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

Példák[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 \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[szerkesztés | forrásszöveg szerkesztése]

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

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

A legjobb alsó becslést Ruzsa Imre adta,[4] 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,[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 | forrásszöveg szerkesztése]

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