On the number of error correcting codes

Abstract

We show that for a fixed $q$, the number of $q$-ary $t$-error correcting codes of length $n$ is at most $2^{(1+o(1))H_q(n,t)}$ for all $t\le (1-q^{-1})n-C_q\sqrt{n\log n}$ (for sufficiently large constant $C_q$), where $H_q(n,t)=q^n/V_q(n,t)$ is the Hamming bound and $V_q(n,t)$ is the cardinality of the radius $t$ Hamming ball. This proves a conjecture of Balogh, Treglown, and Wagner, who showed the result for $t=o(n^{1/3}(\log n{)}^{-2/3})$.

13 pages. Comments welcome!