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 | |
|---|---|---|---|---|---|
| Sep 27, 2012 at 1:17 | vote | accept | Gil Kalai | ||
| Sep 27, 2012 at 1:17 | history | bounty ended | Gil Kalai | ||
| Jul 5, 2012 at 21:28 | comment | added | Kevin P. Costello | 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$). | |
| Jul 5, 2012 at 21:03 | comment | added | Kevin P. Costello | 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$). | |
| Jul 5, 2012 at 14:54 | comment | added | Gil Kalai | Wonderful, Kevin (but I did not carefully check either). Do you know (by heuristics or numerics perhaps) what the answer should be? | |
| Jul 3, 2012 at 22:17 | history | edited | Kevin P. Costello | CC BY-SA 3.0 |
$m/4$ instead of $m/2$ in one place
|
| Jul 3, 2012 at 22:01 | history | answered | Kevin P. Costello | CC BY-SA 3.0 |