Johnson beyond Johnson
The Johnson bound is well known to anyone working on hash-based proof systems. With minimal assumptions it achieves a very useful list size bound for a non-trivial range beyond the unique decoding radius, up to the Johnson radius 1 - \sqrt{1 - \delta}.
It has always bothered me that standard presentations stop so abruptly at the Johnson radius. Here I’ll show how the same geometric argument naturally continues beyond it, using Better.codes as a running example.
Error Correcting Codes
In this post we assume generic codes, not necessarily MDS or even linear. These results therefore hold on very weak assumptions (yet despite this they are some of the strongest used in practice).
Definition 1. (Code) Let \Sigma be an alphabet of size q > 1, a q-ary code of length n is a subset \mathcal{C} \subseteq \Sigma^{n}. Define the Hamming distance of two words a,b \in \Sigma^{n} as
\mathrm{d}(a,b) = |\left\{ i \in \lbrack n\rbrack:a_{i} \neq b_{i} \right\}|
then the minimum distance of the code is
d = \min\limits_{a,b \in \mathcal{C} \land a \neq b}\mathrm{d}(a,b).
Definition 2. (List decoding) Given a word w \in \Sigma^{n}, the list at decoding radius e is
\mathrm{L}(w,e) = \left\{ c \in \mathcal{C}:\mathrm{d}(w,c) \leq e \right\}
The maximum list size is
\mathrm{L}(e) = \max\limits_{w \in \Sigma^{n}}|\mathrm{L}(w,e)|
It is customary to work in units relative to n, define the relative minimum distance \delta = \frac{d}{n} and relative decoding radius \tau = \frac{e}{n}. We will use this interchangeably, e.g. in \mathrm{L}(\tau).
Example. For the code from the better.codes competition, the parameters are
\begin{aligned} q & = \left( 2^{31} - 2^{24} + 1 \right)^{6} & n & = 2^{18} \\ d & = 2^{17} + 1 & \delta & = \frac{1}{2} + 2^{- 18}. \end{aligned}
We are interested in upper bounds on the maximum list size for a given q-ary code of length n with minimum distance d.
Unique Decoding Bound
Theorem 3. (Unique Decoding Bound) Define the unique decoding radius by
e_{U} = \left\lfloor \frac{d - 1}{2} \right\rfloor
then for e \leq e_{U} we have
\mathrm{L}(e) \leq 1.
Proof. To see this, fix w \in \Sigma^{n}. If a,b \in \mathrm{L}(w,e), then by the triangle inequality
\mathrm{d}(a,b) \leq \mathrm{d}(a,w) + \mathrm{d}(w,b) \leq 2e_{U} = 2\left\lfloor \frac{d - 1}{2} \right\rfloor < d.
Thus a = b by the definition of the minimum distance, so |\mathrm{L}(w,e)| \leq 1.
This bound is perfectly tight as a universal minimum-distance bound, but it is only valid up to the unique decoding radius \tau_{U} \approx \frac{\delta}{2}.
Example. For better codes the unique decoding radius is
\begin{aligned} e_{U} & = 2^{16} = 65536 & \tau_{U} & = 0.25. \end{aligned}
The competition seeks the largest \tau proven safe. Given a certified \tau, the score is computed as - 128\log_{2}(1 - \tau) rounded down to the nearest one-hundredth. Assuming we can show the unique decoding regime safe (we can), the maximum achievable score is
- 128\log_{2}\left( 1 - \tau_{U} \right) = 53.12.
And indeed this was the score the competition started at.
Johnson Bound
Definition 4. (Johnson Bound) Define the Johnson radius by
\tau_{J} = 1 - \sqrt{1 - \delta}
with integer bound \begin{aligned} e_{J} & = \left\lceil {n\tau_{J}} \right\rceil - 1 \end{aligned}. For e \leq e_{J}, the maximum list size satisfies
\mathrm{L}(\tau) \leq \frac{\delta - \tau}{\delta - 2\tau + \tau^{2}}.
What now follows is the linear agreement-set proof of the Johnson bound which is slightly stronger than the more common q-ary combinatorial bound (see appendix). This results in the additional - \tau term in the numerator. It will also set us up for the Delsarte LP proof that follows next.
Proof. Fix w \in \Sigma^{n} and consider \mathrm{L}(w,e). Let L = |\mathrm{L}(w,e)| and enumerate the list words \mathrm{L}(w,e) = \left\{ c_{1},\ldots,c_{L} \right\}. By definition each list word agrees with w on at least a = n - e coordinates. For each list word i \in \lbrack L\rbrack choose exactly a agreement coordinates such that
\begin{array}{rlr} A_{i} & \subseteq \left\{ j:c_{i,j} = w_{j} \right\} & |A_{i}| = a \end{array}
Now define agreement indicator vectors \mathbf{1}_{A_{i}} \in {\mathbb{R}}^{n} such that
\left( \mathbf{1}_{A_{i}} \right)_{j} = \begin{cases} 1 & \text{if }j \in A_{i} \\ 0 & \text{otherwise}. \end{cases}
These vectors have fixed coordinate sum \sum_{j}\mathbf{1}_{A_{i}} = a and norm \left\| \mathbf{1}_{A_{i}} \right\| = \sqrt{a}. Define normalized centered vectors
{\mathbf{a}}_{i} = \sqrt{\frac{n}{ae}}\left( \mathbf{1}_{A_{i}} - \frac{a}{n}\mathbf{1} \right)
such that \sum_{j}\left( {\mathbf{a}}_{i} \right)_{j} = 0 and \left\| {\mathbf{a}}_{i} \right\| = 1. Furthermore we have
\langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle = \frac{n|A_{i} \cap A_{j}| - a^{2}}{ae}
Since distinct codewords have distance at least d, we have
|A_{i} \cap A_{j}| \leq n - d.
Therefore, for distinct i,j, \langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle \leq \rho ≔ \frac{n(n - d) - a^{2}}{ae}
Now use positive-definiteness of the inner product:
\begin{array}{rlr} 0 & \leq \sum_{i,j \in \lbrack L\rbrack}\langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle & = \sum_{i \in \lbrack L\rbrack}\left\| {\mathbf{a}}_{i} \right\|^{2} + \sum_{\substack{ i,j \in \lbrack L\rbrack \\ i \neq j }}\langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle \\ & \leq L + L(L - 1)\rho \end{array}
For \rho < 0 it follows
L \leq 1 - \frac{1}{\rho}
which, after expanding \rho and simplifying is
L \leq \frac{n(d - e)}{nd - 2ne + e^{2}}
The condition \rho < 0 is satisfied when \begin{aligned} a^{2} & > n(n - d) \end{aligned}, which simplifies to
\frac{e}{n} < 1 - \sqrt{1 - \frac{d}{n}}.
Example. For better codes the Johnson radius is \begin{aligned} e_{J} & = 76780 & \tau_{J} & \approx 0.2929. \end{aligned}
Assuming we can show the Johnson radius safe (we can get very close), the maximum achievable score is
- 128\log_{2}\left( 1 - \frac{e_{J}}{n} \right) = 63.99.
And indeed this was where the competition ended up on the second day. Though the actual radius proven safe is 76770, a little below the Johnson radius.
Delsarte LP Bound
We can make the Johnson bound stronger by augmenting the sum
\sum_{i,j \in \lbrack L\rbrack}\langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle
with a polynomial p that preserves the useful bound, i.e. we will instead use
\sum_{i,j \in \lbrack L\rbrack}p\left( \langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle \right).
To make this work we need a result from spherical harmonics:
Definition 5. (Gegenbauer Kernels) Fix D = n - 1 > 2. The Gegenbauer kernels K_{r}(t) in dimension D are polynomials defined by
\begin{aligned} K_{0}(t) & = 1 & K_{1}(t) & = t \end{aligned}
and for r \geq 1
\begin{aligned} K_{r + 1}(t) & = tK_{r}(t) - \frac{r(r + D - 3)}{(2r + D - 2)(2r + D - 4)}K_{r - 1}(t). \end{aligned}
In particular, \begin{aligned} K_{2}(t) & = t^{2} - \frac{1}{D} \\ K_{3}(t) & = t^{3} - \frac{3}{D + 2}t \end{aligned}
These polynomials have the following useful property:
Theorem 6. (Gegenbauer positive-definiteness) Let {\mathbf{a}}_{1},\ldots,{\mathbf{a}}_{L} \in S^{D - 1}. For every r \geq 0, define
\mathrm{M}_{ij} = K_{r}\left( \langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle \right)
then \mathrm{M} is positive semidefinite. In particular
\sum_{i,j \in \lbrack L\rbrack}K_{r}\left( \langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle \right) \geq 0.
Theorem 7. (Delsarte LP bound) Assume 0 < \tau < 1 and define the inner-product cap
\rho(\tau) = \frac{\delta - 2\tau + \tau^{2}}{\tau^{2} - \tau}
and let p(t) be a polynomial of degree \leq m such that
\begin{aligned} p(t) & = \sum_{r \in \lbrack 0,m\rbrack}c_{r}K_{r}(t) \\ c_{0} & > 0 \\ c_{r} & \geq 0\text{ for all }r \in \lbrack 1,m\rbrack \\ p(t) & \leq 0\text{ for all }t \in \lbrack - 1,1\rbrack\text{ where }t \leq \rho(\tau). \end{aligned}
Then the Delsarte LP bound witnessed by p is
\mathrm{L}(\tau) \leq \frac{p(1)}{c_{0.}}
Proof. Define centered normalized agreement vectors {\mathbf{a}}_{i} as before in the Johnson proof and recall that for i \neq j,
\langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle \leq \rho.
Consider the sum
\begin{aligned} \sum_{i,j \in \lbrack L\rbrack}p\left( \langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle \right) & = \sum_{r \in \lbrack 0,m\rbrack}\sum_{i,j \in \lbrack L\rbrack}c_{r}K_{r}\left( \langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle \right) \\ & = c_{0}L^{2} + \sum_{r \in \lbrack 1,m\rbrack}\sum_{i,j \in \lbrack L\rbrack}c_{r}K_{r}\left( \langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle \right) \\ & \geq c_{0}L^{2} \end{aligned}
where we used the fact that K_{0}(t) = 1 and the nonnegativity of each K_{r} contribution.
Simultaneously, we can split the sum in diagonal and off-diagonal terms
\begin{aligned} \sum_{i,j \in \lbrack L\rbrack}p\left( \langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle \right) & = \sum_{i \in \lbrack L\rbrack}p\left( \langle{\mathbf{a}}_{i},{\mathbf{a}}_{i}\rangle \right) + \sum_{\substack{ i,j \in \lbrack L\rbrack \\ i \neq j }}p\left( \langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle \right) \\ & \leq p(1)L \end{aligned}
where we used that fact that \langle{\mathbf{a}}_{i},{\mathbf{a}}_{i}\rangle = 1 and p\left( \langle{\mathbf{a}}_{i},{\mathbf{a}}_{j}\rangle \right) \leq 0 when i \neq j.
We therefore have c_{0}L^{2} \leq p(1)L and hence L \leq \frac{p(1)}{c_{0}}.
Setting p(t) = t - \rho recovers the Johnson bound. We have p(1) = 1 - \rho and c_{0} = - \rho and thus L \leq \frac{1 - \rho}{- \rho} = 1 - \frac{1}{\rho} = \frac{\delta - \tau}{\delta - 2\tau + \tau^{2}}
This is valid when c_{0} > 0 and hence \rho < 0
\begin{aligned} \frac{\delta - 2\tau + \tau^{2}}{\tau^{2} - \tau} & < 0. \end{aligned}
Since 0 < \tau < 1 the denominator is negative. So we need \begin{aligned} \delta - 2\tau + \tau^{2} & > 0 \end{aligned} which has root \tau_{J} = 1 - \sqrt{1 - \delta}.
We can attempt to find higher degree solutions numerical. For this we normalize c_{0} = 1 and either use a grid for p(t) \leq 0 or use an exchange method where we dynamically add t points. But for better codes the resulting linear programming problem is very ill-conditioned, which is not fixed by a simple rescaling or change of basis. We can find a cubic solution though:
Example. For better codes a numerical m = 3 Delsarte LP solution at e = 76855
\begin{aligned} c_{0} & = & 1 & , \\ c_{1} & = & 40795 & .7498822753, \\ c_{2} & = & 10196244 & .2707756, \\ c_{3} & = & 5282724690 & .85052. \end{aligned}
gives a list bound of
\mathrm{L}(e) \leq 5292901238 \approx 2^{32.3}.
Note that this is solved using a grid search for p(t), which is not by itself a proof that the solution satisfies.
Assuming we can prove the numerical bound (we can) and also prove a safe MCA (we currently can’t), this would result in a score of 64.07.
Levenshtein Polynomials
The cubic is not an isolated trick. Levenshtein identified the optimal auxiliary polynomial of each bounded degree, with the active degree increasing as the decoding radius grows. For each degree bound m and \tau in a corresponding interval, the truncated Delsarte LP has an explicit optimal solution called a Levenshtein polynomial. As m increases, these intervals cover the full range corresponding to \tau < \delta. Thus the hierarchy extends up to the minimum-distance threshold. For MDS codes, \delta = 1 - R + \frac{1}{n}, so this threshold approaches the list-decoding capacity 1 - R asymptotically.
Example. Levenshtein bounds for the Better.codes parameters. At the integer radii shown here, only odd degrees become active; the intervening even-degree intervals are too narrow to contain at most one integer radius.
Conclusion
The Johnson bound is interesting because of how few assumptions it makes on the code. It does not even assume linearity! Yet despite this, stronger bounds based on stronger assumptions are surprisingly hard to obtain for the codes of interest in hash-based commitment schemes. This shows how strong the finite geometry argument is.
As we have seen the Johnson bound does not have to end abruptly and can be naturally extended. This extension however quickly diverges into very large list sizes. There is obviously some slack remaining, as the bound does not converge to 1 at the unique decoding radius, but I also suspect this is where stronger assumptions will have to come in.
Appendix: q-ary Johnson Bound
Definition 8. (q-ary Johnson Bound) Assuming \delta < \frac{q - 1}{1}, define the Johnson radius by
\begin{aligned} e_{J}' & = n\left( \frac{q - 1}{q} \right)\left( 1 - \sqrt{1 - \frac{q}{q - 1}\frac{d}{n}} \right) \end{aligned}
with integer bound \begin{aligned} e_{J} & = \left\lceil {e_{J}'} \right\rceil - 1 \end{aligned}. For e \leq e_{J}, the maximum list size satisfies
\mathrm{L}(e) \leq \frac{d}{d - 2e + \frac{q}{q - 1}\frac{e^{2}}{n}}.
This is typically presented with relative distances in the limit of large q \begin{aligned} \tau & < 1 - \sqrt{1 - \delta} & \mathrm{L}(\tau) & \leq \frac{\delta}{\delta - 2\tau\left( 1 - \frac{\tau}{2} \right)}. \end{aligned}
Proof. Fix w \in \Sigma^{n} and consider \mathrm{L}(w,e). Let L = |\mathrm{L}(w,e)|. For coordinate i and a \in \Sigma define
N_{i,a} = |\left\{ c \in \mathrm{L}(w,e):c_{i} = a \right\}|,
the number of list words having letter a at coordinate i. Let
t_{i} = \sum_{\substack{ a \in \Sigma \\ a \neq w_{i} }}N_{i,a} = L - N_{i,w_{i}}
be the number of list words having an error at coordinate i. Since every word has at most e errors, we have
\sum_{i}t_{i} \leq Le
Now count coordinate agreements between pairs of list words:
P = \sum_{i \in \lbrack n\rbrack}\sum_{a \in \Sigma}\binom{N_{i,a}}{2}
Because distinct codewords have at least d different coordinates, every pair agrees in at most n - d coordinates. Therefore
P \leq \binom{L}{2}(n - d) = \left( \frac{L^{2} - L}{2} \right)(n - d)
Recall the Cauchy-Schwarz bound for arbitrary k \in {\mathbb{N}} and a \in {\mathbb{N}}^{k}:
\left( \sum_{j \in \lbrack k\rbrack}a_{j} \right)^{2} \leq k\sum_{j \in \lbrack k\rbrack}a_{j}^{2}
and apply this for a fixed coordinate i as
\left( \sum_{\substack{ a \in \Sigma \\ a \neq w_{i} }}N_{i,a} \right)^{2} \leq (q - 1)\sum_{\substack{ a \in \Sigma \\ a \neq w_{i} }}N_{i,a}^{2}
and hence
\sum_{\substack{ a \in \Sigma \\ a \neq w_{i} }}N_{i,a}^{2} \geq \frac{t_{i}^{2}}{q - 1}.
Adding the a = w_{i} contribution back using N_{i,w_{i}} = L - t_{i} we get
\sum_{a \in \Sigma}N_{i,a}^{2} \geq \frac{t_{i}^{2}}{q - 1} + \left( L - t_{i} \right)^{2.}
From the binomial identity \binom{x}{2} = \frac{x^{2} - x}{2} we have
\sum_{a \in \Sigma}\binom{N_{i,a}}{2} = \frac{1}{2}\left( \sum_{a \in \Sigma}N_{i,a}^{2} - L \right).
where we used \sum_{a \in \Sigma}N_{i,a} = L.
Inserting our bound on \sum_{a \in \Sigma}N_{i,a}^{2} we get
\sum_{a \in \Sigma}\binom{N_{i,a}}{2} \geq \frac{1}{2}\left( \frac{t_{i}^{2}}{q - 1} + \left( L - t_{i} \right)^{2} - L \right).
Summing over i we get
P \geq \frac{1}{2}\sum_{i \in \lbrack n\rbrack}\left( \frac{t_{i}^{2}}{q - 1} + \left( L - t_{i} \right)^{2} - L \right).
Let
\overline{t} = \frac{1}{n}\sum_{i \in \lbrack n\rbrack}t_{i}
and define
f(t) = \frac{t^{2}}{q - 1} + (L - t)^{2} - L.
Since f is convex, Jensen’s inequality gives
\sum_{i \in \lbrack n\rbrack}f\left( t_{i} \right) \geq nf\left( \overline{t} \right).
In the Johnson range we have \frac{e}{n} < \frac{q - 1}{q}, and f is decreasing up to \frac{L(q - 1)}{q}. Since \overline{t} \leq L\frac{e}{n}, it follows that f\left( \overline{t} \right) \geq f\left( L\frac{e}{n} \right) and hence
P \geq \frac{n}{2}\left( \frac{\left( L\frac{e}{n} \right)^{2}}{q - 1} + \left( L - L\frac{e}{n} \right)^{2} - L \right).
Combining both P constraints we have
\begin{aligned} \frac{n}{2}\left( \frac{\left( L\frac{e}{n} \right)^{2}}{q - 1} + \left( L - L\frac{e}{n} \right)^{2} - L \right) & \leq \left( \frac{L^{2} - L}{2} \right)(n - d) \end{aligned} \begin{aligned} L & \leq \frac{\frac{d}{n}}{\left( \frac{d}{n} \right) - 2\left( \frac{e}{n} \right) + \left( \frac{q}{q - 1} \right)\left( \frac{e}{n} \right)^{2}} \end{aligned}
