Semidefinite Code Bounds Based on Quadruple Distances
Dion Gijswijt, Hans Detlef Mittelmann, Alexander Schrijver · IEEE Transactions on Information Theory · 2012
LetA(n,d) be the maximum number of 0, 1 words of lengthn, any two having Hamming distance at leastd. It is proved thatA(20,8)=256, which implies that the quadruply shortened Golay code is optimal. Moreover, it is shown thatA(18,6) ≤ 673,A(19,6) ≤ 1237,A(20,6) ≤ 2279,A(23,6) ≤ 13674,A(19,8) ≤ 135,A(25,8) ≤ 5421,A(26,8) ≤ 9275,A(27,8) ≤ 17099,A(21,10) ≤ 47,A(22,10) ≤ 84,A(24,10) ≤ 268,A(25,10) ≤ 466,A(26,10) ≤ 836,A(27,10) ≤ 1585,A(28,10) ≤ 2817,A(25,12) ≤ 55, andA(26,12) ≤ 96. The method is based on the positive semidefiniteness of matrices derived from quadruples of words. This can be put as constraint in a semidefinite program, whose optimum value is an upper bound forA(n,d). The order of the matrices involved is huge. However, the semidefinite program is highly symmetric, by which its feasible region can be restricted to the algebra of matrices invariant under this symmetry. By block diagonalizing this algebra, the order of the matrices will be reduced so as to make the program solvable with semidefinite programming software in the above range of values ofnandd.