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_1M_1 + x_2M_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_1M_1+x_2M_2$ for some vectors $x_1, x_2$ .

We can rewrite this as:

$x_1M_1 = y - x_2M_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_1M_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