ON A GENERALIZATION OF A THEOREM BY VOSPER

Oriol Serra

UPC, Jordi Girona, 1, 08034 Barcelona, Spain

                               oserra@mat.upc.es

Gilles Zémor

ENST, 46 rue Barrault, 75 634 Paris 13, France

                             zemor@infres.enst.fr

Received: 4/7/00, Accepted: 8/4/00, Published: 8/4/00

Abstract

Let S, T be subsets of ℤ/pℤ with min{|S|, |T |} > 1. The Cauchy–Davenport theorem states that |S + T | ≥ min{p, |S| + |T | − 1}. A theorem by Vosper characterizes the critical pair in the above inequality. We prove the following generalization of Vosper’s theorem. If |S + T | ≤ min\{p − 2, |S| + |T | + m\}, 2 ≤ |S|, |T |, and |S| ≤ p − \binom{m+4}{2}, then S is a union of at most m + 2 arithmetic progressions with the same difference. The term \binom{m+4}{2} is best possible, i.e. cannot be replaced by a smaller number.

1. Introduction

One of the subjects of additive number theory is the study of inverse problems, i.e. the study of the structure of subsets S and T of a group such that the cardinality |S + T | is “small”. The oldest result in this vein is the Cauchy-Davenport theorem which states that |S + T | ≥ min{p, |S| + |T | − 1} for any subsets S, T of a group of prime order p. Vosper’s theorem [6] characterizes the sets for which equality holds. It states :

Theorem 1 (Vosper) Let S and T be subsets of a group of prime order p such that |S| ≥ 2, |T | ≥ 2, and |S + T | < p − 1. Then either |S + T | ≥ |S| + |T |, or S and T are in arithmetic progression with the same difference.

Freiman [1] gave the following improvement of Vosper’s Theorem in the case when S = T.

Theorem 2 (Freiman) Let S be a subset of a group of prime order p such that |S| < p/35. Suppose that |S + S| ≤ 2|S| + m with m ≤ \frac{2}{5}|S| − 3. Then S is contained in an arithmetic progression of length at most |S| + m + 1.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A10 2

As far as we know, the first improvement of Vosper’s result for different sets S and T is the recent result of Hamidoune and Rødseth [5] who proved :

Theorem 3 (Hamidoune-Rødseth) Let S and T be subsets of a group of prime order p, such that |S| ≥ 3, |T | ≥ 3, 7 ≤ |S + T | ≤ p − 4. Then either |S + T | ≥ |S| + |T | + 1, or S and T are contained in arithmetic progressions with the same difference and |S| + 1 and |T | + 1 elements respectively.

In another direction, the Cauchy-Davenport theorem was generalized to arbitrary Abelian groups by Mann [2, p. 2] :

Theorem 4 (Mann) Let S be a subset of an arbitrary Abelian group G. Then one of the following holds:

(i) for every subset T such that S + T ≠ G we have |S + T | ≥ |S| + |T | − 1.

(ii) there exists a proper subgroup H of G such that |S + H| < |S| + |H| − 1.

The following theorem of Hamidoune [4] is both a generalization of Mann’s theorem and of Vosper’s theorem.

Theorem 5 (Hamidoune) Let G be a (not necessarily Abelian) group generated by a finite subset S containing 0. Suppose that every nonzero element of G has order ≥ |S|. Then one of the following holds:

(i) for every subset T such that 2 ≤ |T | < ∞, we have |S + T | ≥ min(|G| − 1, |S| + |T |).

(ii) S is an arithmetic progression.

Notice the similarity between Mann’s and Hamidoune’s theorems 4 and 5. Together they state, broadly speaking, that subsets S of a group for which S + T is “small” for some T tend either to cluster around subgroups or to be an arithmetic progression.

A very interesting feature of Hamidoune’s proof of his result is that it unites Theorems 1 and 4 under a short, elegant, and insightful explanation. This involves defining k–isoperimetric numbers and k-atoms associated to S. It turns out that the 1–atoms lead naturally to the subgroup H in Theorem 4 and that the 2–atoms lead to the difference of the arithmetic progression in Theorem 5.

