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 ≥ 3 {\displaystyle k\geq 3} természetes szám, definiáljuk az r k ( n ) {\displaystyle r_{k}(n)} függvényt a következőképpen: jelölje r k ( n ) {\displaystyle r_{k}(n)} az { 1 , … , n } {\displaystyle \{1,\dots ,n\}} halmaz legnagyobb olyan részhalmazának az elemszámát, amely nem tartalmaz k-tagú számtani sorozatot. Ekkor

lim n → ∞ r k ( n ) n = 0. {\displaystyle \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 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 c k = lim r k ( n ) / n {\displaystyle c_{k}=\lim r_{k}(n)/n} határérték létezik és vagy minden c k {\displaystyle c_{k}} 0-val egyenlő vagy pedig lim c k = 1 {\displaystyle \lim c_{k}=1} . Behrend alsó korlátot is megadott,[3] belátta, hogy r 3 ( n ) > n e c log ⁡ n {\displaystyle r_{3}(n)>ne^{c{\sqrt {\log n}}}} . Ezt Robert Rankin r k ( n ) > n e − c ( log ⁡ n ) 1 / ( k − 1 ) {\displaystyle 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 {\displaystyle 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 {\displaystyle 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, X {\displaystyle {\mathcal {X}}} σ-algebra rajta, μ valószínűségi mérték X {\displaystyle {\mathcal {X}}} -en. Ekkor minden E ∈ X {\displaystyle E\in {\mathcal {X}}} halmazra, ha μ ( E ) > 0 {\displaystyle \mu (E)>0} , akkor

lim inf 1 N ∑ n = 0 N − 1 μ ( E ∩ T − n E ∩ T − 2 n E ∩ ⋯ ∩ T − ( k − 1 ) n E ) > 0 {\displaystyle \liminf {\frac {1}{N}}\sum _{n=0}^{N-1}\mu (E\cap T^{-n}E\cap T^{-2n}E\cap \cdots \cap T^{-(k-1)n}E)>0}

E bizonyítás érdekessége, hogy elvileg sem adhat semmilyen becslést az r k ( n ) {\displaystyle 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

Roth eredeti bizonyítása nem adott korlátot r 3 ( n ) {\displaystyle r_{3}(n)} -re, de 1953-ban megmutatta, hogy módszerével az

r 3 ( n ) = O ( n log ⁡ log ⁡ n ) {\displaystyle 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 ( n ( log ⁡ n ) c ) {\displaystyle 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 ( log ⁡ log ⁡ n log ⁡ n n ) {\displaystyle 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 ( n ( log ⁡ log ⁡ n ) c ( k ) ) {\displaystyle 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 ( n ( log ⁡ n ) c ) {\displaystyle 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.

Jegyzetek

  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.
  • Matematika Matematikaportál • összefoglaló, színes tartalomajánló lap