Hales–Jewetts teorem

Inom matematiken är Hales -Jewett-satsen ett grundläggande kombinatoriskt resultat av Ramsey-teorin uppkallad efter Alfred W. Hales och Robert I. Jewett, angående i vilken grad högdimensionella objekt måste uppvisa någon kombinatorisk struktur; det är omöjligt för sådana föremål att vara "helt slumpmässiga".

Ett informellt geometriskt uttalande av satsen är att det för alla positiva heltal n och c finns ett tal H så att om cellerna i en H -dimensionell n × n × n ×...× n kub färgas med c -färger måste vara en rad, kolumn eller viss diagonal (mer information nedan) med längd n vars alla celler har samma färg. Med andra ord kan den högre dimensionella, multi-player, n -i-rad-generaliseringen av ett spel med tic-tac-toe inte sluta oavgjort, oavsett hur stort n är, oavsett hur många personer c är spelar, och oavsett vilken spelare som spelar varje tur, förutsatt att den spelas på en bräda med tillräckligt hög dimension H . Genom ett standardstrategistöldargument kan man alltså dra slutsatsen att om två spelare alternerar, så har den första spelaren en vinnande strategi när H är tillräckligt stor, även om ingen praktisk algoritm för att erhålla denna strategi är känd.

Formellt uttalande

Kombinatorisk linje i en kub

Låt W
H n vara uppsättningen av ord med längden H över ett alfabet med n bokstäver; det vill säga uppsättningen av sekvenser av {1, 2, ..., n } av längden H . Denna mängd bildar hyperkuben som är föremål för satsen. Ett variabelt ord w ( x ) över W
H n har fortfarande längden H men inkluderar specialelementet x i stället för minst en av bokstäverna. Orden w (1), w (2), ..., w ( n ) som erhålls genom att ersätta alla instanser av specialelementet x med 1, 2, ..., n , bildar en kombinatorisk linje i rymden W
H n ; kombinatoriska linjer motsvarar rader, kolumner och (några av) diagonalerna i hyperkuben . Hales–Jewett-satsen säger sedan att för givna positiva heltal n och c finns det ett positivt heltal H , beroende på n och c , så att för varje uppdelning av W
H n i c -delar finns det åtminstone en del som innehåller en hel kombinatorisk linje.

Ta till exempel n = 3, H = 2 och c = 2. Hyperkuben W
H n i det här fallet är bara den vanliga tick-tac-toe- brädan med nio positioner:

11 12 13
21 22 23
31 32 33

En typisk kombinatorisk linje skulle vara ordet 2x, vilket motsvarar raden 21, 22, 23; en annan kombinatorisk linje är xx, vilket är raden 11, 22, 33. (Observera att raden 13, 22, 31, även om den är en giltig linje för spelet tic-tac- toe , inte anses vara en kombinatorisk linje.) I detta särskilt fall gäller inte Hales–Jewett-satsen; det är möjligt att dela upp tic-tac-toe- brädan i två uppsättningar, t.ex. {11, 22, 23, 31} och {12, 13, 21, 32, 33}, som ingen av dem innehåller en kombinatorisk linje (och skulle motsvara till oavgjort i spelet tic-tac-toe ). Å andra sidan, om vi ökar H till, säg, 8 (så att brädet nu är åttadimensionellt, med 3 8 = 6561 positioner), och delar upp denna bräda i två uppsättningar ("nollorna" och "korsen") , då måste en av de två uppsättningarna innehålla en kombinatorisk linje (dvs inget drag är möjligt i denna variant av tic-tac-toe ) . För ett bevis, se nedan.

Bevis för Hales–Jewetts teorem (i ett specialfall)

Vi bevisar nu Hales–Jewett-satsen i specialfallet n = 3, c = 2, H = 8 som diskuterats ovan. Tanken är att reducera denna uppgift till att bevisa enklare versioner av Hales–Jewett-satsen (i detta specifika fall till fallen n = 2, c = 2, H = 2 och n = 2, c = 6, H = 6). Man kan bevisa det allmänna fallet med Hales-Jewett-satsen med liknande metoder, med hjälp av matematisk induktion .

