Search

Conjuntos tapas: matemáticas a velocidad de internet

Autor
Categoría
Tecnología
Fecha de Publicación
2016/12/06
7 more properties
Para quien no tenga conocimiento del tema, la matemática puede parecer jeroglíficos. Incluso peor: alguien podría imaginarse que sólo se trata de hacer multiplicaciones mentales de números cada vez más grandes o poder calcular el vuelto del pan. ¡Cuán lejos está esto de la realidad! Nos abogamos hoy a discutir una de estas ideas fijas: ¿Es la matemática inaccesible? ¿Está todo descubierto en matemáticas?
Para discutir este punto, mostramos un problema que no necesita introducción muy aparatosa: todo se puede reducir a un juego de cartas bastante simple. Sorprendentemente, este problema estuvo sin resolver por muchos años y la solución llegó hace poco, de una manera totalmente inesperada y muy simple para los estándares matemáticos.
Veremos hoy la historia de los «conjuntos tapa».

Juguemos un juego

Tenemos una baraja de cartas y tenemos 4 características diferentes: número, forma, color y achurado (a rayas). Cada una de estas características puede tomar 3 valores distintos:
•
Número: uno, dos o tres.
•
Forma: círculo, cuadrado o triángulo.
•
Color: rojo, azul o verde.
•
Relleno: vacío, a rayas o sólido.
Cada carta toma uno de los valores para cada característica. Por ejemplo, una carta puede mostrar dos círculos rojos sólidos o un triángulo azul a rayas. Como cada carta puede tomar 3 valores posibles en cada una de 4 características, hay un total de 34 = 81 cartas distintas en la baraja.
Las 81 cartas de nuestro juego.
Un trío es una colección de tres cartas donde, para cada característica, aparecen todos los valores posibles o aparece sólo uno. No importa el orden en que aparezcan. Un ejemplo de trío es el siguiente:
Tres cartas que forman un trío.
pues aparecen todos los números (uno, dos, tres), sólo una forma (cuadrado), todos los colores (rojo, azul, verde) y un sólo relleno (sólido). Por lo tanto, esta colección de cartas es un trío. Por el contrario, las siguientes tres cartas no forman un trío:
Tres cartas que no forman un trío.
pues aparecen sólo dos formas (cuadrado y triángulo). Necesitamos que la condición se cumpla para las cuatro características.
El juego es el siguiente: yo soy el repartidor, usted y sus amigos o amigas están sentados en una mesa. Voy poniendo cartas boca arriba sobre la mesa, una por una. Apenas alguien vea una colección de cartas que forma un trío, debe gritar «¡trío!» y se junta con dos personas más a tener sexo grupal y se lleva las tres cartas. Pongo cartas en la mesa hasta rellenar 12 cartas en total y doy tiempo para pensar. Si nadie ve un trío, voy poniendo más cartas si es necesario. El juego termina cuando la baraja se acabó y no quedan más tríos en las cartas que están en la mesa. Quien se quedó con más cartas, gana.
Pues este juego existe, de verdad, en una versión con copyright estadounidense y se llama Set. Para ilustrarlo, usamos una versión artesanal y así evitamos demandas.
La pregunta que se hicieron los matemáticos es la siguiente: ¿cuál es la mayor cantidad de cartas que puede haber boca arriba en la mesa sin que haya ningún trío? Una colección de cartas de este tipo se llama un conjunto tapa (porque uno quiere buscar tríos y te hace ¡tapa! (en inglés les dicen cap sets)). ¿Qué tamaño tiene el conjunto tapa más grande?

El problema no es problema

