The lattice spanned by $m$ random 0-1 vectors of length $n$

Question

Consider $m$ random 0-1 vectors of length $n$. Let $L$ be the lattice spanned by them. What is the value of $m$ (as a function of $n$) for which it is true with positive probability that $L=Z^n$? More generally, let $V(L)$ be the rank of $Z^n/L$ (The volume of $L$). What is the behavior of $V(L)$ as a function of $n$ and $m$?

Answer 1

I believe (but haven't fully checked) that you can get an upper bound of $m=cn \log^2 n$ using the second moment method. I'm including a sketched argument below.

I will assume WLOG that $m$ is even. I will also (for now) make a parity assumption: I will assume that, modulo $2$, the sum of all $m$ vectors is equal to $(1,0,\dots,0)$.

Consider the $\binom{m}{m/2}$ vectors $$v_A := \sum_{j \in A} v_j - \sum_{j \notin A} v_j,$$ where $A$ is any subset of size $m/2$. For any given $A$, the probability $v_A$ equals $(1,0,\dots 0)$ is $$\frac{\binom{m}{m/2-1}}{2^{m-1}} \left(\frac{\binom{m}{m/2}}{2^{m-1}}\right)^{n-1} = \left(\frac{4}{\pi n}+o(1)\right)^{n/2}$$ by Stirling's approximation (note that I'm dividing by $2^{m-1}$ here due to the parity assumption).

