CRITICAL PAIRS IN ABELIAN GROUPS AND KEMPERMAN’S STRUCTURE THEOREM

VSEVOLOD F. LEV

Abstract. A well-known result by Kemperman describes the structure of those pairs (A, B) of finite subsets of an abelian group satisfying |A + B| ≤ |A| + |B| − 1. We establish a description which is, in a sense, dual to Kemperman’s, and as an application sharpen several results due to Deshouillers, Hamidoune, Hennecart, and Plagne.

1. Overview of the paper

The sumset of two subsets A and B of an additively written group is denoted by A + B and defined as the set of all those group elements, representable as a sum of an element of A and an element of B:

A + B := {a + b: a ∈ A, b ∈ B}.

In his remarkable paper [K60], Kemperman classified completely all pairs (A, B) of finite subsets of an abelian group with the small sumset; more precisely, those pairs satisfying

|A + B| ≤ |A| + |B| − 1.  (1)

This truly outstanding result, complementing a basic theorem by Kneser, may have not received yet the recognition that it certainly deserves. One of the reasons for this is that the structure of pairs, satisfying (1), is rather complicated, and so is Kemperman’s description reflecting this structure. Indeed, [K60] is not an easy reading, and an essential part of this paper constitutes an attempt to present Kemperman’s theorem and the mathematics around it in a possibly clear and transparent form, allowing one to appreciate this highly non-trivial theorem and facilitating its application.

To prepare the ground and explain where Kemperman’s theorem stemmed from, we start with the theorems of Kneser and Kemperman-Scherk; this is the subject of

2000 Mathematics Subject Classification. Primary: 11P70; secondary: 11B25, 11B13.

Key words and phrases. Critical pairs, small doubling, sumset, Kemperman’s theorem, Kneser’s theorem.

2 VSEVOLOD F. LEV

the next section, where also the basic notion of period and some useful notation are introduced.

In Section 3 we first define elementary pairs, which are the “building blocks” of Kemperman’s construction; once this is accomplished, Kemperman’s theorem is stated.

Having finished with the expository part, we present a number of new results in Section 4. Though the exact formulations are to be postponed until the necessary notation is introduced and Kemperman’s theorem (to which our results are to be compared) is stated, we try to give here a brief outline.

Our main result is Theorem 2, which is in a sense dual to Kemperman’s theorem. In a very rough way, Kemperman’s theorem can be compared to the statement that if a pair (a, b) of non-negative integers possesses some property P, then there exist integers d ≥ 1, \overline{a}, \overline{b} ≥ 0, and a_{0}, b_{0} ∈ [0, d−1] such that a = \overline{a}d+a_{0}, b = \overline{b}d+b_{0}, and moreover, the pair (a_{0}, b_{0}) is “elementary”, while the pair (\overline{a}, \overline{b}) satisfies P. Thus, we have a closed-form description of the “residual pair” (a_{0}, b_{0}) and a recursive description of the “root pair” (\overline{a}, \overline{b}). Theorem 2 can then be compared to the statement that, under the same assumption, the integers d ≥ 1, \overline{a}, \overline{b} ≥ 0, and a_{0}, b_{0} ∈ [0, d − 1] with a = \overline{a}d + a_{0}, b = \overline{b}d + b_{0} exist so that (\overline{a}, \overline{b}) is elementary, while (a_{0}, b_{0}) satisfies P.

Another result established in this paper is Theorem 1, which can be viewed as a light version of Kemperman’s theorem. While the assumptions of Theorem 1 are slightly weaker than those of Kemperman’s theorem, the former provides somewhat less structure information than the later, giving only a necessary (but not sufficient) condition for (1) to hold. The potential advantage of Theorem 1 is its relative simplicity; at the same time, it keeps much of the strength of Kemperman’s theorem in the sense that the deduction of each of these two results from the other is reasonably short. Indeed, we do not have an independent proof of Theorem 1; instead, we derive it from Kemperman’s theorem, and then derive Theorem 2 from Theorem 1.

As applications of Kemperman’s theorem and Theorem 2, we improve several results by Deshouillers, Hamidoune, Hennecart, and Plagne; see Section 4 for more information and discussion.

The proofs of all the results, presented in Section 4, are concentrated in Section 5. In the Appendix we give two claims persistent to the definition of Kemperman’s elementary pairs.

CRITICAL PAIRS AND KEMPERMAN’S THEOREM 3

2. Preliminaries: theorems of Kneser and Kemperman-Scherk

Let G be an (additively written) abelian group. For finite non-empty subsets A, B ⊆ G with given cardinalities |A| and |B|, how small can the sumset A + B be? It is not difficult to see that if G is torsion-free, then |A + B| ≥ |A| + |B| − 1 holds for any choice of A and B. The well-known Cauchy-Davenport theorem asserts that if G is cyclic of prime order, then this estimate remains true under the additional assumption that A + B ≠ G. Kneser’s theorem is a deep and far-going extension of these results onto arbitrary abelian groups; loosely speaking, it says that if |A + B| < |A| + |B| − 1 holds, then some torsion is involved. To state the theorem precisely we have to introduce some notation.

For a subset S and an element g of an abelian group G, we use the abbreviations S + g and g + S for the sumset S + {g}. If H is a subgroup of G, then the canonical homomorphism of G onto the quotient group G/H is denoted by φ_{G/H}, and the full inverse image under φ_{G/H} of a subset \overline{S} ⊆ G/H is denoted by φ_{G/H}^{−1}(\overline{S}). The period of a subset S ⊆ G will be denoted by π(S); recall, that this is the subgroup of G defined by

π(S) := {g ∈ G: S + g = S},

and that S is called periodic if π(S) ≠ {0} and aperiodic otherwise. Thus, S is a union of cosets of π(S) and indeed, π(S) lies above any subgroup of G such that S is a union of its cosets. Observe also that if H = π(S), then φ_{G/H}(S) is an aperiodic subset of G/H.

Theorem A (Kneser, [K53, K55]; see also [M65]). Let A and B be finite, non-empty subsets of an abelian group G, satisfying (1). Then, letting H := π(A + B), we have

|A + B| = |A + H| + |B + H| − |H|.

This theorem will be referred to as “Kneser’s theorem”. It shows that any pair (A, B), satisfying (1), can be obtained by “lifting” a pair (\overline{A}, \overline{B}) of subsets of a quotient group with |\overline{A}+\overline{B}| = |\overline{A}|+|\overline{B}|−1. Indeed, if A, B, and H are as in Kneser’s theorem, \overline{A} = φ_{G/H}(A), and \overline{B} = φ_{G/H}(B), then |A+H| = |\overline{A}||H|, |B +H| = |\overline{B}||H|, and |A + B| = |\overline{A} + \overline{B}||H|, so that the conclusion of the theorem takes the shape |\overline{A} + \overline{B}| = |\overline{A}| + |\overline{B}| − 1. Furthermore,

(|A + H| − |A|) + (|B + H| − |B|) = |H| + (|A + B| − |A| − |B|) < |H|

whence A and B are obtained from A + H = φ_{G/H}^{−1}(\overline{A}) and B + H = φ_{G/H}^{−1}(\overline{B}) by removing less than |H| elements totally. Conversely, one verifies easily that if H is a finite subgroup of an abelian group G, the finite non-empty subsets \overline{A}, \overline{B} ⊆ G/H satisfy |\overline{A} + \overline{B}| = |\overline{A}| + |\overline{B}| − 1, and A ⊆ φ_{G/H}^{−1}(\overline{A}), B ⊆ φ_{G/H}^{−1}(\overline{B}) satisfy (|φ_{G/H}^{−1}(\overline{A})| − |A|) + (|φ_{G/H}^{−1}(\overline{B})| − |B|) < |H|, then (1) holds.

