for all $y \in \mathbb{Z}_q^n$, there exists $x \in \{0,1\}^m$ s.t $y=Ax \mod q$. I saw a lemma.
$m \geq 2n \log q$. Then for almost $A \in \mathbb{Z}^{n \times m}$, the subset-sums of the columns of $A$ generate $\mathbb{Z}_q^n$.
i.e. for all $y \in \mathbb{Z}_q^n$, there exists $x \in \{0,1\}^m$ s.t $y=Ax \mod q$.
It means that the function $f(x)=Ax$ is surjective.
But I dont know why.
Some reseaches said $f(x)=Ax$ is surjective by pigeonhole argument because the size of domain is bigger than the size of range.
But I think some $y$ does not have $x$ if many $x$ is mapping to one $y$.
So I think the size of domain and range cannot the reason.
Is it not correct? Let me know why.
 A: Suppose that $A$ is chosen at random from $\mathbb{Z}_q^{n \times m}$, where $q$ is prime (more generally, we can work over $\mathbb{F}_q$ and allow $q$ to be a prime power).
Fix some $y \in \mathbb{Z}_q^n$, and for $0 \neq x \in \{0,1\}^m$, let $E_x$ be the event $Ax=y$. We claim that $\Pr[E_x] = q^{-n}$. Indeed, suppose that $x_i \neq 0$. Then conditioned on all columns but the $i$th column, there is exactly one value for the $i$th column for which $Ax=y$.
We claim that moreover, if $x \neq z$ then $\Pr[E_x \land E_z] = q^{-2n}$. Suppose without loss of generality that $x_i = 0$ and $z_i = 1$. Since $E_x$ doesn't depend on the $i$th column of $A$, we can argue as follows. Choose all columns of $A$ but the $i$th ones. It is still the case that $\Pr[E_x] = q^{-n}$. Given that $E_x$ holds, there is still a unique choice of the $i$th column that will cause $Az=y$, hence this happens with probability $q^{-n}$ even given $E_x$.
Now let $I_x$ be the indicator of $E_x$, and $I = \sum_{x \neq 0} I_x$. We have
$$
\mathbb{E}[I] = (2^m-1) q^{-n}, \\
\mathbb{E}[I^2] = (2^m-1) q^{-n} + (2^m-1)(2^m-2) q^{-2n}, \\
\mathbb{V}[I] = (2^m-1) q^{-n} (1-q^{-n}).
$$
Chebyshev's inequality shows that
$$
\Pr[I \leq 0] \leq \frac{\mathbb{V}[I]}{\mathbb{E}[I]^2} \approx 2^{-m} q^n.
$$
If we choose $m = (2+\epsilon)n\log_2 q$, then the right-hand side is roughly $q^{-(1+\epsilon) n}$. This is an upper bound on the probability that $y$ is not in the range. Going over all $q^n$ possible values of $y$, we see that the probability that the range doesn't consist of all of $\mathbb{Z}_q^n$ is at most roughly $q^{-\epsilon n}$, which is $o(1)$ as a function of $n$.
