RESTRICTED SET ADDITION IN GROUPS, III. INTEGER SUMSETS WITH GENERIC RESTRICTIONS

VSEVOLOD F. LEV

Dedicated to András Sárközy on the occasion of his 60th birthday

Abstract. Let A be a finite set of integers. Assuming that R ⊆ A × A is not “too large”, we give a lower-bound estimate for the cardinality of the restricted sumset

A +^{R} A := {a_{1} + a_{2} : a_{1}, a_{2} ∈ A, (a_{1}, a_{2}) ∉ R}

in terms of the cardinality and the length of A.

1. Background and motivation

Let A, B ⊆ G be two (finite, non-empty) subsets of the set of all elements of a group G. The sumset of A and B is

(1)  A + B := {a + b: a ∈ A, b ∈ B},

and the restricted sumsets are

(2)  A ˙+ B := {a + b: a ≠ b, a ∈ A, b ∈ B}

and

(3)  A +^{R} B := {a + b: (a, b) ∉ R, a ∈ A, b ∈ B},

where the “restriction set” R ⊆ A×B is an arbitrary subset of the Cartesian product. (Though we use additive notation, no commutativity is assumed, unless indicated explicitly.) Notice that (2) is a particular case of (3), obtained when R is induced by the equality relation: R = {(a, b) ∈ A × B: a = b}.

We are interested in the lower bounds for the cardinalities of sumsets (1)– (3). The non-restricted sumset A + B is well studied. The historically first result is due

to Cauchy and Davenport who have shown that

|A + B| ≥ min{p, |A| + |B| − 1}

for the group G = ℤ_{p} of residues modulo a prime p; equality is attained when A and B are arithmetic progressions modulo p sharing a common difference. A generalization onto arbitrary Abelian group G is due to Kneser, see Theorem D below. Kneser’s theorem is of utmost importance in many additive number theory problems. However, for the group of integers G = ℤ it only gives the estimate |A+B| ≥ |A|+|B|−1; this is best possible (consider again progressions with common difference) but nearly trivial and practically useless. Subtler estimates which take into account the “lengths” of A and B are due to Freiman [F59], Smeliansky and the present author [LS95], and Stanchescu [S98]. The case B = A was settled by Freiman.

1991 Mathematics Subject Classification. Primary: 11B75; Secondary: 11P99, 05C25, 05C35.

Partially supported by the Edmund Landau Center for Research in Mathematical Analysis and Related Areas, sponsored by the Minerva Foundation (Germany).

Theorem A (Freiman). Let A ⊆ [0, l] be a set of n = |A| ≥ 2 integers such that 0, l ∈ A and gcd(A) = 1. Then

|A + A| ≥ \begin{cases}l + n, & if l ≤ 2n − 3, \\ 3n − 3, & if l ≥ 2n − 2. \end{cases}

Due to space limitations, we cannot discuss here numerous far-going extensions of this remarkable result.

Considerably less is known about the restricted sumset A ˙+ B. Instead of Cauchy-Davenport theorem, we have

|A ˙+ B| ≥ min{|A| + |B| − 3, p} (A, B ⊆ ℤ_{p})

conjectured by Erdős and Heilbronn in [EG80] and proved by Dias da Silva and Hamidoune in [DH94]. (Another and simpler proof which also gives a series of more general results is due to Alon, Nathanson, and Ruzsa, see [ANR95, ANR96].) No analogue of Kneser’s theorem for restricted sumsets has been proved, but the following was conjectured in [L00]. Given an arbitrary group G we define its doubling constant L = L(G) as the maximum number of pairwise distinct elements of G that share a common doubling:

L := max_{\begin{matrix}g_{1},...,g_{λ}∈G \\ g_{i}≠g_{j} (1≤i<j≤λ) \\ 2g_{1}=...=2g_{λ} \end{matrix}} λ.

Conjecture 1 (Lev, [L00]). Let G be an Abelian group with the doubling constant L = L(G). Then

|A ˙+ B| ≥ |A| + |B| − (L + 2)

for any finite A, B ⊆ G such that A ˙+ B ≠ A + B.

For the case B = A we were able to prove a somewhat weaker estimate (with the commutativity requirement dropped, however).

Theorem B (Lev, [L00]). Let G an arbitrary group with the doubling constant L = L(G). Then

|A ˙+ A| ≥ θ|A| − (L + 2); θ = (1 + \sqrt{5})/2 ≈ 1.61

