Teorema lui Schur (teoria Ramsey)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 24 aprilie 2020; verificările necesită 2 modificări .

Teorema lui Schur este o afirmație din teoria Ramsey conform căreia pentru orice colorare a numerelor naturale într-un număr finit de culori, există o soluție monocoloră a ecuației . Numit după autorul său, Isai Shura . $x+y=z$

Origini

Teorema lui Schur a apărut ca instrument de demonstrare a unei afirmații care ar urma trivial din negația ultimei teoreme a lui Fermat, nedovedită atunci , și anume, răspunsul la întrebarea despre solubilitatea ecuației sale în inelul rezidual cu un modul prim suficient de mare : pt. oricare pentru numere prime , ecuația $n\ge 3$ $p>p_{0}=p_{0}(n)$

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

are soluții diferite de zero?

Astfel de ecuații (și altele similare) au fost luate în considerare de Guglielmo Libri în 1832 [1] , dar abia în 1909 Leonard Eugene Dixon a primit primul rezultat general pe această temă - el a arătat corectitudinea acestei afirmații pentru toate numerele prime . [2] $n$

Dixon a acționat prin metode teoretice numerelor, dar în 1917 Schur a aplicat o abordare combinatorie a problemei, considerând împărțirea unui inel modulo un prim în clase de reziduuri corespunzătoare diferitelor valori ale logaritmului discret al unuia sau altui reziduu modulo ( cu alte cuvinte, în seturi ale subgrupurilor multiplicative ). În acest caz, prin înmulțirea tuturor variabilelor cu o rădăcină primitivă , se pot „transfera” soluțiile oricărei ecuații liniare de la o clasă la alta (dacă înainte de înmulțire toate variabilele erau în aceeași clasă, atunci după un astfel de „transfer” va fi aceeași). Datorită acestui fapt, o declarație de tip Ramsey (despre existența doar a unui element de partiție, dar nu despre proprietățile fiecărei mulțimi particulare) referitoare la ecuații liniare se transformă cu ușurință într-o afirmație teoretică a numerelor (despre proprietățile unei mulțimi), deoarece existenţa unei configuraţii într-un element al partiţiei atrage după sine existenţa acesteia în toate celelalte. [3] $n$

Formulare

Dacă , atunci ${\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}$

Ca multe afirmații din teoria Ramsey, teorema lui Schur admite și o formulare finită. Aceasta înseamnă că, pentru fix, minimul dintre cei care se potrivesc condiției nu poate fi arbitrar de mare. $k$ $X y$

Versiunea finala

Pentru toată lumea există astfel încât dacă , atunci $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}$

Dovada

Se obișnuiește să se demonstreze teorema Schur în formularea finală luând în considerare , adică , numerele Ramsey pentru 3-clicuri (triunghiuri) atunci când se colorează . Dacă înseamnă culoarea unui număr într-o colorare fixă , atunci când colorați marginile graficului complet în așa fel încât , existența unui triunghi monocolor implică existența soluției dorite monocolore în partiție $S=R(3,\dots ,3)$ $k$ $c(n)$ $n$ $\{1,\dots ,S\}$ $K_{S}$ ${\overline {c}}(i,j)=c(|ij|)$ $\{1,\dots ,S\}$

La momentul primei publicări a teoremei lui Schur, teorema lui Ramsey nu era încă cunoscută, dar Schur a efectuat argumente pentru diferențele de numere aparținând uneia dintre clasele de partiții care erau complet similare cu cele efectuate în demonstrația generală a lui Ramsey. teorie.

O astfel de dovadă oferă o estimare . Așa cum este aplicat la problema solvabilității ecuației pentru valorile luate în considerare mai devreme, sa dovedit a fi mai proastă decât cea obținută de Libri (el a arătat că pentru numere prime , condiția este suficientă ). [patru] $S<e\cdot (n!)$ $x^{n}+y^{n}\equiv z^{n}{\pmod {p}}$ $n$ $n$ $p>n^{4)$

Relația cu alte teoreme

Teorema lui Schur este foarte asemănătoare cu teorema lui van der Waerden pentru progresii de lungime 3 (deoarece o astfel de progresie este soluția ecuației ), totuși, spre deosebire de aceasta, nu permite o generalizare aditiv-combinatorie (care este teorema Roth ). pentru teorema lui van der Waerden ), deoarece mulțimea fără sumă în sine poate fi suficient de densă (de exemplu, mulțimea tuturor numerelor impare). $x+y=2z$

Vezi și

Teorema lui Folkman

Literatură

Par dl. G. Libri de Florence. Memoire sur la theorie des numes. (franceză) // Journal für die reine und angewandte Mathematik. - 1832. - Vol. 9 , livr. 2 . — P. 261-276 .
Domnul. LE Dickson. Despre congruență $x^{n}+y^{n}+z^{n}\equiv 0{\pmod {p}}$ (engleză) // Journal für die reine und angewandte Mathematik. - 1909. - Vol. 135 . - P. 134-141 .
I. Schur. Über die Kongruenz $x^{m}+y^{m}\equiv z^{m}{\pmod {p))$ (germană) // Jahresbericht der Deutschen Mathematiker-Vereinigung. - 1917. - Bd. 25 . - S. 114-117 .

Note

↑ Libri, 1832 .
^ Dickson, 1909 .
↑ Schur, 1917 .
↑ Schur, 1917 , p. 116, formula este menționată pe un rând separat la mijlocul ultimului paragraf. $M=m^{4}-6m^{3}+13m^{2}-6m+1$