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 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 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 for some vectors x_1, x_2. We can rewrite this as: Fixing the value of the last k-l coordinates of (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 BCH2,m,d is an linear code. Let C^\perp be BCH2,log n,ℓ+1. Then C is an \ell-wise independent source of size.

Proof of corollary

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