ZERO SUMS IN FINITE CYCLIC GROUPS

W. D. Gao^{1}

Department of Computer Science and Technology, University of Petroleum, Beijing, China, 102200.

Received: 12/12/99, Accepted: 10/31/00, Published: 11/6/00

Abstract

Let C_{n} be the cyclic group of n elements, and let S = (a_{1}, ⋯, a_{k}) be a sequence of elements in C_{n}. We say that S is a zero sequence if ∑_{i=1}^{k} a_{i} = 0 and that S is a minimal zero-sequence if S is a zero sequence and S contains no proper zero subsequence. In this paper we prove, among other results, that if S is a minimal zero sequence of elements in C_{n} and |S| ≥ n − [\frac{n+1}{3}] + 1, then there exists an integer m coprime to n such that |ma_{1}|+⋯+|ma_{k}| = n, where |x| denotes the least positive inverse image under the natural homomorphism from the additive group of integers Z onto C_{n}. On the other hand, we give some explicit minimal zero sequences of length [\frac{n+1}{2}] + 1 not having this property above.

1. Introduction

Let G be a finite abelian group. Let S = (a_{1}, ⋯, a_{k}) be a sequence of elements in G. By σ(S) we denote the sum ∑_{i=1}^{k} a_{i}. We say that S is a zero sequence if σ(S) = 0, that S is a zero-free sequence if S contains no nonempty zero subsequence, and that S is a minimal zero sequence if S is a zero sequence and S contains no proper zero subsequence. By ∑(S) we denote the set consisting of all elements which can be expressed as a sum over a nonempty subsequence of S, i.e.

∑(S) = {σ(T)|T is a nonempty subsequence of S}

Sometimes we also write S = ∏_{i=1}^{k} a_{i}. If T is a subsequence of S, by ST^{−1} we denote the subsequence W such that W T = S. We say subsequences S_{1}, ⋯, S_{r} of S are disjoint if S_{1} ⋯ S_{r} is a subsequence of S. For every g ∈ G, we use v_{g}(S) to denote the number of the times that g occurs in S.

Let C_{n} be the cyclic group of order n. For every x ∈ C_{n}, we define |x| to be the least positive inverse image under the natural homomorphism from the additive group of integers Z onto C_{n}. For example, |0| = n. Let S = (a_{1}, ⋯, a_{k}) be a sequence of elements in C_{n}, by |S|_{n} we denote the sum ∑_{i=1}^{k} |a_{i}|. Define

Index(S) = min_{(m,n)=1}{|mS|_{n}}

1This work has been supported partly by the National Natural Science Foundation of China and the Foundation of Education Committee of China.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A12 2

Index(C_{n}) was first introduced by Chapman, Freeze, and Smith in [2]. It is well known that if S is a minimal zero sequence of n elements in C_{n}, then S = (\underbrace{a, ⋯, a}_{n}) for some a generating C_{n}.

Hence, Index(S) = n. From a result of ([3], Lemma 2 ) we can easily derive that every minimal zero sequence S of elements in C_{n} with |S| ≥ n − [n/4] satisfies Index(S) = n. In Section 2 of this paper, we prove that the last conclusion holds for the restriction of |S| ≥ n−[n/4] replaced by |S| ≥ n − [n/3] + 1; In Sectoin 3 we study the sums of divisors of a positive integer n; the final section 4 contains some conculding remarks.

2. On Index(S)

Definition. Let l(C_{n}) be the minimal integer t such that every minimal sequence S of at least t elements in C_{n} satisfies Index(S) = n.

Theorem 2.1 (1). [\frac{n+1}{2}] + 1 ≤ l(C_{n}) ≤ n − [\frac{n+1}{3}] + 1 holds for all n ≥ 8.

(2). l(C_{n}) = 1 for n = 1, 2, 3, 4, 5, 7 and l(C_{6}) = 5.

