Szemerédiho věta

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 {\displaystyle n_{0}} , že pro všechna n ≥ n 0 {\displaystyle n\geq n_{0}} každá podmnožina 1 , 2 , … , n {\displaystyle {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

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. On some sequences of integers. Journal of the London Mathematical Society. 1936, s. 261–264. Dostupné online. DOI 10.1112/jlms/s1-11.4.261. Je zde použita šablona {{Citation}} označená jako k „pouze dočasnému použití“.
  2. ↑ SZEMERÉDI, Endre. On sets of integers containing no k elements in arithmetic progression. Acta Arithmetica. 1975, s. 199–245. Dostupné online. Zbl 0303.10056, MR0369312. Je zde použita šablona {{Citation}} označená jako k „pouze dočasnému použití“.
  3. ↑ SZEMERÉDI, Endre. On sets of integers containing no four elements in arithmetic progression. Acta Math. Acad. Sci. Hung.. 1969, s. 89–104. DOI 10.1007/BF01894569. Zbl 0175.04301, MR0245555. Je zde použita šablona {{Citation}} označená jako k „pouze dočasnému použití“.
  4. ↑ ROTH, Klaus Friedrich. On certain sets of integers, I. Journal of the London Mathematical Society. 1953, s. 104–109. DOI 10.1112/jlms/s1-28.1.104. Zbl 0050.04002, MR0051853. Je zde použita šablona {{Citation}} označená jako k „pouze dočasnému použití“.
  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. A new proof of Szemerédi's theorem. Geom. Funct. Anal.. 2001, s. 465–588. Dostupné online. DOI 10.1007/s00039-001-0332-9. MR1844079. Je zde použita šablona {{Citation}} označená jako k „pouze dočasnému použití“.