for any finite A ⊆ G such that A ˙+ A ≠ A + A.

This theorem was used to prove a result for G = ℤ which is parallel to Freiman’s Theorem A.

Theorem C (Lev, [L00]). Let A ⊆ [0, l] be a set of n = |A| ≥ 2 integers such that 0, l ∈ A and gcd(A) = 1. Then

|A ˙+ A| ≥ \begin{cases}l + n − 2, & if l ≤ 2n − 5, \\ (θ + 1)n − 6, & if l ≥ 2n − 4, \end{cases}

where θ = (1 + \sqrt{5})/2.

Conjecturally, (θ + 1)n − 6 can be replaced by 3n − 7, provided n ≥ 7.

A general result that relates the cardinalities of sumsets (1) and (2) was recently obtained by Schoen (see [S00]):

|A ˙+ B| ≥ (1 − γ (ln |A + B|)^{−1/16}) |A + B|,

where A and B are finite subsets of either the set of integers or the set of residues modulo an integer m > 1, and γ > 0 is an (unspecified) absolute constant.

Restricted sumset A +^{R} B is almost unexplored. Good estimates are known for the group G = ℤ_{p} only: the method of [ANR95, ANR96] allows one to handle polynomial restriction sets R = {(a, b) ∈ A × B: P (a, b) = 0} (where P is a polynomial over

ℤ_{p} in two variables) and gives sharp estimates of |A +^{R} B| in terms of |A|, |B|, and deg P, and in [L01] generic restriction sets R are considered and sharp estimates in terms of |A|, |B|, and |R| are given. For groups other than ℤ_{p} no sharp estimates

of |A +^{R} B| are known, though some non-trivial results were obtained in [L01] under certain assumptions on R. Sumset (3) in the group of integers G = ℤ is terra incognita.

2. Summary of results

Let K and s be non-negative integer numbers. We denote by R_{K,s}(A, B) the family of all subsets R ⊆ A × B satisfying the following conditions:

(a) to any fixed element a ∈ A there correspond at most s elements b ∈ B such that (a, b) ∈ R;

(b) to any fixed element b ∈ B there correspond at most s elements a ∈ A such that (a, b) ∈ R;

(c) any element c ∈ A + B has at most K representations c = a + b; (a, b) ∈ R. We note that if R is induced by the equality relation, then R ∈ R_{L(G),1}(A, B).

Our main result is the following analog of Theorems A and C.

Theorem 1. Let A ⊆ [0, l] be a set of n = |A| ≥ 3 integers such that 0, l ∈ A and gcd(A) = 1. Suppose that R ∈ R_{K,s}(A, A). Then

|A +^{R} A| ≥ \begin{cases}l + n − 2s, & if l ≤ 2n − 2K − 3, \\ (θ + 1)n − 4s − 2K − θ, & if l ≥ 2n − 2K − 2, \end{cases}

where θ = (\sqrt{5} + 1)/2.

To prove Theorem 1 we employ a version of the argument, used in [L00] (this argument originates from [LS95] and was applied in a number of our subsequent papers). Roughly speaking, our method combines two steps. First, we relate the

cardinalities of |A +^{R} A| and |Ā +^{\overline{R}} Ā|, where Ā is the canonical image of A in ℤ_{l}, and

\overline{R} ⊆ Ā × Ā is a suitably defined restriction set. Second, we show that Ā +^{\overline{R}} Ā is large, unless we are in a certain special situation. The central ingredient of this second step is the following result, which strengthens [L01, Theorem 4] in the particular case of B = A.

Theorem 2. Let A ⊆ G be a set of n = |A| ≥ 2 elements of an arbitrary group G,

and let R ∈ R_{K,s}(A, A). Suppose that A +^{R} A ≠ A + A.^{1)} Then

|A +^{R} A| > θn − K − 2s; θ = (\sqrt{5} + 1)/2.

(Observe that in this theorem we do not assume that G is Abelian.)

Theorems 1 is proved in Section 5 and Theorem 2 in Section 4.

3. Auxiliary results

We give here two results that will be used to deduce Theorem 1 from Theorem 2: a simple estimate of the cardinality of restricted sumset (3) and Kneser’s theorem, mentioned in Section 1.

Lemma 1. Let A and B be two (finite, non-empty) sets of integers, and suppose that R ∈ R_{K,s}(A, B). Then

