Schurs teorem (Ramsey-teorin)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 april 2020; kontroller kräver 2 redigeringar .

Schurs teorem är ett uttalande i Ramsey-teorin att för varje färgning av naturliga tal i ett ändligt antal färger finns det en enfärgslösning av ekvationen . Uppkallad efter dess författare, Isai Shura . $x+y=z$

Origins

Schurs sats uppstod som ett verktyg för att bevisa ett påstående som trivialt skulle följa av negationen av den då obevisade Fermats sista sats , nämligen svaret på frågan om lösbarheten av dess ekvation i restringen med en tillräckligt stor primmodul : för någon för primtal , ekvationen $n\ge 3$ $p>p_{0}=p_{0}(n)$

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

har lösningar som inte är noll?

Sådana ekvationer (och liknande) övervägdes av Guglielmo Libri 1832 [1] , men först 1909 fick Leonard Eugene Dixon det första allmänna resultatet i detta ämne - han visade att detta uttalande var korrekt för alla primtal . [2] $n$

Dixon agerade med talteoretiska metoder, men 1917 tillämpade Schur ett kombinatoriskt tillvägagångssätt på problemet, och betraktade uppdelningen av en ringmodulo som ett primtal i klasser av rester som motsvarar olika värden på den diskreta logaritmen för en eller annan restmodulo ( med andra ord, till uppsättningar av multiplikativa undergrupper ). I det här fallet, genom att multiplicera alla variabler med en primitiv rot , kan man "överföra" lösningar av vilken linjär ekvation som helst från en klass till en annan (om före multiplikationen var alla variabler i samma klass, så kommer det efter en sådan "överföring" att vara det samma). Tack vare detta förvandlas ett påstående av Ramsey-typ (om förekomsten av endast ett partitionselement, men inte om egenskaperna för varje särskild uppsättning) angående linjära ekvationer lätt till ett talteoretiskt påstående (om egenskaperna hos en mängd), eftersom förekomsten av en konfiguration i ett element av partitionen innebär att det finns i alla andra. [3] $n$

Formulering

Om , då ${\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}$

Liksom många påståenden från Ramsey-teorin medger Schurs teorem också en ändlig formulering. Detta innebär att, för fast, det minimum av de som passar till villkoret inte kan vara godtyckligt stort. $k$ $x,y$

Slutversion

För alla finns det så att om , då $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 är vanligt att bevisa Schur-satsen i den slutliga formuleringen genom att beakta , det vill säga Ramsey-talen för 3-klickar (trianglar) när man färgar . Om betyder färgen på ett nummer i någon fast färg , då när man färgar kanterna på hela grafen på ett sådant sätt att , förekomsten av en enfärgad triangel innebär att det finns den önskade enfärgade lösningen 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\}$

Vid tidpunkten för den första publiceringen av Schurs sats var Ramseys sats ännu inte känd, men Schur förde argument för skillnader i tal som tillhörde en av partitionsklasserna som var helt lika de som utfördes i det allmänna beviset för Ramseys teori.

Ett sådant bevis ger en uppskattning . Som tillämpat på frågan om lösbarheten av ekvationen för de värden som ansågs tidigare, visade det sig vara värre än det som erhölls av Libri (han visade att för primtal räcker villkoret ). [fyra] $S<e\cdot (n!)$ $x^{n}+y^{n}\equiv z^{n}{\pmod {p))$ $n$ $n$ ${\displaystyle p>n^{4))$

Samband med andra teorem

Schurs sats är mycket lik van der Waerdens sats för progressioner av längd 3 (eftersom en sådan progression är lösningen på ekvationen ), men till skillnad från den tillåter den inte en additiv-kombinatorisk generalisering (vilket är Roth-satsen för van der Waerdens sats ), eftersom den summafria mängden i sig kan vara tillräckligt tät (till exempel mängden av alla udda tal). $x+y=2z$

Se även

Folkmans teorem

Litteratur

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

Anteckningar

↑ Libri, 1832 .
↑ Dickson, 1909 .
↑ Schur, 1917 .
↑ Schur, 1917 , sid. 116, nämns formeln på en separat rad i mitten av sista stycket. $M=m^{4}-6m^{3}+13m^{2}-6m+1$