In this paper, we study the 2–atoms of an arbitrary subset S of a group of prime order and give a sufficient condition on |S| for them to be of cardinality two. We shall see that this condition is necessary in very many situations. This leads to a further generalization of Vosper’s theorem in the prime order case. Our main result is :

Theorem 6 Let m be a non-negative integer and let S be a subset of a group of prime order p such that 2 ≤ |S| < p − \binom{m+4}{2}. Then either

|S + T | > |S| + |T | + m,

for any subset T such that 2 ≤ |T | and |S + T | ≤ p − 2, or S is the union of at most m + 2 arithmetic progressions with the same difference.

Our proof leads to the condition |S| < p − \binom{m+4}{2} in a natural way, and we shall see that this bound is best possible. More precisely, there exist subsets S of ℤ/pℤ with cardinality p − \binom{m+4}{2} that are not the union of at most m + 2 arithmetic progressions and for which |S + T | ≤ |S| + |T | + m ≤ p − 2 for some subset |T | ≥ 2. Note that this situation is unlike that of ℤ, but these sets S have to be “large”, i.e. |S| ≥ p − \binom{m+4}{2}.

2. Atoms

Let S be a fixed subset of ℤ/pℤ with 0 ∈ S. For a subset X ⊂ G we write

N_{S}(X) = (X + S) \ X.

We omit the subscript S when the reference to it is clear from the context. If 0 ∈ X, we write X^{∗} = X \ {0}.

Following the terminology of Hamidoune [4], we say that S is k–separable if there is X ⊂ ℤ/pℤ such that |X| ≥ k and |X+S| ≤ p−k. If S is k–separable, the k–isoperimetric connectivity of S is

κ_{k}(S) = min{|N(X)|, X ⊂ ℤ/pℤ, k ≤ |X| and |X + S| ≤ p − k},

and the k–isoperimetric number of S is

d_{k}(S) = min{|N(X)|, X ⊂ ℤ/pℤ, |X| = k}.

We say that a subset F ⊂ G is a k–fragment of S if |N(F)| = κ_{k}(S), |F | ≥ k and |F +S| ≤ p−k. A k–fragment of minimum cardinality is said to be a k–atom of S. We denote by α_{k}(S) the cardinality of a k–atom of S. Note that α_{k}(S) > k if and only if κ_{k}(S) < d_{k}(S). Note also that, when |S| = 2 and S is k-separable, then α_{k}(S) = k and κ_{k}(S) = 1. To avoid trivial cases we always assume that |S| > 2.

The following basic property of k–atoms is proved in [4].

Theorem 7 Let A be a k–atom and let F be a k–fragment of a subset S ⊂ ℤ/pℤ with 0 ∈ S. Then, either A ⊂ F or |A ∩ F | ≤ k − 1.

This theorem has a number of consequences. We use it here to derive some intermediate results that we shall need. For the rest of this section it is always assumed that S is a 2–separable subset of ℤ/pℤ, 0 ∈ S, and |S| ≥ 3.

Proposition 8 Let A be a 2–atom of S. Then, |A|(|A| − 1) ≤ 2κ_{2}(S).

Proof. We may assume |A| > 2. Let S = {0 = s_{0}, s_{1}, …, s_{r}}, r ≥ 2. We have

κ_{2}(S) = |A + S| − |A| = |⋃_{i=1}^{r}[(A + s_{i}) \ ∪_{0≤j<i}(A + s_{j})]| .  (1)

If A is a 2–atom then so is A + z for any z. Therefore equation (1) and Theorem 7 imply

κ_{2}(S) ≥ (|A| − 1) + (|A| − 2) + max{|A| − 3, 0} + … + max{|A| − r, 0}.

If |A| > |S| then |A + S| − |A| ≥ (|A| − 1) + (|A| − 2) ≥ 2|A| − 3 ≥ 2|S| − 1 ≥ d_{2}(S), which implies α_{2}(S) = 2. Hence |A| ≤ |S|. Therefore,

κ_{2}(S) ≥ (|A| − 1) + … + 2 + 1 = |A|(|A| − 1)/2,

as claimed.

Recall that X ⊂ G is a Sidon set if |2X| = \binom{|X|+1}{2}, that is, there are no two unordered pairs of (possibly equal) elements in X with the same sum. The following is an easy consequence of Theorem 7.

