Semidefinite bounds for nonbinary codes based on quadruples

Autor: Alexander Schrijver, Bart Litjens, Sven Polak
Přispěvatelé: Algebra, Geometry & Mathematical Physics (KDV, FNWI), Faculty of Science
Rok vydání: 2016
Předmět:
Upper bounds
Nonbinary code
0102 computer and information sciences
02 engineering and technology
Positive-definite matrix
90C22
01 natural sciences
Upper and lower bounds
Representation theory
Article
Combinatorics
Cardinality
FOS: Mathematics
0202 electrical engineering
electronic engineering
information engineering
Mathematics - Combinatorics
Semidefinite programming
Representation Theory (math.RT)
Mathematics - Optimization and Control
Mathematics
Polynomial (hyperelastic model)
Code
Applied Mathematics
Order (ring theory)
020206 networking & telecommunications
Function (mathematics)
94B65
05E10
90C22
20C30
Computer Science Applications
Optimization and Control (math.OC)
010201 computation theory & mathematics
Bounded function
Delsarte
94B65
Combinatorics (math.CO)
20C30
05E10
Mathematics - Representation Theory
Zdroj: Designs, Codes, and Cryptography
Designs, Codes and Cryptography, 84, 87-100
Designs, Codes and Cryptography, 84(1-2), 87-100. Springer Netherlands
ISSN: 1573-7586
0925-1022
DOI: 10.1007/s10623-016-0216-5
Popis: For nonnegative integers q, n, d, let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_q(n,d)$$\end{document}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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_q(n,d)$$\end{document}Aq(n,d). For any k, let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{C}_k$$\end{document}Ck be the collection of codes of cardinality at most k. Then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_q(n,d)$$\end{document}Aq(n,d) is at most the maximum value of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum _{v\in [q]^n}x(\{v\})$$\end{document}∑v∈[q]nx({v}), where x is a function \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{C}_4\rightarrow {\mathbb {R}}_+$$\end{document}C4→R+ such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x(\emptyset )=1$$\end{document}x(∅)=1 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x(C)=\!0$$\end{document}x(C)=0 if C has minimum distance less than d, and such that the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{C}_2\times \mathcal{C}_2$$\end{document}C2×C2 matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(x(C\cup C'))_{C,C'\in \mathcal{C}_2}$$\end{document}(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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_4(6,3)\le 176$$\end{document}A4(6,3)≤176, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_4(7,3)\le 596$$\end{document}A4(7,3)≤596, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_4(7,4)\le 155$$\end{document}A4(7,4)≤155, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_5(7,4)\le 489$$\end{document}A5(7,4)≤489, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_5(7,5)\le 87$$\end{document}A5(7,5)≤87.
Databáze: OpenAIRE
Externí odkaz: