# Short lattice vectors orthogonal to a random vector

Let $N$ be some prime number. Suppose I draw $s$ elements $g_1,..., g_s$, where each $g_i\in [N]$ is taken uniformly from some interval $I_i$ of size, say $\sqrt{N}$.

Is it possible to provide a lower-bound (which works on average, or w.h.p.) on the minimal length of a vector $h\in \mathbf{Z}^s$, for which $h \cdot g = 0 (mod N)$.? Here I refer to the length of a vector as the magnitude of its largest coordinate. At least intuitively, I would say the minimal length $h$ for a "typical" $g$ is $\Omega(\sqrt{N})$.

One can assume that $s$ is much smaller than $log^a(N)$, where $a<1$, so that there is negligible chance of two disjoint subsets of $g_i$'s having the exact same sum.

-
I think you'll be interested in thm 2 of this paper by Venkatesh - math.stanford.edu/~akshay/research/andreas.pdf There's a good chance one can formulate it better (and provide a bit shorter proof) for your case, as your dealing with the homogeneous case and not the inhomogeneous one (which requires analysis of the affine group, rather than $SL$). –  Asaf Sep 25 '13 at 8:52

I left my old answer below. For very small $s$ I think that the right answer is about $M=N^{1/s}$ (for non-negative entries.) My reasoning is that one can pick all but the last entry of $h$ freely and then the last entry is forced and uniformly distributed in $[0,N-1].$ So if we run over the $k=M^{s-1}$ ways to make those choices keeping the entries under $M$, we expect the smallest possibility for that last entry to be of order $\frac{N}{M^{s-1}}$.

Here is a small experiment with $N=1009$ and $s=3$. Ten times I picked 3 random elements and then looked for the minimal vector $h$ (using non-negative entries) I expected about $p^{1/3} \approx 10$ to be enough most of the time. It got a bit higher than that but nowhere near $\sqrt{N} \gt 31.$

[855, 752, 433], [8, 7, 7]

[872, 804, 715], [4, 0, 5]

[862, 647, 603], [7, 1, 9]

[764, 731, 897], [7, 14, 13]

[352, 811, 776], [12, 8, 7]

[285, 653, 876], [13, 11, 6]

[334, 502, 752], [7, 10, 9]

[840, 788, 333], [15, 2, 15]

[48, 476, 627], [6, 1, 2]

[526, 55, 580], [7, 6, 7]

Allowing $h$ to have entries in the range $(1-p)/2,(p-1)/2]$ should (and does in similar experiments) make the max about half as big.

OLDER If $h\in \mathbf{Z}^s$ then $h$ might be said to have length $s$. Obviously that is not what you mean, but what do you mean? The separation between the first and last non-zero entries? The sum of the squares of the entries?

For either of those there is a "short" solution when $s \gt 2\sqrt[4]{N}$. Then there are $\binom{s}{2} \ge 2\sqrt{N}+\sqrt[4]{N}$ sums $g_i+g_j$ all falling in an interval of length $2\sqrt{N}.$ Hence some two are equal and there is sure to be an appropriate vector $h$ with all entries $0$ except two $+1$ and two $-1$.

If I compute correctly, then, for $s = 2\sqrt[4]{N}$, there is about an $85\%$ chance that there is $i \ne j$ with $g_i=g_j$ which allows only two non-zero entries, each $\pm 1$. For larger $s$ this becomes highly likely.

The cases above have $h\cdot g=0$ in $\mathbf{Z}$

If $s \gt \log_2{N}$ then there will have to be (disjoint) subsets with equal sum $\mod N$ and hence some appropriate vector $h$ with all entries $-1,0,1$. Probably we can keep $s$ much smaller and have such a solution with high probability. With $s \gt (1+\epsilon)\log_2{N}$ and $g_i$ chosen from $[0,N-1]$ one could even be sure to have an equal sum in $\mathbf{Z}.$

Later Thanks for clarifying. My argument for magnitude $1$ when $s \gt \log_2{N}$ still applies.

I am note sure what happens if the vector $h$ needs entries from $\mathbf{N}.$ That seems more natural (npi) to me.

Perhaps you do want to just choose the $g_i$ from $[0,N-1]$, otherwise the choice of $I_i$ matters.

Perhaps you meant fixed $s$ although it seems likely to depend on $s$. for $s=1$ one has the uniform distribution in $[0,N-1]$ or $[0,\frac{N}{2}]$ (non-negative vs integer case).

-
Great answer! still, I'm actually interested in the regime where s is significantly smaller than log(N), say smaller than $log(N)^a$ where $a<1$. In this regime counting arguments may not work. –  Lior Eldar Sep 25 '13 at 8:15
For very small $s$ the right bound is $N^{1/s}$ or about half that if $h$ has entries in the range $(-p/2,p/2)$ –  Aaron Meyerowitz Sep 25 '13 at 9:09