We need the following, almost immediate, corollary from Kneser’s theorem.

Corollary 1. Let A and B be finite, non-empty subsets of an abelian group, satisfying |A + B| < |A|/2 + |B|. Then A is contained in a coset of π(A + B).

Proof. Write H := π(A + B). Then by Kneser’s theorem and the assumption,

|A + H| + |B + H| − |H| = |A + B| < |A + H|/2 + |B + H|,

and hence |A + H| < 2|H|. Thus in fact |A + H| = |H|, as wanted. □

For finite subsets A and B of an abelian group and a group element c we write

ν_{c}(A, B) := #{(a, b) ∈ A × B: c = a + b};

that is, ν_{c}(A, B) is the number of representations of c as a sum of an element of A and an element of B. Observe, that ν_{c}(A, B) > 0 if and only if c ∈ A + B. The smallest number of representations of an element of A + B will be denoted by μ(A, B):

μ(A, B) := min{ν_{c}(A, B): c ∈ A + B}.

Another result frequently used in this paper is a beautiful theorem by Kemperman and Scherk, relating the quantities |A+B| and μ(A, B). We call it “the Kemperman-Scherk theorem”. This name is not standard; the reader can check [L05, Section 1] for explanations and historical references.

Theorem B (Kemperman-Scherk). If A and B are finite, non-empty subsets of an abelian group, then

|A + B| ≥ |A| + |B| − μ(A, B).

Thus, the theorem of Kemperman-Scherk shows that if the sumset A + B is small, then any element c ∈ A + B has many representations of the form c = a + b with a ∈ A and b ∈ B.

Here is a short deduction of the theorem of Kemperman-Scherk from Kneser’s theorem.

Proof of Theorem B. Let H := π(A + B), choose arbitrarily c ∈ A + B, and fix a representation c = a_{0} + b_{0} with a_{0} ∈ A and b_{0} ∈ B. If (1) fails, the assertion is trivial;

CRITICAL PAIRS AND KEMPERMAN’S THEOREM 5

otherwise, by Kneser’s theorem we have

|(A − a_{0}) ∩ H| + |(b_{0} − B) ∩ H| = |A ∩ (a_{0} + H)| + |B ∩ (b_{0} + H)|
= 2|H| − |(a_{0} + H) \ A| − |(b_{0} + H) \ B|
≥ 2|H| − |(A + H) \ A| − |(B + H) \ B|
= |H| + (|A| + |B| − |A + B|)

and by the box principle, the sets (A − a_{0}) ∩ H and (b_{0} − B) ∩ H share at least |A|+|B|−|A+B| common elements. However, each pair (a, b) ∈ A×B with a−a_{0} = b_{0} − b yields the representation c = a + b, whence ν_{c}(A, B) ≥ |A| + |B| − |A + B|. □

3. Introduction: Kemperman’s theorem

As we saw above, Kneser’s theorem reduces the problem of classifying all pairs (A, B) of finite, non-empty subsets of an abelian group, satisfying (1), to that of describing those pairs for which equality is attained in (1). This latter problem was solved by Kemperman in [K60]. As Kemperman has shown, one has to bring into consideration the following additional condition:

either π(A + B) = {0}, or μ(A, B) = 1.  (2)

Kneser’s theorem shows that this condition is not too restrictive; more precisely, if (1) holds while Kemperman’s condition (2) fails, then there exist a finite nonzero subgroup H ≤ G and subsets \overline{A}, \overline{B} ⊆ G/H such that A and B are “dense” in φ_{G/H}^{−1}(\overline{A}) and φ_{G/H}^{−1}(\overline{B}), respectively, and (\overline{A}, \overline{B}) satisfies the analogs of both (1) and (2). Furthermore, from theorems of Kneser and Kemperman-Scherk it follows that if (A, B) satisfies (1) and (2), then in fact equality holds in (1).

Kemperman’s description relies on the notion of an elementary pair, which we introduce after short preparations.

By an arithmetic progression in an abelian group G with difference d ∈ G we mean a set of the form {g+d, g+2d, …, g+kd}, where g is an element of G and k is a positive integer, not exceeding the order of d in G. Thus, cosets of finite cyclic subgroups (and in particular, one-element sets) are considered arithmetic progressions, while the empty set is not.

For a subset A of an abelian group we write −A := {−a: a ∈ A}, and given yet another subset B and an element g of the same group we let B − A := B + (−A) and g − A := {g} − A.

Following Kemperman, we say that a pair (A, B) of finite subsets of an abelian group G is elementary if at least one of the following holds:

6 VSEVOLOD F. LEV

(I) min{|A|, |B|} = 1; (II) A and B are arithmetic progressions sharing a common difference d ∈ G, the

order of which in G is at least |A| + |B| − 1; (III) A = g_{1} + (H_{1} ∪ {0}) and B = g_{2} − (H_{2} ∪ {0}), where g_{1}, g_{2} ∈ G and H_{1}, H_{2}

are non-empty subsets of a subgroup H ≤ G such that H = H_{1} ∪ H_{2} ∪ {0} is a partition of H. Moreover, c := g_{1} + g_{2} is the only element of A + B with ν_{c}(A, B) = 1;

(IV) A = g_{1} + H_{1} and B = g_{2} − H_{2}, where g_{1}, g_{2} ∈ G and H_{1}, H_{2} are non-empty, aperiodic subsets of a subgroup H ≤ G such that H = H_{1} ∪ H_{2} is a partition of H. Moreover, μ(A, B) ≥ 2.

We note that if (A, B) is an elementary pair of subsets, then A and B are nonempty; also, the subgroup H in (III) and (IV) is finite and satisfies |H| ≥ 3. Another immediate, yet important observation is that if A and B are subsets of a subgroup F ≤ G, then (A, B) is an elementary pair in G of some type if and only if it is an elementary pair in F of the same type.

Notice, that for type (III) pairs we have |A| + |B| = |H| + 1 whence A + B = g_{1} + g_{2} + H by the box principle, while for type (IV) pairs we have |A| + |B| = |H| and A+B = g_{1}+g_{2}+(H \{0}). (To prove the last equality fix an element h ∈ H \{0} and notice that since h ∉ π(H_{2}), there exist h_{2} ∈ H_{2} and h_{1} ∈ H_{1} with h + h_{2} = h_{1}, whence g_{1} + g_{2} + h = (g_{1} + h_{1}) + (g_{2} − h_{2}) ∈ A + B.) One now verifies easily that both (1) and (2) hold true for elementary pairs (A, B) of any type.

It can be shown that the first sentence in (III) describes precisely those pairs (A, B), satisfying both (1) and (2) and such that A + B is an H-coset; the second sentence excludes the situation where (A, B) can be decomposed into “more elementary” pairs. Similarly, the first sentence in (IV) describes precisely those pairs (A, B) satisfying both (1) and (2) and such that A + B is an H-coset with one element removed, while the second one excludes the situation where (A, B) can be further decomposed. We make these statements precise and prove them in the Appendix.

Now we can state the result which throughout the rest of the paper is referred to as “Kemperman’s theorem”.

