New Bounds on the Size of Binary Codes with Large Minimum Distance

Let $A(n,d)$ denote the maximum size of a binary code of length $n$ and minimum Hamming distance $d$. Studying $A(n,d)$, including efforts to determine it as well to derive bounds on $A(n,d)$ for large $n$’s, is one of the most fundamental subjects in coding theory. In this paper, we explore new lower and upper bounds on $A(n,d)$ in the large-minimum distance regime, in particular, when $d=n\mathrm{/}2-\mathrm{\Omega }(\sqrt{n})$. We first provide a new construction of cyclic codes, by carefully selecting specific roots in the binary extension field for the check polynomial, with length $n=2^m-1$, distance $d\ge n\mathrm{/}2-2^{c-1}\sqrt{n}$, and size $n^{c+1\mathrm{/}2}$, for any $m\geq 4$andanyinteger$c$with$0 \leq c \leq m/2 - 1$. These code parameters are slightly worse than those of the Delsarte–Goethals (DG) codes that provide the previously known best lower bound in the large-minimum distance regime. However, using a similar and extended code construction technique we show a sequence of cyclic codes that improve upon DG codes and provide the best lower bound in a narrower range of the minimum distance $d$, in particular, when $d = n/2 - \Omega(n^{2/3})$. Furthermore, by leveraging a Fourier-analytic view of Delsarte’s linear program, upper bounds on $A(n,n\mathrm{/}2-\rho \sqrt{n})$ with $\rho \in (0.5,9.5)$ are obtained that scale polynomially in $n$. To the best of authors’ knowledge, the upper bound due to Barg and Nogin \cite{barg2006spectral} is the only previously known upper bound that scale polynomially in $n$ in this regime. We numerically demonstrate that our upper bound improves upon the Barg-Nogin upper bound in the specified high-minimum distance regime.