Lower Bounds for $q$-ary Codes with Large Covering Radius

  • Wolfgang Haas
  • Immanuel Halupczok
  • Jan-Christoph Schlage-Puchta


Let $K_q(n,R)$ denote the minimal cardinality of a $q$-ary code of length $n$ and covering radius $R$. Recently the authors gave a new proof of a classical lower bound of Rodemich on $K_q(n,n-2)$ by the use of partition matrices and their transversals. In this paper we show that, in contrast to Rodemich's original proof, the method generalizes to lower-bound $K_q(n,n-k)$ for any $k>2$. The approach is best-understood in terms of a game where a winning strategy for one of the players implies the non-existence of a code. This proves to be by far the most efficient method presently known to lower-bound $K_q(n,R)$ for large $R$ (i.e. small $k$). One instance: the trivial sphere-covering bound $K_{12}(7,3)\geq 729$, the previously best bound $K_{12}(7,3)\geq 732$ and the new bound $K_{12}(7,3)\geq 878$.

Article Number