Varje element i hyperkuben W
8 3 är en sträng med åtta siffror från 1 till 3, t.ex. 13211321 är ett element i hyperkuben. Vi antar att denna hyperkub är helt fylld med "nollor" och "korsar". Vi ska använda ett motsägelsebevis och anta att varken uppsättningen av noller eller uppsättningen av kors innehåller en kombinatorisk linje. Om vi ​​fixar de första sex delarna av en sådan sträng och låter de två sista variera, får vi en vanlig tick-tac-toe- bräda, till exempel "132113??" ger en sådan tavla. För varje sådan styrelse "abcdef??", betraktar vi positionerna "abcdef11", "abcdef12", "abcdef22". Var och en av dessa måste fyllas med antingen en noll eller ett kors, så enligt duvhålsprincipen måste två av dem fyllas med samma symbol. Eftersom två av dessa positioner är en del av en kombinatorisk linje, måste det tredje elementet i den raden upptas av den motsatta symbolen (eftersom vi antar att ingen kombinatorisk linje har alla tre elementen fyllda med samma symbol). Med andra ord, för varje val av "abcdef" (som kan ses som ett element i den sexdimensionella hyperkuben W
6 3 ), finns det sex (överlappande) möjligheter:

  1. abcdef11 och abcdef12 är nollor; abcdef13 är ett kors.
  2. abcdef11 och abcdef22 är nollor; abcdef33 är ett kors.
  3. abcdef12 och abcdef22 är nollor; abcdef32 är ett kors.
  4. abcdef11 och abcdef12 är korsningar; abcdef13 är en noll.
  5. abcdef11 och abcdef22 är korsningar; abcdef33 är en noll.
  6. abcdef12 och abcdef22 är korsningar; abcdef32 är en noll.

Således kan vi dela upp den sexdimensionella hyperkuben W
6 3 i sex klasser, motsvarande var och en av ovanstående sex möjligheter. (Om ett element abcdef följer flera möjligheter, kan vi välja en godtyckligt, t.ex. genom att välja den högsta på listan ovan).

Betrakta nu de sju elementen 111111, 111112, 111122, 111222, 112222, 122222, 222222 i W
6 3 . Enligt duvhålsprincipen måste två av dessa element falla i samma klass. Anta att till exempel 111112 och 112222 faller i klass (5), så är 11111211, 11111222, 11222211, 11222222 kors och 11111233, 11222233 är nolls. Men överväg nu positionen 11333233, som måste fyllas med antingen ett kryss eller ett nolla. Om den är fylld med ett kors, så är den kombinatoriska linjen 11xxx2xx helt fylld med kors, vilket motsäger vår hypotes. Om den istället är fylld med noll, så är den kombinatoriska raden 11xxx233 helt fylld med nollor, vilket återigen motsäger vår hypotes. På samma sätt om några andra två av ovanstående sju element i W
6 3 faller i samma klass. Eftersom vi har en motsägelse i alla fall måste den ursprungliga hypotesen vara falsk; sålunda måste det finnas åtminstone en kombinatorisk linje som helt består av nollor eller helt av korsningar.

Ovanstående argument var något slösaktigt; i själva verket gäller samma sats för H = 4. Om man utvidgar ovanstående argument till allmänna värden på n och c , kommer H att växa mycket snabbt; även när c = 2 (vilket motsvarar två spelare tic-tac-toe ) växer H som ges av ovanstående argument lika snabbt som Ackermann-funktionen . Den första primitiva rekursiva gränsen beror på Saharon Shelah och är fortfarande den mest kända bunden i allmänhet för Hales–Jewett-talet H = H ( n , c ).

Samband med andra teorem

