Número mínimo de puntos no nulos en $\mathbb{F}_2^n$ que cubren todos los subespacios de codimensión k

Question

¿Cuál es el tamaño mínimo de $S \subset \mathbb{F}_2^n \setminus \{0\}$ de modo que para cualquier codimensión $k$ subespacio $W \subset \mathbb{F}_2^n$ existe $s \in S$ tal que $s \in W$ ? Podemos suponer que $k$ es $O(1)$ .

He pensado en esto durante un tiempo y no puedo conseguir un buen tamaño. Sé que tenemos $\binom{n}{k}_2$ muchos subespacios, pero elegir un vector por subespacio no es correcto, ya que hay un solapamiento significativo entre estos subespacios. Me conformaría con mostrar que $|S|$ es $o(2^n)$ Aunque no estoy seguro de que eso sea cierto.

Answer 1

No es un resultado muy agudo, pero si $T$ es cualquier $k+1$ subespacio dimensional, entonces $S:=T- \{0\}$ lo hará, porque $W$ debe intersecar $T$ de forma no trivial (la suma de las dimensiones es mayor que el espacio ambiental). $T$ tiene $2^{k+1}$ elementos, por lo que $|S|=2^{k+1}-1$ que es un límite superior para su pregunta.

Edición: En el caso $k=n-1$ el espacio $W$ es unidimensional, que en $\mathbb{F}_2^n$ es un solo vector (y el vector cero). Así, en este caso, $S$ tiene que ser todo el espacio (excepto el cero), por lo que $|S|=2^{k+1}-1$ lo que sugiere que el resultado anterior puede ser óptimo, al menos asintóticamente en $k$ .