On the Limit of the Linear Programming Bound for Codes and Packing

Posted on January 21, 2024 by Gil Kalai

Samorodnitsky

Alex Samorodnitsky

The most powerful general method for proving upper bounds for the size of error correcting codes and of spherical codes (and sphere packing) is the linear programming method that goes back to Philippe Delsarte. There are very interesting results and questions about the power of this method and in this post I would like to present a few of them, especially results from 2001 and 2004 papers by Alex Samorodnitsky, a 2001 paper by Alexander Barg and David Jaffe, and a 2009 paper by Alex and Michael Navon. Finally I will very briefly mention three recent papers on the limitations of the linear programming method for sphere packings (for dimension \le 32) by  Cohn and Triantafillou, Li, and de Courcy-Ireland,  Dostert, and  Viazovska. I will also mention some other related papers. Two recent posts over here on sphere packing are this post and this post.

Recall that the rate R(C) of a binary code C of length n is defined as \displaystyle \frac {\log |C|}{n}. Let us start with the following central questions:

Question 1: For a real number \alpha, 0 < \alpha < 1/2, what is (asymptotically) the maximum rate f(\alpha) of a binary error-correcting binary code of length n and minimum distance $d=\alpha n$?

Question 2: For a real number \theta < \pi/2 and a spherical d-dimensional code C with minimal distance \theta. What is the maximum value of \displaystyle \frac {\log |C|}{d} as d goes to infinity?

The best known bound upper bound for Question 1 is the McEliece, Rodemich, Rumsey
and Welch (MRRW) bound; The best known upper bound for Question 2 is the Kobatyanski-Levenshtein (KL) bound.

Of course, questions 1 and 2 are important asymptotic special cases of even more general questions regarding upper bounds for the sizes of binary and spherical codes.

We will mainly discuss in this post the following two problems.

Question 3: For a real number \alpha, 0 < \alpha < 1/2, what is (asymptotically) the best upper bound B(\alpha) for  f(\alpha) that follows from Delsarte’s linear program.

Question 4: For a real number \theta <\pi/2, what is (asymptotically) the best upper bound B(\theta) for  f(\theta) that follows from Delsarte’s linear program.

We start with the following paper:

On the optimum of Delsarte’s linear program, A. Samorodnitsky, Journal of Combinatorial Theory, Ser. A, 96, 2, 2001

Abstract: We are interested in the maximal size A(n, d) of a binary error-correcting code of length n and distance d, or, alternatively, in the best packing of balls of radius (d-1)/2 in the n-dimensional Hamming space. The best known lower bound on A(n, d) is due to Gilbert and Varshamov, and is obtained by a covering argument. The best known upper bound is due to McEliece, Rodemich, Rumsey and Welch, and is obtained using Delsarte’s linear programming approach. It is not known, whether this is the best possible bound one can obtain from Delsarte’s linear program. We show that the optimal upper bound obtainable from Delsarte’s linear program will strictly exceed the Gilbert-Varshamov lower bound. In fact, it will be at least as big as the average of the Gilbert-Varshamov bound and the McEliece, Rodemich, Rumsey and Welch upper bound. Similar results hold for constant weight binary codes. The average of the Gilbert-Varshamov bound and the McEliece, Rodemich, Rumsey and Welch upper bound might be the true value of Delsarte’s bound. We provide some evidence for this conjecture

For 0 \le \alpha \le 1 let H(\alpha) denote the entropy function.   

