Lower bounds for multidimensional zero sums

Christian Elsholtz

July 16, 2004

Abstract

Let f(n, d) denote the least integer such that any choice of f(n, d) elements in ℤ_{n}^{d} contains a subset of size n whose sum is zero. Harborth proved that (n − 1)2^{d} + 1 ≤ f(n, d) ≤ (n − 1)n^{d} + 1. The upper bound was improved by Alon and Dubiner to c_{d} n. It is known that f(n, 1) = 2n − 1 and Reiher proved that f(n, 2) = 4n − 3. Only for n = 3 it was known that f(n, d) > (n − 1)2^{d} + 1, so that it seemed possible that for a fixed dimension, but a sufficiently large prime p, the lower bound might determine the true value of f(p, d). In this note we show that this is not the case. In fact, for all odd n ≥ 3 and d ≥ 3 we show that f(n, d) ≥ 1.125^{⌊ \frac{d}{3} ⌋}(n − 1)2^{d} + 1.

1 Introduction

A classical result of Erdős, Ginzburg, and Ziv [8] states that amongst any 2n − 1 integers one can choose n such that their sum is divisible by n.

Harborth [14] considered the corresponding problem for d-dimensional integer lattices. Let f(n, d) denote the minimal number such that any choice of f(n, d) not necessarily distinct vectors v_{i} ∈ ℤ_{n}^{d} contains a subset of n vectors whose sum is 0 ∈ ℤ_{n}^{d}. Harborth proved that

(n − 1)2^{d} + 1 ≤ f(n, d) ≤ (n − 1)n^{d} + 1.

The lower bound follows from the example in which there are n − 1 copies of each of the 2^{d} vectors with entries 0 or 1. The upper bound follows since any set of (n − 1)n^{d} + 1 vectors must contain, by the pigeonhole principle, n vectors which are equivalent modulo n.

The upper bound was greatly improved upon by Alon and Dubiner [2]:

f(n, d) ≤ c_{d}n.

For composite integers n = n_{1}n_{2} an upper bound on f(n, d) is induced by upper bounds on f(n_{1}, d) and f(n_{2}, d) as follows (see Harborth [14]):

f(n_{1}n_{2}, d) ≤ min {f(n_{1}, d) + (f(n_{2}, d) − 1)n_{1}, f(n_{2}, d) + (f(n_{1}, d) − 1)n_{2}} .

(1)

One therefore often restricts the consideration to a prime argument n = p.

For d = 2 it was conjectured that f(n, 2) = 4n − 3, so that the lower bound would determine the correct value. In fact it suffices to prove this conjecture for prime values of n, since the conjecture then follows by (1). There were partial results in favour of this conjecture, see Kemnitz [16], as well as Gao [10], [11], [12], and Thangadurai [21]. Rónyai [20] proved that for primes p one has f(p, 2) ≤ 4p − 2, which implies that f(n, 2) ≤ 4.1 n. Gao [13] extended this to powers of primes: f(p^{a}, 2) ≤ 4p^{a} − 2. Reiher [19] eventually proved this conjecture: f(n, 2) = 4n − 3.

For d ≥ 3 very little is known.

f(2^{a}, d) = (2^{a} − 1)2^{d} + 1  see Harborth [14],
f(3, 3) = 19  see Harborth [14], Brenner [3],
f(3, 4) = 41  see Pellegrino [18], Brown and Buhler [4],

Brenner [3], Kemnitz [16],

91 ≤ f(3, 5) ≤ 121  see Kemnitz [15],
f(3, 5) = 91  see Edel et al. [7], Davis and Maclagan [5]
225 ≤ f(3, 6) ≤ 229  see Davis and Maclagan [5]
f(3, 18) ≥ 300 × 2^{12}  see Frankl, Graham, Rödl [9],
f(3, d) ≥ 2.179^{d} for d ≥ d′  see Frankl, Graham, Rödl [9],
f(3, d) ≥ 2.217389^{d} for d ≥ d′  see Edel [6]
f(n, d) = o(n^{d}) for fixed n, as d → ∞ see Alon, Dubiner [2]

where d′ is sufficiently large. The result f(3, d) = o(3^{d}) (Brown and Buhler [4], and Frankl, Graham and Rödl [9]) can be derived from the Szemerédi-Roth theorem on arithmetic progressions of length 3. Ruzsa proved that f(3, d) = O (\frac{3^{d}}{\sqrt{d}}) holds (see Meshulam [17]) and Meshulam proved a more general result on arithmetic progressions of length three in finite abelian groups which implies as a special case f(3, d) = O (\frac{3^{d}}{d} ) (see also [17]).

