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$. 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/2 - \Omega(\sqrt{n})$. We first provide a lower bound by demonstrating a carefully designed construction of cyclic codes of length $n= 2^m -1$ showing that $A(n, d= n/2 - 2^{c-1}\sqrt{n}) \geq n^{c+1/2}$, for any integer $c$ with $1 \leq c \leq m/2 - 1$. Using a similar code construction technique a sequence of improved lower bounds are shown 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/2 - \rho\sqrt{n})$ with $\rho\in (0.5, 9.5)$ are obtained that scale polynomially in $n$. We provide numerical results to demonstrate that these are the tightest upper bounds, to the best of our knowledge, in the specified regime compared with previously known bounds in the literature.