Semidefinite lower bounds for covering codes
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912305994792960 |
|---|---|
| author | Gijswijt, Dion Polak, Sven |
| author_facet | Gijswijt, Dion Polak, Sven |
| contents | Let $K_q(n,r)$ denote the minimum size of a $q$-ary covering code of word length $n$ and covering radius $r$. In other words, $K_q(n,r)$ is the minimum size of a set of $q$-ary codewords of length $n$ such that the Hamming balls of radius $r$ around the codewords cover the Hamming space $\{0,\ldots,q-1\}^n$. The special case $K_3(n,1)$ is often referred to as the football pool problem, as it is equivalent to finding a set of forecasts on $n$ football matches that is guaranteed to contain a forecast with at most one wrong outcome.
In this paper, we build and expand upon the work of Gijswijt (2005), who introduced a semidefinite programming lower bound on $K_q(n,r)$ via matrix cuts. We develop techniques that strengthen this bound, by introducing new semidefinite constraints inspired by Lasserre's hierarchy for 0-1 programs and symmetry reduction methods, and a more powerful objective function. The techniques lead to sharper lower bounds, setting new records across a broad range of values of $q$, $n$, and $r$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_01932 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Semidefinite lower bounds for covering codes Gijswijt, Dion Polak, Sven Combinatorics Information Theory Optimization and Control Let $K_q(n,r)$ denote the minimum size of a $q$-ary covering code of word length $n$ and covering radius $r$. In other words, $K_q(n,r)$ is the minimum size of a set of $q$-ary codewords of length $n$ such that the Hamming balls of radius $r$ around the codewords cover the Hamming space $\{0,\ldots,q-1\}^n$. The special case $K_3(n,1)$ is often referred to as the football pool problem, as it is equivalent to finding a set of forecasts on $n$ football matches that is guaranteed to contain a forecast with at most one wrong outcome. In this paper, we build and expand upon the work of Gijswijt (2005), who introduced a semidefinite programming lower bound on $K_q(n,r)$ via matrix cuts. We develop techniques that strengthen this bound, by introducing new semidefinite constraints inspired by Lasserre's hierarchy for 0-1 programs and symmetry reduction methods, and a more powerful objective function. The techniques lead to sharper lower bounds, setting new records across a broad range of values of $q$, $n$, and $r$. |
| title | Semidefinite lower bounds for covering codes |
| topic | Combinatorics Information Theory Optimization and Control |
| url | https://arxiv.org/abs/2504.01932 |