A generalization of Kneser’s Addition Theorem

Matt DeVos, Luis Goddyn^{∗}, and Bojan Mohar^{†}^{‡}

Department of Mathematics

Simon Fraser University

Burnaby, B.C. V5A 1S6

           email: [mdevos,goddyn,mohar]@sfu.ca

October 17, 2008

Abstract

Let A = (A_{1}, …, A_{m}) be a sequence of finite subsets from an additive abelian group G. Let Σ^{ℓ}(A) denote the set of all group elements representable as a sum of ℓ elements from distinct terms of A, and set H = stab(Σ^{ℓ}(A)) = {g ∈ G : g + Σ^{ℓ}(A) = Σ^{ℓ}(A)}. Our main theorem is the following lower bound:

|Σ^{ℓ}(A)| ≥ |H|(1 − ℓ + ∑_{Q∈G/H} min{ℓ, |{i ∈ {1, …, m} : A_{i} ∩ Q ≠ ∅}|}).

In the special case when m = ℓ = 2, this is equivalent to Kneser’s addition theorem, and indeed we obtain a new proof of this result. The special case when every A_{i} has size one is a new result concerning subsequence sums which extends some recent work of Bollobás-Leader, Hamidoune, Hamidoune-Ordaz-Ortuño, Grynkiewicz, and Gao, and resolves two recent conjectures of Gao, Thangadurai, and Zhuang.

∗Supported by a Canada NSERC Discovery Grant.

†Supported in part by Slovenian Research Grant P1–0297 and by Canadian NSERC Discovery Grant and by the CRC program.

‡On leave from: IMFM & FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia.

1 Introduction

Throughout we shall assume that G is a (possibly infinite) additive abelian group. Let A, B ⊆ G and g ∈ G. We define the sumset A + B = {a + b : a ∈ A, b ∈ B} and we define g + A = A + g = {g} + A. Any set of the form g + A is called a shift of A. We define the stabilizer of A to be stab(A) = {g ∈ G | g + A = A}. Note that stab(A) ≤ G. The starting point for our subject is the following classical result of Cauchy [5] and Davenport [6] (see also [17]), which gives a lower bound on |A + B| for groups of prime order. Here we let ℤ_{n} = ℤ/nℤ.

Theorem 1.1 (Cauchy-Davenport) If p is prime and A, B ⊆ ℤ_{p} are nonempty, then |A + B| ≥ min{p, |A| + |B| − 1}.

This theorem was generalized by Kneser [16] to all abelian groups as follows.

Theorem 1.2 (Kneser) If A, B ⊆ G are finite and nonempty and H = stab(A + B), then |A + B| ≥ |A + H| + |B + H| − |H|.

Our principal subject matter is sequences of sets. If A = (A_{1}, A_{2}, …, A_{m}) is a sequence of finite subsets of G, and ℓ ≤ m, we define

Σ^{ℓ}(A) = {a_{i_{1}} + ⋯ + a_{i_{ℓ}} : 1 ≤ i_{1} < ⋯ < i_{ℓ} ≤ m and a_{i_{j}} ∈ A_{i_{j}} for every 1 ≤ j ≤ ℓ}.

So Σ^{ℓ}(A) is the set of all elements which can be represented as a sum of ℓ terms from distinct members of A. The following is our main result.

Theorem 1.3 Let A = (A_{1}, …, A_{m}) be a sequence of finite subsets of G, let ℓ ≤ m, and let H = stab(Σ^{ℓ}(A)). If Σ^{ℓ}(A) is nonempty, then

|Σ^{ℓ}(A)| ≥ |H|(1 − ℓ + ∑_{Q∈G/H} min {ℓ, |{i ∈ {1, …, m} : A_{i} ∩ Q ≠ ∅}|}).

In the special case when m = ℓ = 2, our result is equivalent to Kneser’s Theorem, and our argument gives a new proof of this theorem. In fact, this new proof was found by the first author somewhat earlier than this more general argument, and will be published elsewhere.

A rich subject closely related to sumsets is the study of subsequence sums. Given a sequence a = (a_{1}, a_{2}, …, a_{m}) of elements of G, we define

Σ^{ℓ}(a) = {a_{i_{1}} + a_{i_{2}} + ⋯ + a_{i_{ℓ}} : 1 ≤ i_{1} < i_{2} < ⋯ < i_{ℓ} ≤ m}.

So Σ^{ℓ}(a) is the set of all group elements representable as a sum of an ℓ-term subsequence of a. The study of subsequence sums features a wide expanse of interconnected results. In the remainder of the introduction, we shall take a tour of some of these theorems, and then move on to some related results on graphs and matroids. Our tour begins with the following classic theorem of Erdős, Ginzburg, and Ziv [7].

Theorem 1.4 (Erdős, Ginzburg, Ziv) If |G| = ℓ and a = (a_{1}, a_{2}, …, a_{2ℓ−1}) is a sequence of elements from G, then 0 ∈ Σ^{ℓ}(a).

This theorem has recently been generalized in a number of different directions, some of which we will discuss shortly. However, first let us point out that the special case of our theorem when each A_{i} has size one gives a natural lower bound for subsequence sums. This is stated below as Corollary 1.5. This corollary may be used to derive Theorem 1.4, so we may view this as another generalization of Erdős-Ginzburg-Ziv. However, as we shall show, this corollary is strong enough to imply several other generalizations of it. See Figure 1.

Corollary 1.5 If a = (a_{1}, a_{2}, …, a_{m}) is a sequence of elements of G, ℓ ≤ m, and H = stab(Σ^{ℓ}(a)), then

|Σ^{ℓ}(a)| ≥ |H|(1 − ℓ + ∑_{Q∈G/H} min {ℓ, |{i ∈ {1, …, m} : a_{i} ∈ Q}|}).  (1)

Note that if a = (a_{1}, …, a_{m}) and ℓ ≤ m, then it follows immediately that Σ^{m−ℓ}(a) = (∑_{i=1}^{m} a_{i}) − Σ^{ℓ}(a). Thus, the sets Σ^{m−ℓ}(a) and −Σ^{ℓ}(a) are shifts of one another, and in particular, these two sets have the same size and the same stabilizer. As such, our theorem may be applied in two different ways to a given sequence a, and generally these two bounds will be different.

Let us remark that Corollary 1.5 is a slight strengthening of a result in [12] which follows from Grynkiewicz’s “partition analogue of the Cauchy-Davenport Theorem” (hereafter called Grynkiewicz’s partition theorem). This theorem of Grynkiewicz concerns a refinement of a partition of a sequence into sets, and we shall not state it in full, but a key consequence of it is as follows. If a = (a_{1}, …, a_{m}) is a sequence of elements from G, then there exists a subset C ⊆ Σ^{ℓ}(a) and a subgroup H ≤ stab(C) for which inequality (1) holds with the left hand side replaced by |C|.

Now let us commence with our tour with some generalizations of the Erdős-Ginzburg-Ziv Theorem. In this theorem, the authors study only sequences of length 2|G| − 1 and subsequences of length |G|. Perhaps the most obvious attempt at generalization would be to consider what happens when we consider different length sequences and subsequences (although it is not obvious how the conclusion should be modified). Indeed, Bollobás and Leader [3] found a nice generalization of Theorem 1.4 by considering subsequences of length |G| from an arbitrary sequence. Hamidoune [14] further generalized this with the following theorem, where subsequences of arbitrary length are considered. Here ℕ denotes the set of nonnegative integers.

Theorem 1.6 (Hamidoune) Let a = (a_{1}, …, a_{m}) be a sequence of elements from G, let ℓ ∈ ℕ, and assume 1 ≤ ℓ ≤ m ≤ 2ℓ − 1. Then one of the following holds:

