INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A24

MINIMAL ZERO SEQUENCES OF FINITE CYCLIC GROUPS

Vadim Ponomarenko

Department of Mathematics, Trinity University, One Trinity Place, San Antonio, Texas 78212-7200

                            vadim@trinity.edu

Received: 7/7/04, Accepted: 12/14/04, Revised: 12/16/04, Published: 12/22/04

Abstract

If G is a finite Abelian group, let MZS(G, k) denote the set of minimal zero sequences of G of length k. In this paper we investigate the structure of the elements of this set, and the cardinality of the set itself. We do this for the class of groups G = ℤ_{n} for k both small (k ≤ 4) and large (k > \frac{2n}{3}).

Keywords: Zero-sum problems, minimal zero sequence

1. Introduction

Let G be a finite Abelian group and X = {x_{1}, x_{2}, …, x_{k}} a multiset chosen from G. This unordered collection of not necessarily distinct elements of G is traditionally called a sequence. We say the length of X is k. If x_{1} +x_{2} +⋯+x_{k} = 0 (in G), then X is called a zero-sequence. We denote the set of all zero sequences of G by ZS(G). If X is in ZS(G) but no proper subsequence of X is in ZS(G), then X is called a minimal zero sequence. We denote the set of all minimal zero sequences of G of length k by MZS(G, k), and the set of all minimal zero sequences of G of any length by MZS(G). The maximum k for which MZS(G, k) is nonempty is the well-known Davenport constant of G.

Notice that Aut(G) acts on ZS(G), on MZS(G), and on MZS(G, k), inducing equivalence relations on these sets. We denote by E(X) the set of sequences equivalent to sequence X, as induced in this manner.

We express G canonically as ℤ_{n_{1}} ⊕ ℤ_{n_{2}} ⊕ ⋯ ⊕ ℤ_{n_{r}}, with n_{1}|n_{2}| ⋯ |n_{r}. We say that zero sequence X is basic if E(X) contains a zero sequence whose sum in coordinate i is at most n_{i} (for 1 ≤ i ≤ r), when the sum is viewed as an integer. To avoid confusion, henceforth the symbol ‘+’ shall denote addition as integers, and the symbol ∑ X shall denote the sum of the elements of X as integers. If G is cyclic, that is its rank r = 1, then all basic zero sequences are minimal.

If every element of MZS(G, k) is basic, we say that (G, k) is a basic pair, otherwise it is a non-basic pair. Chapman, Freeze, and Smith [2] have shown that (ℤ_{n}, 5) is a non-basic pair for all n ≠ 2, 3, 4, 5, 7; further, for these five values of n, (ℤ_{n}, k) is a basic pair for all k. This left open the question of which (ℤ_{n}, k) are basic pairs.

We offer a partial answer to this question, for all n ≥ 5 and both very small and large k. We show in Theorems 1 and 5 that (ℤ_{n}, k) is a basic pair for k > \frac{2n}{3} and k ≤ 3; whereas (ℤ_{n}, 4) is a non-basic pair if gcd(n, 6) ≠ 1.

As an application, we count the number of minimal zero sequences of length greater than \frac{2n}{3}.

2. Short Minimal Zero Sequences

We first consider the question of whether (ℤ_{n}, k) is a basic pair for n ≤ 4. We have evidence to support the converse of the second part of the theorem; that is, we believe that if gcd(n, 6) = 1, then (ℤ_{n}, 4) is a basic pair. This has been verified computationally for n ≤ 1000.

Theorem 1. Let n ≥ 5. Then (ℤ_{n}, k) is a basic pair for k = 1, 2, 3. If gcd(n, 6) ≠ 1, then (ℤ_{n}, 4) is a non-basic pair.

Proof. The only element of MZS(ℤ_{n}, 1) is {0}, which is basic. Let X = {a, b} ∈ MZS(ℤ_{n}, 2). It has a < n and b < n, and hence a + b < 2n, so X is basic. Suppose that X = {a, b, c} ∈ MZS(ℤ_{n}, 3) were non-basic. Then a + b + c > n, but a + b + c < 3n, so a + b + c = 2n. Now, ϕ(y) = n − y is an automorphism on MZS(ℤ_{n}, 3), and ϕ(X) = {n−a, n−b, n−c} has ∑ ϕ(X) = (n−a)+(n−b)+(n−c) = 3n−(a+b+c) = 3n−2n = n. Hence X is, in fact, basic.

