A covering code of radius R is a set of binary n-words so that every binary n-word can be reached from one of the codewo

Definitions and mathematical statement

For binary words $x,y\in\{0,1\}^n$, let $d_H(x,y)$ be their Hamming distance, the number of coordinates at which they differ. A covering code of radius $R$ is a set $C\subseteq\{0,1\}^n$ such that each word is within distance $R$ of at least one codeword. Put \[ K(n,R)=\min\{|C|:\bigcup_{c\in C}B_H(c,R)=\{0,1\}^n\}, \qquad V(n,R)=\sum_{j=0}^R\binom nj \] for $0\le R\le n$. The sphere-covering bound is $K(n,R)V(n,R)\ge2^n$.

For each fixed integer $R\ge1$, determine the sharp asymptotic size of $K(n,R)$ as $n\to\infty$. In particular, is \[ K(n,R)\sim R!\,\frac{2^n}{n^R}, \] equivalently, does the covering density $K(n,R)V(n,R)/2^n$ tend to one? If this fails, determine the correct leading behavior, distinguishing a genuine limiting constant from bounds on upper and lower limits.

Codes are arbitrary subsets, with no linearity assumption. Balls may overlap, and every binary word must be covered. The radius stays fixed while the block length grows. The exponential factor is $2^n$, the size of the ambient cube; the $2^R$ appearing in the transcribed source's general-size formula is a typographical error.

Short English statement

Determine the asymptotic minimum size of binary covering codes of fixed radius, including whether sphere-covering density tends to one.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3100073 (AMR-030-0073), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Cooper - Combinatorial Problems I Like (2020 snapshot), Words and Codes, source-order bullet 73. Original source indexed by AMR-030-0073. https://people.math.sc.edu/cooper/combprob.html.