Anar al contingut

Teorema de Hales–Jewett

De L'Enciclopèdia, la wikipedia en valencià
La teorema de Hales-Jewett és un resultat combinatori fonamental de la teoria de Ramsey que du el nom d'Alfred W. Hales i Robert I. Jewett.

En matemàtiques, la teorema de Hales-Jewett és un resultat combinatori fonamental de la teoria de Ramsey que du el nom d'Alfred W. Hales i Robert I. Jewett, en relació en el grau en que els objectes d'alta dimensió deuen exhibir necessàriament alguna estructura combinatòria; és impossible que tals objectes siguen "completament aleatoris".[1]

Un enunciat geomètric informal de la teorema és que per a qualsevol sancer positiu n i c hi ha un número H tal que si les celes d'una gaveta H -dimensional n × n × n ×... × n estan coloreadas en c colores, existix una fila, columna o certa diagonal (més detalls a continuació) de llongitut n les celes de la qual són del mateix color. En atres paraules, la generalisació de n -en-fila, multijugador i de dimensions superiors d'un joc de tic-tac-toe no pot terminar en empat, no importa cuán gran siga n, no importa quàntes persones c estan jugant, i no importa qué jugador jugue cada tanda, sempre que es jugue en un tauler de dimensió H suficientment alta. Per mig d'un argument de robo d'estratègia estàndar, es pot concloure que si dos jugadors s'alternen, llavors el primer jugador té una estratègia guanyadora quan H és suficientment gran, encara que no es coneix cap algoritme pràctic per a obtindre esta estratègia.

Més formalment, siga WnH el conjunt de paraules de llongitut H sobre un alfabet en n lletres; és dir, el conjunt de successions de {1, 2,..., n } de llongitut H. Este conjunt forma el hipercubo que és el tema de la teorema. Una paraula variable w (x) en WnH encara té llongitut H pero inclou un element especial x en lloc d'a lo manco una de les lletres que ho componen. Les paraules w (1), w (2),..., w ( n) obtingudes en reemplaçar totes les instàncies de l'element especial x en 1, 2,..., n, formen una llínea combinatòria en l'espai WnH; les llínees combinatòries corresponen a files, columnes i (algunes de les) diagonals del hipercubo. La teorema de Hales-Jewett establix que per a sancers positius n i c donats, existix un sancer positiu H, que depén de n i c, tal que per a qualsevol partició de WnH en c partixes, hi ha a lo manco una part que conté tota una llínea combinatòria.

Per eixemple, prenga n = 3, H = 2 i c = 2. El hipercubo WnH en este cas és solament el tauler estàndar de tic-tac-toe, en nou posicions:

11 12 13
21 22 23
31 32 33


Una llínea combinatòria típica seria la paraula 2x, que correspon a la llínea 21, 22, 23; una atra llínea combinatòria és 'xx, que és la llínea 11, 22, 33. (Tinga en conte que la llínea 13, 22, 31, encara que és una llínea vàlida per al tic-tac-toe, no es considera una llínea combinatòria). En este cas particular, la teorema de Hales-Jewett no s'aplica; és possible dividir el tauler de tic-tac-toe en dos conjunts, per eixemple, {11, 22, 23, 31} i {12, 13, 21, 32, 33}, cap dels quals conté una llínea combinatòria (i correspondria empat en el joc de tic-tac-toe). Per un atre costat, si aumentem H a, digam, 8 (de modo que el tauler ara siga de huit dimensions, en 38 = 6561 posicions), i dividir este tauler en dos conjunts (els "zeros" i "creus"), llavors un dels dos conjunts deu contindre una llínea combinatòria (és dir, no és possible empatar en esta variant de tic-tac-toe). Per a una prova, veja a continuació.

Prova de la teorema de Hales-Jewett (en un cas especial)

[editar | editar còdic]

Ara vàrem demostrar la teorema de Hales-Jewett en el cas especial n = 3, c = 2, H = 8 discutit anteriorment. L'idea és reduir esta tasca a la de provar versions més simples de la teorema de Hales-Jewett (en este cas particular, als casos n = 2, c = 2, H = 2 yn = 2, c = 6, H = 6). Es pot provar el cas general de la teorema de Hales-Jewett per métodos similars, usant inducció matemàtica.

Cada element del hipercubo W38 és una successió de huit números de l'1 al 3, per eixemple, 13211321 és un element del hipercubo. Estem assumint que este hipercubo està completament ple de "zeros" i "creus". Usarem una prova per contradicció i assumirem que ni el conjunt de zeros ni el conjunt de creus contenen una llínea combinatòria. Si fixem els primers sis elements de dita successió i deixem que els dos últims varien, obtenim una tauler de tic-tac-toe ordinari, per eixemple 132113 ?? dona tal tauler. Per a cada u d'estos taulers abcdef ??, considerem les posicions abcdef11, abcdef12, abcdef22. Cada u d'estos deu ser omplit en una "zero" o una "creu", pel principi de caseller dos d'ells deuen omplir-se en el mateix símbol. Ya que dos d'estes posicions són part d'una llínea combinatòria, el tercer element d'eixa llínea deu estar ocupat pel símbol opost (ya que assumim que cap llínea combinatòria té els tres elements plens en el mateix símbol). En atres paraules, per a cada elecció de abcdef (que es pot considerar com un element del hipercubo de sis dimensions W36), hi ha sis possibilitats (superpostes):

  1. abcdef11 i abcdef12 són zeros; abcdef13 és una creu.
  2. abcdef11 i abcdef22 són zeros; abcdef33 és una creu.
  3. abcdef12 i abcdef22 són zeros; abcdef32 és una creu.
  4. abcdef11 i abcdef12 són creus; abcdef13 no és res.
  5. abcdef11 i abcdef22 són creus; abcdef33 no és res.
  6. abcdef12 i abcdef22 són creus; abcdef32 no és res.