Samorodnitsky Theorem (2001):  B(\delta) \ge (H(1/2 - \sqrt{\delta(1-\delta)}) + (1-H(\delta))/2.

I remember that I was (around 1998) completely fascinated by Alex’s result. This was still in the BB era (before blog) so I did not write about it. As we will see, Alex himself improved the result and thus refuted the conjecture at the end of the abstract. Motivated by Alex’s paper, Alexander Barg and David Jaffe conducted numerical experiments for n=1000. In their paper  Numerical results on the asymptotic rate of binary codes, they wrote: “the most important conclusion is that Delsarte’s linear programming method is unlikely to yield major improvements of the known general upper bounds on the size of codes,” leading to the following conjectures:

Conjecture 6 (supported by numerical computation by Barg and Jaffe): Asymptotically, the MRRW bounds  are the best that can be derived from Delsarte’s linear programming.

Conjecture 7 (by analogy): For spherical codes, asymptotically, the KL bounds are the best that can be derived from the linear programming method.

I find Conjectures 6 and 7 very fascinating and yet perhaps not hopeless.

We note that MRRW themselves (naturally) conjectured that Delsarte’s LP can lead to better bounds than their bounds.

In 2004 Alex proved an analogous result for his result about binary codes to the case of spherical codes. (The paper also studies spherical designs.) The best known upper bounds by Grigory Kabatiansky and Vladimir Levenshtein are based on Delsarte’s LP. The best known lower bounds are achieved by greedy spherical codes (or random spherical codes) and only slight improvements for them are known. (See this post; these small improvements have no bearing on the rate.) 

On linear programming bounds for spherical codes and designs, A. Samorodnitsky, Discrete and Computational Geometry, 31, 3, 2004.

Abstract: We investigate universal bounds on spherical codes and spherical designs that could be obtained using Delsarte’s linear programming methods. We give a lower estimate for the LP upper bound on codes, and an upper estimate for the LP lower bound on designs. Specifically, when the distance of the code is fixed and the dimension goes to infinity, the LP upper bound on codes is at least as large as the average of the best known upper and lower bounds. When the dimension n of the design is fixed, and the strength k goes to infinity, the LP bound on designs turns out, in conjunction with known lower bounds, to be proportional to k^{n-1}. 

The next paper I want to discuss is Linear programming bounds for codes via a covering argument, M. Navon, A. Samorodnitsky, Discrete and Computational Geometry, 41, 2, 2009.

This paper contains results in various directions, but related to the topic of our post it improves Alex 2001 bound about the limitation of Delsarte’s LP:

Navon and Samorodnitsky Theorem (2009):

B(\delta) \ge 1/2 H(1 - 2\sqrt{\delta(1-\delta)}).

This gives better bounds for large values of \delta and is the current world record for B(\delta).

Let me mention three recent papers about the limitations of  Cohn-Elkies’ linear program for sphere packing. The first is: Henry Cohn, Nicholas Triantafillou, Dual linear programming bounds for sphere packing via modular forms, the second is by Rupert Li, Dual Linear Programming Bounds for Sphere Packing via Discrete Reductions, and the third is by  Matthew de Courcy-Ireland, Maria Dostert, and Maryna Viazovska, Six-dimensional sphere packing and linear programming.

Some comments:

1) MRRW1 and MRRW2. MRRW beautifully derived their bound (H(1/2 - \sqrt{\delta(1-\delta)}) (referred to as MRRW1) from the LP programs, went on to apply Delsarte’s linear program  for constant weight codes and obtained similar upper bounds for them. Then they used these bounds to improve MRRW1 to stronger bounds (referred to as MRRW2) for some values of \delta. As it recently turned out  MRRW2 could also be derived directly from Delsarte’s LP for the Hamming cube.

2) The Fourier connections. There is a nice way to get the Delsarte’s linear programming by Fourier analysis of Boolean functions. This is explained in a 1995 paper by Nati Linial and me On the distance distribution of binary codes.

3) Various proofs for MRRW1.  Although the original proof of MRRW1 (and MRRW2) are not very complicated new proofs shed light on the theorem. Let me mention a few papers: Friedman and Tillich’s ingenious paper, Generalized Alon–Boppana theorems and error-correcting codes; The paper by Navon and Samorodnitsky mentioned above; A recent paper by Samorodnitsky, One more proof of the first linear programming bound for binary codes and two conjectures; A recent paper by Linial and Elyassaf Loyfer, An Elementary Proof of the First LP Bound on the Rate of Binary Codes.

4) What will it take to improve MRRW or KL? This is, of course, a holy grail in the area, and a central problem in mathematics. Over the years there were several interesting proposals on how to improve Delsarte’s LP and improve the MRRW and KL bounds. So far, there have been no improvements of the bounds themselves. This is a topic for a whole new post.

5) Can hypercontractivity help? A suggestion from my old paper with Nati was to add to Delsarte’s LP  hypercontractive inequalities. It will be nice to pursue this direction. Alex’s conjectures in the paper mentioned in comment 3 are related. Alex told me that hypercontractive inequalities (and discrete isoperimetric inequalities) are also useful for understanding the limitations of Delsarte’s LP.

Two additional pictures

fbds

From a Facebook discussion about the breakthrough of Marcelo Campos, Matthew Jenssen, Marcus Michelen, and Julian Sahasrabudhe. 