Theorem C (Kemperman, [K60, Theorem 5.1]). Let A and B be finite, non-empty subsets of a non-trivial abelian group G. A necessary and sufficient condition for both (1) and (2) to hold simultaneously is that there exist non-empty subsets A_{0} ⊆ A, B_{0} ⊆ B and a non-zero subgroup H ≤ G such that, writing \overline{A} := φ_{G/H}(A) and \overline{B} := φ_{G/H}(B), we have

CRITICAL PAIRS AND KEMPERMAN’S THEOREM 7

(i) each of A_{0} and B_{0} is contained in an H-coset, and the pair (A_{0}, B_{0}) is elementary;

(ii) each of A \ A_{0} and B \ B_{0} is a (possibly, empty) union of H-cosets; (iii) |\overline{A} + \overline{B}| = |\overline{A}| + |\overline{B}| − 1; (iv) A_{0} + B_{0} + H, considered as an element of G/H, has a unique representation

as a sum of an element of \overline{A} and an element of \overline{B}.

We notice that one can choose H = G in Kemperman’s theorem if and only if (A, B) is an elementary pair. Observe also that, as it follows from (ii), the set (A + B) \ (A_{0} + B_{0}) is a (possibly, empty) union of H-cosets. Consequently, if H is finite then conditions (i) and (ii) show that |A+H|−|A| ≤ |H|−1, |B +H|−|B| ≤ |H|−1, and |A+B +H|−|A+B| ≤ |H|−1 (cf. Theorem 1 below). Note, that for a finite set C ⊆ G and a finite subgroup H ≤ G the condition |C +H|−|C| ≤ |H|−1 (frequently emerging in what follows, and sometimes written as |C + H| ≤ |C| + |H| − 1) means that C is a “dense” subset of a union of H-cosets.

4. Summary of results

In this section we present and discuss our results; the proofs are postponed until Section 5.

While Kemperman’s theorem describes the structure of the “residual” pair (A_{0}, B_{0}), in the following theorem (qualified above as a light version of Kemperman’s theorem) we make the emphasis on the structure of the “root” pair (\overline{A}, \overline{B}). Notice, that Kemperman’s condition (2) is replaced by a weaker assumption; on the other hand, we obtain a less precise information about the distribution of elements of A and B in H-cosets (cf. Theorem 2 below).

Theorem 1. Let A and B be finite, non-empty subsets of a non-trivial abelian group G, satisfying (1). Suppose that either A + B ≠ G or μ(A, B) = 1 (or both) hold true. Then there exists a finite, proper subgroup H < G such that, writing \overline{A} = φ_{G/H}(A) and \overline{B} = φ_{G/H}(B), we have

(i) |C +H|−|C| ≤ |H|−1 with C substituted by any of the sets A, B, and A+B; (ii) (\overline{A}, \overline{B}) is an elementary pair in G/H.

Theorem 1 shows that, under some mild technical restriction, any pair of finite subsets (A, B) of an abelian group G, satisfying (1), can be obtained by lifting an elementary pair (\overline{A}, \overline{B}) of subsets of a quotient group G/H and removing “a small number” of elements from the lifted subsets. Concerning the technical restriction just mentioned, we observe that the condition “either A+B ≠ G or μ(A, B) = 1 (or both)

8 VSEVOLOD F. LEV

hold true” means that there is a group element with at most one representation as a + b with a ∈ A and b ∈ B.

Our next theorem provides an alternative classification of pairs (A, B), satisfying (1). The reader can now appreciate the statement made in Section 1 on duality between this theorem and Kemperman’s.

Theorem 2. Let A and B be finite, non-empty subsets of an abelian group G. A necessary and sufficient condition for both (1) and (2) to hold simultaneously is that either the pair (A, B) is elementary, or there exist non-empty subsets A_{0} ⊆ A, B_{0} ⊆ B and a finite, non-zero, proper subgroup H < G such that, writing \overline{A} := φ_{G/H}(A) and \overline{B} := φ_{G/H}(B), we have

(i) each of A_{0}, B_{0} is contained in an H-coset, |A_{0} + B_{0}| = |A_{0}| + |B_{0}| − 1, and (A_{0}, B_{0}) satisfies Kemperman’s condition (2);

(ii) each of A \ A_{0} and B \ B_{0} is a (possibly, empty) union of H-cosets; (iii) the pair (\overline{A}, \overline{B}) is elementary, and A_{0} + B_{0} + H, considered as an element

of G/H, has a unique representation as a sum of an element of \overline{A} and an element of \overline{B}.

We point it out once again that Theorem 2 will be derived from Theorem 1 which, in turn, is deduced from Kemperman’s theorem.

Turning to applications, we first show how Theorem 1 can be used to sharpen one of the central results of [HP04].

We say that a non-empty, finite subset A of an abelian group G is a thick component of G (the term used in [HP04] is “Vosper subset”) if for any finite subset B ⊆ G with |B| ≥ 2 either |A + B| ≥ |A| + |B|, or |A| + |B| ≥ |G| − 1 (or both) hold. Evidently, if |G| > 4 and A is a thick component of G, then |A| ≥ 2.

Theorem D ([HP04, Theorem 2.1]). Let A be a generating subset of a finite abelian group G. Suppose that 0 ∈ A and |A| ≤ |G|/2. Then there exists a subgroup H < G satisfying |A + H| − |A| ≤ |H| − 1 and A + H ≠ G, and such that φ_{G/H}(A) is either an arithmetic progression or a thick component (of G/H).

Our version is as follows.

Theorem 3. Let A be a finite, non-empty subset of an abelian group G. Suppose that |A| ≤ |G|/2. Then there exists a finite subgroup H < G satisfying |A + H| − |A| ≤ |H| − 1 and A + H ≠ G, and such that φ_{G/H}(A) is either an arithmetic progression or a thick component (of G/H).

CRITICAL PAIRS AND KEMPERMAN’S THEOREM 9

Next, we show how the original Kemperman’s theorem leads to an improvement of a result of Hamidoune [H01, Theorem 6.6] (see [HP02, Lemma 2] and [HP04, Theorem A and Lemma 3.2] for the corrected statement).

Theorem 4. Let A and B be finite subsets of an abelian group G, satisfying (1) and such that A is non-empty, |B| ≥ 2, and |A + B| ≤ |G| − 2. Then at least one of the following holds:

(i) there exists a finite, non-zero subgroup H < G such that |A+H|−|A| ≤ |H|−1 and A + H ≠ G;

(ii) there exist a non-zero subgroup H ≤ G of finite index n := [G : H], elements g_{1}, …, g_{n−1} ∈ G, and an arithmetic progression A_{0} ⊆ A, such that A is the disjoint union A = A_{0} ∪ (g_{1} + H) ∪ ⋯ ∪ (g_{n−1} + H).

Observe that if the subgroup H in (ii) satisfies H = G, then A is an arithmetic progression. Also, if H is infinite then H = G necessarily holds since A is finite.

Remark. As compared with Theorem 4, [HP04, Theorem A] imposes the extra restrictions that G is finite, A contains zero and generates G, and |A| ≤ |G|/2.

Finally, we apply Theorem 2 to the situation where G is an elementary abelian 2-group, and the set summands A and B are identical. That is, we are interested in the structure of those subsets A ⊆ (ℤ/2ℤ)^{r}, with a positive integer r, satisfying |2A| < 2|A|. (Here and below, 2A is used as an abbreviation for A+A.) We show that Theorem 2 allows one to give a complete, closed-form (non-recursive) classification of such subsets. We start with two theorems, describing the present state of the art; the former of them establishes the structure of the sumset 2A (for a set A ⊆ (ℤ/2ℤ)^{r} with |2A| < 2|A|), the latter presents some structure information about the set A itself.

