1
$\begingroup$

For positive integers $q, n, m>n$, how do we derive the lower bound $Pr[A\cdot \mathbb Z_q^m = \mathbb Z_q^n] \geq 1 - \frac{1}{q^{m-n}}$ for a uniformly random matrix $A \in \mathbb Z_q^{n \times m}$?

I know this probability is equivalent to the probability that each row has gcd 1 with q, $gcd(a_{i,1}, \dots, a_{i,m}, q) = 1$. Also, there is a lower bound on the totient function, $\varphi(q) \geq \sqrt q/\sqrt 2$, but this hasn't led me to a solution for the bound we want.

$\endgroup$
2
$\begingroup$

I think you're overthinking it.

Hint

The event in which $A\cdot \mathbb Z_q^m \neq \mathbb Z_q^n$ is the event in which the matrix $A$ has a rank defect, which is "contained" in the event in which (say) the first row is a linear combination of the other rows. Now, what's the probability of the latter event?

$\endgroup$
2
$\begingroup$

One problem is that the formula you're trying to prove isn't true in general.

One example where it is not true is $q=8, m=2, n=1$.

In this case, the random matrix $A$ consists of two values; it generates the entire space $\mathbb Z_q^n$ iff at least one of the those two values is odd; this happens with probability $\frac{3}{4}$.

However, your formula says that the probability is $\ge 1 - \frac{1}{q^{m-n}} = \frac{7}{8}$; obviously, this is not true.

Now, it is true if we restrict $q$ to be prime.

The easiest way I can think of to show that is to derive the exact probability

$$Pr[A\cdot \mathbb Z_q^m = \mathbb Z_q^n] = 1 - \sum_{i = m-n+1}^m \frac{1}{q^i}$$

(which can be done by simulating the first $n$ iterations of Gaussian Elimination; if any step fails (and step $i$ will fail with probability $\frac{1}{q^{m-i}}$), then we can generate a postimage that cannot be produced with that random matrix; if all step fails, then for any possible postimage, we can produce a preimage).

Then, we just note that this exact probability is $\ge$ to the given approximation.

$\endgroup$

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.