hcnt

Links to various relevant papers. (Please comment on additional relevant papers especially on the central question of the limitations of Delsarte’s LP.)

  1. R McEliece, E Rodemich, H Rumsey, L Welch New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities,  IEEE Transactions on Information Theory 23 (1977)
  2. G.A. Kabatyanskii and V. I. Levenshtein, Bounds for  packings on a sphere and in space, Probl. Inform.Transm.,14 (1978).
  3. Philippe Delsarteand and Vladimir I. Levenshtein,  Association Schemes and Coding Theor, IEEE Transactions on Information Theory. 44 (1998)
  4. Gil Kalai and Nati Linial, On the distance distribution of binary codes., IEEE Trans. Inf. Th., 41(1995).
  5. A. Samorodnitsky, On the optimum of Delsarte’s linear program, Journal of Combinatorial Theory, Ser. A, 96, 2, 2001
  6. Linear codes and character sums, N. Linial and A. Samorodnitsky, Combinatorica 22 (2002), no. 4, 497–522.
  7. Alexander Barg and David Jaffe, Numerical results on the asymptotic rate of binary codes,
  8. Alexei Ashikhmin, Alexander Barg, and Simon Litsyn, Estimates_of_the_distance_distribution_of_codes_and_designs, IEEE Transactions on Information Theory, 47 (2001).
  9.  Joel Friedman and Jean-Pierre Tillich, Generalized Alon–Boppana theorems and error-correcting codes, SIAM J. Discret. Math. 19(2005), 700-718. 
  10. A. Schrijver. New code upper bounds from the Terwilliger algebra and semidefinite
    programming. IEEE Transactions on Information Theory, 51 (2005) 2859–2866.
  11. M. Navon, A. Samorodnitsky,  Linear programming bounds for codes via a covering argument,  Discrete and Computational Geometry, 41 (2009).

  12. Alex Samorodnitsky,  A modified logarithmic Sobolev inequality for the Hamming cube and some applications,  arXiv:0807.1679.

  13. Henry Cohn, Nicholas Triantafillou, Dual linear programming bounds for sphere packing via modular forms
  14. On the weight distribution of random binary linear codes, Nati Linial and Jonathan Mosheiff, Random Strutures and Algorithms, 56(1): 5-36 (2020).
  15. Leonardo N. Coregliano, Fernando G. Jeronimo, Chris Jones, A Complete Linear Programming Hierarchy for Linear Codes, arXiv:2112.09221. 
  16. Rupert Li, Dual Linear Programming Bounds for Sphere Packing via Discrete Reductions,  arXiv 2206.09876
  17. Alex Samorodnitsky, Hypercontractive Inequalities for the Second Norm of Highly Concentrated Functions, and Mrs. Gerber’s-Type Inequalities for the Second Rényi Entropy,
  18. Matthew de Courcy-Ireland, Maria Dostert, and Maryna Viazovska, Six-dimensional sphere packing and linear programming.
  19. Alex Samorodnitsky, One more proof of the first linear programming bound for binary codes and two conjectures, Israel Journal of Mathematics
  20. Nati Linial and Elyassaf Loyfer, New LP-based upper bounds in the rate-vs.-distance problem for linear codes, arXiv 2206.09211.
  21. Nati Linial and Elyassaf Loyfer, An elementary proof of the first LP bound on the rate of binary codes. arXiv 2303.16619.
  22. Steven Dougherty, Jon-Lark Kim, and Patrick Sole, Open_Problems_in_Coding_Theory, 2015.
This entry was posted in Combinatorics, Convexity, Geometry and tagged , , , . Bookmark the permalink.

2 Responses to On the Limit of the Linear Programming Bound for Codes and Packing

  1. Gil Kalai says:
    February 3, 2024 at 10:31 pm

    I added a few more relevant papers. I will always be happy to learn about more.

    Reply
  2. Chris Jones says:
    March 7, 2024 at 2:49 am

    There are some intriguing computational results in the paper “High-dimensional sphere packing and the modular bootstrap” by Afkhami-Jeddi, Cohn, Hartman, de Laat, Tajdini. They suggest that the KL bound for sphere packing may not be tight (and by extension they suggest the possiblity that the Delsarte LP can prove a better bound than MRRW2). Their numerical basis for the conjecture appears reasonable enough but this would be extremely surprising if true!

    Reply

Leave a comment