Semidefinite lower bounds for covering codes

Problem Definition
The paper addresses the problem of determining $K_q(n, r)$, defined as the minimum size of a $q$-ary covering code of word length $n$ and covering radius $r$. A set of codewords $C \subseteq \{0, \dots, q-1\}^n$ has covering radius $r$ if the union of Hamming balls of radius $r$ centered at the codewords covers the entire Hamming space. A specific instance of this problem, $K_3(n, 1)$, is known as the "football pool problem," which seeks the minimum number of forecasts required to guarantee at most one error in $n$ football matches. While upper bounds are typically established by constructing explicit codes, this paper focuses on deriving improved lower bounds for $K_q(n, r)$.

Methodology
The authors build upon the work of Gijswijt (2005), which introduced a semidefinite programming (SDP) lower bound for covering codes using matrix cuts. The methodology presented in this paper strengthens this bound through three primary technical advancements:

1. Lasserre Hierarchy Constraints: The authors introduce new semidefinite constraints inspired by the Lasserre hierarchy for 0-1 programs. Specifically, they utilize the second level of this hierarchy, which involves analyzing the distribution of triples of codewords. This leads to the construction of a matrix $N$ derived from the incidence vector of the code, subject to covering inequalities of the form $\sum \lambda_i A_i(u) \ge \beta$.
2. Symmetry Reduction via Terwilliger Algebras: To make the resulting SDP computationally tractable, the authors employ symmetry reduction. They utilize the Terwilliger algebra of the Hamming scheme (both binary and nonbinary cases). By identifying the orbits of pairs and triples of codewords under the action of the isometry group $Aut(q, n)$ (and its stabilizer subgroup $Aut_0(q, n)$), they reduce the dimensionality of the matrix variables.
   • For the binary case ($q=2$), the algebra $A_{2,n}$ is block-diagonalized using a $\ast$-isomorphism $\phi$ mapping it to a direct sum of smaller matrix blocks, reducing the complexity from $O(2^n)$ to $O(n^3)$ variables.
   • For the nonbinary case ($q \ge 3$), a similar block-diagonalization is applied to the algebra $A_{q,n}$, reducing the complexity to $O(n^4)$ variables.
3. Enhanced Objective Function: The paper proposes a more powerful objective function. Instead of minimizing the standard linear term related to the code size, the authors minimize the trace of the matrix variable corresponding to the third moment of the code size ($|C|^3$). They prove that this cubic objective yields a strictly tighter lower bound than the linear or quadratic objectives previously used.

Key Contributions

• Theoretical Framework: The paper establishes a rigorous SDP framework for covering codes that generalizes Schrijver's bounds for error-correcting codes to the covering problem. It formally derives the constraints for the matrix $N$ and the bordered matrices $R(c, N)$ within the context of the Lasserre hierarchy.
• Symmetry Reduction Algorithms: The authors provide explicit formulas for the block-diagonalization of the relevant Terwilliger algebras for both binary and nonbinary Hamming schemes. This includes detailed combinatorial coefficients ($\eta$ and $\alpha$) required to translate the matrix cut inequalities and Lasserre constraints into the reduced variable space.
• Computational Implementation: The authors implemented these bounds using high-precision arithmetic (512-bit BigFloats) via the Julia programming language and the SDPA-GMP solver. They developed independent code to validate the generation of the SDPs.

Results
The authors present new lower bounds for $K_q(n, r)$ across a broad range of parameters ($q, n, r$). These results are compiled in Tables 1, 2, and 3, covering binary ($q=2$), ternary ($q=3$), and quaternary/quinary ($q=4, 5$) cases.

• Binary Case: The new bounds improve upon previously known lower bounds for various values of $n$ and $r$ (e.g., $K_2(13, 1)$, $K_2(21, 1)$, $K_2(13, 2)$). The authors note that while they initially found improved bounds for $K_2(18, 1)$ and $K_2(30, 1)$, these specific values were subsequently surpassed by Wu and Chen (2026).
• Nonbinary Case: Significant improvements are reported for ternary codes (football pool problem), such as $K_3(13, 3)$ and $K_3(14, 4)$, as well as for $q=4$ and $q=5$.
• Computational Scale: The paper reports the number of variables and block sizes for the symmetry-reduced SDPs. For instance, for $n=32$ in the binary case, the reduced SDP involves 1,239 variables with a sum of squared block sizes of 6,545. Solving times ranged from seconds to several days depending on the instance size and the number of nonzero coefficients in the inequality constraints.

Significance
The paper claims that the proposed techniques lead to "sharper lower bounds" that set new records for a wide range of covering code parameters. By extending the Lasserre hierarchy approach to covering codes and effectively utilizing symmetry reduction, the authors demonstrate that the gap between known lower and upper bounds can be narrowed. The work provides a systematic method for computing these bounds, offering a more powerful alternative to linear programming bounds and previous SDP approaches that did not fully exploit the triple-distribution constraints or the specific objective function optimization. The results serve as updated benchmarks for the field of covering codes and the football pool problem.