|A +^{R} B| ≥ |A| + |B| − 2s − 1.

Proof. Write A = {a_{1}, …, a_{n}} and B = {b_{1}, …, b_{m}}, where a_{1} < … < a_{n} and b_{1} < … < b_{m}. Then among the m + n − 1 distinct sums

a_{1} + b_{1}, …, a_{1} + b_{m−1}, a_{1} + b_{m}, a_{2} + b_{m}, …, a_{n} + b_{m}

at most 2s do not belong to A +^{R} B. □

For a subset C ⊆ G of the set of elements of an Abelian group G, the period of C is defined by

H(C) := {g ∈ G: C + g = C}.

Evidently, H(C) is a subgroup of G, and C consists of a number of H(C)-cosets.

Theorem D (Kneser [K53, K55]). Let A and B be (finite, non-empty) subsets of the set of elements of an Abelian group G. Suppose that |A + B| ≤ |A| + |B| − 1. Then

|A + B| = |A + H| + |B + H| − |H|,

where H = H(A + B) is the period of A + B.

4. Proof of Theorem 2

Assume that |A +^{R} A| ≤ θn − K − 2s. We break the proof in four steps.

i) For g ∈ G, denote by ν(g) the number of representations g = a_{1}+a_{2} with a_{1}, a_{2} ∈ A.

Evidently, there exists σ ∈ A + A (and even σ ∈ A +^{R} A) such that

ν(σ) ≥ \frac{n^{2} − |R|}{|A +^{R} A|} ≥ \frac{n^{2} − ns}{θn − K − 2s} > \frac{n(n − s)}{θ(n − s)} = (θ − 1)n.

ii) Suppose that c = −a_{1} + a_{2} ∈ −A + A. Since

|(a_{i} + A) \ (A +^{R} A)| ≤ s (i = 1, 2),

1)This condition is discussed in depth in [L00] and [L01].

we have

|(a_{1} + A) ∪ (a_{2} + A)| ≤ |A +^{R} A| + 2s ≤ θn − K,

whence

|(a_{1} + A) ∩ (a_{2} + A)| ≥ (2 − θ)n + K.

As any equality a_{1} + a′ = a_{2} + a′′ yields the representation

c = −a_{1} + a_{2} = a′ − a′′,

we conclude that −A + A ⊆ A − A and moreover, every c ∈ −A + A has at least (2−θ)n+K representations as c = a′ −a′′. Similarly, A−A ⊆ −A+A and moreover, every c ∈ A − A has at least (2 − θ)n + K representations as c = −a′ + a′′. Therefore, A − A = −A + A and each c ∈ A − A has at least (2 − θ)n + K representations as c = a′ − a′′. iii) From i) and ii), for any c ∈ A − A there are more than K triples (a_{1}, a_{2}, a_{3}) ∈ A × A × A such that c = a_{1} − a_{2} and σ = a_{2} + a_{3}. For any such triple we have c + σ = a_{1} + a_{3}, and since there are at most K representations of c + σ in this form

with (a_{1}, a_{3}) ∈ R, it follows that c + σ ∈ A +^{R} A. Therefore, A − A + σ ⊆ A +^{R} A, and hence

(4)  |A − A| ≤ |A +^{R} A|.

iv) To conclude the proof, we show that A − A is too large to satisfy (4). Since

A +^{R} A ≠ A + A, there exist a_{1}, a_{2} ∈ A such that c = a_{1} + a_{2} ∉ A +^{R} A. Then

|(−a_{1} + A) ∩ (a_{2} − A)| ≤ K,

as any equality −a_{1}+a′ = a_{2}−a′′ yields the representation c = a′+a′′ with (a′, a′′) ∈ R

(in view of c ∉ A +^{R} A), and there are at most K such representations. Therefore,

|A − A| ≥ |(−a_{1} + A) ∪ (a_{2} − A)| ≥ 2n − K > θn − K − 2s ≥ |A +^{R} A|,

contradicting (4).

5. Proof of Theorem 1

