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.

  • 1
    $\begingroup$ 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$. $\endgroup$ – Zack Wolske Mar 19 '12 at 5:42
  • $\begingroup$ @Zack: Thanks for your alternative solution. I was putting too much hope for the conjecture. $\endgroup$ – John Jiang Mar 19 '12 at 5:59
  • $\begingroup$ 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$. $\endgroup$ – Will Sawin Mar 19 '12 at 6:39
  • $\begingroup$ @Will, isn't $\pi_2 =1$ and $\pi_3 < 1$ (for instance, $a_1 = a_2 = a_3 =1$ makes $v_1 = 0$). $\endgroup$ – John Jiang Mar 20 '12 at 1:34

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

  • $\begingroup$ @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. $\endgroup$ – John Jiang Mar 19 '12 at 3:49
  • $\begingroup$ Well this edit should make it correct. $\endgroup$ – Will Sawin Mar 19 '12 at 5:09
  • 1
    $\begingroup$ You want a $\neq$ at the end there. $\endgroup$ – Zack Wolske Mar 19 '12 at 5:46
  • $\begingroup$ Nice! I have no further conditions to add. $\endgroup$ – John Jiang Mar 19 '12 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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