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 ℓ {\displaystyle \ell } -wise independent source. That is, the set of vectors from the input vector space are mapped to an ℓ {\displaystyle \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 − ℓ {\displaystyle 1-2^{-\ell }} -approximation to MAXEkSAT.
Lemma Let C ⊆ F 2 n {\displaystyle C\subseteq F_{2}^{n}} be a linear code such that C ⊥ {\displaystyle C^{\perp }} has distance greater than ℓ + 1 {\displaystyle \ell +1} . Then C {\displaystyle C} is an ℓ {\displaystyle \ell } -wise independent source.
Proof of lemma It is sufficient to show that given any k × l {\displaystyle 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 ∈ F 2 k {\displaystyle x\in F_{2}^{k}} , x M {\displaystyle xM} takes every value in F 2 l {\displaystyle 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 {\displaystyle M_{1}} and M 2 {\displaystyle M_{2}} , where M 1 {\displaystyle M_{1}} has rank equal to l. This means that x M {\displaystyle xM} can be rewritten as x 1 M 1 + x 2 M 2 {\displaystyle x_{1}M_{1}+x_{2}M_{2}} for some x 1 {\displaystyle x_{1}} and x 2 {\displaystyle x_{2}} . If we consider M written with respect to a basis where the first l rows are the identity matrix, then x 1 {\displaystyle x_{1}} has zeros wherever M 2 {\displaystyle M_{2}} has nonzero rows, and x 2 {\displaystyle x_{2}} has zeros wherever M 1 {\displaystyle M_{1}} has nonzero rows. Now any value y, where y = x M {\displaystyle y=xM} , can be written as x 1 M 1 + x 2 M 2 {\displaystyle x_{1}M_{1}+x_{2}M_{2}} for some vectors x 1 , x 2 {\displaystyle x_{1},x_{2}} . We can rewrite this as:
x 1 M 1 = y − x 2 M 2 {\displaystyle x_{1}M_{1}=y-x_{2}M_{2}}
Fixing the value of the last k − l {\displaystyle k-l} coordinates of
x 2 ∈ F 2 k {\displaystyle x_{2}\in F_{2}^{k}} (note that there are exactly 2 k − l {\displaystyle 2^{k-l}}
such choices), we can rewrite this equation again as:
x 1 M 1 = b {\displaystyle x_{1}M_{1}=b} for some b. Since M 1 {\displaystyle M_{1}} has rank equal to l, there is exactly one solution x 1 {\displaystyle x_{1}} , so the total number of solutions is exactly 2 k − l {\displaystyle 2^{k-l}} , proving the lemma.
Corollary Recall that BCH2,m,d is an [ n = 2 m , n − 1 − ⌈ d − 2 / 2 ⌉ m , d ] 2 {\displaystyle [n=2^{m},n-1-\lceil {d-2}/2\rceil m,d]_{2}} linear code. Let C ⊥ {\displaystyle C^{\perp }} be BCH2,log n,ℓ+1. Then C {\displaystyle C} is an ℓ {\displaystyle \ell } -wise independent source of size O ( n ⌊ ℓ / 2 ⌋ ) {\displaystyle O(n^{\lfloor \ell /2\rfloor })} .
Proof of corollary The dimension d of C is just ⌈ ( ℓ + 1 − 2 ) / 2 ⌉ log n + 1 {\displaystyle \lceil {(\ell +1-2)/{2}}\rceil \log n+1} . So d = ⌈ ( ℓ − 1 ) / 2 ⌉ log n + 1 = ⌊ ℓ / 2 ⌋ log n + 1 {\displaystyle d=\lceil {(\ell -1)}/2\rceil \log n+1=\lfloor \ell /2\rfloor \log n+1} . So the cardinality of C {\displaystyle C} considered as a set is just
2 d = O ( n ⌊ ℓ / 2 ⌋ ) {\displaystyle 2^{d}=O(n^{\lfloor \ell /2\rfloor })} , proving the Corollary.
References Coding Theory notes at University at Buffalo Coding Theory notes at MIT