Observera att ovanstående argument också ger följande följd: om vi låter A vara mängden av alla åttasiffriga tal vars siffror alla är antingen 1, 2, 3 (sålunda innehåller A siffror som 11333233), och vi färgar A med två färger, då innehåller A minst en aritmetisk progression av längd tre, vars alla element har samma färg. Detta beror helt enkelt på att alla de kombinatoriska linjerna som förekommer i ovanstående bevis på Hales–Jewett-satsen också bildar aritmetiska progressioner i decimalnotation . En mer allmän formulering av detta argument kan användas för att visa att Hales–Jewett-satsen generaliserar van der Waerdens sats . I själva verket är Hales-Jewett-satsen väsentligt en starkare sats.

Precis som van der Waerdens sats har en starkare densitetsversion i Szemerédis sats , har Hales–Jewetts sats också en densitetsversion. I denna förstärkta version av Hales–Jewett-satsen får man istället för att färga hela hyperkuben W
H n till c -färger en godtycklig delmängd A av hyperkuben W
H n med någon given densitet 0 < δ < 1. Satsen anger att om H är tillräckligt stor beroende på n och δ, så måste mängden A nödvändigtvis innehålla en hel kombinatorisk linje.

Densitet Hales–Jewett-satsen bevisades ursprungligen av Furstenberg och Katznelson med hjälp av ergodisk teori . 2009 Polymath Project ett nytt bevis på Hales–Jewetts densitetssats baserat på idéer från proof of the corners-satsen . Dodos, Kanellopoulos och Tyros gav en förenklad version av Polymath-beviset.

Hales-Jewett generaliseras av Graham-Rothschild-satsen , på högre dimensionella kombinatoriska kuber .

Se även

  1. ^   Hales, Alfred W.; Jewett, Robert I. (1963). "Regularitets- och positionsspel" . Trans. Amer. Matematik. Soc. 106 (2): 222–229. doi : 10.1090/S0002-9947-1963-0143712-1 . MR 0143712 .
  2. ^   Hindman, Neil; Tressler, Eric (2014). "Det första icke-triviala Hales-Jewett-numret är fyra" (PDF) . Ars Combinatoria . 113 : 385-390. MR 3186481 .
  3. ^    Shelah, Saharon (1988). "Primitiva rekursiva gränser för van der Waerden-tal" . J. Amer. Matematik. Soc. 1 (3): 683-697. doi : 10.2307/1990952 . JSTOR 1990952 . MR 0929498 .
  4. ^    Furstenberg, Hillel ; Katznelson, Yitzhak (1991). "En densitetsversion av Hales-Jewett-satsen" . Journal d'Analyse Mathématique . 57 (1): 64–119. doi : 10.1007/BF03041066 . MR 1191743 . S2CID 123036744 .
  5. ^   DHJ Polymath (2012). "Ett nytt bevis på Hales–Jewetts densitetssats" . Annals of Mathematics . 175 (3): 1283–1327. doi : 10.4007/annals.2012.175.3.6 . MR 2912706 .
  6. ^    Gowers, William Timothy (2010). "Polymat och densitet Hales-Jewett teorem". I Bárány, Imre; Solymosi, József (red.). Ett oregelbundet sinne . Bolyai Society Mathematical Studies. Vol. 21. Budapest: János Bolyai Mathematical Society. s. 659–687. doi : 10.1007/978-3-642-14444-8_21 . ISBN 978-963-9453-14-2 . MR 2815619 .
  7. ^   Ajtai, Miklós; Szemerédi, Endre (1974). "Uppsättningar av gitterpunkter som inte bildar rutor". Hingst. Sci. Matematik. Ungern . 9 :9–11. MR 0369299 .
  8. ^   Dodos, Pandelis; Kanellopoulos, Vassilis; Tyros, Konstantinos (2014). "Ett enkelt bevis på Hales–Jewetts densitetssats". Int. Matematik. Res. Inte. IMRN . 2014 (12): 3340–3352. arXiv : 1209.4986 . doi : 10.1093/imrn/rnt041 . MR 3217664 .

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Hales–Jewett_theorem&oldid=1140136736 "