INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A21

ON SHORT ZERO-SUM SUBSEQUENCES II

W. D. Gao

Center for Combinatorics, Nankai University, Tianjin 300071, China

                           gao@cfc.nankai.edu.cn

Q. H. Hou

Center for Combinatorics, Nankai University, Tianjin 300071, China

                             hou@nankai.edu.cn

W. A. Schmid

Institut für Mathematik und Wissenschaftliches Rechnen, Karl-Franzens-Universität Graz, Heinrichstraße 36, 8010 Graz, Austria

                        wolfgang.schmid@uni-graz.at

R. Thangadurai

School of Mathematics, Harish-Chandra Research Institute, Chhatnag Road, Jhunsi, Allahabad - 211019,

India

                            thanga@mri.ernet.in

Received: 7/7/06, Accepted: 4/11/07, Published: 4/18/07

Abstract

Let G be a finite abelian group of exponent n. In this paper we investigate the structure of the maximal (in length) sequences over G that contain no zero-sum subsequence of length [at most] n. Among others, we obtain a result on the multiplicities of elements in these sequences, which support well-known conjectures on the structure of these sequences. Moreover, we investigate the related invariants s(G) and η(G), which are defined as the smallest integer l such that every sequence over G of length at least l has a zero-sum subsequence of length n (at most n, respectively). In particular, we obtain the precise value of s(G) for certain groups of rank 3.

1. Introduction and Main Results

Let G be a finite abelian group. By s(G) (or η(G) respectively) we denote the smallest integer l ∈ ℕ such that every sequence S over G of length |S| ≥ l has a zero-sum subsequence T of length |T | = exp(G) (or 1 ≤ |T | ≤ exp(G) respectively). For details on terminology and notation we refer to Section 2. The investigation of these invariants has a long tradition, and in recent years the investigation of these invariants and of the according inverse problems, i.e., the investigation of the structure of extremal sequences with, and in particular without, the respective properties, received an increasing amount of attention. Among others, this is due to applications in the theory of non-unique factorizations. We refer to the monograph [21], in particular to Chapter 5, for a detailed account of results on these invariants and their applications in the theory of non-unique factorizations, and to the recent survey article [16] for an exposition of the state of the knowledge and numerous references.

Still, many questions are wide open. The precise value of s(G) for cyclic groups is known by the classical Erdős–Ginzburg–Ziv theorem [9], but s(G) for groups of rank 2 has only recently been determined by C. Reiher [26], and the precise value of s(G) is unknown for most groups of rank greater than 2, as is the value of η(G). In Theorem 2.2 we recall these and some further results on s(G) and η(G) that we apply in our investigations.

A main motivation for the investigations of this paper is the following conjecture.

Conjecture 1.1. ([14, Conjecture 2.3]) Let G be a finite abelian. Then

s(G) = η(G) + exp(G) − 1.

It is well-known and not difficult to see that s(G) ≥ η(G) + exp(G) − 1 (cf., e.g., [21, Lemma 5.7.2]). Moreover, several (in general unproven) assertions, which we recall below, on the structure of maximal sequences without zero-sum subsequences of length exp(G) would imply this conjecture.

Open Problems 1.2. Let G be a finite abelian group with exp(G) = n. Are the following claims true?

(C1) Every sequence S ∈ F(G) of length s(G) − 1 that has no zero-sum subsequence of length n contains some element g ∈ G with multiplicity v_{g}(S) ≥ ⌊(n − 1)/2⌋.

(C2) Every sequence S ∈ F(G) of length s(G) − 1 that has no zero-sum subsequence of length n contains some element g ∈ G with multiplicity v_{g}(S) = n − 1.

(C3) Suppose G ≅ C_{n}^{r}. Every sequence S ∈ F(G) of length η(G) − 1 that has no non-empty zero-sum subsequence of length at most n is of the form S = T^{n−1} for some T ∈ F(G), i.e., each element contained in S is contained in it with multiplicity n − 1. (A group for which this is true is said to have Property C.)

(C4) Suppose G ≅ C_{n}^{r}. Every sequence S ∈ F(G) of length s(G) − 1 that has no zero-sum subsequence of length n is of the form S = T^{n−1} for some T ∈ F(G). (A group for which this is true is said to have Property D.)

Apparently, these four claims are closely related. Obviously, (C2) is a stronger claim than (C1), and for G ≅ C_{n}^{r} the claim (C4) is stronger than (C2). And, it is known that if for a group (C1) is true, then so is Conjecture 1.1 (see [14, Proposition 2.7]). Moreover, it is known that (C4) implies (C3). Conversely, if for a group both (C1) and (C3) are true, then so is (C4) (see [18, Theorem 2]).

No counterexample to Conjecture 1.1 or to these claims is known and there are several results that support them (see, e.g., [13, 15, 18, 7]). However, they are only confirmed for very few types of groups. It is easy to see that elementary 2-groups have Property D and H. Harborth [22, Beweis von Hilfssatz 3] showed (not using this terminology) that elementary 3-groups have Property D as well. Furthermore, for cyclic groups the inverse problems are well investigated (see, e.g., [12, 11, 29, 17]), and in particular it is known that cyclic groups have Property D. Yet, for groups of rank 2 only Conjecture 1.1 is confirmed in general (cf. Theorem 2.2); the more general claims are confirmed only in special cases: for instance it is known that C_{n}^{2} has Property D if n is not divisible by a prime greater than 7 (see [28] and the references there). Additionally, Conjecture 1.1 is confirmed for certain 2- and 3-groups (see [7]), in particular for groups of exponent 4 (see [14]), for C_{5}^{3} (see [16, Theorem 6.6.4]), and for a special type of p-group with “large” exponent (see [27]).

In this paper, we confirm Conjecture 1.1 and the claims in Open Problems 1.2 for certain groups and obtain results that support them for more general groups. Moreover, we determine the precise value of s(G) for certain groups of rank 3. Below, we outline the results of this paper in more detail.

First, we obtain two results valid for fairly general groups. The first gives some information on the structure of “long” sequences without a zero-sum subsequence of length equal to the exponent of the group.

Theorem 1.3. Let G be a finite abelian group with exp(G) = n. Let S ∈ F(G) such that |S| ≥ η(G) + n − 2 and S has no zero-sum subsequence of length n.

1. v_{g}(S) ≠ n − 2 for each g ∈ G.

2. If n − 3 ≥ ⌊(n − 1)/2⌋ and gcd(2, n) = 1, then v_{g}(S) ≠ n − 3 for each g ∈ G.

3. If n − 4 ≥ ⌊(n − 1)/2⌋ and gcd(6, n) = 1, then v_{g}(S) ≠ n − 4 for each g ∈ G.

This theorem directly yields the following result.

Corollary 1.4. Let G be a finite abelian group with exp(G) = n. Let S ∈ F(G) such that either |S| = s(G) − 1 and S has no zero-sum subsequence of length n, or |S| = η(G) − 1 and S has no non-empty zero-sum subsequence of length at most n. Then assertions 1., 2., and 3. of Theorem 1.3 hold.

This result, in particular, implies that if (C2) (or Properties C or D) should not hold for some group, then the structure of the extremal sequences has to differ considerably from the “expected” one. Furthermore, it immediately implies that C_{3}^{r} has Property D for every r ∈ ℕ.

The second result is an upper bound on s(G), which supports Conjecture 1.1. For now, we only state a special case; for the more technical results see Section 4.

Theorem 1.5. Let G be a finite abelian group and let H ⊂ G be a subgroup such that exp(G) = exp(H) exp(G/H). If exp(G) ≥ |G/H|^{2}, then

s(G) ≤ exp(G/H)s(H) + η(G/H) − 1.

At first it might not be clear that this results actually supports Conjecture 1.1 and, thus, we add the following explanation. We recall a result that generalizes a classical result of H. Harborth [22]; also see Theorem 1.2 and Lemma 4.1 in [7] for other and more general results of this type.

Lemma 1.6. ([5, Proposition 3.1]) Let G be a finite abelian group and let H ⊂ G be a subgroup such that exp(G) = exp(H) exp(G/H). Then

s(G) ≤ exp(G/H)s(H) + s(G/H) − exp(G/H).

Consequently, if Conjecture 1.1 is true for G/H, then the upper bound of Theorem 1.5 follows immediately. Conversely, we can use Theorem 1.5 to confirm, under certain conditions, Conjecture 1.1 (see Section 4 for details).

Then, we focus on specific groups of rank 3 and obtain the following results.

Theorem 1.7. Let n = 3^{a}5^{b} for a, b ∈ ℕ_{0}. Then

s(C_{n}^{3}) = η(C_{n}^{3}) + n − 1 = 9n − 8.

Thus, equality holds at the lower bound obtained by C. Elsholtz [8] (cf. Theorem 2.2.3 for his actual result, which is more general), so far this was known only for n = 3^{a}.

Theorem 1.8. Let n = 2^{a}3 with a ∈ ℕ. Then

s(C_{n}^{3}) = η(C_{n}^{3}) + n − 1 = 8n − 7.

