Szemerédiho věta: Porovnání verzí

← Přejít na předchozí porovnání Přejít na další porovnání →

Smazaný obsah Přidaný obsah

V textu

Verze z 12. 2. 2019, 17:54

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\geq 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

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.

↑ 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.
↑ 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, MR 0369312.
↑ 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, MR 0245555.
↑ 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, MR 0051853.
↑ 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. MR 0498471.
↑ 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. MR 1844079.

[erdos_turan-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.

[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, MR 0369312.

[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, MR 0245555.

[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, MR 0051853.

[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. MR 0498471.

[gowers-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. MR 1844079.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Řádek 1: / Řádek 1: @@
-'''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 <math>n_0</math>, že pro všechna <math>n\ge n_0</math> každá podmnožina <math>{1,2,\dots,n}</math> [[mohutnost]]i alespoň ''dn'' obsahuje ''k''-prvkovou [[aritmetická posloupnost|aritmetickou posloupnost]].<ref name="erdos turan">{{citation|authorlink1=Pál Erdős|first1=Pál|last1=Erdős|authorlink2=Pál Turán|first2=Pál|last2=Turán|title=On some sequences of integers|journal=[[Journal of the London Mathematical Society]]|volume=11|issue=4|year=1936|pages=261–264|url=http://www.renyi.hu/~p_erdos/1936-05.pdf|doi=10.1112/jlms/s1-11.4.261}}</ref>  Jako větu tvrzení dokázal v roce 1975 [[Endre Szemerédi]],<ref>{{citation|authorlink=Endre Szemerédi|first=Endre|last=Szemerédi|title=On sets of integers containing no ''k'' elements in arithmetic progression|journal=Acta Arithmetica|volume=27|pages=199–245|year=1975|url=http://matwbn.icm.edu.pl/ksiazki/aa/aa27/aa27132.pdf|id=Zbl 0303.10056, [[Mathematical Reviews|MR]][http://www.ams.org/mathscinet-getitem?mr&#61;0369312 0369312]{{Cizojazyčná verze šablony|en|Citace elektronického periodika|komentář = viz '''[[Wikipedie:Citace]]'''|šablona = MathSciNet}}}}</ref> který již předtím v roce 1969 publikoval důkaz pro ''k'' = 4.<ref>{{citation|authorlink=Endre Szemerédi|first=Endre|last=Szemerédi|title=On sets of integers containing no four elements in arithmetic progression|journal=Acta Math. Acad. Sci. Hung.|volume=20|pages=89–104|year=1969|id=Zbl 0175.04301, [[Mathematical Reviews|MR]][http://www.ams.org/mathscinet-getitem?mr&#61;0245555 0245555]{{Cizojazyčná verze šablony|en|Citace elektronického periodika|komentář = viz '''[[Wikipedie:Citace]]'''|šablona = MathSciNet}}|doi=10.1007/BF01894569}}</ref> Předtím existoval důkaz pro ''k=3'' z roku 1953 od [[Klaus Roth|Klause Rotha]]<ref>{{citation|authorlink=Klaus Friedrich Roth|first=Klaus Friedrich|last=Roth|title=On certain sets of integers, I|journal=[[Journal of the London Mathematical Society]]|volume=28|pages=104–109|year=1953|id=Zbl 0050.04002, [[Mathematical Reviews|MR]][http://www.ams.org/mathscinet-getitem?mr&#61;0051853 0051853]{{Cizojazyčná verze šablony|en|Citace elektronického periodika|komentář = viz '''[[Wikipedie:Citace]]'''|šablona = MathSciNet}}|doi=10.1112/jlms/s1-28.1.104}}</ref> (případy ''k=1,2'' mají důkaz triviální).
+'''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 <math>n_0</math>, že pro všechna <math>n\ge n_0</math> každá podmnožina <math>{1,2,\dots,n}</math> [[mohutnost]]i alespoň ''dn'' obsahuje ''k''-prvkovou [[aritmetická posloupnost|aritmetickou posloupnost]].<ref name="erdos turan">{{citation|authorlink1=Pál Erdős|first1=Pál|last1=Erdős|authorlink2=Pál Turán|first2=Pál|last2=Turán|title=On some sequences of integers|journal=[[Journal of the London Mathematical Society]]|volume=11|issue=4|year=1936|pages=261–264|url=http://www.renyi.hu/~p_erdos/1936-05.pdf|doi=10.1112/jlms/s1-11.4.261}}</ref>  Jako větu tvrzení dokázal v roce 1975 [[Endre Szemerédi]],<ref>{{citation|authorlink=Endre Szemerédi|first=Endre|last=Szemerédi|title=On sets of integers containing no ''k'' elements in arithmetic progression|journal=Acta Arithmetica|volume=27|pages=199–245|year=1975|url=http://matwbn.icm.edu.pl/ksiazki/aa/aa27/aa27132.pdf|id=Zbl 0303.10056, [[Mathematical Reviews|MR]][http://www.ams.org/mathscinet-getitem?mr&#61;0369312 0369312]}}</ref> který již předtím v roce 1969 publikoval důkaz pro ''k'' = 4.<ref>{{citation|authorlink=Endre Szemerédi|first=Endre|last=Szemerédi|title=On sets of integers containing no four elements in arithmetic progression|journal=Acta Math. Acad. Sci. Hung.|volume=20|pages=89–104|year=1969|id=Zbl 0175.04301, [[Mathematical Reviews|MR]][http://www.ams.org/mathscinet-getitem?mr&#61;0245555 0245555]|doi=10.1007/BF01894569}}</ref> Předtím existoval důkaz pro ''k=3'' z roku 1953 od [[Klaus Roth|Klause Rotha]]<ref>{{citation|authorlink=Klaus Friedrich Roth|first=Klaus Friedrich|last=Roth|title=On certain sets of integers, I|journal=[[Journal of the London Mathematical Society]]|volume=28|pages=104–109|year=1953|id=Zbl 0050.04002, [[Mathematical Reviews|MR]][http://www.ams.org/mathscinet-getitem?mr&#61;0051853 0051853]|doi=10.1112/jlms/s1-28.1.104}}</ref> (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]]<ref>{{Citace periodika
@@ Řádek 10: / Řádek 10: @@
  |strany =204–256
  |rok =1977
- |id =[[Mathematical Reviews|MR]][http://www.ams.org/mathscinet-getitem?mr&#61;0498471 0498471]{{Cizojazyčná verze šablony|en|Citace elektronického periodika|komentář = viz '''[[Wikipedie:Citace]]'''|šablona = MathSciNet}}
+ |id =[[Mathematical Reviews|MR]][http://www.ams.org/mathscinet-getitem?mr&#61;0498471 0498471]
  |doi =10.1007/BF02813304
-}}</ref>, další v roce 2001 [[Timothy Gowers]].<ref name="gowers">{{citation|authorlink=Timothy Gowers|first=Timothy|last=Gowers|title=A new proof of Szemerédi's theorem|journal=Geom. Funct. Anal.|volume=11|issue=3|pages=465–588|url=http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi|year=2001|id=[[Mathematical Reviews|MR]][http://www.ams.org/mathscinet-getitem?mr&#61;1844079 1844079]{{Cizojazyčná verze šablony|en|Citace elektronického periodika|komentář = viz '''[[Wikipedie:Citace]]'''|šablona = MathSciNet}}|doi=10.1007/s00039-001-0332-9}}</ref>
+}}</ref>, další v roce 2001 [[Timothy Gowers]].<ref name="gowers">{{citation|authorlink=Timothy Gowers|first=Timothy|last=Gowers|title=A new proof of Szemerédi's theorem|journal=Geom. Funct. Anal.|volume=11|issue=3|pages=465–588|url=http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi|year=2001|id=[[Mathematical Reviews|MR]][http://www.ams.org/mathscinet-getitem?mr&#61;1844079 1844079]|doi=10.1007/s00039-001-0332-9}}</ref>
 Tvrzení lze vyslovit také tak, že každá [[podmnožina]] přirozených čísel s nenulovou [[horní asymptotická hustota|horní asymptotickou hustotou]] obsahuje konečné aritmetické posloupnosti libovolné délky.