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 , relativa al grado en que los objetos de alta dimensión deben necesariamente exhibir alguna estructura combinatoria; es imposible que tales objetos sean "completamente aleatorios". [1]
Una declaración geométrica informal del teorema es que para cualquier número 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 sean del mismo color. En otras palabras, suponiendo que n y c sean fijos, la generalización de dimensiones superiores, multijugador y n en fila de un juego de tres en raya con c jugadores no puede terminar en empate, sin importar cuán grande sea. n es, sin importar cuántas personas c estén jugando, y sin importar qué jugador juegue cada turno, siempre que se juegue en un tablero de dimensión H suficientemente alta . Mediante un argumento estándar de robo de estrategia , 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.
Sea Wh
norteser el conjunto de palabras de longitud H sobre un alfabeto de n letras; es decir, el conjunto de secuencias de {1, 2,..., n } de longitud H. Este conjunto forma el hipercubo que es el tema del teorema. Una palabra variable w ( x ) sobre Wh
nortetodavía tiene 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 reemplazando todas las instancias del elemento especial x con 1, 2, ..., n , forman una línea combinatoria en el espacio W.h
norte; Las líneas combinatorias corresponden a filas, columnas y (algunas de las) diagonales del hipercubo . El teorema de Hales-Jewett establece entonces que para números enteros positivos n y c dados , existe un entero positivo H , dependiendo de n y c , tal que para cualquier partición de Wh
norteen 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
norteen este caso es sólo el tablero estándar de tres en raya , con nueve posiciones:
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, si bien es una línea válida para el juego tres en raya , no se considera una línea combinatoria). En caso particular, el teorema de Hales-Jewett no se aplica; es posible dividir el tablero de tres en raya 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 al empate en el juego de tres en raya ). Por otro lado, si aumentamos H a, digamos, 8 (de modo que el tablero ahora tiene ocho dimensiones, con 3 8 = 6561 posiciones) y dividimos este tablero en dos conjuntos (los "ceros" y las "cruces") , entonces uno de los dos conjuntos debe contener una línea combinatoria (es decir, en esta variante del tres en raya no es posible dibujar ). Para una prueba, vea a continuación.
Ahora demostramos el teorema de Hales-Jewett en el caso especial n = 3, c = 2, H = 8 analizado anteriormente. La idea es reducir esta tarea a la de demostrar versiones más simples del teorema de Hales-Jewett (en este caso particular, a los casos n = 2, c = 2, H = 2 y n = 2, c = 6, H = 6). Se puede demostrar el caso general del teorema de Hales-Jewett mediante métodos similares, utilizando la 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 supondremos que ni el conjunto de ceros ni el conjunto de cruces contienen una línea combinatoria. Si fijamos los primeros seis elementos de dicha cadena y dejamos que los dos últimos varíen, obtenemos un tablero de tres en raya ordinario , por ejemplo "132113??" da tal tablero. Para cada tablero "abcdef??", consideramos las posiciones "abcdef11", "abcdef12", "abcdef22". Cada uno de ellos debe llenarse con un cero o 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 suponemos que ninguna línea combinatoria tiene los tres elementos llenos 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):
Así podemos dividir el hipercubo de seis dimensiones W.6
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 W.6
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 considere ahora la posición 11333233, que debe llenarse con una cruz o un cero. Si se llena con una cruz, entonces la línea combinatoria 11xxx2xx se llena completamente con cruces, lo que contradice 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
3caer en la misma clase. Como 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 compuesta enteramente de ceros o enteramente de cruces.
El argumento anterior fue un tanto inútil; de hecho, el mismo teorema se cumple para H = 4. [2] Si se extiende el argumento anterior a valores generales de n y c , entonces H crecerá muy rápidamente; incluso cuando c = 2 (que corresponde al tres en raya 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 ).
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 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 prueba 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
norteen c colores, se le da un subconjunto arbitrario A del hipercubo Wh
nortecon una densidad dada 0 < δ < 1. El teorema establece que si H es suficientemente grande dependiendo de n y δ, entonces el conjunto A debe contener necesariamente una línea combinatoria completa.
El teorema de densidad de Hales-Jewett fue demostrado originalmente por Furstenberg y Katznelson utilizando la teoría ergódica . [4] En 2009, el Proyecto Polymath desarrolló una nueva prueba [5] [6] del teorema de densidad de Hales-Jewett basada en ideas 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 Hales-Jewett se generaliza mediante el teorema de Graham-Rothschild , en cubos combinatorios de dimensiones superiores .