ON ZERO-SUM SUBSEQUENCES IN FINITE ABELIAN GROUPS

Wolfgang A. Schmid

Institut für Mathematik, Karl-FranzensUniversität, Heinrichstrasse 36, 8010 Graz, Austria

Received: 11/14/00, Revised: 12/11/00, Accepted: 12/29/00, Published: 1/11/01

Abstract

Let G be a finite abelian group and k ∈ ℕ with k ∤ exp(G). Then E_{k}(G) denotes the smallest integer l ∈ ℕ such that every sequence S ∈ F(G) with |S| ≥ l has a zero-sum subsequence T with k ∤ |T |. In this paper we prove that if G = C_{n_{1}} ⊕ ⋯ ⊕ C_{n_{r}} is a p-group, k ∈ ℕ with k ∤ exp(G) and gcd(p, k) = 1, then

E_{k}(G) = ⌊\frac{k}{k − 1} ∑_{i=1}^{r}(n_{i} − 1)⌋ + 1.

1. Introduction and Main Result

Let G be an additively written, finite abelian group and let exp(G) denote its exponent. We will consider sequences in G and recall some terminology. Let F(G) be the multiplicatively written, free abelian monoid with basis G and let S = ∏_{i=1}^{l} g_{i} ∈ F(G) be a sequence in G. We denote by |S| = l ∈ ℕ_{0} the length of S and by σ(S) = ∑_{i=1}^{l} g_{i} ∈ G the sum of S. We call the sequence S a zero-sum sequence, if σ(S) = 0. If ∅ ≠ I ⊂ {1, …, l}, then we call T = ∏_{i∈I} g_{i} ∈ F(G) a subsequence of S. If σ(T) = 0, we call T a zero-sum subsequence of S.

In 1961 P. Erdős, A. Ginzburg and A. Ziv (cf. [4]) proved that in case G is a cyclic group, 2|G| − 1 is the smallest integer l such that every sequence S ∈ F(G) with |S| ≥ l has a zero-sum subsequence with |T | = |G|.

This was a starting point to study subsequences of given sequences, that have sum zero and satisfy some given additional property. Each of the following problems had its own motivation and its own history.

Problem: Determine the smallest integer l ∈ ℕ such that every sequence S ∈ F(G) with |S| ≥ l has a zero-sum subsequence T such that

1. |T | = |G| (cf. [2, 5, 13]).

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 1 (2001), #A01 2

2. |T | = exp(G) (cf. [1, 14, 15]).

3. 1 ≤ |T | ≤ exp(G) (cf. [9]).

4. T is a product of k zero-sum subsequences (for given k ∈ ℕ) (cf. [12]).

Recently W. D. Gao studied Problem 2 in a series of papers (cf. [6, 7, 8]). To do so he introduced the following invariant.

Definition 1.1. Let G be a finite abelian group and k ∈ ℕ with k ∤ exp(G). Then E_{k}(G) denotes the smallest integer l ∈ ℕ such that every sequence S ∈ F(G) with |S| ≥ l has a zero-sum subsequence T with k ∤ |T |.

W. D. Gao showed how the invariant is related with Problem 2 and he determined E_{2}(G) in case G is a p-group with odd p or G is a cyclic group of odd order (cf. [8]). In this paper we determine E_{k}(G) in case G is a p-group, k ∈ ℕ with k ∤ exp(G) and gcd(p, k) = 1.

For some real number x ∈ ℝ let ⌊x⌋ = max{m ∈ ℤ | m ≤ x} and for some n ∈ ℕ let C_{n} denote the cyclic group with n elements.

The aim of the paper is to prove the following result:

Theorem 1.2. Let G = C_{n_{1}} ⊕ ⋯ ⊕ C_{n_{r}} be a p-group, k ∈ ℕ with k ∤ exp(G) and gcd(p, k) = 1. Then

