Sum of $n$ vectors in $(\mathbb Z/n)^k$

Question

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!

Answer 1

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:

Elsholtz, C. Lower Bounds For Multidimensional Zero Sums. Combinatorica 24, 351–358 (2004).

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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 is proved. See:

Reiher, C. On Kemnitz’ conjecture concerning lattice-points in the plane. Ramanujan J 13, 333–337 (2007).

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

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

Elsholtz, C. Lower Bounds For Multidimensional Zero Sums. Combinatorica 24, 351–358 (2004).

There is a factor of $1.125$ to the $d/3$ power so there is an exponent greater than two as a lower bound.