most recent 30 from http://mathoverflow.net 2013-05-20T17:05:48Z http://mathoverflow.net/feeds/question/23422 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/23422/random-projection-and-finite-fields ilyaraz 2010-05-04T13:05:35Z 2010-05-04T14:24:50Z

<p>Suppose we have, say, $n$ $2n$-dimensional linearly independent vectors over $\mathbb{F}_2$. We do a projection on a random $d$-dimensional subspace. We are interested in probability that images of our vectors will be linearly independent (over $\mathbb{F}_2$) too.</p> <p>The question is as follows: how large $d - n$ should be if we want this probability to be, say, $1 - 1 / \mathrm{poly}(n)$?</p>

http://mathoverflow.net/questions/23422/random-projection-and-finite-fields/23431#23431 Ben Green 2010-05-04T14:24:50Z 2010-05-04T14:24:50Z

<p>Suppose the vectors are $e_1,\dots,e_n$. The kernel of projection onto a random subspace of dimension $n+r$ is a random subspace of dimension $n-r$, so you want the probability that such a subspace has trivial intersection with the span of $e_1,\dots, e_n$. Now just count the number of choices for a basis $v_1,\dots, v_{n-r}$ of such a space: $2^{2n} - 2^n$ for the first vector, then $2^{2n} - 2^{n+1}$ for the second, and so on. This is to be compared with $2^{2n} - 1$ choices for the first vector if one doesn't have an restriction, $2^{2n}-2$ for the second and so on.</p> <p>So the probability of this happening is the ratio of these two quantities, which you need to find a good approximation for; a very brief back-of-an-envelope calculation suggested it's about $1 - c2^{-r}$, at least if $r$ is largeish. For your specific needs, then, $d - n$ should be about $C\log n$. </p>