Bueno, para el juego que acabamos de describir, la respuesta es 20. Esto significa que existe un conjunto de 20 cartas que no forma ningún trío, y todo conjunto de 21 cartas obligatoriamente va a contener al menos un trío.
A continuación mostramos un ejemplo de un conjunto tapa. Usted puede comprobar que no se puede formar ningún trío con las cartas mostradas.
Un conjunto tapa.
Además, si se agregase cualquier otra carta a esta colección, necesariamente se va a formar un trío.
La pregunta se pone más interesante cuando generalizamos a un número arbitrario de características. Digamos que tenemos el mismo juego de cartas pero ahora tengo n características (color, número, forma, achurado, transparencia, posición, etc… Doscientas, cien, las que querái). Cada característica sigue teniendo 3 valores posibles y los tríos se definen de la misma forma: una colección de 3 cartas donde, para cada característica, aparecen los tres valores distintos, o sólo un valor.
Una colección de cartas de este tipo tiene tamaño 3n. Un conjunto tapa se define de la misma forma: un conjunto de cartas de tamaño máximo que no forma ningún trío. ¿Qué tamaño tiene un conjunto tapa que es lo más grande posible?
Usando un computador, pudieron calcular cuánto vale el tamaño del conjunto tapa más grande cuando tengo desde 1 hasta 6 características. Los primeros cinco valores son (1):
¿Puede completar la sexta fila de la tabla? Inténtelo. Puede que el problema se vuelva un poco aparatoso si quiere hacerlo a mano, pero la idea es usar la intuición. Si tengo 6 características en total, el número total de cartas en la baraja es 726. ¿Cuán grande puede ser el conjunto tapa en este caso? ¿Qué cree usted? ¿Existe algún patrón que pueda deducirse mirando los valores anteriores de la tabla? ¿Alguna estimación, al menos?
¿Pudo adivinar el sexto valor?
Nosotros tampoco.
La respuesta es 112.
Podemos notar que el valor del conjunto tapa más grande es relativamente chico en comparación al total de cartas que tenemos. Por ejemplo, cuando hay 6 características diferentes, hay un total de 729 cartas, pero el conjunto tapa más grande tiene tamaño 112, alrededor de sólo un 15% del total de cartas.
¿Qué tan grande puede ser el conjunto tapa? Es relativamente fácil encontrar un conjunto tapa de tamaño 2n. En cada característica elijo dos atributos y me quedo sólo con las cartas que muestren esos. Por ejemplo, en el juego presentado anteriormente, puedo seleccionar sólo con las cartas que tengan círculos y cuadrados, de color rojo y azul, uno o dos figuras, vacías o sólidas. Eso me da 24 = 16 cartas y es imposible encontrar un trío con éstas.
Giussepe Pellegrino, en 1971, fue el primero en descubrir que se podía hacer mejor que 16 cartas: él encontró el conjunto de 20 cartas que sirven en el caso anterior (2). El mejor caso general fue encontrado por Yves Edel en 2004 (3), quien pudo construir conjuntos tapa de tamaño 2,174553n.
Los matemáticos buscaron demostrar que un conjunto tapa no podía ser mucho más grande que estos casos conocidos. Sorprendentemente, el problema resultó ser bastante más difícil de lo que pensaban. Roy Meshulam, en 1995, pudo mostrar que el tamaño de un conjunto tapa es a lo más 3n/n (3). Esto da una buena aproximación para valores pequeños de n, pero a medida que n es grande, no resulta tan bueno. Sólo como una comparación rápida, si n=10, tenemos que 310/10 = 5904.9 (que corresponde con el resultado de Meshulam); pero 2,17455310 = 2364,285… (que corresponde con el resultado de Edel). Esta diferencia se pone cada vez peor a medida que n se hace más y más grande.
El problema de encontrar mejores cotas superiores para el problema quedó prácticamente intacto por casi veinte años. En 2012, Michael Bateman y Nets Hawk Katz pudieron mejorar el resultado de Meshulam (5) pero sólo un poco.
¿Quién podrá defendernos?

Polinomios al rescate

La solución llegó de manera inesperada en 2016 y de manera vertiginosa (vertiginosa pensando en matemáticas, obvio). El 5 de mayo de 2016, Ernie Croot, Vsevolod Lev y Peter Pach subieron a Internet un borrador de un artículo que resolvía un problema similar usando una técnica novedosa (6). Usando este resultado, el 13 de mayo, Jordan Ellenberg pudo encontrar una mejora sustancial sobre el problema del conjunto tapa, que fue generalizado el 15 de mayo por Dion Gijswit, y luego ambos publicaron juntos (7). De casi nada de progreso en veinte años, llegaron a una mejora enorme en... ¡Menos de diez días! Matemáticas a velocidad de Internet. Ambos artículos ya fueron aceptados en la revista Annals of Mathematics, considerada por muchos la más importante de toda la disciplina.
Lo más bello en este caso es que la solución es muy simple. El artículo de Ellenberg y Gijswit tiene sólo cuatro páginas (y una de ellas sólo tiene la lista de referencias). ¿Cómo lo hicieron?
La respuesta completa requiere detalles técnicos, pero se basa en un concepto que quizás conoce: los polinomios. Si recuerda de la enseñanza media a la célebre función cuadrática a x2 + b x + c, pues bien, recuerda lo que es un polinomio. Ese es un polinomio de grado dos, pues la potencia de x más grande que aparece es un x2. En general, pueden existir polinomios de grado n, que son funciones de la forma a xn + b xn-1 + ... + z. Por ejemplo, 4 x3 + 6 x + 10 es un polinomio de grado 3. De la misma forma, un polinomio de grado uno, se juntó con otro de grado dos, se multiplicaron e hicieron un grado 3 (Gracias, no se molesten).
Para solucionar el problema, los matemáticos ocuparon unas fórmulas un poquito más complicadas. Siguen siendo polinomios, pero ahora en lugar de tener una sola variable libre x, pueden tener varias, como x, y, z; de manera tal que siempre las variables x, y, z aparezcan como potencias. Por ejemplo, algo como p(x,y,z) = 3 x2 y z + x y + 4 es un polinomio en las variables x, y, z. En el caso de un polinomio en varias variables se le puede asignar un número (llamado el rango del polinomio) que mide, en cierta medida, qué tan fácil es de descomponer en polinomios más simples (de una sola variable). Mientras más rango tiene un polinomio, más «complicado» es.
La magia de la demostración consiste en una igualdad de polinomios. Tomamos un conjunto tapa A, cualquiera. Queremos demostrar que el tamaño de A no es muy grande. Debido a las propiedades del conjunto tapa A, podemos escribir un polinomio p cuyo rango es igual al tamaño del conjunto tapa. Por otro lado, podemos escribir un polinomio q que, tras un poco de análisis, puede verse que tiene rango no tan grande, a lo más de tamaño 2,765n. El golpe de gracia es demostrar que los polinomios p y q son iguales. Luego el tamaño de A es igual al rango de p que es igual al rango de q que es a lo más 2,765n. Luego el tamaño de A es a lo más 2,765n.
El lenguaje técnico marea un poco, pero usted apreciará que al menos la «estructura» de la demostración es simple. El uso de los polinomios en este tipo de problemas resultó ser novedoso, e inexplicablemente poderoso para ayudar a resolver el problema de forma sencilla.