(i) |Σ^{ℓ}(a)| ≥ m − ℓ + 1.

(ii) There exists i ∈ {1, …, m}, so that ℓa_{i} ∈ Σ^{ℓ}(a).

Both Grynkiewicz’s partition theorem and our Corollary 1.5 imply Theorem 1.6. To derive Theorem 1.6 from Corollary 1.5, note that if there is an H-coset Q ∈ G/H so that |{1 ≤ i ≤ m : a_{i} ∈ Q}| ≥ ℓ, then Σ^{ℓ}(a) contains the H-coset ℓQ, so ℓa_{i} ∈ Σ^{ℓ}(a) for every 1 ≤ i ≤ m with a_{i} ∈ Q. Otherwise, our bound immediately implies |Σ^{ℓ}(a)| ≥ m − ℓ + 1.

Perhaps the most obvious way to limit the size of Σ^{ℓ}(a) is to choose a so that all or almost all of its entries are the same. Accordingly, a number of authors have studied the effect of limiting the maximum multiplicity

ρ(a) = max_{g∈G} |{i ∈ {1, …, m} : a_{i} = g}|

among elements in a. Next we state a two-part conjecture due to Gao, Thangadurai, and Zhuang (Conjectures 1 and 2 in [11]) on this theme. We use the notation Σ(a) = ∪_{i=0}^{m}Σ^{i}(a).

Conjecture 1.7 (Gao, Thangadurai, Zhuang) Let ℓ > 1 be an integer, let p be the smallest prime divisor of ℓ, and let a = (a_{1}, a_{2}, …, a_{m}) be a sequence of elements from ℤ_{ℓ}. If m ≥ ℓ + \frac{ℓ}{p} − 1 and ρ(a) ≤ m − ℓ, then both of the following hold.

(1) 0 ∈ Σ^{ℓ}(a).

(2) If 0 appears exactly m − ℓ times in a, then Σ^{m−ℓ}(a) = Σ(a).

The proposers prove this conjecture in the case where ℓ is a prime power. More recently, Cao [4] verified part (1) when ℓ is the product of two prime powers, and Gao [10] proved a slightly weaker form of part (1) for general ℓ. Conjecture 1.7 follows from our next corollary (proved in Section 3).

Corollary 1.8 Let G be a nontrivial finite abelian group and let p be the smallest prime divisor of |G|. Let a = (a_{1}, …, a_{m}) be a sequence of elements from G, let ℓ ≤ m and set H = stab(Σ^{ℓ}(a)). If m ≥ ℓ + \frac{ℓ}{p} − 1 and ρ(a) ≤ m − ℓ, then one of the following holds.

(i) |Σ^{ℓ}(a)| ≥ ℓ.

(ii) H ≠ {0} and there exists Q ∈ G/H so that |{i ∈ {1, …, m} : a_{i} ∈ Q}| > ℓ.

Let us pause to show that the above corollary implies Conjecture 1.7. With the assumptions of Conjecture 1.7, both parts (1) and (2) follow from Corollary 1.8 if conclusion (i) holds (as then Σ^{ℓ}(a) = Σ^{m−ℓ}(a) = ℤ_{ℓ}), so we may assume that (ii) holds. Then H = ℓQ ⊆ Σ^{ℓ}(a) and part (1) follows. For part (2), note that since 0 appears m − ℓ times, Q must equal H, so the image of a under the canonical quotient mapping from ℤ_{ℓ} to ℤ_{ℓ}/H, call it b, is a sequence with fewer than m − ℓ nonzero terms. Thus Σ^{m−ℓ}(b) = Σ(b). It follows from this that Σ^{m−ℓ}(a) = Σ(a).

Bialostocki and Dierker [2] generalized the Erdős-Ginzburg-Ziv theorem by studying sequences of length 2|G| − 2 and characterizing those without zero-sum subsequences of length |G|. They prove that (for nontrivial groups), such sequences can only occur when G is cyclic, and the sequence contains exactly two group elements, each occurring exactly |G| − 1 times. Stated another way, every sequence of length 2|G|−2 with at least three distinct terms must have a zero-sum subsequence of length |G|. Indeed, the assumption that a sequence has many distinct terms also tends to increase the number of distinct subsequence sums, and a number of authors have studied this phenomenon. Next we state a theorem of Grynkiewicz [13] which exploits a distinctness assumption. This theorem resolved a conjecture of Hamidoune [14], and extended some earlier results of Hamidoune [14], and Hamidoune, Ordaz, and Ortuño [15], in addition to the Bialostocki-Dierker theorem mentioned above.

Theorem 1.9 (Grynkiewicz) Let G be an abelian group of order ℓ and let a = (a_{1}, …, a_{m}) be a sequence of elements from G with m > ℓ. If a contains at least k distinct terms and ρ(a) ≤ ℓ − k + 2, then one of the following holds.

(i) |Σ^{ℓ}(a)| ≥ min{ℓ, m − ℓ + k − 1}.

(ii) There is a nontrivial subgroup H ≤ stab(Σ^{ℓ}(a)) with H ⊆ Σ^{ℓ}(a), there is an H-coset Q which contains all but at most t terms of a where t ≤ min\{⌊\frac{m−ℓ+k−2}{|H|}⌋ − 1, [G : H] − 2\} and |Σ^{ℓ}(a)| ≥ (t + 1)|H|.

By setting k = 3 and m = 2ℓ − 2 and applying the above theorem, we deduce that 0 ∈ Σ^{ℓ}(a). This is the heart of the aforementioned result of Bialostocki-Dierker. Theorem 1.9 appears to be close to the truth for small values of k, but we do not know in general when these lower bounds are tight. Our Corollary 1.5 can also be used to derive Theorem 1.9. Indeed, it implies the following stronger result where the dependence on the order of the group has been removed.

Corollary 1.10 Let m, k, ℓ ∈ ℕ with ℓ < m, let a = (a_{1}, …, a_{m}) be a sequence of elements from G with H = stab(Σ^{ℓ}(a)). If a contains at least k distinct terms, and ρ(a) ≤ ℓ − k + 2, then one of the following holds.

(i) |Σ^{ℓ}(a)| ≥ min{ℓ + 1, m − ℓ + k − 1} .

(ii) H ≠ {0}, there exists Q ∈ G/H so that |{i ∈ {1, …, m} : a_{i} ∈ Q}| > ℓ.

Next, let us indicate how the above corollary implies Theorem 1.9. Given the assumptions of Theorem 1.9 and applying Corollary 1.10, we are done immediately if conclusion (i) holds, so we may assume that conclusion (ii) holds. Assuming further that |Σ^{ℓ}(a)| < ℓ (otherwise we are done) the bound from Corollary 1.5 shows that Q is the only H-coset containing ≥ ℓ terms of a, and further, setting t = |{1 ≤ i ≤ m : a_{i} ∉ Q}| we have |Σ^{ℓ}(a)| ≥ |H|(t + 1).

Assuming |Σ^{ℓ}(a)| < min{ℓ, m − ℓ + k − 1} (otherwise we are done), this yields the upper bound on t given in Theorem 1.9.

Finally, we introduce a fundamental result of Gao [9]. For every finite abelian group G, the Davenport constant of G, denoted s(G), is the smallest positive integer k so that every sequence of elements of G with length ≥ k has a nontrivial subsequence which sums to 0. Similarly, we define s′(G) to be the smallest positive integer k so that every sequence of elements of G with length ≥ k has a subsequence of length |G| which sums to 0. So the Erdős-Ginzburg-Ziv theorem asserts that s′(G) ≤ 2|G| − 1 for every finite abelian group G. It is an easy exercise to show that s(G) ≤ |G| for every G. In light of this, the following theorem of Gao [9] may also be viewed as a generalization of Theorem 1.4.

Theorem 1.11 (Gao) s′(G) = s(G) + |G| − 1 for every finite abelian group G.

In the third section of our paper we will use Corollary 1.5 to obtain a new proof of Gao’s Theorem. Although our proof of Gao’s Theorem is no shorter than existing proofs, we have included it since it follows naturally from our result in a manner similar to that of the other generalizations of Erdős-Ginzburg-Ziv.

Instead of considering all possible ℓ-element subsequences of a given sequence a, one might introduce some additional structure on a and consider only certain special types of subsequences. Bialostocki and Dierker [1] did this by introducing an underlying geometry in the form of a graph. Let X be a graph and let w : E(X) → G be a map. We define w(X) = {∑_{e∈E(T)} w(e) : T is a spanning tree of X}.

Theorem 1.12 (Bialostocki-Dierker) Let p be prime, let X be a complete graph on p + 1 vertices, and let w : E(X) → ℤ_{p} be a map. Then 0 ∈ w(X).

This theorem suggested a rather different type of zero-sum problem, and was soon extended in a number of different directions. Füredi and Kleitman [8] proved that a similar result holds for arbitrary (even nonabelian) groups. More precisely, they prove that for every multiplicative group G of order n, and every edge-labeling of the complete graph on n + 1 vertices with elements of G, there exists a spanning tree whose edges may be ordered so that the product of the labels (in this order) is the identity. Schrijver and Seymour [19] generalized the Bialostocki-Dierker theorem to hypergraphs, thus obtaining a new proof of the Füredi-Kleitman theorem for abelian groups.

Perhaps even more excitingly, Schrijver and Seymour [18] generalized the underlying geometry further to matroids. If M is a matroid on E, and w : E → G is a map, we define w(M) = {∑_{b∈B} w(b) : B is a base of M}.

Conjecture 1.13 (Schrijver-Seymour) Let M be a matroid on E with rank function rk. Let w : E → G where G is an abelian group. If H = stab(w(M)), then

|w(M)| ≥ |H|(1 − rk(M) + ∑_{Q∈G/H} rk(w^{−1}(Q))).

We consider this conjecture to be very important. Indeed, our main theorem is a very special case of it. Corollary 1.5 is equivalent to the above conjecture for uniform matroids. Our main theorem is equivalent to the above conjecture for matroids obtained from uniform matroids by adding parallel elements.

Schrijver and Seymour [18] proved their conjecture in the special case when |G| is prime. In their paper, they state “we have convinced ourselves that it is true when |G| is a power of a prime, or the product of two primes. But this last, if it is correct, will appear in a later paper.” Unfortunately, this later paper was never written. In the final section of our paper, we prove their conjecture for two special types of groups.

Theorem 1.14 Conjecture 1.13 holds whenever |G| = pq for primes p, q or G ≅ ℤ_{p^{n}} for a prime p and a positive integer n.

There is a unifying framework for some above-mentioned results. If a matroid M of rank n has two disjoint cocircuits and w: E(M) → {0, 1} ⊆ ℤ_{n} is a weighting whose support is one of these cocircuits, then 0 ∉ w(M). Schrijver and Seymour [18] (essentially) observe that Conjecture 1.13 implies a converse to this statement.

Proposition 1.15 (Schrijver-Seymour) Let G be an abelian group. Let M be a matroid of rank |G| in which every two cocircuits meet. If Conjecture 1.13 holds for G and the dual matroid M^{∗}, then for any map w : E(M) → G we have 0 ∈ w(M).

We have already seen two matroids to which this proposition applies. When M is the uniform matroid with rank |G| on 2|G|−1 points, we obtain the Erdős-Ginzburg-Ziv theorem, since M^{∗} is uniform and satisfies Conjecture 1.13 by Corollary 1.5. When M is a complete graph on |G| + 1 vertices and |G| is prime, we obtain the Bialostocki-Dierker theorem, as was observed in [18]. Both of these matroids are minimal in the sense that deleting any element results in a matroid with two disjoint cocircuits. It appears hopeless to characterize such minimal matroids. For example, M is a dual-paving matroid if all its cocircuits have size at least |M| − rk(M). Such matroids are easily constructed by modifying a uniform matroid, and they form a very rich class (it is suspected [20] that most matroids of a given size are paving matroids). When constructing a dual-paving matroid M of size 2 rk(M) or 2 rk(M) + 1, it is easy to arrange that M is minimal with respect to not containing disjoint cocircuits. This shows the existence of a large class of minimal matroids M to which we can apply Theorem 1.14; if G is a cyclic group and rk(M) = |G| is a prime power or the product of two primes, then 0 ∈ w(M) for every w: M → G.

Figure 1: Implications among statements in in Section 1. New results have bold borders.

The remainder of this paper is organized as follows. We prove our main theorem in the next section. We prove three consequences of the main theorem for sequences (Corollaries 1.8, 1.10, and Theorem 1.11) in Section 3. Then, in the final section, we prove our matroidal result, Theorem 1.14.

2 Main Theorem

The goal of this section is to prove our main theorem. In fact, for the purpose of our induction, we will prove a slightly stronger statement. We continue with some further notation.

If K ≤ G and ℓ ∈ ℕ, we call a map μ : G/K → ℕ a K-pattern of weight ℓ if ∑_{Q∈G/K} μ(Q) = ℓ. If A = (A_{1}, A_{2}, …, A_{m}) is a sequence of finite subsets of G and μ is a K-pattern of weight ℓ, we call a sequence (b_{1}, b_{2}, …, b_{ℓ}) μ-feasible (in A) if there exist 1 ≤ i_{1} < i_{2} < ⋯ < i_{ℓ} ≤ m which satisfy the following properties:

• b_{j} ∈ A_{i_{j}} for every 1 ≤ j ≤ ℓ.

• μ(Q) = |{j ∈ {1, …, ℓ} : b_{j} ∈ Q}| for every Q ∈ G/K.

Expanding our earlier notation, we now make the following definition.

Σ^{μ}(A) = {b_{1} + ⋯ + b_{ℓ} : (b_{1}, b_{2}, …, b_{ℓ}) is μ-feasible in A}.

For every ℓ ∈ ℕ and H ≤ G we define

Θ_{H}^{ℓ}(A) = ∑_{Q∈G/H} min{ℓ, |{1 ≤ i ≤ m : A_{i} ∩ Q ≠ ∅}|}.

We are now ready to state our main result in its most general form.

Theorem 2.1 Let A = (A_{1}, …, A_{m}) be a sequence of finite subsets of G, let K ≤ G and let μ : G/K → ℕ be a K-pattern of weight ℓ. If Σ^{μ}(A) ≠ ∅ and stab(Σ^{μ}(A)) = J, then

|Σ^{μ}(A)| ≥ |J|(Θ_{J}^{ℓ}(A) − ℓ + 1) − |K|(Θ_{K}^{ℓ}(A) − ℓ).

Before we prove Theorem 2.1, let us show that it implies our main theorem. To see this, let A = (A_{1}, …, A_{m}) be a sequence of subsets of G and let ℓ be a positive integer. Now set K = G and define μ : G/K → ℕ by the rule μ(G) = ℓ. Then Σ^{ℓ}(A) = Σ^{μ}(A) and Θ_{K}^{ℓ}(A) = ℓ. Now it is obvious that the bound in Theorem 2.1 implies Theorem 1.3. In particular, Theorem 2.1 implies Kneser’s Theorem. In our proof, we will argue by considering a counterexample which is in some sense minimal, and we will use the fact that our main theorem (and hence Kneser’s Theorem) hold for all smaller examples.

Proof: We shall assume (for a contradiction) that the theorem is false and choose a counterexample A = (A_{1}, …, A_{m}) so that

(i) |Σ^{μ}(A)| is minimum.

(ii) ∑_{i=1}^{m} |A_{i}| is minimum (subject to (i)).

(iii) ∑_{i=1}^{m} |A_{i}|^{2} is maximum (subject to (i),(ii)).

(iv) m is minimum (subject to (i), (ii), (iii)).

It follows from (iv) that A_{i} is nonempty for every 1 ≤ i ≤ m. Next we will show that our assumptions imply J = {0}. It is immediate that Σ^{μ}(A) is contained in the K-coset ∑_{Q∈G/K} μ(Q)Q, so in particular J ≤ K. Suppose (for a contradiction) that J ≠ {0} and let ϕ : G → G/J be the canonical homomorphism. Let A_{ϕ} = (ϕ(A_{1}), …, ϕ(A_{m})), let K_{ϕ} = ϕ(K) and let μ_{ϕ} : (G/J)/K_{ϕ} → ℕ be given by the rule μ_{ϕ}(Q) = μ(∪Q) for every Q ∈ (G/J)/K_{ϕ}. Then Σ^{μ_{ϕ}}(A_{ϕ}) = ϕ(Σ^{μ}(A)) has trivial stabilizer, so by the minimality of our counterexample we have

|Σ^{μ}(A)| = |J| · |Σ^{μ_{ϕ}}(A_{ϕ})|
≥ |J| (Θ_{{0}}^{ℓ}(A_{ϕ}) − ℓ + 1 − |K_{ϕ}|(Θ_{K_{ϕ}}^{ℓ}(A_{ϕ}) − ℓ))
= |J|(Θ_{J}^{ℓ}(A) − ℓ + 1) − |K|(Θ_{K}^{ℓ}(A) − ℓ).

This contradiction implies that J = {0} as desired.

The next step in our proof is to handle one rather special case, when ℓ = m, and there exists 1 ≤ j ≤ m so that |A_{j} + K| > |K|. Although the induction we will apply here is different than that used in the general case, the remainder of the argument is similar (but much easier in this special case). The idea is to iteratively build nested subsets of Σ^{μ}(A) with increasing size and decreasing stabilizers. We will call the subsets produced in this process “convergents” – a term borrowed from approximations to continued fractions. Define a set C ⊆ Σ^{μ}(A) with H = stab(C) to be a convergent if it satisfies the following property

|C| ≥ |H|(Θ_{H}^{ℓ}(A) − ℓ + 1) − |K|(Θ_{K}^{ℓ}(A) − ℓ).

As in the general argument, we will first show (using an inductive application of our theorem) that a convergent exists. Choose a μ-feasible sequence (a_{1}, …, a_{m}) and for every 1 ≤ i ≤ m let A′_{i} = A_{i} ∩ (a_{i} + K). Then set C_{0} = ∑_{i=1}^{m} A′_{i} and H_{0} = stab(C_{0}). Note that |A′_{j}| < |A_{j}|, so we can apply our theorem to the sequence A′_{1}, A′_{2}, …, A′_{m} to find that |C_{0}| ≥ ∑_{i=1}^{m} |A′_{i} + H_{0}| − (m − 1)|H_{0}|. Now we have

|K|(Θ_{K}^{m}(A) − m) = ∑_{i=1}^{m} |(A_{i} \ A′_{i}) + K|
≥ ∑_{i=1}^{m} |(A_{i} \ A′_{i}) + H_{0}|
= |H_{0}|(Θ_{H_{0}}^{m}(A)) − ∑_{i=1}^{m} |A′_{i} + H_{0}|.

Thus, |C_{0}| ≥ ∑_{i=1}^{m} |A′_{i} + H_{0}| − (m − 1)|H_{0}| ≥ |H_{0}|(1 − m + Θ_{H_{0}}^{m}(A)) − |K|(Θ_{K}^{m}(A) − m). It follows from this that C_{0} is a convergent, and we may now choose a convergent C with H = stab(C) minimal. If H = {0}, then since Σ^{μ}(A) ⊇ C our proof is complete. Thus, we may assume that H is nontrivial.

Since J = {0}, we may choose a μ-feasible sequence (b_{1}, b_{2}, …, b_{m}) for which ∑_{i=1}^{m} b_{i} + H ⊈ Σ^{μ}(A). Let ν : G/H → ℕ be the H-pattern of weight ℓ = m given by the rule ν(R) = |{1 ≤ i ≤ m : b_{i} + H = R}|. Now set D = Σ^{ν}(A) and H′ = stab(D), and note that stab(C ∪ D) = H′ < H since D is properly included in some H-coset disjoint from C. By the assumption that C is a convergent and an application of our bound to D = Σ^{ν}(A) we have

|C ∪ D| = |C| + |D|
≥ |H|(Θ_{H}^{ℓ}(A) − ℓ + 1) − |K|(Θ_{K}^{ℓ}(A) − ℓ)
+ |H′|(Θ_{H′}^{ℓ}(A) − ℓ + 1) − |H|(Θ_{H}^{ℓ}(A) − ℓ)
> |H′|(Θ_{H′}^{ℓ}(A) − ℓ + 1) − |K|(Θ_{K}^{ℓ}(A) − ℓ).

It follows that C ∪ D is a convergent with stabilizer H′ < H contradicting our choice of C. This completes the proof of this special case.

For the general argument, we shall arrange (after some adjusting) that our first two sets A_{1} and A_{2} satisfy A_{1} \ A_{2} ≠ ∅ and A_{2} \ A_{1} ≠ ∅. Further, we will arrange that the sequence A′ = (A_{1}∩A_{2}, A_{1}∪A_{2}, A_{3}, …, A_{m}) satisfies Σ^{μ}(A′) ≠ ∅. It will then follow from our choice of A that the theorem applies (nontrivially) to A′. This application will be our initial building block (giving us the existence of a convergent). The preparation for this intersection-union operation is slightly different depending on whether ℓ = m or ℓ < m so we shall consider these two cases separately.

First suppose that ℓ < m. For every 1 ≤ i ≤ m let A^{i} = (A_{1}, …, A_{i−1}, A_{i+1}, …, A_{m}). By possibly rearranging our sequence, we may assume that A_{1} has minimum size over all sets A_{i} for which Σ^{μ}(A^{i}) ≠ ∅. If A_{1} ⊆ A_{i} for every 1 ≤ i ≤ m, then Σ^{μ}(A) = Σ^{μ}(A^{1}), Θ_{K}^{ℓ}(A) = Θ_{K}^{ℓ}(A^{1}), and Θ_{{0}}^{ℓ}(A) = Θ_{{0}}^{ℓ}(A^{1}) so A^{1} contradicts the choice of A for (ii). Thus, by rearranging (keeping A_{1} fixed), we may assume that A_{1} ⊈ A_{2}. If A_{2} ⊂ A_{1}, then Σ^{μ}(A^{2}) ⊇ Σ^{μ}(A^{1}) ≠ ∅ contradicting our choice of A_{1}. Hence, A_{2} ⊈ A_{1}. Thus, we have A_{1} \ A_{2} ≠ ∅, A_{2} \ A_{1} ≠ ∅, and defining A′ = (A_{1} ∩ A_{2}, A_{1} ∪ A_{2}, A_{3}, …, A_{m}), we have Σ^{μ}(A′) ⊇ Σ^{μ}(A^{1}) ≠ ∅ as desired.

