The University of Michigan Combinatorics Seminar
Winter 2000
March 24, 4:10-5:00, 3866 East Hall

On the optimum of Delsarte's linear program

Alex Samorodnitsky

Institute for Advanced Study


We are interested in the maximal size A(n,d) of a binary error correcting code of length n and distance d, or, alternatively, in the best packing of balls of radius (d-1)/2 in the n-dimensional Hamming space. The best known lower bound on A(n,d) is due to Gilbert and Varshamov, and is obtained by a covering argument. The best know upper bound is due to McEliece, Rodemich, Rumsey and Welch, and is obtained using Delsarte's linear programming approach. It is not known, whether this is the best possible bound one can obtain from Delsarte's linear program. We show that the optimal upper bound obtainable from Delsarte's linear program will strictly exceed the Gilbert-Varshamov lower bound. In fact, it will be at least as big as the average of the Gilbert-Varshamov bound and the McEliece, Rodemich, Rumsey and Welch upper bound. Similar results hold for constant weight binary codes.