Proposition 9 Let A be a 2–atom of S. If |A| > 2 then A is a Sidon set.

Proof. Suppose that x + y = x′ + y′ for x, y, x′, y′ in A. Then {x, y′} ∈ (A + x − x′) ∩ A. Since A + z is a 2–atom for each z ∈ ℤ/pℤ, Theorem 7 implies either x = y′ or x = x′. Hence, all twofold sums of elements of A are different and A is a Sidon set.

Proposition 10 Suppose S is a Sidon set in ℤ/pℤ. Then, α_{2}(S) = 2.

Proof.

For each x ∈ ℤ/pℤ, x ≠ 0, we have |S ∩ (S + x)| ≤ 1. For k ≤ |S| let X = {x_{1}, …, x_{k}} ⊂ ℤ/pℤ. Then,

|N(X)| = |S + X| − |X| = |⋃_{i=1}^{k}[(S + x_{i}) \ ⋃_{j<i}(S + x_{j})]| − |X|
≥ [|S| + (|S| − 1) + (|S| − 2) + ⋯ + (|S| − |X| + 1)] − |X| = \frac{1}{2}|X|(2|S| − |X| − 1).

In particular,

d_{k}(S) ≥ \frac{1}{2}k(2|S| − k − 1).  (2)

Let A be a 2–atom of S and suppose that |A| > 2, so that |N(A)| < d_{2}(S). We have, for any s ∈ S^{∗}, |S + {0, s}| = 2|S| − 1 so that |N({0, s})| = 2|S| − 3 : we conclude therefore that |N(A)| < 2|S| − 3. But according to the lower bound (2), which is a quadratic function of k with negative leading term and zeros at k = 0 and k = 2|S| − 1, this implies |A| > 2|S| − 3. By Proposition 8 we then have (2|S| − 3)(2|S| − 4) < 2(2|S| − 4), which implies |S| < 3 against our assumption. Hence, α_{2}(S) = 2.

Finally we have :

Proposition 11 Let A be a 2–atom of S. Then, α_{2}(A) = 2. Moreover, |A| ≤ m + 3, where m = κ_{2}(S) − |S|.

Proof. If α_{2}(S) = |A| = 2 there is nothing to prove. Suppose that |A| > 2. We may assume that 0 ∈ A. By Proposition 9, A is a Sidon set. By Proposition 10 we have α_{2}(A) = 2.

On the other hand, we have |S + A| − |A| = |S| + m, which implies

|A| + m = |S + A| − |S| ≥ κ_{2}(A) = d_{2}(A) = 2|A| − 3.

Hence |A| ≤ m + 3.

3. Surjective pairs of subsets

To prove that a set S is the union of sufficiently few arithmetic progressions, say of difference a, our basic strategy is to show that {0, a} is a 2-atom of S. This is why, in this section, we study 2–atoms A of sets S such that |A| > 2. We shall prove that these 2–atoms have very special structure, namely that they define, together with S, surjective pairs. Before defining this concept we need some notation.

Let Y be a fixed subset of ℤ/pℤ. For each subset X ⊂ ℤ/pℤ and each integer i ≥ 2 we denote

N_{i}(X) = N_{Y} (X + (i − 1)Y),

where iY = \underbrace{Y + … + Y}_{i}. We write N_{0}(X) = X and N_{1}(X) = N_{Y} (X). Note that

N_{i+1}(X) = (N_{i}(X) + Y) \ ⋃_{0≤j≤i} N_{i}(X).

For a subset U of Y and i ≥ 1, we denote by N_{i}^{U}(X) the set of elements z ∈ N_{i}(X) such that z − U ⊂ N_{i−1}(X) and U is a maximal subset of Y with this property. We also write

N_{i}^{≤U}(X) = ⋃_{V ⊂U} N_{i}^{V} (X).

Lemma 12 For each U ⊂ Y and i ≥ 1, if N_{i+1}^{U}(X) ≠ ∅ then

N_{i+1}^{U}(X) − U ⊂ N_{i}^{≤U}(X).