Suppose now that n is even, so n = 2m. We will now show that X = {1, m, m + 1, 2m − 2} is not basic, and hence that (ℤ_{2m}, 4) is a non-basic pair. First, X sums to a multiple of n, but no proper subset does, hence X is a minimal zero sequence. Now, let ϕ be any automorphism of ℤ_{2m}. We must have ϕ(y) = ky, for k some positive odd integer, different from m, less than n. We see that ϕ(X) = {k, km, km + k, k(2m − 2)}.

Reducing modulo n, we see that ϕ(X) = \begin{cases}\{k, m, m + k, 2m − 2k\} & if k < m, \\ \{k, m, k − m, 4m − 2k\} & if k > m. \end{cases}

In both cases we have ∑ ϕ(X) = 2n. Hence, X is not basic if n is even.

Now suppose that 3|n; that is, n = 3m. We will now show that X = {1, m + 1, 2m + 1, 3m − 3} is not basic, and hence that (ℤ_{n}, 4) is a non-basic pair. First, X sums to a multiple of n, but no proper subset does, hence X is a minimal zero sequence. Now, let ϕ be any automorphism of ℤ_{n}. We must have ϕ(y) = ky, for k some positive integer, less than n, relatively prime to n. We have ϕ(X) = {k, km + k, 2km + k, 3km − 3k}. We next note that {km + k, 2km + k} are congruent (modulo n) to {m + k, 2m + k} in some order, depending on whether k ≡ 1 or k ≡ 2 (modulo 3). We can now reduce modulo n,

and find ϕ(X) = \begin{cases}\{k, m + k, 2m + k, 3m − 3k\} & if k < m, \\ \{k, m + k, k − m, 6m − 3k\} & if m < k < 2m, \\ \{k, k − 2m, k − m, 9m − 3k\} & if 2m < k. \end{cases}

In all three cases we have ∑ ϕ(X) = 2n. Hence, X is not basic if 3|n.

3. Long Minimal Zero Sequences

We now consider minimal zero sequences in ℤ_{n}, long relative to the maximal possible length (namely n). We begin with some structure theorems, and ultimately show that (ℤ_{n}, k) is a basic pair for all k > \frac{3n−3}{4}.

We state a theorem that was first proved in [1], was rediscovered in [7], and restated in various forms in [6, 8].

Theorem 2. Let k > \frac{n+3}{2}, and let X ∈ MZS(ℤ_{n}, k). Then there is some element a ∈ ℤ_{n} that appears in X at least 2k − n times.

With a stronger restriction on k, we can get a bit more. This next result has a stronger hypothesis and conclusion than a similar one found in [5]. It has previously appeared in [4], with a substantially different proof.

Theorem 3. Let k > max(\frac{n+3}{2}, \frac{2n}{3}), and let X ∈ MZS(ℤ_{n}, k). Then there is some element a ∈ ℤ_{n} that appears in X at least 2k − n times, whose order is n (in ℤ_{n}).

Proof. Applying Theorem 2, we write X = {a^{m}, b_{1}, b_{2}, …, b_{j}} (where m is the multiplicity of a), with m ≥ 2k − n and m + j = k.

Now, suppose that the order of a were less than n. Then, we can write a = a′d and n = n′d, where gcd(a′, n′) = 1 and d ≥ 2. However, if d ≥ 3, we have n′ ≤ \frac{n}{3} < m. Hence X contains n′ copies of a, whose sum is n′a = n′da′ = na′. But this is a proper zero-sum, which is forbidden. Therefore, we must have d = 2, n even (since d|n), and m < \frac{n}{2} (since a^{m} is not a zero subsequence). The remainder of the proof develops a contradiction in these circumstances.

We now show that there is an automorphism ϕ of G with ϕ(a) = 2. Because gcd(a′, n′) = 1, there is some integer w with wa′ ≡ 1 modulo n′. If w is odd, then gcd(w, n) = 1 and ϕ(x) = wx is the desired automorphism. If w is even, then n′ must be odd. In this case, (w + n′)a′ ≡ 1 modulo n′. We have w + n′ odd, so gcd(w + n′, n) = 1 and therefore ϕ(x) = (w + n′)x is the desired automorphism. Henceforth we will assume without loss that a = 2.

