Probability a random matrix contains a short integer vector in its kernel Consider a random $m$ by $n$ matrix $M$ with $m \leq n$, chosen uniformly over all those whose elements are in $\{0,1\}$  (or $\{-1,1\}$ if it is any easier).    Is there any mathematical theory that can give bounds or estimates for the probability that the kernel of $M$ contains at least one short non-zero vector $v\in \mathbb{Z}^n $?
By short I mean with small $L_2$ norm.  Although I am interested in a general theory, my specific interest is in vectors no longer than $\sqrt{n}$.
Added I would also be interested in any ideas for the $L_1$ norm as well. Specifically if the $L_1$ norm is bounded by $n$ for example.
 A: For $m$ around $n/log n$ the probability goes to $0$, with $(0,1)$ or $(-1,1)$, it doesn't matter.
Combinatorial Lemma: Any set of subsets of $\{1,\dots, n\}$ which contains no pair of subsets $A, B$ with $A \subset B$ has size at most $\begin{pmatrix} n \\\lfloor n/2 \rfloor \end{pmatrix}$ elements.
Proof: Consider all paths from the empty set to the full subset that add one element at each time. Each one can intersect the set once, and there are $n!$ such paths. Each subset of size $k$ in the set must intersect $k! (n-k)!$ paths. This is minimized when $k = \lfloor n/2 \rfloor$, giving the upper bound.
Consequence: For a vector $v$ with $c$ nonzero entries, the probability that it is in the kernel of a random matrix is at most
$$ \left( \frac{ \begin{pmatrix} c \\\lfloor c/2 \rfloor \end{pmatrix}}{ 2^c}  \right)^m \approx \left( \frac{2}{\sqrt{\pi c} } \right)^m, \leq \left( \frac{1}{2} \right)^{m}$$
Proof: We may ignore the columns corresponding to the entries in the vector that are zero. So we may assume $n=c$. Each row is independent, so the probability is the probability that a single row is orthogonal to the vector, raised to the power $m$. Form a bijection between row vectors and subsets, where, if the entry in $v$ is positive, $1$ corresponds to being in the subset and $0$ or $-1$ does not, and if $v$ is negative, $0$ or $-1$ corresponds to being in the subset and $1$ does not. Then the row dot the vector is a monotonic function, so the set where it is zero contains no two subsets that dominate each other, so has the upper bound from the combinatorial lemma. Dividing it by $2^n$, we obtain the probability, and then raise it to the power $m$.
The asymptotic is well-known, though I may have the constant wrong, and the upper bound is obvious.
Now we split the short vectors into the ones with $<C$ entries and the ones with more than $C$ entries.
There are at most
$$\begin{pmatrix} n \\ C \end{pmatrix} \sqrt{n}^C \approx n^{ (3/2) C}$$
vectors with fewer than $C$ nonzero entries, and each has probability of at most $2^{-m}$ of being in the kernel, so we need:
$$ n^{ (3/2) C} < 2^m $$
There are at most $k^n$ vectors of length $<\sqrt{n}$ for a constant $k$, and each has a probability at most $(2/\sqrt{\pi C})^m$ of being in the kernel, so we need:
$$ k^n < C^{m/2} (\pi/2)^{m/2} $$
Taking $m$ a small constant multiple of $n/\log n$ and $C$ a small constant multiple of $n/(\log n)^2$ does the trick.
The improvement over Igor Rivin's bound comes only from the better estimate for the number of vectors of length $\sqrt{n}$. The proof of this is simple: Consider the sum over $v \in \mathbb Z^n$ vectors of $e^{- |v|^2}$. This is $\left( \sum_{x \in \mathbb Z} e^{-x^2} \right)^n$, and each vector of length at most $\sqrt{n}$ contributes at least $e^{-n}$, giving the desired bound. The complicated combinatorial calculations only serve to make the argument more rigorous.
A: Well, the probability that the kernel of $M$ is nontrivial is bounded above by around $(3/4)^n,$ by Tao-Vu (J. Amer. Math. Soc. 20 (2007), 603-628), so there is that.
A: Consider a random integer vector $v$ of norm bounded by $L.$ If you believe Anthony Quas' comment on this question, there are around $2^n/(L \sqrt{n})$ vectors with $0, 1$ coordinates which annihilate it, so the number of $n \times m$ matrices which annihilate $v$ is on the order of $2^{m n}/(L^m n^{m/2}),$ so the number of matrices which annihilate some vector of norm bounded by $L$ is (by the union bound) at most of order $2^{m n} L^{n-m}/n^{m/2}.$ Since there are $2^{m n}$ $0-1$ matrices in total, the probability that a given matrix has an integer vector of norm at most $L$ in the kernel is bounded above by $$f_{m, n}(L)=\frac{L^{n-m}}{n^{m/2}}.$$ For this bound to be nontrivial, we must have $$L \ll n^{\frac{m}{2 (n-m)}}.$$ In the OP's question $L \sim \sqrt{n},$ so this shows that when $m>n/2,$ the probability of having such a short vector in the kernel goes to zero, with explicit (superexponential) bound.