Theorem E ([HP03, Theorem 1]). Let r ≥ 1 be an integer and suppose that A is a non-empty subset of the elementary abelian 2-group (ℤ/2ℤ)^{r}, satisfying |2A| = c|A| with c < 2. Then there exist a subgroup H ≤ (ℤ/2ℤ)^{r} and an element g ∈ (ℤ/2ℤ)^{r} such that A ⊆ g + H, and moreover,

(i) if 1 ≤ c < 7/4 then 2A = H;

(ii) if 7/4 ≤ c < 2 then either 2A = H, or there exist a subgroup F < H with |F | ≤ |H|/8 and an element h_{0} ∈ H such that 2A = H \ (h_{0} + F).

The restriction of [DHP04, Theorem 2] onto the range c ∈ [1, 2) is

10 VSEVOLOD F. LEV

Theorem F (cf. [DHP04, Theorem 2]). Let r ≥ 1 be an integer and suppose that A is a non-empty subset of the elementary abelian 2-group (ℤ/2ℤ)^{r}, satisfying |2A| = c|A| with c < 2. Then there exists a subgroup H ≤ (ℤ/2ℤ)^{r} such that A ⊆ H and |A| ≥ u(c)|H|, where u(c) = (3c − 1 − c^{2})/(2c − 1).

We are now in a position to state the necessary and sufficient condition for |2A| < 2|A| (with A ⊆ (ℤ/2ℤ)^{r}) to hold. Suppose that H ≤ (ℤ/2ℤ)^{r} is a non-zero subgroup and let h_{0} ∈ H be a non-zero element of H. We say that S ⊆ H is an h_{0}-antisymmetric subset of H, if H is the disjoint union H = S ∪ (h_{0} + S); in other words, S contains exactly one element from each pair (h, h + h_{0}), for any h ∈ H. Evidently, in this case we have |S| = |H|/2.

Theorem 5. Let r ≥ 1 be an integer. If a subset A ⊆ (ℤ/2ℤ)^{r} satisfies |2A| < 2|A|, then one of the following holds:

(i) there exists a subgroup H ≤ (ℤ/2ℤ)^{r} such that A is contained in an H-coset and |A| > |H|/2;

(ii) there exist two subgroups F, H ≤ (ℤ/2ℤ)^{r}, satisfying |F | ≥ 8 and F ∩H = {0}, and an aperiodic antisymmetric subset S ⊆ F, such that A is obtained from a shift of the set S +H by removing less than |H|/2 of its elements. In this case 2A is the sum F ⊕ H with one H-coset removed, so that |2A| = (|F | − 1)|H|.

Conversely, let F, H ≤ (ℤ/2ℤ)^{r} be subgroups satisfying F ≠ {0} and F ∩ H = {0}, and let S be an antisymmetric subset of F. If A is obtained from a shift of the set S+H by removing less than |H|/2 of its elements, then |2A| = (|F | − |π(S)|)|H| < 2|A|.

5. Proofs

Proof of Theorem 1. Suppose that A and B are finite, non-empty subsets of a nontrivial abelian group G, satisfying (1) and such that either A+B ≠ G or μ(A, B) = 1 (or both) hold true. We want to show that there exists a finite proper subgroup H < G with the properties that

(i) |C + H| − |C| ≤ |H| − 1 for C = A, B, A + B;

(ii) (\overline{A}, \overline{B}) is an elementary pair in G/H, where \overline{A} = φ_{G/H}(A) and \overline{B} = φ_{G/H}(B).

If there exists a finite proper subgroup H < G such that |A + B + H| − |A + B| ≤ |H| − 1 and |H| ≥ |A + B|, then |A + B + H| < 2|H|; consequently, A + B, and therefore each of the sets A and B, is contained in a coset of H, from which the assertion follows.

CRITICAL PAIRS AND KEMPERMAN’S THEOREM 11

Suppose now that for each finite proper subgroup H < G with |A + B + H| − |A + B| ≤ |H| − 1 we have |H| < |A + B|. Observing that the zero subgroup H = {0} satisfies the conditions

(a) |C + H| − |C| ≤ |H| − 1 for C = A, B, A + B;

(b) either \overline{A} + \overline{B} ≠ G/H or μ(\overline{A}, \overline{B}) = 1 (or both) hold true;

(c) |\overline{A} + \overline{B}| ≤ |\overline{A}| + |\overline{B}| − 1, we can then find a finite proper subgroup H < G which also satisfies these conditions and which is maximal by inclusion among all finite proper subgroups with this property. (Here and below in the proof \overline{A} and \overline{B} are defined by \overline{A} = φ_{G/H}(A), \overline{B} = φ_{G/H}(B).) We show that the pair (\overline{A}, \overline{B}) is elementary.

Assume first that (\overline{A}, \overline{B}) satisfies Kemperman’s condition (2). Let \overline{F} ≤ G/H be the non-zero subgroup, the existence of which is guaranteed by Kemperman’s theorem as applied to the subsets \overline{A}, \overline{B} ⊆ G/H, and let F := φ_{G/H}^{−1}(\overline{F}), so that H ≨ F. If (\overline{A}, \overline{B}) is not elementary, then \overline{F} is finite and \overline{F} ≨ G/H, whence F is finite, too, and F ≨ G. Writing C̃ = φ_{G/F} (C) for a subset C ⊆ G, we show that F satisfies the conditions

(a′) |C + F | − |C| ≤ |F | − 1 for C = A, B, A + B; (b′) either Ã + B̃ ≠ G/F or μ(Ã, B̃) = 1 (or both) hold true; (c′) |Ã + B̃| ≤ |Ã| + |B̃| − 1,

contradicting maximality of H.

Indeed, (c′) follows immediately from assertion (iii) of Kemperman’s theorem in view of the natural isomorphism (G/H)/\overline{F} ≅ G/F. Similarly, (b′) follows from assertion (iv) of Kemperman’s theorem, which implies that μ(Ã, B̃) = 1. Finally, to prove (a′) we observe that for C being any of A, B, A + B we have

(|C̃| − 1)|\overline{F} | = |\overline{C} + \overline{F} | − |\overline{F} | ≤ |\overline{C}| − 1

(see a remark following the statement of Kemperman’s theorem). Multiplication by |H| and condition (a) yield

(|C̃| − 1)|F | ≤ |C + H| − |H| ≤ |C| − 1,

whence

|C + F | − |F | ≤ |C| − 1,

as wanted.

Now assume that the pair (\overline{A}, \overline{B}) does not satisfy Kemperman’s condition (2). In this case \overline{A} + \overline{B} is periodic and we define \overline{F} ≤ G/H to be the period: \overline{F} := π(\overline{A} + \overline{B}); also, let F := φ_{G/H}^{−1}(\overline{F}). By (b), we have \overline{F} ≠ G/H, whence H ≨ F ≨ G. As above, for C ⊆ G we write C̃ = φ_{G/F} (C) and show that F satisfies (a′)–(c′), contradicting maximality of H.

By Kneser’s theorem we have

|\overline{A} + \overline{B}| = |\overline{A} + \overline{F} | + |\overline{B} + \overline{F} | − |\overline{F} |;

equivalently, |Ã + B̃| = |Ã| + |B̃| − 1, establishing (c′). Next, Ã + B̃ = G/F would imply \overline{F} = G/H which is wrong; this proves (b′). Finally,

