most recent 30 from http://mathoverflow.net 2013-06-19T18:26:28Z http://mathoverflow.net/feeds/question/91581 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91581/probability-of-a-set-of-random-vectors-over-finite-field-being-a-spanning-set John Jiang 2012-03-19T00:15:24Z 2012-03-19T06:28:01Z

<p>Suppose I have a set of random vectors $f(a_1, \ldots, a_\ell) := (v_1, \ldots, v_m) \subset F_p^n$, $m \ge n$, given by a matrix valued polynomial function $f$, where the $a_i$'s are independent, uniformly distributed in $F_p \setminus {0}$, and each component of $f$ consists of some polynomial in the $a_i$'s whose coefficients are all in ${0,1}$, and such that the degree of each variable is at most $1$. For example, the following set of random vectors fits the discription:</p> <p>$$ v_1 = (a_1, a_2 a_1, a_3); v_2 = (a_2, a_1 a_2 a_3 + a_2, 0); v_3 = (a_1 + a_2, a_2 + a_3, a_3 a_1)$$.</p> <p>Now consider the quantity $\pi_p = \mathbb{P}(f(a_1, \ldots, a_\ell) \text{ spans } F_p^n)$. My question is, is $\pi_p$ monotone non-decreasing in $p$? If not can one give a counterexample? The motivation comes from a recent result of Yuval Peres and Allan Sly (Arxiv preprint arXiv:1105.4402, 201) giving the right order of mixing time for the most natural random walk on uni-upper triangular matrices over $F_p$. Knowing the above will extend their result of $\mathcal{O}(n^2)$ to $p$ that grows with $n$, which is highly anticipated. </p> <p>Edit: Will Sawin below essentially solved an earlier version of this problem, where I forgot to state the degree condition on the $a_i$'s.</p>

http://mathoverflow.net/questions/91581/probability-of-a-set-of-random-vectors-over-finite-field-being-a-spanning-set/91588#91588 Will Sawin 2012-03-19T02:58:44Z 2012-03-19T06:28:01Z

<p>One vector $v=a_1^2+1$. The probability that it forms a spanning set is $1$ or less than $1$ depending on if $-1$ is a quadratic residue mod $p$.</p> <p>Edit: In the linear case, you can just set $v_1=(a_1,a_2)$, $v_2=(a_2,-a_1)$, determinant of the matrix $=a_1^2+a_2^2$. They span if and only if the determinant is nonzero, which happens if and only if $(a_1/a_2)^2\neq-1$.</p>