New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming

Abstract

We give a new upper bound on the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. It is based on block-diagonalizing the Terwilliger algebra of the Hamming cube. The bound strengthens the Delsarte bound, and can be calculated with semidefinite programming in time bounded by a polynomial in n. We show that it improves a number of known upper bounds for concrete values of n and d. From this we also derive a new upper bound on the maximum size A(n,d,w) of a binary code of word length n, minimum distance at least d, and constant weight w, again strengthening the Delsarte bound and yielding several improved upper bounds for concrete values of n, d, and w