Next suppose that ℓ = m. Since we have already handled the case when |A_{i} + K| > |K| for some 1 ≤ i ≤ m we may further assume that every A_{i} is included in a K-coset. Thus Σ^{μ}(A) = Σ^{m}(A) = ∑_{i=1}^{m} A_{i} and we may assume that K = G since this has no effect on the bound. By possibly rearranging our sets, we may assume that |A_{1}| ≤ |A_{2}|. If A_{1} = {a} for some a ∈ G then the result follows by applying the theorem to the sequence (A_{2}, A_{3}, …, A_{m}). Otherwise, choose distinct a, a′ ∈ A_{1}. Note that stab(A_{2}) ⊆ stab(Σ^{m}(A)) = {0}. Therefore, a′ −a ∉ stab(A_{2}), so there exists b ∈ A_{2} so that b+a′ −a ∉ A_{2}. Now replace A_{2} by A_{2} −b+a (and use the notation A_{2} for this shifted set henceforth). This has the effect of shifting Σ^{m}(A), but does not affect the size of this set or its stabilizer. By construction, a ∈ A_{1} ∩A_{2}, a′ ∈ A_{1} \ A_{2}, and A_{2} \ A_{1} ≠ ∅ (this last fact follows from the second and |A_{1}| ≤ |A_{2}|). Now setting A′ = (A_{1} ∩ A_{2}, A_{1} ∪ A_{2}, A_{3}, …, A_{m}) we have Σ^{μ}(A′) ≠ ∅ as desired.

Let us observe that in both cases, the new sequence A′ satisfies ∅ ≠ Σ^{μ}(A′) ⊆ Σ^{μ}(A). Further, since A_{1} \ A_{2} ≠ ∅ and A_{2} \ A_{1} ≠ ∅ our theorem applies to A′ by minimality assumption (i) or (iii).

Now we will redefine our notion of convergent. We define a set C to be a convergent if Σ^{μ}(A′) ⊆ C ⊆ Σ^{μ}(A) and if setting H = stab(C) we have

|C| ≥ |H|(Θ_{H}^{ℓ}(A′) − ℓ + 1) − |K|(Θ_{K}^{ℓ}(A) − ℓ).

Next we will show that C_{0} = Σ^{μ}(A′) ≠ ∅ is a convergent. To see this, let H_{0} = stab(C_{0}) and apply the theorem inductively to A′ to get the following:

|C_{0}| ≥ |H_{0}|(Θ_{H_{0}}^{ℓ}(A′) − ℓ + 1) − |K|(Θ_{K}^{ℓ}(A′) − ℓ)
≥ |H_{0}|(Θ_{H_{0}}^{ℓ}(A′) − ℓ + 1) − |K|(Θ_{K}^{ℓ}(A) − ℓ).

Thus, C_{0} is a convergent, and we may now choose a convergent C with stabilizer H so that H is minimal. If H = {0}, then we have

|Σ^{μ}(A)| ≥ |C|
≥ Θ_{{0}}^{ℓ}(A′) − ℓ + 1 − |K|(Θ_{K}(A) − ℓ)
= Θ_{{0}}^{ℓ}(A) − ℓ + 1 − |K|(Θ_{K}(A) − ℓ).

This contradiction implies that H ≠ {0}.

Our plan is to construct three new sets C^{1}, C^{2}, and C^{12}, each of which will be a superset of C with stabilizer ≤ H. We will then derive a contradiction under the assumption that none of them is a convergent with strictly smaller stabilizer than C.

Since Σ^{μ}(A) has trivial stabilizer and stab(C) = H ≠ {0} we may choose a μ-feasible sequence (b_{1}, b_{2}, …, b_{ℓ}) so that R = ∑_{j=1}^{ℓ} b_{j} +H ⊈ Σ^{μ}(A). Note that R ∩C = ∅. Further, it follows from Σ^{μ}(A′) ⊆ C that b_{1} ∈ A_{1} and b_{2} ∈ A_{2}. Let ν : G/H → ℕ be the H-pattern of weight ℓ given by the rule ν(Q) = |{j ∈ {1, …, ℓ} : b_{j} + H = Q}| and note that Σ^{ν}(A) ⊆ R. Next, let A^{∗} = (A_{3}, A_{4}, …, A_{m}) and let ν^{∗} be the H-pattern of weight ℓ − 2 given by the rule ν^{∗}(Q) = |{j ∈ {3, …, ℓ} : b_{j} + H = Q}|. Then, for δ = 1, 2, set A_{1}^{δ} = A_{1} ∩ (b_{δ} + H) and set A_{2}^{δ} = A_{2} ∩ (b_{3−δ} + H) (here the reader should note a deliberate “crossing” of our indices). Note further that b_{1} ∈ A_{1}^{1} and b_{2} ∈ A_{2}^{1} so A_{1}^{1} ≠ ∅ ≠ A_{2}^{1}. Then set B^{1} = A_{1}^{1} + A_{2}^{1}, set B^{2} = A_{1}^{2} + A_{2}^{2} and set B^{12} = B^{1} ∪ B^{2}. Next we give a few definitions, culminating with C^{1}, C^{2}, and C^{12}.

D^{12} = B^{12} + Σ^{ν^{∗}}(A^{∗}), H^{12} = stab(D^{12}).

Now for δ = 1, 2 we define the set D^{δ} and name its stabilizer as follows.

D^{δ} = B^{δ} + Σ^{ν^{∗}}(A^{∗}) + H^{12}, H^{δ} = stab(D^{δ}).

Finally, for ϵ = 1, 2, 12 we define the set C^{ϵ} as follows (for clarity, we will continue to let δ be a variable ranging over 1, 2 and let ϵ range over 1, 2, 12)

C^{ϵ} = C ∪ D^{ϵ}.

Let us make a few simple observations concerning these newly defined sets. First, note that by construction, D^{1} ≠ ∅ and D^{12} ≠ ∅. Further, D^{ϵ} ⊆ Σ^{ν}(A) ⊂ R for every ϵ = 1, 2, 12 so each of these sets is disjoint from C. Since each D^{ϵ} is a proper subset of the H-coset R, it follows that stab(C^{ϵ}) = H^{ϵ} whenever D^{ϵ} ≠ ∅. Figure 2 shows the containment relationships among the sets C^{ϵ} and their stabilizers H^{ϵ}.

Figure 2: Containment relations among the sets C^{ϵ} and their stabilizers.

Let us pause to note that by (i) of our choice of A, and the observation that |Σ^{μ}(A)| > |C| ≥ |H|, it follows that our theorem holds true (and Kneser’s theorem holds) whenever the associated sumset is contained in some H-coset. This fact will be used repeatedly in the remainder of the argument.

Next we shall make two claims which hold for ϵ = 1, 12 and also hold for ϵ = 2 if D^{2} ≠ ∅. Both of these claims will help us to simplify the equations which result from inductive applications of our theorem.

Claim 1: |Σ^{ν^{∗}}(A^{∗}) + H^{ϵ}| ≥ |H^{ϵ}|(Θ_{H^{ϵ}}^{ℓ−2}(A^{∗}) − ℓ + 3) − |H|(Θ_{H}^{ℓ−2}(A^{∗}) − ℓ + 2).

Proof of Claim: Set B = (A_{3}+H^{ϵ}, A_{4}+H^{ϵ}, …, A_{m}+H^{ϵ}) and note that Σ^{ν^{∗}}(B) = Σ^{ν^{∗}}(A^{∗})+ H^{ϵ}. Further, it follows from the definition of D^{ϵ} and H^{ϵ} that stab(Σ^{ν^{∗}}(B)) = H^{ϵ}. Thus, by applying our theorem inductively to Σ^{ν^{∗}}(B) we have

|Σ^{ν^{∗}}(A^{∗}) + H^{ϵ}| = |Σ^{ν^{∗}}(B)|
≥ |H^{ϵ}|(Θ_{H^{ϵ}}^{ℓ−2}(B) − ℓ + 3) − |H|(Θ_{H}^{ℓ−2}(B) − ℓ + 2)
= |H^{ϵ}|(Θ_{H^{ϵ}}^{ℓ−2}(A^{∗}) − ℓ + 3) − |H|(Θ_{H}^{ℓ−2}(A^{∗}) − ℓ + 2)

