113 Error-Correcting Codes — MRRW Bound
113.1 Overview
This chapter formalizes the binary first McEliece–Rodemich–Rumsey–Welch (MRRW) bound on the asymptotic rate of binary codes: for every \(\delta \in [0,1/2]\),
where \(R\) is the asymptotic binary code rate and \(H\) is the binary entropy function. The development supplies the maximum code size \(A(n,d)\), the binary Krawtchouk polynomials (both as an explicit alternating sum and as genuine polynomials over \(\mathbb {R}\) defined by the three-term recurrence), Delsarte’s linear-programming bound, the truncated Christoffel–Darboux kernel \(\Phi _{n,t}\) together with its feasibility properties, and the asymptotic ingredients needed to assemble the main theorem.
113.2 Declarations
113.2.1 Statement and normalization
For naturals \(n\) and \(d\), \(A(n,d)\) is the supremum of the cardinalities \(k\) for which there is a finite set \(C\) of binary codewords \(\mathrm{Fin}\, n \to \mathrm{Bool}\) with \(|C| = k\) and such that any two distinct \(x, y \in C\) differ in at least \(d\) coordinates.
The binary entropy function
using the base-\(2\) logarithm, with the convention \(0\log _2 0 = 0\) inherited from \(\log _2 0 = 0\).
For \(\delta \in [0,1]\), the asymptotic rate is
113.2.2 Krawtchouk polynomials
For naturals \(n\), \(j\), \(x\),
where the subtraction \(n-x\) is natural-number subtraction; the definition gives the intended values for \(x \le n\).
The family of real polynomials defined by the three-term recurrence \(K_0 = 1\), \(K_1 = n - 2X\), and
extending the integer-argument definition to real arguments.
For all \(n\) and \(x\), \(K_0^{(n)}(x) = 1\).
For \(j \le n\), \(K_j^{(n)}(0) = \binom {n}{j}\).
For \(x \le n\), \(K_1^{(n)}(x) = n - 2x\).
For \(x \le n\) and every real \(z\),
For \(r \le n\) and \(s \le n\),
For \(1 \le j\), \(j + 1 \le n\) and \(x \le n\),
For \(j \le n\) and \(x \le n\), evaluating the polynomial \(K_j^{(n)}\) at the real number \(x\) gives the value \(K_j^{(n)}(x)\) of the alternating-sum definition.
113.2.3 Delsarte’s linear programming bound
Let \(F(x) = \sum _{j=0}^{n} F_j K_j^{(n)}(x)\) for real coefficients \(F_j\). If \(F_0 \gt 0\), if \(F_j \ge 0\) for all \(1 \le j \le n\), and if \(F(x) \le 0\) for every integer \(x\) with \(d \le x \le n\), then
113.2.4 Christoffel–Darboux kernel and feasibility
For \(t \le n\) and real \(a, x\), the truncated reproducing kernel is
For \(t + 1 \le n\) and real \(a \ne x\) there is a scalar \(c \gt 0\) with
Fix \(t + 1 \le n\) and a real \(a\) that is strictly smaller than every real zero \(\xi \) of \(K_t^{(n)}\). Then \(K_j^{(n)}(a) \gt 0\) for every \(j \le t\).
Under the same hypotheses (\(t + 1 \le n\) and \(a\) strictly below every real zero of \(K_t^{(n)}\)), there exists a threshold \(\eta \) such that \(\Phi _{n,t}(a,x) \le 0\) for every integer \(x\) with \(\eta \le x \le n\).
Let \(t + 1 \le n\), let \(a\) be strictly below every real zero of \(K_t^{(n)}\), and suppose \(\Phi _{n,t}(a,x) \le 0\) for every integer \(x\) with \(d \le x \le n\). Then
113.2.5 Asymptotic choice of parameters
Let \(0 \lt \tau \lt 1/2\) and let \(t_n\) satisfy \(t_n / n \to \tau \). Then there is a sequence \(a_n\) such that, eventually in \(n\), \(a_n\) lies strictly below every real zero of \(K_{t_n}^{(n)}\), with \(a_n/n \to \tfrac 12 - \sqrt{\tau (1-\tau )}\), and such that eventually \(\Phi _{n,t_n}(a_n,x) \le 0\) for all integers \(x\) with \(\lfloor (\tfrac 12 - \sqrt{\tau (1-\tau )})n \rfloor \le x \le n\).
Let \(0 \lt \tau \lt 1/2\), let \(t_n/n \to \tau \), and let \(a_n\) eventually lie strictly below every real zero of \(K_{t_n}^{(n)}\). Then
For \(0 \le \tau \le 1/2\),
113.2.6 Conclusion of the MRRW bound
For \(0 \le \delta \le 1/2\), setting \(\tau = \tfrac 12 - \sqrt{\delta (1-\delta )}\) gives back \(\delta = \tfrac 12 - \sqrt{\tau (1-\tau )}\); that is, the map is an involution on \([0,1/2]\).
\(H(0) = 0\).
\(H(1/2) = 1\).
For every \(\delta \) with \(0 \le \delta \le 1/2\),