New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming. (English) Zbl 1105.94027

Summary: We give a new upper bound on the maximum size \(A_{q}(n,d)\) of a code of word length \(n\) and minimum Hamming distance at least \(d\) over the alphabet of \(q\geq 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 A. Schrijver [IEEE Trans. Inf. Theory 51, 2859–2866 (2005)] on the Terwilliger algebra of the binary Hamming scheme.


94B65 Bounds on codes
05E30 Association schemes, strongly regular graphs
90C22 Semidefinite programming
Full Text: DOI Link


[1] Bannai, E.; Ito, T., Algebraic combinatorics I: association schemes, (1984), Benjamin/Cumings Menlo Park, CA · Zbl 0555.05019
[2] Bogdanova, G.T.; Brouwer, A.E.; Kapralov, S.N.; Östergård, P.R.J., Error-correcting codes over an alphabet of four elements, Des. codes cryptogr., 23, 333-342, (2001) · Zbl 1011.94029
[3] Bogdanova, G.T.; Östergård, P.R.J., Bounds on codes over an alphabet of five elements, Discrete math., 240, 13-19, (2001) · Zbl 1005.94032
[4] Brouwer, A.E.; Hämäläinen, H.O.; Östergård, P.R.J.; Sloane, N.J.A., Bounds on mixed binary/ternary codes, IEEE trans. inform. theory, 44, 140-161, (1998) · Zbl 0911.94009
[5] Delsarte, P., An algebraic approach to the association schemes of coding theory, Philips res. rep. suppl., vol. 10, (1973), Philips Res. Lab. Eindhoven · Zbl 1075.05606
[6] Schrijver, A., New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE trans. inform. theory, 51, 2859-2866, (2005) · Zbl 1298.94152
[7] Terwilliger, P., The subconstituent algebra of an association scheme, part I, J. algebraic combin., 1, 363-388, (1992) · Zbl 0785.05089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.