We now consider the odd elements of X. We pair them arbitrarily and take the residue modulo n. The result is X′ = {2^{m}, c_{1}, c_{2}, …, c_{j′}}, where some c_{i′} are equal to an even b_{i}, while others are equal to the reduced sum of two odd elements of X. This is still a minimal zero sequence, and all of its terms are even. Further, we have j′ ≥ \frac{j}{2}. Note that m+j = k > \frac{2n}{3}, and hence j′ ≥ \frac{j}{2} > \frac{n}{3} − \frac{m}{2} > \frac{n}{3} − \frac{n}{4} + \frac{1}{2} = \frac{n}{12} + \frac{1}{2}. Therefore, in particular, j′ ≥ 2. Now we will show that any proper subsequence of {c_{1}, c_{2}, …, c_{j′}} has sum at most n−2m−2, by induction on the cardinality of the subsequence. For the base case, observe that each singleton c_{i} must have c_{i} ≤ n−2m−2, as otherwise X′ would not be a minimal zero sequence. Now, let S be a proper subsequence. Write S = S_{1} ∪S_{2}, the disjoint union of two nonempty subsequences. By the inductive hypothesis, ∑ S_{1} ≤ n − 2m − 2 and ∑ S_{2} ≤ n − 2m − 2. Adding, we get ∑ S = ∑ S_{1} + ∑ S_{2} ≤ 2n − 4m − 4 ≤ 2n − \frac{4n}{3} − 4 = \frac{2n}{3} − 4 < n. We have ∑ S even, but because S is a proper subsequence, we must not have ∑ S ∈ [n − 2m, n]. Therefore ∑ S ≤ n − 2m − 2. Finally, we note that (c_{1} + c_{2} + ⋯ + c_{j′−1}) + c_{j′} ≤ n − 2m − 2 + n − 2m − 2 ≤ \frac{2n}{3} − 4 < n. Therefore, because X′ is a minimal zero sequence, we must have 2m + c_{1} + c_{2} + ⋯ + c_{j′} = n. However, each c_{i} is even, so we therefore have the chain of inequalities n = \frac{n}{3} + \frac{2n}{3} < m + k = 2m + j ≤ 2m + 2j′ ≤ 2m + c_{1} + ⋯ + c_{j′} = n. This is a contradiction.

Corollary 1. Let n ≥ 10, k > \frac{2n}{3}, and let X ∈ MZS(ℤ_{n}, k). Then there is some element a ∈ ℤ_{n} that appears in X more than \frac{k}{2} times, whose order is n (in ℤ_{n}).

Proof. The condition n ≥ 10 ensures that \frac{2n}{3} ≥ \frac{n+3}{2}, so that the conditions of Theorem 3 are met. As before, we write X = \{a^{m}, b_{1}, b_{2}, …, b_{j}\}. Since k > \frac{2n}{3}, we must have m > 2(\frac{2n}{3}) − n = \frac{n}{3}. We also have m + j = k, and hence m ≥ 2k − n = (m + j) + k − n. Rearranging, we get j ≤ n − k < \frac{n}{3}. Combining these two facts, we get j < \frac{n}{3} < m, and hence m > \frac{k}{2}.

This allows us to conclude that all sufficiently long minimal zero sequences of ℤ_{n} are basic.

Theorem 4. Let n ≥ 10, k > \frac{3n−3}{4}. Then MZS(ℤ_{n}, k) is a basic pair.

Proof. Let Y ∈ MZS(ℤ_{n}, k). By Theorem 3 and Corollary 1, there is some element y ∈ Y, of order n, that appears at least 2k − n times. Let ϕ ∈ Aut(ℤ_{n}) be such that ϕ(y) = 1. Let X = ϕ(Y). We will show that ∑ X = n, which proves the theorem. Write X = {1^{m}, x_{1}, x_{2}, …, x_{j}}, where m ≥ 2k − n, m + j = k, and each x_{i} > 1. First, note that if j = 1 then ∑ X = m + x_{j} < m + n < 2n, so ∑ X = n. Otherwise, j > 1 and we see that each x_{i} ≤ n − m − 1, since otherwise X would properly contain a zero sequence. Now, x_{1} < n − m, but x_{1} + x_{2} + ⋯ + x_{j} ≥ n − m. Let w be such that x_{1} + x_{2} + ⋯ + x_{w−1} < n − m, but x_{1} + x_{2} + ⋯ + x_{w} ≥ n − m. If w = j, then because x_{w} < n, we have x_{1} + x_{2} + ⋯ + x_{w} = n − m and hence ∑ X = n. Otherwise, x_{1} + x_{2} + ⋯ + x_{w} ≥ n + 1 because X is a minimal zero sequence. Subtracting, we get x_{w} ≥ m + 2. However, n − m − 1 ≥ x_{w} ≥ m + 2. Rearranging, we get m ≤ \frac{n−3}{2}. But also m ≥ 2k − n > 2\frac{3n−3}{4} − n = \frac{n−3}{2}. This is impossible, and hence w = j and thus ∑ X = n.