¿Y esto de qué sirve?

El problema tiene aplicaciones que van más allá de jugar juegos de mesa. Posiblemente la aplicación más «aterrizada a la vida diaria» sea el diseño de algoritmos para multiplicar matrices. Este es un problema computacional que se usa constantemente en muchos programas computacionales de manera implícita. Por ejemplo, se ocupa constantemente en los programas que generan gráficos computacionales, como videojuegos. Resolver el problema de «multiplicar matrices» de manera rápida podría mejorar de manera sustancial la velocidad y la calidad de muchos programas que usamos regularmemente.
Por ello se busca diseñar algoritmos buenos y rápidos para el problema de multiplicación de matrices. En 2005, Cohn, Kleinberg, Szegedy y Umans propusieron un algoritmo que, de ser cierta una conjetura, entregaría una forma rápida de resolver el problema de multiplicación de matrices. La resolución del problema del conjunto tapa, lamentablemente, entrega un resultado negativo: la estrategia de Cohn, Kleinberg, Szegedy y Umans no funciona (8). No es una solución definitiva al problema todavía, pero ayuda a entenderlo de manera mucho más profunda.
Así que, quién sabe, posiblemente un matemático jugando juegos de cartas esté ayudando involuntariamente a que tus consolas de videojuegos funcionen mejor.
Advertencia: El lector pedante que tenga conocimiento del tema notará que estamos siendo imprecisos: la mayoría de los resultados que citamos en términos de cotas son sólo ciertos de manera asintótica. Estamos conscientes de ello, pero decidimos obviar dicho detalle sólo para alivianar la exposición del texto, que está dirigido a un público general.
El lector horriblemente pedante habrá notado que el chiste de los polinomios que se multiplican puede no ser cierto si los coeficientes de dichos polinomios viven en un anillo con divisores de cero. Por suerte, éste no es el caso. Dichos polinomios ahora tienen una relación estable y se proyectan a futuro.

Referencias

(1) N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences, http://oeis.org. Sequence A090245. https://oeis.org/A090245
(2) G. Pellegrino, Sul massimo ordine delle calotte in S4,q, Le Matematiche, 25 (1970). 149-157.
(3) Y. Edel, Extensions of Generalized Product Caps, Designs, Codes and Cryptography, 31 (2004). 5–14.
(4) R. Meshulam, On subsets of finite abelian groups containing no 3-term arithmetic progressions, Journal of Combinatorial theory Ser. A. , 71(1995) 168-172.
(5) M. Bateman y N. H. Katz,. New bounds on cap sets. J. Amer. Math. Soc. 25 (2012), 585-613 https://arxiv.org/abs/1101.5851
(6) E. Croot, V. Lev y P. P. Pach, Progression-free sets in Zn4 are exponentially small. Annals of Mathematics, 185 (2017), no. 1, 331-337.
(7) J. S. Ellenberg y D. Gijswijt, On large subsets of Fnq with no three-term arithmetic progression, Annals of Mathematics, 185 (2017), no. 1, 339-343
(8)J. Blasiak, T. Church, H. Cohn, J. A. Grochow, E. Naslund, W. F. Sawin y C. Umans,  On cap sets and the group-theoretic approach to matrix multiplication. Arxiv: https://arxiv.org/abs/1605.06702