Take the 2-minute tour ×

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:

$$ 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)$$.

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.

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.

share|improve this question
I must be misreading something. Take $v_1 = (a_1 + a_2, a_1a_2)$ and $v_2 = a_1a_2, a_1 + a_2)$. Then $\pi_2 = 1$, but $\pi_3 = 1/2$. –  Zack Wolske Mar 19 '12 at 5:42
@Zack: Thanks for your alternative solution. I was putting too much hope for the conjecture. –  John Jiang Mar 19 '12 at 5:59
Oh, here's a fun one, based on the same principle: $v_1=a_1+a_2+a_3$. It has the same $\pi_2$ and $\pi_3$. –  Will Sawin Mar 19 '12 at 6:39
@Will, isn't $\pi_2 =1$ and $\pi_3 < 1$ (for instance, $a_1 = a_2 = a_3 =1$ makes $v_1 = 0$). –  John Jiang Mar 20 '12 at 1:34
add comment

1 Answer

up vote 4 down vote accepted

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$.

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$.

share|improve this answer
@Will: thanks! I actually had an extra condition in mind, namely one the degree of each variable is at most $1$. I hope you don't mind that I uncheck your answer to keep the question open for a while. –  John Jiang Mar 19 '12 at 3:49
Well this edit should make it correct. –  Will Sawin Mar 19 '12 at 5:09
You want a $\neq$ at the end there. –  Zack Wolske Mar 19 '12 at 5:46
Nice! I have no further conditions to add. –  John Jiang Mar 19 '12 at 5:58
add comment

Your Answer