Thus, equality holds at the classical lower bound due to H. Harborth [22] (cf. Theorem 2.2.2). The crucial point in the proofs of these two results is the investigation of C_{5}^{3} and C_{6}^{3}, respectively. In these investigations Theorem 1.3 plays a key role. However, considerable additional effort and the aid of a computer is needed to obtain the results. In particular, we also prove that (C2) holds for C_{6}^{3} (see Proposition 6.3) and moreover obtain the following result.

Theorem 1.9. Let a ∈ ℕ. The group C_{5^{a}}^{3} has Property D.

In view of these results, we formulate the following conjecture.

Conjecture 1.10. Let n ∈ ℕ. Then

s(C_{n}^{3}) = \begin{cases}8n − 7 & if n is even \\ 9n − 8 & if n is odd . \end{cases}

As mentioned above, 8n − 7 and 9n − 8, respectively, are known to be lower bounds. Moreover, if n is even, C_{n}^{3} has Property D, and s(C_{m}^{3}) = 9m − 8 where m denotes the maximal odd divisor of n, then s(C_{n}^{3}) = 8n − 7; this follows by Lemma 1.6 and the wellknown fact that this conjecture is true for powers of 2 (cf. Theorem 2.2.2).

The organization of the paper is as follows: in Section 2 we recall basic terminology and results, and each of the other sections is devoted to the proof of one or two of the above mentioned theorems. Following [7], we use geometrical methods.

2. Preliminaries

Our terminology and notation is consistent with the monograph [21]. For convenience we recall some key notions.

Let ℕ and ℕ_{0} denote the positive and non-negative integers, respectively. Throughout, all finite abelian groups are written additively. For r, n ∈ ℕ, we denote by C_{n} a cyclic group of order n and by C_{n}^{r} the direct sum of r copies of C_{n}.

Let G denote a finite abelian group. If |G| > 1, then there exist uniquely determined integers 1 < n_{1} | ⋯ | n_{r} such that G ≅ C_{n_{1}} ⊕ ⋯ ⊕ C_{n_{r}}, and exp(G) = n_{r} is called the exponent of G and r(G) = r the rank of G. For |G| = 1, let exp(G) = 1 and r(G) = 0. We call G a p-group if exp(G) = p^{k} for p a prime number and k ∈ ℕ, and we call G an elementary p-group if exp(G) = p.

We denote by F(G) the (multiplicatively written) free abelian monoid with basis G. An element S ∈ F(G) is called a sequence over G and is written in the following ways:

S = ∏_{g∈G} g^{v_{g}(S)} = ∏_{i=1}^{l} g_{i},

where v_{g}(S) ∈ ℕ_{0}, and l ∈ ℕ_{0} and g_{i} ∈ G. The neutral element of F(G) is called the empty sequence. We call |S| = l ∈ ℕ_{0} the length, σ(S) = ∑_{i=1}^{l} g_{i} ∈ G the sum, and supp(S) = {g ∈ G: v_{g}(S) > 0} the support of S. Moreover, v_{g}(S) is called the multiplicity of g in S.

A sequence is called a zero-sum sequence if σ(S) = 0, it is called squarefree if v_{g}(S) ≤ 1 for each g ∈ G, and it is called short (with respect to G) if 1 ≤ |S| ≤ exp(G). A sequence T is called a subsequence of S (in symbols T | S) if T divides S (in F(G)), i.e., there exists a sequence T′ ∈ F(G) such that T T′ = S; clearly the sequence T′ is uniquely determined by T and S and we denote it by T^{−1}S.

As mentioned in Section 1, we investigate the invariants s(·) and η(·). In our investigations we make use of an other related invariant as well. We summarize their definitions.

Definition 2.1 Let G be a finite abelian group. We denote by

• η(G) the smallest l ∈ ℕ such that every sequence S ∈ F(G) of length |S| ≥ l has a short zero-sum subsequence.

• s(G) the smallest l ∈ ℕ such that every sequence S ∈ F(G) of length |S| ≥ l has a zero-sum subsequence of length exp(G).

• g(G) the smallest l ∈ ℕ such that every squarefree sequence S ∈ F(G) of length |S| ≥ l has a zero-sum subsequence of length exp(G).

We point out that, though, in case G is an elementary 2-group or a cyclic group of even order no squarefree zero-sum sequences over G of length exp(G) exist, the invariant g(G) is nevertheless well-defined (cf. [16, Lemma 10.1]).

In the following theorem we recall known results on these invariants that we use in this paper.

Theorem 2.2. Let m, n, r ∈ ℕ with m | n.

1. η(C_{m} ⊕ C_{n}) = 2m + n − 2 and s(C_{m} ⊕ C_{n}) = 2m + 2n − 3.

2. η(C_{n}^{r}) ≥ (2^{r} − 1)(n − 1) + 1 and s(C_{n}^{r}) ≥ 2^{r}(n − 1) + 1. If n is a power of 2, then equality holds.

3. If n is odd, then η(C_{n}^{3}) ≥ 8n − 7 and s(C_{n}^{3}) ≥ 9n − 8. If n is a power of 3, then equality holds.

4. g(C_{5}^{2}) = 9 and g(C_{3}^{3}) = 10.

Proof.

1. The result is based on work of C. Reiher [26] and may be found in [21, Theorem 5.8.3].

2. The result is due to H. Harborth [22, Hilfsatz 1 and Satz 1], also see [7, Proposition 3.1].

3. The lower bound is due to C. Elsholtz [8, Theorem] (actually, he obtained an improvement on (2) for odd n for arbitrary r ≥ 3; moreover see [7] for further improvements for r ≥ 4). Equality for powers of 3 holds by Lemma 1.6, since s(C_{3}^{3}) = 19 (see [22, Satz 4]); also cf. [7, Corollary 4.5].

4. The results are due to A. Kemnitz [24, Theorem 3] and H. Harborth [22, Beweis von Satz 4], respectively. The latter result was also obtained in other contexts; see [7, Section 5] for details. □

Let G′ be a finite abelian group. For every map ϕ : G → G′ there exists a unique continuation to a monoid homomorphism F(G) → F(G′), which we thus denote by ϕ as well; it is given by ϕ(∏_{i=1}^{l} g_{i}) = ∏_{i=1}^{l} ϕ(g_{i}). In particular, |S| = |ϕ(S)| and ϕ(supp(S)) = supp(ϕ(S)), and if ϕ : G → G′ is a homomorphism, then σ(ϕ(S)) = ϕ(σ(S)).

We call a map α : G → G′ affine if there exists a homomorphism ϕ_{α} : G → G′ and an element h_{α} ∈ G′ such that α(g) = ϕ_{α}(g)+h_{α} for every g ∈ G; furthermore, we call a bijective affine map an affinity. Obviously, for α an affine map, ϕ_{α} and h_{α} are uniquely determined, and α is an affinity if and only if ϕ_{α} is an isomorphism.

We will frequently and freely make use of the following result (see [7, Lemma 2.2]).

Lemma 2.3. Let G and G′ be finite abelian groups, let S ∈ F(G), and let ϕ : G → G′. Suppose that ϕ is an affinity (in particular exp(G′) = exp(G)). Then S has a zero-sum subsequence of length exp(G) if and only if ϕ(S) has a zero-sum subsequence of length exp(G).

Elementary p-groups are in a natural way vector spaces over 𝔽_{p}, the field with p elements; whenever it is convenient we consider elementary p-groups as vector spaces over 𝔽_{p}. Clearly, in this case our definition of an affinity coincides with the usual one.

As in [7], we use the following well-known geometric notion in our investigations (cf., e.g., the monograph [23, Chapters 16 and 18]): a set of points C (in some geometry) is called a cap if no three distinct points in C are collinear. Considering elementary p-groups as vector spaces these are naturally affine geometries. Explicitly, a subset C of an elementary p-group is a cap if and only if for each three distinct elements f, g, h ∈ C we have ⟨g − f⟩ ≠ ⟨h − f⟩. At one point, in Lemma 6.1, we need to embed an elementary p-group into a projective geometry in order to apply geometric results; we give the details there.

As discussed in [7] in detail, the investigation of (the maximal cardinality) of caps and of s(G) and g(G) for elementary p-groups is closely related. In particular, for p = 3 these problems are equivalent. We make use of this relation in Sections 5 and 6.

3. Proof of Theorem 1.3 and its Corollary

First, we prove Theorem 1.3 and then Corollary 1.4.

Proof of Theorem 1.3. We prove the three statements separately. In each case, we suppose that n fulfills the respective condition and assume to the contrary that v_{g}(S)=n−i for some g ∈ G, where i equals 2, 3, and 4, respectively. By Lemma 2.3 we may assume that g = 0.

1. For n = 1 the claim is trivial and we thus assume n ≥ 2. Let S = 0^{n−2}T. We have |T | ≥ η(G). Thus, by definition of η(G), there exists a short zero-sum subsequence W | T and, since 0 ∤ T, we have |W | ≥ 2. Therefore, W 0^{n−|W |} is a subsequence of S, and its sum equals 0 and its length equals n, a contradiction.

