INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5(1) (2005), #A27

A CHARACTERIZATION OF MINIMAL ZERO-SEQUENCES OF INDEX ONE IN FINITE CYCLIC GROUPS

Scott T. Chapman^{1}

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

                           schapman@trinity.edu

William W. Smith

The University of North Carolina at Chapel Hill, Department of Mathematics, Phillips Hall, Chapel Hill,

NC 27599-3250, USA

                           wwsmith@email.unc.edu

Received: 4/27/05, Revised: 10/26/05, Accepted: 11/16/05, Published: 11/29/05

Abstract

Let G ≅ ℤ_{n} where n is a positive integer. A finite sequence S = {g_{1}, …, g_{k}} of not necessarily distinct elements from G for which ∑_{i=1}^{k} g_{i} = 0 is called a zero-sequence. If a zero-sequence S contains no proper subzero-sequence, then it is called a minimal zero-sequence. The notion of the index of a minimal zero-sequence (see Definition 1) in ℤ_{n} has been recently addressed in the mathematical literature. In this note, we offer a characterization of minimal zerosequences in ℤ_{n} with index 1.

Let G be an additive abelian group and S = {g_{1}, …, g_{k}} a finite sequence of not necessarily distinct elements from G. Denote by | S |= k the number of elements in S (or the length of S) and let supp(S) = {g | g ∈ G with g = g_{i} for some i} be the support of S. Various properties of the sequence S have been considered over the last several years in the mathematical literature. Some of these properties are among the following.

1. S is zero-free if ∑_{i∈ℐ}g_{i} ≠ 0 for any nonempty subset ℐ ⊆ {1, 2, …, k}.

2. S is a zero-sequence if ∑_{i=1}^{k} g_{i} = 0.

3. A zero-sequence S is a minimal zero-sequence (or MZS) if for every nonempty ℐ ⊊ {1, 2, …, k}, the sequence {g_{i}}_{i∈ℐ} is zero-free.

1Part of this work was completed while the first author was on an Academic Leave granted by the Trinity University Faculty Development Committee.

4. A zero-sequence S which is not an MZS is an almost minimal zero-sequence (or AMZS) if for every nonempty ℐ ⊊ {1, 2, …, k} where the sequence {g_{i}}_{i∈ℐ} is a zero-sequence, then {g_{i}}_{i∈ℐ} is a minimal zero-sequence.

In this article, we will consider a property of minimal zero-sequences in finite cyclic groups which was introduced in the literature in [2] and consequently considered in greater detail in [4] and [7]. Some notation will be necessary before giving a formal statement describing this property. Since the ordering of the elements in a sequence S does not matter, we will view sequences as elements of F(G), the free abelian monoid on G. Hence, we write

S = ∏_{g∈G} g^{n_{g}}

where only finitely many of the n_{g} are not zero.

Our goal is to offer a characterization of index 1 minimal zero-sequences in ℤ_{n}. This will be done in terms of almost minimal zero-sequences (see [3, Chapter 5] for more information on AMZSs). We will find the language of block monoids useful for expressing and applying some of our arguments. For a finite abelian group G, let B(G) represent the set of elements in F(G) which are zero-sequences. Further, let U(G) be the subset of B(G) consisting of the minimal zero-sequences of G. If S_{1} = ∏_{g∈G} g^{m_{g}} and S_{2} = ∏_{g∈G} g^{s_{g}} are in B(G), then B(G) can be considered as a commutative cancellative monoid under the operation

S_{1} ∗ S_{2} = ∏_{g∈G} g^{m_{g}+s_{g}}

and is commonly called a block monoid (more information on block monoids can be found in [6]). The irreducible elements of B(G) are merely the elements of U(G) and the empty block (i.e., S = ∅) acts as the identity of B(G). An interpretation of an almost minimal zero-sequence in terms of block monoids can be stated as follows: B ∈ B(G) is an almost minimal zero-sequence if and only if B = B_{1} ⋯ B_{t} with each B_{i} in U(G) implies that t = 2.

Definition 1. Let G be an abelian group.

