The University of Michigan Combinatorics Seminar


Abstract 

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 (d1)/2 in the ndimensional 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 GilbertVarshamov lower bound. In fact, it will be at least as big as the average of the GilbertVarshamov bound and the McEliece, Rodemich, Rumsey and Welch upper bound. Similar results hold for constant weight binary codes. 