2. Let S = 0^{n−3}T. We have |T | ≥ η(G) + 1. Thus, there exists a short zero-sum subsequence W | T. If |W | ≥ 3, the sequence W 0^{n−|W |} yields a contradiction. Thus, since |W | > 1, we have |W | = 2, i.e., W = (−g)g for some g ∈ G. Indeed, we may assume that every short zero-sum subsequence of T has length 2. Consequently, since n ≥ 5, the sequence W^{−1}T has no short zero-sum subsequence. However, the sequences g^{−1}T = (−g)W^{−1}T and (−g)^{−1}T = gW^{−1}T, since they are of length η(G), each have a short zero-sum subsequence, which consequently contains −g and g, respectively. By assumption, these short zero-sum sequences are of length 2 and thus are both equal to (−g)g. Consequently, g | g^{−1}T and −g | (−g)^{−1}T. Since 2 ∤ n, we have −g ≠ g and therefore (−g)^{2}g^{2} is a short zero-sum subsequence of T of length 4, a contradiction.

3. Let S = 0^{n−4}T. The sequence T has a short zero-sum subsequence W, which is of length at least 2. If |W | ≥ 4, then W 0^{n−|W |} is a subsequence of S, which yields a contradiction. Moreover, if W^{−1}T contains a short zero-sum sequence W′, then, since n ≥ 7, we get that W, W′, or W W′ is a short zero-sum subsequence of T of length at least 4. Thus, we may assume that W^{−1}T has no short zero-sum subsequence, and consequently |W^{−1}T | < η(G) and |W | > 2.

In other words, we may assume that for each short zero-sum subsequence V of T

• |V | = 3 and

• V^{−1}T has no short zero-sum subsequence (in particular, if V′ is a short zero-sum subsequence of T, then supp(V) ∩ supp(V′) ≠ ∅).

Now, we distinguish two cases.

Case 1. Every short zero-sum subsequence of T is squarefree. Let V be a short zerosum subsequence of T and let g ∈ supp(V). Since V^{−1}T does not have a short zero-sum subsequence, gV^{−1}T has a short zero-sum subsequence V′ and g ∈ supp(V′). By assumption V′ is squarefree. Thus, it follows that v_{g}(T) = 1, since otherwise V′ | V^{−1}T, a contradiction. We write V = g_{1}g_{2}g_{3}. By the above reasoning, for each 1 ≤ j ≤ 3, there exists a short zero-sum subsequence U_{j} | g_{j}V^{−1}T with g_{j} ∈ supp(U_{j}). We distinguish two subcases.

Subcase 1.1. ⋂_{j=1}^{3} supp(U_{j}) ≠ ∅. The intersection contains a unique element; we denote it by h ∈ G. We note that h ∉ supp(V). For 1 ≤ j ≤ 3, let h_{j} ∈ G such that U_{j} = g_{j}hh_{j}. There exists a short zero-sum subsequence R | h_{1}U_{1}^{−1}T with h_{1} ∈ supp(R_{1}). We have supp(R) ∩ supp(V) = {g_{j}} for some 1 ≤ j ≤ 3, and, since g_{1} ∉ supp(R), we have j ∈ {2, 3}. Let i ∈ ℕ such that {i, j} = {2, 3}. We note that {h, g_{i}} ∩ supp(R) = ∅ and g_{j} ∉ supp(U_{i}). Thus supp(R) ∩ supp(U_{i}) = {h_{i}} and R = h_{1}h_{i}g_{j}. We note that V U_{1}U_{i} = R(g_{1}hg_{i})^{2}. Since σ(V) = σ(U_{1}) = σ(U_{i}) = σ(R) = 0, we infer that 2σ(g_{1}hg_{i}) = σ((g_{1}hg_{i})^{2}) = 0. Thus, since 2 ∤ n, we have σ(g_{1}hg_{i}) = 0. However, this implies h = −g_{1} − g_{i} = g_{j}, a contradiction, since U_{j} is squarefree.

Subcase 1.2. ⋂_{j=1}^{3} supp(U_{j}) = ∅. Since |supp(U_{i}) ∩ supp(U_{j})| = 1 for 1 ≤ i < j ≤ 3, we infer that | ⋃_{j=1}^{3} supp(U_{i}) \ supp(V)| = 3, and each of these 3 elements is contained in exactly 2 of the U_{j}s. Thus U_{1}U_{2}U_{3} = V R^{2} for some squarefree sequence R with supp(R) ∩ supp(V) = ∅. Furthermore, 2σ(R) = σ(R^{2}) = 0 and thus σ(R) = 0. Consequently, R is a short zero-sum subsequence of V^{−1}T, a contradiction.

Case 2. There exists a short zero-sum subsequence V of T that is not squarefree. Since |V | = 3 and since 3 ∤ n, we have V = gh^{2} with distinct elements g, h ∈ G. There exists a short zero-sum subsequence U | gV^{−1}T with g ∈ supp(U). We distinguish three cases.

Subcase 2.1. v_{h}(U) ≥ 1. This implies v_{h}(U) = 2, U = V, and v_{h}(T) ≥ 4. Consequently v_{g}(T) = 1. Let R | hV^{−1}T a short zero-sum sequence with h ∈ supp(R). Since g ∉ supp(R) and since R ≠ h^{3}, we infer that R | V^{−1}T, a contradiction.

Subcase 2.2. v_{g}(U) = 1 (and v_{h}(U) = 0). We have v_{g}(T) = 1, otherwise U | V^{−1}T. Moreover, since v_{g}(U) = 1 and 2 ∤ n, we know that U is squarefree. Let R | hV^{−1}T be a short zero-sum sequence with h ∈ supp(R). We have v_{g}(R) = 0 and thus v_{h}(R) = 1. Since supp(R)∩supp(U) ≠ ∅, we have U = gff_{1} and R = hff_{2} with f, f_{1}, f_{2} ∈ G. Clearly f_{1} ≠ f_{2}. Let Q | f_{1}U^{−1}T be a short zero-sum sequence with f_{1} ∈ supp(Q). Since supp(Q)∩supp(V) ≠ ∅, we have Q = f_{1}hf_{3}. We have f_{3} ≠ h. Moreover, since f ≠ f_{1} and f + f_{2} = f_{1} + f_{3}, we have f_{2} ≠ f_{3}. Thus Q | R^{−1}T, a contradiction.

Subcase 2.3. v_{g}(U) ≥ 2 (and v_{h}(U) = 0). Let U = g^{2}f with f ∈ G, and we have g ≠ f. Let R | fU^{−1}T a short zero-sum sequence with f ∈ supp(R). We may assume that v_{f}(R) ≥ 2 and v_{g}(R) = 0, otherwise we are in the situation of Subcase 2.1 or 2.2. Let R = f^{2}f′. On the one hand we have g ≠ f, and furthermore

g + 2h = 2g + f = 2f + f′ = 0,

which implies

• f ≠ h, since otherwise g = h, a contradiction,

• f′ ≠ g, since otherwise f = g, a contradiction,

• f′ ≠ h, since otherwise 3(f +g+h) = 0 and f +g+h = 0, a contradiction as (fgh)^{2} | T.

On the other hand, we have supp(R) ∩ supp(V) ≠ ∅, that is {g, h} ∩ {f, f′} ≠ ∅, a contradiction. □

Proof of Corollary 1.4. If |S| = s(G) − 1 and S has no zero-sum subsequence of length n, then, since s(G) ≥ η(G) + n − 1, the result is obvious by Theorem 1.3. If |S| = η(G) − 1 and S has no short zero-sum subsequence, then we note that 0^{n−1}S has no zero-sum subsequence of length n and again the claim is obvious by Theorem 1.3. □

4. Proof of Theorem 1.5 and Related Results

To prove Theorem 1.5, we first derive a technical result (Proposition 4.1). From this result, using known upper and lower bounds for the involved quantities, we derive Theorem 1.5. Moreover, we discuss some other ways to derive “explicit” results from the technical one.

Proposition 4.1. Let G be a finite abelian group and let H ⊂ G be a subgroup such that exp(G) = exp(H) exp(G/H). We denote exp(G/H) by n. Then

s(G) ≤ max\{|G/H|(n − 2 + (\frac{n}{⌈\frac{n+1}{2}⌉} − 1)(s(G/H) − η(G/H) − 1)),
n s(H) + η(G/H) − 1}.

Proof. Let S ∈ F(G) such that S is at least as long as the claimed upper bound on s(G). We have to show that S has a zero-sum subsequence of length exp(G). Let ϕ : G → G/H be the canonical epimorphism. Without restriction we assume that v_{0}(ϕ(S)) = max{v_{g}(ϕ(S)): g ∈ G/H}; let v_{0}(ϕ(S)) = v. We have v ≥ |S|/|G/H|. We write ϕ(S) = 0^{v}T. Let T_{1} … T_{a} | T such that σ(T_{i}) = 0 ∈ G/H and |T_{i}| = n for each 1 ≤ i ≤ a. We assume that a is maximal, i.e., W = T (∏_{i=1}^{a} T_{i})^{−1} has no zero-sum subsequence of length n, and thus |W | ≤ s(G/H)−1. Further, let W_{1} … W_{b} | W such that each W_{i} is a short zero-sum sequence. We may assume that |W_{1}| ≥ ⋯ ≥ |W_{b}| and that |W_{i}| ≥ ⌈(n + 1)/2⌉ for each 1 ≤ i ≤ b − 1. Moreover, we assume that |W | − ∑_{i=1}^{b} |W_{i}| ≤ η(G/H) − 1, and in case b ≥ 1 that |W | − ∑_{i=1}^{b−1} |W_{i}| ≥ η(G/H).