Proof. Let z ∈ N_{i+1}^{U}(x), u ∈ U and z′ = z − u ∈ N_{i}(X). Then z′ ∈ N_{i}^{V} (X) for some subset V of Y. But, for any v ∈ V, we have z − v = z′ − v + u ∈ N_{j}(X) for some j < i + 1. Since z ∈ N_{i+1}(X) we must have j = i : this implies V ⊂ U. In particular, if N_{i+1}^{U}(X) ≠ ∅, then N_{i+1}^{U}(X) − U ⊂ ∪_{V ⊂U}N_{i}^{V} (X) = N_{i}^{≤U}(X).

Definition A pair (X, Y) of subsets of ℤ/pℤ is said to be h-surjective if X, Y ≠ ℤ/pℤ and

|(z − Y) ∩ X| ≥ h for each z ∈ N_{Y} (X).  (3)

The following two lemmas are the key steps in our proof of Theorem 6.

Lemma 13 Let S be a 2-separable subset of ℤ/pℤ and let A be a 2–atom of S such that |A^{∗}| ≥ 2. Then

(i) (S, A) is a 2-surjective pair, and

(ii) (S + A, A) is a |A^{∗}|-surjective pair.

Proof. We may assume that 0 ∈ A. Let z ∈ N_{A}(S) and suppose that there is only a single element z′ ∈ A such that z − z′ ∈ S. Let A′ = A \ {z′}. Then |A + S| = |(A′ + S) ∪ {z}| = |A′ + S| + 1. Therefore, |N_{S}(A)| = |N_{S}(A′)| and |A′| ≥ 2, contradicting the minimality of A. Hence, (S, A) is 2-surjective.

Let U be a subset of A^{∗} with at most |A| − 2 elements.

By Lemma 12 and the Cauchy-Davenport theorem, if N_{i}^{U}(S) ≠ ∅ for some i ≥ 2, then we have

|N_{i−1}^{≤U}(S)| ≥ |N_{i}^{U}(S) − U| ≥ |N_{i}^{U}(S)| + |U| − 1.  (4)

If |U| ≤ |N_{1}^{≤U}(S)|, then

|S + (A \ U)| − |A \ U| ≥ |S + A| − |N_{1}^{≤U}(S)| + |U| − |A| ≤ |S + A| − |A|,

thus contradicting the hypothesis that A is a 2-atom. Hence,

|N_{1}^{≤U}(S)| ≤ |U| − 1, U ⊂ A^{∗}, |U| ≤ |A| − 2.

Therefore, if N_{2}^{U}(S) ≠ ∅, then (4) implies

|N_{2}^{U}(S)| ≤ |N_{1}^{≤U}(S)| − (|U| − 1) ≤ 0,

a contradiction. Hence N_{2}^{U}(S) = ∅ for each proper subset of A^{∗} and therefore (S + A, A) is an |A^{∗}|-surjective pair.

Lemma 14 Let (X, Y) be an h-surjective pair in ℤ/pℤ and i ≥ 1. If X + iY ≠ ℤ/pℤ then (X + iY, Y) is also an h-surjective pair. In particular, if |N_{i}^{≤U}(X)| < h for some U ⊂ Y and i ≥ 1 then N_{i+1}^{U}(X) = ∅.

Proof. Assume that (X +(i−1)Y, Y) is h-surjective for some i ≥ 1. We have N_{1}(X +(i−1)Y) = N_{i}(X). For each subset U of Y with strictly less than h elements, we have N_{i}^{≤U}(X) = ∅. If N_{i+1}^{U}(X) ≠ ∅, i ≥ 1 then Lemma 12 implies N_{i+1}^{U}(X) − U ⊂ N_{i}^{≤U}(X) = ∅, a contradiction. Therefore, (X + iY, Y) is also h-surjective. The first part of the result follows by induction.

Suppose now that |N_{i}^{≤U}(X)| < h for some U ⊂ Y. Then, if N_{i+1}^{U}(X) ≠ ∅, Lemma 12 implies h > |N_{i}^{≤U}(X)| ≥ |N_{i+1}^{U}(X) − U| ≥ |U|, this contradicts the h-surjectivity of (X + iY, Y).

Theorem 15 Let S ⊂ ℤ/pℤ be a 2-separable subset. If α_{2}(S) > 2 then

|S| ≥ p − \binom{m + 4}{2},

where m = κ_{2}(S) − |S|.