So the expected number of $v_A$ equal to $(1,0,\dots,0)$ is (again using Stirling's approximation) $$\frac{2^m}{\sqrt{\pi m/2}} \left(\frac{2}{\pi n}+o(1)\right)^{n/2}, $$ which tends to infinity for $m=c n \log n$ and sufficiently large $c$. We now look at the second moment.

If $|A \cap B|=k$, then for each coordinate (except the first, which is pretty much the same), the event $v_A(t)=v_B(t)=0$ corresponds (after a bit of rearrangement) to the pair of events $$\sum_{j \in A \cap B} v_j (t) = \sum_{j \in A^C \cap B^C} v_j(t)$$ $$\sum_{j \in A \cap B^C} v_j (t) = \sum_{j \in A^C \cap B} v_j(t).$$ So the probability that both occur equals $$\frac{\binom{2k}{k} \binom{m-2k}{m/2-k}}{2^{m-1}}.$$ We therefore have $$\frac{P(v_A=v_B=0)}{P(v_A=0)^2}=\left( 2^{m-1} \frac{\binom{2k}{k} \binom{m-2k}{m/2-k}}{\left(\binom{m}{m/2}\right)^2} \right)^n$$ Applying Stirling/central binomial asmyptotics again, I get that after some more algebra this becomes $$\left(\frac{m/4}{\sqrt{k(m/2-k)}} \left(1+O(\frac{1}{\min(k,m/2-k)})\right)\right)^n.$$

For $|k-m/4|=t\sqrt{m}$, the first fraction is $1+O\left(\frac{t^2}{m}\right)$ so for $t=o(\sqrt{\log n})$ we have $$\frac{P(v_A=v_B=0)}{P(v_A=0)^2}= \left(1+O(\frac{t^2}{m})\right)^n = 1+o(1).$$ [The parity assumption is necessary to make this work -- otherwise the fact that $v_A=v_B$ modulo $2$ increases the probability by a factor of $2$ for each coordinate]. I believe (but haven't gone through the full details) that it's similarly possible to bound the tails, so by Chebyshev we will almost surely have $(1,0,0,\dots,0)$ by the time we get to $m=c n \log n$, under our parity conditioning.

By another second moment calculation, we know that any subset of size $2m$ vectors almost surely has a subset of size $m$ having the desired sum modulo $2$ (the second moment calculation's actually a lot simpler here -- for any $A \neq B$ the sums of $A$ and $B$ are independent!). So by increasing $m$ to $2cn \log n$, we can remove the parity conditioning and almost surely have a sum equal to $(1,0,\dots,0)$. Taking $\log n$ collections of this size $m$, we can almost surely hit every coordinate vector.

Effectively I lost a $\log$ in this argument when I only considered the $v_A$ instead of more general sums, and another $\log$ in the end when I considered $\log n$ disjoint collections of vectors instead of allowing the collections to interact with each other. Both may be unncessary.

Answer 2

To get an upper bound (for the first part of the question), one can use use the estimates described in the answers to this question. Then, if the volume of the quotient by the lattice generated by the first $n$ vectors is $x,$ a coupon-collector argument gives an $n + x \log x$ upper bound (one has to be a bit careful, since the expectation is not enough, one needs information about the distribution. For the second question, you want estimates on the singular values of an $m \times n$ matrix, which is a much studied subject, especially lately by Rudelson and Vershynin. You can check out Roman Vershynin's surveys on the subject.

Answer 3

I believe it is possible to use some recent closely related work of Kenneth Maples to get a much better (but probably still not quite tight) bound. Let $C>0$ be a constant to be chosen later. Call an $n \times n$ matrix $A$ good if it satisfies each of the following properties

P1. $A$ is non-singular over $\mathbb{R}$.

P2. $|det(A)|$ has at most $C \log n$ prime factors.

P3. $A$ has rank at least $n-C \log n$ over ${\mathbb F}_p$ for every prime $p$.

Here are two claims which together would imply $n+O(\log n)$ vectors are enough.

Claim 1: A random $n \times n$ $(0,1)$ matrix is good with probability $1-O\left(C^{-1}\right)$.

Claim 2: If $A$ is any fixed good matrix, augmenting $A$ by $5C \log n$ random rows with high probability leads to a matrix whose rows span ${\mathbb Z}^n$.

We first look at claim 1. The probability P1 fails is exponentially small in $n$ (as originally shown by Kahn, Komlos, and Szemeredi).

For P2 and P3, we use the following result of Maples (Corollary 1.3 here): For any prime $p$, the probability that a random $n \times n$ matrix has rank $n-k$ over ${\mathbb F}_p$ is

$$p^{-k^2} \frac{\prod_{\ell=k+1}^{\infty} \left(1-p^{-\ell}\right)}{\prod_{\ell=1}^k \left(1-p^{-\ell}\right)}+O\left(e^{-cn/2}\right),$$ where both $c$ and the constant implicit in $O()$ are independent of $p$. We can actually bound the probability above by $O\left(p^{-k^2} +e^{-cn/2}\right)$, since the ratio of products is at most $\prod_{\ell=1}^{\infty} (1-2^{-\ell})^{-1}$. Summing over all $k$, the probability $A$ is singular over ${\mathbb F}_p$ is $O\left(\frac{1}{p} + e^{-\frac{cn}{2}}\right)$. Summing over all $p$, the expected number of primes less than $e^{cn/4}$ dividing $|det(A)|$ is at most $\log n +O(1)$.

There can be at most $2 \log n/c$ prime factors of $|det(A)|$ larger than $e^{cn/4}$, since otherwise $|det(A)|$ would be larger than $n^{n/2}$ and violate Hadamard's bound. So the total expected number of factors is $O(\log n)$, and the probability P2 fails is $O(1/C)$ by Markov's inequality.

For P3, we again split into small and large primes. Applying Maples' theorem again, the probability P3 fails for a given prime less than $e^{cn/4}$ is at most $O\left(p^{-C^2 \log^2 n}+ e^{-cn/2}\right)$, and by the union bound the probability P3 fails for some small prime is small.

For large primes, we use the observation that $A$ can only have rank less than $n-k$ over ${\mathbb F}_p$ if $p^k$ divides the determinant of $A$ (e.g. because in this case we can row reduce over the integers so $k$ rows have all entries divisible by $p$, at which point we can pull a factor of $p$ out for each row). In particular, if $C$ is sufficiently large we know from Hadamard's bound it is impossible for P1 to succeed and P3 to fail for some prime larger than $e^{cn/4}$. This finishes Claim 1.

We now turn to Claim 2. We first note that the for $m \geq n$ the vectors $v_1, \dots, v_m$ span ${\mathbb Z}^n$ if and only if the matrix with the $v_i$ as rows has full rank over ${\mathbb F}_p$ for every prime $p$ (if the volume of a cell is $V$, then $V$ divides the determinant of every $n \times n$ submatrix). Since $A$ is good, we know that we already are full rank for all but at most $C \log n$ primes. So it is enough to show the augmentation with high probability fixes each of those primes. Fix any one such prime $p$.

We use the following observation (originally due to Odlyzko): Any proper subspace of ${\mathbb F}_p^n$ contains at most half of the $(0,1)$ vectors (e.g. because if you fix a column basis, whichever column is not in the basis is determined by the remaining $n-1$ columns). It follows that so long as $v_1, \dots ,v_j$ do not already span the space, $$P\left(v_{j+1} \notin Span(v_1, \dots v_j) \right) \geq \frac{1}{2}.$$ By assumption P3, $A$ already had rank at least $n-C \log n$ before we added the rows. The only way $A$ can fail to be full rank after the augmentation is if the above event occurred at least $4 C \log n$ times, an event which occurs with probability at most $$\binom{5C \log n}{4 C \log n} 2^{-4C \log n} = 2^{(-0.39+o(1)) C \log n}.$$ Taking the union bound over all $p$ which divide $|det(A)|$, the probability we fail to be of full rank modulo some prime is at most $C \log n 2^{-(0.39+o(1)) C \log n} = Cn^{-0.39C+o(1)}$, proving Claim 2.

This bound is probably still not quite tight, especially in the handling of P3 for large $p$. One annoyance in trying to drop below $\log n$ is that if the last row of $A$ and all the rows added in the augmentation are zero (an event occurring with probability roughly $2^{-n(m-n)}$), the matrix fails to be of full rank modulo every prime. This means just taking the union bound over all the roughly $2^{c n \log n}$ primes less than $n^{n/2}$ won't be enough if $m-n$ is much smaller than $\log n$, unless we could possibly get some handle on the event "$A$ is of full rank over $\mathbb{R}$ but not over ${\mathbb F}_p$" for large $p$.

Answer 4

When you pick n+1 vectors from Z^n according to basically any distribution, the probability they generate is heuristically (for large n) the reciprocal of zeta(2)zeta(3), which is about 0.436...

For example, I just did it 1000 runs of 21 vectors in Z^{20} and got the full lattice 430 times.

In other words: The answer is m=n+1 but I don't know if you could prove it.