12
$\begingroup$

Let $V$ be an $n$-dimensional $\mathbb F_2$ vector space. Note that $V$ has $2^n$ elements and $\mathcal P(V)$ has $2^{2^n}$.

I'm interested in the probability (under a uniform distribution) that an element of $\mathcal P(V)$ is a spanning set for $V$. Equivalently a closed form formula (or at least one who's asymptotics as $n\rightarrow \infty$ are easy to work out) for the number of spanning sets or non-spanning sets.

It's not hard to show that the probability is greater than or equal to $1/2$. Since any subset of size greater than $2^{n-1}$ must span the space. I calculated the proportion of spanning sets of size $n$ for $n$ up to $200$ which seem to be going to a number starting with $.2887$. This leads me to believe that the probability exceeds $1/2$. I couldn't nail down a formula for arbitrary sized subsets though to continue experimental calculations.

I feel like this is something that's been done before, but googling I've mostly found things concerning counting points on varieties over finite fields or counting subspaces of finite fields. Any references would be appreciated.

  • 0
    I think it would be sufficient to count how many different bases you can have in V. Then multiply that number by all possibilities of adding elements to it, since that does not perturb the spanning property of the set.2012-07-17
  • 1
    @Raskolnikov The issue with that is avoiding duplicates.2012-07-17
  • 0
    Indeed, you're right.2012-07-17

2 Answers 2

14

A random subset of $V$ is owerwhelmingly likely to span $V$.

Let's look at how hard it is for a random subset not to span $V$. In order not to span $V$, there must be an $(n-1)$-dimensional subspace that contains the entire subset. There are exactly $2^n-1$ such subspaces, since they are in bijective correspondence with the nontrivial linear maps $V\to\mathbb F_2$ (each subspace is the kernel of exactly one map).

For each fixed $(n-1)$ dimensional subspace, the probability for a random subset to stay within that subspace is $2^{-2^{n-1}}$, since the $2^{n-1}$ vectors outside the subspace must all randomly decide not to be in the subset.

So the probability for a random set not to span is at most $(2^n-1)2^{-2^{n-1}} < 2^{-(2^{n-1}-n)}$ (and this is slightly too high, because there are a few non-spanning subsets that have more than one proper subspace they fit into and so are counted twice here). Everything else spans.

Even for $n$ as small as $5$ the probability for a random subset to span $V$ is above 99.9%, and the number of 9's increases exponentially with larger $n$s.

  • 0
    There isn't an inner product in positive characteristic, so I'm not sure "orthogonal" makes much sense here.2012-07-17
  • 1
    There are indeed $2^n - 1$ subspaces of dimension $n - 1$. There is a bijection with subspaces of dimension $1$, though not via the inner product.2012-07-17
  • 0
    I don't quite see how you get to the numbers you get to so quickly. Even if I just count the subspaces of V for $n=4$ I arrive at more than 6 subsets as Jyrki alluded to.2012-07-17
  • 2
    I think the problem is that the probability that some set $S$ is not contained in some subspace $U$ is _not_ independent of the probability that $S$ is not contained in some other subspace $U'$.2012-07-17
  • 0
    @Jyrki, Jacob: I also forgot to subtract $1$ from $n$ in the topmost exponent when I estimated the 99.99%, which threw things off a bit.2012-07-17
  • 0
    @Zhen: It's true that they are not independent. That's why when I just add the probabilities, I get an _upper bound_ for the probability of not-spanning, which implies a _lower bound_ for the probability to span.2012-07-17
  • 2
    That works, and it's certainly enough to get the conclusion that the probability goes to $1$ as $n \to \infty$.2012-07-17
  • 3
    (+1 to Henning) @ZhenLin: A non-degenerate bilinear form gives that correspondence (as you probably noticed) between $(2^n-1)$ non-zero vectors (=1-dim. subspaces) and $(n-1)$-dimensional subspaces. IMHO the word *orthogonal* might still be used - with the caveat that a vector or a subspace may be orthogonal to itself.2012-07-17
  • 0
    Thanks @Jyrki. I've un-panicked and put the $2^n-1$ back in, though for clarity it's probably best to avoid the o-word and speak of one-forms instead.2012-07-17
  • 2
    @Jyrki: I think it is cleaner to speak of nonzero vectors in $V$ and $(n-1)$-dimensional subspaces in $V^{\ast}$ (their annihilators) as this correspondence is functorial and doesn't require the addition of extra structure.2012-07-17
4

It's worth mentioning that there is an explicit formula for the probability that $N$ random vectors drawn from $\mathbb{F}_q^n$ span. (Note: I am doing sampling with replacement. If you want to require the $N$ vectors to be distinct, you can do this using inclusion-exclusion, but the result will be much messier.) Of course, the answer is $0$ if $N, so assume $N \geq n$.

Write down an $n \times N$ matrix whose columns are the vectors in question. Note that the following are equivalent:

  1. The columns span $\mathbb{F}_q^n$.
  2. The matrix has rank $n$.
  3. The rows are linearly independent.

Thinking in terms of rows, we have the new question: If we draw $n$ vectors at random from $\mathbb{F}_q^N$, what is the probability that they are linearly independent?

The probability that the first vector is nonzero is $1-q^{-N}$. Given that, the probability that the second vector is not in the span of the first is $1-q^{-N+1}$. Given that, the probability that the third vector is not in the span of the first two is $1-q^{-N+2}$. Continuing in this manner, the probability that $n$ vectors in $\mathbb{F}_q^n$ are independent is $$(1-q^{-N}) (1-q^{-N+1}) \cdots (1-q^{-N+n-1}).$$ And, by the above argument, this is also the probability that $N$ random vectors will span $\mathbb{F}_q^n$.

In particular, as Henning says, once $N-n$ is of any significant size, this is extremely close to $1$.

  • 0
    For anyone interested, here's a nice plot based on this answer showing $n$ vs $k = N - n$ to demonstrate the OP's observation that at $k = 0$ you get a number approaching 0.288...: https://www.wolframalpha.com/input/?i=plot3d%5Bproduct%5B1-2%5E(i-floor%5Bn%5D-floor%5Bk%5D),+%7Bi,+0,+floor%5Bn%5D+-+1%7D%5D,+%7Bn,+1,+10%7D,+%7Bk,+0,+5%7D%5D2016-04-25