Proof. We may assume |S| > 2. Let A be a 2–atom of S containing 0 and suppose that |A| > 2.

We use the above notation with Y = S, namely, N_{i}(S) = N_{A}(S + (i − 1)A). By definition of κ_{2}(S) and m we have |S + A| = |A| + |S| + m, so that |N_{1}(S)| = |A| + m.

1. Suppose first |A| = 3, so that N_{1}(S) = |A| + 3.

By Lemma 13 and Lemma 14, if S + iA ≠ ℤ/pℤ, i ≥ 1, then (S + iA, A) is a 2-surjective pair. Therefore N_{i}(S) = N_{i}^{A^{∗}}(S) for i ≥ 2. If N_{i}(S) ≠ ∅, then Lemma 12 implies N_{i}(S) − A^{∗} ⊂ N_{i−1}(S). By the Cauchy-Davenport theorem this implies, for all i ≥ 2 such that N_{i}(S) ≠ ∅,

|N_{i}(S)| ≤ |N_{i−1}(S)| − 1.

Therefore, |N_{i}(S)| ≤ (m + 3) − (i − 1) = m + 4 − i and N_{i}(S) = ∅ for i ≥ m + 4. Hence, ℤ/pℤ = ∪_{i=0}^{m+3}N_{i}(X) which implies

|S| ≥ p − ∑_{i=1}^{m+3} |N_{i}(S)| ≥ p − \frac{(m + 3)(m + 4)}{2},

as claimed.

2. Suppose now that h + 1 = |A| > 3. Let us write ℤ/pℤ = ∪_{i=0}^{k}N_{i}(X), so that we have

|S| = p − ∑_{i=1}^{k} |N_{i}(S)|.

By Lemma 13 and Lemma 14, if S + iA ≠ ℤ/pℤ, i ≥ 1, then (S + iA, A) is an hsurjective pair. Therefore N_{i}(S) = N_{i}^{A^{∗}}(S) for i ≥ 2. If N_{i}(S) ≠ ∅, then Lemma 12 implies N_{i}(S) − A^{∗} ⊂ N_{i−1}(S). Since A^{∗} is a Sidon set with more than 2 elements, it is not an arithmetic progression. By Vosper’s theorem this implies, for all i ≥ 2 such that |N_{i}(S)| > 1,

|N_{i}(S)| ≤ |N_{i−1}(S)| − h.

Therefore, |N_{2}(S)| ≤ m + |A| − h = m + 1, and if k ≥ 3,

(i) |N_{i}(S)| ≤ (m + 1) − (i − 2)h for all i such that 3 ≤ i ≤ k − 1, and (ii) either |N_{k}(S)| = 1 and |N_{k−1}(S)| = h or |N_{k}(S)| ≤ (m + 1) − (k − 2)h.

In every case we get k ≤ 2 + (m + 1)/h. By Proposition 11, |N_{1}(S)| = m + |A| ≤ 2m + 3; therefore, if k = 2 we get

|N_{1}(S)| + |N_{2}(S)| ≤ 3m + 4

and it is routinely checked that this is always smaller than \binom{m+4}{2}. If k ≥ 3 we get

∑_{i=1}^{k} |N_{i}(S)| ≤ (2m + 3) + (m + 1)(k − 1) − h\frac{(k − 2)(k − 1)}{2} + 1

which gives, since we have supposed h ≥ 2,

∑_{i=1}^{k} |N_{i}(S)| ≤ (2m + 4) + (k − 1)[(m + 1) − (k − 2)] ≤ (2m + 4) + (k − 1)m,

and, since k − 1 ≤ 1 + (m + 1)/h, we get

∑_{i=1}^{k} |N_{i}(S)| ≤ (3m + 4) + m(m + 1)/2

which is less than \binom{m+4}{2}.

This concludes the proof.

4. A Proof of Theorem 6: Discussion

Suppose S is a subset of ℤ/pℤ satisfying the conditions of Theorem 6 and suppose there exists T ⊂ ℤ/pℤ such that 2 ≤ |T |, |S + T | ≤ p − 2, and |S + T | ≤ |S| + |T | + m. Then, without loss of generality we may suppose 0 ∈ S, and S is a 2-separable set for which κ_{2}(S) ≤ |S| + m. Let A be a 2-atom of S containing 0. By Theorem 15 we have |A| = 2 and therefore

