Graham conjecture on small sets in abelian groups

A continuación se presenta un resumen técnico detallado del artículo "Conjetura de Graham sobre conjuntos pequeños en grupos abelianos" de Costa, Della Fiore, Fontana y Vena, estructurado según los puntos solicitados.

1. El Problema: Secuenciabilidad en Grupos Abelianos

El trabajo aborda la Conjetura de Graham (también conocida como Conjetura de Graham/Alspach), un problema fundamental en la teoría de grupos y combinatoria aditiva.

• Definición de Secuenciabilidad: Sea $G$ un grupo abeliano y $A \subseteq G \setminus \{0\}$ un subconjunto finito. Se dice que $A$ es secuenciable si existe un ordenamiento de sus elementos $a_1, \dots, a_k$ tal que todas sus sumas parciales $p_i = \sum_{j=1}^i a_j$ (para $1 \le i \le k$) sean distintas entre sí. Si, además, ninguna suma parcial es cero (excepto la suma total si el conjunto es de suma cero), se habla de un ordenamiento de "secuenciación" estricto.
• Estado del Arte:
  • La conjetura afirma que todo subconjunto de un grupo abeliano que no contenga al cero es secuenciable.
  • Para grupos cíclicos de orden primo ($\mathbb{Z}_p$), se ha demostrado recientemente para $p$ suficientemente grande (Pham y Sauermann, 2024), pero el caso de primos pequeños y grupos generales permanecía abierto.
  • Los mejores resultados previos para grupos abelianos genéricos (sin asumir estructura específica) se limitaban a conjuntos de tamaño $|A| \le 9$ (Alspach y Liversidge, mediante búsqueda exhaustiva por fuerza bruta).
  • Para la Conjetura CMPP (Costa-Morini-Pasotti-Pellegrini), que añade la restricción de que la suma de los elementos sea cero y no contenga pares inversos $\{x, -x\}$, el límite conocido era $|A| \le 10$ en grupos genéricos.

2. Metodología: Enfoque Recursivo y Computacional

Los autores desarrollan un enfoque híbrido que combina teoría algebraica avanzada con una búsqueda computacional exhaustiva optimizada.

A. El Lema Recursivo (Teoría)

El núcleo teórico del trabajo es un Lema Recursivo (Corolario 2.5). Este lema establece que, para cualquier conjunto $A \subseteq G \setminus \{0\}$, se cumple una de dos condiciones:

1. $A$ ya es secuenciable.
2. Existen dos elementos distintos $x_1, x_2 \in A$ tales que su suma $x_1 + x_2$ no es cero y no pertenece a $A \setminus \{x_1, x_2\}$.

Si se cumple la segunda condición, se puede construir un nuevo conjunto $A' = (A \setminus \{x_1, x_2\}) \cup \{x_1 + x_2\}$ de tamaño $|A|-1$. Si $A'$ es secuenciable, entonces $A$ también lo es. Esto reduce el problema de tamaño $k$ a uno de tamaño $k-1$.

La demostración de este lema se realiza mediante dos vías:

• En $\mathbb{Z}_p$: Utilizando el Teorema del Cero Combinatorio de Alon (Combinatorial Nullstellensatz). Se construye un polinomio homogéneo $F_k$ y se demuestra que existe una asignación de variables tal que el polinomio no se anula, garantizando la existencia de los elementos fusionables.
• En grupos abelianos genéricos: Mediante una demostración directa basada en la caracterización de subconjuntos cerrados bajo la suma de elementos distintos (Teorema 2.4), utilizando ideas relacionadas con el Teorema de Kneser. Se demuestra que si no se pueden fusionar elementos, el conjunto más el cero debe formar un subgrupo, lo cual ya está resuelto en la literatura.

B. Algoritmo de Búsqueda Computacional

Para verificar la secuenciabilidad de los conjuntos reducidos (y los originales), los autores implementan un algoritmo de búsqueda en árbol (BFS) con poda basada en certificados de contradicción.

• Estructura del Árbol: Cada nodo representa un ordenamiento parcial y una matriz de restricciones (vectores de incidencia) derivada de suposiciones de colisión (sumas parciales iguales).
• Certificados de Terminación: El algoritmo detiene la exploración de una rama si detecta una contradicción lineal en las restricciones acumuladas:
  1. Certificado de Cero: Implica que un elemento $a_i = 0$ (imposible por definición).
  2. Certificado de Igualdad: Implica que $a_i = a_j$ para $i \neq j$ (imposible por ser elementos distintos).
  3. Certificado de Compresión: Utiliza el resultado del Lema Recursivo. Si el conjunto reducido $A'$ tiene una secuenciación conocida, el algoritmo verifica si la suposición de colisión en $A$ contradice la estructura de sumas cero prohibidas en $A'$.
• Implementación: El código está escrito en Python, utilizando álgebra lineal numérica (numpy) para calcular rangos de matrices y verificar dependencias lineales. Se ejecutó en un servidor con 128 núcleos y 2 TB de RAM.

3. Contribuciones Clave y Resultados

El trabajo establece nuevos límites superiores para la secuenciabilidad en grupos abelianos genéricos, superando significativamente la barrera de $|A| \le 9$.

Teoremas Principales

1. Teorema 1.4 (Caso General): Todo subconjunto $A \subseteq G \setminus \{0\}$ es secuenciable si $|A| \le 20$.
   • Mejora: Incrementa el límite conocido de 9 a 20.
2. Teorema 1.5 (Caso de Suma Cero): Si además $\sum_{x \in A} x = 0$, entonces $A$ es secuenciable si $|A| \le 22$.
3. Teorema 1.6 (Conjetura CMPP): Si $\sum_{x \in A} x = 0$ y $A$ no contiene pares inversos $\{x, -x\}$, entonces $A$ es secuenciable si $|A| \le 23$.

Avances Metodológicos

• Validación del Lema Recursivo: Se proporciona una prueba rigurosa y general del lema que permite la reducción de tamaño, algo que no estaba disponible de forma general para grupos arbitrarios.
• Eficiencia Computacional: Se demuestra que el enfoque recursivo, combinado con la búsqueda de certificados, es mucho más eficiente que un algoritmo de árbol puro. Sin el Lema Recursivo, el algoritmo se queda limitado a $|A| \le 10$ (coincidiendo con resultados anteriores), mientras que con él alcanza 23.

4. Significado e Impacto

• Resolución Parcial de la Conjetura: Aunque la conjetura completa para grupos arbitrarios sigue abierta, este trabajo cierra la brecha para conjuntos "pequeños" (hasta 23 elementos), un rango que era completamente inexplorado para grupos generales.
• Aplicabilidad: Los resultados tienen implicaciones directas en el diseño de Arrays de Heffter y otros problemas de diseño combinatorio donde la secuenciabilidad es un requisito estructural.
• Nueva Estrategia: El trabajo introduce una metodología robusta que combina demostraciones algebraicas (Nullstellensatz y teoría de grupos) con verificación computacional asistida por reducción recursiva. Esto ofrece un modelo para atacar problemas combinatorios similares donde la fuerza bruta pura es inviable.
• Reproducibilidad: Los autores han hecho público el código fuente y los datos, permitiendo la verificación independiente y la extensión futura de los límites (por ejemplo, intentando llegar a $|A| = 24$ o más).

En resumen, el artículo representa un avance sustancial en la teoría de secuenciabilidad, elevando el umbral de validez conocida para la Conjetura de Graham en grupos abelianos genéricos de 9 a 20 (y hasta 23 bajo restricciones adicionales), mediante una sofisticada combinación de teoría algebraica y computación de alto rendimiento.