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^$-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^$
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^$, proving the lemma.

Corollary

Recall that BCH_{2,''m'',''d''} is an =2^m, n-1 -\lceil /2\rceil m, d2 linear code.

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

Proof of corollary

The dimension ''d'' of ''C'' is just $\lceil\rceil \log n +1$. So $d = \lceil /2\rceil \log n +1 = \lfloor \ell/2 \rfloor \log n +1$.

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

References

Coding Theory notes at University at BuffaloCoding Theory notes at MIT

Article proofs