Lemma 2.2 ([1]) Let n − 2k ≥ 1, and let S = (a_{1}, ⋯, a_{n−k}) be a zero-free sequence of n − k elements in C_{n}. Then there is an element g ∈ C_{n} such that v_{g}(S) ≥ n − 2k + 1.

Lemma 2.3 ([4]) Let S be a zero-free sequence of elements in C_{n}, and let g ∈ C_{n} with order(g) = n/m. Suppose that |S| > n/2. Then v_{g}(S) < \frac{n−|S|}{m−1}.

Lemma 2.4 ([4]) Let S be a zero-free sequence of elements in an abelian group, and let S_{1}, ⋯, S_{k} be disjoint subsequences of S. Then, | ∑(S)| ≥ ∑_{i=1}^{k} | ∑(S_{i})|.

Let S = (a_{1}, ⋯, a_{k}) and T = (b_{1}, ⋯, b_{k}) be two sequences of elements in C_{n} with the same length. We say S is similiar to T if there exists an integer m coprime to n and a permutation δ of {1, ⋯, k} such that a_{i} = mb_{δ(i)} for i = 1, ⋯, k. Denote it by S ∼ T.

Lemma 2.5 Let 1 ≤ k ≤ [\frac{n+1}{3}], and let S be a zero-free sequence of n − k elements in C_{n}. Then

S ∼ (\underbrace{1, ⋯, 1}_{n−2k+1}, x_{1}, ⋯, x_{k−1})

with ∑_{i=1}^{k−1} |x_{i}| ≤ 2k − 2. Therefore, Index(S) < n.

Proof. By Lemma 2.2, there is an element g ∈ C_{n} such that v_{g}(S) ≥ n − 2k + 1 ≥ k = n − |S|. It follows from Lemma 2.3 that order(g) = n. Without loss of generality, we may assume that g = 1. Set l = v_{g}(S). Suppose S = 1^{l} ∏_{i=1}^{t} a_{i}, where l + t = |S| . Since S is zero-free, we clearly have

1 ≤ |a_{i}| ≤ n − l − 1 for i = 1, ⋯, t.  (1)

If |a_{t}| ≥ l + 1, then | ∑(1^{l}a_{t})| = 2l + 1. By Lemma 2.4, n − 1 ≥ | ∑(S)| ≥ | ∑(1^{l}a_{t})| + t − 1 ≥ 2l + t = n − k + l ≥ n − k + n − 2k + 1 ≥ n, a contradiction. Hence,

1 ≤ |a_{i}| ≤ l for i = 1, ⋯, t  (2)

Since S is zero-free, 1 ≤ |a_{1} + a_{2}| ≤ n − l − 1. By (1) and (2), |a_{1}| + |a_{2}| ≤ n − 1. Therefore, |a_{1}| + |a_{2}| = |a_{1} + a_{2}| ≤ n − l − 1. Similarly, one can get |a_{1}| + |a_{2}| + |a_{3}| = |a_{1} + a_{2}| + |a_{3}| = |a_{1} + a_{2} + a_{3}| ≤ n − l − 1. Finally, we must get ∑_{i=1}^{t} |a_{i}| = | ∑_{i=1}^{t} a_{i}| ≤ n − l − 1. Therefore, Index(S) ≤ n − 1. □

Proof of Theorem 2.1. (1). We first prove the upper bounds. Let S be a minimal zero sequence of elements in C_{n} with |S| ≥ n − [\frac{n+1}{3}] + 1. Take an arbitrary element x from S. Then Sx^{−1} is zero-free. By Lemma 2.5, Index(S) ≤ Index(Sx^{−1}) + n − 1 ≤ n − 1 + n − 1 < 2n. Hence, Index(S) = n.

To prove the lower bounds we distinguish four cases.

Case 1. n is odd. Set S = (\underbrace{1, ⋯, 1}_{\frac{n−5}{2}}, \frac{n+3}{2}, \frac{n+3}{2}, \frac{n−1}{2}). Note that for n ≥ 9, clearly Index(S) =