(1) Let g ∈ G be a non-zero element with ord(g) = n > 1. For a sequence S = (n_{1}g) ⋯ (n_{l}g), where l ∈ ℕ_{0} and n_{1}, …, n_{l} ∈ [1, n], we define

∥S∥_{g} = \frac{n_{1} + … + n_{l}}{n}

to be the g-norm of S. If S = ∅, then set ∥S∥_{g} = 0.

(2) Let S be a zero-sum sequence for which ⟨supp(S)⟩ ⊂ G is a nontrivial finite cyclic group. Then we call

index(S) = min{ ∥S∥_{g} | g ∈ G with ⟨supp(S)⟩ = ⟨g⟩} ∈ ℕ_{0}

the index of S.

Notice that the index of a sequence S depends only on S and not the choice of the cyclic group G which contains supp(S). Theorem 2 of [2] indicates that as n increases, there exist minimal zero-sequences of ℤ_{n} of arbitrarily high index. The papers [7] and [4] have both shown that for a fixed value of n, “long” minimal zero-sequences must have index 1. In particular, [4, Section 2] shows for n ≥ 10 that a minimal zero-sequence S in ℤ_{n} with | S | > \frac{2n}{3} must have index 1.

When restricting our attention to cyclic groups, the g-norm of an zero-sequence can be used to draw some helpful conclusions. We determine some basic properties of the g-norm in the next proposition.

Proposition 2. Let G be an abelian group, g ∈ G a nonzero element and S, T ∈ B(⟨g⟩).

(1) ∥ · ∥_{g} : B(⟨g⟩) → ℕ_{0} is a monoid homomorphism (i.e., ∥S ∗ T ∥_{g} = ∥S∥_{g} + ∥T ∥_{g}).

(2) ∥S∥_{g} = 0 if and only if S = ∅.

(3) ∥0∥_{g} = 1.

(4) If ∥S∥_{g} = 1, then S is a MZS.

(5) If ∥S∥_{g} = 2, then S is an AMZS.

Proof. The proofs of (1)-(3) are clear. For (4), if S = S_{1} ∗ S_{2} with S_{1} and S_{2} in B(⟨g⟩), then 1 = ∥S∥_{g} = ∥S_{1}∥_{g} +∥S_{2}∥_{g} ≥ 2, a contradiction. For (5), if S is neither an MZS or an AMZS, then S = S_{1} ∗ S_{2} ∗ S_{3} for S_{1}, S_{2} and S_{3} in B(⟨g⟩). The argument now follows as in (4).

We note that index one MZSs satisfy several interesting properties. Two of these properties follow. Recall that if S = ∏_{g∈G} g^{n_{g}} is an MZS in ℤ_{n}, then the cross number of S is defined as 𝕜(S) = ∑_{g∈G} \frac{n_{g}}{ord(g)} where ord(g) represents the order of g in G (more information on the cross number can be found in [1]). For S ∈ B(G) consider these properties.

(P1) S ∗ S is an AMZS in ℤ_{n}.

(P2) 𝕜(S) ≤ 1.

It follows directly from Proposition 2 that S = ∏_{g∈G} g^{n_{g}} an MZS in ℤ_{n} with ∥S∥_{g} = 1 satisfies (P1). That ∥S∥_{g} = 1 implies 𝕜(S) ≤ 1 can be seen as follows. Suppose S = (n_{1}g) ⋯ (n_{l}g) is written as in Definition 1 with n = ord(g). Then

𝕜(S) = ∑_{i=1}^{l} \frac{1}{ord(n_{i}g)} = ∑_{i=1}^{l} \frac{1}{\frac{n}{gcd (n_{i},n)}} ≤ ∑_{i=1}^{k} \frac{n_{i}}{n} = ∥S∥_{g} = 1.

Hence we have the following.

Proposition 3. If S is a MZS of ℤ_{n} with index(S) = 1, then S satisfies properties (P1) and (P2).

