MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question may be very trivial, I apologize if it is so.

I have subspace $V\subset \mathbb Z_2^r$ with the property that for every choice of a subset $I$ of $k$ elements in $\{1,2,\dots r\}$, the projection of $V$ onto the corresponding $k$ coordinates is surjective.

QUESTION: Can one find a lower bound on $\dim V$, apart from the obvious $\dim V\ge k$?

In the case I'm interested in I have $k\ge \frac r 2$.

share|cite|improve this question
up vote 7 down vote accepted

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$.

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$.

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$.

share|cite|improve this answer
This is very interesting, thank you! – rita Feb 5 '13 at 18:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.