Szemerédi-tétel
Szemerédi tétele a matematika, ezen belül a kombinatorika egyik fontos eredménye.
A tétel állítása
[szerkesztés]Ha természetes szám, definiáljuk az függvényt a következőképpen: jelölje az halmaz legnagyobb olyan részhalmazának az elemszámát, amely nem tartalmaz k-tagú számtani sorozatot. Ekkor
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]A sejtést Erdős Pál és Turán Pál 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 határérték létezik és vagy minden 0-val egyenlő vagy pedig . Behrend alsó korlátot is megadott,[3] belátta, hogy . Ezt Robert Rankin -re általánosította.[4]
Először 1952-ben Roth bizonyította[5] az állítást -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 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, σ-algebra rajta, μ valószínűségi mérték -en. Ekkor minden halmazra, ha , akkor
E bizonyítás érdekessége, hogy elvileg sem adhat semmilyen becslést az 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]Roth eredeti bizonyítása nem adott korlátot -re, de 1953-ban megmutatta, hogy módszerével az
becslés adható. Heath-Brown és Szemerédi később az
becslést adta egy valamilyen c>0 konstanssal. Ezt Bourgain megjavította az
becslésre.
Gowers 2001-ben az általános esetre az
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
becslést kapta (alkalmas c>0-val).
Források
[szerkesztés]- 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]- ↑ P. Erdős, P. Turán, On some sequences of integers, J. London Math. Soc., 11(1936), 261--264.
- ↑ P.Erdős: Some unsolved problems, Magyar Tud. Akad. Mat. Kut. Int. Közl., 9(1961)221-254.
- ↑ F. A. Behrend: On the sets of integers which contain no three in arithmetic progression, Proc. Nat. Acad. Sci., 23(1946), 331-332.
- ↑ 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.
- ↑ K. F. Roth, On certain sets of integers I, J. London Math. Soc., 28(1953), 104-109.
- ↑ E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hung., 20(1969)89-104.
- ↑ E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica, 27(1975), 199-245.
- ↑ W. T. Gowers: A new proof of Szemerédi's theorem, Geom. Funct. Anal., 11(2001), 465-588.