|A + B + F | = |A + B + H| ≤ |A + B| + |H| − 1 < |A + B| + |F | − 1

(as \overline{A} + \overline{B} + \overline{F} = \overline{A} + \overline{B}) and furthermore,

|\overline{A} + \overline{F} | + |\overline{B} + \overline{F} | − |\overline{F} | = |\overline{A} + \overline{B}| ≤ |\overline{A}| + |\overline{B}| − 1,
|\overline{A} + \overline{F} | ≤ |\overline{A}| + |\overline{F} | − 1,
|A + F | ≤ |A + H| + |F | − |H| ≤ |A| + |F | − 1;

similarly,

|B + F | ≤ |B| + |F | − 1.

This proves (a′). □

Proof of Theorem 2. Leaving the simple sufficiency part as an exercise to the interested reader, we prove necessity: assuming that the pair (A, B) satisfies (1) and (2) and is not elementary (and in particular min{|A|, |B|} > 1), we establish the existence of A_{0}, B_{0}, and H possessing properties (i)–(iii). We divide the proof into two parts, the first of which will be further subdivided.

1. First, consider the situation where at least one of the sets A and B is contained in a coset of a finite proper subgroup of G. Suppose, for instance, that A is a subset of a coset of a finite proper subgroup H < G, and let, moreover, H be a minimal (by inclusion) subgroup with this property. If B is also contained in an H-coset, the assertion is immediate; otherwise, we represent B as a union

B = B_{0} ∪ B_{1} ∪ ⋯ ∪ B_{n−1}

where n ≥ 2, each subset B_{i} is contained in a coset of H, and these n cosets are pairwise disjoint. Notice, that then A + B is the disjoint union

A + B = (A + B_{0}) ∪ (A + B_{1}) ∪ ⋯ ∪ (A + B_{n−1}).

We recall that (A, B) satisfies either π(A + B) = {0}, or μ(A, B) = 1.

CRITICAL PAIRS AND KEMPERMAN’S THEOREM 13

1.1. If μ(A, B) = 1 then, renumbering the sets B_{i} if necessary, we can assume that μ(A, B_{0}) = 1, whence |A+B_{0}| ≥ |A|+|B_{0}|−1 by the theorem of Kemperman-Scherk. Combining this with the trivial estimate |A + B_{i}| ≥ |B_{i}| (i ∈ [1, n − 1]) we get

|A| + |B_{0}| + |B_{1}| + ⋯ + |B_{n−1}| − 1 ≥ |A + B| ≥ (|A| + |B_{0}| − 1) + |B_{1}| + ⋯ + |B_{n−1}|.

It follows that |A+B_{0}| = |A|+|B_{0}|−1 and |A+B_{i}| = |B_{i}| for all indices i ∈ [1, n−1]. The latter is only possible if A is contained in a coset of π(B_{i}). By minimality of H, we have then π(B_{i}) = H; that is, B_{i} is an H-coset for any i ∈ [1, n − 1]. This establishes the required structure (with A_{0} = A). 1.2. If μ(A, B) > 1, then π(A + B) = {0}. In this case we first observe that, by (1), there is at most one index i ∈ [0, n−1] such that |A+B_{i}| ≥ |B_{i}|+|A|/2; without loss of generality, we can assume that |A+B_{i}| < |B_{i}|+|A|/2 for i ∈ [1, n−1]. Corollary 1 shows that A is contained in a coset of π(A + B_{i}) for i ∈ [1, n − 1], and by minimality of H, all A + B_{i} (i ∈ [1, n − 1]) are H-cosets. Now, since A + B is aperiodic, so is A + B_{0}, whence |A + B_{0}| ≥ |A| + |B_{0}| − 1 by Kneser’s theorem. Finally,

|A| + |B_{0}| + |B_{1}| + ⋯ + |B_{n−1}| − 1 ≥ |A + B| = |A + B_{0}| + (n − 1)|H| ≥ |A| + |B_{0}| + (n − 1)|H| − 1,

which implies |A + B_{0}| = |A| + |B_{0}| − 1 and |B_{i}| = |H| for i ∈ [1, n − 1].

2. For the rest of the proof we assume that neither A nor B is contained in a coset of a finite proper subgroup of G. We find then a subgroup H as in Theorem 1, so that H is finite, {0} ≨ H ≨ G (H is non-zero as the pair (A, B) is not elementary), and (\overline{A}, \overline{B}) is elementary of one of the types (II)–(IV); here and below in the proof \overline{A} and \overline{B} are defined by \overline{A} := φ_{G/H}(A) and \overline{B} := φ_{G/H}(B), as in Theorem 1. Write

A = A_{0} ∪ A_{1} ∪ ⋯ ∪ A_{m−1} and B = B_{0} ∪ B_{1} ∪ ⋯ ∪ B_{n−1},

where m, n ≥ 2, each of the sets A_{i} and B_{j} is contained in an H-coset, the cosets A_{i} + H are pairwise disjoint, and so are the cosets B_{j} + H. Renumbering the sets A_{i} and B_{j} we assume that if μ(A, B) = 1, then there exists c ∈ A + B with

ν_{c}(A_{0}, B_{0}) = ν_{c}(A, B) = 1,  (3)

and if μ(A, B) > 1 and π(A + B) = {0} then

A_{0} + B_{0} + H ⊈ A + B.  (4)

Furthermore, interchanging A and B, if necessary, we can assume that

|A_{0}| ≤ |B_{0}|.  (5)

We notice that for each i ∈ [1, m − 1] we have

|A_{0}| + |A_{i}| ≥ 2|H| − (|A + H| − |A|) ≥ |H| + 1,  (6)

and similarly,

|B_{0}| + |B_{j}| ≥ |H| + 1  (7)

for each j ∈ [1, n − 1].

If μ(A, B) = 1 then μ(A_{0}, B_{0}) = 1 by (3) and consequently

|A_{0}| + |B_{0}| ≤ |H| + 1  (8)

by the box principle. If, on the other hand, μ(A, B) > 1 and π(A+B) = {0}, then (8) (and in fact, the stronger estimate |A_{0}| + |B_{0}| ≤ |H|) follows from the box principle and (4). We see that (8) holds in any case, and comparing it with (6) and (7) we conclude that

|A_{i}| + |B_{j}| ≥ |H| + 1  (9)

for each i ∈ [1, m − 1] and j ∈ [1, n − 1]. Also,

|A_{i}| + |B_{0}| ≥ |A_{i}| + |A_{0}| ≥ |H| + 1  (10)

for each i ∈ [1, m−1] by (5) and (6). From (9) and (10) we conclude now that A_{i} +B_{j} is an H-coset for any i ∈ [1, m − 1] and j ∈ [0, n − 1].

It follows that A_{0} + B_{0} + H ∈ G/H has a unique representation as a sum of an element of \overline{A} and an element of \overline{B}: for, assuming A_{i} + B_{j} = A_{0} + B_{0} + H with i ∈ [1, m − 1] and j ∈ [1, n − 1], we obtain a contradiction with both (3) and (4). Thus, (\overline{A}, \overline{B}) is type (II) or (III), and in either case, each element of \overline{A} + \overline{B}, except A_{0} + B_{0} + H, has a representation as (A_{i} + H) + (B_{j} + H) with i ∈ [1, m − 1] and j ∈ [0, n − 1]; accordingly, A + B is a disjoint union of |\overline{A} + \overline{B}| − 1 = m + n − 2 full H-cosets and the “residual” set A_{0} + B_{0}. The number of elements of this residual set can now be easily estimated: if μ(A_{0}, B_{0}) = 1 then