E_{k}(G) = ⌊\frac{k}{k − 1} ∑_{i=1}^{r}(n_{i} − 1)⌋ + 1.

2. Proof of the Main Result

Throughout, let G denote a finite abelian group and let k ∈ ℕ with k ∤ exp(G). If |G| > 1, then there are uniquely determined n_{1}, …, n_{r} ∈ ℕ with 1 < n_{1}| … |n_{r} and

G ≅ C_{n_{1}} ⊕ ⋯ ⊕ C_{n_{r}}.

If |G| = 1, we set r = n_{r} = 1.

Let D(G) denote Davenport’s constant, which is defined as the smallest integer l ∈ ℕ such that every sequence S ∈ F(G) with |S| ≥ l contains a zero-sum subsequence. Furthermore, let s(G) denote the invariant arising from Problem 2, i.e. the smallest integer l ∈ ℕ such that every sequence S ∈ F(G) with |S| ≥ l has a zero-sum subsequence T such that |T | = exp(G). We start with a simple lemma showing relations between D(G), s(G) and E_{k}(G)

Lemma 2.1. 1. D(G) ≤ E_{k}(G) ≤ s(G).

2. If D(G) < k, then D(G) = E_{k}(G).

Proof. The inequality D(G) ≤ E_{k}(G) holds by definition. The inequaltiy E_{k}(G) ≤ s(G) holds, since k ∤ exp(G) and therefore a zero-sum subsequence of length exp(G) is as well a zero-sum subsequence of length not divisible by k. To prove D(G) = E_{k}(G), in case D(G) < k, it suffices to prove E_{k}(G) ≤ D(G). Let T ∈ F(G) with |T | = D(G). By definition T has a zero-sum subsequence Z. Since |Z| ≤ |T | < k, we have k ∤ |T |. Therefore every S ∈ F(G) with |S| ≥ D(G), has a zero-sum subsequence of length not divisible by k. This implies E_{k}(G) ≤ D(G).

In various problems involving zero-sum sequences it has turned out to be useful to reformulate the original problem into an equivalent one involving zerofree sequences (as usual, we call a sequence zerofree, if it has no zero-sum subsequence). This procedure proved successful in all investigations on the generalized Davenport’s constant (cf. Problem 4 of the Introduction) and in all investigations on the cross number of sequences (cf. [10, 11]). Although the above reformulation of the given problem is quite simple in many cases, we regard this as a key idea which we are going to apply for investigating E_{k}(G).

We need some further notations. Let d(G) denote the largest integer l ∈ ℕ such that there exists a sequence S ∈ F(G) which is zerofree and has length l. It is well known that

D(G) = d(G) + 1 and  ∑_{i=1}^{r}(n_{i} − 1) ≤ d(G).

Definition 2.2. Let e_{k}(G) denote the largest integer l ∈ ℕ such that there exists a sequence S ∈ F(G) with |S| = l and k | |T | for all zero-sum subsequences T of S.

The following will show that there are relations among E_{k}(G) and e_{k}(G), which are similar to those among D(G) and d(G).

Lemma 2.3.

E_{k}(G) = e_{k}(G) + 1.

Proof. By definition, e_{k}(G) < E_{k}(G). Indeed, there exists a sequence S ∈ F(G) of length e_{k}(G) such that k divides the lengths of all zero-sum subsequences of S. On the other hand, the maximality of e_{k}(G) implies that every sequence with length greater e_{k}(G) has a zero-sum subsequence with length not divisible by k. Therefore E_{k}(G) ≤ e_{k}(G) + 1, and the equality follows.

Lemma 2.4.

⌊\frac{k}{k − 1} ∑_{i=1}^{r}(n_{i} − 1)⌋ ≤ e_{k}(G).

Proof. The proof is done by construction of a sequence of length ⌊\frac{k}{k−1} ∑_{i=1}^{r}(n_{i} − 1)⌋ such that k divides the length of every zero-sum subsequence. Let e_{1}, …, e_{r} ∈ G such that