The exact determination of f(n, d) is a very difficult problem. Harborth’s lower bound has been improved only in the above mentioned very few special cases with n = 3. Not a single case for odd n > 3 was known with f(n, d) > 2^{d}(n − 1) + 1. It seemed conceivable that for any fixed dimension and a sufficiently large prime p the lower bound determines the correct value of f(p, d). In this note we show that this is not the case. We prove the following theorem:

Theorem. Let n ≥ 3 be an odd integer. The following inequality holds:

f(n, d) ≥ 1.125^{⌊ \frac{d}{3} ⌋}(n − 1)2^{d} + 1.

Formally, the bound is also valid for d = 1 and d = 2, but is not new in these cases. This theorem has a number of simple corollaries:

Corollary 1. For fixed d this implies that the constant c_{d} in Alon and Dubiner’s result must satisfy

c_{d} ≥ 2^{d}1.125^{⌊ \frac{d}{3} ⌋}.

If we take a fixed n and a large dimension d, then this implies:

Corollary 2. For odd n and sufficiently large d ≥ d′ the following lower bound holds:

f(n, d) ≥ 2.08^{d}.

For n = 3 this is weaker than the existing bound f(3, d) ≥ 2.217389^{d} (for large d).

It is interesting to note that we have for the general case considered in the Theorem a simple and uniform proof based on only one particular value: f(3, 3) = 19. It is not surprising that this can be extended to f(3, d), but it is certainly surprising that the proof can be extended to different n.

For the related problem, where g(n, d) denotes the minimal number such that any set of g(n, d) distinct vectors in ℤ_{n}^{d} has a zero sum of length n, we show similar bounds. It is known that g(n, d) ≥ (n − 1)2^{d−1} + 1 for n ≥ 3, and g(n, d) ≥ n2^{d−1} + 1 for even n, g(3, 3) = 10, g(3, 4) = 21, (see Harborth [14], Brenner [3], Frankl, Graham and Rödl [9], and Kemnitz [15], [16]). By the pigeonhole principle we have that g(n, d) ≥ \frac{f(n,d)−1}{n−1} + 1. Therefore the theorem immediately implies the following

Corollary 3. Let n ≥ 3 be an odd integer. The following bound holds:

g(n, d) ≥ 1.125^{⌊ \frac{d}{3} ⌋}2^{d} + 1.

In particular, for large d:

g(n, d) ≥ 2.08^{d}.

For fixed d and large n the corollary is much weaker than the theorem. One trivially has that n ≤ g(n, d). The lower bound of the corollary is independent of n and therefore in this respect not optimal. But for fixed n and large d the corollary above may be of interest.

2 Proof

In the proof of the theorem we start off from Harborth’s example which shows that f(3, 3) ≥ 19. We first extend this in dimension 3 from n = 3 to arbitrary n. We then increase the dimension by an explicit product construction.

We take the 9 vectors considered by Harborth but we consider these in ℤ_{n}^{3} (not only in ℤ_{3}^{3}).

(\begin{matrix}2 \\ 1 \\ 2 \end{matrix}) , (\begin{matrix}0 \\ 0 \\ 0 \end{matrix}) , (\begin{matrix}0 \\ 0 \\ 1 \end{matrix}) , (\begin{matrix}0 \\ 1 \\ 0 \end{matrix}) , (\begin{matrix}0 \\ 1 \\ 1 \end{matrix}) , (\begin{matrix}1 \\ 0 \\ 0 \end{matrix}) , (\begin{matrix}1 \\ 0 \\ 1 \end{matrix}) , (\begin{matrix}1 \\ 1 \\ 2 \end{matrix}) , (\begin{matrix}1 \\ 2 \\ 2 \end{matrix}) .

If n ≥ 3, then these vectors are distinct in ℤ_{n}^{3}. We shall prove: Lemma. Let n ≥ 3 be an odd integer. If any n vectors taken from a multiset of the above 9 vectors add to 0 ∈ ℤ_{n}^{3}, then necessarily one has taken n times the very same vector.

To avoid such kind of zero sum our example in d = 3 starts off with n − 1 copies of each of the above 9 elements in ℤ_{n}^{3}. In dimension d > 3 we construct our vectors as follows. Up to dimension 3⌊\frac{d}{3}⌋ we take all 9^{⌊ \frac{d}{3} ⌋} vectors which are composed out of any of the 9 vectors in the coordinates 3i + 1 up to 3i + 3, where i = 0, …, ⌊\frac{d−3}{3}⌋. In the remaining d_{0} = 0, 1 or 2 coordinates we take all 2^{d_{0}} combinations of vectors composed of 0 and 1 only. Note that 2^{d_{0}} × 2^{3⌊ \frac{d}{3} ⌋} = 2^{d}. We take any of these vectors n − 1 times such that the total number of used vectors is 1.125^{⌊ \frac{d}{3} ⌋}2^{d}(n − 1).

