The Asymptotic Number of Anticodes in Hamming Spaces

Abstract

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\infty$, the total number of $d$-anticodes satisfies \[ |\mathcal{A}_q(n,d)|=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^{\Theta_q(d^2+d\log_q(n/d))}$ in the sublinear regime and $q^{\Theta(n^2)}$ when $d/n\to\alpha\in(0,1)$. In the near-full regime $n-d=o(n)$, we obtain the sharper count $q^{(1/4+o(1))n^2}$. A random-generator construction further improves the binary lower bound for every fixed linear diameter.