An Improved Linear Programming Bound on the Average Distance of a Binary Code

Abstract

Ahlswede and Katona (1977) posed the following isodiametric problem in Hamming spaces: For every $n$ and $1\le M\le 2^n$, determine the minimum average Hamming distance of binary codes with length $n$ and size $M$. Fu, Wei, and Yeung (2001) used linear programming duality to derive a lower bound on the minimum average distance. However, their linear programming approach was not completely exploited. In this paper, we improve Fu-Wei-Yeung's bound by finding a better feasible solution to their dual program. For fixed $0<a\le 1/2$ and for $M=\lceil a{2}^n\rceil$, our feasible solution attains the asymptotically optimal value of Fu-Wei-Yeung's dual program as $n\to \infty$. Hence for $0<a\le 1/2$, all possible asymptotic bounds that can be derived by Fu-Wei-Yeung's linear program have been characterized. Furthermore, noting that the average distance of a code is closely related to weights of Fourier coefficients of a Boolean function, we also apply the linear programming technique to prove bounds on Fourier weights of a Boolean function of various degrees.

17 pages, 2 figures