Unique Optima of the Delsarte Linear Program

Abstract

The Delsarte linear program is used to bound the size of codes given their block length $n$ and minimal distance $d$ by taking a linear relaxation from codes to quasicodes. We study for which values of $(n,d)$ this linear program has a unique optimum: while we show that it does not always have a unique optimum, we prove that it does if $d>n/2$ or if $d\le 2$. Introducing the Krawtchouk decomposition of a quasicode, we prove there exist optima to the $(n,2e)$ and $(n-1,2e-1)$ linear programs that have essentially identical Krawtchouk decompositions, revealing a parity phenomenon among the Delsarte linear programs. We generalize the notion of extending and puncturing codes to quasicodes, from which we see that this parity relationship is given by extending/puncturing. We further characterize these pairs of optima, in particular demonstrating that they exhibit a symmetry property, effectively halving the number of decision variables.

To appear in Designs, Codes and Cryptography. 24 pages

Cited by in corpus (1)

• Dual Linear Programming Bounds for Sphere Packing via Discrete Reductions