Let $n$ be a positive integer, let $p$ be a prime, let $\mathbb F_p$ be the field with $p$ elements, and let $V = \mathbb F_p^n$ be the $n$-dimensional vector space over $\mathbb F_p$. For an integer $k\in\{1,\dots,n\}$, we say that a set $S\subset V$ is $k$-spanning if it contains a basis of every $k$-dimensional subspace of $V$. More precisely, $S\subset V$ is $k$-spanning if for every $k$-dimensional subspace $W$ of $V$, there are $v_1,\dots,v_k\in S$ such that $\mathrm{span}(v_1,\dots,v_k) = W$. Here, $\mathrm{span}(v_1,\dots,v_k)$ denotes the $\mathbb F_p$-linear span of $v_1,\dots,v_k$.
Let $C_{n,p}(k)$ be the minimal cardinality of a $k$-spanning set: \begin{align*} C_{n,p}(k) = \min\{|S|\colon S \subset V \text{ is $k$-spanning}\} \end{align*}
Problem: Determine $C_{n,p}(k)$. In particular, derive good upper bounds on $C_{n,p}(k)$.
Here are two trivial cases.
- $C_{n,p}(1)$ is the number of $1$-dimensional subspaces of $\mathbb F_p^n$, so $C_{n,p}(1) = (p^n - 1)/(p-1)$.
- $C_{n,p}(n) = n$.
Now to the general case.
A lower bound:
It is easy to get a lower bound for $C_{n,p}(k)$. The number of $k$-dimensional subspaces of $V$ is $\frac{ (p^n-1)(p^n-p) \dotsm (p^n-p^{k-1}) }{ (p^k-1)(p^k-p) \dotsm (p^k-p^{k-1}) } \ge p^{k(n-k)}$. If $S\subset V$ has cardinality $m$, it spans at most ${m\choose k}$ distinct $k$-dimensional subspaces. So if $S$ is $k$-spanning, we have that \begin{align*} {m\choose k} \ge p^{k(n-k)}. \end{align*} Using the bound ${m\choose k} \le \left(\frac{me}k\right)^k$, this implies that \begin{align*} m \ge \frac{k}{e} p^{n-k} = \Omega(k p^{n-k}). \end{align*}
An upper bound:
An ad-hoc probabilistic argument gives a non-trivial upper bound for $C_{n,p}(k)$. Let $S = \{s_1,\dots,s_m\}$ be a uniformly random subset of $V \setminus \{0\}$ of cardinality $m$.
Fix a $k$-dimensional subspace $W$ of $V$. For each $\ell \in [m]$, the probability that $\mathrm{dim}\left(\mathrm{span}(\{s_1,\dots,s_{\ell-1}\} \cap W)\right) + 1 = \mathrm{dim}\left(\mathrm{span}(\{s_1,\dots,s_{\ell}\} \cap W)\right)$ is at least $q = \frac{p^k - p^{k-1}}{p^n-1} > \frac{p - 1}{p^{n-k + 1}}$. Hence, the probability that $S$ contains a spanning set of $W$ is at least as large as the probability that a random variable $X \sim B(m,q)$ takes a value of $k$ or larger (here, $B(m,q)$ is a binomial distribution with sample size $m$ and success rate $q$). A standard bound for the tails of binomial distributions (from Wikipedia) gives that \begin{align*} P(S \text{ does not contain a spanning set of } W) \le P(X < k) \le e^{-m D\left(\frac km \mid q\right)}, \end{align*} where $D(a \mid b) = a \log \frac ab + (1-a)\log \frac{1-a}{1-b}$ is the Kullback-Leiber divergence between Bernoulli random variables with success rates $a$ and $b$. We want the RHS to be smaller than one over the number of $k$-dimensional subspaces of $V$, since then the probability that $S$ contains a spanning set of every $k$-dimensional subspace of $V$ is positive. So let's backtrack.
The number of $k$-dimensional subspaces of $V$ is $\frac{ (p^n-1)(p^n-p) \dotsm (p^n-p^{k-1}) }{ (p^k-1)(p^k-p) \dotsm (p^k-p^{k-1}) } \le \frac{p^{kn}}{p^{(k-1)k}} = p^{k(n-k+1)}$. So we need that \begin{align*} e^{-m D\left(\frac km \mid q\right)} < p^{-k(n-k+1)}. \end{align*} Taking logarithms, we see that we need \begin{align*} m D\left(\frac km \mid q\right) > k(n-k+1)\log p. \end{align*} Let's estimate the LHS. For $0 \le 2a \le b << 1$, we have $\log\frac{1-a}{1-b} \ge \log(1 + \frac b2) \approx \frac b2$. Hence, \begin{align*} m D\left(\frac km \mid q\right) &= m\left(\frac km \log \frac{k}{mq} + (1-\frac km)\log \frac{1 - \frac km}{1 - q}\right)\\ &\gtrapprox k \log\frac k{mq} + \frac{mq}{2}\\ &\gtrapprox k(n-k+1)\log p - k\log m + \frac{mq}2. \end{align*} So we need that $\frac m{\log m} > \frac{2k}q$. For $a,b > 0$, $a > 2b \log(2b)$ implies $\frac{a}{\log a} > b$, so it is sufficient that \begin{align*} m > \frac{4k}q \log\left(\frac{4k}q\right) \gtrapprox \frac{4k p^{n-k+1}}{p-1} (n-k)\log p = O(n^2 p^{n-k}), \end{align*} where the implied constant depends on $p$.
Open problems:
- Is the truth closer to the upper or the lower bound?
- How can one construct small $k$-spanning sets?
- Are there structure theorems for (close to) minimal $k$-spanning sets? That is, does every $k$-spanning set of cardinality $C_{n,p}(k)$ have a particular pattern?
- Am I missing obvious solutions to any of these problems?
