Szemerédiho veta

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Szemerédiho veta hovorí, že každá podmožina prirodzených čísel s kladnou hornou asymptotickou hustotou obsahuje konečné aritmetické postupnosti lubobovolnej dĺžky. Szemerédiho veta zovšeobecnuje van der Waerdenovu vetu.

História[upraviť | upraviť zdroj]

Tvrdenie Szemerédiho vety navrhol ako zaujímavú hypotézu Paul Erdős a Paul Turán v roku 1936.

História postupného dokazovania Szemerédiho vety sa odvíja od maximálnej dĺžky k konečných aritmetických podpostupností ktoré predchodcovia Szemerédiho vety v podmnožine prirodzených čísel garantovali.

  • Prípady k=1 a k=2, teda tvrdenia garantujúce existenciu jedno a dvojprvkových postupností sú triviálne, pretože lubovoľné číslo alebo lubovoľná dvojica čísel tvorí triviálnu konečnú aritmetickú postupnosť.
  • Prípad k=3 zodpovedal pozitívne Klaus Roth v roku 1956.
  • Prípad k=4 pozitívne zodpovedal Endre Szemerédi v roku 1969.
  • V roku 1972 prípad k=4 vyriešil aj Roth použijúc metódu podobnú tej, ktorou predtým vyriešil prípad k=3.
  • Pre lubovoľné k tvrdenie nakoniec dokázal Szemerédi v roku 1975.
  • V roku 1977 podal Hillel Furstenberg doležitý alternatívny dôkaz Szemerédiho vety založený na ergodickej teórii.
  • V roku 2001 podal Timothy Gowers iný alternatívny dôkaz.

Pozri aj[upraviť | upraviť zdroj]