|A_{0} + B_{0}| ≥ |A_{0}| + |B_{0}| − 1  (11)

by the theorem of Kemperman-Scherk, and if A + B is aperiodic then so is A_{0} + B_{0}, and hence (11) holds true by Kneser’s theorem. To complete the proof we notice that

|A_{0}| + |A_{1}| + ⋯ + |A_{m−1}| + |B_{0}| + |B_{1}| + ⋯ + |B_{n−1}| − 1

≥ |A + B| = (m + n − 2)|H| + |A_{0} + B_{0}| ≥ (m + n − 2)|H| + |A_{0}| + |B_{0}| − 1.

This shows that |A_{i}| = |B_{j}| = |H| for all i ∈ [1, m − 1], j ∈ [1, n − 1], and that equality holds in (11). □

Proof of Theorem 3. If A is contained in a coset of a finite proper subgroup of G then we can take this subgroup for H and the result follows as φ_{G/H}(A) is then a one-element set, hence an arithmetic progression. For the rest of the proof we assume that A is not contained in a coset of a finite proper subgroup.

Suppose that H < G is a finite subgroup such that

|A + H| − |A| ≤ |H| − 1 and A + H ≠ G.  (12)

Since A is not contained in an H-coset, we derive from (12) that 2|H| ≤ |A + H| < |A| + |H|, whence |H| < |A|. As H = {0} satisfies (12), there exists a finite subgroup H < G satisfying (12) and maximal in the sense that it is not properly contained in any other finite subgroup satisfying (12). We show that \overline{A} := φ_{G/H}(A) is either an arithmetic progression or a thick component of G/H.

Indeed, assume that |\overline{A}| ≥ 2 and that \overline{A} is not a thick component of G/H, so that |\overline{A}+\overline{B}| < min\{|G/H|−1, |\overline{A}|+|\overline{B}|\} for some finite subset \overline{B} ⊆ G/H with |\overline{B}| ≥ 2. By Theorem 2, either (\overline{A}, \overline{B}) is an elementary pair, or there exist a finite non-zero proper subgroup \overline{F} < G/H and subsets \overline{A}_{0} ⊆ \overline{A} and \overline{B}_{0} ⊆ \overline{B} such that both \overline{A}_{0} and \overline{B}_{0} are contained in \overline{F} -cosets, and both \overline{A}\\overline{A}_{0} and \overline{B}\\overline{B}_{0} are unions of \overline{F} -cosets. In the former case ((\overline{A}, \overline{B}) is an elementary pair) from min\{|\overline{A}|, |\overline{B}|\} ≥ 2, |\overline{A} + \overline{B}| ≤ |G/H| − 2, and the fact that \overline{A} is not contained in a finite proper coset of G/H it follows that \overline{A} is an arithmetic progression. In the latter case, writing F := φ_{G/H}^{−1}(\overline{F}), we get

|A + F | = |\overline{A} + \overline{F} ||H| ≤ (|\overline{A}| + |\overline{F} | − 1)|H| = |A + H| + |F | − |H| ≤ |A| + |F | − 1,

whence A + F = G by maximality of H. Thus \overline{A} + \overline{F} = G/H and therefore

|\overline{A}| = |G/H| − |\overline{F} | + |\overline{A}_{0}| ≥ |G/H| − |\overline{F} | + 1,
|A| > |A + H| − |H| = (|\overline{A}| − 1)|H| ≥ (|G/H| − |\overline{F} |)|H| = |G| − |F |.

Now |A| ≤ |G|/2 gives |F | > |G|/2 and hence F = G, contradicting \overline{F} ≨ G/H. □

16 VSEVOLOD F. LEV

Proof of Theorem 4. Clearly, the period P := π(A+B) is finite and satisfies A+P ≠ G in view of A + B ≠ G. Furthermore, |A + P | − |A| ≤ |P | − 1 by Kneser’s theorem, and if P is non-zero then the assertion follows. Suppose now that P = {0}; that is, A + B is aperiodic. In this case the pair (A, B) satisfies (2) and we find subsets A_{0} ⊆ A and B_{0} ⊆ B and a non-zero subgroup H ≤ G as in Kemperman’s theorem.

If H is infinite or H = G then (A, B) is an elementary pair. Moreover, if A is not an arithmetic progression, as we can assume, then (A, B) is elementary of type (III) or (IV); thus, there is a finite subgroup F ≤ G such that A is contained in a coset of F and |A + B| ≥ |F | − 1. Since |A + B| ≤ |G| − 2, we have F ≠ G. This shows that A is contained in a coset of a proper subgroup, and the assertion follows.

Finally, consider the case where H is a finite proper subgroup of G. Then |A+H|− |A| ≤ |H|−1 and we may assume that A+H = G; that is, there exist g_{1}, …, g_{n−1} ∈ G such that A is the disjoint union A = A_{0}∪(g_{1}+H)∪⋯∪(g_{n−1}+H). Since A_{0}+B_{0}+H has a unique representation as an element of φ_{G/H}(A) and an element of φ_{G/H}(B), we have B = B_{0}. If A_{0} is not an arithmetic progression, then, as above, the pair (A_{0}, B_{0}) is elementary of type (III) or (IV), and there exists a non-zero subgroup F ≤ H such that A_{0} is contained in a coset of F and |A_{0} + B_{0}| ≥ |F | − 1. The last estimate shows that F ≠ H: for the complement of A + B in G is the complement of A_{0} + B_{0} in the corresponding coset of H, and if F = H then this complement contains at most one element. To complete the proof we observe that A + F ≠ G and |A + F | − |A| ≤ |F | − 1. □

We now turn to small doubling sets in the elementary abelian groups (ℤ/2ℤ)^{r} and the proof of Theorem 5. Our first observation is that μ(A, A) ≥ 2 holds for any subset A ⊆ (ℤ/2ℤ)^{r} with |A| ≥ 2; therefore, for B = A Kemperman’s condition (2) reduces to π(2A) = {0}. We need several lemmas.

Lemma 1. Let r ≥ 1 be an integer. If H ≤ (ℤ/2ℤ)^{r} is a subgroup, h_{0} ∈ H, and S ⊆ H is an h_{0}-antisymmetric subset, then 2S = H \ (h_{0} + π(S)). In particular, if S is aperiodic, then 2S = H \ {h_{0}}.

Proof. Let h ∈ H. In order for h ∉ 2S to hold it is necessary and sufficient that (S + h) ∩ S = ∅; equivalently, S + h = H \ S, or S + h = h_{0} + S. The last condition can be re-written as h + h_{0} ∈ π(S), or h ∈ h_{0} + π(S). □

Lemma 2. Let r ≥ 1 be an integer. For a subset A ⊆ (ℤ/2ℤ)^{r}, the pair (A, A) is elementary if and only if A is a shift of an aperiodic antisymmetric subset of a subgroup of (ℤ/2ℤ)^{r}; that is, if there exist an element g ∈ (ℤ/2ℤ)^{r}, a non-zero subgroup H ≤ (ℤ/2ℤ)^{r}, a subgroup element h_{0} ∈ H, and an aperiodic h_{0}-antisymmetric subset S ⊆ H so that A = g + S.

