# Average minimum number of random k-sparse vectors in GF(2) to span the whole space?

What is the average minimum required number of independent $k$-sparse (having at most $k$ non-zero elements) random vectors belonging to $\mathbb{F}_2^n$ to span the whole space of $\mathbb{F}_2^n$? Any such vector is uniformly probable to be chosen among the total $\sum_{j=0}^k \binom{n}{j}$ vectors.

Here are the two extreme cases:

1. If $k=n$, this average value is $n+1.6067$ as proved here.
2. If $k=1$, using coupon collector problem this average value is proved to be larger than $\Theta(n \log n)$.

Can we prove that if $k = \Theta(\log n)$, then this average value is $\Theta(n)$? or something similar? My simulation results show that for a pretty large range of $k$ this average value is $\Theta(n)$.

• You might look at this related MO question of mine and its answer by Kevin Costello. May 3 '16 at 17:21
• Thank you Robert! I have seen this post before and also the mentioned papers. My guess is that if $k$ is larger than the XORSAT satisfiability threshold, the average minimum required number of vectors will be equal to $n(1+o(1))$ but I don't know how to prove or disprove it? May 3 '16 at 17:37
• When k=2, this is equivalent to taking a graph on n+1 vertices and adding random edges until it is connected. Here the vector $e_i+e_j$ corresponds to edge $(i,j)$ and the vector $e_i$ corresponds to edge $(0,i)$ May 4 '16 at 14:31
• This is a nice analogy. Do you know the exact value of the minimum number of edges to be added to make this graph connected. May 4 '16 at 20:34

Let $k=\Theta(\log n)$. We will keep adding random $k$-sparse vectors one at a time and stop when we get a spanning set. Assume that currently the vectors span a space $A$ of codimension $j$ for $j\le n/(2k)$. We want to figure out the expected number of steps to reach codimension $j-1$, which is the inverse of the probability that a randomly chosen $k$-sparse vector is outside of $A$.
Since $A$ has codimension $j$, we can find $j$ basis vectors $e_{\ell_1},\ldots,e_{\ell_j}$ such that $A\cap\text{span}(e_{\ell_1},\ldots,e_{\ell_j})=\{0\}$. This means that for any vector $v$ that has $k-1$ 1's, none of them at a position $\ell_i$, we have that at most one of $v,v+e_{\ell_1},v+e_{\ell_2},\ldots,v+e_{\ell_j}$ is in $A$. Thus there are at least $j\binom{n-j}{k-1}$ $k$-sparse vectors outside of $A$, so the probability of a random $k$-sparse vector is outside of $A$ is at least $$\frac{j\binom{n-j}{k-1}}{\sum_{i=0}^k \binom{n}{i}}=\Theta\left(\frac{j\binom{n}{k-1}}{\binom{n}{k}}\right)=\Theta\left(\frac{jk}{n}\right)=\Theta\left(\frac{j\log n}{n}\right)$$ where we used the fact that $j\le n/(2k)$ to get $\binom{n-j}{k-1}=\Theta\left(\binom{n}{k-1}\right)$. This means that going from codimension $j$ to codimension $j-1$ takes an average of $\Theta\left(\frac{n}{j\log n}\right)$ steps, so going from codimension $\lfloor \frac{n}{2k}\rfloor$ to codimension $0$ (spanning set) takes an average of $$\sum_{j=1}^{n/(2k)} \frac{n}{j\log n}=\Theta\left(\frac{n\log(n/(2k))}{log n}\right)=\Theta(n)$$ steps.
If the codimension is $j=\lfloor \frac{n}{2k}\rfloor$, then we derived above that decreasing the codimension by 1 requires an average of $\Theta\left(\frac{n}{j\log n}\right)=\Theta(1)$ steps. Since the number of steps necessary is only smaller when the codimension is greater, it takes us at most $\Theta(n/\log n)$ steps to get to codimension $\lfloor \frac{n}{2k}\rfloor$. Therefore the whole process takes $\Theta(n)$ steps.
• Thank you Sam! I think this is the correct answer for $k=\Theta(\log(n))$. But what is the actual threshold for $k$ such that the average number is $\Theta(n)$? Can we prove something stronger that the average value is indeed $n(1+o(1))$ for $k=\Omega(\log(n))$? May 4 '16 at 17:36
• This was based on taking $jk/n$ as the lower bound that each new vector is outside of $A$, which corresponds to the worst case when $A=span\{e_1,\ldots,e_{n-j}\}$. Intuitively, it seems like the average case should have higher probability (and thus take fewer steps), which would make the threshold for k less than $\log n$, but I'm not sure how to prove that. May 5 '16 at 21:02