Lower bound on the dimension of a subspace of $\mathbb Z_2^r$? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T17:40:15Z http://mathoverflow.net/feeds/question/120843 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120843/lower-bound-on-the-dimension-of-a-subspace-of-mathbb-z-2r Lower bound on the dimension of a subspace of $\mathbb Z_2^r$? rita 2013-02-05T08:13:27Z 2013-02-05T12:34:30Z <p>This question may be very trivial, I apologize if it is so.</p> <p>I have subspace $V\subset \mathbb Z_2^r$ with the property that for every choice of a subset $I$ of $k$ elements in <code>$\{1,2,\dots r\}$</code>, the projection of $V$ onto the corresponding $k$ coordinates is surjective. </p> <p>QUESTION: Can one find a lower bound on $\dim V$, apart from the obvious $\dim V\ge k$? </p> <p>In the case I'm interested in I have $k\ge \frac r 2$. </p> http://mathoverflow.net/questions/120843/lower-bound-on-the-dimension-of-a-subspace-of-mathbb-z-2r/120856#120856 Answer by Peter Mueller for Lower bound on the dimension of a subspace of $\mathbb Z_2^r$? Peter Mueller 2013-02-05T12:34:30Z 2013-02-05T12:34:30Z <p>Let $\pi_i:V\to\mathbb Z_2$ be the projection to the $i$-th coordinate. The $\pi_i$ are elements of the dual space $V^\star$, and by assumption, any $k$ of these $\pi_i$ are linearly independent. Let $C$ be subspace of $\mathbb Z_2^r$ consisting of those tuples $(a_1,\dots,a_r)$ such that $\sum a_i\pi_i=0$. So $C$ is a code of minimal Hamming distance $d\ge k$. On the other hand, $\dim C=r-\dim\langle\pi_i|i=1,2,\dots,r\rangle\ge r-\dim V^\star=r-\dim V$.</p> <p>Thus $\dim V\ge r-\dim C$. Now use some good bounds from error correcting codes. If $k$ is bigger than $r/2$, then the Plotkin bound gives good results, here $2^{\dim C}\le k/(k-r/2)$, which is much better than $\dim V\ge k$.</p> <p>If $k=r/2$, or $k\lt r/2$ then one can use the Griesmer bound, or other bounds if $k$ is small compared to $r$.</p>