Welcome to MathOverflow

Question

5

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.

edited Mar 19 2012 at 4:12

asked Mar 19 2012 at 0:15

John Jiang
1,846●3●11

1

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 2012 at 5:42

@Zack: Thanks for your alternative solution. I was putting too much hope for the conjecture. – John Jiang Mar 19 2012 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 2012 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 2012 at 1:34

Will Sawin · Accepted Answer · 2012-03-19 06:28:01Z UTC

3

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

edited Mar 19 2012 at 6:28

answered Mar 19 2012 at 2:58

Will Sawin
18.5k●1●24●48

@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 2012 at 3:49

Well this edit should make it correct. – Will Sawin Mar 19 2012 at 5:09

1

You want a $\neq$ at the end there. – Zack Wolske Mar 19 2012 at 5:46

Nice! I have no further conditions to add. – John Jiang Mar 19 2012 at 5:58

Probability of a set of random vectors over finite field being a spanning set

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.