Delsarte bound rates for binary and spherical codes solved exactly
The Rate of the Delsarte Bound for Binary Codes and Spheres
Information Theory
Summary
The paper finds an exact formula for how well a mathematical limit, called the Delsarte bound, performs for two important types of codes used in communication and data storage. This extends the author's earlier work on binary codes at a specific distance, now covering a broader range and also spherical codes, which correspond to points on a sphere. To achieve this, the author blends tools from potential theory and spectral analysis, solving a complex problem involving orthogonal polynomials and measures. The results provide matching lower and upper limits, giving a precise understanding of these bounds' rates.
What this means in practice
- •For coding theory engineers: Design tighter performance limits for error-correcting codes in data transmission systems using the exact rate of the Delsarte bound for binary and spherical codes.
- •For quantum information teams: Use the connection between N-qubit constructions and spectral interlacing to refine bounds in quantum error correction schemes related to binary coding.
A theory result. No direct application yet.
Authors
Andrew Salmon
Abstract
We give the asymptotic rate of Delsarte's linear programming bound for binary codes and spherical codes. This extends previous work of the author which formulated and proved an analogue of the conjecture of Afkhami-Jeddi, Cohn, Hartman, de Laat, and Tajdini for binary codes, obtaining the rate of the Delsarte linear program at distance $1/2-1/π$. The lower bounds introduce ideas from potential theory into the study of Delsarte's bounds, whereby the measures underlying a system of orthogonal polynomials give an obstacle problem. We solve the resulting obstacle problem in the case of binary codes and spherical codes, obtaining a closed form for the lower bound in terms of elliptic integrals. For the upper bounds, we relate the $N$-qubit construction for binary codes used in previous work of the author to the constructions in OpenAI's Chapter 2 for spherical codes and observe that they both involve interlacing spectra. This leads to a variational problem involving measures constructed from these spectra under the Markov-Krein correspondence. This variational problem admits an exact solution and matches the lower bound.