4 Various Papers 4.5 Interleaved Linear Code Testing with Logarithmic Randomness 4.7 Bulletproof

4.6 Basefold Random Linear Foldable Code and the Distance Proof

Lemma 4.6.1 (Lemma 2 [CF24]).

Fix any generator matrix $\mathbf{G}_{d-1}$ where the encoding of any nonzero message $\mathbf{m}\in\mathbb{F}^{k_{d-1}}$ has fewer than $t_{d-1}$ zeroes. For any subset $S\subseteq[1,n_{d-1}]$ ,

•

if $\left|S\right|<t_{d-1}$ , then $\left|m_{d}(S)\right|<\left|\mathbb{F}\right|^{2(t_{d-1}-\left|S\right|)}$ ,
•

if $\left|S\right|\geq t_{d-1}$ , then $\left|m_{d}(S)\right|=1$ .

Proof.

When $\left|S\right|\geq t_{d-1}$ , only $\mathbf{m}=\boldsymbol{0}$ can make all alphabets over $S$ being 0. Hence, $\dim\ker\left(G_{d-1,S}^{\mathsf{T}}\right)=0$ , $\left|m_{d}(S)\right|=1$ .

Let $T\subseteq[1,n_{d-1}]\setminus S$ of size $t_{d-1}-\left|S\right|$ . We first have

	$\displaystyle\mathrm{rank}(G_{d-1,T\cup S}^{\mathsf{T}})$	$\displaystyle\leq\mathrm{rank}\left(G_{d-1,S}^{\mathsf{T}}\right)+\mathrm{rank% }\left(G_{d-1,T}^{\mathsf{T}}\right)$
		$\displaystyle\leq\mathrm{rank}\left(G_{d-1,S}^{\mathsf{T}}\right)+(t_{d-1}-% \left\|S\right\|).$

By Rank-Nullity,

k_{d-1}=\mathrm{rank}\left(G_{d-1,T\cup S}^{\mathsf{T}}\right)+\dim\ker\left(G% _{d-1,T\cup S}^{\mathsf{T}}\right),

since the linear code alphabets over $T\cup S$ is $\boldsymbol{0}$ iff $\mathbf{m}=\boldsymbol{0}$ ¹⁹¹⁹19 or by $t_{d-1}\geq k_{d-1}$ as $n_{d-1}-t_{d-1}+1$ is the distance of the $(d-1)^{\mathrm{th}}$ level linear code, which is no more than $n_{d-1}-k_{d-1}+1$ by MDS code. , then

\dim\ker\left(\mathbf{G}_{d-1,T\cup S}^{\mathsf{T}}\right)=0,

hence $\mathrm{rank}\left(G_{d-1,T\cup S}^{\mathsf{T}}\right)=k_{d-1}$ , and $\mathrm{rank}\left(G_{d-1,S}^{\mathsf{T}}\right)\geq k_{d-1}-\left(t_{d-1}-% \left|S\right|\right)$ . Again by Rank-Nullity,

k_{d-1}=\mathrm{rank}\left(G_{d-1,S}^{\mathsf{T}}\right)+\dim\ker\left(G_{d-1,% S}^{\mathsf{T}}\right),

and hence,

\dim\ker\left(G_{d-1,S}^{\mathsf{T}}\right)\leq t_{d-1}-\left|S\right|,

which completes the proof, that $\left|m_{d}(S)\right|\leq\left|F\right|^{2(t_{d-1}-\left|S\right|)}$ . ∎

TODO: basefold stuffs [CF24].