For nonnegative integers q, n, d, let Aq(n, d) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on Aq(n, d). For any k, let Ck be the collection of codes of cardinality at most k. Then Aq(n, d) is at most the maximum value of Pv∈[q]n x({v}), where x is a function C4 → R+ such that x(∅) = 1 and x(C) = 0 if C has minimum distance less than d, and such that the C2 ×C2 matrix (x(C ∪C′))C,C′∈C2 is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds A4(6, 3) ≤ 176, A4(7, 4) ≤ 155, A5(7, 4) ≤ 489, and A5(7, 5) ≤ 87.

, , , ,
Designs, Codes and Cryptography
CWI management

Litjens, B., Polak, S., & Schrijver, L. (2017). Semidefinite bounds for nonbinary codes based on quadruples. Designs, Codes and Cryptography, 84, 87–100. doi:10.1007/s10623-016-0216-5