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$, že pro všechna $n\ge n_0$ každá podmnožina $1,2,\dots ,n$ mohutnosti alespoň dn obsahuje k-prvkovou aritmetickou posloupnost. Jako větu tvrzení dokázal v roce 1975 Endre Szemerédi, který již předtím v roce 1969 publikoval důkaz pro k = 4. Předtím existoval důkaz pro k=3 z roku 1953 od Klause Rotha (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, další v roce 2001 Timothy Gowers.

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