Schurin lause (Ramseyn teoria)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 24. huhtikuuta 2020 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Schurin lause on Ramseyn teorian väite, jonka mukaan luonnollisten lukujen värjäykseen äärellisessä määrässä värejä on yhtälön yksivärinen ratkaisu . Nimetty kirjoittajansa Isai Shuran mukaan . $x+y=z$

Origins

Schurin lause syntyi työkaluna todistaa yksi väite, joka seuraisi triviaalisti tuolloin todistamattoman Fermatin viimeisen lauseen negaatiosta , nimittäin vastauksen kysymykseen sen yhtälön ratkaistavuudesta jäännösrenkaassa riittävän suurella alkumoduulilla : for mikä tahansa alkuluvuille , yhtälö $n\ge 3$ $p>p_{0}=p_{0}(n)$

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

onko nollasta poikkeavia ratkaisuja?

Tällaisia yhtälöitä (ja vastaavia) tarkasteli Guglielmo Libri vuonna 1832 [1] , mutta vasta vuonna 1909 Leonard Eugene Dixon sai ensimmäisen yleistuloksen tästä aiheesta - hän osoitti tämän väitteen oikeellisuuden kaikille alkuluvuille . [2] $n$

Dixon toimi lukuteoreettisilla menetelmillä, mutta vuonna 1917 Schur sovelsi kombinatorista lähestymistapaa ongelmaan, koska se harkitsi renkaan modulo-alkuluvun jakamista jäännösluokkiin, jotka vastaavat yhden tai toisen jäännöksen moduulin diskreetin logaritmin eri arvoja ( toisin sanoen kertovien alaryhmien koseteihin ). Tässä tapauksessa kertomalla kaikki muuttujat primitiivijuurella voidaan "siirtää" minkä tahansa lineaarisen yhtälön ratkaisut luokasta toiseen (jos ennen kertomista kaikki muuttujat olivat samassa luokassa, niin tällaisen "siirron" jälkeen se on sama). Tämän ansiosta lineaariyhtälöitä koskeva Ramsey-tyyppinen lause (vain osioelementin olemassaolosta, mutta ei kunkin tietyn joukon ominaisuuksista) muuttuu helposti lukuteoreettiseksi lauseeksi (joukon ominaisuuksista), koska konfiguraation olemassaolo osion yhdessä elementissä edellyttää sen olemassaoloa kaikissa muissa elementeissä. [3] $n$

Sanamuoto

Jos , niin ${\mathbb {N} }={\mathcal {N}}_{1}\cup {\mathcal {N}}_{2}\cup \dots \cup {\mathcal {N}}_{ k}$ $\exists i,x,y:\ \left\lhaulu {x,y,x+y}\oikea\rhaulu \alajoukko {\mathcal {N}}_{i}$

Kuten monet Ramseyn teorian väitteet, Schurin lause sallii myös rajallisen muotoilun. Tämä tarkoittaa, että kiinteällä ehtoon sopivien vähimmäismäärä ei voi olla mielivaltaisen suuri. $k$ $x,y$

Viimeinen versio

Kaikille on olemassa sellainen, että jos , niin $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\lhaulu {x,y,x+y}\oikea\rhaulu \alajoukko {\mathcal {N}}_{i}$

Todiste

On tapana todistaa Schur-lause lopullisessa muotoilussa ottamalla huomioon , eli Ramsey-luvut 3-klikeille (kolmioille) väritettäessä . Jos tarkoittaa luvun väriä jossain kiinteässä värjäyksessä , niin kun värjätään täydellisen graafin reunat siten , että yksivärisen kolmion olemassaolo merkitsee halutun yksivärisen ratkaisun olemassaoloa osiossa $S=R(3,\pisteet ,3)$ $k$ $c(n)$ $n$ $\{1,\dots ,S\}$ $K_{S}$ ${\overline {c}}(i,j)=c(|ij|)$ $\{1,\dots ,S\}$

Kun Schurin lause julkaistiin ensimmäisen kerran , Ramseyn lause ei ollut vielä tiedossa, mutta Schur esitti argumentteja yhteen osioluokkaan kuuluvien lukujen eroista, jotka olivat täysin samanlaisia kuin Ramseyn yleisessä todistuksessa suoritetut argumentit. teoria.

Tällainen todiste antaa arvion . Aiemmin tarkasteltujen arvojen yhtälön ratkaistavuuden kysymykseen sovellettuina se osoittautui huonommaksi kuin Libri (hän osoitti, että alkuluvuille ehto riittää ). [neljä] $S<e\cdot (n!)$ $x^{n}+y^{n}\equiv z^{n}{\pmod {p}}$ $n$ $n$ ${\displaystyle p>n^{4))$

Suhde muihin lauseisiin

Schurin lause on hyvin samankaltainen kuin van der Waerdenin lause 3 pituisille progressioille (koska tällainen progressio on yhtälön ratkaisu ), mutta toisin kuin se, se ei salli additiivis-kombinatorista yleistystä (joka on Rothin lause van der Waerdenin lauseelle ), koska itse summaton joukko voi olla riittävän tiheä (esimerkiksi kaikkien parittomien lukujen joukko). $x+y=2z$

Katso myös

Folkmanin lause

Kirjallisuus

Par Mr. G. Libri de Florence. Muisto teoria des nombres. (ranska) // Journal für die reine und angewandte Mathematik. - 1832. - Voi. 9 , livr. 2 . — s. 261-276 .
Herra. LE Dickson. On the congruence $x^{n}+y^{n}+z^{n}\equiv 0{\pmod {p}}$ (englanniksi) // Journal für die reine und angewandte Mathematik. - 1909. - Voi. 135 . - s. 134-141 .
I. Schur. Über die Kongruenz $x^{m}+y^{m}\equiv z^{m}{\pmod {p}}$ (saksa) // Jahresbericht der Deutschen Mathematiker-Vereinigung. - 1917. - Bd. 25 . - S. 114-117 .

Muistiinpanot

↑ Libri, 1832 .
↑ Dickson, 1909 .
↑ Schur, 1917 .
↑ Schur, 1917 , s. 116, kaava mainitaan erillisellä rivillä viimeisen kappaleen keskellä. $M=m^{4}-6m^{3}+13m^{2}-6m+1$