2017

# Semidefinite bounds for nonbinary codes based on quadruples

## Publication

### Publication

*Designs, Codes and Cryptography , Volume 84 p. 87- 100*

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.

Additional Metadata | |
---|---|

Journal | Designs, Codes and Cryptography |

Citation |
Litjens, B, Polak, S.C, & Schrijver, A. (2017). Semidefinite bounds for nonbinary codes based on quadruples.
Designs, Codes and Cryptography, 84, 87–100. |