5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$). $\endgroup$
    – Asaf
    Sep 25, 2013 at 8:52

1 Answer 1

4
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Lior Eldar
    Sep 25, 2013 at 8:15
  • $\begingroup$ 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)$ $\endgroup$ Sep 25, 2013 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.