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 -wise independent source. That is, the set of vectors from the input vector space are mapped to an -wise independent source. The proof of this fact below as the following Lemma and Corollary is useful in derandomizing the algorithm for a -approximation to MAXEkSAT.

Lemma

Let be a linear code such that has distance greater than. Then is an -wise independent source.

Proof of Lemma

It is sufficient to show that given any matrix M, where k is greater than or equal to l, such that the rank of M is l, for all, takes every value in the same number of times.
Since M has rank l, we can write M as two matrices of the same size, and, where has rank equal to l. This means that can be rewritten as for some and.
If we consider M written with respect to a basis where the first l rows are the identity matrix, then has zeros wherever has nonzero rows, and has zeros wherever has nonzero rows.
Now any value y, where, can be written as for some vectors.
We can rewrite this as:
Fixing the value of the last coordinates of
, we can rewrite this equation again as:
for some b.
Since has rank equal to l, there
is exactly one solution, so the total number of solutions is exactly, proving the lemma.

Corollary

Recall that BCH2,m,d is an linear code.
Let be BCH2,log n,ℓ+1. Then is an -wise independent source of size.

Proof of Corollary

The dimension d of C is just. So.
So the cardinality of considered as a set is just
, proving the Corollary.