This is also used in Brakedown for its soundness proof. It's for general codes, so…
The main statement is that
\[\left\lVert \sum_{i=1}^n r_i x_i - V \right\rVert_0 \le q \implies X \text{ is } q\text{-close to } V\]
where \(r_i\) are random, with failure probability \(q/\lvert \mathbb{F} \rvert\).
To be more precise, we will assume that the distance from \(X\) to \(V\) is \(>q\) and show that
\[\text{Pr} \left( \left\lVert \sum_{i=1}^n r_ix_i - V \right\rVert_0 \le q \right) \le (q+1) / \lvert \mathbb{F} \rvert\]
Define \(\Delta(x, V)\) as the set of different indices from \(x\) to its closest vector in \(V\).
We first show the case \(q < d'/4\) with arbitrary \(n\). This is Lemma 4.2 in the paper.
Denote \(W = \text{span}(x_1, x_2, \cdots, x_n)\).
Create a basis of \(W\) including \(w\) - now a random vector in \(W\) can be written as \(\alpha w + x\) where the distribution of \(x\) is independent of \(\alpha \in \mathbb{F}\). The claim is that there is at most one \(\alpha\) such that \(\lVert \alpha w + x - V \rVert_0 \le q\) for each \(x\) - this will be sufficient to finish the proof.
Indeed, if there were more than one \(\alpha\), triangle inequality would show \(\lVert w - V \rVert_0 \le 2q\).
We are now in unique decoding radius. Therefore, we can write \(x_i = v_i + \delta_i\) with
\[v_i \in V, \quad \lVert \delta_i \rVert_0 \le 2q\]
Denote \(E_i\) to be the non-zero entry indices of \(\delta_i\), and let \(E = \cup E_i\). Note \(\lvert E \rvert > q\).
We claim that for each \(j \in E\), except with \(1/\lvert \mathbb{F} \rvert\) probability over random \(w \in W\) we have
\[ j \in \Delta(w, V) \lor \lVert w - V \rVert_0 > q\]
from which, via the union bound, the proof would be complete.
Say \(j \in E_i\) and write \(w = \alpha x_i + y\) with \(y\) being independent of \(\alpha\). Fixing \(y\), we show that at most one \(\alpha\) can satisfy both \(j \notin \Delta( \alpha x_i + y, V)\) and \(\lVert \alpha x_i + y - V \rVert_0 \le q\).
Once again, assume there are two \(\alpha, \alpha'\) that satisfy the conditions. We see that any linear combination \(\alpha x_i + y\) and \(\alpha' x_i + y\) has distance at most \(2q\) from \(V\) via triangle inequality. Since we are within unique decoding radius, the closest codeword itself is the linear combination of the two closest codeword as well. This implies that \(j\)th entry will always be equal between the linear combination and its closest codeword.
However, note that \(x_i\) is also a linear combination of \(\alpha x_i + y\) and \(\alpha' x_i + y\). This would imply that \(j \notin \Delta(x_i, V)\), but this is a contradiction as we already know \(j \in E_i\).
Assume otherwise and take \(w_0 \in W\) that maximizes the distance from \(V\). Since \(\lVert w_0 - V \rVert_0 \le q\), there exists an \(i\) such that \(\Delta(x_i, V) \setminus \Delta(w_0, V) \neq \emptyset\).
Set \(w_0 = v_0 + \delta_0\) and \(x_i = v_i + \delta_i\) with \(v_0, v_i \in V\) and \(\lVert \delta_0 \rVert_0, \lVert \delta_i \rVert_0 \le q\).
Now the idea is to take \(\alpha x_i + w_0 \in W\) to increase the distance from \(w_0\).
We know that there exists \(v' \in V\) such that
\[\lVert \alpha x_i + w_0 - v' \rVert_0 \leq q\]
but at the same time note that
\[\lVert \alpha x_i + w_0 - \alpha v_i - v_0 \rVert_0 \le 2q\]
and via triangle inequality and \(3q < d'\), we have \(v' = \alpha v_i + v_0\).
In other words, we have
\[\lVert (\alpha x_i + w_0) - V \rVert_0 = \lVert \alpha \delta_i + \delta_0 \rVert_0\]
so we can take an \(\alpha\) such that the one index in \(\Delta(x_i, V) \setminus \Delta(w_0, V)\) becomes non-zero, while all non-zero indexes in \(\delta_0\) stay non-zero. This is possible with sufficiently large \(\mathbb{F}\).
We arrive at a contradiction against the maximality of \(\lVert w_0 - V \rVert_0\).
Fix \(a, b \in \mathbb{F}^n\) and define \(l_{a, b} = \{a + t b : t \in \mathbb{F} \}\). The claim is that either
We note that performing the following operations do not change anything
Therefore, if there is \(a + tb\) that is \(q\)-close to \(V\), we change \(a\) to \(a + tb + v\) to make \(\lVert a \rVert_0 \le q\).
Assume
\[\lVert a \rVert_0 \le q, \quad \lVert a + t_1 b - V \rVert_0 \le q, \quad \lVert a + t_2b - V \rVert_0 \le q\]
and write
\[a = \delta_a, \quad a + t_1b = v_1 + \delta_1, \quad a + t_2b = v_2 + \delta_2\]
so \(\delta_a(t_1-t_2) + \delta_1 t_2 - \delta_2 t_1 \in V\) but this has at most \(3q < d'\) non-zero entries.
This forces \(t_1(\delta_2 - \delta_a) = t_2(\delta_1 - \delta_a)\) so setting \(\delta = (\delta_1 - \delta_a)/t_1 = (\delta_2 - \delta_a) / t_2\) and \(v = v_1 / t_1 = v_2 / t_2\) we have \(b = v + \delta\). At this point, we know that if \(a + tb\) is \(q\)-close to \(V\), we must have that the closest vector in \(V\) is simply \(tv\), and the distance will be \(\delta_a + t \delta\).
Denote \(NZ(v)\) to be non-zero entry indices of \(v\). We divide two cases.
The Case 1 is same. In Case 2, we begin by selecting \(w'\) such that \(\lVert w' - V \rVert_0 > q\) via Claim 1.
Now we can write all vectors in \(W\) as \(\alpha w' + x\) where \(x\) is independent of \(\alpha\).
Fix \(x\). By Claim 2, that there are at most \(d\) values of \(\alpha\) that \(\lVert \alpha w' + x - V \rVert_0 \le q\), so the result will follow. Note that this is the case where \(NZ(\delta)\) is guaranteed to have size \(>q\).
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe