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

Let A(n, d) denote the maximum number of codewords in a binary code of length n and minimum Hamming distance d. Deriving upper and lower bounds on A(n, d) has been a subject for extensive research in coding theory. In this paper, we examine upper and lower bounds on A(n, d) in the high-minimum distance regime, in particular, when $d = n/2 - \Theta(\sqrt{n})$. We will first provide a lower bound based on a cyclic construction for codes of length $n= 2^m -1$ and show that $A(n, d) \geq n^c$ for $d= n/2 - 2^{c-1}\sqrt{n}$, where c is an integer with $1 \leq c \leq m/2 - 1$. With a Fourier-analytic view of Delsarte's linear program, novel upper bounds on $A(n, n/2 - \sqrt{n})$ and $A(n, n/2 - 2\sqrt{n})$ are obtained, both of which scale polynomially in $n$.