Szemerédi-tétel

A Wikipédiából, a szabad lexikonból.

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

[szerkesztés] A tétel állítása

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

[szerkesztés] Története

A sejtést Erdős és Turán fogalmazta meg 1936-ban. 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.

Először 1952-ben Roth bizonyította az állítást $k = 3$ -ra, a Hardy-Littlewood-féle körmódszer felhasználásával. 1953-ban Roth megmutatta, hogy módszerével az

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

becslés adható. A legjobb alsó korlát a Behrendtől eredő

$r_3(n)\geq n^{1-c/\sqrt{\log n}}.$

1967-ben Szemerédi Endre teljesen elemi, kombinatorikus okoskodással igazolta a $k = 4$ esetet, majd 1969-ben az általános esetet is. Ez a bizonyítás rendkívül bonyolult, kifinomult volt. 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, 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 $μ(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 T. Gowers harmonikus analízist használó újabb bizonyítást adott Szemerédi tételére, ez igen jó becsléseket adott. Fürstenberg módszerét módosítva 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.