Szemerédi tétele a matematika, ezen belül a kombinatorika egyik fontos eredménye.
A tétel állítása 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 A sejtést Erdős Pál és Turán Pál fogalmazta megP. Erdős, P. Turán, On some sequences of integers, J. London Math. Soc., 11(1936), 261--264. 1936-ban (bár Erdős 1961-ben megjegyezte, hogy a problémát 1930 körül Issai Schur is felvetetteP.Erdős: Some unsolved problems, Magyar Tud. Akad. Mat. Kut. Int. Közl., 9(1961)221-254.). 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,F. A. Behrend: On the sets of integers which contain no three in arithmetic progression, Proc. Nat. Acad. Sci., 23(1946), 331-332. belátta, hogy . Ezt Robert Rankin -re általánosította.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.
Először 1952-ben Roth bizonyítottaK. F. Roth, On certain sets of integers I, J. London Math. Soc., 28(1953), 104-109. 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,E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hung., 20(1969)89-104. majd 1975-ben az általános esetet is.E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica, 27(1975), 199-245. 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ástW. T. Gowers: A new proof of Szemerédi's theorem, Geom. Funct. Anal., 11(2001), 465-588. 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 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 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
Kategória:Additív kombinatorika Kategória:Számelméleti tételek Kategória:Kombinatorikai tételek