|S + A| ≤ |S| + |A| + m = |S| + m + 2.

Let A = {0, a}. Let S = S_{1} ∪ … ∪ S_{h} be a partition of S into arithmetic progressions of difference a such that (S_{i} + a) ∩ S_{j} = ∅ for each pair of different subscripts i, j. Then,

|S + A| = ∑_{i=1}^{h} |S_{i} + {0, a}| = |S| + h,

which implies h ≤ m + 2 and Theorem 6 is proved.

We now show that the term \binom{m+4}{2} in Theorem 6 cannot be reduced. First consider the following example. Let p be a prime number of the form p = 3b + 1 for some positive integer b and let S = [0, b − 1] ∪ [b + 1, 2b − 2] ∪ [2b + 1, 3b − 3] and A = {0, 1, b}. Then |S + A| = |S| + |A|, i.e. |N_{S}(A)| = |S|. Note that |S| = p − 6 = \binom{4+0}{2}. Note also that |N_{S}(\{0, x\})| ≥ |S| + 1 for any x ≠ 0, since otherwise Vosper’s theorem would imply that S is an arithmetic progression of difference x, which can be easily checked not to be the case. This shows that 2-atoms of size more than 2 do exist. Furthermore, by Proposition 11, the size of a 2-atom is at most 3 in this example, so that A is actually a 2-atom of S.

This example can be generalized to sets S with κ_{2}(S) = |S| + m for m > 0 and for which α_{2}(S) = 3. They are built with a similar pattern. Let b be a positive integer such that p = (m + 3)b + 1 is a prime number. Let

S = [0, b − 1] ∪ [b + 1, 2b − 2] ∪ [2b + 1, 3b − 3] ∪ … ∪ [(m + 2)b + 1, (m + 3)b − (m + 3)].

Again set A = \{0, 1, b\}. We have |S +A| = |S|+|A|+m. Note that |S| = p−\binom{m+4}{2}, i.e. exactly the bound of Theorem 6. It is not quite clear to us how to formally prove that d_{2}(S) > |S| + m, or, equivalently, that S is not the union of k arithmetic progressions for k ≤ m + 2, but this can be checked by exhaustive search for many values of m as long as p is not too large. In these cases we actually have κ_{2}(S) = |S| + m. This is because the second part of the proof of Theorem 15 shows us that atoms of size > 3 are incompatible with |S| achieving the bound p − \binom{m+4}{2}: therefore A actually is a 2–atom.

The above examples are sets S

(i) that satisfy |S + T | = |S| + |T | + m < p − 2 for some set T containing more than one element,

(ii) that are the union of m + 3 arithmetic progressions with the same difference but not less.

Additional examples of sets S of cardinality larger than p − \binom{m+4}{2} can be found

(i) that are the union of m + k arithmetic progressions but not less, for k > 3,

(ii) for which we also have |S + T | = |S| + |T | + m < p − 2 for some set T containing more than one element.

As a simple example, take A = {0, 1, 3, 13, 41} ⊂ ℤ/91ℤ. Then translates S of ℤ/91ℤ \ (A + A) have κ_{2}(S) = |S| + 5, α_{2}(S) = 5, and S is not the union of less than 9 arithmetic progressions.

References

[1] G.A. Freiman, Inverse problems of additive number theory. On the addition of sets of residues with respect to a prime modulus, 2 Soviet. Math. Doklady, (1961) 1520–1522.

[2] H. B. Mann, Addition theorems : The addition theorems of group theory and number theory, Interscience, New York, 1965.

[3] M. B. Nathanson, Additive number theory : Inverse problems and the Geometry of sumsets, Springer-Verlag GTM 165 (1996).

[4] Y.O. Hamidoune, An Isoperimetric method in Additive Theory, J. of Algebra 179 (1996), 622-630.

[5] Y.O. Hamidoune and Ø. J. Rødseth, An inverse theorem mod p, Acta Arithmetica, XCII.3, (2000), 251–262.

[6] G. Vosper, The critical pairs of subsets of a group of prime order, J. London Math. Soc. 31 (1956), 200-205.