G = ⟨e_{1}⟩ ⊕ ⋯ ⊕ ⟨e_{r}⟩

and ord(e_{i}) = n_{i} for all i ∈ {1, …, r}.

If S′ = ∏_{i=1}^{r}(−e_{i})^{(n_{i}−1)}, then S′ is zerofree and it remains to construct a sequence S′′ of length ⌊^{\frac{∑_{i=1}^{r}(n_{i}−1)}{k−1}}⌋ such that k | |Z| for every zero-sum subsequence Z of S′S′′. We consider the sequence T = ∏_{i=1}^{r} e_{i}^{(n_{i}−1)}, which is zerofree and we write it as a product of sequences B_{1}, …, B_{l} of length k − 1 and a rest R of length less than k − 1:

T = (∏_{i=1}^{l} B_{i})R

with |B_{i}| = k − 1 for all i ∈ {1, …, l} and 0 ≤ |R| < k − 1. We define

S′′ = ∏_{i=1}^{l} σ(B_{i}).

It follows that S′′ is zerofree and has length |S′′| = l = ⌊\frac{|T |}{k−1}⌋ = ⌊^{\frac{∑_{i=1}^{r}(n_{i}−1)}{k−1}}⌋. Therefore |S′S′′| = ⌊\frac{k}{k−1} ∑_{i=1}^{r}(n_{i} − 1)⌋, and it remains to show that k divides the length of every zero-sum subsequence. Let Z denote an arbitrary zero-sum subsequence of S′S′′. Since S′ and S′′ are both zerofree, Z can be written as Z′Z′′ with subsequences Z′ of S′ and Z′′ of S′′. Every element z′′ of Z′′ can be written in the form z′′ = ∑_{j=1}^{k−1} e_{i_{j}} with suitable i_{j} ∈ {1, …, r}. Since Z is a zero-sum sequence, we get ∏_{j=1}^{k−1}(−e_{i_{j}})|Z′. The zero-sum sequence z′′(∏_{j=1}^{k−1}(−e_{i_{j}})) is of length k and Z can be written as a product of sequences of this form. Therefore k divides |Z|.

Lemma 2.5. If G = G_{1} ⊕ G_{2}, then

e_{k}(G_{1}) + e_{k}(G_{2}) ≤ e_{k}(G).

Proof. Since exp(G) = lcm(exp(G_{1}), exp(G_{2})) and k ∤ exp(G), it follows that k ∤ exp(G_{1}) and k ∤ exp(G_{2}). Therefore e_{k}(G_{1}) and e_{k}(G_{2}) are well-defined. For i ∈ {1, 2} let S_{i} ∈ F(G_{i}) be a sequence with |S_{i}| = e_{k}(G_{i}) such that for every zero-sum subsequence T_{i} of S_{i}, k divides |T_{i}|. We define S = S_{1}S_{2} ∈ F(G). For every zero-sum subsequence T of S, there exist T_{i} ∈ F(G_{i}) for i ∈ {1, 2} such that T = T_{1}T_{2}. Since T has sum zero, the sequences T_{1} and T_{2} have sum zero too. Due to the definition of S_{1} and S_{2}, we have k | |T_{1}| and k | |T_{2}|. Therefore k | |T_{1}| + |T_{2}| = |T | and S is a sequence in G of length e_{k}(G_{1}) + e_{k}(G_{2}), for which every zero-sum subsequence has a length divisible by k. By definition of e_{k}(G), we have

e_{k}(G_{1}) + e_{k}(G_{2}) = |S_{1}| + |S_{2}| = |S| ≤ e_{k}(G).

For the proof of Theorem 1.2 we need two results on p-groups. The first result has been proved independently by D. Kruyswijk and J. E. Olson (cf. [3, 16])

Theorem 2.6. If G is a p-group, then d(G) = ∑_{i=1}^{r}(n_{i} − 1).