If ∑_{i=1}^{b}(n − |W_{i}|) ≤ v, then T_{1} … T_{a}(W_{1}0^{n−|W_{1}|}) … (W_{b}0^{n−|W_{b}|}) | ϕ(S), i.e., we can “extend” the W_{i}s to zero-sum subsequences of length n of ϕ(S). We assert that indeed ∑_{i=1}^{b}(n−|W_{i}|) ≤ v. If b = 0, this is trivial. If b = 1, then n−|W_{b}| ≤ n−2 ≤ |S|/|G/H| ≤ v. We assume b ≥ 2. We have (b − 1)|W_{b−1}| ≤ ∑_{i=1}^{b−1} |W_{i}| ≤ s(G/H) − 1 − η(G/H). Thus

∑_{i=1}^{b}(n − |W_{i}|) ≤ (n − |W_{b}|) + (b − 1)(n − |W_{b−1}|)

≤ n − 2 + \frac{s(G/H) − η(G/H) − 1}{|W_{b−1}|}(n − |W_{b−1}|)

≤ n − 2 + (s(G/H) − η(G/H) − 1)\frac{n − ⌈\frac{n+1}{2}⌉}{⌈\frac{n+1}{2}⌉}

≤ \frac{|S|}{|G/H|} ≤ v.

Now, we set c = ⌊(v − ∑_{i=1}^{b}(n − |W_{i}|))/n⌋ and have

T_{1} … T_{a}(W_{1}0^{n−|W_{1}|}) … (W_{b}0^{n−|W_{b}|})(0^{n})^{c} | ϕ(S).

Thus, we have a + b + c zero-sum subsequences of length n of ϕ(S).

We assert that a + b + c > s(H) − 1. We have

(a + b)n = ∑_{i=1}^{a} |T_{i}| + ∑_{i=1}^{b} |W_{i}| + ∑_{i=1}^{b}(n − |W_{i}|)

and |S|−v−∑_{i=1}^{a} |T_{i}|−∑_{i=1}^{b} |W_{i}| ≤ η(G/H)−1. Moreover, nc ≥ v−∑_{i=1}^{b}(n−|W_{i}|)−(n−1). Consequently,

n(a + b + c) ≥

|S| − v − η(G/H) + 1 + ∑_{i=1}^{b}(n − |W_{i}|) + v − ∑_{i=1}^{b}(n − |W_{i}|) − (n − 1) ≥

n s(H) + η(G/H) − 1 − η(G/H) + 1 − (n − 1) =

n s(H) − (n − 1) > n(s(H) − 1).

Let S_{1} … S_{a+b+c} | S such that ϕ(S_{i}) is equal to T_{i}, W_{i−a}0^{n−|W_{i−a}|} or 0^{n} according as 1 ≤ i ≤ a, a+1 ≤ i ≤ a+b or a+b+1 ≤ i. Since ∏_{i=1}^{a+b+c} σ(S_{i}) ∈ F(H) is a sequence of length at least s(H), it has a zero-sum subsequence of length exp(H). Let I ⊂ {1, …, a + b + c} a subset of cardinality exp(H) such that ∑_{i∈I} σ(S_{i}) = 0. Then ∏_{i∈I} S_{i} is a zero-sum subsequence of S of length n exp(H) = exp(G). □

From this result we can derive the following corollary, which is slightly less precise but more convenient for the present purpose.

Corollary 4.2. Let G be a finite abelian group and let H ⊂ G be a subgroup such that exp(G) = exp(H) exp(G/H) and

s(H) ≥ \frac{|G/H|}{exp(G/H)}(s(G/H) − η(G/H) + exp(G/H) − 3).

Then s(G) ≤ exp(G/H)s(H) + η(G/H) − 1.

Proof. We denote exp(G/H) by n. For n = 1 the result is trivial and we assume n ≥ 2. By Proposition 4.1, it suffices to prove that

|G/H|(n − 2 + (\frac{n}{⌈\frac{n+1}{2}⌉} − 1)(s(G/H) − η(G/H) − 1)) ≤ n s(H) + η(G/H) − 1.

This follows by an easy calculation. □

In order to obtain Theorem 1.5 we need the following bounds on s(·) and η(·). The lower bounds are fairly obvious. The upper bounds for s(·) and η(·) were obtained in [20] (also cf. [21, Theorem 5.7.4]). All bounds are sharp for cyclic groups.

Proposition 4.3. Let G be a finite abelian group with exp(G) = n.

1. n ≤ η(G) ≤ |G|.

2. 2n − 1 ≤ s(G) ≤ |G| + n − 1.

Having all auxiliary results at hand, we prove Theorem 1.5.

Proof of Theorem 1.5. By Corollary 4.2 it suffices to assert that s(H) ≥ |G/H|(s(G/H) − η(G/H) + n − 3)/n. Furthermore, using the bounds recalled in Proposition 4.3 it thus suffices to show the inequality 2 exp(H) − 1 ≥ |G/H|(|G/H| − 1 + n − 3)/n. By assumption n exp(H) = exp(G), thus if exp(G) ≥ |G/H|^{2} this inequality holds. □

For various types of groups refined upper and lower bounds for s(·) and η(·) are known, see, e.g., [1] and [7]. Using these bounds or known precise values for s(·) and η(·), instead of the general bounds, we can obtain refined versions of Theorem 1.5 for various types of groups. As an example, we state the following result.

Corollary 4.4. Let m, n, r ∈ ℕ with r ≥ 3. If m ≥ n^{2r−1}/2^{r}, then s(C_{mn}^{r}) ≤ n s(C_{m}^{r}) + η(C_{n}^{r}) − 1.

Proof. For n = 1 the assertion is obvious. Let n ≥ 2. Let H ⊂ C_{mn}^{r} denote the subgroup of elements whose order divides m; it is isomorphic to C_{m}^{r} and C_{mn}^{r}/H ≅ C_{n}^{r}. Using the classical lower bounds, recalled in Theorem 2.2.2, for η(C_{n}^{r}) and s(C_{m}^{r}), and the upper bound of Proposition 4.3 for s(C_{n}^{r}), the result follows by Corollary 4.2. □

As indicated in Section 1, the results of this section can be applied to confirm Conjecture 1.1 for certain groups. In particular, this is the case if there exists a “large” subgroup for which equality holds in Lemma 1.6.

Corollary 4.5. Let G be a finite abelian group and let H ⊂ G be a subgroup such that exp(G) = exp(H) exp(G/H) and exp(G) ≥ |G/H|^{2}. If s(G) = exp(G/H)s(H) + s(G/H) − exp(G/H), then s(G/H) = η(G/H) + exp(G/H) − 1.

Proof. By Theorem 1.5 we have s(G) ≤ exp(G/H)s(H) + η(G/H) − 1. Since s(G) = exp(G/H)s(H)+s(G/H)−exp(G/H), we infer s(G/H) ≤ η(G/H)+exp(G/H)−1. However, it is well-known that s(G/H) ≥ η(G/H) + exp(G/H) − 1. □

Corollary 4.6. Let n, r ∈ ℕ such that there exists a constant c = c(n, r) with s(C_{n^{a}}^{r}) = c(n^{a} − 1) + 1 for every a ∈ ℕ. Then s(C_{n^{a}}^{r}) = η(C_{n^{a}}^{r}) + n^{a} − 1 for every a ∈ ℕ.

Proof. Let a ∈ ℕ. We need to show s(C_{n^{a}}^{r}) = η(C_{n^{a}}^{r}) + n^{a} − 1. Let b = (2r − 1)a and let G = C_{n^{a+b}}^{r}. By assumption we have s(G) = c(n^{a+b}−1)+1. Let H ⊂ G be the subgroup isomorphic to C_{n^{b}}^{r}. Clearly G/H ≅ C_{n^{a}}^{r}. We have s(G) = exp(G/H)s(H) + s(G/H) − exp(G/H) and, since n^{a+b} ≥ (n^{ar})^{2}, it follows by Corollary 4.5 that s(G/H) = η(G/H) + exp(G/H) − 1. □

We point out that r and n that fulfil the condition of Corollary 4.6 actually exist. It is well-known that the conditions hold for r ≤ 2 and arbitrary n, where however also the conclusion of Corollary 4.6 is known; but, in the following section we prove that they hold for r = 3 and every n whose only prime divisor are 3 and 5 as well, and we conjecture that they hold in further cases as well (cf. Conjecture 1.10).

5. Proof of Theorem 1.7 and Theorem 1.9

We recall and prove several auxiliary results. We start with the more general ones.

5.1 General Auxiliary Results

Let G be a finite abelian group and let ∅ ≠ A, B ⊂ G. Then A + B = {a + b: a ∈ A, b ∈ B} is called the sum of A and B, and ∑_{k} A = {∑_{a∈A′} a: A′ ⊂ A, |A′| = k} is called the set of k-term subsums. In the following proposition we recall two well-known results on set addition. The first result is the classical Theorem of Cauchy–Davenport and the second one was conjectured by P. Erdős and H. Heilbronn [10] and proved by J. Dias da Silva and Y. ould Hamidoune [6], and differently by N. Alon, M. B. Nathanson, and I. Ruzsa [2, 3]. We refer to the monograph [25], in particular Theorem 2.2 and Theorem 3.4, for a detailed account.

