MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.