Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $n,k$ be positive integers. What is the smallest value of $N$ such that for any $N$ vectors (may be repeated) in $(\mathbb Z/(n))^k$, one can pick $n$ vectors whose sum is $0$?

My guess is $N=2^k(n-1)+1$. It is certainly sharp: one can pick our set to be $n-1$ copies of the set $(a_1,...,a_k)$, with each $a_i=0$ or $1$. The case $k=1$ is some math competition question (I think, but can't remember the exact reference). Does anyone know of some references? Thanks.


Thank you all! I wish I could accept all the answers, they are very helpful!

share|improve this question
    
In the title of the question, don't you mean the sum of $N$ (not $n$) vectors? –  José Figueroa-O'Farrill Dec 5 '09 at 18:18
1  
@José: I think the lowercase n is correct. It's slightly long, but a good title would be, "Minimum N st any size N set in (Z/n)^k has a size n subset summing to 0." –  Anton Geraschenko Dec 5 '09 at 18:29
1  
Indeed, the same example has no size n-1 subsets summing to 0 vector, which explains why the problem is about size n subsets. –  Ilya Nikokoshev Dec 5 '09 at 23:54

6 Answers 6

up vote 8 down vote accepted

Your guess is correct for k=1 and 2, but when k is bigger, things get more complicated. For instance, when k=n=3, N=19. For a summary of some known results, see:

http://www.ma.rhul.ac.uk/~elsholtz/WWW/papers/papers08harborth.pdf

share|improve this answer

The case k = 1 is the Erdős-Ginzburg-Ziv Theorem. Take a look at this Wikipedia article which has links to some surveys of the large literature of similar results. (The particular generalizations I'm aware of ask for a set of vectors summing to 0 whose size is the cardinality of the group, not its exponent.)

The case k = 2 is the Kemnitz conjecture, as pointed out by Kristal, and as Ricky mentioned (and also as mentioned on the Wikipedia page I linked to) it was proved by Reiher in 2003.

share|improve this answer

There was some discussion of the case n=3 in sci.math around 1994. There is a card game called Set with an 81 card deck so that each card is naturally a point in $(\mathbb Z/3)^4$. Several cards are dealt out, and your task is to identify triples of cards called Sets which form a line, or equivalently, which add up to the 0 vector. A natural question is how many points you can deal out without the existence of a line. It's not too hard to construct 9 distinct points in affine 3-space, or 20 distinct points in affine 4-space over $\mathbb Z/3$ so that there is no line contained in the points, and these are the maximums. These correspond to $N=19$ for $(n,k) = (3,3)$ and $N=41$ for $(n,k) = (3,4)$, as in the reference Ricky Liu linked, by repeating each point twice.

The maximal configurations are highly symmetric. The 9 points in dimension 3 correspond to a nondegenerate conic, which is unique up to symmetry. The 20 points in dimension 4 actually correspond to a nondegenerate conic containing 10 points in projective 3-space viewed as lines passing through the origin in affine 4-space.

For example, there are 9 points in dimension 3 satisfying $z=x^2 + y^2:$ $\{(0,0,0),(\pm1,0,1),(0,\pm1,1),(\pm1,\pm1,-1)\}$ and this set contains no lines.

share|improve this answer

The case $k=2$ is handled (extremal sequences identified) in this paper of Gao and Goldinger, which was published in the journal Integers.

share|improve this answer

While I dont know the answer to your specific question it seems related to a well known problem where you only insist that the number of simmands is non zero. Much is known about it and there are interesting open problems. When n is a prime you need (n-1)k+1 vectors (and this is sharp). This is "Olson's theorem" and it can be proved by Chevaley's theorems on non zero solutions for polynomial equations when the number of variables exceeds the degree. Maybe similar techniques (at least for the n=prime case) will work for your problem.)

The reference for Olson is: J. E. Olson, A combinatorial problem on nite abelian groups I, J. Number Theory 1 (1969), 8-10.

For the non prime power look at the paper by R. Meshulam: An uncertainty inequality and zero subsums. Discrete Math. 84 (1990), no. 2, 197--200.

For a general relevant method: N. Alon, Combinatorial Nullstellensatz. Combin. Probab. Comput. 8 (1999), no. 1-2, 7--29.

share|improve this answer

For $k$ greater than one the smallest value will be equal or less than $n^{k-1}(2n-2)+1$. To see this use the pigeonhole principle for the first $k-1$ coordinates there are only $n^{k-1}$ sets of possible values so one set of these coordinates must have $2n-1$ elements we can choose n of these that have coordinate $k$ sum to zero by the Erdős-Ginzburg-Ziv theorem then since the first $k-1$ coordinates are fixed they will sum to zero as well and we have the desired set of vectors summing to zero.

For $k=2$ there is the Kemnitz conjecture that it is $4n-3$.

I now see this conjecture isis proved. See:

http://www.springerlink.com/content/h2w35453626952n0/ We can then apply the argument of the first paragraph and get for $k=2$ or more the smallest value must be less than or equal to $n^{k-2}(4n-4)+1$.

Fort the pattern to continue the next case would be for k=3 it would be $8m-7$ there is a counterexample in fact for all odd k and n greater than 3 it is not true. The following paper was mentioned in another answer the last sentence of the abstract has the general result. http://www.ma.rhul.ac.uk/~elsholtz/WWW/papers/papers08harborth.pdf There is a factor of 1.125 to the $d/3$ power so there is an exponent greater than two as a lower bound.

share|improve this answer
2  
The Kemnitz conjecture was proved by C. Reiher in 2003. See: springerlink.com/content/h2w35453626952n0 –  Ricky Liu Dec 5 '09 at 19:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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