The latice spanned by $m$ random 0-1 vectors of length $n$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T07:29:50Z http://mathoverflow.net/feeds/question/101246 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101246/the-latice-spanned-by-m-random-0-1-vectors-of-length-n The latice spanned by $m$ random 0-1 vectors of length $n$ Gil Kalai 2012-07-03T17:45:53Z 2012-09-27T01:17:24Z <p>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$? </p> http://mathoverflow.net/questions/101246/the-latice-spanned-by-m-random-0-1-vectors-of-length-n/101247#101247 Answer by Igor Rivin for The latice spanned by $m$ random 0-1 vectors of length $n$ Igor Rivin 2012-07-03T18:00:41Z 2012-07-03T18:00:41Z <p>To get an upper bound (for the first part of the question), one can use use the estimates described in the answers to <a href="http://mathoverflow.net/questions/13008/expected-determinant-of-a-random-nxn-matrix" rel="nofollow">this question</a>. 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 <a href="http://www-personal.umich.edu/~romanv/papers/papers.html" rel="nofollow">surveys on the subject.</a></p> http://mathoverflow.net/questions/101246/the-latice-spanned-by-m-random-0-1-vectors-of-length-n/101261#101261 Answer by Kevin P. Costello for The latice spanned by $m$ random 0-1 vectors of length $n$ Kevin P. Costello 2012-07-03T22:01:15Z 2012-07-03T22:17:53Z <p>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. </p> <p>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)$. </p> <p>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).</p> <p>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. </p> <p>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.$$</p> <p>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.</p> <p>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.</p> <p>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. </p> http://mathoverflow.net/questions/101246/the-latice-spanned-by-m-random-0-1-vectors-of-length-n/106077#106077 Answer by Kevin P. Costello for The latice spanned by $m$ random 0-1 vectors of length $n$ Kevin P. Costello 2012-08-31T23:00:37Z 2012-08-31T23:07:46Z <p>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$ <em>good</em> if it satisfies each of the following properties</p> <p>P1. $A$ is non-singular over $\mathbb{R}$.</p> <p>P2. $|det(A)|$ has at most $C \log n$ prime factors.</p> <p>P3. $A$ has rank at least $n-C \log n$ over ${\mathbb F}_p$ for every prime $p$.</p> <p>Here are two claims which together would imply $n+O(\log n)$ vectors are enough.</p> <p>Claim 1: A random $n \times n$ $(0,1)$ matrix is good with probability $1-O\left(C^{-1}\right)$.</p> <p>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$.</p> <p>We first look at claim 1. The probability P1 fails is exponentially small in $n$ (as originally shown by Kahn, Komlos, and Szemeredi).</p> <p>For P2 and P3, we use the following result of Maples (Corollary 1.3 <a href="http://user.math.uzh.ch/maples/maples-cokernel.pdf" rel="nofollow">here</a>): For any prime $p$, the probability that a random $n \times n$ matrix has rank $n-k$ over ${\mathbb F}_p$ is</p> <p>$$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)$.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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$.</p> <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.</p> <p>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$. </p> http://mathoverflow.net/questions/101246/the-latice-spanned-by-m-random-0-1-vectors-of-length-n/106097#106097 Answer by anonymous for The latice spanned by $m$ random 0-1 vectors of length $n$ anonymous 2012-09-01T06:33:10Z 2012-09-01T06:33:10Z <p>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... </p> <p>For example, I just did it 1000 runs of 21 vectors in Z^{20} and got the full lattice 430 times. </p> <p>In other words: The answer is m=n+1 but I don't know if you could prove it. </p>