9
$\begingroup$

Among the good asymptotic bounds in coding theory in the MRRW bound. It is obtained by using the linear programming problem of Delsarte's and providing a solution. The LP problem is

Suppose $C \subset \mathbb{F}_2^n $ is a code such $d(C)\ge d$. Let $\beta(x) = 1+ \sum_{k=1}^{n} y_k K_k (x)$ be a polynomial such that $y_k \ge 0$ but $\beta(j) \le 0$ for $j=d, d+1,\dots ,n$. Then, we have that $|C| \le \beta(0)$.

Here $K_k(x)$ are the Kravchuk polynomials. In the proof of the MRRW bound, upto scaling, they basically come up with the following polynomial $\beta$ for a general $n$.

$$\beta(x) =\frac{1}{a-x} \left[ K_t(a) K_{t+1}(x) - K_{t+1}(a)K_{t}(x) \right]^{2}$$

After using the Christoffel-Darboux formula the values of $t$ and $a$ are adjusted to make it optimal.

There is no justification for why such a polynomial was chosen other than that it works. Is there anything more that can be said over why this polynomial was chosen?

$\endgroup$
1
  • 1
    $\begingroup$ You might find a partial answer to your question in: A. Samorodnitsky, "On the optimum of Delsarte's linear program," J. Comb. Th. Ser. A, 96(2), 261-287, 2001. $\endgroup$ Jan 21, 2019 at 19:44

2 Answers 2

2
$\begingroup$

I don't know what they were thinking in the past, but there are several modern points of view these days.

  1. We can view the Delsarte LP as the symmetrization of a very large LP (or as the symmetrization of the Lovász theta function SDP on the hypercube graph with edges between strings of distance $\le d$). The Kravchuk polynomials arise naturally in this way since they are the symmetrization of the Boolean Fourier characters. Symmetrization makes the program exponentially smaller, but it does not change the value.
  2. The candidate solution to the Delsarte LP has the form $(a-x) F(x)^2$ after applying Christoffel-Darboux to the candidate $\beta(x)$ in the question. The term $(a-x)$ enforces the sign constraints of the LP, and $\widehat{F}(x)$ is chosen to be an approximate eigenfunction to the matrix $a\cdot\text{Id} - A$. Here $A$ is the adjacency matrix of the standard Boolean hypercube, then symmetry-reduced into a matrix on $\{0,1, \dots, n\}$. The approximate eigenfunction condition guarantees that the MacWilliams identities are satisfied. See "An Elementary Proof of the First LP Bound on the Rate of Binary Codes" by Nati Linial and Elyassaf Loyfer for more on this perspective (for disclosure, they are my collaborators).
  3. A precise perspective which constructs an exact eigenfunction (ultimately achieving the same asymptotic bound) is given in "Spectral Approach to Linear Programming Bounds on Codes" by Barg and Nogin.
$\endgroup$
11
$\begingroup$

For linear programming type bounds it is sometimes only possible to give effective bounds (that is bounds that work and are manageable) and what is surprising is that the primitive method often gives in fact optimal bounds.

The LP problem from McEliece, Rodemich, Rumsey and Welch's paper that is cited in the question requires the auxiliary function $\beta(x)$ satisfy $\beta(j) = 1+ \sum_{k=1}^{n} y_k K_k (j)\leq 0$ for all $j=d,d+1,\dots,n$. The supplied $\beta(x)$ is designed to meet this requirement by making it change sign at value $a$, so that $\beta(x)\leq 0$ for $x\geq a$. This is the first point.

The Krawtchouk polynomials already appear in the LP problem, so that there are no questions of why the might appear in the auxiliary function $\beta$, but just to emphasize the importance of the Krawtchouk polynomials, they are used in discrete linear programming problems due to the positive definiteness criterion associated to them, namely that for a polynomial $$f(z)=\sum\limits_{i=0}^{n} a_{i}z^{i}$$ the matrix $$f(d(x,y)),\ x,y\in\mathbb{F}^{n}$$ is non-negative definite if and only if all coefficients $\lambda_{i}$ of the expansion $f(z)=\sum\limits_{i=0}^{n} \lambda_{i} K_{i}(z)$ over Krawtouck polynomials are nonnegative.

Now, to keep all the coefficients $y_k$ positive as required in the LP program, it makes sense to introduce the square, but in order to preserve the sign change in $\beta(x)$ at $x=a$, one divides by $(a-x)$.

Finally, the choice of the exact expression inside the square works, because as was noted, the Christoffel-Darboux formula allows for rewriting

$$K_t(a) K_{t+1}(x) - K_{t+1}(a)K_{t}(x)=\frac{2(a-x)}{t+1}\binom{n}{t}\sum\limits_{k=0}^t \frac{K_{k}(x)K_{k}(a)}{\binom{n}{k}}$$

so that one may check quickly that $\beta(x)$ has expansion coefficients $y_{k}$ in the Krawtouck polynomials non-negative. Optimizing in $a$ and $t$ as noted give the MRRW upper bound $M_{LP}(n,d)\leq \binom{n}{t}\frac{(n+1)^2}{2(t+1)}$.

$\endgroup$
2
  • $\begingroup$ So the overall reason is that they saw the Chrisotoffel-Darboux expressions and had a clever inspiration? Maybe it's really just that. Let's see if someone has a better answer. $\endgroup$ Dec 27, 2018 at 5:04
  • $\begingroup$ @Breakfastisready Yes, essentially this is what is being suggested. This tool and the fact that the function $\beta(x)$ has the desired property of switching signs at $x=a$ seem to be ample motivation for choosing the above function. $\endgroup$ Dec 27, 2018 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.