Return to Revisions

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.