6
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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
    Commented Mar 19, 2012 at 5:42
  • $\begingroup$ @Zack: Thanks for your alternative solution. I was putting too much hope for the conjecture. $\endgroup$
    – John Jiang
    Commented Mar 19, 2012 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
    Commented Mar 19, 2012 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
    Commented Mar 20, 2012 at 1:34

1 Answer 1

Reset to default
4
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .