Schur-tétel (Ramsey-elmélet)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. április 24-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

Schur tétele a Ramsey-elmélet állítása, miszerint a természetes számok véges számú színben történő színezésére létezik az egyenlet egyszínű megoldása . A szerzőről, Isai Shura -ról nevezték el . $x+y=z$

Eredet

Schur tétele egy olyan állítás bizonyításának eszközeként merült fel, amely triviálisan következne az akkor még nem bizonyított Fermat utolsó tételének tagadásából , nevezetesen az egyenletének a maradékgyűrűben való megoldhatóságának kérdésére adott válasz, kellően nagy prímmodulussal : tetszőleges prímekre , az egyenlet $n\ge 3$ $p>p_{0}=p_{0}(n)$

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

vannak nem nulla megoldások?

Az ilyen egyenleteket (és hasonlókat) Guglielmo Libri fontolgatta 1832-ben [1] , de csak 1909-ben Leonard Eugene Dixon kapta meg az első általános eredményt ebben a témában - megmutatta ennek az állításnak a helyességét minden prímszámra . [2] $n$

Dixon számelméleti módszerekkel járt el, de 1917-ben Schur kombinatorikus megközelítést alkalmazott a problémára, figyelembe véve egy gyűrű modulo prím felosztását olyan csoportokba, amelyek megfelelnek az egyik vagy másik maradék modulo diszkrét logaritmusának különböző értékeinek ( más szóval, multiplikatív alcsoportok cosetjeibe ). Ebben az esetben az összes változót primitív gyökkel megszorozva bármely lineáris egyenlet megoldását átvihetjük egyik osztályból a másikba (ha a szorzás előtt minden változó ugyanabba az osztályba tartozott, akkor egy ilyen „átvitel” után ugyanaz). Ennek köszönhetően a lineáris egyenletekre vonatkozó Ramsey-típusú állítás (csak egy partícióelem létezéséről, de nem az egyes halmazok tulajdonságairól) könnyen számelméleti állítássá válik (egy halmaz tulajdonságairól), hiszen a konfiguráció megléte a partíció egyik elemében azt jelenti, hogy az összes többi elemben is létezik. [3] $n$

Megfogalmazás

Ha , akkor ${\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}$

Mint a Ramsey-elmélet sok állítása, Schur tétele is megenged egy véges megfogalmazást. Ez azt jelenti, hogy fix esetén a feltételnek megfelelő minimum nem lehet tetszőlegesen nagy. $k$ $x,y$

Végső verzió

Mindenki számára létezik olyan, hogy ha , akkor $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}$

Bizonyítás

Szokásos a Schur-tételt a végső megfogalmazásban úgy bizonyítani , hogy figyelembe veszik a , azaz a 3-klikk (háromszögek) Ramsey-számait a színezés során . Ha egy szám színét jelenti valamilyen rögzített színezésben , akkor ha a teljes gráf éleit úgy színezzük ki, hogy az egyszínű háromszög létezése a kívánt egyszínű megoldás meglétét jelenti a partícióban $S=R(3,\pontok ,3)$ $k$ $c(n)$ $n$ $\{1,\dots ,S\}$ $K_{S}$ ${\overline {c}}(i,j)=c(|ij|)$ $\{1,\dots ,S\}$

Schur tételének első közzététele idején Ramsey tétele még nem volt ismert, de Schur olyan érveket állított fel az egyik partíciós osztályhoz tartozó számok különbségei mellett, amelyek teljesen hasonlóak voltak a Ramsey-féle általános bizonyításhoz. elmélet.

Egy ilyen bizonyíték becslést ad . A korábban vizsgált értékekre az egyenlet megoldhatóságának kérdésére vonatkoztatva rosszabbnak bizonyult, mint a Libri által kapott (megmutatta, hogy prímszámokhoz elegendő a feltétel ). [négy] $S<e\cdot (n!)$ $x^{n}+y^{n}\equiv z^{n}{\pmod {p))$ $n$ $n$ ${\displaystyle p>n^{4))$

Kapcsolat más tételekkel

Schur tétele nagyon hasonlít Van der Waerden 3 hosszúságú progressziókra vonatkozó tételére (mert egy ilyen haladás a ) egyenlet megoldása, azonban ettől eltérően nem tesz lehetővé additív-kombinatorikus általánosítást (ami a Roth-tétel van der Waerden tételére ), hiszen maga az összegmentes halmaz is kellően sűrű lehet (például az összes páratlan szám halmaza). $x+y=2z$

Lásd még

Folkman tétele

Irodalom

Par Mr. G. Libri de Firenze. Memoire sur la theorie des nombres. (francia) // Journal für die reine und angewandte Mathematik. - 1832. - Kt. 9 , livr. 2 . — P. 261-276 .
Úr. LE Dickson. On the congruence $x^{n}+y^{n}+z^{n}\equiv 0{\pmod {p}}$ (angol) // Journal für die reine und angewandte Mathematik. - 1909. - 1. köt. 135 . - P. 134-141 .
I. Schur. Über die Kongruenz $x^{m}+y^{m}\equiv z^{m}{\pmod {p))$ (német) // Jahresbericht der Deutschen Mathematiker-Vereinigung. - 1917. - Bd. 25 . - S. 114-117 .

Jegyzetek

↑ Libri, 1832 .
↑ Dickson, 1909 .
↑ Schur, 1917 .
↑ Schur, 1917 , p. 116, a képlet külön sorban szerepel az utolsó bekezdés közepén. $M=m^{4}-6m^{3}+13m^{2}-6m+1$