Smallest set of nonzero vectors in $\mathbb F_2^n$ which intersects every 2-dimensional subspace

Question

What is the smallest set of nonzero vectors in $\mathbb F_2^n$ which intersects every 2-dimensional subspace?

For example, for n = 3, the set {001, 010, 011} does the job, and is minimal. For n = 4, {0001,0010,0011,1000,1001,1010,1011} does the job.

This is a special case of the Minimum Hitting Set problem (and equivalently, Minimum Set Cover), which is known to be hard in general. However, it is such a special case that I wonder if more can be said. I have not had much luck finding existing results on the question, and trying to find the numbers by computer power does not seem easy, even for modest values of n. My best results for $n$=5 and $n$=6 are sets of size 16 and 44, respectively, but I am not certain those are minimal. That might suggest A129045, but I know the answer for $n$=7 is much less than 134.

There are obvious generalizations – if you can answer the question for $k$-dimensional subspaces of $\mathbb F_q^n$, so much the better, but the particular case I have mentioned seems like a good starting point to me.

Most of all, I would appreciate links to existing literature! Thanks.

Answer 1

$2^{n-1}-1$.

Let $H$ be a codimension one subspace of the $n$-dimensional vector space $V$. Then the intersection of $S$ with any $2$-dimensional subspace has dimension at least one, so that $H-0$ is a set of the kind you are asking about.

Conversely suppose that $S$ is a set of nonzero vectors intersecting every $2$-dimensional subspace. If $S$ does not have every nonzero vector in it, then say that it does not have $v$ and let $L$ be the one-dimensional subspace spanned by $v$. The image of $S$ in $V/L$ intersects every one-dimensional subspace nontrivially, so it has at least $2^{n-1}-1$ elements.

EDIT: More generally if $S$ is a set of nonzero vectors intersecting each $d$-dimensional subspace then $S$ has at least $2^{n-d+1}-1$ elements. Proof: Wlog $d$ is minimal. Choose a $(d-1)$-dimensional subspace $W$ of $V$ disjoint from $S$. The image of $S$ in $V/W$ has all the nonzero vectors. And this is best possible by taking $S$ to be the complement of $0$ in a vector subspace of codimension $d-1$.