Szemerédiho věta

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Szemerédiho věta je tvrzení z oboru teorie čísel, které potvrzuje Erdősovu–Turánovu domněnku z roku 1936. Pál Erdős a Paul Turán vyslovili hypotézu, že pro každé přirozené číslo k a reálné číslo d, 0<d<1, existuje takové přirozené číslo n_0, že pro všechna n\ge n_0 každá podmnožina {1,2,\dots,n} mohutnosti alespoň dn obsahuje k-prvkovou aritmetickou posloupnost.[1] Jako větu tvrzení dokázal v roce 1975 Endre Szemerédi,[2] který již předtím v roce 1969 publikoval důkaz pro k = 4.[3] Předtím existoval důkaz pro k=3 z roku 1953 od Klause Rotha[4] (případy k=1,2 mají důkaz triviální).

Szemerédiho větu se později podařilo dokázat několika dalšími metodami, jeden z alternativních důkazů publikoval v roce 1977 Hilel Fürstenberg[5], další v roce 2001 Timothy Gowers.[6]

Tvrzení lze vyslovit také tak, že každá podmnožina přirozených čísel s nenulovou horní asymptotickou hustotou obsahuje konečné aritmetické posloupnosti libovolné délky.

Jedná se o zobecnění van der Waerdenovy věty, naopak Greenova-Taova věta představuje silnější tvrzení pro speciální případ množiny prvočísel (ta má asymptotickou hustotu nulovou a samotná Szemerédiho věta se na ni tedy nevztahuje).

Reference[editovat | editovat zdroj]

V tomto článku byly použity překlady textů z článků Szemerédiho veta na slovenské Wikipedii a Szemerédi's theorem na anglické Wikipedii.

  1. Erdős, Pál; Turán, Pál(1936),"On some sequences of integers",Journal of the London Mathematical Society11(4): 261–264, http://www.renyi.hu/~p_erdos/1936-05.pdf 
  2. Szemerédi, Endre(1975),"On sets of integers containing no k elements in arithmetic progression",Acta Arithmetica27: 199–245, Zbl 0303.10056, MR0369312, http://matwbn.icm.edu.pl/ksiazki/aa/aa27/aa27132.pdf 
  3. Szemerédi, Endre(1969),"On sets of integers containing no four elements in arithmetic progression",Acta Math. Acad. Sci. Hung.20: 89–104, Zbl 0175.04301, MR0245555 
  4. Roth, Klaus Friedrich(1953),"On certain sets of integers, I",Journal of the London Mathematical Society28: 104–109, Zbl 0050.04002, MR0051853 
  5. FÜRSTENBERG, Hilel. Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions. J. D’Analyse Math.. 1977, s. 204–256. DOI:10.1007/BF02813304. MR0498471. 
  6. Gowers, Timothy(2001),"A new proof of Szemerédi's theorem",Geom. Funct. Anal.11(3): 465–588, MR1844079, http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi