ON SMALL SUMSETS IN ABELIAN GROUPS

VSEVOLOD F. LEV

Abstract. In this paper we investigate the structure of those pairs of finite subsets of an abelian group whose sums have relatively few elements: |A + B| < |A| + |B|. In 1960, J. H. B. Kemperman gave an exhaustive but rather sophisticated description of recursive nature. Using intermediate results of Kemperman, we obtain below a description of another type. Though not (generally speaking) sufficient, our description is intuitive and transparent and can be easily used in applications.

1. Introduction

By G we denote an abelian group. A finite non-empty subset S ⊆ G is said to be an arithmetic progression with difference d if S is of the form

S = {a + id: i = 1, …, |S|} (a, d ∈ G).

If, in addition, the order of the group element d satisfies ord d ≥ |S| + 2, then we say that S is a true arithmetic progression.

Let A and B be finite subsets of G. We write

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

and consider the following condition:

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

The aim of this paper is to prove the following

Main Theorem . Let A and B satisfy (∗), and suppose that max{|A|, |B|} > 1. Then there exist a finite subgroup H ⊆ G and two finite subsets S_{1}, S_{2} ⊆ G such that A ⊆ S_{1} + H, B ⊆ S_{2} + H, and one of the following holds:

i) |S_{1}| = |S_{2}| = 1, and |A + B| ≥ \frac{1}{2}|H| + 1; ii) |S_{1}| = 1, |S_{2}| > 1, and |A + B| ≥ (|S_{2}| − 1)|H| + 1; iii) |S_{1}| > 1, |S_{2}| = 1, and |A + B| ≥ (|S_{1}| − 1)|H| + 1; iv) min{|S_{1}|, |S_{2}|} > 1, and |A + B| ≥ (|S_{1}| + |S_{2}| − 2)|H| + 1; moreover, S_{1} and

S_{2} are true arithmetic progressions with common difference d of order at least ord d ≥ |S_{1}| + |S_{2}| + 1.

2 VSEVOLOD F. LEV

It can be easily verified that the conclusion of Main Theorem implies

|A + B + H| − |A + B| ≤ |H| − 1

in cases ii)–iv), and

|A + B + H| − |A + B| ≤ \frac{1}{2}|H| − 1

in case i): just observe that

|A + B + H| ≤ |S_{1} + S_{2} + H| ≤ |S_{1} + S_{2}||H|.

The Main Theorem will be proved in Section 3. Now, we give two definitions. We say that the subgroup H ⊆ G, |H| ≥ 2 is a period of the finite subset C ⊆ G

if C is a union of one or more H-cosets, that is if C + H = C. In this case C is called periodic and we write H = P (C).

We say that the subgroup H ⊆ G, |H| ≥ 2 is a quasi-period of the finite subset C ⊆ G, if C is a union of one or more H-cosets and possibly a subset of yet another H-coset. In this case C is called quasi-periodic and we write H = Q(C).

If H = P (C), we also say that H is a true period of C, as opposed to H = Q(C), when C is a quasi-period. Obviously, if H = P (C) or H = Q(C) then |H| < ∞. Notice that according to the above definitions each periodic set is also quasi-periodic.

2. Auxiliary results

The following deep result due to Kemperman (see [1]) plays the central role in our proof.

Theorem 1 (Kemperman). Let A and B be finite subsets of G such that (∗) holds and min{|A|, |B|} > 1. Then either A + B is an arithmetic progression or A + B is quasi-periodic.

Corollary 1. Under the assumptions of Theorem 1, one of the following holds: i) A + B is in true arithmetic progression; ii) A + B = c + H \ {0} where H ⊆ G is a subgroup, and c ∈ G — an element

of G; iii) A + B is quasi-periodic.

The next lemma also originates in [1].

Lemma 1 (Kemperman). Suppose that (∗) holds and that A+B is in true arithmetic progression of difference d. Then also A and B are in true arithmetic progressions with the same difference d. Moreover, in (∗) equality holds, and therefore ord d ≥ |A| + |B| + 1.

We need three more lemmas.

Lemma 2. Let A and B be finite non-empty subsets of G, and let H ⊆ G be a finite non-zero subgroup of G, satisfying

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

Then H = P (A + B).

Proof. We choose c = a + b ∈ A + B and h ∈ H and we prove that c + h ∈ A + B. We have:

|(a + H) ∩ \overline{A}| + |(b + H) ∩ \overline{B}| ≤ |(A + H) ∩ \overline{A}| + |(B + H) ∩ \overline{B}| < |H|,

hence

|(a + H) ∩ A| + |(b + H) ∩ B| > |H|,
|H ∩ (A − a)| + |h − H ∩ (B − b)| > |H|,

and therefore there exist h_{a}, h_{b} ∈ H such that

h_{a} = h − h_{b}, h_{a} = a′ − a, h_{b} = b′ − b (a′ ∈ A, b′ ∈ B).

But then c + h = a + b + h_{a} + h_{b} = a′ + b′ ∈ A + B which was to be proved. □

Lemma 3. Let A, B ⊆ G satisfy (∗). Suppose that A+B is quasi-periodic, and write H = Q(A + B). Denote by σ the canonical homomorphism σ: G → G/H, and set A_{1} = σA, B_{1} = σB. Then

i) |A_{1} + B_{1}| ≤ |A_{1}| + |B_{1}| − 1; ii) |A_{1} + B_{1}| < |A + B|; iii) |A + B| − 1 ≥ (|A_{1} + B_{1}| − 1)|H|.

Proof. i) Suppose first that H = P (A+B). Obviously, |A+B| ≤ |A+H|+|B+H|−1. But the left-hand side, as well as |A+H| and |B +H|, divides by |H|, so we also have |A+B| ≤ |A+H|+|B +H|−|H|. Eventually, |A+H| = |A_{1}||H|, |B +H| = |B_{1}||H| and |A + B| = |A_{1} + B_{1}||H|.

Now consider the situation, when H is a quasi-period, but not a true period of A + B. Then by Lemma 2,

|A + B| + 1 ≤ |A| + |B| ≤ |A + H| + |B + H| − |H|,

hence (since the right-hand side divides by |H|) we also have |A + B + H| ≤ |A + H| + |B + H| − |H|, and the proof finishes as in the case H = P (A + B).

ii) Follows from iii).

4 VSEVOLOD F. LEV

iii) If H = P (A + B), then

|A + B| − 1 = |A_{1} + B_{1}||H| − 1 > (|A_{1} + B_{1}| − 1)|H|.

If H is not a true period of A+B, then A+B contains |A_{1}+B_{1}|−1 full H-cosets, and at least one element in yet another H-coset, therefore |A+B| ≥ (|A_{1}+B_{1}|−1)|H|+1. □

Lemma 4. Let A + B = c + H \ {0} and suppose that min{|A|, |B|} ≥ 2, where A, B ⊆ G are subsets, H ⊆ G a subgroup, and c ∈ G an element of G. Then |H| ≥ 4.

Proof. We have: |H|−1 = |A+B| ≥ |A| ≥ 2, hence |H| ≥ 3. Suppose |H| = 3, and so |A| = |B| = |A + B| = 2. Let A = a + {0, d_{1}}, B = b + {0, d_{2}}. Then A + B = a + b + {0, d_{1}, d_{2}, d_{1} +d_{2}}, hence d_{2} = d_{1}, d_{1} +d_{2} = 0, and H = {0}∪{a+b−c, a+b+d−c}, where d = d_{1} = d_{2}, 2d = 0. Therefore d = (a + b + d − c) − (a + b − c) ∈ H, which contradicts to |H| = 3, 2d = 0. □

3. Proof of the Main Theorem

Denote G_{0} = G, A_{0} = A, B_{0} = B and consider the following conditions: 1) |A| = |B| = 1;

2) |A| = 1, |B| > 1;

3) |A| > 1, |B| = 1;

4) A + B = c + H̃ \ {0}, where H̃ is a subgroup, and c ∈ G — an element of G;

5) A + B is in true arithmetic progression. If all these conditions fail, then by Corollary 1 the sum A_{0} + B_{0} is quasi-periodic, and we put H_{1} = Q(A_{0} + B_{0}), G_{1} = G_{0}/H_{1}, denote by σ_{1} the canonical homomorphism σ_{1} : G_{0} → G_{1} and set A_{1} = σ_{1}A_{0}, B_{1} = σ_{1}B_{0}, so that A_{1}, B_{1} satisfy (∗) by Lemma 3, i). Now check, whether some of the conditions 1)–5) is met with G_{1}, A_{1}, B_{1} substituted for G, A, B. If not, we continue the process by defining

H_{2} = Q(A_{1} + B_{1}), G_{2} = G_{1}/H_{2},
σ_{2} : G_{1} → G_{2}, A_{2} = σ_{2}A_{1}, B_{2} = σ_{2}B_{1}

and so on. At each step we obtain a pair of subsets A_{i}, B_{i} ⊆ G_{i}, satisfying (∗) and also |A_{i} + B_{i}| < |A_{i−1} + B_{i−1}| (by Lemma 3, ii)). Eventually we obtain a pair A_{k}, B_{k} ⊆ G_{k} (k ≥ 0), which meets at least one of the conditions 1)–5). We write σ = σ_{k} ⋯ σ_{1} : G → G_{k} (or σ = id_{G} in the case k = 0) so that A_{k} = σA, B_{k} = σB, and we write H = σ^{−1}H̃ if the first condition met is 4), or H = ker σ otherwise. We distinguish 5 cases according to the first condition satisfied.

ON SMALL SUMSETS IN ABELIAN GROUPS 5

1) Here k > 0 and A_{k−1} + B_{k−1} = c + H_{k}, where c ∈ G_{k−1} (since H_{k} is a quasiperiod of A_{k−1} +B_{k−1}), therefore A_{k−1} ⊆ a+H_{k}, B_{k−1} ⊆ b+H_{k} (a, b ∈ G_{k−1}), whence A ⊆ a′ + H, B ⊆ b′ + H (a′, b′ ∈ G). We choose now S_{1} = {a′}, S_{2} = {b′} and observe, that by Lemma 3, iii)

|A + B| − 1 ≥ (|A_{1} + B_{1}| − 1)|H_{1}| ≥ ⋯ ≥
≥ (|A_{k−1} + B_{k−1}| − 1)|H_{k−1}| ⋯ |H_{1}| =
= (|H_{k}| − 1)|H_{k−1}| ⋯ |H_{1}| ≥
≥ \frac{1}{2}|H_{k}||H_{k−1}| ⋯ |H_{1}| = \frac{1}{2}|H|.

2) Also here we may assume k > 0, since otherwise the result is trivial if we choose S_{1} = A, S_{2} = B, H = {0}. Furthermore, as in 1) we have A ⊆ a + H. We choose S_{1} = {a}, and for S_{2} we choose the system of arbitrary representatives of all H-cosets, containing at least one element of B, so that A ⊆ S_{1} + H, B ⊆ S_{2} + H and |S_{2}| = |B_{k}|. Then

|A + B| − 1 ≥ ⋯ ≥ (|A_{k} + B_{k}| − 1)|H_{k}| ⋯ |H_{1}| = (|S_{2}| − 1)|H|.

3) This case is analogous to the previous one in view of the symmetry between A and B.

4) In this case there exist a, b ∈ G such that A ⊆ a + H, B ⊆ b + H and we choose S_{1} = {a}, S_{2} = {b}. Then

|A + B| − 1 ≥ ⋯ ≥ (|A_{k} + B_{k}| − 1)|H_{k}| ⋯ |H_{1}| =
= (|H̃| − 2)|H_{k}| ⋯ |H_{1}| ≥ \frac{1}{2}|H̃||H_{k}| ⋯ |H_{1}| = \frac{1}{2}|H|

(since |H̃| ≥ 4 by Lemma 4).

5) In this case, by Lemma 1, A_{k} and B_{k} are in true arithmetic progressions with common difference d of order ord d ≥ |A_{k}| + |B_{k}| + 1, and |A_{k} + B_{k}| = |A_{k}| + |B_{k}| − 1. It is easily seen that we can choose two true arithmetic progressions S_{1}, S_{2} ⊆ G with a common difference d′ in such a way, that A_{k} = σS_{1}, B_{k} = σS_{2} and |S_{1}| = |A_{k}|, |S_{2}| = |B_{k}|, ord d′ ≥ ord d. Then

A ⊆ S_{1} + H, B ⊆ S_{2} + H, ord d′ ≥ |S_{1}| + |S_{2}| + 1

and

|A + B| − 1 ≥ ⋯ ≥ (|A_{k} + B_{k}| − 1)|H_{k}| ⋯ |H_{1}| = (|S_{1}| + |S_{2}| − 2)|H|.

This completes the proof. □

6 VSEVOLOD F. LEV

References

[1] Kemperman J.H.B., On small sumsets in an abelian group, Acta Math., 103 (1960), 63–88. School of Math. Sciences, Tel-Aviv University, 69978 Tel-Aviv, Israel

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