The sum-product problem for small sets II

Este artículo establece que todo conjunto de 10 (y 11) números naturales determina al menos 30 (y 34) sumas o productos distintos, extendiendo resultados previos mediante la identificación de configuraciones óptimas y la clasificación de conjuntos reales que minimizan estas cantidades bajo ciertas restricciones de progresiones.

Lo esencial

¡Hola! Imagina que tienes una caja llena de números enteros (como 1, 2, 3, 4...). Ahora, vamos a jugar a dos juegos diferentes con estos números:

1. El Juego de las Sumas: Tomas dos números de tu caja, los sumas y anotas el resultado. Repites esto con todas las parejas posibles. ¿Cuántos resultados diferentes obtienes?
2. El Juego de las Multiplicaciones: Haces lo mismo, pero multiplicando los números en lugar de sumarlos. ¿Cuántos resultados diferentes obtienes?

La pregunta central de este documento es: ¿Es posible tener una caja de números donde tanto las sumas como las multiplicaciones den muy pocos resultados diferentes?

Los matemáticos (Erdős y Szemerédi) sospechaban hace mucho tiempo que no. Creían que si intentas hacer que las sumas sean "aburridas" (pocos resultados distintos), las multiplicaciones se volverán "caóticas" (muchos resultados distintos), y viceversa. Es como intentar mantener el equilibrio en una cuerda floja: si te inclinas demasiado hacia un lado, el otro lado se dispara.

¿Qué descubrieron estos autores?

Este equipo de investigadores (estudiantes universitarios y un profesor) se enfocó en cajas pequeñas, específicamente con 10 y 11 números.

Antes de ellos, ya sabían la respuesta para cajas de hasta 9 números. Pero para 10 y 11, el misterio persistía. Su trabajo es como resolver las últimas piezas de un rompecabezas muy difícil.

Sus hallazgos principales son:

• Para 10 números: Si tienes una caja con 10 números, es imposible que tengas menos de 30 resultados diferentes en sumas Y menos de 30 en multiplicaciones. Al menos una de las dos operaciones tendrá que "explotar" y darte al menos 30 resultados distintos.
• Para 11 números: La regla se vuelve un poco más estricta. Necesitas al menos 34 resultados distintos en una de las dos operaciones.

¿Cómo lo descubrieron? (La analogía de la "Fórmula Mágica")

Imagina que los números en tu caja son como ingredientes en una receta.

• Si los ingredientes están en una Progresión Aritmética (como 1, 2, 3, 4, 5...), las sumas son muy predecibles y pocas. Pero las multiplicaciones se vuelven locas.
• Si están en una Progresión Geométrica (como 1, 2, 4, 8, 16...), las multiplicaciones son predecibles, pero las sumas se vuelven locas.

El truco que intentaron estos autores fue encontrar una "receta híbrida": una mezcla de ingredientes que fuera un poco aritmética y un poco geométrica para engañar a ambos juegos y mantener los números bajos en ambos lados.

El "Campeón" (La mejor receta):
Encontraron que la mejor manera de mantener los números bajos para 10 elementos es usar este conjunto específico:
{1, 2, 3, 4, 6, 8, 9, 12, 16, 18}

Si usas esta caja:

• Las sumas dan 30 resultados distintos.
• Las multiplicaciones dan 29 resultados distintos.

¡Casi lo lograron! Pero no pudieron bajar de 30 en ambas cosas al mismo tiempo. Y lo más importante: demostraron que no existe ninguna otra combinación de 10 números que funcione mejor que esta (salvo que multipliques todos los números por 2, o por 3, etc., lo cual es como cambiar la escala de la receta pero no la estructura).

¿Cómo lo probaron? (El uso de la Computadora)

Este no fue un trabajo de "papel y lápiz" tradicional. Fue una caza de tesoros digital.

1. La Búsqueda (WinnersSearch): Imagina que tienes un robot que prueba millones de combinaciones de números. El robot construye cajas de números paso a paso. Si en algún momento ve que las sumas o multiplicaciones se están volviendo demasiado grandes, descarta esa caja y prueba otra.
2. La Clasificación: El robot descubrió que casi todas las cajas "eficientes" (las que mantienen los números bajos) tienen una estructura muy específica: son como una cuadrícula de dos dimensiones. Piensa en una tabla de Excel donde los números crecen hacia la derecha (multiplicando por un número) y hacia abajo (multiplicando por otro número).
3. El Control de Colisiones: Luego, usaron matemáticas avanzadas y más computadoras para ver si, dentro de esas estructuras especiales, podían ocurrir "choques" (donde dos sumas diferentes dan el mismo resultado). Contaron cuántos choques podían ocurrir y demostraron que, incluso con los mejores trucos, siempre terminas con al menos 30 resultados distintos.