2n. Therefore, \frac{n+1}{2} + 1 ≤ l(C_{n}).

Case 2. n is even and n ≥ 12. Set

S = (\underbrace{1, ⋯, 1}_{\frac{n−6}{2}}, \frac{n+4}{2}, \frac{n+4}{2}, \frac{n−2}{2}). Clearly Index(S) = 2n. Therefore, [\frac{n+1}{2}] + 1 ≤ l(C_{n}).

Case 3. n = 8 , set S = (1, 4, 5, 6). It is easy to check that S is a minimal zero sequence and that Index(S) = 16. Therefore [9/2] + 1 = 4 + 1 ≤ l(C_{8}).

Case 4. n = 10, set S = (1, 5, 8, 3, 3). It is easy to check that S is a minimal zero sequence and that Index(S) = 20. Therefore [11/2] + 1 = 5 + 1 ≤ l(C_{10}).

(2). It is proved in [2] that l(C_{n}) = 1 for n = 1, 2, 3, 5, 7. For n = 4, it is easy to see that l(C_{4}) = 1. For n = 6, by Lemma 2.5, we clearly have l(C_{6}) ≤ 5. For S = (1, 3, 4, 4) it is clear that Index(S) = 12. Therefore l(C_{6}) = 5. □

Let S be a zero-free (resp. minimal zero) sequence of elements in an abelian group G. We say S is splitable if there exists an element a ∈ S and two elements x, y ∈ G such that x+y = a and such that Sa^{−1}xy is zero-free (resp. minimal zero) sequence as well.

Proposition 2.6 Let S be a minimal zero subsequence with |S| = l(C_{n}) − 1. Suppose that Index(S) > n. Then S is not splitable.

Proof. Assume to the contrary that S is splitable. Then there exist a ∈ S and x, y ∈ C_{n} such that Sa^{−1}xy is also a minimal zero squenece. Since, |Sa^{−1}xy| = l(C_{n}), by the definition of l(C_{n}), Index(Sa^{−1}xy) = n. Therefore, Index(S) ≤ Index(Sa^{−1}xy) = n, a contradiction. This proves the proposition. □

Conjecture 2.7 Let S be a minimal zero subsequence with |S| = l(C_{n}) − 1. Suppose that S is not splitable. Then Index(S) = 2n.

This conjecture, if true, would be useful for determining l(C_{n}).

Theorem 2.8 Let G be a finite abelian group and let G = C_{n_{1}} ⊕ ⋯ ⊕ C_{n_{k}} be a decomposition of G into direct summands, where all n_{i} > 1. Let C_{n_{i}} = ⟨e_{i}⟩ for i = 1, ⋯, k. Then the sequence S = (e_{1} + ⋯ + e_{k}) ∏_{i=1}^{k} e_{i}^{n_{i}−1} is not splitable.

Proof. Clear. □

Conjecture 2.9 Let G = C_{n_{1}}⊕⋯⊕C_{n_{k}} be a finite non-cyclic abelian group with 1 < n_{1}| ⋯ |n_{k}, and let S be a minimal zero sequence of elements in G. Suppose that ⟨S⟩ = G and suppose that S is not splitable. Then S contains at least k + 1 distinct elements.

Definition. Let sp(G) be the largest integer t such that every minimal zero sequence of elements in G with |S| ≤ t is splitable.

Problem. Determine sp(G).

We clearly have, log_{2}(\frac{|G|}{2}) ≤ sp(G) ≤ l(G) − 1.

Conjecture 2.10 sp(G) ≤ c ln |G| for some absolute constant c.

Define

I(C_{n}) = max_{S}{Index(S)},

where S runs over all minimal zero sequences of elements in C_{n}.

Proposition 2.11 I(C_{n}) ≥ \frac{n+1}{2}(1 + [log_{3}(\frac{n}{3})]) + 1.

Lemma 2.12 If a is an element in C_{n}, then |ma| + |m(n − 2a)| > n/2 holds for every integer m coprime to n.

Proof. If |ma| > n/2 then we are done. Otherwise, |ma| < n/2, then

|ma| + |m(n − 2a)| = |ma| + n − 2|na| = n − |ma| > n/2. □

Proof of Proposition 2.11. Let t = [log_{3}(\frac{n}{3})], set T = (1, 3, 3^{2}, ⋯, 3^{t}, n−2, n−6, n−18, ⋯, n−2× 3^{t}) = ∏_{i=0}^{t}(3^{i}, n−2×3^{i}). Since 3^{i+1} > 2 ∑_{j=1}^{i} 3^{i} for i = 0, ⋯, t−1 and 2 ∑_{i=1}^{t} 3^{i} = 3^{t+1}−1 < n, T is zero-free. Let m be the positive integer coprime to n such that Index(T) = |mT |. By Lemma 2.12, Index(T) = |mT | = ∑_{i=0}^{t}(|m3^{i}|+|m(n−2×3^{i})| ≥ \frac{n+1}{2}(t+1). Set S = T ·(−σ(T)). Then S is a minimal zero sequence with Index(S) ≥ Index(T) + 1 ≥ \frac{n+1}{2}(t + 1) + 1. □

3. Sums of Divisors of n

In [5], Lemke and Kleitman proved, among other results, that if S = (a_{1}, ⋯, a_{n}) is a sequence of positive integer and a_{i}|n holds for every i = 1, ⋯, n then there is a subsequence T of S with σ(T) = n. Here we shall show a generaliztion of this result.

Theorem 3.1 Let S = (a_{1}, ⋯, a_{k}, b_{1}, ⋯, b_{n−k}) be a sequence of n positive integers. Suppose that a_{i}|n for i = 1, ⋯, k, and suppose that all of b_{i} are distinct and b_{i} ≤ n for i = 1, ⋯, n − k. Then, there is a subsequence T of S with σ(T) = n.

Lemma 3.2 Let A be a subset of [0, n], and B \ {0} a set of positive divisors of n. Suppose that 0 ∈ A ∩ B and suppose that n ∉ A + B. Then, |(A + B) ∩ [0, n]| ≥ |A| + |B| − 1, where [0, n] = {0, 1, 2, ⋯, n − 1, n}.

Proof. We proceed by induction on |B|. |B| = 1 implies B = {0} and the lemma is trivial. Assume that the lemma is true for |B| < k (k ≥ 2), we want to prove it is true also for |B| = k. Take an arbitrary b ∈ B \ \{0\}. Then b|n. Since n ∉ A + B, (\frac{n}{b} − 1)b ∉ A. Let r be the least nonnegative integer such that rb ∉ A. Then 1 ≤ r < \frac{n}{b}. Therefore (r − 1)b ∈ A but b + (r − 1)b ∉ A. Set a = (r − 1)b. Set B_{0} = {b′ ∈ B|a + b′ ∉ A and a + b′ < n}. Then B_{0} ≠ ∅. Now set A_{1} = A∪(a+B_{0}) and set B_{1} = B\B_{0}. Clearly, (A_{1}+B_{1})∩[0, n] ⊂ (A+B)∩[0, n]. Note that |B_{1}| < k. By the inductive assumption we have |(A + B) ∩ [0, n]| ≥ |(A_{1} + B_{1}) ∩ [0, n]| ≥ |A_{1}| + |B_{1}| − 1 = |A| + |B| − 1. □

Proof of Theorem 3.1. Set A_{0} = {0, b_{1}, ⋯, b_{n−k}} and set A_{i} = {0, a_{i}} for i = 1, ⋯, k. Assume to the contrary that n ∉ ∑(S). By Lemma 3.2 we have, |(A_{0} + A_{1}) ∩ [1, n]| = |(A_{0} + A_{1}) ∩ [0, n]|−1 ≥ |A_{0}|+|A_{1}|−2. Similiarly, one can get |(A_{0} +A_{1} +A_{2})∩[1, n] ≥ |(A_{0} +A_{1})∩[0, n]|+ |A_{2}| − 1 ≥ |A_{0}| + |A_{1}| + |A_{2}| − 3, and finally, we must get |(A_{0} + A_{1} + A_{2} + ⋯ + A_{k}) ∩ [1, n]| ≥ |A_{0}| + |A_{1}| + ⋯ + |A_{k}| − k − 1 = |S| = n, a contradiction on n ∉ ∑(S). □

Kleitman and Lemke [5] suggested that Conjecture 3.3 Every sequence of n elements in C_{n} contains a nonempty subsequence T such that Index(T) = n.

They pointed out that this conjecture is open even for n prime.

Conjecture 3.4 Let S = (a_{1}, ⋯, a_{k}) be a sequence of elements in C_{n}. Suppose that S contains no subsequence T with Index(T) = n. Then, |{σ(T)|λ ≠ T ⊂ S and Index(T) < n}| ≥ k, where λ denotes the empty sequence.

This conjecture, if true, would clearly imply Conjecture 2.4.

4. Concluding Remarks

Let S = (a_{1}, ⋯, a_{k}) be a sequence of elements in C_{n}. For a positive integer l, we say S is a partition of l if ∑_{i=1}^{k} |a_{i}| = l. By the definition of Index(S) we have that every sequence S of elements in C_{n} is similiar to a partition of Index(S). By the definition of I(C_{n}) we have that every minimal zero sequence of elements in C_{n} is similiar to a partition of ln for some l ≤ I(C_{n})/n. Hence, if Index(S) > I(C_{n}), then S contains a proper zero subsequence. From Theorem 1.1 we see that every minimal zero sequence of at least n − [\frac{n+1}{3}] + 1 elements in C_{n} is similiar to a partition of n. For every positive integer k ≤ n − 1, we define

I_{k}(C_{n}) = max_{|T |=k}{Index(T)},

where T runs over all zero-free sequences of k elements in C_{n}.

Proposition 4.1 (1). If p is the smallest positive divisor of n then I_{1}(C_{n}) = n/p.

(2). If n ≥ 3 is a prime then I_{2}(C_{n}) = \frac{n+1}{2}.

Proof. (1). Clear.

(2). By Lemma 1.12, I_{2}(C_{n}) ≥ \frac{n+1}{2}. To prove the upper bound, let x, y be two nonzero elements (not necessarily distinct) with x + y ≠ 0. Set z = −x − y. Then (x, y, z) is a minimal zero sequence. Let t be the positive intger such that tz = \frac{p+1}{2} and 1 ≤ t ≤ p − 1. Then (p−t)z = \frac{p−1}{2}. Since |tx|+|ty|+|tz|+|(p−t)x|+|(p−t)y|+|(p−t)z| = 3p, |tx|+|ty|+|tz| = p or |(p−t)x|+|(p−t)y|+|(p−t)z| = p. Therefore, |ty|+|tz| = \frac{p−1}{2} or |(p−t)x|+|(p−t)y| = \frac{p+1}{2}. □

Conjecture 4.2 I(C_{n}) ≤ c ln n for some absolute constant c.

References

[1] J. D. Bovey, P. Erdős and I. Niven, Conditions for zero-sum modulo n, Canad. Math. Bull., 18(1975),27-29.

[2] S. Chapman, M. Freeze, and W. W. Smith, Minimal zero-sequence and the strong Davenport constant, Discrete Math., 203(1999), 271-277.

[3] W. D. Gao, An addition theorem for finite cyclic groups, Discrete Math., 163(1997), 257-265.

[4] W. D. Gao and A. Geroldinger, On the structure of zero-free sequences, Combinatoria, 18(1998), 519-527.

[5] D. J. Kleitman and P. Lemke, An addition theorem on the integers modulo n, J.Number Theory, 31(1989), 335-345.