Schurův teorém (Ramseyho teorie)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. dubna 2020; kontroly vyžadují 2 úpravy .

Schurův teorém je tvrzení v Ramseyově teorii , že pro jakékoli obarvení přirozených čísel v konečném počtu barev existuje jednobarevné řešení rovnice . Pojmenováno po svém autorovi Isai Shura . $x+y=z$

Origins

Schurova věta vznikla jako nástroj k prokázání jednoho tvrzení, které by triviálně vyplývalo z negace tehdy neprokázané Fermatovy poslední věty , totiž odpověď na otázku řešitelnosti její rovnice v reziduálním kruhu s dostatečně velkým primárním modulem: pro libovolné pro prvočísla , rovnice $n\ge 3$ $p>p_{0}=p_{0}(n)$

x^{n}+y^{n}\equiv z^{n}{\pmod {p}}

má nenulová řešení?

Takové rovnice (a podobné) uvažoval Guglielmo Libri v roce 1832 [1] , ale teprve v roce 1909 získal Leonard Eugene Dixon první obecný výsledek na toto téma - ukázal správnost tohoto tvrzení pro všechna prvočísla . [2] $n$

Dixon jednal pomocí číselně teoretických metod, ale v roce 1917 Schur použil kombinatorický přístup k problému, přičemž považoval rozdělení modulů kruhu za prvočíslo do tříd zbytků odpovídajících různým hodnotám diskrétního logaritmu jednoho nebo druhého rezidua modulo ( jinými slovy do množin multiplikativních podskupin ). V tomto případě vynásobením všech proměnných primitivním kořenem lze „přenést“ řešení libovolné lineární rovnice z jedné třídy do druhé (pokud byly před násobením všechny proměnné ve stejné třídě, pak po takovém „přenosu“ bude stejný). Díky tomu se výrok Ramseyho typu (o existenci pouze rozdělovacího prvku, nikoli však o vlastnostech každé konkrétní množiny) o lineárních rovnicích snadno změní na výrok číselně teoretický (o vlastnostech množiny), neboť existence konfigurace v jednom prvku oddílu znamená jeho existenci ve všech ostatních. [3] $n$

Formulace

Pokud , pak ${\displaystyle {\mathbb {N} }={\mathcal {N}}_{1}\cup {\mathcal {N}}_{2}\cup \dots \cup {\mathcal {N}}_{ k))$ $\exists i,x,y:\ \left\lbrace {x,y,x+y}\right\rbrace \subset {\mathcal {N}}_{i}$

Stejně jako mnoho výroků z Ramseyho teorie, i Schurova věta připouští konečnou formulaci. To znamená, že pro fixní nemůže být minimum těch, které splňují podmínku , libovolně velké. $k$ $x, y$

Finální verze

Pro každého existuje taková, že když , tak $k$ $S=S(k)$ $\{1,2,\dots ,S\}={\mathcal {N}}_{1}\cup {\mathcal {N}}_{2}\cup \dots \cup {\mathcal { N}}_{k}$ $\exists i,x,y:\ \left\lbrace {x,y,x+y}\right\rbrace \subset {\mathcal {N}}_{i}$

Důkaz

Je zvykem dokázat Schurovu větu v konečné formulaci tím, že při vybarvování uvažujeme , tedy Ramseyova čísla pro 3 kliky (trojúhelníky) . If znamená barvu čísla v nějakém pevném vybarvení , pak při vybarvování okrajů celého grafu tak , že existence jednobarevného trojúhelníku implikuje existenci požadovaného jednobarevného řešení v oddílu $S=R(3,\tečky ,3)$ $k$ $c(n)$ $n$ $\{1,\tečky ,S\}$ $K_{S}$ ${\overline {c}}(i,j)=c(|ij|)$ $\{1,\tečky ,S\}$

V době prvního zveřejnění Schurovy věty nebyla Ramseyova věta ještě známa, ale Schur provedl argumenty pro rozdíly čísel patřících do jedné z dělicích tříd, které byly zcela podobné těm, které byly provedeny v obecném důkazu Ramseyho teorie.

Takový důkaz poskytuje odhad . Pokud jde o otázku řešitelnosti rovnice pro hodnoty uvažované dříve, ukázalo se, že je horší než to, které získal Libri (ukázal, že pro prvočísla podmínka stačí ). [čtyři] $S<e\cdot (n!)$ $x^{n}+y^{n}\equiv z^{n}{\pmod {p}}$ $n$ $n$ ${\displaystyle p>n^{4))$

Vztah s jinými teorémy

Schurova věta je velmi podobná větě van der Waerdenové pro posloupnosti délky 3 (protože taková posloupnost je řešením rovnice ), na rozdíl od ní však neumožňuje aditivně-kombinatorické zobecnění (což je Rothův teorém pro van der Waerdenův teorém ), protože samotná bezsoučtová množina může být dostatečně hustá (například množina všech lichých čísel). $x+y=2z$

Viz také

Folkmanova věta

Literatura

Par Mr. G. Libri de Florence. Memoire sur la theorie des nombres. (francouzsky) // Journal für die reine und angewandte Mathematik. - 1832. - Sv. 9 , livr. 2 . — S. 261-276 .
Pan. LE Dickson. O kongruenci $x^{n}+y^{n}+z^{n}\equiv 0{\pmod {p}}$ (anglicky) // Journal für die reine und angewandte Mathematik. - 1909. - Sv. 135 . - S. 134-141 .
I. Schur. Über die Kongruenz $x^{m}+y^{m}\equiv z^{m}{\pmod {p}}$ (německy) // Jahresbericht der Deutschen Mathematiker-Vereinigung. - 1917. - Bd. 25 . - S. 114-117 .

Poznámky

↑ Libri, 1832 .
↑ Dickson, 1909 .
↑ Schur, 1917 .
↑ Schur, 1917 , str. 116 je vzorec uveden na samostatném řádku uprostřed posledního odstavce. $M=m^{4}-6m^{3}+13m^{2}-6m+1$