Example 4. Properties (P1) and (P2) do not characterize MZSs of index 1. Notice that all of the index 2 MZSs in [2] do not satisfy (P1) (see in particular the proof of [2, Theorem 2]). A slight modification of the construction used in [2] yields the following example. Let G = ℤ_{23} and set S = 2 · 7 · 9 · 11 · 17. It is a routine calculation to check the 22 possible values of ∥S∥_{g} and determine that index(S) = 2. Since 𝕜(S) ≤ 1, S satisfies (P2). For considering property (P1), note that ∥S∥_{1} = 2 and so ∥S ∗ S∥_{1} = 4. To establish that S ∗ S is an AMZS, one needs only observe that if it were not, then S ∗ S = A ∗ B ∗ C for some zero sequences A, B, and C. It follows that this has to be done (with the proper choice of g) so that ∥A∥_{g} = ∥B∥_{g} = 1 and ∥C∥_{g} = 2. The key then to observing such a decomposition is impossible is to note that 7^{2} · 9 is the only subsequence of S ∗ S that sums to 23.

While (P1) and (P2) do not offer the characterization of index 1 MZSs we desire, a relatively simple condition involving the AMZS’s which contain an MZS S does provide a characterization.

Theorem 5. Let G be an abelian group and S a minimal zero-sequence over G such that supp(S) generates a cyclic group H of order n ≥ 2. Then the following statements are equivalent:

(a) There exists some AMZS A ∈ F(H) of length |A| = |S|+n where S divides A in B(G).

(b) There exists some g ∈ H such that g^{n}S is an AMZS.

(c) index(S) = 1.

Proof. (a) ⇒ (b) Let A = ST be an AMZS of length |S| + n for some T ∈ F(H). Then T is a minimal zero-sum sequence of length n. Thus, for example by [5, Lemma 13], there exists some g ∈ H such that T = g^{n}.

(b) ⇒ (c) Let g ∈ H and A = g^{n}S an AMZS. Then there are m_{1}, …, m_{l} ∈ [1, n − 1] with m_{1} ≤ … ≤ m_{l} such that S = ∏_{i=1}^{l}(m_{i}g). We assert that ∥S∥_{g} = 1. Assume to the contrary that

∥S∥_{g} = \frac{m_{1} + … + m_{l}}{n} = k with k ≥ 2.

Since S is a minimal zero-sum sequence, there exist u, v ∈ [1, l − 1] such that

(k − 2)n < m_{1} + … + m_{u} < (k − 1)n < m_{1} + … + m_{u} + m_{u+1}

and

m_{u+1} + … + m_{v} < n < m_{u+1} + … + m_{v} + m_{v+1}.

We set

r = (k − 1)n − (m_{1} + … + m_{u}),

s = n − (m_{u+1} + … + m_{v})

and we define

N_{1} = g^{r} ∏_{i=1}^{u}(m_{i}g), N_{2} = g^{s} ∏_{i=u+1}^{v}(m_{i}g) and N_{3} = g^{n−(r+s)} ∏_{i=v+1}^{l}(m_{i}g).

By construction, N_{1}, N_{2} and N_{3} are zero-sum sequences with A = N_{1}N_{2}N_{3}, a contradiction to the fact that A is an AMZS.

(c) ⇒ (a) Let g ∈ H such that ∥S∥_{g} = 1. We set A = g^{n}S, and since ∥A∥_{g} = 2, it follows that A is an AMZS.

Acknowledgement

The authors would like to thank the referee for many helpful suggestions.

References

[1] S. T. Chapman, On the Davenport constant, the cross number, and their application in factorization theory, Zero-dimensional commutative rings (Knoxville, TN, 1994), Marcel Dekker, New York, 1997, 167–190.

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

[3] M. Freeze, Lengths of Factorizations in Dedekind domains, Ph. D. Dissertation, The University of North Carolina at Chapel Hill, 1999.

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

[5] A. Geroldinger, Systeme von Längenmengen, Abh. Math. Sem. Univ. Hamburg 60(1990), 115–130.

[6] A. Geroldinger and F. Halter-Koch, Nonunique factorizations in block semigroups and their arithmetical applications, Math. Slovaca 42(1992), 641–661.

[7] V. Ponomarenko, Minimal zero sequences of finite Abelian groups, Integers, (electronic) 4(2004) A24, 6 pp.