Proof. It is easily seen that if H, S, g, and h_{0} are as indicated, then (A, A) is elementary of type (I) (if |A| = 1) or of type (IV) (if |A| > 1).

On the other hand, if (A, A) is elementary of type (I) then |A| = 1 and we can take g to be the element of A, set S = {0}, choose for H an arbitrary two-element subgroup, and let h_{0} be the non-zero element of this subgroup. Next, it is plain that (A, A) cannot be elementary of type (II), unless |A| = 1 (there are no nontrivial arithmetic progressions in (ℤ/2ℤ)^{r}). Moreover, (A, A) cannot be of type (III) either: for equality |g_{1} + (H_{1} ∪ {0})| = |g_{2} − (H_{2} ∪ {0})| yields |H_{1}| = |H_{2}|, whence |H_{1}| + |H_{2}| + 1 is odd. Finally, if (A, A) is of type (IV), then A = g_{1} + H_{1} = g_{2} + H_{2} whence A + g_{1} = H_{1} = (g_{1} + g_{2}) + H_{2} is a (g_{1} + g_{2})-antisymmetric subset of H. □

Lemma 3. Let r ≥ 1 be an integer and suppose that A ⊆ (ℤ/2ℤ)^{r} satisfies π(2A) = {0}. Then |2A| < 2|A| holds if and only if (A, A) is an elementary pair.

Proof. We have to show that if A satisfies |2A| ≤ 2|A| − 1 and π(2A) = {0}, then (A, A) is an elementary pair. Without loss of generality, we assume that A is not contained in a coset of a proper subgroup of (ℤ/2ℤ)^{r}. If (A, A) is not elementary then we find H ≨ (ℤ/2ℤ)^{r} as in Theorem 2, as applied with B = A. In view of \overline{B} = \overline{A} (we keep using the notation of Theorem 2) and since there is an element in G/H with a unique representation as a sum of an element of \overline{A} and an element of \overline{B}, we have then |\overline{A}| = 1; this, however, contradicts the assumption that A is not contained in a coset of a proper subgroup. □

Proof of Theorem 5. For brevity and to avoid double indexation, we write G = (ℤ/2ℤ)^{r} throughout the proof.

Suppose that |2A| < 2|A| and let H := π(2A). If |2A| = |H|, then A is contained in an H-coset and |A| > |2A|/2 = |H|/2. Assuming now that |2A| ≥ 2|H|, write \overline{A} := φ_{G/H}(A). Since |2\overline{A}| < 2|\overline{A}| (as it follows from Kneser’s theorem) and π(2\overline{A}) = \{0\}, by Lemmas 3 and 2 we have \overline{A} = \overline{z} + \overline{S}, where \overline{z} ∈ G/H and \overline{S} is an aperiodic antisymmetric subset of a non-zero subgroup \overline{F} ≤ G/H. From |2A| ≥ 2|H| we derive that |\overline{S}| = |\overline{A}| ≥ 2 and in fact |\overline{S}| > 2, for any two-element subset of an elementary abelian 2-group is periodic; therefore, |\overline{F} | = 2|\overline{S}| ≥ 8. Choose a subgroup F ≤ G such that φ_{G/H}^{−1}(\overline{F}) = F ⊕ H and a subset S ⊆ F such that φ_{G/H}(S) = \overline{S}; thus, |F | = |\overline{F} | and |S| = |\overline{S}|. It is easily seen that S is antisymmetric (if \overline{S} is φ_{G/H}(f)- antisymmetric for some f ∈ F, then S is f-antisymmetric) and aperiodic (if S+g = S for some g ∈ G, then \overline{S} + φ_{G/H}(g) = \overline{S}, hence φ_{G/H}(g) = 0, g ∈ H, and therefore g = 0 as g ∈ 2S ⊆ F). Next, from \overline{A} = \overline{z} + \overline{S} it follows that A ⊆ z + S + H, where z is an (arbitrarily selected) element of G such that φ_{G/H}(z) = \overline{z}. Furthermore, 2\overline{A} = \overline{F} \ \{\overline{f}\} with some \overline{f} ∈ \overline{F} holds by Lemma 1, whence 2A = (F ⊕ H) \ (f + H) for the appropriate choice of f ∈ F. (Recall that H = π(2A).) Finally, in view of

2|A| > |2A| = |F ||H| − |H| = 2|S||H| − |H| = 2|S + H| − |H|

we have |S + H| − |A| < |H|/2.

Now suppose that F, H, S, and A is as in the second part of the theorem, and to simplify the notation assume that A is obtained by removing elements from the zero shift of the set S + H. For each s ∈ S we have then |(s + H) \ A| < |H|/2, whence |(s + A) ∩ H| > |H|/2 and therefore H ⊆ (s_{1} + A) + (s_{2} + A) = s_{1} + s_{2} + 2A for any s_{1}, s_{2} ∈ S. It follows that s_{1} + s_{2} + H ⊆ 2A and hence 2S + H = 2A. Applying Lemma 1 we obtain

|2A| = (|F | − |π(S)|)|H| ≤ 2|S||H| − |H| = 2|S + H| − |H| < 2|A|,

which completes the proof. □

Appendix: On elementary pairs of types III and IV

The following two propositions shed some light on the definitions of elementary pairs of types (III) and (IV). We prove the first proposition only; the proof of the second is quit similar and we leave it to the reader.

Proposition 1. Suppose that G is an abelian group.

(i) Let H be a finite subgroup of G, and let (A, B) be a pair of subsets of G with min{|A|, |B|} ≥ 2, satisfying (1) and (2) and such that A + B is a coset of H. Then there exist a partition H = H_{1} ∪ H_{2} ∪ {0} and elements g_{1}, g_{2} ∈ G such that A = g_{1} + (H_{1} ∪ {0}) and B = g_{2} − (H_{2} ∪ {0}).

(ii) Let H = H_{1} ∪ H_{2} ∪ {0} be a partition of a finite subgroup H ≤ G with nonempty subsets H_{1}, H_{2}, let g_{1}, g_{2} be elements of G, and set A := g_{1} + (H_{1} ∪ {0}) and B := g_{2} − (H_{2} ∪ {0}). Then the pair (A, B) satisfies (1) and (2), and A + B is a coset of H.

(iii) Let H, H_{1}, H_{2}, g_{1}, g_{2}, A, B be as in (ii) and suppose that some group element c ≠ g_{1} + g_{2} satisfies ν_{c}(A, B) = 1. Write f := c − g_{1} − g_{2} (so that f ∈ H), denote by F the subgroup of H, generated by f, and let \overline{A} := φ_{G/F} (A) and \overline{B} := φ_{G/F} (B). Then |\overline{A} + \overline{B}| = |\overline{A}| + |\overline{B}| − 1 and \overline{A} + \overline{B} is a coset of H/F. Furthermore, A is a union of F -cosets and an arithmetic progression A_{0} with

CRITICAL PAIRS AND KEMPERMAN’S THEOREM 19

difference f, and B is a union of F -cosets and an arithmetic progression B_{0} with difference f; moreover, A_{0} + B_{0} is an F -coset, |A_{0} + B_{0}| = |A_{0}| + |B_{0}| − 1, μ(A_{0}, B_{0}) = 1, and A_{0} +B_{0}, considered as an element of G/F, has a unique representation as an element of \overline{A} and an element of \overline{B}.