as desired.

For ϵ = 1, 2, 12 we define X^{ϵ} and Y^{ϵ} as follows:

X^{ϵ} = (b_{1} + H) \ ((A_{1}^{1} ∪ A_{2}^{2}) + H^{ϵ}),
Y^{ϵ} = (b_{2} + H) \ ((A_{1}^{2} ∪ A_{2}^{1}) + H^{ϵ}).

Claim 2: |H|(Θ_{H}^{ℓ}(A′) − Θ_{H}^{ℓ−2}(A^{∗})) − |H^{ϵ}|(Θ_{H^{ϵ}}^{ℓ}(A′) − Θ_{H^{ϵ}}^{ℓ−2}(A^{∗})) ≥ |X^{ϵ} ∪ Y^{ϵ}|.

Proof of Claim: First observe that contribution of an H-coset Q to |H|(Θ_{H}^{ℓ}(A′) − Θ_{H}^{ℓ−2}(A^{∗})) (which must be either 0, |H|, or 2|H|) is always at least the contribution of the H^{ϵ}-cosets contained in Q to |H^{ϵ}|(Θ_{H^{ϵ}}^{ℓ}(A′) − Θ_{H^{ϵ}}^{ℓ−2}(A^{∗})). Next, consider the coset b_{1} + H. If this coset has nontrivial intersection with A_{1}∩A_{2} or has nontrivial intersection with > ℓ−2 members of A^{∗}, then Σ^{ν}(A′) ≠ ∅. However, this contradicts the assumption that Σ^{ν}(A) ⊆ R is disjoint from C since Σ^{ν}(A) ⊇ Σ^{ν}(A′) ⊆ Σ^{μ}(A′) ⊆ C. It follows that the contribution of b_{1} + H to |H|(Θ_{H}^{ℓ}(A′) − Θ_{H}^{ℓ−2}(A^{∗})) is exactly |H|. By a similar argument, the contribution of the H^{ϵ}-cosets contained in b_{1} +H to |H^{ϵ}|(Θ_{H^{ϵ}}^{ℓ}(A′)−Θ_{H^{ϵ}}^{ℓ−2}(A^{∗})) is exactly |(A_{1}^{1} ∪A_{2}^{2})+H^{ϵ}|. Thus, the contribution of b_{1} +H and its H^{ϵ}-cosets to the left hand side of the equation in the claim is |X^{ϵ}|. Similarly, the coset b_{2} + H contributes |Y^{ϵ}|. Whether or not b_{1} + H = b_{2} + H, our claim follows immediately.

The next equation holds for ϵ = 1, 12 and for ϵ = 2 if D^{2} ≠ ∅. It follows from the assumption that C is a convergent, but C^{ϵ} is not.

|D^{ϵ}| = |C^{ϵ}| − |C|
< |H^{ϵ}|(Θ_{H^{ϵ}}^{ℓ}(A′) − ℓ + 1) − |H|(Θ_{H}^{ℓ}(A′) − ℓ + 1)  (2)

On the other hand, D^{ϵ} is defined by a sumset to which we may apply our theorem inductively. In the following equation, we have repeatedly applied our theorem inductively in the form of Kneser’s theorem, and we have also applied Claim 1. This equation holds for ϵ = 1, 12 and also holds for ϵ = 2 if D^{2} ≠ ∅.

|D^{ϵ}| = |B^{ϵ} + Σ^{ν^{∗}}(A^{∗}) + H^{ϵ}|
≥ |B^{ϵ} + H^{ϵ}| + |Σ^{ν^{∗}}(A^{∗}) + H^{ϵ}| − |H^{ϵ}|
≥ |B^{ϵ} + H^{ϵ}| + |H^{ϵ}|(Θ_{H^{ϵ}}^{ℓ−2}(A^{∗}) − ℓ + 2) − |H|(Θ_{H}^{ℓ−2}(A^{∗}) − ℓ + 2)  (3)

Combining equations 2 and 3 and applying Claim 2 gives us the following equation which holds for ϵ = 1, 12 and also holds for ϵ = 2 if D^{2} ≠ ∅.

|H| > |B^{ϵ} + H^{ϵ}| + |X^{ϵ} ∪ Y^{ϵ}| + |H^{ϵ}|  (4)

Using equation (4) and an inductive application of our theorem (again in the form of Kneser’s theorem) gives us the following equation which holds for δ = 1 and holds for δ = 2 if D^{2} ≠ ∅.

|H| > |A_{1}^{δ} + H^{δ}| + |A_{2}^{δ} + H^{δ}| + |X^{δ} ∪ Y^{δ}|.

Consider the above equation with δ = 1. If A_{2}^{2} = ∅, then |X^{1}| = |H| − |A_{1}^{1} + H^{1}| and we have a contradiction. Thus A_{2}^{2} ≠ ∅. We get a similar contradiction (by considering Y^{1}) under the assumption that A_{2}^{1} = ∅. It follows that D^{2} ≠ ∅, so equations (2), (3), and (4) hold for ϵ = 2, and the above equation holds for δ = 2. If b_{1} + H = b_{2} + H, then A_{2}^{1} = A_{2}^{2} so |X^{1}| = |(b_{1} +H)\((A_{1}^{1} ∪A_{2}^{1})+H^{1})| ≥ |H|−|A_{1}^{1} +H^{1}|−|A_{2}^{1} +H^{1}|, but again this contradicts the above equation for δ = 1. Thus b_{1} + H ≠ b_{2} + H, and we have that X^{ϵ} and Y^{ϵ} are disjoint for ϵ = 1, 2, 12.

Our next equation follows from the previous equation, and the observation that |H|, |A_{1}^{δ} + H^{δ}|, and |A_{2}^{δ} + H^{δ}| are all multiples of |H^{δ}|. It holds for δ = 1, 2:

|H| ≥ |A_{1}^{δ} + H^{δ}| + |A_{2}^{δ} + H^{δ}| + |H^{δ}|
≥ |A_{1}^{δ} + H^{12}| + |A_{2}^{δ} + H^{12}| + |H^{δ}|  (5)

The next equation follows from equation (4) for ϵ = 12 and another application of Kneser’s theorem. Here the application of Kneser’s theorem requires the observation that the stabilizer of the sumset (A_{1}^{δ} + H^{12}) + (A_{2}^{δ} + H^{12}) = B^{δ} + H^{12} is a subgroup of H^{δ} - a fact which follows from the definition of D^{δ}.

|H| ≥ |B^{12} + H^{12}| + |X^{12} ∪ Y^{12}|
≥ |B^{δ} + H^{12}| + |X^{12}| + |Y^{12}|
≥ |A_{1}^{δ} + H^{12}| + |A_{2}^{δ} + H^{12}| − |H^{δ}| + |X^{12}| + |Y^{12}|  (6)

Summing the four inequalities obtained by taking equations 5 and 6 for δ = 1, 2 and then dividing by two yields

2|H| > |A_{1}^{1} + H^{12}| + |A_{1}^{2} + H^{12}| + |A_{2}^{1} + H^{12}| + |A_{2}^{2} + H^{12}| + |X^{12}| + |Y^{12}|.

However, b_{1} +H = X^{12} ∪(A_{1}^{1} +H^{12})∪(A_{2}^{2} +H^{12}) and b_{2} +H = Y^{12} ∪(A_{1}^{2} +H^{12})∪(A_{2}^{1} +H^{12}). This yields the final contradiction and completes the proof. □

3 Corollaries

