Misplaced Pages

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 ${\displaystyle 1-2^{-\ell }}$-approximation to MAXEkSAT.

Lemma

Let ${\displaystyle C\subseteq F_{2}^{n}}$ be a linear code such that ${\displaystyle C^{\perp }}$ has distance greater than ${\displaystyle \ell +1}$. Then ${\displaystyle C}$ is an ${\displaystyle \ell }$-wise independent source.

Proof of lemma

It is sufficient to show that given any ${\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 ${\displaystyle x\in F_{2}^{k}}$, ${\displaystyle xM}$ takes every value in ${\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, ${\displaystyle M_{1}}$ and ${\displaystyle M_{2}}$, where ${\displaystyle M_{1}}$ has rank equal to l. This means that ${\displaystyle xM}$ can be rewritten as ${\displaystyle x_{1}M_{1}+x_{2}M_{2}}$ for some ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$.

If we consider M written with respect to a basis where the first l rows are the identity matrix, then ${\displaystyle x_{1}}$ has zeros wherever ${\displaystyle M_{2}}$ has nonzero rows, and ${\displaystyle x_{2}}$ has zeros wherever ${\displaystyle M_{1}}$ has nonzero rows.

Now any value y, where ${\displaystyle y=xM}$, can be written as ${\displaystyle x_{1}M_{1}+x_{2}M_{2}}$ for some vectors ${\displaystyle x_{1},x_{2}}$.

We can rewrite this as:

${\displaystyle x_{1}M_{1}=y-x_{2}M_{2}}$

Fixing the value of the last ${\displaystyle k-l}$ coordinates of ${\displaystyle x_{2}\in F_{2}^{k}}$ (note that there are exactly ${\displaystyle 2^{k-l}}$ such choices), we can rewrite this equation again as:

${\displaystyle x_{1}M_{1}=b}$ for some b.

Since ${\displaystyle M_{1}}$ has rank equal to l, there is exactly one solution ${\displaystyle x_{1}}$, so the total number of solutions is exactly ${\displaystyle 2^{k-l}}$, proving the lemma.

Corollary

Recall that BCH_2,m,d is an ${\displaystyle _{2}}$ linear code.

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

Proof of corollary

The dimension d of C is just ${\displaystyle \lceil {(\ell +1-2)/{2}}\rceil \log n+1}$. So ${\displaystyle d=\lceil {(\ell -1)}/2\rceil \log n+1=\lfloor \ell /2\rfloor \log n+1}$.

So the cardinality of ${\displaystyle C}$ considered as a set is just ${\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

• Article proofs