6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ You can compute the probability for any fixed short vector using the circle method. Then summing over all short vectors should give the answer. I don't know how short they have to be for this method to work. $\endgroup$
    – Will Sawin
    Jul 3 '15 at 22:26
  • $\begingroup$ @WillSawin It would be great if you could a worked example of using the circle method to do this for a specific vector. $\endgroup$
    – Giraffe
    Jul 4 '15 at 19:10
3
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The OP seems to be interested in non square matrices as well as vectors in the kernel with only integer components. Is the result if tao and vu relevant to that? $\endgroup$
    – Giraffe
    Jul 4 '15 at 19:13
  • $\begingroup$ @dorothy well, if the matrix is nonsingular, it has no vectors in the kernel, so Tao-Vu gives an upper bound for the probability of having such a vector. I don't know how close their bound is to the truth, but it is certainly a NONTRIVIAL bound. Of course, it is only relevant for $m=n,$ since otherwise there is always a non-trivial kernel, but again, the OP did ask for $m\leq n,$ so this is relevant. $\endgroup$
    – Igor Rivin
    Jul 5 '15 at 1:46
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ There are several complexities here, like that the bound is not right for short $v$, and especially for very special $v$ like a $v$ with only a couple nonzero entries. $\endgroup$
    – Will Sawin
    Jul 7 '15 at 2:43
  • $\begingroup$ @WillSawin Well, very special $v$ is not random... $\endgroup$
    – Igor Rivin
    Jul 7 '15 at 3:05
  • $\begingroup$ The bound cannot actually be super exponential, as there is a fixed vector such that the probability that it is in the kernel is $2^{-m}$. $\endgroup$
    – Will Sawin
    Jul 7 '15 at 12:57

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.