In this section use our main corollary for subsequence sums (Corollary 1.5) to derive Corollaries 1.8 and 1.10, and to give a new proof of Gao’s Theorem (1.11). We use the following notation. If a = (a_{1}, …, a_{m}) is a sequence of elements from G and S ⊆ G, we let ρ_{S}(a) = |{1 ≤ i ≤ m : a_{i} ∈ S}|. Similarly, if g ∈ G we define ρ_{g}(a) = ρ_{{g}}(a). The function ρ defined in the introduction (the maximum multiplicity of an element) is then ρ(a) = max_{g∈G} ρ_{g}(a). For convenience we have restated Corollary 1.5 below with this new notation.

Corollary 1.5 If a = (a_{1}, …, a_{m}) is a sequence of elements of G and H = stab(Σ^{ℓ}(a)), then

|Σ^{ℓ}(a)| ≥ |H|(1 − ℓ + ∑_{Q∈G/H} min {ℓ, ρ_{Q}(a)}).

Proof of Corollary 1.8: Recall that the sets Σ^{ℓ}(a) and Σ^{m−ℓ}(a) have the same size and the same stabilizer (one is just a shift of the (additive) inverse of the other), so we may apply Corollary 1.5 both for Σ^{ℓ}(a) and Σ^{m−ℓ}(a). Let H = stab(Σ^{ℓ}(a)) = stab(Σ^{m−ℓ}(a)). If H = {0}, then applying Corollary 1.5 to Σ^{m−ℓ}(a) shows that |Σ^{ℓ}(a)| = |Σ^{m−ℓ}(a)| ≥ ℓ + 1 (since ρ(a) ≤ m−ℓ), so (i) holds. Otherwise, applying this bound to Σ^{ℓ}(a) shows that either (ii) holds, or |Σ^{ℓ}(a)| ≥ |H|(1 + m − ℓ) ≥ |H| · ℓ/p ≥ ℓ which implies (i). □

Proof of Corollary 1.10: We shall assume that neither (i) nor (ii) holds and derive a contradiction. Set h = |H| and set t = |{Q ∈ G/H : ρ_{Q}(a) ≥ m−ℓ}|. If t = 0, then Corollary 1.5 (applied with m−ℓ in place of ℓ) shows that |Σ^{ℓ}(a)| = |Σ^{m−ℓ}(a)| ≥ h(1−(m−ℓ)+m) = h(1+ℓ), so (i) holds. Thus t ≥ 1.

Suppose that H = {0}. If t = 1, then let g_{0} ∈ G be the unique element with ρ_{g_{0}}(a) ≥ m − ℓ, and note that since ρ_{g_{0}}(a) ≤ ℓ − k + 2, we must have ∑_{g∈G} min{m − ℓ, ρ_{g}(a)} = m − (ρ_{g_{0}}(a) − (m − ℓ)) ≥ 2m − 2ℓ + k − 2. If t ≥ 2, then since a contains at least k distinct terms, we have ∑_{g∈G} min{m−ℓ, ρ_{g}(a)} ≥ t(m−ℓ)+k−t = t(m−ℓ−1)+k ≥ 2m−2ℓ+k−2. Since this inequality holds for all possible values of t, Corollary 1.5 shows that |Σ^{m−ℓ}(a)| ≥ 1 − (m − ℓ) + (2m − 2ℓ + k − 2) = m − ℓ + k − 1 and conclusion (i) holds.

Thus H ≠ {0}, i.e., h > 1. Assuming that (i) and (ii) do not hold, Corollary 1.5 gives

m − ℓ + k > |Σ^{ℓ}(a)|
≥ |H|(1 − ℓ + ∑_{Q∈G/H} ρ_{Q}(a))
= h(m − ℓ + 1)

so we have

k − h > (h − 1)(m − ℓ).  (7)

Note that this implies in particular that k ≥ h + 2. Since t ≥ 1, we may choose R ∈ G/H so that ρ_{R}(a) ≥ m − ℓ. Then our bound gives

|Σ^{m−ℓ}(a)| ≥ h(1 − m + ℓ + ∑_{Q∈G/H} min{m − ℓ, ρ_{Q}(a)})
= h(1 + ∑_{Q∈(G/H)\{R}} min{m − ℓ, ρ_{Q}(a)}).  (8)

First suppose that m − ℓ ≥ h. Then the Σ-term in the right hand side of equation (8) must be at least the number of distinct elements in G\R which appear at least once in a. Thus, in this case we have |Σ^{m−ℓ}(a)| ≥ h(1 + k − |R|) = h(1 + k − h). Combining this with Equation (7) and the assumption that (i) does not hold we have

(k − h)/(h − 1) > m − ℓ
> |Σ^{ℓ}(a)| − k
= |Σ^{m−ℓ}(a)| − k
≥ h(1 + k − h) − k
= (k − h)(h − 1).

However, this is contradictory since k ≥ h + 2 and h ≥ 2.

Thus we may now assume m − ℓ < h. Again let us consider the Σ-term in the right hand side of equation (8). There are at least k − |R| = k − h distinct elements in G \ R which appear in a. If Q ∈ G/H \ {R} contains s distinct elements of G which appear in a, then the contribution of this coset to the Σ-term will be at least min\{s, m − ℓ\} ≥ \frac{m−ℓ}{h}s. Thus, the Σ-term in the right hand side of (8) is at least \frac{m−ℓ}{h}(k − h). Combining this with the assumption that (i) does not hold we have

(m − ℓ) + (k − h) > |Σ^{m−ℓ}(a)| − h
≥ (k − h)(m − ℓ).

Since we have already observed that k ≥ h + 2, the above equation implies that m = ℓ + 1 (recall that m > ℓ by assumption). But then |Σ^{1}(a)| ≥ k since a contains k distinct terms, so we find |Σ^{ℓ}(a)| = |Σ^{1}(a)| ≥ k = m − ℓ + k − 1 and conclusion (i) holds. This completes the proof. □

Proof of Theorem 1.11: To see that s′(G) ≥ s(G) + |G| − 1, choose a sequence a of length s(G) − 1 without a nontrivial subsequence which sums to 0 and append |G| − 1 copies of 0 to a. This new sequence demonstrates s′(G) ≥ s(G) + |G| − 1.

Next we shall prove s′(G) ≤ s(G)+|G|−1 by induction on |G|. Let m = s(G)+|G|−1 and let a = (a_{1}, a_{2}, …, a_{m}) be a sequence of elements from G. We need to show that 0 ∈ Σ^{|G|}(a). Set H = stab(Σ^{|G|}(a)). If H ≠ {0}, then let ϕ : G → G/H be the canonical homomorphism and consider the sequence a_{ϕ} = (ϕ(a_{1}), ϕ(a_{2}), …, ϕ(a_{m})). Since s(G/H) ≤ s(G), we may apply our theorem inductively to get a subsequence of length [G : H] and sum zero in G/H. After removing this subsequence from a_{ϕ}, we apply the theorem again to get another such sequence. After |H| repetitions, we have |H| disjoint subsequences of a_{ϕ} each with length [G : H] and sum equal to zero in G/H. Combining the corresponding subsequences of a gives a subsequence of length |G| whose sum is in H. Since H = stab(Σ^{|G|}(a)), it follows that 0 ∈ Σ^{|G|}(a). Thus, we may assume that H = {0}.

If ρ(a) < s(G), then by Corollary 1.5 we have

|Σ^{s(G)−1}(a)| ≥ 2 − s(G) + ∑_{g∈G} min{s(G) − 1, ρ_{g}(a)} ≥ |G| + 1