Suppose that there is a choice of n vectors which sums to the zero vector, modulo n. Any choice of n vectors which sums in the last d_{0} coordinates to 0 or n must necessarily have n times the same value of ε_{i} ∈ {0, 1}. Moreover, we use the lemma for triples of dimensions (3i + 1, 3i + 2, 3i + 3), where i = 0, … ⌊\frac{d−3}{3}⌋. Suppose for a moment the lemma is proven: then a zero sum must take in these three coordinates n copies of the same entries. But since there are n − 1 copies of each d-dimensional vector only, the n vectors cannot be identical. They differ in at least one of the three dimensions 3i + 1 up to 3i + 3 (say) or in the last d_{0} dimensions). In these dimensions there is no zero sum of length n, which proves the theorem.

It is therefore sufficient to prove the lemma. Suppose our choice of the n vectors uses a_{i} copies of the i-th vector, where i = 1, …, 9 and where 0 ≤ a_{i} ≤ n − 1. We then have the following system of equations.

(1) a_{1} + a_{2} + a_{3} + a_{4} + a_{5} + a_{6} + a_{7} + a_{8} + a_{9} = n
(2) 2a_{1}  + a_{6} + a_{7} + a_{8} + a_{9} ≡ 0 mod n
(3) a_{1}  + a_{4} + a_{5}  + a_{8} + 2a_{9} ≡ 0 mod n
(4) 2a_{1}  + a_{3}  + a_{5}  + a_{7} + 2a_{8} + 2a_{9} ≡ 0 mod n.

We show first that the three expressions on the left hand side of (2), (3), and (4) must be equal to n. In order to see this, we must consider various cases. Case 1) In equation (2) we must exclude that 2a_{1} + a_{6} + a_{7} + a_{8} + a_{9} = 0 or ≥ 2n. Similarly, cases 2) and 3) will treat the equations (3) and (4). Case 1a) Equation (1) and 0 ≤ a_{i} < n shows that 2a_{1}+a_{6}+a_{7}+a_{8}+a_{9} < 2n. Case 1b) So let us suppose for a contradiction that 2a_{1}+a_{6}+a_{7}+a_{8}+a_{9} = 0. This implies that a_{1} = a_{6} = a_{7} = a_{8} = a_{9} = 0. Our system of equations simplifies to

(1′) a_{2} + a_{3} + a_{4} + a_{5} = n
(3′)  a_{4} + a_{5} ≡ 0 mod n
(4′)  a_{3}  + a_{5} ≡ 0 mod n.

Moreover

\begin{aligned}(1′) − (3′) & a_{2} & + & a_{3} & & & ≡ 0 mod n \\ (1′) − (4′) & a_{2} & & & + & a_{4} & ≡ 0 mod n. \end{aligned}

If we assume that a_{4} + a_{5} = n, then a_{2} = a_{3} = 0, by (1′). But then by (1′) − (4′): a_{4} ≡ 0 mod n. Then 0 ≤ a_{i} < n shows that a_{4} = 0, so that a_{5} = n, a contradiction to a_{5} < n. Similarly, if we assume that a_{2}+a_{3} = n, so that a_{4} = a_{5} = 0, then the same kind of contradiction follows from (1′)−(4′): a_{2} ≡ 0 mod n, and a_{3} = n. Case 2a) Since a_{9} < n we can exclude that

(3) a_{1} + a_{4} + a_{5} + a_{8} + 2a_{9} ≥ 2n.

Case 2b) So, let us suppose that

(3) a_{1} + a_{4} + a_{5} + a_{8} + 2a_{9} = 0,

which implies that a_{1} = a_{4} = a_{5} = a_{8} = a_{9} = 0.

Our system of equations then is

(1′) a_{2} + a_{3} + a_{6} + a_{7} = n
(2′)  a_{6} + a_{7} = n  by case 1)
(4′)  a_{3}  + a_{7} ≡ 0 mod n.

This implies a_{2} = a_{3} = 0. Then (4′) implies that a_{7} ≡ 0 mod n, i.e. a_{7} = 0, which contradicts a_{6} < n. Case 3a) Suppose that

(4) 2a_{1} + a_{3} + a_{5} + a_{7} + 2a_{8} + 2a_{9} ≥ 2n.

Then 2(1) − (4) gives

2a_{2} + a_{3} + 2a_{4} + a_{5} + 2a_{6} + a_{7} ≤ 0,

so that

a_{2} = a_{3} = a_{4} = a_{5} = a_{6} = a_{7} = 0.

Our system of equations then is:

(1′) a_{1} + a_{8} + a_{9} = n
(2′) 2a_{1} + a_{8} + a_{9} = n  by case 1)
(3′) a_{1} + a_{8} + 2a_{9} = n  by case 2).

This implies that a_{1} = a_{9} = 0, a_{8} = n, which contradicts a_{8} < n. Case 3b) So, we assume that

