An asymmetric covering code of radius R is a set of binary n-words so that every binary n-word can be reached from one o

Definitions and mathematical statement

Order binary words coordinatewise, so $x\le y$ means that every one in $x$ is also a one in $y$. The upward asymmetric ball of radius $R$ centered at $x\in\{0,1\}^n$ is \[ B_R^+(x)=\{y\in\{0,1\}^n:x\le y,\ d_H(x,y)\le R\}. \] It consists of words obtained by changing at most $R$ zeroes of $x$ to ones; changing ones to zeroes is forbidden. An upward covering code is a set $C$ with $\bigcup_{x\in C}B_R^+(x)=\{0,1\}^n$. Let $K^+(n,R)$ be the minimum possible $|C|$.

For each fixed integer $R\ge1$, determine its sharp asymptotic growth as $n\to\infty$. The proposed leading term is \[ K^+(n,R)\sim 2^R R!\,\frac{2^n}{n^R}. \] Is this correct, and if not, what leading constant or upper and lower limiting densities replace it?

Unlike symmetric Hamming balls, these balls have sizes depending on their centers: if $x$ has $w$ ones, their size is $\sum_{j=0}^{\min(R,n-w)}\binom{n-w}{j}$. Thus uniform sphere sizes cannot simply be assumed. Complementing every bit gives the equivalent downward convention. The source's exponential factor $2^R$ in its general order formula is corrected to $2^n$; the separate factor $2^R$ in the conjectured coefficient remains.

Short English statement

Determine the sharp asymptotic minimum size of fixed-radius asymmetric binary covering codes with zero-to-one errors.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3100074 (AMR-030-0074), 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 74. Original source indexed by AMR-030-0074. https://people.math.sc.edu/cooper/combprob.html.