Throughout this section, A, n, l, R, K, and s will be as in the formulation of Theorem 1, and Ā will denote the image of A under the canonical homomorphism ℤ → ℤ_{l}, so that |Ā| = n − 1. Generally, we adopt the following convention: if a letter denotes an integer number or a set of integers, then the same letter overlined will denote the canonical image in ℤ_{l} of this number or set. Furthermore, by \overline{R} we denote the set of all pairs (ā_{1}, ā_{2}) ∈ Ā × Ā such that for any pre-image a_{1} ∈ A of ā_{1} and any pre-image a_{2} ∈ A of ā_{2} we have (a_{1}, a_{2}) ∈ R. (If ā_{i} ≠ 0 (i = 1, 2), then each ā_{i} has only one pre-image a_{i} ∈ A, and (ā_{1}, ā_{2}) ∈ \overline{R} if and only if (a_{1}, a_{2}) ∈ R.)

Lemma 2. We have: \overline{R} ∈ R_{2K,s}(Ā, Ā).

Proof. i) Suppose that (ā, ā_{i}) ∈ \overline{R} (i = 1, …, t) and show that t ≤ s. Indeed, let a, a_{1}, …, a_{t} be any pre-images of a, a_{1}, …, a_{t} in A, respectively. Then (a, a_{i}) ∈ R (i = 1, …, t) and the assertion follows in view of R ∈ R_{K,s}(A, A). ii) Similarly, if (ā_{i}, ā) ∈ \overline{R} (i = 1, …, t), then t ≤ s. iii) Suppose that \overline{c} = ā′_{i} + ā′′_{i}, where (ā′_{i}, ā′′_{i}) ∈ \overline{R} (i = 1, …, t) and c is the image in ℤ_{l} of an integer c ∈ [1, l], and show that t ≤ 2K. Indeed, let a′_{i} and a′′_{i} be the maximal pre-images in A of ā′_{i} and ā′′_{i}, respectively. Then a′_{i} + a′′_{i} ∈ {c, c + l} and the assertion follows since in view of (a′_{i}, a′′_{i}) ∈ R, at most K of the sums a′_{i} + a′′_{i} can be equal to c, and at most K can be equal to c + l. □

Our next lemma gives a first indication of how an estimation of |A +^{R} A| can be

reduced to that of |Ā +^{\overline{R}} Ā|.

Lemma 3. We have: |A +^{R} A| ≥ |Ā +^{\overline{R}} Ā| + n − 2s.

Proof. Write A = {a_{1}, …, a_{n}} where 0 = a_{1} < … < a_{n} = l and consider the table

ā_{1} + ā_{n} a_{1} + a_{1}, a_{1} + a_{n}, a_{n} + a_{n}
ā_{1} + ā_{2} a_{1} + a_{2}, a_{n} + a_{2}
⋮
ā_{1} + ā_{n−1} a_{1} + a_{n−1}, a_{n} + a_{n−1}.

The first column contains elements of Ā + Ā, the second their pre-images in A + A;

they may or may not be in Ā +^{\overline{R}} Ā and A +^{R} A. For i = 2, …, n − 1 we say that the i th

row is “good”, if both a_{1} + a_{i} and a_{n} + a_{i} belong to A +^{R} A. Otherwise, it is “bad”; for this to happen, we need either (a_{1}, a_{i}), (a_{i}, a_{1}) ∈ R, or (a_{n}, a_{i}), (a_{i}, a_{n}) ∈ R. It follows that there are at most 2s bad rows; exactly how many are there?

i) If there are 2s−2 or less bad rows, then the number of good rows is at least n−2s,

and each of these good rows contains two distinct elements of A +^{R} A having the same

image in Ā +^{\overline{R}} Ā. Therefore, |A +^{R} A| ≥ |Ā +^{\overline{R}} Ā| + n − 2s, as claimed. ii) Suppose there is exactly 2s − 1 bad rows, say

(a_{1}, a_{i_{j}}), (a_{i_{j}}, a_{1}) ∈ R for j = 1, …, s,
(a_{n}, a_{i_{j}}), (a_{i_{j}}, a_{n}) ∈ R for j = s + 1, …, 2s − 1,

with i_{j} ∈ [2, n − 1] all distinct. Then we have n − 2s − 1 good rows and in addition,

(a_{1}, a_{n}), (a_{1}, a_{1}) ∉ R, whence |A +^{R} A| ≥ |Ā +^{\overline{R}} Ā| + (n − 2s − 1) + 1.

iii) Finally, suppose that there are 2s bad rows, say

(a_{1}, a_{i_{j}}), (a_{i_{j}}, a_{1}) ∈ R for j = 1, …, s,
(a_{n}, a_{i_{j}}), (a_{i_{j}}, a_{n}) ∈ R for j = s + 1, …, 2s,

with i_{j} ∈ [2, n − 1] all distinct. Then we have n − 2s − 2 good rows and in addition,

(a_{1}, a_{n}), (a_{1}, a_{1}), (a_{n}, a_{n}) ∉ R, whence |A +^{R} A| ≥ |Ā +^{\overline{R}} Ā| + (n − 2s − 2) + 2. □

We now prove a “restricted analog” of a well-know basic lemma.

Lemma 4. Let C be a subset of the set of elements of an arbitrary finite group G,

and let R ∈ R_{K,s}(C, C). Suppose that 2|C| > |G| + K. Then C +^{R} C = G.

Proof. For any g ∈ G we have |C ∩ (g − C)| ≥ 2|C| − |G| > K, hence there are more that K pairs (c′, c′′) ∈ C ×C such that c′ = g −c′′. At least one of these pairs satisfies

(c′, c′′) ∉ R, and then g = c′ + c′′ ∈ C +^{R} C. □

Corollary 1. Suppose that l ≤ 2n − 2K − 3. Then |A +^{R} A| ≥ l + n − 2s.

Proof. We apply Lemma 4 to Ā ⊆ ℤ_{l} and \overline{R} ∈ R_{2K,s}(Ā, Ā). Since 2|Ā| = 2n − 2 >

l + 2K, we have Ā +^{\overline{R}} Ā = ℤ_{l}, and it remains to use Lemma 3. □

We notice that Corollary 1 settles one of the two cases of Theorem 1, and that the second case (l ≥ 2n − 2K − 2) follows by Theorem 2 and Lemma 3, assuming that

Ā +^{\overline{R}} Ā ≠ Ā + Ā: indeed, we have then

|A +^{R} A| ≥ |Ā +^{\overline{R}} Ā| + n − 2s > θ(n − 1) − 2K − 2s + n − 2s.

We now turn to the remaining case Ā +^{\overline{R}} Ā = Ā + Ā.

Proposition 1. Suppose that Ā +^{\overline{R}} Ā = Ā + Ā. Then

|A +^{R} A| ≥ min{l, 2n − 2s − 3} + n − 2s.

Proof. We can assume that

(5)  |Ā +^{\overline{R}} Ā| = |Ā + Ā| ≤ 2|Ā| − 2s − 2 :

otherwise |A +^{R} A| ≥ 2|Ā|−2s−1+n−2s = 3n−4s−3 by Lemma 3. Let H = H(Ā+Ā) be the period of Ā + Ā.

As 0 ∈ Ā, we have Ā ⊆ Ā + Ā and therefore Ā + H ⊆ Ā + Ā; moreover, we can assume that Ā + H ≠ Ā + Ā: otherwise

Ā + Ā = (Ā + Ā) + H = Ā + (Ā + H) = Ā + Ā + Ā = … = ℤ_{l}

(Ā is a generating subset of ℤ_{l} in view of gcd(A) = 1) and then |A +^{R} A| ≥ l + n − 2s, as in Corollary 1.

We see that the sumset Ā+Ā is a disjoint union of its three subsets Ā, (Ā+H)\Ā,

and (Ā + Ā) \ (Ā + H), and we count separately the number of integers c ∈ A +^{R} A such that the image \overline{c} falls into each of these three subsets.

i) #\{c ∈ A +^{R} A: \overline{c} ∈ Ā\} ≥ 2n − 2s − 1: if A = \{a_{1}, …, a_{n}\}, where 0 = a_{1} < … <

a_{n} = l, then of the 2n − 1 sums

a_{1} + a_{1}, …, a_{1} + a_{n−1}, a_{1} + a_{n}, a_{2} + a_{n}, …, a_{n} + a_{n}

at most 2s do not belong to A +^{R} A.

ii) #\{c ∈ A +^{R} A: \overline{c} ∈ (Ā+H)\Ā\} ≥ |Ā+H|−|Ā|: indeed, any \overline{c} ∈ (Ā+H)\Ā ⊆ Ā +^{\overline{R}} Ā

has a pre-image in A +^{R} A.

iii) #\{c ∈ A +^{R} A: \overline{c} ∈ (Ā + Ā) \ (Ā + H)\} ≥ 2|Ā| − |Ā + H| − 2s − 1. This estimate is somewhat tricky. Set N := (|Ā + Ā| − |Ā + H|)/|H| ≥ 1, the number of H-cosets in (Ā + Ā) \ (Ā + H). Any of these cosets is of the form ā_{1} + ā_{2} + H, where a_{1}, a_{2} ∈ A and ā_{1}, ā_{2} ∉ H. (We don’t assume any longer that the elements of A are numbered in an increasing order and that a_{i} denotes any particular element of A.) Let

A_{i} := {a ∈ A: ā ∈ ā_{i} + H}; i = 1, 2.

Plainly,

|A_{i}| = |Ā_{i}| = |Ā_{i} + H| − |(Ā_{i} + H) \ Ā_{i}|

≥ |H| − |(Ā + H) \ Ā| = |H| + |Ā| − |Ā + H|.

If a′ ∈ A_{1}, a′′ ∈ A_{2}, and (a′, a′′) ∉ R, then evidently c := a′ + a′′ ∈ A +^{R} A and

\overline{c} ∈ ā_{1} + ā_{2} + H. By Lemma 1, we have

#{(a′, a′′): a′ ∈ A_{1}, a′′ ∈ A_{2}, (a′, a′′) ∉ R}

≥ |A_{1}| + |A_{2}| − 2s − 1 ≥ 2|H| + 2|Ā| − 2|Ā + H| − 2s − 1.

We denote the right-hand side by M and we note that M ≥ |H| + 1: indeed, by Kneser’s theorem and the assumption (5)

M = 2|H| + 2|Ā| − 2|Ā + H| − 2s − 1 = |H| + 2|Ā| − |Ā + Ā| − 2s − 1 ≥ |H| + 1.

We see that for any H-coset of those N contained in the set (Ā + Ā) \ (Ā + H) there

are at least M elements c ∈ A +^{R} A such that \overline{c} belongs to this coset. It follows that

#\{c ∈ A +^{R} A: \overline{c} ∈ (Ā + Ā) \ (Ā + H)\} ≥ NM

= (N − 1)(M − |H|) + N|H| + M − |H| ≥ N|H| + M − |H|

= |Ā + Ā| + |H| + 2|Ā| − 3|Ā + H| − 2s − 1 = 2|Ā| − |Ā + H| − 2s − 1.

(We used here Kneser’s theorem once again.)

Combining the estimates of i)–iii), we obtain

|A +^{R} A| ≥ (2n − 2s − 1) + (|Ā + H| − |Ā|) + (2|Ā| − |Ā + H| − 2s − 1)
= |Ā| + 2n − 4s − 2
= 3n − 4s − 3.
□

We can now easily complete the proof of Theorem 1. The remark following the proof

of Corollary 1 shows that it suffices to consider the case l ≥ 2n−2K−2, Ā +^{\overline{R}} Ā = Ā+Ā only, and in this case by Proposition 1 we have

|A +^{R} A| ≥ min{2n − 2K − 2, 2n − 2s − 3} + n − 2s
= 3n − 2s − 2 − max{2K, 2s + 1}
≥ 3n − 4s − 2K − 3
≥ (θ + 1)n − 4s − 2K − θ.

This completes the proof.

References

[ANR95] N. Alon, M.B. Nathanson, and I.Z. Ruzsa, Adding distinct congruence classes modulo a prime, American Math. Monthly 102 (1995), 250–255.

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

[DH94] J.A. Dias da Silva and Y.O. Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc. 26 (1994), 140–146.

[EG80] P. Erdős and R.L. Graham, Old and new problems and results in combinatorial number theory, L’Enseignement Mathématique, Geneva, 1980.

[F59] G. Freiman, On addition of finite sets, I, Izv. Vyssh. Uchebn. Zaved. Mat. 6(13) (1959), 202–213.

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

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

[L00] V.F. Lev, Restricted set addition in groups. I. The classical setting, Journal of the London Math. Society, to appear.

[L01] V.F. Lev, Restricted set addition in groups. II. A generalization of the Erdős-Heilbronn conjecture, Submitted.

[LS95] V.F. Lev and P.Y. Smeliansky, On addition of two distinct sets of integers, Acta Arithmetica 70(1) (1995), 85–91.

[S00] T. Schoen, The cardinality of restricted sumsets, Submitted.

[S98] I. Stanchescu, On addition of two distinct sets of integers, Acta Arithmetica 75(2) (1996), 191–194.

Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel.

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