(4) 2a_{1} + a_{3} + a_{5} + a_{7} + 2a_{8} + 2a_{9} = 0,

which implies

a_{1} = a_{3} = a_{5} = a_{7} = a_{8} = a_{9} = 0.

By equation (2) we see that a_{6} = n, which contradicts a_{6} < n.

The above case study shows that the left hand sides of (1), (2), (3), (4) are all equal to n. Let us look at equation

(1) + (4) − (2) − (3) a_{2} + 2a_{3} + a_{5} + a_{7} + a_{8} = 0.

Because of 0 ≤ a_{i} we find that

a_{2} = a_{3} = a_{5} = a_{7} = a_{8} = 0.

Therefore equation (4) simplifies to

2a_{1} + 2a_{9} = n,

which is a contradiction, since n is odd, by assumption. ■ Remarks:

It seems conceivable that starting off from other examples for small fixed n and d, one might be able to improve the lower bound. But it is not at all obvious that this will work for any particular value of f(n, d). It is indeed somewhat surprising that an argument modulo 3 can be extended to an argument modulo all odd integers.

For even n the lower bound cannot hold in general since for n = 2^{a} one knows that f(2^{a}, d) = (2^{a} − 1)2^{d} + 1.

The author would like to thank N. Alon, T. Bekehermes, I. Ruzsa, the anonymous referees, and in particular S. Kubertin for remarks on an earlier version of this manuscript.

References

[1] Alon, N.; Dubiner, M.; Zero-sum sets of prescribed size. Combinatorics, Paul Erdős is eighty, Vol. 1, 33–50, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993.

[2] Alon, N.; Dubiner, M.; A lattice point problem and additive number theory. Combinatorica 15 (1995), 301–309.

[3] Brenner, J.L.; Problem 6298, Amer. Math. Monthly, 89 (1982), 279–280.

[4] Brown, T.C.; Buhler, J.P.; A density version of a geometric Ramsey theorem. J. Combin. Theory Ser. A 32 (1982), 20–34.

[5] B. L. Davis and D. Maclagan: The card game SET. Mathematical Intelligencer 25 (No. 3), 2003, 33-40.

[6] Y. Edel: Extensions of generalized product caps. Des. Codes Cryptogr. 31 (2004), no. 1, 5–14.

[7] Y. Edel, S. Ferret, I. Landjev and L. Storme, The classification of the largest caps in AG(5, 3). J. Combin. Theory Ser. A 99 (2002), no. 1, 95–110.

[8] Erdős, P.; Ginzburg, A.; Ziv, A.; Theorem in the additive number theory, Bull. Res. Council Israel 10F (1961), 41–43.

[9] Frankl, P.; Graham, R.L.; Rödl, V.; On subsets of abelian groups with no three term arithmetic progression. J. Combin. Theory Ser. A 45 (1987), 157–161.

[10] Gao, W.; On zero-sum subsequences of restricted size, J. Number Theory, 61 (1996), 97–102.

[11] Gao, W.; A combinatorial problem on finite abelian groups, J. Number Theory, 58 (1996), 100–103.

[12] Gao, W.; Two zero-sum problems and multiple properties, J. Number Theory, 81 (2000), 254-265.

[13] Gao, W.; Note on a zero-sum problem. J. Combin. Theory Ser. A 95 (2001), 387–389.

[14] Harborth, H.; Ein Extremalproblem für Gitterpunkte. J. Reine Angew. Math. 262/263 (1973), 356–360.

[15] Kemnitz, A.; Extremalprobleme für Gitterpunkte. Ph.D. Thesis, Technische Universität Braunschweig, (1982).

[16] Kemnitz, A.; On a lattice point problem. Ars Combin. 16 (1983), B, 151–160.

[17] Meshulam, R.; On subsets of finite abelian groups with no 3-term arithmetic progressions. J. Combin. Theory Ser. A 71 (1995), 168–172.

[18] G. Pellegrino: Sul massimo ordine delle calotte in S_{4,3}. Matematiche (Catania) 25 (1970), 149–157 (1971).

[19] C. Reiher, Kemnitz’ Conjecture Concerning Lattice-Points in the Plane, manuscript.

[20] Rónyai, L.; On a conjecture of Kemnitz. Combinatorica 20 (2000), 569– 573.

[21] Thangadurai, R.; On a conjecture of Kemnitz. C. R. Math. Acad. Sci. Soc. R. Can. 23 (2001), no. 2, 39–45.

Christian Elsholtz

Department of Mathematics Royal Holloway, University of London Egham Surrey TW20 0EX UK

christian.elsholtz@rhul.ac.uk
2000 Mathematics Subject Classification:
Primary:
11B50 Sequences (mod m)
Secondary:
05D05 Extremal set theory