New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming

• DOI: 10.1016/j.jcta.2006.03.010
• Publication Date: 2006-06-19T13:44:00Z
• Authors: Dion Gijswijt; Alexander Schrijver; Hajime Tanaka
• Keywords: Semidefinite Programming; Hamming distance

AbstractWe give a new upper bound on the maximum size Aq(n,d) of a code of word length n and minimum Hamming distance at least d over the alphabet of q⩾3 letters. By block-diagonalizing the Terwilliger algebra of the nonbinary Hamming scheme, the bound can be calculated in time polynomial in n using semidefinite programming. For q=3,4,5 this gives several improved upper bounds for concrete values of n and d. This work builds upon previous results of Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005) 2859–2866] on the Terwilliger algebra of the binary Hamming scheme.