Schurs teorem (Ramsey teori)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 24. april 2020; checks kræver 2 redigeringer .

Schurs sætning er et udsagn i Ramsey-teorien om, at for enhver farvning af naturlige tal i et endeligt antal farver, er der en enfarvet løsning af ligningen . Opkaldt efter dens forfatter, Isai Shura . $x+y=z$

Oprindelse

Schurs sætning opstod som et værktøj til at bevise et udsagn, der trivielt ville følge af negationen af den dengang ubeviste Fermats sidste sætning , nemlig svaret på spørgsmålet om solvabiliteten af dens ligning i restringen med et tilstrækkeligt stort primmodul : for enhver for primtal , ligningen $n\ge 3$ $p>p_{0}=p_{0}(n)$

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

har ikke-nul løsninger?

Sådanne ligninger (og lignende) blev overvejet af Guglielmo Libri i 1832 [1] , men først i 1909 modtog Leonard Eugene Dixon det første generelle resultat om dette emne - han viste rigtigheden af denne erklæring for alle primtal . [2] $n$

Dixon handlede ved talteoretiske metoder, men i 1917 anvendte Schur en kombinatorisk tilgang til problemet, idet han betragtede opdelingen af en ringmodulo som et primtal i klasser af rester svarende til forskellige værdier af den diskrete logaritme af en eller anden restmodulo ( med andre ord, i kosæt af multiplikative undergrupper ). I dette tilfælde kan man ved at multiplicere alle variabler med en primitiv rod "overføre" løsninger af en hvilken som helst lineær ligning fra en klasse til en anden (hvis før multiplikation alle variable var i samme klasse, vil det efter en sådan "overførsel" være det samme). Takket være dette bliver et udsagn af Ramsey-typen (om eksistensen af kun et partitionselement, men ikke om egenskaberne af hvert enkelt sæt) vedrørende lineære ligninger let til en talteoretisk udsagn (om en mængdes egenskaber), da eksistensen af en konfiguration i et element af partitionen medfører dens eksistens i alle andre. [3] $n$

Ordlyd

Hvis , så ${\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}$

Som mange udsagn fra Ramsey-teorien indrømmer Schurs sætning også en endelig formulering. Det betyder, at for fast, minimum af dem, der passer til betingelsen , ikke kan være vilkårligt stort. $k$ $x,y$

Sidste version

For alle findes der sådan, at hvis , så $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}$

Bevis

Det er sædvanligt at bevise Schur-sætningen i den endelige formulering ved at overveje , det vil sige Ramsey-tallene for 3-kliker (trekanter), når man farvelægger . Hvis betyder farven på et tal i en bestemt farve , så når man farvelægger kanterne af hele grafen på en sådan måde , at eksistensen af en ensfarvet trekant indebærer eksistensen af den ønskede enfarvede løsning i partitionen $S=R(3,\dots,3)$ $k$ $c(n)$ $n$ $\{1,\dots ,S\}$ $K_{S}$ ${\overline {c}}(i,j)=c(|ij|)$ $\{1,\dots ,S\}$

På tidspunktet for den første udgivelse af Schurs sætning var Ramseys sætning endnu ikke kendt, men Schur fremførte argumenter for forskelle i tal tilhørende en af partitionsklasserne, som var fuldstændig magen til dem, der blev udført i det generelle bevis for Ramseys sætning. teori.

Et sådant bevis giver et skøn . Som anvendt på spørgsmålet om løseligheden af ligningen for de værdier, der blev betragtet tidligere, viste det sig at være værre end det, der blev opnået af Libri (han viste, at for primtal er betingelsen tilstrækkelig ). [fire] $S<e\cdot (n!)$ $x^{n}+y^{n}\equiv z^{n}{\pmod {p))$ $n$ $n$ ${\displaystyle p>n^{4))$

Forholdet til andre teoremer

Schurs sætning minder meget om van der Waerdens sætning for progressioner af længde 3 (fordi en sådan progression er løsningen af ligningen ), men i modsætning til den tillader den ikke en additiv-kombinatorisk generalisering (som er Roth-sætningen ) for van der Waerdens sætning ), da den sumfri mængde i sig selv kan være tilstrækkelig tæt (f.eks. mængden af alle ulige tal). $x+y=2z$

Se også

Folkmans teorem

Litteratur

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

Noter

↑ Libri, 1832 .
↑ Dickson, 1909 .
↑ Schur, 1917 .
↑ Schur, 1917 , s. 116, er formlen nævnt på en separat linje i midten af sidste afsnit. $M=m^{4}-6m^{3}+13m^{2}-6m+1$