Proposition 5.1. Let p be a prime number, k ∈ ℕ, and ∅ ≠ A, A_{1}, …, A_{r} ⊂ C_{p}.

1. |A_{1} + ⋯ + A_{r}| ≥ min{p, ∑_{i=1}^{r} |A_{i}| − (r − 1)}.

2. | ∑_{k} A| ≥ min{p, k(|A| − k) + 1}.

Now, we use these results to establish the following lemma, which was proved in [19] in the special case r = 2.

Lemma 5.2. Let p be a prime number and r ≥ 2. Let π : C_{p}^{r} → C_{p}^{r} be a linear projection onto a subgroup of rank r − 1. Further, let S ∈ F(C_{p}^{r}) be a squarefree sequence. If there exists a zero-sum subsequence T | π(S) such that ∑_{h∈im(π)} v_{h}(T)(v_{h}(π(S)) − v_{h}(T)) ≥ p − 1, then there exists a zero-sum subsequence T^{∗} | S with |T^{∗}| = |T |.

Proof. Let H = im(π). We assume that T | π(S) is a zero-sum sequence such that ∑_{h∈H} v_{h}(T)(v_{h}(π(S)) − v_{h}(T)) ≥ p − 1

For h ∈ H, let S_{h} | S such that π(S_{h}) = h^{v_{h}(π(S))}. Since S is squarefree, we know that (id−π)(S_{h}) ∈ F(ker(π)) is squarefree. Clearly ker(π) ≅ C_{p}. Therefore, by Proposition 5.1.2,

|{σ((id − π)(T_{h})): T_{h} | S_{h}, |T_{h}| = v_{h}(T)}| ≥ min{p, v_{h}(T)(|S_{h}| − v_{h}(T)) + 1}.

Furthermore,

{σ((id − π)(T′)): T′ | S, π(T′) = T } =

{σ((id − π)(∏_{h∈H} T_{h})): T_{h} | S_{h}, |T_{h}| = v_{h}(T) for each h ∈ H} =

{∑_{h∈H} σ((id − π)(T_{h})): T_{h} | S_{h}, |T_{h}| = v_{h}(T) for each h ∈ H} =

∑_{h∈H}{σ((id − π)(T_{h})): T_{h} | S_{h}, |T_{h}| = v_{h}(T)} = A.

Now, by Proposition 5.1.1, the above inequality, and the assumption, we have

|A| ≥ min{p, ∑_{h∈H} |{σ((id − π)(T_{h})): T_{h} | S_{h}, |T_{h}| = v_{h}(T)}| − (|H| − 1)}

≥ min{p, ∑_{h∈H} min{p, v_{h}(T)(|S_{h}| − v_{h}(T)) + 1} − (|H| − 1)}

≥ min{p, 1 + ∑_{h∈H} v_{h}(T)(|S_{h}| − v_{h}(T))}

= p.

Thus, A = ker(π) ⊃ {0} and consequently there exists a sequence T^{∗} | T such that π(T^{∗}) = T and σ((id − π)(T^{∗})) = 0. Since by definition σ(π(T^{∗})) = σ(π(T)) = 0, we have σ(T^{∗}) = 0 and clearly |T | = |T^{∗}|. □

5.2 Results for Elementary 5-groups

For elementary 3-groups it is known that the support of a sequence without a zero-sum subsequence of length equal to the exponent is a cap (cf. [7, Lemma 5.2]). Though, this cannot hold in general for elementary 5-groups, we prove that this is true for the sequences that are of maximal length.

Proposition 5.3. Let r ∈ ℕ and let S ∈ F(C_{5}^{r}).

1. If |S| = s(C_{5}^{r}) − 1 and S has no zero-sum subsequence of length 5, then supp(S) is a cap.

2. If |S| = η(C_{5}^{r}) − 1 and S has no short zero-sum subsequence, then supp(S) is a cap.

Proof. 1. We suppose that |S| = s(C_{5}^{r}) − 1 and S has no zero-sum subsequence of length 5. Let f, g, h ∈ supp(S) be distinct elements. We have to show that ⟨g−f⟩ ≠ ⟨h−f⟩. By Lemma 2.3 we may assume that f = 0, and we assume to the contrary that h ∈ {2g, −2g, −g}. By Corollary 1.4 we know that v = v_{0}(S) ∈ {1, 4}. Let S = 0^{v}T. We distinguish several cases.

Case 1. v = 1 and h = −g. The sequence (gh)^{−1}T has a short zero-sum subsequence |W |. We have 2 ≤ |W | ≤ 5. Thus, gh0W, ghW, 0W, or W is a zero-sum subsequence of S of length 5.

Case 2. v = 1 and h = 2g. By Corollary 1.4 we have v_{g}(T) ∈ {1, 4}. If v_{g}(T) = 4, then g^{3}h0 is a zero-sum subsequence of S of length 5. Thus, we assume v_{g}(T) = 1. The sequence h^{−1}g^{2}T has a zero-sum subsequence W of length 5; this follows by Corollary 1.4, since the sequence has length s(C_{5}^{r}) − 1 and the multiplicity of g is 3. Since W ∤ T, we have g^{2} | W and therefore 0hg^{−2}W is a zero-sum subsequence of S of length 5.

Case 3. v = 4 and h = −g. The sequence gh0^{3} is a zero-sum subsequence of length 5 of S.

Case 4. v = 4 and h = 2g. If v_{g}(T) = 4, then 0g^{3}h | S and we are done. Thus, again, we assume v_{g}(T) = 1 and proceed similarly to Case 2.

Case 5. v = 1 or v = 4, and h = −2g. Since g = 2h, this follows by Case 2 and Case 4, respectively.

2. The argument is similar. We omit the details. □

Since clearly each sequence over C_{5}^{r} without a zero-sum subsequences of length 5, contains no element with multiplicity exceeding 4, Proposition 5.3 yields four times the maximal cardinality of a cap in C_{5}^{r} as an upper bound for s(C_{5}^{r})−1. One could combine this observation with results on caps in C_{5}^{r} (see, e.g., [4, Section 8]) to obtain bounds for s(C_{5}^{r}). However, to bound s(C_{n}^{r}) by n − 1 times the maximal cardinality of a cap, for n = 5, opposed to the situation for n = 3, seems to introduce a considerable error. Here, being interested in exact values, we do not pursue this approach any further. Yet, we make use of Proposition 5.3, in a different way, in the present investigations.

Now, we turn to the investigation of C_{5}^{3}.

Lemma 5.4. Let S ∈ F(C_{5}^{3}) such that |S| = s(C_{5}^{3}) − 1 and S has no zero-sum subsequence of length 5. Further, let T | S be a squarefree sequence. There exists a linear projection π : C_{5}^{3} → C_{5}^{3} onto a subgroup of rank 2 such that π(T) = U^{2}V where UV is a squarefree sequence and |U| ≥ |T |(|T | − 1)/62.

Proof. Let N be a subgroup of C_{5}^{3} of order 5. Let

q_{N} = |{{g, h}: {g, h} ⊂ supp(T), g − h ∈ N \ {0}}|.

We have

∑_{N<C_{5}^{3}, |N|=5} q_{N} = \binom{|T |}{2} ,

where N < C_{5}^{3} means that N is a subgroup. We note that C_{5}^{3} has (5^{3} − 1)/(5 − 1) = 31 subgroups of order 5. Thus, there exists some N′ such that

q_{N′} ≥ \frac{1}{31} \frac{|T |(|T | − 1)}{2} .

Let π′ : C_{5}^{3} → C_{5}^{3} be a linear projection onto N′ and let π = id − π′, which is a projection onto ker(π′) = H, a subgroup of C_{5}^{3} of rank 2. We observe that

q_{N′} = ∑_{h∈H} \binom{v_{h}(π(T))}{2} .

By Proposition 5.3, each triple of distinct elements in supp(S) does not lie on a line. Consequently, π maps no three distinct elements in supp(S) to the same element. Since T | S is squarefree, this implies that v_{h}(π(T)) ≤ 2 for each h ∈ H. Thus, v_{h}(π(T)) = 2 for q_{N′} ≥ |T |(|T | − 1)/62 elements h ∈ H, and the result follows. □

Next, we prove a result on the structure of sequences over C_{5}^{3} without a zero-sum subsequence of length 5 of maximal length. In particular, this result shows that (C2) is true for the group C_{5}^{3}.

Proposition 5.5. Let S ∈ F(C_{5}^{3}) such that |S| = s(C_{5}^{3}) − 1 and S has no zero-sum subsequence of length 5. Then (e_{0}e_{1}e_{2}e_{3}g)^{4} | S for some affine basis {e_{0}, e_{1}, e_{2}, e_{3}} of C_{5}^{3} and some g ∈ C_{5}^{3}.

