5
$\begingroup$

Let $q$ be a prime so that $\mathbb{Z}_q$ is a field. I would like to sample $n$ vectors independently and uniformly from $\mathbb{Z}^n_q$, to get a set $V = \{ v_i \}_{i=1}^n$. What is the probability that $V$ is a basis for $\mathbb{Z}^n_q$? I had the following proof idea, by induction. The problem reduces to what is the probability of sampling $n$ linearly independent vectors, and as such, we proceed by induction on the number of sampled vectors $k$. For $k = 1$, we only require that we are not sampling the zero vector, and as such we have that $\Pr[\{v_1\} \text{is LI} ] = 1 - q^{-n}$. Now let us suppose that we have $k$ linearly independent vectors $\{ v_i \}_{i=1}^k$. We sample a new vector $v_{k+1}$. In order for it to be linearly independent, it must be that it is not a linear combination of the others, and as such there are at most $q^k$ possible 'forbidden' values. Namely these correspond to the possible coefficients $\alpha_i$ of the linear combinations $\sum_{i=1}^k \alpha_i v_i$. So we have that $\Pr[\{v_i\}_{i=1}^{k+1} \text{is LI} \, | \, \{v_i\}_{i=1}^{k} \text{is LI}] \geq 1 - q^{k - n}$. As such we should have that

$$\Pr[\{v_i\}_{i=1}^n \text{is LI}] = \Pr[\{v_i\}_{i=1}^n \text{is LI} | \{v_i\}_{i=1}^{n-1} \text{is LI}] \Pr[\{v_i\}_{i=1}^{n-1} \text{is LI}] \geq \prod_{i=1}^n (1 - q^{i - n})$$

Do you think this analysis is correct? What I am also interested in is the following generalizations, on which I, unfortunately, had less success.

  • Suppose we set $n=3k$ and that instead of sampling the vectors independently we sample three matrices $M, M_0, M_1 \in \mathbb{Z}^{3k\times k}_q$ such that each matrix is of full rank. What would be an upper bound on the probability of the columns of said matrices spanning $\mathbb{Z}_q^{3k}$? I have found in the literature (Lemma 8) a claim that it should be at least $1 - \frac{2k}{q}$ but have not found any good argument
  • Let us relax the very first statement, and admit that $q$ could be composite. Does this change the argument significantly? I am interested in this result both in the vector case and in the three matrices sample case.

Thank you, I hope the formatting is clear enough :) For context, I am investigating whether the construction in the linked paper would hold in nonprime order groups.

$\endgroup$
3
+50
$\begingroup$

Your analysis is correct. There is possibly a typo: $i$ should be $k$. Moreover, I think it is equality. More precisely, $\{v_i\}_{i=1}^{k+1} \text{is LI} \, | \, \{v_i\}_{i=1}^{k} \text{is LI}$ if and only if $v_{k+1}$ is not a linear combination of $v_1,\ldots,v_k$. The only thing that you need to make sure is that two different linear combinations of $\{v_i\}_{i=1}^{k}$ give rise to two different vectors, which would be true since $\{v_i\}_{i=1}^{k}$ is LI. Thus $\Pr[\{v_i\}_{i=1}^{k+1} \text{is LI} \, | \, \{v_i\}_{i=1}^{k} \text{is LI}] = \frac{q^n-q^k}{q^n}$.

If it is not a field (that is $q$ is composite) then the equality may not hold as two different linear combinations can give you the same vector. To see this take $q=6$, then $v_1=(1,0,0,0,0,0)', v_2=(5,2,0,0,0,0)$, note that here $v_1+v_2 = 4v_1+4v_2=(0,2,0,0,0,0)$.

The inequality that you wrote still holds (after the typo correction:)).

Matrix Case: write $M_0|M_1|M_2$ for the augmented $3k\times 3k$ matrix. Now $M_0|M_1|M_2 \text{ is LD}$ if one of the columns in $M_1$ is linear combination of columns in $M_0$ or one of the column in $M_2$ is linear combination of columns in $M_0$ and $M_1$. Now probability that a fixed column in $M_1$ is linear combination of columns in $M_0$ is at most $\frac{q^k}{q^{3k}}\leq \frac{1}{q}$, and probability that a fixed column in $M_2$ is linear combination of columns in $M_0$ and $M_1$ is at most $\frac{q^{2k}}{q^{3k}}\leq \frac{1}{q}$. Therefore using union bound $$ \mathbb{P}(M_0|M_1|M_2 \text{ is LD}) \leq \frac{2k}{q}. $$ You can see that this bound holds even if $q$ is not a prime.

$\endgroup$
4
  • $\begingroup$ Thank you! I fixed the typo now. Let me know what you think of the matrix bound, I have an idea that would involve switching the distribution to uniform matrices which would then reduce to this case, but I would love the find out how the authors came up with their estimates :) $\endgroup$ Mar 15 at 13:37
  • 1
    $\begingroup$ @WizardOfMenlo Added the matrix part. $\endgroup$ Mar 16 at 10:44
  • 1
    $\begingroup$ In fact, I just noticed that the reasoning for the inequality will not necessarily hold in the composite case. This can happen since $v_k$ not in span of LI $v_1, ... v_{k-1}$ is not enough for linear independence. For example, take (0, 2) mod 6 which is linearly dependent by itself. $\endgroup$ Jun 20 at 18:19
  • $\begingroup$ Yes, yes..you are right!! It only holds for primes. $\endgroup$ Jun 20 at 20:03

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.