On the largest sum-free subset of the lattice cube

A continuación se presenta un resumen técnico detallado del artículo "On the largest sum-free subset of the lattice cube" de Peter Keevash y Jeck Lim.

1. Enunciado del Problema

El artículo aborda el problema de determinar la densidad asintótica del mayor subconjunto libre de sumas dentro de un cubo reticular de dimensión $d$.

• Definiciones: Un subconjunto $S$ de un grupo abeliano es libre de sumas si no existen $x, y, z \in S$ tales que $x + y = z$. Los autores estudian subconjuntos del cubo reticular $[n+1]^d = \{0, 1, \dots, n\}^d$.
• Objetivo: Determinar el límite $c_d = \lim_{n \to \infty} \frac{|S|}{n^d}$, donde $S$ es el mayor subconjunto libre de sumas.
• Contexto:
  • Para $d=1$, es bien conocido que $c_1 = 1/2$.
  • Para $d=2$, Elsholtz y Rackham demostraron que $c_2 = 3/5$.
  • Para $d=3, 4$, Lepsveridze y Sun resolvieron recientemente estos casos.
  • La Conjetura: Se conjeturó que para todo $d$, el conjunto óptimo es una "rebanada" del cubo definida por un hiperplano. Específicamente, el conjunto $S^* = \{x \in [n+1]^d \mid u \le \sum x_i < 2u\}$, donde $u$ se elige para maximizar el volumen de la rebanada, produce la densidad máxima.
  • Sea $c^*_d$ el volumen máximo de dicha rebanada en el límite continuo $[0,1]^d$. La conjetura establece que $c_d = c^*_d$.

2. Metodología

La demostración sigue el enfoque establecido por Lepsveridze y Sun, utilizando una combinación de dualidad de programación lineal y acoplamiento probabilístico (mezclabilidad conjunta).

A. Reducción a Programación Lineal

El problema de acotar $|S|$ se reformula como un programa lineal (PL).

• Problema Primal: Maximizar $\sum |S(x)|$ (donde $S(x)$ son las fibras del conjunto $S$) sujeto a la restricción de que para cualquier $x, y, z$ con $x+y=z$, se cumple $|S(x)| + |S(y)| + |S(z)| \le 2(n+1)$.
• Problema Dual: Para encontrar una cota superior, se debe construir una solución factible (pesos) para el PL dual. La existencia de tales pesos depende de la capacidad de acoplar distribuciones de probabilidad específicas.

B. Mezclabilidad Conjunta

La innovación técnica central es la demostración de un resultado de Mezclabilidad Conjunta.

• Definición: Las distribuciones $\mu_1, \mu_2, \mu_3$ son mezclables conjuntamente si existe un acoplamiento $(X_1, X_2, X_3)$ con estas marginales tal que $X_1 + X_2 + X_3 = \mathbb{E}[X_1] + \mathbb{E}[X_2] + \mathbb{E}[X_3]$ casi seguramente.
• El Teorema Clave (Teorema 1.5): Los autores demuestran que para cualesquiera enteros no negativos $r, s, t$ tales que $r+s+t = dn$, las distribuciones uniformes sobre las rebanadas discretas $L_d(r), L_d(s), L_d(t)$ (donde $L_d(k) = \{x \in [n+1]^d : \sum x_i = k\}$) son mezclables conjuntamente.
• Técnica de Demostración:
  • Inducción sobre $d$: El caso base $d=2$ se basa en resultados conocidos sobre intervalos y desigualdades triangulares.
  • Paso Inductivo ($d \ge 3$): Los autores construyen un acoplamiento para las primeras coordenadas utilizando un argumento de punto fijo (Teorema del Punto Fijo de Brouwer o Perron-Frobenius). Definen una aplicación en el espacio de distribuciones de probabilidad sobre el soporte de las primeras coordenadas y demuestran que existe un punto fijo. Este punto fijo asegura que las marginales coincidan con las distribuciones uniformes requeridas en las rebanadas, permitiendo aplicar la hipótesis de inducción a las restantes $d-1$ coordenadas.

