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. 



Short lattice vectors orthogonal to a random vector
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). 