Proof. By Corollary 1.4 we have v_{h}(S) ∈ {0, 1, 4} for each h ∈ C_{5}^{3}. First, we prove that at least 5 distinct elements have multiplicity 4 in S. We assume that this is not the case. Then |supp(S)| ≥ 36 − 3 · 4 = 24. Let T | S denote the maximal squarefree subsequence. By Lemma 5.4 there exists a linear projection π onto a subgroup of rank 2 such that π(T) = U^{2}V where UV is a squarefree sequence and |U| ≥ 24 · 23/62 > 8. Thus by Theorem 2.2.4 there exists a zero-sum subsequence W | U with |W | = 5. Let U′ | T such that π(U′) = U^{2}. By Lemma 5.2, applied to U′ and W, there exists a zero-sum subsequence W^{∗} of U′, and thus of S, of length |W | = 5, a contradiction. Thus, we have S = (g_{1}g_{2}g_{3}g_{4}g_{5})^{4}S′ with g_{i} ∈ G. It remains to show that {g_{1}, g_{2}, g_{3}, g_{4}, g_{5}} contains an affine basis of C_{5}^{3}. If this is not the case, then {g_{1}, g_{2}, g_{3}, g_{4}, g_{5}} is contained in an affine plane of C_{5}^{3}. Yet, by Lemma 2.3, since s(C_{5}^{2}) = 17 (see Theorem 2.2.1), this implies that (g_{1}g_{2}g_{3}g_{4}g_{5})^{4} has a zero-sum subsequence of length 5, a contradiction. □

We use this (incomplete) structural result as “initial value” for a program, which we describe below, that yields the following result.

Proposition 5.6. s(C_{5}^{3}) = 37 and C_{5}^{3} has Property D.

Proof and description of program. Let S ∈ F(C_{5}^{3}) such that |S| = s(C_{5}^{3}) − 1 and S has no zero-sum subsequence of length 5. We have to show that |S| = 36 and S = T^{4} for some T ∈ F(C_{5}^{3}).

Roughly speaking, our program recursively constructs sequences without a zero-sum subsequence of length 5, i.e., for S′ ∈ F(C_{5}^{3}) without a zero-sum subsequence of length 5 it determines all g ∈ G such that S′g has no zero-sum subsequence of length 5 (we refer to these elements as admissible elements of S′). It turns out that the set of admissible elements of (all) sequences of length 36 without a zero-sum subsequence of length 5 is empty, i.e. s(C_{5}^{3}) − 1 ≤ 36 and moreover every sequence of length 36 without a zero-sum subsequence of length 5 is equal to T^{4} for some T ∈ F(C_{5}^{3}).

However, actually our program does not start “from scratch” when constructing these sequences. By Proposition 5.5 we know that for every S ∈ F(C_{5}^{3}) with |S| = s(C_{5}^{3}) − 1 and without a zero-sum subsequence of length 5 there exists some U ∈ F(C_{5}^{3}) such that U^{4} | S, |U| = 5, and supp(U) contains an affine basis C_{5}^{3}. Moreover, by Lemma 2.3 we may assume that this affine basis is equal to {0, e_{1}, e_{2}, e_{3}} for some (fixed) basis {e_{1}, e_{2}, e_{3}} of C_{5}^{3}. Thus, since we are only interested in sequences of length s(C_{5}^{3}) − 1 we can restrict to considering sequences that have a subsequence with the above mentioned properties. Therefore, instead of starting the recursive construction with the empty sequence we can start it with a fixed sequence of length 16, and additionally we can make use of the fact that at least one (further) element has to occur with multiplicity 4.

To implement this procedure we represent the elements of C_{5}^{3} by (unsigned) integers in the following way: Every g ∈ C_{5}^{3} has a unique representation a_{g}e_{1} + b_{g}e_{2} + c_{g}e_{3} with 0 ≤ a_{g}, b_{g}, c_{g} ≤ 4. For each g ∈ C_{5}^{3} let n_{g} = 25a_{g} +5b_{g} +c_{g}. (Note that we are only interested in sums of at most 5 elements of C_{5}^{3}.) For the complete code and the detailed output of the

program see http://www.combinatorics.net.cn/homepage/hou/C53.html.  □

Finally, we use the results on C_{5}^{3} to prove Theorems 1.7 and 1.9.

Proof of Theorem 1.7. By Theorem 2.2.4 s(C_{3}^{3}) = 27 − 8 and by Proposition 5.6 s(C_{5}^{3}) = 45 − 8. Thus, the claim follows by [7, Corollary 4.5]; having all auxiliary results at hand, we sketch the argument for a more self-contained exposition: By Theorem 2.2.3 we known that s(C_{n}^{3}) ≥ 9n − 8 and we have to prove that 9n − 8 is an upper bound as well. We know this for C_{3}^{3} and C_{5}^{3}. Using Lemma 1.6, the general case follows by induction on a + b. Finally, noting that s(C_{n}^{3}) − n + 1 ≥ η(C_{n}^{3}) ≥ 8n − 7, the proof is complete. □

Proof of Theorem 1.9. By Proposition 5.6 we know that C_{5}^{3} has Property D. By [18, Theorem 1], this implies that C_{5^{a}}^{3} has Property D for every a ∈ ℕ. □

6. Proof of Theorem 1.8

Throughout this section we use the following convention and notation. We consider C_{6}^{3} as C_{3}^{3} ⊕ C_{2}^{3}, and we denote by π_{3} : C_{6}^{3} → C_{3}^{3} and π_{2} : C_{6}^{3} → C_{2}^{3} the canonical epimorphisms.

We need a further results on caps in C_{3}^{3}, or in other words squarefree sequences without a zero-sum subsequence of length 3. It is essentially well-known (cf. the monograph of J.W.P. Hirschfeld [23]), however only in the context of projective geometries. For convenience, we provide a detailed “translation.”

Lemma 6.1. Let A ⊂ C_{3}^{3} be a cap with |A| = 8. Then there exists at most one cap B ⊂ C_{3}^{3} with A ⊊ B.

Proof. If A is inclusion-maximal the statement is obvious. Thus, we assume that A is not inclusion-maximal. We embed C_{3}^{3} into PG(3, 3), the projective space of dimension 3 over the field of order 3; we denote the embedding by ι. We recall (cf. [23, Theorem 16.1.5]) that the maximal cardinality of a cap in PG(3, 3) is 10, and a cap with maximal cardinality is called an ovaloid.

First, we assert that ι(A) is contained in some ovaloid. Since A is not an inclusion maximal cap, ι(A) is not an inclusion-maximal cap, and there exists a cap C ⊂ PG(3, 3) such that ι(A) ⊊ C. Since |C| ≥ 9, it follows by [23, Theorem 18.4.2] or [23, Theorem 16.1.7] that C is contained in a (unique) elliptic quadric E. The quadric E is an ovaloid (cf. [23, Proof of Theorem 16.1.5]) and obviously ι(A) ⊂ E.

Now, let B ⊂ C_{3}^{3} be a cap with A ⊊ B. Then ι(A) ⊊ ι(B) and, since ι(A) ⊂ E and |ι(A)| = 8, it follows by [23, Theorem 18.4.2] that ι(B) ⊂ E. Since A, B ⊂ C_{3}^{3}, we have ι(A) ⊊ ι(B) ⊂ (E ∩ ι(C_{3}^{3})) ⊊ E; the last inclusion is proper, since every plane and thus in particular the plane “at infinity” intersects E (cf. [23, Lemma 16.1.6]). Since |ι(A)| = 8 and |E| = 10, this implies ι(B) = E ∩ ι(C_{3}^{3}). Consequently, ι(B) and thus B is unique. □

In the following lemma we obtain basic properties of sequences over C_{6}^{3} without a zerosum subsequence of length 6.

Lemma 6.2. Let S ∈ F(C_{6}^{3}) such that S has no zero-sum subsequence of length 6.

1. Let S_{1} … S_{m} | S with |S_{i}| = 3 and σ(π_{3}(S_{i})) = 0 for each 1 ≤ i ≤ m. If |S| ≥ 40 + ε, with ε ∈ {0, 1, 2}, then there exists a squarefree sequence T ∈ F(C_{3}^{3}) of length 7 + ε such that T^{2} | π_{3}(S(∏_{i=1}^{m} S_{i})^{−1}). In particular, m ≤ 8.

2. For g ∈ C_{3}^{3}, let S_{g} | S such that supp(π_{3}(S_{g})) = {g}. If |S| ≥ 40 + ε, with ε ∈ {0, 1}, and |S_{g}| ≥ 4, then |supp(S_{g})| ≤ 2 − ε.

Proof. 1. Without restriction we may assume that π_{3}(S(∏_{i=1}^{m} S_{i})^{−1}) has no zero-sum subsequence of length 3. On the one hand, we have |π_{3}(S(∏_{i=1}^{m} S_{i})^{−1})| ≤ 18 = s(C_{3}^{3}) − 1, |supp(π_{3}(S(∏_{i=1}^{m} S_{i})^{−1}))| ≤ 9 = g(C_{3}^{3}) − 1 (see Theorem 2.2), and v_{g}(π_{3}(S(∏_{i=1}^{m} S_{i})^{−1})) ≤ 2 for each g ∈ C_{3}^{3}. On the other hand, since S has no zero-sum subsequence of length 6, the sequence ∏_{i=1}^{m} σ(S_{i}) ∈ F(C_{2}^{3}) has no zero-sum sequence of length 2 and thus m ≤ s(C_{2}^{3})−1 = 8, which implies |π_{3}(S(∏_{i=1}^{m} S_{i})^{−1})| = |S| − 3m ≥ 16 + ε. These conditions imply that π_{3}(S(∏_{i=1}^{m} S_{i})^{−1}) contains at least 7 + ε distinct elements with multiplicity 2, which is just what we claimed.

