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.

arXiv commentTwo figures. Comments are welcome