The Asymptotic Number of Anticodes in Hamming Spaces

In the Hamming space ${\mathbb{F}}_q^n$, a $d$-anticode is a subset in which every pair of points has Hamming distance at most $d$, or equivalently, a set of diameter at most $d$. Let $m_q(n,d)$ denote the maximum size of a $d$-anticode and let ${\mathcal{A}}_q(n,d)$ be the family of all $d$-anticodes. We show that for fixed $q$, as $n\to \mathrm{\infty }$, the total number of $d$-anticodes satisfies $$\mathrm{\mid }{\mathcal{A}}_q(n,d)\mathrm{\mid }=2^{(1+o(1))m_q(n,d)}$$ for $4\le d\le n-1$, except when $q=2$ and $d=n-1$. We also count linear $d$-anticodes, that is, subspaces of ${\mathbb{F}}_q^n$ with diameter at most $d$. For fixed $q$ and $d$, their number is polynomial in $n$. For growing $d$, we determine the exponential order as $q^{{\mathrm{\Theta }}_q(d^2+d{\log }_q(n\mathrm{/}d))}$ in the sublinear regime and $q^{\mathrm{\Theta }(n^2)}$ when $d\mathrm{/}n\to \alpha \in (0,1)$. In the near-full regime $n-d=o(n)$, we obtain the sharper count $q^{(1\mathrm{/}4+o(1))n^2}$. A random-generator construction further improves the binary lower bound for every fixed linear diameter.