Theorem 2.6 implies that for two p-groups G and H

d(G) + d(H) = d(G ⊕ H).

The second result is due to W. D. Gao. For convenience we repeat its short proof.

Lemma 2.7. [8] Let G be a p-group. Then there exists a p-group H such that D(G⊕H) is a power of p.

Proof. Let G = ⨁_{i=1}^{r} C_{p^{m_{i}}} with m_{i} ∈ ℕ and M = ∏_{i=1}^{r} m_{i}. Then G is a direct summand of

Ḡ = C_{p^{M}}^{p^{M} −r+1} ⊕ ⨁_{i=1}^{r} Cp^{m_{i}}^{\frac{p^{M} −1}{p^{m_{i}} −1}}

and by Theorem 2.6

\begin{matrix}D(Ḡ) = & 1 + d(Ḡ) = 1 + (p^{M} + 1 − r)(p^{M} − 1) + ∑_{i=1}^{r} \frac{p^{M} − 1}{p^{m_{i}} − 1}(p^{m_{i}} − 1) = \\ 1 + (p^{M} + 1)(p^{M} − 1) = p^{2M}. \end{matrix}

Now we are ready to prove Theorem 1.2.

Proof of Theorem 1.2. By Lemma 2.3 and Lemma 2.4 it suffices to prove

e_{k}(G) ≤ ⌊\frac{k}{k − 1} ∑_{i=1}^{r}(n_{i} − 1)⌋ .

The proof is done in three steps. In the first and the second step the proof is given for special groups. In the third step the general case is proved, by using the result for the groups of special type.

1. Suppose that there exists some n ∈ ℕ such that d(G) = (k − 1)(p^{n} − 1). Let S ∈ F(G) with |S| = ⌊\frac{k}{k−1} ∑_{i=1}^{r}(n_{i} − 1)⌋ + 1. We shall prove that S possesses a zero-sum subsequence T such that k ∤ |T |. This implies that

e_{k}(G) = E_{k}(G) − 1 ≤ |S| − 1 ≤ ⌊\frac{k}{k − 1} ∑_{i=1}^{r}(n_{i} − 1)⌋ .

We consider the map

ζ : \begin{cases}G → G ⊕ C_{p^{n}} \\ g ↦ g + e \end{cases}

where G ⊕ C_{p^{n}} = G ⊕ ⟨e⟩. For W = ∏_{i=1}^{l} g_{i} ∈ F(G) we set ζ(W) = ∏_{i=1}^{l} ζ(g_{i}) ∈ F(G ⊕ C_{p^{n}}). By Theorem 2.6 we get

|S| = \frac{k}{k − 1}d(G) + 1 = d(G) + 1 + (p^{n} − 1) = k(p^{n} − 1) + 1 < kp^{n}

and

d(G ⊕ C_{p^{n}}) = d(G) + (p^{n} − 1) = k(p^{n} − 1) < |S| = |ζ(S)|.

Therefore, again by Theorem 2.6, there exists a subsequence T of S such that σ(ζ(T)) = 0. By construction σ(T) = 0, p^{n} | |T | and, since |T | ≤ |S| < kp^{n}, we have k ∤ |T |.

2. Suppose that (k − 1) divides d(G).

By Lemma 2.7 there exists a p-group H and an integer n ∈ ℕ such that d(G⊕H) = p^{n} −1. If H′ = G^{k−2} ⊕H^{k−1}, then d(G⊕H′) = d((G⊕H)^{k−1}) = (k −1)d(G⊕H) = (k − 1)(p^{n} − 1). Since d(H′) = d((G ⊕ H)^{k−1}) − d(G), we also get (k − 1)|d(H′). From the previous step we obtain

\frac{k}{k − 1}d((G ⊕ H)^{k−1}) = \frac{k}{k − 1}d(G ⊕ H′) = \frac{k}{k − 1}d(G) + \frac{k}{k − 1}d(H′) ≤