¿Por qué es importante?

Este trabajo es como cerrar una puerta en un edificio de matemáticas.

• Sabemos que para cajas pequeñas (hasta 11 números), la "regla del 30" y la "regla del 34" son leyes inquebrantables.
• Han encontrado la única "excepción perfecta" (la caja {1, 2, 3, 4, 6, 8, 9, 12, 16, 18}) y han demostrado que es única.

El futuro:
El documento termina diciendo que para 12 números, la cosa se pone muy difícil (el "terreno peligroso"). La mejor caja conocida hasta ahora sugiere que el límite sube a 41, pero la estructura de los números cambia de ser una cuadrícula de 2 dimensiones a una de 3 dimensiones (como un cubo de Rubik en lugar de una hoja de papel).

En resumen:
Estos investigadores usaron la fuerza bruta de las computadoras combinada con la lógica matemática para demostrar que, en el mundo de los números pequeños, no puedes tenerlo todo. Si intentas ser muy ordenado en las sumas, el caos de las multiplicaciones te alcanzará, y viceversa. Y han encontrado la forma más eficiente posible de intentar (y fallar) en ese equilibrio.

Resumen técnico

A continuación presento un resumen técnico detallado del artículo "THE SUM-PRODUCT PROBLEM FOR SMALL SETS II" (El problema suma-producto para conjuntos pequeños II) de Antis, Britt, Chapman, Hawkins, Rice y Warren.

1. El Problema

El problema suma-producto, formulado inicialmente por Erdős y Szemerédi en la década de 1980, investiga hasta qué punto un subconjunto finito $A$ de los enteros (o anillos generales) puede tener simultáneamente un número pequeño de sumas distintas y un número pequeño de productos distintos.

Se definen:

• $A + A = \{a + b : a, b \in A\}$ (conjunto de sumas).
• $AA = \{ab : a, b \in A\}$ (conjunto de productos).

El objetivo central es determinar la función $SP(k)$, definida como el mínimo valor de $\max\{|A+A|, |AA|\}$ sobre todos los subconjuntos $A \subseteq \mathbb{N}$ con $|A| = k$. La conjetura principal asintótica sugiere que $SP(k) = k^{2-o(1)}$, lo que implica que no se pueden tener pocos sumas y pocos productos al mismo tiempo.

Este trabajo se centra en casos pequeños ($k$ pequeño), donde el comportamiento es discreto y depende de la estructura algebraica específica de los conjuntos, en lugar de límites asintóticos.

2. Metodología

Los autores emplean una combinación de teoría de números aditiva, clasificación estructural y computación intensiva asistida por Python. Su enfoque se basa en los siguientes pilares:

A. Reducción a Estructuras Geométricas

Utilizando teoremas de Freiman (específicamente los Teoremas 1.2 y 1.3), el trabajo establece que si un conjunto tiene muy pocas sumas, debe estar contenido en una progresión aritmética o ser una unión de dos progresiones aritméticas.

• En el lado del producto, esto se traduce mediante logaritmos: si $|AA|$ es pequeño, $A$ debe estar contenido en una progresión geométrica o ser una unión de dos progresiones geométricas con la misma razón.
• Para $k=10$ y $k=11$, los autores demuestran que si $|AA|$ es bajo, el conjunto $A$ (tras escalar) debe tener una estructura de progresión geométrica bidimensional de la forma $\{r^m s^n\}$, donde $r, s \in \mathbb{Q}$ y $\log_r(s) \notin \mathbb{Q}$.

B. Clasificación Computacional (Algoritmo WinnersSearch)

Para identificar todas las posibles estructuras de conjuntos que minimizan las sumas, desarrollan un algoritmo de búsqueda recursiva llamado WinnersSearch.

• Este algoritmo construye conjuntos $P \subseteq \mathbb{Z}^2$ (que representan los exponentes de las progresiones geométricas) paso a paso.
• Filtra las estructuras basándose en la condición de que el número de sumas no exceda un umbral dado ($M$).
• Clasifica las estructuras "ganadoras" (aquellas que mantienen un número bajo de sumas) hasta similitud (traslación y transformación lineal invertible).
• Para $k=10$ y $|L+L| \le 29$, el algoritmo identifica un número finito de configuraciones posibles de $P$.

C. Control de Colisiones (Algoritmo CollisionCheck)

Una vez identificadas las estructuras candidatas (subconjuntos de $G_1 = \{r^m s^n : 0 \le m \le 7, n \in \{0,1\}\}$ y $G_2 = \{r^m s^n : 0 \le m \le 3, 0 \le n \le 2\}$), el desafío es cuantificar cuántas sumas se pierden debido a "colisiones" (cuadruplas aditivas no triviales donde $a+b=c+d$).

• Los autores modelan las colisiones como sistemas de ecuaciones polinómicas bivariadas en $r$ y $s$.
• Utilizan resultantes de polinomios y el teorema de la raíz racional para encontrar pares excepcionales $(r, s)$ donde ocurren múltiples colisiones simultáneas ("doble colisión").
• Identifican 155 pares excepcionales para $G_1$ y 75 para $G_2$.
• Para todos los casos no excepcionales, demuestran que el número de colisiones es limitado, lo que permite establecer cotas inferiores estrictas para $|A+A|$.

3. Contribuciones Clave y Resultados

Resultados Principales (Teorema 1.5)

El artículo establece los valores exactos para $SP(k)$ en $k=10$ y $k=11$:

• $SP(10) = 30$: Todo conjunto de 10 enteros positivos determina al menos 30 sumas distintas o 30 productos distintos.
• $SP(11) = 34$: Todo conjunto de 11 enteros positivos determina al menos 34 sumas distintas o 34 productos distintos.

Unicidad de los Conjuntos Extremales

El trabajo no solo encuentra los valores, sino que clasifica únicamente (salvo escalamiento) los conjuntos que alcanzan estos mínimos:

• Para $k=10$, el único conjunto es $\{1, 2, 3, 4, 6, 8, 9, 12, 16, 18\}$. Este conjunto tiene $|A+A|=30$ y $|AA|=29$.
• Para $k=11$, el único conjunto es $\{1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24\}$. Este conjunto tiene $|A+A|=34$ y $|AA|=32$.

Extensiones y Clasificaciones Adicionales

• Resultados para Reales: Se presentan clasificaciones para conjuntos de números reales que tienen a lo sumo 29 sumas (o productos) y que no contienen 8 elementos en una progresión aritmética (o geométrica).
• Corrección de la Literatura: Se identifican y corrigen lagunas en la clasificación de Freiman para $|A+A| = 3k-2$, proporcionando estructuras faltantes que no estaban cubiertas en trabajos anteriores.
• Límites para $k=12$ y $k=13$: Se discute que para $k=12$, la estructura bidimensional sigue siendo dominante, pero para $k=13$, la estructura óptima parece requerir una dimensión tres (unión de tres progresiones geométricas con razones comunes pero puntos de partida en progresión aritmética), lo que marca un cambio de régimen en el problema.

4. Significado e Impacto

1. Precisión en Casos Pequeños: Mientras que la literatura asintótica se centra en el crecimiento de $SP(k)$, este trabajo resuelve el problema de manera exacta para valores pequeños de $k$, llenando un vacío entre los resultados conocidos para $k \le 9$ y el comportamiento asintótico.
2. Método Híbrido: El artículo demuestra la viabilidad de combinar teoremas profundos de teoría aditiva (Freiman) con búsquedas computacionales exhaustivas y análisis de sistemas polinómicos para resolver problemas combinatorios difíciles.
3. Unicidad Estructural: La demostración de que los conjuntos extremos son únicos (salvo escalamiento) es un resultado fuerte que ofrece una comprensión profunda de cómo deben organizarse los números para minimizar la "energía" suma-producto.
4. Herramientas Abiertas: Los autores han hecho público todo el código Python y los cuadernos Jupyter utilizados, permitiendo la verificación y extensión de sus resultados por la comunidad matemática.

En resumen, este trabajo representa un avance significativo en la comprensión del problema suma-producto para conjuntos finitos pequeños, resolviendo casos abiertos de larga data y estableciendo un marco metodológico robusto para futuros estudios en $k > 11$.