16
$\begingroup$

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$?

$\endgroup$
3
  • $\begingroup$ For the first question, are you holding this positive probability fixed as $n$ varies? $\endgroup$
    – Will Sawin
    Jul 3, 2012 at 19:47
  • $\begingroup$ Will, yes e.g. what is m as a function of m so that the probability is roughly 1/2. $\endgroup$
    – Gil Kalai
    Jul 3, 2012 at 20:31
  • $\begingroup$ Too bad you aren't asking for roughly 1/4. arxiv.org/abs/math/0511636 has some data about 0-1 matrices whose Smith Normal Form is the identity, which is roughly a fourth of all matrices for small n. (It also kindly quotes a result of mine in another section. Full disclosure and all that.) It would not surprise me if n + O(loglogn) were achievable. Gerhard "Ask Me About System Design" Paseman, 2012.08.31 $\endgroup$ Sep 1, 2012 at 0:25

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Wonderful, Kevin (but I did not carefully check either). Do you know (by heuristics or numerics perhaps) what the answer should be? $\endgroup$
    – Gil Kalai
    Jul 5, 2012 at 14:54
  • $\begingroup$ My guess (though I don't have any sort of rigorous backup) is that actually $m=O(n)$ (or even something like $n(1+o(1))$) would be enough. The idea is that if you look at any set of $n$ vectors, they probably will be independent and therefore span some vector of the form $(a,0,0\dots,0)$. The only way that $(1,0,\dots,0)$ would not be in the span is if there was some factor common to the $a$ from every set of $n$ vectors, and it feels like this shouldn't be too likely (akin to how over a small field an $n \times (n+k)$ matrix is not full rank with probability exponentially small in $k$). $\endgroup$ Jul 5, 2012 at 21:03
  • $\begingroup$ By the way, I think that the above comment may tie in with what Igor said in his comment about the relation to random homology. As I understand it the situation with the Linial-Meshulam problem is that they have found a threshold which holds for $\mathbb{Z}_p$-homology for any fixed prime $p$ (the analogue of almost-surely being non-singular over $\mathbb{Z}_p$ for any fixed $p$), but the question is still open whether there might be some sort of torsion growing with $n$ (whether there might be some common factor to all the $a$ growing with $n$). $\endgroup$ Jul 5, 2012 at 21:28
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Igor, x is fairly huge (the determinant of an n by n random 0,1 matrix) and then your upper bound is superexponential in n. It does not look very good. $\endgroup$
    – Gil Kalai
    Jul 3, 2012 at 20:12
  • $\begingroup$ @Gil: true, but do you believe that the truth is polynomial in $n?$ If so, why? $\endgroup$
    – Igor Rivin
    Jul 3, 2012 at 20:31
  • $\begingroup$ Dear Igor, I do not know which is why I was asking. There is a vast new progress on related questions, in particular, on the behavior of random 0/1 matrices so perhaps this is either known or follows from what is known to the experts. Maybe your estimate is close to the truth; another problem is that I do not understand the coupon collector argument even without the careful part. Can you ellaborate? $\endgroup$
    – Gil Kalai
    Jul 3, 2012 at 20:46
  • $\begingroup$ @Gil: the coupon collector argument is simply that every time you generate a new vector, it projects somewhere in the quotient. For the images to cover the quotient will take time $x \log x,$ where $x$ is the size (=volume, more or less) of the quotient). Of course, this is a very crude argument, and it may be that the Rudelson-Vershynin results give a much better bound. $\endgroup$
    – Igor Rivin
    Jul 3, 2012 at 21:35
  • $\begingroup$ @Gil and by the way, I don't know if this is why you are asking, but this has a very close relationship to the homology of random complexes (a la Linial-Meshulam). I recall thinking about this once, and a good answer to your question can help treat the $\mathbb{Z}$ coefficients case, if memory serves... $\endgroup$
    – Igor Rivin
    Jul 4, 2012 at 0:41
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.