A rough draft.
The dimension bound theorem is linear algebra says puts a hard limit on the size of linearly independent sets in finite dimensional vector spaces. If $\dim(V) = d$ then any set of $d + 1$ vectors in $V$ must be linearly dependent.
Let $p$ be a prime and $V$ be the vector space $\mathbb{F}_p^d$. We’re interested in the “growth rate” of linear independent sets in $V$. What do we mean by this?
Consider the following random process for “growing” a linearly independent set. We first randomly and uniformly select a vector $v_1 \in V$. If this vector is the zero vector then the set $\{v_1\}$ is dependent and we stop the process.
If our initial vector is not the zero vector, then we add a new randomly selected vector $v_2$ to the set. If our updated set of vectors $\{v_1, v_2\}$ is linearly dependent then we stop. The process continues like this until it hits the dimension bound, at which point the set must be dependent.
We’re interest in the question: when does the growth process stop? To do so, we calculate the expected value of the stopping time $T$. The tail sum formula gives:
\[ \mathbb{E}(T) = \sum_{k=1} {Pr}(T \geq k). \]
We calculate the individual probabilities.
To start, notice that
\[
{Pr}(T \geq 1) = 1
\]
because the process always goes for
at least one step: we select the vector $\{v_1\}$.
To calculate ${Pr}(T \geq 2)$ we need the probability that the process got to the second step. If the process gets to the second step then we know that $v_1 \neq 0$. And so, there are $p^d - 1$ choices for $v_1$ because the selection process needs to avoid the zero vector. This gives: \[ {Pr}(T \geq 2) = {Pr}(v_1 \neq 0) = \frac{p^d - 1}{p^d}. \] Before moving to the general formula, we consider ${Pr}(T \geq 3)$. If the process arrives at the third step, we know $\{v_1, v_2\}$ must be independent. Independece implies means that their span has size $|{span}\{v_1, v_2\}| = p^2$. Thefore, the choice of the third vector must avoid $p^2$ vectors in the span, and must come from the remaining $p^d - 2$ vectors in the vector space. \[ {Pr}(T \geq 3) = \left(\frac{p^d - p^2}{p^d - 2}\right){Pr}(T \geq 2) = \left(\frac{p^d - p^2}{p^d - 2}\right)\left( \frac{p^d - 1}{p^d} \right) \] In general, we consider what needs to happen for the process to reach stage $k$. When picking $v_{k-1}$ we must avoid the span of $\{v_1, \dots, v_{k-2} \}$. This span has size $p^{k-2}$ because the vectors in $\{v_1, \dots, v_{k-2} \}$ are linearly independent. Also, note that we are selecting $v_{k-1}$ from a total of $p^d - (k-2)$ vectors, because the vectors $\{v_1, \dots, v_{k-2}\}$ have already been selected. If this all works out, then the set $\{v_1, \dots, v_{k-2}, v_{k-1}\}$ will be independent and the process will continue to stage $k$. And so we get the following probability1 of the process continuing up to stage $k$. \[ {Pr}(T \geq k) = \prod_{i = 1}^{k-1} \frac{p^d - p^{i-1}}{p^d - (i-1)} \]
Applying the tail sum formula to this gives:
\[ \mathbb{E}(T) = \sum_{k=1}^{d+1} \prod_{i = 1}^{k-1} \frac{p^d - p^{i-1}}{p^d - (i-1)}. \]
The product has upper bound $k = d + 1$ because the process never continues passed $d + 1$; the dimension bound forces any set of size at least $d+1$ to be dependent, so the process must stop.
To get a sense for these numbers, we do a bit of caluculation.
| p | d | E[T] |
|---|---|---|
| 3 | 4 | 4.435849 |
| 3 | 10 | 10.320266 |
| 3 | 50 | 50.317846 |
| 3 | 100 | 100.317846 |
| 5 | 4 | 4.713765 |
| 5 | 10 | 10.698282 |
| 5 | 50 | 50.698266 |
| 5 | 100 | 100.698266 |
| 7 | 4 | 4.813167 |
| 7 | 10 | 10.809090 |
| 7 | 50 | 50.809090 |
| 7 | 100 | 100.809090 |
I got tripped up several times by the indices in this formula. It feels weird that the upper index in the produce is $i = k - 1$, and that for the process to coninute to stage $k$ we need to think so much about avoiding sets of vectors of size $k-2$. Notice, however, that when we plug in the upper bound $i = k - 1$ we get: \[ \frac{p^d - p^{(k-1)-1}}{p^d - ((k-1)-1)} = \frac{p^d - p^{k-2}}{p^d - (k-2)} \] Another thing to keep in mind: If the process gets to stage $k$, then the choice of vector $v_{k-1}$ must have “succeeded” and the set $\{v_1, \dots, v_{k-1}\}$ is independent. The choice of $v_{k-1}$ must avoid various things of size $k-2$, which is why we see this value cropping up so much. ↩︎
Published: Feb 10, 2026 @ 20:50.
Home / Now / Blog / Notes / Reading / Office Camera / Tags / Bookmarks / RSS Feeds / Top of Page
Thanks for reading! If you have any comments or questions about the content, please let me know. Anyone can contact me by email.