Skip to main content
2 of 2
edited body

How did they come up with the MRRW bound?

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?