which is contradictory. It follows that there exists g ∈ G so that ρ_{g}(a) ≥ s(G). By replacing a by (a_{1}−g, a_{2}−g, …, a_{m}−g) we do not affect the set Σ^{|G|}(a) but may now assume that ρ_{0}(a) ≥ s(G). By rearranging our sequence, we may further assume that a_{|G|+1}, a_{|G|+2}, … a_{|G|+s(G)−1} are all 0. Now, by the definition of the Davenport constant s(G), we may repeatedly choose disjoint subsequences of (a_{1}, a_{2}, …, a_{|G|}) each of which has zero sum, so that the number of leftover elements is at most s(G) − 1. By concatenating these sequences, and then adding an appropriate number of zero terms a_{i} with i > |G|, we obtain a subsequence of length |G| with zero sum, as required. □

4 Matroids

The goal of this section is to prove Theorem 1.14. Fix an abelian group G, a matroid M on E with rank function rk, and let B(M) denote the set of bases of M. Departing from the original treatment of Schrijver and Seymour, we let W be a weight function which assigns to each element e ∈ E a nonempty set W (e) ⊆ G. For every S ⊆ G let E_{S} = {e ∈ E : S ∩W (e) ≠ ∅} and abbreviate E_{g} = E_{{g}}. We define

W (M) = ⋃_{B∈B(M)} ∑_{b∈B} W (b).

With this notation we restate Theorem 1.14.

Theorem 4.1 Let p, q be primes and assume that G ≅ ℤ_{p^{n}} or G ≅ ℤ_{p} × ℤ_{q}. If H = stab(W (M)), then

|W (M)| ≥ |H|(1 − rk(M) + ∑_{Q∈G/H} rk(E_{Q})).

Proof: We proceed by induction on |E|. We may assume that M has no loops or parallel elements (if e, f ∈ E are parallel, then replace W (e) by W (e) ∪ W (f), delete f and apply induction). If rk(M) = 1, then the result is trivial, so we may further assume that rk(M) ≥ 2. For every e ∈ E, we define the subgroup

H_{e} = stab(W (e)).

By possibly replacing W (e) with a superset, we may assume that for every e ∈ E and every g ∈ G\W (e), the weight function W′ obtained from W by the adjustment W′(e) = W (e)∪{g} satisfies W′(M) ≠ W (M). The inequality below follows from this maximality assumption.

H ≤ H_{e} for every e ∈ E.  (9)

If g ∈ G and E_{g} spans e, then replacing W (e) by W (e) ∪ {g} does not change the set W (M). To see this let h ∈ g + ∑_{b∈B−e} W (b) where B is a basis containing e. Then B − e + f is a basis for some f ∈ E_{g}\B, whence h ∈ ∑_{b∈B−e+f} W (b). By repeating this process, we may assume that W (e) = {g ∈ G : E_{g} spans e} for every e ∈ E. Equivalently (in light of equation (9)), we have

W (e) = ∪{Q ∈ G/H : E_{Q} spans e}  (10)

Let M/e denote the matroid obtained from M by contracting e and consider the set W (e) + W (M/e). By construction, this is a subset of W (M) and has stabilizer ≥ H_{e} = stab(W (e)). However, the maximality of W (e) further implies that

H_{e} = stab(W (e) + W (M/e)).  (11)

Suppose now that G ≅ ℤ_{p} × ℤ_{q}. If there exist e, f ∈ E with H_{e} and H_{f} being distinct nontrivial subgroups, then we may choose a base B containing e and f, and we find that stab (∑_{b∈B} W (b)) ≥ H_{e} + H_{f} = G so W (M) = G, and we have H = G which contradicts either H ≤ H_{e} or H ≤ H_{f}. It follows from this argument that the subgroups {H_{e} : e ∈ E} are nested when G ≅ ℤ_{p} × ℤ_{q}. Since any two subgroups of ℤ)_{p^{n}} are nested, the same conclusion also holds for this case. Thus, we may choose f ∈ E so that H_{f} ≤ H_{e} for every e ∈ E. It follows immediately from this that H_{f} ≤ stab(W (M)) = H, and H_{f} ≤ stab(W (M/f)). The first of these inequalities and (9) imply that H_{f} = H. It follows from the second and equation (11) that stab(W (M/f)) = H_{f} = H. So, all three sets W (M), W (M/f), and W (f) + W (M/f) have stabilizer H. Now, applying Kneser’s Theorem (Theorem 1.2), equation (10), and the induction hypothesis, we have:

|W (M)| ≥ |W (f) + W (M/f)|
≥ |W (f)| + |W (M/f)| − |H|
≥ |H|(|{Q ∈ G/H : E_{Q} spans f }| + 1 − rk(M/f) + ∑_{Q∈G/H} rk_{M/f}(E_{Q})) − |H|
= |H|(1 − rk(M) + ∑_{Q∈G/H} rk_{M}(E_{Q}))

which completes the proof. □

References

[1] A. Bialostocki, P. Dierker, Zero sum Ramsey theorems, Congr. Numer. 70 (1990), 119– 130.

[2] A. Bialostocki, P. Dierker, On the Erdős-Ginzburg-Ziv Theorem and the Ramsey numbers for stars and matchings, Discrete Math. 110 (1992), 1–8.

[3] B. Bollobás, I. Leader, The number of k-sums modulo k, J. Number Theory 78 (1999), 27–35.

[4] H. Q. Cao, An addition theorem on the cyclic group ℤ_{p^{α}q^{β}}, The Electronic J. of Combinatorics 13 (2006), N9.

[5] A. L. Cauchy, Recherches sur les nombres, J. École polytech. 9 (1813), 99–116.

[6] H. Davenport, On the addition of residue classes, J. London Math. Soc. 10 (1935), 30–32.

[7] P. Erdős, A. Ginzburg, A. Ziv, Theorem in the additive number theory, Bull. Res. Coucil 10F (1961), 41–43.

[8] Z. Füredi, D. J. Kleitman, On zero-trees. J. Graph Theory 16 (1992), 107–120.

[9] W. Gao, A combinatorial problem on finite abelian groups, J. Number Theory 58 (1996), 100–103.

[10] W. D. Gao, Three addition Theorems on ℤ_{n}, preprint.

[11] W. D. Gao, R. Thangadurai, J. Zhuang, Addition Theorems on the cyclic groups ℤ_{p^{n}}, preprint.

[12] D. Grynkiewicz, On a partition analog of the Cauchy-Davenport Theorem, Acta Math. Hungar. 107 (2005), 167–181.

[13] D. Grynkiewicz, On a conjecture of Hamidoune for subsequence sums, Integers: Electr. J. Comb. Number Theory 5 (2) (2005) A07.

[14] Y. O. Hamidoune, Subsequence sums, Combin. Probab. Comput. 12 (2003), 413–425.

[15] Y. O. Hamidoune, O. Ordaz, A. Ortuño, On a combinatorial theorem of Erdős, Ginzburg, and Ziv, Combin. Probab. Comput. 7 (1998), 403–412.

[16] M. Kneser, Abschätzung der asymptotischen Dichte von Summenmengen, Math. Z. 58 (1953), 459–484.

[17] M. B. Nathanson, Additive Number Theory. Inverse Problems and the Geometry of Sumsets, Graduate Texts in Mathematics 165, Springer-Verlag, New York, 1996.

[18] A. Schrijver, P. D. Seymour, Spanning trees of different weights, DIMACS Series in Discrete Math. and Theoret. Comp. Sci., Vol 1 (1990), 281–288.

[19] A. Schrijver, P. D. Seymour, A simpler proof and a generalization of the zero-trees theorem, J. Combin. Theory Ser. A 58 (1991), 301–305.

[20] D. J. A. Welsh, Matroid theory, Academic Press [Harcourt Brace Jovanovich Publishers], London, 1976. L. M. S. Monographs, No. 8.