2
$\begingroup$

Let $[n]$ denote the subset of $2n+1$ integers with absolut value at most $n$. Consider $k$ (not necessarily different) vectors in $[n]^d$ summing up to zero. What is the smallest $k>1$ (for fixed $n$ and $d$) that assures the existence of a strict subsequence of vectors also summing up to zero?

I am most interested in the case $n=1$.

Improve this question
$\endgroup$
3
  • $\begingroup$ Some bounds may be deduced from the case $d=1$ where I believe the answer is about $2n$. $\endgroup$
    – user27328
    Dec 8, 2012 at 17:52
  • $\begingroup$ Could you please clarify if you allow repetions of the same vector? (I am unsure, on the one hand you say 'subset' which suggests not, on the other hand you say for d=1 it should be about 2n which seems wrong without repetition.) $\endgroup$
    – user9072
    Dec 8, 2012 at 18:03
  • $\begingroup$ Sorry, I allow repretitions. Eg for $d=1$ for the starting sequence $(-1,-1,-1,-1,2,2)$ I can choose $(-1,-1,2)$, but for $(-1,-3,2,2)$ I cannot choose $(-1,-1,2)$ as $-1$ appears only once in the original sequence. $\endgroup$
    – user27328
    Dec 8, 2012 at 18:30

2 Answers 2

Reset to default
3
$\begingroup$

For n=1 we have recently solved the problem, the answer is around $d^d$, see http://arxiv.org/abs/0912.0424 By we I mean my coauthors and by solve I mean gave a reasonable lower and upper bound.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for the answer. I see there is a lower bound for m problem. Does your paper also imply that if I have around $d^d$ vectors, then I can found a subsequence summing up to zero? $\endgroup$
    – user27328
    Dec 8, 2012 at 19:12
  • $\begingroup$ I think that follows from the Steinitz lemma. $\endgroup$
    – domotorp
    Dec 8, 2012 at 21:33
  • $\begingroup$ Could you please be more specific? $\endgroup$
    – user27328
    Dec 9, 2012 at 2:51
  • $\begingroup$ In the paper there is a detailed description of how to use the Steinitz lemma to prove an upper bound. The main idea is that if we can order the vectors $v_i$ such that for any $k$ we have $\sum_{i=1}^k v_i$ is in $[-d,d]^d$, then for some $k_1$ and $k_2$ these sums are close, so their difference is also small. Since in your case all vectors are integers, the difference is also an integer, thus the all zero vector. $\endgroup$
    – domotorp
    Dec 9, 2012 at 16:41
2
$\begingroup$

To complement domotrop's answer with info on the general problem:

Bounds for the general problem (even a more general problem, considering arbitrary prescribed subsets of admissible vectors) were obtained by Diaconis, Graham, Sturmfels 'Primitive Partition Identities'.

In addition, for the case $d=1$ the precise value $2n-1$ is established.

The general upper bound is of the form $$(2d)^d (d+1)^{d+1} D$$ where $D$ is the largest absolute value of the determinant of any $d$ of the admissible vectors.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I couldn't resist upvoting... $\endgroup$
    – user5117
    Dec 8, 2012 at 19:14
  • $\begingroup$ @Artie Prendergast-Smith: yes, I like the result, too. And, thanks for the vote. $\endgroup$
    – user9072
    Dec 8, 2012 at 19:33
  • $\begingroup$ Thanks! So for n=1 I get more or less d^{3d}? $\endgroup$
    – user27328
    Dec 9, 2012 at 2:53
  • $\begingroup$ @Wajcha: you are welcome! Regarding your question: you could save about a d^(d/2) by using Hadamard's bound to bound the D by d^(d/2) (which can be optimal). But, of course, it is still much worse than domptorp's bound in this case. $\endgroup$
    – user9072
    Dec 9, 2012 at 11:05

Your Answer

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