2. We suppose that |S| ≥ 40+ε with ε ∈ {0, 1} and |S_{g}| ≥ 4 for some g ∈ C_{3}^{3}, and assume to the contrary that |supp(S_{g})| ≥ 3 − ε. Let T_{g} | S_{g} with |T_{g}| = 4 and |supp(T_{g})| ≥ 3 − ε. Let W = T_{g}^{−1}S. Since |W | ≥ 36 + ε = (18 + ε) + s(C_{3}^{3}) − 1, it follows that there exist W_{1} … W_{6+ε} | W such that σ(π_{3}(W_{i})) = 0 and |W_{i}| = 3 for each 1 ≤ i ≤ 6 + ε. Since W has no zero-sum subsequence of length 6, we have |{σ(W_{i}): 1 ≤ i ≤ 6 + ε}| = 6 + ε. Since π_{3}(T_{g}) = g^{4}, it is clear that σ(π_{3}(W′)) = 0 for every subsequence W′ | T_{g} of length 3.

However, since |supp(T_{g})| ≥ 3 − ε, we infer that there exist subsequences W′_{1}, …, W′_{3−ε} of T_{g} of length 3 with pairwise distinct sums. Thus, {σ(W′_{i}): 1 ≤ i ≤ 3 − ε} ∩ {σ(W_{i}): 1 ≤ i ≤ 6 + ε} ≠ ∅ and consequently S has a zero-sum subsequence of length 6, a contradiction. □

The following proposition, in particular, shows that (C2) holds for C_{6}^{3}. Moreover, it is a key tool in the proof of Theorem 1.8.

Proposition 6.3. Let S ∈ F(C_{6}^{3}) such that |S| = 40 and S has no zero-sum subsequence of length 6. Then there exists a squarefree T ∈ F(C_{6}^{3}) with |T | = 6 such that T^{5} | S. Moreover, at least one of the following statements holds:

1. for some g ∈ G, we have v_{g}(T^{−5}S) = 5.

2. for distinct g, g′ ∈ G, we have v_{g}(T^{−5}S) = v_{g′}(T^{−5}S) = 4.

3. for some h ∈ C_{3}^{3}, we have v_{h}(π_{3}(S)) ≥ 6.

Proof. Since |S| = 22 + s(C_{3}^{3}) − 1, we have S_{1} … S_{8} | S such that σ(π_{3}(S_{i})) = 0 and |S_{i}| = 3 for each i. Since S has no zero-sum subsequence of length 6, we have |{σ(S_{i}): 1 ≤ i ≤ 8}| = 8 and W = π_{3}(S(∏_{i=1}^{8} S_{i})^{−1}) has no zero-sum subsequence of length 3. Thus, |supp(W)| ≤ 9 and v_{g}(W) ≤ 2 for each g ∈ supp(W). Consequently, W = T^{2}rs where T is squarefree |T | = 7 and r, s ∉ supp(T). We distinguish two cases.

Case 1. r ≠ s. For each 1 ≤ j ≤ 8, we consider the sequence π_{3}(S_{j})W.

Subcase 1.1. π_{3}(S_{j}) is squarefree, say π_{3}(S_{j}) = h_{1}h_{2}h_{3}. If |supp(T) ∩ {h_{1}, h_{2}, h_{3}}| ≥ 2, say h_{1}h_{2} | T, then h_{1}^{3}h_{2}^{3} | π_{3}(S_{j})W, a contradiction to Lemma 6.2.1, since the product of 9 zero-sum sequence of length 3 would divide π_{3}(S). If |supp(T) ∩ {h_{1}, h_{2}, h_{3}}| = 1, say h_{1} | T, then h_{2}h_{3} ≠ rs, say h_{2} ∤ rs. By Lemma 6.1, the sequence h_{1}^{−1}T rsh_{2} has a zero-sum subsequence U of length 3, and consequently h_{1}^{3}U | π_{3}(S_{j})W, a contradiction. Thus, |supp(T) ∩ {h_{1}, h_{2}, h_{3}}| = 0. If rs ∤ h_{1}h_{2}h_{3}, say h_{1}, h_{2} ∉ {r, s}, then by Lemma 6.1 T rh_{1} and T sh_{2} both have a zero-sum subsequence of length 3, a contradiction. Therefore, π_{3}(S_{j}) = rs(−r − s).

Subcase 1.2. π_{3}(S_{j}) is not squarefree, and thus π_{3}(S_{j}) = h_{j}^{3} for some h_{j} ∈ C_{3}^{3}. If h_{j} ∤ W, then T rh_{j} and T sh_{j} both have a zero-sum subsequence of length 3, a contradiction. Thus h_{j} | W. We assert that |π_{3}^{−1}(h_{j}) ∩ supp(S)| = 1. The argument is similar to Lemma 6.2.2. Let S′ = S_{j}S(∏_{i=1}^{8} S_{i})^{−1}. First, we assert that |π_{3}^{−1}(h_{j}) ∩ supp(S′)| = 1. Assume this is not true. We note that v_{h_{j}}(π_{3}(S′)) ≥ 4. There exist subsequences U and U′ of S′ such that π_{3}(U) = π_{3}(U′) = h_{j}^{3} and σ(U) ≠ σ(U′). Since {σ(S_{i}): 1 ≤ i ≤ 8, i ≠ j}∩{σ(U), σ(U′)} ≠ ∅, we get a zero-sum subsequence of S of length 6, a contradiction. Now, we assume there exists some k ≠ j such that h_{j} | π_{3}(S_{k}), say g_{k} | S_{k} and π_{3}(g_{k}) = h_{j}. Let g_{j} | S_{j}, and define S′_{k} = g_{k}^{−1}g_{j}S_{k} and S′_{j} = g_{k}g_{j}^{−1}S_{j}. By the above argument |π_{3}^{−1}(h_{j}) ∩ supp(S′_{j})| = 1. This proves the assertion.

Thus for each 1 ≤ j ≤ 8, either we have π_{3}(S_{j}) = rs(−r − s) or we have π_{3}(S_{j}) = h_{j}^{3} and |π_{3}^{−1}(h_{j}) ∩ supp(S)| = 1. We note that we may assume that the former is the case at most once, since, if j ≠ j′ such that π_{3}(S_{j}) = π_{3}(S′_{j}) = rs(−r−s), then S_{j}S_{j′}W = r^{3}s^{3}T^{2}(−r−s)^{2} and we are in the situation of Case 2.

If none of the sequences π_{3}(S_{j}) is equal to rs(−r −s), we get S = (∏_{i=1}^{6+ε} g_{i}^{5})(∏_{i=7+ε}^{8} g_{i}^{4})R, where g_{i} ∈ C_{6}^{3}, ε ∈ {0, 1}, and |R| = 2 − ε. We note that supp(R) ∩ {g_{1}, …, g_{8}} = ∅ and thus the result holds with 1. or 2. according as ε equals 1 or 0. If one of the sequences π_{3}(S_{j}) is equal to rs(−r − s), we get S = (∏_{i=1}^{7} g_{i}^{5})R, where |R| = 5, and the result holds with 1.

Case 2. r = s. Let T_{0} = T r, then W = T_{0}^{2}. Again, we consider π_{3}(S_{j})W.

Subcase 2.1. π_{3}(S_{j}) is squarefree, say π_{3}(S_{j}) = h_{1}h_{2}h_{3}. By Lemma 6.1, there exists at most one k ∈ {1, 2, 3} such that the sequence T_{0}h_{k} has no zero-sum subsequence of length 3, a contradiction.

Subcase 2.2. π_{3}(S_{j}) = h_{j}^{3}. If h_{j} | T_{0}, then, as in Subcase 1.2, we get |π_{3}^{−1}(h_{j}) ∩ supp(S)| = 1. If h_{j} ∤ T_{0}, it follows that T_{0}h_{j} has no zero-sum subsequence of length 3, and by Lemma 6.1 h_{j} is thus uniquely determined by T_{0}.

Thus, either we have π_{3}(S_{j}) = h_{0}^{3} for some h_{0} ∈ C_{3}^{3} that is independent of j, or π_{3}(S_{j}) = h_{j}^{3} and |π_{3}^{−1}(h_{j}) ∩ supp(S)| = 1. Let n = |{j: π_{3}(S_{j}) = h_{0}^{3}}|. We note that n ≤ 3, since by Lemma 6.2.2 |π_{3}^{−1}(h_{0}) ∩ supp(S)| ≤ 2 and clearly every element has multiplicity at most 5 in S. If n = 0, we get S = (∏_{i=1}^{8} g_{i}^{5}). If n = 1, we get S = (∏_{i=1}^{7} g_{i}^{5})R where |R| = 5. If n = 2, we get S = (∏_{i=1}^{6} g_{i}^{5})R where |R| = 10. If n = 3, we get S = (∏_{i=1}^{5} g_{i}^{5})g_{6}^{5}g_{7}^{4}R where |R| = 6. Thus, for 0 ≤ n ≤ 1 the result holds with 1. and for 2 ≤ n ≤ 3 it holds with 3. □