Per lo tant, podem dividir el hipercubo de sis dimensions W36 en sis classes, corresponents a cada una de les sis possibilitats anteriors. (Si un element abcdef obedix a múltiples possibilitats, podem elegir una arbitrariamente, per eixemple, elegint la més alta de la llista anterior).


Ara considere els sèt elements 111111, 111112, 111122, 111222, 112222, 122222, 222222 en W36. Segons el principi del caseller, dos d'estos elements deuen pertànyer a la mateixa classe. Supongam, per eixemple, que 111112 i 112222 pertanyen a la classe (5), per lo que 11111211, 11111222, 11222211, 11222222 són creus i 11111233, 11222233 són zeros. Pero ara considere la posició 11333233, que deu omplir-se en una creu o en un zero. Si s'ompli en una creu, llavors la llínea combinatòria 11xxx2xx s'ompli completament en creus, contradient la nostra hipòtesis. Si, en canvi, s'ompli en un zero, llavors la llínea combinatòria 11xxx233 s'ompli completament en zeros, contradient novament la nostra hipòtesis. De la mateixa manera, si atres dos dels sèt elements anteriors de W36 entren en la mateixa classe. Ya que tenim una contradicció en tots els casos, l'hipòtesis original deu ser falsa; per tant, deu existir a lo manco una llínea combinatòria que consistixca enterament en zeros o enterament en creus.

L'argument anterior va ser alguna cosa inútil; de fet, la mateixa teorema és vàlit per a H = 4.[2] Si s'estén l'argument anterior als valors generals de n i c, llavors H creixerà molt ràpit; inclús quan c = 2 (que correspon al tic-tac-toe de dos jugadors), la H donada per l'argument anterior creix tan ràpit com la funció de Ackermann. La primera cota recursiva primitiva es deu a Saharon Shelah,[3] i seguix sent la millor cota en general per al número de Hales-Jewett H = H(n, c).

Conexions en atres teoremes

[editar | editar còdic]

Observe que l'argument anterior també dona el següent corolari: si deixem que A siga el conjunt de tots els números de huit dígits els dígits dels quals són tots 1, 2, 3 (per lo tant, A conté números com 11333233), i coloreamos A en dos colors, llavors A conté a lo manco una progressió aritmètica de llongitut tres, tots els elements dels quals són del mateix color. Açò es deu simplement a que totes les llínees combinatòries que apareixen en la demostració anterior de la teorema de Hales-Jewett també formen progressions aritmètiques en notació decimal. Es pot utilisar una formulació més general d'este argument per a demostrar que la teorema de Hales-Jewett generalisa la teorema de van der Waerden. De fet, la teorema de Hales-Jewett és substancialment una teorema més forta.

Aixina com la teorema de van der Waerden té una versió de densitat més forta en el teorema de Szemerédi, la teorema de Hales-Jewett també té una versió de densitat. En esta versió reforçada de la teorema de Hales-Jewett, en lloc de colorear tot el hipercubo WnH en c colores, se li dona un subconjunt arbitrari A del hipercubo WnH en una densitat donada 0 < δ < 1. La teorema establix que si H és suficientment gran depenent de n i δ, llavors el conjunt A deu contindre necessàriament una llínea combinatòria completa.


La teorema de densitat de Hales-Jewett va ser provat originalment per Furstenberg i Katznelson usant la teoria ergòdica.[4] En 2009, el Proyecte Polymath va desenrollar una nova prova[5][6] de la teorema de densitat Hales-Jewett basada en idees a partir de la prova del teorema dels cantons.[7] Dodos, Kanellopoulos i Tyros varen donar una versió simplificada de la prova de Polymath.[8]

La teorema de Graham-Rothschild generalisa la teorema de Hales-Jewett en gavetes combinatòries de dimensions superiors.

Vore també

[editar | editar còdic]

Referències

[editar | editar còdic]
  1. ↑ Transactions of the American Mathematical Society.106(2)
    222–229.ISSN 0002-9947.doi:10.1090/S0002-9947-1963-0143712-1.Consultat el 2021-02-15.
  2. ↑ “The first nontrivial Hales-Jewett number is four” (2014). Ars Combinatòria 113: 385–390.
  3. ↑ Journal of the American Mathematical Society.1(3)
    683–697.ISSN 0894-0347.doi:10.1090/S0894-0347-1988-0929498-X.Consultat el 2021-02-15.
  4. ↑ Journal d’Analyse Mathématique.57(1)
    64–119.ISSN 1565-8538.doi:10.1007/BF03041066.Consultat el 2021-02-15.
  5. ↑ «A new proof of the density Hales-Jewett theorem» (en en).
  6. ↑ Gowers, W. T. (2010). An Irregular Mind: Szemerédi is 70 (en en), Springer, pp. 659–687. doi:10.1007/978-3-642-14444-8_21. ISBN 978-3-642-14444-8.
  7. ↑ “Sets of lattice points that form no squares” (1974). Stud. Sci. Math. Hungar. 9: 9–11.
  8. ↑ “A simple proof of the density Hales–Jewett theorem” (2014). Int. Math. Res. Not. IMRN 2014 (12): 3340–3352. doi:10.1093/imrn/rnt041.


Referències

[editar | editar còdic]


Obtingut de «https://www.lenciclopedia.org/w/index.php?title=Teorema_de_Hales–Jewett&oldid=827140»