Dual of BCH is an independent source

A certain family of BCH codes have a particularly useful property, which is that treated as linear operators, their dual operators turns their input into an $\ell$-wise independent source. That is, the set of vectors from the input vector space are mapped to an $\ell$-wise independent source. The proof of this fact below as the following Lemma and Corollary is useful in derandomizing the algorithm for a $1-2^{-\ell }$-approximation to MAXEkSAT.

Lemma

Let $C\subseteq F_{2}^{n}$ be a linear code such that $C^{\perp }$ has distance greater than $\ell +1$. Then $C$ is an $\ell$-wise independent source.

Proof of lemma

It is sufficient to show that given any $k\times l$ matrix M, where k is greater than or equal to l, such that the rank of M is l, for all $x\in F_{2}^{k}$, $xM$ takes every value in $F_{2}^{l}$ the same number of times.

Since M has rank l, we can write M as two matrices of the same size, $M_{1}$ and $M_{2}$, where $M_{1}$ has rank equal to l. This means that $xM$ can be rewritten as $x_{1}M_{1}+x_{2}M_{2}$ for some $x_{1}$ and $x_{2}$.

If we consider M written with respect to a basis where the first l rows are the identity matrix, then $x_{1}$ has zeros wherever $M_{2}$ has nonzero rows, and $x_{2}$ has zeros wherever $M_{1}$ has nonzero rows.

Now any value y, where $y=xM$, can be written as $x_{1}M_{1}+x_{2}M_{2}$ for some vectors $x_{1},x_{2}$.

We can rewrite this as:

$x_{1}M_{1}=y-x_{2}M_{2}$

Fixing the value of the last $k-l$ coordinates of $x_{2}\in F_{2}^{k}$ (note that there are exactly $2^{k-l}$ such choices), we can rewrite this equation again as:

$x_{1}M_{1}=b$ for some b.

Since $M_{1}$ has rank equal to l, there is exactly one solution $x_{1}$, so the total number of solutions is exactly $2^{k-l}$, proving the lemma.

Corollary

Recall that BCH_2,m,d is an $[n=2^{m},n-1-\lceil {d-2}/2\rceil m,d]_{2}$ linear code.

Let $C^{\perp }$ be BCH_{2,log n,ℓ+1}. Then $C$ is an $\ell$-wise independent source of size $O(n^{\lfloor \ell /2\rfloor })$.

Proof of corollary

The dimension d of C is just $\lceil {(\ell +1-2)/{2}}\rceil \log n+1$. So $d=\lceil {(\ell -1)}/2\rceil \log n+1=\lfloor \ell /2\rfloor \log n+1$.

So the cardinality of $C$ considered as a set is just $2^{d}=O(n^{\lfloor \ell /2\rfloor })$, proving the Corollary.

References

Coding Theory notes at University at Buffalo

Coding Theory notes at MIT