# 1/3: [Ligero](https://eprint.iacr.org/2022/1608.pdf)'s Proof for $q < d'/3$

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$.

## Lemma 4.2: $q < d' / 4$

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)$.

### Case 1: There is $w \in W$ such that $\lVert w - V \rVert_0 > 2q$

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$.

### Case 2: For all $w \in W$, $\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$.

## Lemma 4.4: $q < d'/3$

### Claim 1: There eixsts $w' \in W$ such that $\lVert w' - V \rVert_0 > q$

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$.

### Claim 2: "Proximity Gap over a Line"

Fix $a, b \in \mathbb{F}^n$ and define $l_{a, b} = \{a + t b : t \in \mathbb{F} \}$. The claim is that either
- all vectors in $l_{a, b}$ is $q$-close to $V$
- at most $d$ vectors in $l_{a, b}$ is $q$-close to $V$

We note that performing the following operations do not change anything
- $a \leftarrow a + t b + v$ where $v \in V$
- $b \leftarrow t b + v$ where $v \in V$

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.

- If $NZ(\delta_a) \cup NZ(\delta)$ has size $\le q$, then $\lVert \delta_a + t \delta \rVert_0 \le q$ always.
- If $NZ(\delta_a) \cup NZ(\delta)$ has size $> q$, then cancellation has to occur, but this happens for at most $\lVert \delta_a \rVert_0 \le q$ values of $t$, which lead to at most $q$ vectors that are $q$-close to $V$.

### Finishing

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$.