1
$\begingroup$

What is the minimal size of $S \subset \mathbb{F}_2^n \setminus \{0\}$ so that for any codimension $k$ subspace $W \subset \mathbb{F}_2^n$, there exists $s \in S$ such that $s \in W$? We can assume that $k$ is $O(1)$.

I thought about this for a while and cannot seem to get a good size. I know we have $\binom{n}{k}_2$ many subspaces, but choosing one vector per subspace is not correct as there is significant overlap between these subspaces. I'd be happy just showing that $|S|$ is $o(2^n)$, although I'm not even sure that is true.

$\endgroup$
1
$\begingroup$

Not a sharp result, but if $T$ is any $k+1$ dimensional subspace, then $S:=T- \{0\}$ will do, because $W$ must intersect $T$ non-trivially (the sum of the dimensions is bigger than the ambient space). $T$ has $2^{k+1}$ elements, so $|S|=2^{k+1}-1$, which is an upper bound for your question.

Edit: In the case $k=n-1$, the space $W$ is 1 dimensional, which in $\mathbb{F}_2^n$ is just a single vector (and the zero vector). Thus in this case, $S$ has to be the entire space (except zero), so $|S|=2^{k+1}-1$, suggesting that the above result may be optimal, at least asymptotically in $k$.

$\endgroup$
  • $\begingroup$ I agree. I think this is best possible. $\endgroup$ – Stefan G. Oct 29 '19 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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