MIT Combinatorics Seminar

Some new linear inequalities for binary codes from the Terwilliger algebra

William Martin  (Worcester Polytechnic Institute, visiting MIT)

Friday, February 16, 2007    4:15 pm    Room 2-136


Consider the association scheme of the n-cube, with vertex set X={0,1}^n and relation R_i={(x,y): d(x,y)=i} where d denotes Hamming distance. The adjacency matrix of the n-cube generates a Bose-Mesner algebra, and if we extend this algebra by the diagonal matrix with (x,x)-entry n-2d(0,x), we obtain the Terwilliger algebra of the n-cube. This can also be viewed as the algebra of matrices that commute with the coordinatewise action of the symmetric group S_n on X.

A few years ago, the effort to find upper bounds for the size of a binary error-correcting code seemed to come to an impasse. A. Samorodnitsky proved that the optimum of Delsarte's linear program could never be equal to (or even close to, asymtotically) the Gilbert-Varshamov lower bound. The present talk is one of several efforts to bring new tools to the task of deriving upper bounds. (A closely related result, due to A. Schrijver, made headlines in 2004.) We apply some basic representation theory to describe all of the extreme rays of the positive semidefinite cone of the Terwilliger algebra. These are in one-to-one correspondence with all irreducible S_n-submodules of the module {R}^X. As a result, we obtain explicit linear inequalities which can be appended to Delsarte's system of inequalities (the ``linear programming method'') to improve overall upper bounds.

We illustrate our technique by extending work of de Klerk and Paschnik. They applied semidefinite programming to bound the size of a subset C of X having d(x,y) \neq n/2 for all x,y in C. Our approach is an iterative one, beginning with Delsarte's linear programming problem and adding inequalities based on a Lagrange multiplier analysis of the current optimal solution.

Based on joint work with Terry Visentin, University of Winnipeg.