Proof of Proposition 1. (i) We assume without loss of generality that A, B ⊆ H, so that A + B = H. Since π(A + B) = H ≠ {0} in view of min{|A|, |B|} ≥ 2, we have μ(A, B) = 1 by (2). Shifting A and B, if necessary, we assume that 0 ∈ A ∩ B and ν_{0}(A, B) = 1. Write H_{1} := A \ {0} and H_{2} := −B \ {0}; then |H_{1}| + |H_{2}| = |A|+|B|−2 = |A+B|−1 = |H|−1 by (1) and the theorem of Kemperman-Scherk, and H_{1} ∩ H_{2} = ∅: for h ∈ H_{1} ∩ H_{2} leads to the “forbidden” representation 0 = h + (−h).

(ii) See a remark in Section 3, following the definition of elementary pairs.

(iii) We can assume that g_{1} = g_{2} = 0. Fix a_{0} ∈ A and b_{0} ∈ B with c = a_{0} + b_{0}. Then the two sets A \ {a_{0}} − c and −B are disjoint, and since −B = H_{2} ∪ {0} is the complement in H of H_{1}, we have A \ {a_{0}} − c ⊆ H_{1}. Indeed, from |A \ {a_{0}}| = |H_{1}| it follows that A \ {a_{0}} − c = H_{1}, which can be rewritten as A \ {a_{0}} = (A + c) \ {c}. This shows that shifting A by c results in the same effect as replacing a_{0} with c. Thus, we can write A = A_{0} ∪ A_{1} ∪ ⋯ ∪ A_{m−1}, where m ≥ 1 is an integer, A_{i} + F = A_{i} for i ∈ [1, m − 1], and A_{0} is an arithmetic progression with difference c. (Recall, that F is the subgroup, generated by c.) Similarly, we have B = B_{0} ∪ B_{1} ∪ ⋯ ∪ B_{n−1}, where n ≥ 1 is an integer, B_{i} + F = B_{i} for i ∈ [1, n − 1], and B_{0} is an arithmetic progression with difference c. Clearly, the numeration can be so chosen that if A_{0} is a full coset of F, then a_{0} ∈ A_{0}, and similarly if B_{0} is a full coset of F, then b_{0} ∈ B_{0}.

From |A| + |B| = |H| + 1 ≡ 1 (mod |F |) we derive that |A_{0}| + |B_{0}| ≡ 1 (mod |F |), so that in fact |A_{0}| + |B_{0}| = |F | + 1, and it follows that A_{0} + B_{0} is an F -coset, |A_{0} + B_{0}| = |A_{0}| + |B_{0}| − 1, and μ(A_{0}, B_{0}) = 1. Since

|\overline{A}| + |\overline{B}| = (|A| + |F | − |A_{0}|)/|F | + (|B| + |F | − |B_{0}|)/|F | = (|A| + |B| − 1)/|F | − (|A_{0}| + |B_{0}| − 1)/|F | + 2 = |H/F | + 1,

we have \overline{A} + \overline{B} = H/F and |\overline{A} + \overline{B}| = |\overline{A}| + |\overline{B}| − 1.

It remains to show that A_{0} +B_{0} has a unique representation as a sum of an element of \overline{A} and an element of \overline{B}. To this end we recall that if A_{0} is a coset of F, then a_{0} ∈ A_{0}, and we claim now that this conclusion stays true if A_{0} is not a coset of F; for, in this latter case we have |B_{0}| = |F | + 1 − |A_{0}| ≥ 2, so that if a_{0} ∈ A_{i} with i ∈ [1, m − 1], then c = a_{0} + b_{0} cannot satisfy ν_{c}(A, B) = 1. Similarly, b_{0} ∈ B_{0} holds, and therefore an equality of the form A_{0} + B_{0} = A_{i} + B_{j} with i ∈ [1, m − 1], j ∈ [1, n − 1] would yield a “forbidden” representation of c = a_{0} + b_{0}. □

20 VSEVOLOD F. LEV

Proposition 2. Suppose that G is an abelian group.

(i) Let H be a finite subgroup of G, and let (A, B) be a pair of non-empty subsets of G, satisfying (1) and (2) and such that A+B is a coset of H with one element removed. Then there exist a partition H = H_{1}∪H_{2} with π(H_{1}) = π(H_{2}) = {0} and elements g_{1}, g_{2} ∈ G such that A = g_{1} + H_{1} and B = g_{2} − H_{2}.

(ii) Let H = H_{1} ∪ H_{2} be a partition of a finite subgroup H ≤ G with non-empty aperiodic subsets H_{1}, H_{2}, let g_{1}, g_{2} be elements of G, and set A := g_{1} + H_{1} and B := g_{2} −H_{2}. Then the pair (A, B) satisfies (1) and (2), and A+B is a coset of H with one element removed.

(iii) Let H, H_{1}, H_{2}, g_{1}, g_{2}, A, B be as in (ii) and suppose that some group element c satisfies ν_{c}(A, B) = 1. Write f := c − g_{1} − g_{2} (so that f ∈ H), denote by F the subgroup of H, generated by f, and let \overline{A} := φ_{G/F} (A) and \overline{B} := φ_{G/F} (B). Then |\overline{A} + \overline{B}| = |\overline{A}| + |\overline{B}| − 1 and \overline{A} + \overline{B} is a coset of H/F. Furthermore, A is a union of F -cosets and an arithmetic progression A_{0} with difference f, and B is a union of F -cosets and an arithmetic progression B_{0} with difference f; moreover, A_{0} + B_{0} is an F -coset with one element removed, |A_{0} + B_{0}| = |A_{0}| + |B_{0}| − 1, and A_{0} + B_{0} + F, considered as an element of G/F, has a unique representation as an element of \overline{A} and an element of \overline{B}.

Acknowledgement

The author is grateful to the referee for a careful reading of the paper and a number of valuable remarks.

References

[DF] J.-M. Deshouillers and G. Freiman, A step beyond Kneser’s theorem for abelian finite groups, Proc. London Math. Soc. (3) 86 (1) (2003), 1–28.

[DHP04] J.-M. Deshouillers, F. Hennecart, and A. Plagne, On small sumsets in (ℤ/2ℤ)^{n}, Combinatorica 24 (1) (2004), 53–68.

[H01] Y.O. Hamidoune, Some results in additive number theory, I: The critical pair theory, Acta Arithmetica 96 (2) (2000), 97–119.

[HP02] Y.O. Hamidoune and A. Plagne, A generalization of Freiman’s 3k − 3 theorem, Acta Arithmetica 103 (2) (2002), 147–156.

[HP04] Y.O. Hamidoune and A. Plagne, A new critical pair theorem applied to sum-free sets in Abelian groups, Comment. Math. Helv. 79 (2004), 183–207.

[HP03] F. Hennecart and A. Plagne, On the subgroup generated by a small doubling binary set, European J. Combin. 24 (1) (2003), 5–14.

[K60] J.H.B. Kemperman, On small sumsets in an abelian group, Acta Mathematica 103 (1960), 63–88.

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

[K55] M. Kneser, Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen, Math. Z. 61 (1955), 429–434.

[L05] V.F. Lev, Restricted set addition in abelian groups: results and conjectures, Journal de Théorie des Nombres de Bordeaux (Journées Arithmétiques 2003 special issue) 17 (2005), 191–203.

[M65] H. B. Mann, Addition Theorems: The Addition Theorems of Group Theory and Number Theory, Interscience Publishers, a division of John Wiley and Sons, New York, 1965.

Department of Mathematics, The University of Haifa at Oranim, Tivon 36006, Israel

  E-mail address: seva@math.haifa.ac.il