En matemáticas , el teorema de Hales-Jewett es un resultado combinatorio fundamental de la teoría de Ramsey que lleva el nombre de Alfred W. Hales y Robert I. Jewett, en relación con el grado en que los objetos de alta dimensión deben exhibir necesariamente alguna estructura combinatoria; es imposible que tales objetos sean "completamente aleatorios". [1]
Un enunciado geométrico informal del teorema es que para cualquier entero positivo n y c hay un número H tal que si las celdas de un cubo H -dimensional n × n × n × ... × n están coloreadas con c colores, hay debe ser una fila, columna o cierta diagonal (más detalles a continuación) de longitud n todas cuyas celdas son del mismo color. En otras palabras, la generalización de n -en-fila , multijugador, de mayor dimensión de un juego de tic-tac-toe no puede terminar en empate, no importa cuán grande sea n , no importa cuántas personasc están jugando, y no importa qué jugador juegue cada turno, siempre que se juegue en un tablero de dimensión H suficientemente alta . Mediante un argumento de robo de estrategia estándar , se puede concluir que si dos jugadores se alternan, entonces el primer jugador tiene una estrategia ganadora cuando H es suficientemente grande, aunque no se conoce ningún algoritmo práctico para obtener esta estrategia.
Más formalmente, dejemos que WH
nser el conjunto de palabras de longitud H sobre un alfabeto de n letras; es decir, el conjunto de secuencias de {1, 2, ..., n } de la longitud H . Este conjunto forma el hipercubo que es el tema del teorema. Una palabra variable w ( x ) sobre WH
ntodavía tiene la longitud H pero incluye el elemento especial x en lugar de al menos una de las letras. Las palabras w (1), w (2), ..., w ( n ) obtenidas al reemplazar todas las instancias del elemento especial x con 1, 2, ..., n , forman una línea combinatoria en el espacio WH
n; Las líneas combinatorias corresponden a filas, columnas y (algunas de las) diagonales del hipercubo . El teorema de Hales-Jewett establece que para los enteros positivos n y c dados , existe un entero positivo H , que depende de n y c , de modo que para cualquier partición de WH
nen c partes, hay al menos una parte que contiene una línea combinatoria completa.
Por ejemplo, tome n = 3, H = 2 y c = 2. El hipercubo WH
nen este caso es solo la tabla estándar de tic-tac-toe , con nueve posiciones:
11 | 12 | 13 |
21 | 22 | 23 |
31 | 32 | 33 |
Una línea combinatoria típica sería la palabra 2x, que corresponde a la línea 21, 22, 23; otra línea combinatoria es xx, que es la línea 11, 22, 33. (Tenga en cuenta que la línea 13, 22, 31, aunque es una línea válida para el juego tic-tac-toe , no se considera una línea combinatoria). caso particular, el teorema de Hales-Jewett no se aplica; es posible dividir el tablero de tic-tac-toe en dos conjuntos, por ejemplo, {11, 22, 23, 31} y {12, 13, 21, 32, 33}, ninguno de los cuales contiene una línea combinatoria (y correspondería empate en el juego de tic-tac-toe ). Por otro lado, si aumentamos H a, digamos, 8 (de modo que el tablero ahora sea de ocho dimensiones, con 3 8 = 6561 posiciones), y dividimos este tablero en dos conjuntos (los "ceros" y "cruces") , entonces uno de los dos conjuntos debe contener una línea combinatoria (es decir, no es posible dibujar en esta variante de tic-tac-toe ). Para obtener una prueba, consulte a continuación.
Prueba del teorema de Hales-Jewett (en un caso especial)
Ahora demostramos el teorema de Hales-Jewett en el caso especial n = 3, c = 2, H = 8 discutido anteriormente. La idea es reducir esta tarea a la de probar versiones más simples del teorema de Hales-Jewett (en este caso particular, a los casos n = 2, c = 2, H = 2 yn = 2, c = 6, H = 6). Se puede probar el caso general del teorema de Hales-Jewett por métodos similares, usando inducción matemática .
Cada elemento del hipercubo W8
3es una cadena de ocho números del 1 al 3, por ejemplo, 13211321 es un elemento del hipercubo . Suponemos que este hipercubo está completamente lleno de "ceros" y "cruces". Usaremos una prueba por contradicción y asumiremos que ni el conjunto de ceros ni el conjunto de cruces contienen una línea combinatoria. Si arreglamos los primeros seis elementos de dicha cadena y dejamos que los dos últimos varíen, obtenemos una tabla de tic-tac-toe ordinaria , por ejemplo 132113 ?? da tal tablero. Para cada uno de estos tableros abcdef ??, consideramos las posiciones abcdef11, abcdef12, abcdef22. Cada uno de estos debe llenarse con un nulo o con una cruz, por lo que, según el principio del casillero, dos de ellos deben llenarse con el mismo símbolo. Dado que dos de estas posiciones son parte de una línea combinatoria, el tercer elemento de esa línea debe estar ocupado por el símbolo opuesto (ya que asumimos que ninguna línea combinatoria tiene los tres elementos rellenos con el mismo símbolo). En otras palabras, para cada elección de abcdef (que puede considerarse como un elemento del hipercubo de seis dimensiones W6
3), hay seis posibilidades (superpuestas):
- abcdef11 y abcdef12 son ceros; abcdef13 es una cruz.
- abcdef11 y abcdef22 son ceros; abcdef33 es una cruz.
- abcdef12 y abcdef22 son ceros; abcdef32 es una cruz.
- abcdef11 y abcdef12 son cruces; abcdef13 no es nada.
- abcdef11 y abcdef22 son cruces; abcdef33 no es nada.
- abcdef12 y abcdef22 son cruces; abcdef32 no es nada.
Así podemos dividir el hipercubo de seis dimensiones W6
3en seis clases, correspondientes a cada una de las seis posibilidades anteriores. (Si un elemento abcdef obedece a múltiples posibilidades, podemos elegir una arbitrariamente, por ejemplo, eligiendo la más alta de la lista anterior).
Ahora considere los siete elementos 111111, 111112, 111122, 111222, 112222, 122222, 222222 en W6
3. Según el principio del casillero , dos de estos elementos deben pertenecer a la misma clase. Supongamos, por ejemplo, que 111112 y 112222 pertenecen a la clase (5), por lo que 11111211, 11111222, 11222211, 11222222 son cruces y 11111233, 11222233 son ceros. Pero ahora considere la posición 11333233, que debe llenarse con una cruz o con un cero. Si se llena con una cruz, entonces la línea combinatoria 11xxx2xx se llena completamente con cruces, contradiciendo nuestra hipótesis. Si, en cambio, se llena con un cero, entonces la línea combinatoria 11xxx233 se llena completamente con ceros, contradiciendo nuevamente nuestra hipótesis. De manera similar, si otros dos de los siete elementos anteriores de W6
3caen en la misma clase. Dado que tenemos una contradicción en todos los casos, la hipótesis original debe ser falsa; por tanto, debe existir al menos una línea combinatoria que consista enteramente en ceros o enteramente en cruces.
El argumento anterior fue algo inútil; de hecho, el mismo teorema es válido para H = 4. [2] Si se extiende el argumento anterior a los valores generales de n y c , entonces H crecerá muy rápido; incluso cuando c = 2 (que corresponde al tic-tac-toe de dos jugadores ) la H dada por el argumento anterior crece tan rápido como la función de Ackermann . El primer límite recursivo primitivo se debe a Saharon Shelah , [3] y sigue siendo el límite más conocido en general para el número de Hales-Jewett H = H ( n , c ).
Conexiones con otros teoremas
Observe que el argumento anterior también da el siguiente corolario: si dejamos que A sea el conjunto de todos los números de ocho dígitos cuyos dígitos son todos 1, 2, 3 (por lo tanto, A contiene números como 11333233), y coloreamos A con dos colores, entonces A contiene al menos una progresión aritmética de longitud tres, todos cuyos elementos son del mismo color. Esto se debe simplemente a que todas las líneas combinatorias que aparecen en la demostración anterior del teorema de Hales-Jewett también forman progresiones aritméticas en notación decimal . Se puede utilizar una formulación más general de este argumento para demostrar que el teorema de Hales-Jewett generaliza el teorema de van der Waerden . De hecho, el teorema de Hales-Jewett es sustancialmente un teorema más fuerte.
Así como el teorema de van der Waerden tiene una versión de densidad más fuerte en el teorema de Szemerédi, el teorema de Hales-Jewett también tiene una versión de densidad. En esta versión reforzada del teorema de Hales-Jewett, en lugar de colorear todo el hipercubo WH
nen c colores, a uno se le da un subconjunto arbitrario A del hipercubo WH
ncon alguna densidad dada 0 <δ <1. El teorema establece que si H es suficientemente grande dependiendo de ny δ, entonces el conjunto A debe contener necesariamente una línea combinatoria completa.
El teorema de densidad de Hales-Jewett fue probado originalmente por Furstenberg y Katznelson usando la teoría ergódica . [4] En 2009, el Proyecto Polymath desarrolló una nueva prueba [5] [6] del teorema de densidad Hales-Jewett basada en ideas a partir de la prueba del teorema de las esquinas . [7] Dodos, Kanellopoulos y Tyros dieron una versión simplificada de la prueba de Polymath. [8]
El teorema de Graham-Rothschild generaliza el Hales-Jewett en cubos combinatorios de dimensiones superiores .
Ver también
Referencias
- ^ Hales, Alfred W .; Jewett, Robert I. (1963). "Regularidad y juegos posicionales" . Trans. Amer. Matemáticas. Soc. 106 (2): 222–229. doi : 10.1090 / S0002-9947-1963-0143712-1 . Señor 0143712 .
- ^ Hindman, Neil; Tressler, Eric (2014). "El primer número de Hales-Jewett no trivial es cuatro" (PDF) . Ars Combinatoria . 113 : 385–390. Señor 3186481 .
- ^ Shelah, Saharon (1988). "Límites recursivos primitivos para números de van der Waerden" . J. Amer. Matemáticas. Soc. 1 (3): 683–697. doi : 10.2307 / 1990952 . JSTOR 1990952 . Señor 0929498 .
- ^ Furstenberg, Hillel ; Katznelson, Yitzhak (1991). "Una versión de densidad del teorema de Hales-Jewett". Journal d'Analyse Mathématique . 57 (1): 64-119. doi : 10.1007 / BF03041066 . Señor 1191743 .
- ^ DHJ Polymath (2012). "Una nueva prueba del teorema de densidad Hales-Jewett" . Annals of Mathematics . 175 (3): 1283-1327. doi : 10.4007 / annals.2012.175.3.6 . Señor 2912706 .
- ^ Gowers, William Timothy (2010). "Polymath y el teorema de densidad Hales-Jewett". En Bárány, Imre; Solymosi, József (eds.). Mente irregular . Estudios Matemáticos de la Sociedad Bolyai. 21 . Budapest: Sociedad Matemática János Bolyai. págs. 659–687. doi : 10.1007 / 978-3-642-14444-8_21 . ISBN 978-963-9453-14-2. Señor 2815619 .
- ^ Ajtai, Miklós; Szemerédi, Endre (1974). "Conjuntos de puntos de celosía que no forman cuadrados". Semental. Sci. Matemáticas. Hungar . 9 : 9-11. Señor 0369299 .
- ^ Dodos, Pandelis; Kanellopoulos, Vassilis; Tyros, Konstantinos (2014). "Una prueba simple del teorema de densidad Hales-Jewett". En t. Matemáticas. Res. No. IMRN . 2014 (12): 3340–3352. arXiv : 1209.4986 . doi : 10.1093 / imrn / rnt041 . Señor 3217664 .
enlaces externos
- Prueba completa de HJT - comienza en la diapositiva 57
- Artículo de Science News sobre la prueba colaborativa del teorema de densidad de Hales-Jewett
- Una publicación de blog de Steven Landsburg que analiza cómo se mejoró la prueba de este teorema de manera colaborativa en un blog