It has come to our attention that a stronger result, with a different proof, has been published in [4]:

Theorem 5. Let n ≥ 10, k > \frac{2n}{3}. Then MZS(ℤ_{n}, k) is a basic pair.

4. Counting Minimal Zero Sequences

The cardinality of MZS(ℤ_{n}, k) has already been computed for small k, in [3], as follows.

Theorem 6. |MZS(ℤ_{n}, 2)| = ⌊\frac{n}{2}⌋. |MZS(ℤ_{n}, 3)| = \frac{1}{6}(n^{2} − α), where α is given by:

\begin{matrix}(n mod 6) ≡ & 0 & 1 & 2 & 3 & 4 & 5 \\ α = & 0 & 1 & 4 & -3 & 4 & 1 \end{matrix}

We can find |MZS(ℤ_{n}, k)| for large k with the results of Section . For this purpose, we need the following structure theorem.

Theorem 7. Let n ≥ 10, k > \frac{2n}{3}, and let X ∈ MZS(ℤ_{n}, k) be basic. Then there is exactly one Y ∈ E(X) with ∑ Y = n.

Proof. As X is basic, so at least one such Y exists. Suppose Y has i terms of 1, and the remaining k − i terms are not. Hence n = ∑ Y ≥ i + 2(k − i) = 2k − i. Hence i ≥ 2k − n > 2k − \frac{3}{2}k = \frac{k}{2}. Hence over half of the terms of Y are 1. Suppose that there are Y, Y′ ∈ E(X) with ∑ Y = ∑ Y′ = n. Let ϕ ∈ Aut(ℤ_{n}) with ϕ(Y) = Y′. By the previous, 1 appears in each more than \frac{k}{2} times. Both 1, ϕ(1) appear more than |Y′|/2 times in Y′, but there are not enough elements in Y′ for these to be different. Hence ϕ(1) = 1, and therefore ϕ is the identity and Y = Y′.

We are now ready to count all minimal zero sequences of sufficiently large length. Computational evidence suggests that the condition k > \frac{2n}{3} can be improved to k ≥ \frac{n+4}{2}.

Theorem 8. Let n ≥ 10, k > \frac{2n}{3}. Then |MZS(ℤ_{n}, k)| = ϕ(n)p_{k}(n), where ϕ is Euler’s totient function and p_{k}(n) denotes the number of partitions of n into k parts.

Proof. By Theorem 5, every minimal zero sequence is basic. Therefore, each equivalence class induced by Aut(ℤ_{n}) includes an element whose sum is n. By Theorem 7, each equivalence class contains exactly one element whose sum is n. It is clear that the set of minimal zero sequences whose sum is n is exactly the set of partitions of n into k parts. There are therefore p_{k}(n) equivalence classes. The cardinality of each equivalence class is |Aut(ℤ_{n})| = ϕ(n).

Acknowledgements

The author would like to gratefully acknowledge the work of an anonymous referee, whose suggestions improved several of these proofs.

References

[1] J. D. Bovey, Paul Erdős, and Ivan Niven, Conditions for a zero sum modulo n Canad. Math. Bull., 18(1): 27–29, 1975.

[2] Scott T. Chapman, Michael Freeze, and William W. Smith, Minimal zero-sequences and the strong Davenport constant Discrete Math., 203(1-3): 271–277, 1999.

[3] Bryson W. Finklea, Terri Moore, Vadim Ponomarenko, and Zachary J. Turner, On block monoid atomic structure In Preparation

[4] W. D. Gao, Zero sums in finite cyclic groups Integers 0, A12, 7 pp. (electronic), 2000.

[5] Weidong Gao and Alfred Geroldinger, On the structure of zerofree sequences Combinatorica, 18(4): 519–527, 1998.

[6] Weidong Gao and Alfred Geroldinger, On long minimal zero sequences in finite abelian groups Period. Math. Hungar., 38(3): 179–211, 1999.

[7] R. Thangadurai, Interplay between four conjectures on certain zero-sum problems Expo. Math., 20(3): 215–228, 2002.

[8] R. Thangadurai, Non-canonical extensions of Erdős-Ginzburg-Ziv theorem Integers 2 , A7, 14 pp. (electronic), 2002.