Semidefinite bounds for nonbinary codes based on quadruples
2017
For nonnegative integers q, n, d, let $$A_q(n,d)$$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 $$A_q(n,d)$$Aq(n,d). For any k, let $$\mathcal{C}_k$$Ck be the collection of codes of cardinality at most k. Then $$A_q(n,d)$$Aq(n,d) is at most the maximum value of $$\sum _{v\in [q]^n}x(\{v\})$$źvź[q]nx({v}), where x is a function $$\mathcal{C}_4\rightarrow {\mathbb {R}}_+$$C4źR+ such that $$x(\emptyset )=1$$x(ź)=1 and $$x(C)=\!0$$x(C)=0 if C has minimum distance less than d, and such that the $$\mathcal{C}_2\times \mathcal{C}_2$$C2×C2 matrix $$(x(C\cup C'))_{C,C'\in \mathcal{C}_2}$$(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 $$A_4(6,3)\le 176$$A4(6,3)≤176, $$A_4(7,3)\le 596$$A4(7,3)≤596, $$A_4(7,4)\le 155$$A4(7,4)≤155, $$A_5(7,4)\le 489$$A5(7,4)≤489, and $$A_5(7,5)\le 87$$A5(7,5)≤87.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
9
References
15
Citations
NaN
KQI