In the next result, we show that for even longer sequences over C_{6}^{3} without a zero-sum subsequence of length 6 we would obtain very precise structural results. However, actually we use this result to prove that such sequences do not exist.

Proposition 6.4. Let S ∈ F(C_{6}^{3}) such that |S| = s(C_{6}^{3}) − 1 and S has no zero-sum subsequence of length 6. If |S| ≥ 41, then there exists a T ∈ F(C_{6}^{3}) with |T | = 8 such that T^{5} | S.

Proof. Obviously, v_{g}(S) ≤ 5 for each g ∈ G. For U ∈ F(G), let m(U) = |{g ∈ G: v_{g}(U) = 5}|. We have to show that m(S) = 8. We assume to the contrary m(S) ≤ 7.

If |S| ≥ 42, then there exists a subsequence S′ of S of length 40 such that m(S′) ≤ 5, a contradiction to Proposition 6.3. Thus, we assume |S| = 41. Let S′ | S of length 40 such that m(S′) = 6. By Lemma 6.2.2 we know that v_{h}(π_{3}(S)) ≤ 5 for each h ∈ C_{3}^{3}. Thus by Proposition 6.3 v_{g}(S′) = v_{g′}(S′) = 4 for distinct g, g′ ∈ C_{6}^{3}. Consequently, v_{g}(S) or v_{g′}(S) is equal to 4, a contradiction to Theorem 1.3.1. □

Finally, we are ready to prove Theorem 1.8.

Proof of Theorem 1.8. By Theorem 2.2.2 we known that s(C_{n}^{3}) ≥ 8n − 7. We prove that s(C_{n}^{3}) ≤ 8n − 7. In view of Lemma 1.6, it suffices to prove the result for a = 1; the general case follows by induction.

Thus, we have to prove that s(C_{6}^{3}) ≤ 41. We assume to the contrary that s(C_{6}^{3}) ≥ 42. Let S ∈ F(C_{6}^{3}) such that |S| = s(C_{6}^{3})−1 and S has no zero-sum subsequence of length 6. By Proposition 6.4 we have S = T^{5}R with |T | = 8 and |R| ≥ 1. Let g_{0} | R and let T = ∏_{i=1}^{8} g_{i}. Since π_{3}(g_{i}^{3}) is a zero-sum subsequence of π_{3}(S) for each 1 ≤ i ≤ 8, it follows by Lemma 6.2.1 that π_{3}(g_{0}T^{2}) has no zero-sum subsequence of length 3, in particular supp(π_{3}(g_{0}T^{2})) = {π_{3}(g_{i}): 0 ≤ i ≤ 8} is a cap of cardinality 9. We note that σ(g_{i}^{3}) = 3π_{2}(g_{i}) = π_{2}(g_{i}). Thus |{π_{2}(g_{i}): 1 ≤ i ≤ 8}| = 8. Let 1 ≤ j ≤ 8 such that π_{2}(g_{0}) = π_{2}(g_{j}).

We consider the sequence W = (∏_{i=1}^{8} σ(g_{i}^{2})^{2})σ(g_{j}g_{0}) ∈ F(C_{3}^{3}). Since S has no zero-sum subsequence of length 6, W has no zero-sum subsequence of length 3. Thus, we have σ(g_{j}g_{0}) ∉ {σ(g_{i}^{2}): 1 ≤ i ≤ 8} and {σ(g_{j}g_{0})} ∪ {σ(g_{i}^{2}): 1 ≤ i ≤ 8} is a cap in C_{3}^{3} of cardinality 9. We observe that σ(g_{i}^{2}) = −π_{3}(g_{i}) and thus by Lemma 6.1 we have σ(g_{j}g_{0}) = −π_{3}(g_{0}). However, since σ(g_{j}g_{0}) = π_{3}(g_{j}) + π_{3}(g_{0}), this implies π_{3}(g_{j}) = −2π_{3}(g_{0}) = π_{3}(g_{0}), a contradiction.

Since s(C_{n}^{3}) − n + 1 ≥ η(C_{n}^{3}) ≥ 7n − 6, the result follows. □

Acknowledgments

This work has been supported partially by NSFC with grant no. 10271080. This work was done while the last author was visiting the Center for Combinatorics, Nankai University, Tianjin. He is thankful to the center for providing excellent atmosphere for research and their hospitality. The penultimate author is supported by the FWF (P18779-N13).

References

1. N. Alon and M. Dubiner. A lattice point problem and additive number theory. Combinatorica, 15(3):301–309, 1995.

2. N. Alon, M. B. Nathanson, and I. Ruzsa. Adding distinct congruence classes modulo a prime. Amer. Math. Monthly, 102(3):250–255, 1995.

3. N. Alon, M. B. Nathanson, and I. Ruzsa. The polynomial method and restricted sums of congruence classes. J. Number Theory, 56(2):404–417, 1996.

4. J. Bierbrauer. Large caps. J. Geom., 76:16–51, 2003.

5. R. Chi, S. Ding, W. Gao, A. Geroldinger, and W. A. Schmid. On zero-sum subsequences of restricted size. IV. Acta Math. Hungar., 107(4):337–344, 2005.

6. J. A. Dias da Silva and Y. ould Hamidoune. Cyclic spaces for Grassmann derivatives and additive theory. Bull. London Math. Soc., 26(2):140–146, 1994.

7. Y. Edel, C. Elsholtz, A. Geroldinger, S. Kubertin, and L. Rackham. Zero-sum problems in finite abelian groups and affine caps. Quart. J. Math. Oxford Ser. (2), to appear. Preprint available at:

http://www.ma.rhul.ac.uk/~elsholtz/

8. C. Elsholtz. Lower bounds for multidimensional zero sums. Combinatorica, 24(3):351–358, 2004.

9. P. Erdős, A. Ginzburg, and A. Ziv. Theorem in the additive number theory. Bull. Res. Council Israel, 10F:41–43, 1961.

10. P. Erdős and H. Heilbronn. On the addition of residue classes mod p. Acta Arith., 9:149–159, 1964.

11. L. Gallardo, G. Grekos, L. Habsieger, F. Hennecart, B. Landreau, and A. Plagne. Restricted addition in ℤ/nℤ and an application to the Erdős-Ginzburg-Ziv problem. J. London Math. Soc. (2), 65(3):513– 523, 2002.

12. W. D. Gao. An addition theorem for finite cyclic groups. Discrete Math., 163(1-3):257–265, 1997.

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

14. W. D. Gao. On zero-sum subsequences of restricted size. II. Discrete Math., 271(1-3):51–59, 2003.

15. W. D. Gao and A. Geroldinger. On zero-sum sequences in ℤ/nℤ ⊕ ℤ/nℤ. Integers, 3:A8, 45 pp. (electronic), 2003.

16. W. D. Gao and A. Geroldinger. Zero-sum problems in finite abelian groups: a survey. Expo. Math., 24(4):337–369, 2006.

17. W. D. Gao, A. Panigrahi, and R. Thangadurai. On the structure of p-zero-sum free sequences and its application to a variant of Erdös–Ginzburg–Ziv theorem. Proc. Indian Acad. Sci. Math. Sci., 115(1):67–77, 2005.

18. W. D. Gao and R. Thangadurai. On the structure of sequences with forbidden zero-sum subsequences. Colloq. Math., 98(2):213–222, 2003.

19. W. D. Gao and R. Thangadurai. A variant of Kemnitz conjecture. J. Combin. Theory Ser. A, 107(1):69–86, 2004.

20. W. D. Gao and Y. X. Yang. Note on a combinatorial constant. J. Math. Res. Exposition, 17(1):139– 140, 1997.

21. A. Geroldinger and F. Halter-Koch. Non-unique factorizations. Algebraic, Combinatorial and Analytic Theory. Chapman & Hall/CRC, 2006.

22. H. Harborth. Ein Extremalproblem für Gitterpunkte. J. Reine Angew. Math., 262/263:356–360, 1973.

23. J. W. P. Hirschfeld. Finite projective spaces of three dimensions. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, 1985.

24. A. Kemnitz. On a lattice point problem. Ars Combin., 16(B):151–160, 1983.

25. M. B. Nathanson. Additive number theory. Inverse problems and the geometry of sumsets., volume 165 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1996.

26. C. Reiher. On Kemnitz’ conjecture concerning lattice points in the plane. Ramanujan J., 13(1-3):333–337, 2007.

27. W. A. Schmid and J. J. Zhuang. On short zero-sum subsequences over p-groups. Ars Combin., to appear. Preprint available at:

http://www.uni-graz.at/~wschmid/personal/research.html

28. B. Sury and R. Thangadurai. Gao’s conjecture on zero-sum sequences. Proc. Indian Acad. Sci. Math. Sci., 112(3):399–414, 2002.

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