Timeline for The lattice spanned by $m$ random 0-1 vectors of length $n$
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:57 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jul 4, 2012 at 0:41 | comment | added | Igor Rivin | @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... | |
| Jul 3, 2012 at 21:35 | comment | added | Igor Rivin | @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. | |
| Jul 3, 2012 at 20:46 | comment | added | Gil Kalai | 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? | |
| Jul 3, 2012 at 20:31 | comment | added | Igor Rivin | @Gil: true, but do you believe that the truth is polynomial in $n?$ If so, why? | |
| Jul 3, 2012 at 20:12 | comment | added | Gil Kalai | 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. | |
| Jul 3, 2012 at 18:00 | history | answered | Igor Rivin | CC BY-SA 3.0 |