e_{k}(G) + e_{k}(H′) ≤ e_{k}(G ⊕ H′) = e_{k}((G ⊕ H)^{k−1}) = \frac{k}{k − 1}d((G ⊕ H)^{k−1}),

where the first inequality holds by Lemma 2.4, Theorem 2.6 and the fact that (k − 1)|d(G) and (k − 1)|d(H′). In this chain of inequalities equality holds and therefore

e_{k}(G) = \frac{k}{k − 1}d(G) = ⌊\frac{k}{k − 1} ∑_{i=1}^{r}(n_{i} − 1)⌋ .

3. Assume to the contrary that ⌊\frac{k}{k−1} ∑_{i=1}^{r}(n_{i} − 1)⌋ + 1 ≤ e_{k}(G). Since k − 1 divides (k − 1)d(G) = d(G^{k−1}), we obtain by the previous step and

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 1 (2001), #A01 7

Lemma 2.5:

k d(G) =

(k − 1)(\frac{k}{k − 1}d(G) − 1) + (k − 1) < (k − 1) ⌊\frac{k}{k − 1}d(G)⌋ + (k − 1) =

(k − 1)(⌊\frac{k}{k − 1}d(G)⌋ + 1) = (k − 1)(⌊\frac{k}{k − 1} ∑_{i=1}^{r}(n_{i} − 1)⌋ + 1) ≤

(k − 1)e_{k}(G) ≤ e_{k}(G^{k−1}) = k d(G),

a contradiction. Therefore we have e_{k}(G) ≤ ⌊\frac{k}{k−1} ∑_{i=1}^{r}(n_{i} − 1)⌋.

References

[1] N. Alon and M. Dubiner, Zero-sum sets of prescribed size, in: Combinatorics, Paul Erdős is Eighty, Vol. 1, J. Bolyai Math. Soc., 1993, 33-50.

[2] Y. Caro, Remarks on a Zero-Sum Theorem, J. Combin. Th. Ser. A, 76 (1996), 315-322.

[3] P. van Emde Boas, A combinatorial problem on finite abelian groups II, Report ZW-1969-007, Math. Centre, Amsterdam.

[4] P. Erdős, A. Ginzburg and A. Ziv, A theorem in additive number theory, Bull. Research Council Israel 10F (1961), 41-43.

[5] W. D. Gao, A Combinatorial Problem on Finite Abelian Groups, J. Number Th. 58 (1996), 100-103.

[6] W. D. Gao, On zero-sum subsequences of restricted size, J. Number Th. 61 (1996), 97-102.

[7] W. D. Gao, On zero-sum subsequences of restricted size II.

[8] W. D. Gao, On zero-sum subsequences of restricted size III, Ars Combinatoria.

[9] W. D. Gao and A. Geroldinger, On Long Minimal Zero Sequences in Finite Abelian Groups, Periodica Mathematica Hungarica 38 (3) (1999), 179-211.

[10] A. Geroldinger, The Cross Number of Finite Abelian Groups, J. Number Th. 48 (1994), 219-223.

[11] A. Geroldinger and R. Schneider, The cross number of finite abelian groups III, Discrete Mathematics 150 (1996), 123-130.

[12] F. Halter-Koch, A Generalisation of Davenport’s Constant and its Arithmetical Applications, Colloquium Mathematicum 63 (1992), 203-210.

[13] Y. O. Hamidoune, O. Ordaz and A. Ortunio, On a Combinatorial Theorem of Erdős, Ginzburg and Ziv, Combinatorics, Probability and Computing 7 (1998), 403-412.

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

[15] A. Kemnitz, On a lattice point problem, Ars Combinatoria 16-B (1983), 151-160.

[16] J. E. Olson, A combinatorial problem on finite abelian groups, I, J. Number Th. 1 (1969), 8-10.