Semidefinite lower bounds for covering codes

Definición del Problema
El artículo aborda el problema de determinar $K_q(n, r)$, definido como el tamaño mínimo de un código de cobertura $q$-ario de longitud de palabra $n$ y radio de cobertura $r$. Un conjunto de palabras de código $C \subseteq \{0, \dots, q-1\}^n$ tiene radio de cobertura $r$ si la unión de las bolas de Hamming de radio $r$ centradas en las palabras de código cubre todo el espacio de Hamming. Una instancia específica de este problema, $K_3(n, 1)$, es conocida como el "problema de los pronósticos de fútbol" (football pool problem), que busca el número mínimo de pronósticos requeridos para garantizar como máximo un error en $n$ partidos de fútbol. Si bien los límites superiores se establecen típicamente mediante la construcción de códigos explícitos, este artículo se centra en derivar límites inferiores mejorados para $K_q(n, r)$.

Metodología
Los autores se basan en el trabajo de Gijswijt (2005), quien introdujo un límite inferior de programación semidefinida (SDP) para códigos de cobertura utilizando cortes de matrices. La metodología presentada en este artículo fortalece este límite a través de tres avances técnicos primarios:

1. Restricciones de la Jerarquía de Lasserre: Los autores introducen nuevas restricciones semidefinidas inspiradas en la jerarquía de Lasserre para programas 0-1. Específicamente, utilizan el segundo nivel de esta jerarquía, que implica analizar la distribución de triples de palabras de código. Esto conduce a la construcción de una matriz $N$ derivada del vector de incidencia del código, sujeta a desigualdades de cobertura de la forma $\sum \lambda_i A_i(u) \ge \beta$.
2. Reducción de Simetría mediante Álgebras de Terwilliger: Para hacer que la SDP resultante sea computacionalmente tratable, los autores emplean la reducción de simetría. Utilizan el álgebra de Terwilliger del esquema de Hamming (tanto para casos binarios como no binarios). Al identificar las órbitas de pares y triples de palabras de código bajo la acción del grupo de isometría $Aut(q, n)$ (y su subgrupo estabilizador $Aut_0(q, n)$), reducen la dimensionalidad de las variables de la matriz.
   • Para el caso binario ($q=2$), el álgebra $A_{2,n}$ se descompone en bloques mediante un $\ast$-isomorfismo $\phi$ que la mapea a una suma directa de bloques matriciales más pequeños, reduciendo la complejidad de $O(2^n)$ a $O(n^3)$ variables.
   • Para el caso no binario ($q \ge 3$), se aplica una descomposicion en bloques similar al álgebra $A_{q,n}$, reduciendo la complejidad a $O(n^4)$ variables.
3. Función Objetivo Mejorada: El artículo propone una función objetivo más potente. En lugar de minimizar el término lineal estándar relacionado con el tamaño del código, los autores minimizan la traza de la variable de la matriz correspondiente al tercer momento del tamaño del código ($|C|^3$). Demuestran que esta función objetivo cúbica produce un límite inferior estrictamente más ajustado que los objetivos lineales o cuadráticos utilizados anteriormente.

Contribuciones Clave

• Marco Teórico: El artículo establece un marco riguroso de SDP para códigos de cobertura que generaliza los límites de Schrijver para códigos de corrección de errores al problema de cobertura. Deriva formalmente las restricciones para la matriz $N$ y las matrices bordeadas $R(c, N)$ dentro del contexto de la jerarquía de Lasserre.
• Algoritmos de Reducción de Simetría: Los autores proporcionan fórmulas explícitas para la descomposición en bloques de las álgebras de Terwilliger relevantes para los esquemas de Hamming binarios y no binarios. Esto incluye coeficientes combinatorios detallados ($\eta$ y $\alpha$) necesarios para traducir las desigualdades de corte de matriz y las restricciones de Lasserre al espacio de variables reducido.
• Implementación Computacional: Los autores implementaron estos límites utilizando aritmética de alta precisión (BigFloats de 512 bits) a través del lenguaje de programación Julia y el resolvedor SDPA-GMP. Desarrollaron un código independiente para validar la generación de las SDP.

Resultos
Los autores presentan nuevos límites inferiores para $K_q(n, r)$ a través de un amplio rango de parámetros ($q, n, r$). Estos resultados se compilan en las Tablas 1, 2 y 3, cubriendo los casos binarios ($q=2$), ternarios ($q=3$) y cuaternarios/quinarios ($q=4, 5$).

• Caso Binario: Los nuevos límites mejoran los límites inferiores conocidos previamente para varios valores de $n$ y $r$ (por ejemplo, $K_2(13, 1)$, $K_2(21, 1)$, $K_2(13, 2)$). Los autores señalan que, aunque inicialmente encontraron límites mejorados para $K_2(18, 1)$ y $K_2(30, 1)$, estos valores específicos fueron superados posteriormente por Wu y Chen (2026).
• Caso No Binario: Se reportan mejoras significativas para códigos ternarios (problema de los pronósticos de fútbol), tales como $K_3(13, 3)$ y $K_3(14, 4)$, así como para $q=4$ y $q=5$.
• Escala Computacional: El artículo reporta el número de variables y tamaños de bloque para las SDP reducidas por simetría. Por ejemplo, para $n=32$ en el caso binario, la SDP reducida involucra 1,239 variables con una suma de tamaños de bloque al cuadrado de 6,545. Los tiempos de resolución variaron de segundos a varios días dependiendo del tamaño de la instancia y del número de coeficientes no nulos en las restricciones de desigualdad.

Significancia
El artículo afirma que las técnicas propuestas conducen a "límites inferiores más ajustados" que establecen nuevos récords para una amplia gama de parámetros de códigos de cobertura. Al extender el enfoque de la jerarquía de Lasserre a los códigos de cobertura y utilizar eficazmente la reducción de simetría, los autores demuestran que la brecha entre los límites inferiores y superiores conocidos puede reducirse. El trabajo proporciona un método sistemático para computar estos límites, ofreciendo una alternativa más poderosa a los límites de programación lineal y a los enfoques previos de SDP que no explotaban plenamente las restricciones de la distribución de triples o la optimización de la función objetivo específica. Los resultados sirven como puntos de referencia actualizados para el campo de los códigos de cobertura y el problema de los pronósticos de fútbol.