On the optimum of Delsarte's linear program
type: Item
instance of: scholarly article
title: On the optimum of Delsarte's linear program
zbMATH Open document ID: 0991.94060
author: Alex Samorodnitsky
published in: Journal of Combinatorial Theory. Series A
publication date: 2002-08-24T00:00:00Z
reviewed by: Patric R. J. Östergård
Mathematics Subject Classification ID: 94B65
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 51E22
zbMATH DE Number: 1694169
zbMATH Keywords: bounds on codes
zbMATH Keywords: error-correcting code
zbMATH Keywords: linear programming
MaRDI profile type: Publication
full work available at URL: jcta.2001.3176
OpenAlex ID: W1981075218
cites work: Numerical results on the asymptotic rate of binary codes
cites work: Q3218140
cites work: Q5707657
cites work: On the distance distribution of codes
cites work: Q4063326
cites work: On the minimal redundancy of binary error-correcting codes
cites work: Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces
cites work: Q4276333
cites work: Q4146667
cites work: New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
cites work: Q3818127
cites work: Q4002255
DOI: 10.1006/JCTA.2001.3176
review text: The author studies Delsarte's linear programming approach, which was used by \textit{R. McEliece, E. Rodemich, H. Rumsey}, and \textit{L. Welch} [IEEE Trans. Inf. Theory 23, 157--166 (1977; Zbl 0361.94016)] to get an upper bound for the size of error-correcting codes. The question is whether an even better upper bound can be derived using Delsarte's inequalities. The author arrives at a lower bound for what can be derived; this bound strictly exceeds the Gilbert-Varshamov bound and is at least as big as the average of the Gilbert-Varshamov bound and the McEliece-Rodemich-Rumsey-Welch bound. (In addition to unrestricted binary codes, constant weight codes are also considered in a similar vein.) NEWLINENEWLINENEWLINEOn the other hand, as the author also points out in a note added in proof, recent numerical results by \textit{A. Barg} and \textit{D. Jaffe} [in: Codes and association schemes, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 56, 25--32 (2001; Zbl 0989.94035)] indicate that the McEliece-Rodemich-Rumsey-Welch bound gives (asymptotically) the right answer to Delsarte's linear programming problem, which is not in accordance with the (probably incorrect) main conjecture of the current paper.
description: scientific article; zbMATH DE number 1694169