C. Construcción de Pesos y Estimaciones de Rebanadas

Para aplicar la mezclabilidad conjunta al PL dual:

1. Particionamiento: El dominio $[n+1]^{d-1}$ se partitiona en cinco conjuntos ($A, B, C, D, E$) basados en la suma de las coordenadas en relación con el parámetro de la rebanada óptima $u^*_d$.
2. Función de Peso: Utilizando el resultado de mezclabilidad conjunta, los autores construyen una función de peso $w(x,y,z)$ soportada en triples específicos de estos conjuntos.
3. Estimaciones Analíticas: Utilizan propiedades de log-concavidad de la función de densidad de probabilidad de la suma de variables aleatorias uniformes (distribución de Irwin-Hall). Derivan cotas explícitas sobre los ratios de los volúmenes de las rebanadas (Lema 3.1) para asegurar que los pesos construidos satisfagan las restricciones duales.
   • Para $d$ grande, utilizan estimaciones de grandes desviaciones.
   • Para $d$ pequeño ($5 \le d < 200$), verifican las desigualdades numéricamente.

3. Contribuciones Clave

1. Resolución de la Conjetura para Todo $d$: El artículo demuestra que $c_d = c^*_d$ para todas las dimensiones $d \ge 1$. Esto confirma que el mayor subconjunto libre de sumas es efectivamente la rebanada definida por el hiperplano $\sum x_i \in [u^*_d n, 2u^*_d n)$.
2. Teorema General de Mezclabilidad Conjunta: La demostración del Teorema 1.5 es una contribución significativa a la teoría de la probabilidad y la combinatoria. Establece que las distribuciones uniformes sobre rebanadas discretas de un hipercubo que suman una constante son mezclables conjuntamente, un resultado que generaliza hallazgos previos para dimensiones bajas específicas.
3. Refinamiento del Enfoque Lepsveridze-Sun: Los autores generalizan el método utilizado para $d=3,4$ a dimensiones arbitrarias, superando la complejidad de construir acoplamientos en dimensiones más altas mediante un riguroso argumento inductivo de punto fijo.

4. Resultados Principales

• Teorema 1.1: Para cualquier $d \ge 1$ y cualquier subconjunto libre de sumas $S \subseteq [n+1]^d$, el tamaño está acotado por:
  $$|S| \le c^*_d n^d + O(n^{d-1})$$
  donde $c^*_d$ es el volumen máximo de la rebanada $S_d(u) = \{x \in [0,1]^d : u \le \sum x_i < 2u\}$.
• Corolario: La densidad límite es exactamente el volumen de la rebanada óptima, resolviendo la conjetura natural planteada por Cameron, Green y otros.

5. Significado y Extensiones

• Teoría de Números Combinatoria: Este resultado resuelve un problema abierto de larga data sobre la estructura de los conjuntos libres de sumas en retículos de alta dimensión. Confirma que la construcción de "rebanada" es universalmente óptima, no solo para dimensiones bajas.
• Métodos Probabilísticos: El artículo demuestra el poder de la mezclabilidad conjunta y las técnicas de acoplamiento para resolver problemas combinatorios extremos. La construcción inductiva de acoplamientos mediante teoremas de punto fijo es una técnica novedosa y robusta.
• Conjuntos Convexos Generales: Los autores discuten brevemente si esta optimalidad de "rebanada" se mantiene para conjuntos convexos generales. Proporcionan un contraejemplo (Proposición 5.1) que muestra que para $d$ suficientemente grande, existen conjuntos convexos donde el mayor subconjunto libre de sumas no es una sola rebanada definida por un funcional lineal. Esto destaca que la simetría del hipercubo es crucial para la optimalidad de la rebanada.
• Problema Abierto: El artículo deja abierta la cuestión de si la optimalidad de la rebanada se mantiene para todos los conjuntos convexos acotados en la dimensión $d=2$.

En resumen, este artículo proporciona una solución completa a la densidad asintótica del mayor subconjunto libre de sumas en un cubo reticular, unificando resultados parciales previos e introduciendo potentes herramientas probabilísticas para manejar dimensiones arbitrarias.