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

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

A sejtést Erdős és Turán fogalmazta meg 1936-ban (bár Erdős 1961-ben megjegyezte, hogy a problémát 1930 körül Issai Schur is felvetette). 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,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.

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. 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, majd 1975-ben az általános esetet is. 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 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 $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

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