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₁ and M₂, where M₁ has rank equal to l. This means that xM can be rewritten as x₁M₁ + x₂M₂ for some x₁ and x₂.

If we consider M written with respect to a basis where the first l rows are the identity matrix, then x₁ has zeros wherever M₂ has nonzero rows, and x₂ has zeros wherever M₁ has nonzero rows.

Now any value y, where y = xM, can be written as x₁M₁ + x₂M₂ for some vectors x₁,x₂.

We can rewrite this as:

x₁M₁ = y − x₂M₂

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₁M₁ = b for some b.

Since M₁ has rank equal to l, there is exactly one solution x₁, 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