OP-00940 Open

Density of linear covering codes of large radius

Let $r$ be a fixed positive integer and $H(r)$ the Hamming ball of radius $r$ about $0$ in $\mathbb{F}_2^n$. Let $f(r)$ be the least constant for which infinitely many $n$ admit subspaces $V_n \le \mathbb{F}_2^n$ with $V_n + H(r) = \mathbb{F}_2^n$ and $|V_n| = (f(r) + o(1))\, 2^n / |H(r)|$. The Hamming codes give $f(1) = 1$, and products of $r$ of them give $f(r) \le r^r/r!$. It is not known whether $f(2) = 1$, and $f(r) = 1$ for all $r$ has not been ruled out.

Problem. Does $f(r) \to \infty$ as $r \to \infty$?

Source: B. Green, 100 open problems (version of January 2026), Problem 40.

Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.

Classification

Primary: CO — Combinatorics
Secondary: IT
Keywords: coding theory, covering codes, Hamming balls, linear codes
Literature checked: Oct. 26, 2026 by clemens-admin

References

@book{cohen1997covering,
  author = {Cohen, G{\'e}rard and Honkala, Iiro and Litsyn, Simon and Lobstein, Antoine},
  title = {Covering Codes},
  series = {North-Holland Mathematical Library},
  volume = {54},
  publisher = {North-Holland},
  year = {1997}
}

@article{davydov1990,
  author = {Davydov, A. A.},
  title = {Construction of linear covering codes},
  journal = {Problemy Peredachi Informatsii},
  volume = {26},
  number = {4},
  pages = {38--55},
  year = {1990},
  note = {English translation: Problems of Information Transmission 26 (1990), no. 4, 317--331}
}

@article{davydov1994drozhzhina,
  author = {Davydov, A. A. and Drozhzhina-Labinskaya, A. Yu.},
  title = {Constructions, families, and tables of binary linear covering codes},
  journal = {IEEE Transactions on Information Theory},
  volume = {40},
  number = {4},
  pages = {1270--1279},
  year = {1994},
  doi = {10.1109/18.335937}
}

@article{davydov2026new,
  author = {Davydov, Alexander A. and Marcugini, Stefano and Pambianco, Fernanda},
  title = {New upper bounds for binary linear covering codes},
  journal = {IEEE Transactions on Information Theory},
  volume = {72},
  number = {10},
  pages = {7439--7454},
  year = {2026},
  doi = {10.1109/TIT.2026.3716379},
  eprint = {2511.02542},
  archivePrefix = {arXiv}
}

@misc{davydov2026further,
  author = {Davydov, Alexander A. and Marcugini, Stefano and Pambianco, Fernanda and Wu, Stephen},
  title = {Further results on binary linear covering codes and saturating sets in projective spaces},
  year = {2026},
  eprint = {2609.16078},
  archivePrefix = {arXiv}
}

@phdthesis{struik1994,
  author = {Struik, R.},
  title = {Covering Codes},
  school = {Technische Universiteit Eindhoven},
  year = {1994},
  doi = {10.6100/IR425174}
}

@misc{green100open,
  author = {Green, Ben},
  title = {100 open problems},
  howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
  note = {Problem 40; version of January 2026, most recent update December 2025},
  year = {2026}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00940, "Density of linear covering codes of large radius", clopen.solutions.