Szemerédi-tétel

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

Szemerédi tétele a matematika, ezen belül a kombinatorika egyik fontos eredménye.

A tétel állítása[szerkesztés | forrásszöveg szerkesztése]

Ha k\geq 3 természetes szám, definiáljuk az r_k(n) függvényt a következőképpen: jelölje r_k(n) az \{1,\dots,n\} halmaz legnagyobb olyan részhalmazának az elemszámát, amely nem tartalmaz k-tagú számtani sorozatot. Ekkor

\lim_{n\to\infty}\frac{r_k(n)}{n}= 0.

Ezzel ekvivalens állítás, hogy minden pozitív felső sűrűségű sorozat tartalmaz tetszőleges hosszú számtani sorozatot.

Története[szerkesztés | forrásszöveg szerkesztése]

A sejtést Erdős és Turán fogalmazta meg[1] 1936-ban (bár Erdős 1961-ben megjegyezte, hogy a problémát 1930 körül Issai Schur is felvetette[2]). Céljuk a van der Waerden-tétel kvantitatív vizsgálata és annak a sejtésnek a megtámadása volt, hogy a prímszámok sorozata tartalmaz tetszőlegesen hosszú számtani sorozatot.

Behrend 1946-ban igazolta, hogy minden k-ra a c_k=\lim r_k(n)/n határérték létezik és vagy minden c_k 0-val egyenlő vagy pedig \lim c_k=1. Behrend alsó korlátot is megadott,[3]belátta, hogy r_3(n)>ne^{c\sqrt{\log n}}. Ezt Robert Rankin r_k(n)>ne^{-c(\log n)^{1/(k-1)}}-re általánosította.[4]

Először 1952-ben Roth bizonyította[5] az állítást k=3-ra, a Hardy-Littlewood-féle körmódszer felhasználásával. E tétel volt az egyik indoka annak, hogy 1958-ban Fields-érmet kapott. 1967-ben Szemerédi Endre teljesen elemi, kombinatorikus okoskodással igazolta a k=4 esetet,[6] majd 1975-ben az általános esetet is.[7] Ez a bizonyítás rendkívül bonyolult, kifinomult volt. A bizonyításhoz használt egyik segédtétel, a Szemerédi-féle regularitási lemma később a kombinatorika egyik fontos eszközévé vált. Erdős 1000 dollárral honorálta a rendkívüli teljesítményt, megjegyezve, hogy ezzel valószínűleg megsértette a minimális órabérre vonatkozó USA-törvényt. Mivel Szemerédi bizonyítása felhasználta van der Waerden tételét (a teljes tételt, már a k=4 esetre is), nem volt alkalmas arra, hogy javítson az ismert becsléseken. 1977-ben Hillél Fürstenberg átfogalmazta a tételt egy ergodelméleti állítássá és bebizonyította azt. Eszerint legyen X tetszőleges halmaz, \mathcal X σ-algebra rajta, μ valószínűségi mérték \mathcal X-en. Ekkor minden E\in \mathcal{X} halmazra, ha \mu(E)>0, akkor

\liminf\frac{1}{N}\sum^{N-1}_{n=0}\mu(E\cap T^{-n}E\cap T^{-2n}\cap\cdots T^{-(k-1)n}E)>0

E bizonyítás érdekessége, hogy elvileg sem adhat semmilyen becslést az r_k(n) függvények nagyságrendjére. 2001-ben Timothy Gowers harmonikus analízist használó újabb bizonyítást[8] adott Szemerédi tételére, ez igen jó becsléseket adott. Fürstenberg módszerét módosítva Terence Tao olyan bizonyítást adott, ami alkalmas korlátok kinyerésére, bár ezek messze nem olyan jók, mint a Gowers-félék.

Becslések[szerkesztés | forrásszöveg szerkesztése]

Roth eredeti bizonyítása nem adott korlátot r_3(n)-re, de 1953-ban megmutatta, hogy módszerével az

r_3(n)=O\left(\frac{n}{\log \log n}\right)

becslés adható. Heath-Brown és Szemerédi később az

r_3(n)=O\left(\frac{n}{(\log n)^c}\right)

becslést adta egy valamilyen c>0 konstanssal. Ezt Bourgain megjavította az

r_3(n)=O\left(\sqrt{\frac{\log\log n}{\log n}}n\right)

becslésre.

Gowers 2001-ben az általános esetre az

r_k(n)=O\left(\frac{n}{(\log\log n)^{c(k)}}\right)

korlátot adta, ahol c(k) k-tól függő pozitív konstans.

Legújabban Ben Green és Terence Tao igen bonyolult módszerekkel az

r_4(n)=O\left(\frac{n}{(\log n)^c}\right)

becslést kapta (alkalmas c>0-val).

Források[szerkesztés | forrásszöveg szerkesztése]

  • C. J. Moreno, S. S. Wagstaff: Sums of Squares of Integers, Chapman & Hall/CRC, 2005. (az eredeti Szemerédi-féle bizonyítás)
  • Ben Green, Terence Tao: Szemerédi's theorem a Scholarpedia-n.

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. P. Erdős, P. Turán, On some sequences of integers, J. London Math. Soc., 11(1936), 261--264.
  2. P.Erdős: Some unsolved problems, Magyar Tud. Akad. Mat. Kut. Int. Közl., 9(1961)221-254.
  3. F. A. Behrend: On the sets of integers which contain no three in arithmetic progression, Proc. Nat. Acad. Sci., 23(1946), 331-332.
  4. Robert A. Rankin: Sets of integer containing not more than a given number of terms in arithmetic progression, Proc. Ryal Soc. Edinburgh, Sect A, 65(1962), 332-344.
  5. K. F. Roth, On certain sets of integers I, J. London Math. Soc., 28(1953), 104-109.
  6. E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hung., 20(1969)89-104.
  7. E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica, 27(1975), 199-245.
  8. W. T. Gowers: A new proof of Szemerédi's theorem, Geom. Funct. Anal., 11(2001), 465-588.