ACTA ARITHMETICA
XCII.3 (2000)
An inverse theorem mod p
by
Yahya Ould Hamidoune (Paris) and Øystein J. Rødseth (Bergen)
1. Introduction. Let p be a prime number. Let A and B be two
nonempty subsets of Z/pZ. We write |A| for the number of elements in the
set A. The sumset A + B is the set of all sums a + b where a ∈ A and b ∈ B.
If there exist elements a, d ∈ Z/pZ such that
A = {a + id | i = 0, 1, . . . , |A| − 1},
then A is an arithmetic progression with difference d (or a d-progression). If
A is a d-progression with one term removed, then A is an almost-progression
with difference d (or an almost d-progression). If A is the union of
two d-progressions, then A is a double-progression with difference d (or a
double d-progression). Note that an arithmetic progression is also an almost-
progression, and that an almost-progression is also a double-progression.
A basic result on sumsets mod p is the following well known theorem.
Theorem 1 (Cauchy–Davenport). |A + B| ≥ min(p, |A| + |B| − 1).
This theorem was proved by Cauchy [1] in 1813 and rediscovered by
Davenport [3], [4]. Both proofs were transformation proofs. Cauchy used a
transform which is essentially the transform called the “Dyson e-transform”
by Mann [7, p. 5] and the “e-transform” by Nathanson [8, p. 42]. Davenport
used a quite different transform.
The Cauchy–Davenport theorem is an example of a direct addition theo-
rem mod p. The corresponding inverse problem is to describe the structure
of those sets A, B for which the cardinality of the sumset A + B is small.
The first nontrivial inverse theorem mod p was found by Vosper [9]. The
essential part of Vosper’s theorem is as follows.
Theorem 2 (Vosper). Suppose that |A|, |B| ≥ 2, and that
|A + B| = |A| + |B| − 1 ≤ p − 2.
Then A and B are arithmetic progressions with the same difference.
2000 Mathematics Subject Classification: 11A07, 11B13.
[251]
252 Y. O. Hamidoune and Ø. J. Rødseth
Vosper first used the Davenport transform in the proof of this result.
Later he presented in [10] a simpler proof using the e-transform. Another
transform was used by Chowla, Mann, and Straus in [2], where they also
gave a nice application of Vosper’s theorem to diagonal forms over Z/pZ (cf.
[7, Chap. 2], [8, p. 57]).
In this paper we use, among other things, the Davenport transform to
give an elementary proof of the following theorem, which goes one step
beyond the theorems of Cauchy–Davenport and Vosper.
Theorem 3. Suppose that |A|, |B| ≥ 3, and that
(1) 7 ≤ |A + B| = |A| + |B| ≤ p − 4.
Then A and B are almost-progressions with the same difference.
This can again be seen to imply the following: Suppose that |A|, |B| ≥ 3,
and that (1) holds. Then one of A and B is a d-progression while the other
is an almost d-progression, or that A = {a, a + 2d, a + 3d, . . . , a + |A|d} and
B = {b, b + 2d, b + 3d, . . . , b + |B|d} for some a, b, d ∈ Z/pZ.
Using exponential sums and analytic methods, Freiman [5], [6] proved
a beautiful inverse theorem for sumsets of the special form A + A (cf. [8,
Theorem 2.11]).
Theorem 4 (Freiman). Let r be an integer , 0 ≤ r ≤ 52 |A| − 2. If
|A + A| = 2|A| − 1 + r and |A| ≤ p/35,
then A is contained in an arithmetic progression with |A| + r elements.
For certain applications it is of interest to relax the condition |A| ≤ p/35.
If r = 0, Theorem 2 shows that this condition can be replaced by |A| ≤
1
2 (p − 1). If r = 1, Theorem 3 shows that the condition can be replaced by
|A| ≤ 12 (p − 5).
2. Preliminaries. Throughout this paper A and B will be nonempty
sets of residue classes modulo p. The sumset A + B was defined in Section 1.
We put 2B = B + B. We write A − B for the set of differences a − b, a ∈ A,
b ∈ B, and we also put x ± B = {x} ± B for a residue class x. We write A \ B
for the complement of B in A. If r is an integer, we shall on some occasions
feel free to write r for the residue class modulo p represented by r.
For residue classes x 6= 0 and y, the set x ∗ A + y = {xa + y | a ∈ A} is
an affine image of A. Most of the results below on sumsets A + B are such
that if there are residue classes x 6= 0, y, z such that a result holds for the
affine images x ∗ A + y and x ∗ B + z, then the result is also true for the
sets A, B. This is the reason why it is on many occasions sufficient to prove
a result for some special choice of an affine image of A or B.
An inverse theorem mod p 253
We shall say that a nonempty set Y ⊆ A is a d-component of A if Y is a
maximal d-progression contained in A. Thus Y 6= ∅ is a d-component of A
if and only if the following two conditions hold:
(i) Y is a d-progression,
(ii) if C is a d-progression such that Y ⊆ C ⊆ A, then Y = C.
Clearly, a set A has a unique partition into d-components. By consider-
ing the residue classes mod p as points on a circle, one readily makes the
following observations:
(I) |{0, 1} + A| ≤ |A| + 1 if and only if A is a 1-progression.
(II) |{0, 1} + A| ≤ |A| + 2 if and only if A is a double 1-progression.
(III) If |A| ≤ p − 3, then |{0, 1, 2} + A| ≤ |A| + 2 if and only if A is a
1-progression.
(IV) If |A| ≤ p − 4, then |{0, 1, 2} + A| ≤ |A| + 3 if and only if A is an
almost 1-progression.
(V) If |A| ≤ p − 1, then |{0, 1} + A| = |A| + k, where k is the number
of 1-components of A.
Lemma 1. Let |B| ≥ 3, and suppose that
(2) |A + B| ≤ |A| + |B| ≤ p − 1.
Also assume that B is a d-progression. Then A is an almost d-progression.
P r o o f. It is sufficient to prove the result for d = 1, and we can as-
sume that B = {0, 1, . . . , |B| − 1}. Then B = {0, 1, 2} + B 0 , where B 0 =
{0, 1, . . . , |B| − 3}. By (2) and Theorem 1, we have
p − 1 ≥ |A| + |B| ≥ |A + B| = |A + {0, 1, 2} + B 0 | ≥ |A + {0, 1, 2}| + |B 0 | − 1,
and since |B 0 | = |B| − 2, we have |A + {0, 1, 2}| ≤ |A| + 3. By (2), we also
have |A| ≤ p−4. Hence, by observation (IV), A is an almost 1-progression.
Lemma 2. Let |B| ≥ 2, and suppose that
(3) |A + B| ≤ |A| + |B| ≤ p − 1.
Also assume that B is a d-progression. Then A is a double d-progression.
P r o o f. If |B| ≥ 3, this is clear by Lemma 1. If |B| = 2, we can assume
that B = {0, 1}. Then, by (3), we have |A + {0, 1}| ≤ |A| + 2, and A is a
double 1-progression by observation (II).
Lemma 3. Suppose that A + B is a d-progression such that
(4) |A + B| ≤ |A| + |B| ≤ p − 3.
Then A is an almost d-progression.
254 Y. O. Hamidoune and Ø. J. Rødseth
P r o o f. We prove the result for d = 1. Using (4), observation (III), and
Theorem 1, we get
p − 1 ≥ |A| + |B| + 2 ≥ |A + B| + 2 ≥ |{0, 1, 2} + A + B|
≥ |{0, 1, 2} + A| + |B| − 1,
so that |{0, 1, 2} + A| ≤ |A| + 3, and the result follows by observation (IV).
3. An inverse theorem. In this section we prove the following inverse
theorem mod p.
Theorem 5. Suppose that |B| ≥ 2, and that
(5) |A + B| = |A| + |B| ≤ p − 4.
Then A is a double-progression.
P r o o f. Suppose that there exist pairs (A, B) such that |B| ≥ 2, (5) is
satisfied, and A is not a double-progression. Choose such a pair where |B| is
minimal. It is no restriction to assume 0 ∈ B. Then A + B ⊆ A + 2B. Since
A + B 6= Z/pZ and B generates Z/pZ, we have A + B 6= A + 2B. Putting
X = (A + 2B) \ (A + B),
we thus have X 6= ∅.
For x ∈ X, let
Bx∗ = {b ∈ B | x − b ∈ A + B}, Bx = B \ Bx∗ .
Then 0 6∈ Bx∗ 6= ∅, and 0 ∈ Bx 6= B. (Here Bx is the transform of B employed
by Davenport in his proof of Theorem 1.)
Moreover, it is easily seen that
(A + Bx ) ∪ (x − Bx∗ ) ⊆ A + B, (A + Bx ) ∩ (x − Bx∗ ) = ∅,
so that
|A + B| ≥ |A + Bx | + |x − Bx∗ | = |A + Bx | + |B| − |Bx |.
Thus we have
p − 4 ≥ |A| + |B| = |A + B| ≥ |A + Bx | + |B| − |Bx |,
so that
|A + Bx | ≤ |A| + |Bx | ≤ p − 5.
By the minimality of |B|, we thus have Bx = {0} for any x ∈ X. Hence
Bx∗ = B 0 (x ∈ X),
0
where B = B \ {0}.
Thus X − B 0 ⊆ A + B, and we see that
A ∪ (X − B 0 ) ⊆ A + B and A ∩ (X − B 0 ) = ∅.
An inverse theorem mod p 255
Hence, using (5) and Theorem 1, we get
|A| + |B| = |A + B| ≥ |A| + |X − B 0 | ≥ |A| + |X| + |B| − 2,
that is, |X| ≤ 2.
Now we have
2 ≥ |X| = |A + 2B| − |A + B| ≥ |A + 2B| − (p − 4),
so that |A + 2B| ≤ p − 2. By Lemma 2, B is not an arithmetic progression.
Since |A + B| ≥ 2, Theorems 1 and 2 thus give
|A + 2B| ≥ |A + B| + |B|,
so that
2 ≥ |X| = |A + 2B| − |A + B| ≥ |B|,
which contradicts the fact that B is not an arithmetic progression.
4. More lemmas
Lemma 4. Suppose that |A| ≥ 3, and that
(6) |A + B| = |A| + |B| ≤ p − 4.
Also assume that A is a double 1-progression. Then one of the following
holds.
(i) B is a double 1-progression.
(ii) A and B are almost-progressions with the same difference.
(iii) |A| = 3, B has three 1-components B1 , B2 , B3 , and there exists an
a ∈ A such that A + B has the three 1-components a + {0, 1} + Bi , i = 1, 2, 3.
P r o o f. If A is a d-progression, then, by Lemma 1, B is an almost d-
progression. We therefore assume that A is not a d-progression for any d. In
particular, A has two 1-components A1 , A2 , |A1 | ≤ |A2 |.
We also assume that (i) is false, so that B is not a double 1-progression.
Thus B has at least three 1-components, and by observation (V),
(7) |{0, 1} + B| ≥ |B| + 3.
We look separately at the cases |A1 | ≥ 2 and |A1 | = 1.
Case 1: |A1 | ≥ 2. Then A = {0, 1} + A0 , where |A0 | = |A| − 2 ≥ 2. By
(6), Theorem 1, and (7), we have
p − 4 ≥ |A| + |B| = |A + B| = |A0 + {0, 1} + B|
≥ |A0 | + |{0, 1} + B| − 1 ≥ |A| + |B|,
so that
|A0 + ({0, 1} + B)| = |A0 | + |{0, 1} + B| − 1 ≤ p − 4.
256 Y. O. Hamidoune and Ø. J. Rødseth
Hence, by Theorem 2, both A0 and {0, 1} + B are d-progressions for some
d. Thus A + B = A0 + {0, 1} + B is a d-progression, and, by Lemma 3, (ii)
holds.
Case 2: |A1 | = 1. Then there is an a ∈ A such that A2 = a +
{0, 1, . . . , |A| − 2}. Thus A2 = {0, 1} + A02 , where A02 = a + {0, 1, . . . , |A| − 3}
and |A02 | = |A| − 2.
By (6), Theorem 1, and (7), we have
p − 4 ≥ |A| + |B| = |A + B| ≥ |A2 + B| = |A02 + {0, 1} + B|
≥ |A02 | + |{0, 1} + B| − 1 ≥ |A| − 2 + |B| + 3 − 1 = |A| + |B|.
We see that A + B = A2 + B. We also have |{0, 1} + B| = |B| + 3, so that,
by observation (V), B has three 1-components B1 , B2 , B3 . Moreover,
p − 4 ≥ |A02 + {0, 1} + B| = |A02 | + |{0, 1} + B| − 1.
If |A| ≥ 4, then |A02 | ≥ 2. Hence by Theorem 2, both A02 and {0, 1} + B
are d-progressions. Thus A+B = A2 +B = A02 +{0, 1}+B is a d-progression,
and by Lemma 3, (ii) holds.
Finally, suppose that |A| = 3. Then A is not an arithmetic progression.
If
|{0, 1} + A + B| ≤ |A + B| + 2,
we thus have by (6), Theorems 1 and 2, and (7),
p − 2 ≥ 3 + |B| + 2 = |A + B| + 2 ≥ |{0, 1} + A + B|
≥ |A| + |B + {0, 1}| ≥ 3 + |B| + 3,
a contradiction. Hence,
|{0, 1} + A + B| ≥ |A + B| + 3,
and, by observation (V), A + B has at least three 1-components. Now,
S3
A + B = A2 + B = a + {0, 1} + B = i=1 (a + {0, 1} + Bi ). Since each
set a + {0, 1} + Bi is a 1-progression, A + B has the three 1-components
a + {0, 1} + Bi , i = 1, 2, 3.
Lemma 5. Let |A|, |B| ≥ 3, and suppose that
7 ≤ |A + B| = |A| + |B| ≤ p − 4.
Also assume that A is an almost-progression. Then A and B are almost-
progressions with the same difference.
P r o o f. Suppose that A is an almost 1-progression, and that A and B
are not almost-progressions with the same difference. By Lemma 1, neither
A nor B is an arithmetic progression. In particular, A has two 1-components
A1 , A2 , |A1 | ≤ |A2 |. We look separately at cases (i) and (iii) in Lemma 4.
An inverse theorem mod p 257
We first consider (i). Then B is a double 1-progression. Since B is not an
arithmetic progression, it has two 1-components B1 , B2 , |B1 | ≤ |B2 |. Since
|B| ≥ 3, we have |B2 | ≥ 2.
We have
(8) A + B = (A1 + B1 ) ∪ (A2 + B1 ) ∪ (A + B2 ).
Both A1 + B1 and A2 + B1 are 1-progressions. Since A is an almost 1-
progression and B2 is a 1-progression with at least two elements, we also find
that A + B2 is a 1-progression. Thus A + B has at most three 1-components.
By Lemma 3, A + B has at least two 1-components. Thus A + B has two
or three 1-components. If they are three, then they are given in (8). Then
we must have |B1 | = 1, for otherwise (A1 + B1 ) ∪ (A2 + B1 ) = A + B1 would
be a 1-progression. We have
|A + B2 | = |A| + |B2 | = |A| + |B| − 1,
and
|A| + |B| = |A + B| = |A1 + B1 | + |A2 + B1 | + |A + B2 |
= |A1 | + |A2 | + |A| + |B| − 1 = 2|A| + |B| − 1 ≥ |A| + |B| + 2,
a contradiction. Thus A + B has two 1-components.
By observation (V), we have |{0, 1} + A| = |A| + 2 and |{0, 1} + A + B| =
|A + B| + 2, so that
p − 2 ≥ |{0, 1} + A| + |B| = |A| + |B| + 2 = |A + B| + 2 = |{0, 1} + A + B|;
that is,
|{0, 1} + A + B| = |{0, 1} + A| + |B| ≤ p − 2.
Since A is an almost 1-progression, {0, 1} + A is a 1-progression. It follows
by Lemma 1 that B is an almost 1-progression, which is a contradiction.
We now consider case (iii) of Lemma 4. Then |A| = 3 and |B| ≥ 4. Let
the three components of B satisfy |B1 | ≤ |B2 | ≤ |B3 |. Then |B3 | ≥ 2, and
A + B3 is a 1-progression contained in some 1-component a + {0, 1} + Bi of
A + B. Thus we have
1 + |Bi | = |a + {0, 1} + Bi | ≥ |A + B3 | = 3 + |B3 |,
a contradiction.
Lemma 6. Let |A|, |B| ≥ 3, and suppose that
(9) |A + B| = |A| + |B| ≤ p − 4.
Also assume that both A and B are double 1-progressions, and that B is
not an almost 1-progression. Let A1 be a 1-component of A, and let B1 , B2
be the two 1-components of B. Then A1 + B1 and A1 + B2 lie in distinct
1-components of A + B. Moreover ,
(10) |A1 | ≥ 21 |A| − 1.
258 Y. O. Hamidoune and Ø. J. Rødseth
P r o o f. By Lemma 1, A is not a 1-progression. Thus A has one more
1-component A2 = A \ A1 .
Suppose that A1 + B1 and A1 + B2 are contained in one 1-component
C of A + B. We can assume that A1 = {0, 1, . . . , |A1 | − 1}. Since C is a
1-progression containing A1 + B and B is not an almost-progression, it is
then easy to see that
(11) |C| ≥ |A1 | + |B| + 1.
If C = A+B, then A+B is a 1-progression, so that, by Lemma 3, B is an
almost 1-progression, a contradiction. Thus A + B contains a 1-component
C 0 6= C.
We have
A + B = (A1 + B1 ) ∪ (A1 + B2 ) ∪ (A2 + B1 ) ∪ (A2 + B2 ),
where (A1 + B1 ) ∪ (A1 + B2 ) ⊆ C, and both A2 + B1 and A2 + B2 are
1-progressions. Either for i = 1 or for i = 2, we have A2 + Bi ⊆ C 0 , so that,
by (9), (11), and Theorem 1,
p − 4 ≥ |A| + |B| ≥ |C| + |C 0 | ≥ |A1 | + |B| + 1 + |A2 + Bi |
≥ |A1 | + |B| + 1 + |A2 | + |Bi | − 1 = |A| + |B| + |Bi |,
hence |Bi | ≤ 0, a contradiction. Thus A1 + B1 and A1 + B2 lie in distinct
1-components of A + B.
Moreover, by Theorem 1, we now have
p − 4 ≥ |A| + |B| = |A + B| ≥ |A1 + B1 | + |A1 + B2 | ≥ 2|A1 | + |B| − 2,
so that |A| ≥ 2|A1 |−2. This also holds for the other 1-component A2 = A\A1
of A, so that |A| ≥ 2|A \ A1 | − 2, and (10) follows.
Lemma 7. Let |A|, |B| ≥ 3, and suppose that
7 ≤ |A + B| = |A| + |B| ≤ p − 4.
Let A1 , A2 be the distinct 1-components of A, and let B1 , B2 be the distinct
1-components of B. Also suppose that B is not an almost d-progression for
any d. The 1-components of A + B are then (A1 + B1 ) ∪ (A2 + B2 ) and
(A2 + B1 ) ∪ (A1 + B2 ).
P r o o f. We can assume that |A1 | ≥ |A2 | and |B1 | ≥ |B2 |. By Lemma 6,
A1 + B1 and A1 + B2 lie in distinct 1-components of A + B, so that A + B
has at least two 1-components.
Suppose that A+B has at least three 1-components. A third 1-component
must then contain A2 + Bi for i = 1 or 2, and using Theorem 1, we get
p − 4 ≥ |A| + |B| ≥ |A1 + B1 | + |A1 + B2 | + |A2 + Bi |
≥ |A1 | + |B1 | − 1 + |A1 | + |B2 | − 1 + |A2 | + |Bi | − 1
≥ |A| + |B| + |A1 | + |B2 | − 3,
An inverse theorem mod p 259
so that
(12) |A1 | + |B2 | ≤ 3.
By Lemma 5, since B is not an almost-progression, neither is A. Hence,
by symmetry, we also have
(13) |A2 | + |B1 | ≤ 3,
and adding (12) and (13), we get |A| + |B| ≤ 6, which is against the hy-
potheses. Therefore, A + B has exactly two distinct 1-components C1 , C2 .
Assume that A1 + B1 ⊆ C1 and A1 + B2 ⊆ C2 . By Lemma 6, A1 + B1
and A2 + B1 lie in distinct 1-components of A + B. Thus A2 + B1 ⊆ C2 .
Similarly, A2 + B2 ⊆ C1 .
Lemma 8. Let |A|, |B| ≥ 3, and suppose that
7 ≤ |A + B| = |A| + |B| ≤ min(p − 4, 8).
Then B is an almost-progression.
P r o o f. By Lemma 5, if A is an almost-progression, so is B. Therefore it
is sufficient to show that one of A and B is an almost-progression. We can
assume |A| ≥ |B|. Then |A| ≥ 4. Also assume that neither A nor B is an
almost-progression.
By Theorem 5, A is a double d-progression for some d. We can assume
that d = 1. Thus A is a double 1-progression. By Lemma 4, so is B.
After some suitable affine transformations of A and B, we get to consider
the following cases.
Case I: |A| = 4, |B| = 3.
Case I.1: A = {0, 1, 2, u}, B = {0, 1, v}. By Lemma 7, A + B has the
two 1-components
C1 = {0, 1, 2, 3} ∪ {u + v}, C2 = {u, u + 1} ∪ {v, v + 1, v + 2}.
We have |C1 | + |C2 | = |A + B| = |A| + |B| = 7. Since p ≥ 11, we have
|C1 | ≥ 4 and |C2 | ≥ 3; thus |C1 | = 4 and |C2 | = 3. By looking at C1 , we see
that u + v = 0, 1, 2, or 3. From C2 , we see that u = v or u = v + 1.
If u = v, then 2v = 0, 1, 2, or 3. Since v 6= 0, 1, we have v = 1/2 or
v = 3/2, and
B = {0, 1/2, 1} = {0, d, 2d} or B = {0, 1, 3/2} = {0, 2d, 3d},
where d = (p + 1)/2. This contradicts the fact that B is not an almost-
progression.
If u = v + 1, then 2v + 1 = 0, 1, 2, or 3, so that v = ±1/2. Thus
B = {−1/2, 0, 1} = {b, b + d, b + 3d} for b = (p − 1)/2, d = (p + 1)/2, or
B = {0, 1/2, 1}, and again we have reached a contradiction.
260 Y. O. Hamidoune and Ø. J. Rødseth
Case I.2: A = {0, 1, u, u + 1}, B = {0, 1, v}. By Lemma 7, A + B has
the two 1-components
C1 = {0, 1, 2} ∪ {u + v, u + v + 1}, C2 = {u, u + 1, u + 2} ∪ {v, v + 1}.
We still have |C1 | + |C2 | = 7. By symmetry, we can assume that |C1 | ≥ |C2 |.
Then |C1 | = 4, |C2 | = 3. We see that u + v = −1 or 2, and that u = v
or u = v − 1. If u = v, we find that B = {−1/2, 0, 1}, a contradiction. If
u = v − 1, then B = {0, 1, 3/2}, which is also a contradiction.
Case II: |A| = 5, |B| = 3. Let A1 , A2 be the two 1-components of A,
|A1 | ≤ |A2 |. By Lemma 6, we then have |A1 | ≥ 21 |A| − 1 = 3/2, so that
|A1 | ≥ 2; hence |A1 | = 2 and |A2 | = 3. Thus we can assume that
A = {0, 1, 2, u, u + 1}, B = {0, 1, v}.
By Lemma 7, A + B then has the two 1-components
C1 = {0, 1, 2, 3}∪{u+v, u+v +1}, C2 = {u, u+1, u+2}∪{v, v +1, v +2}.
We have |C1 |+|C2 | = |A+B| = |A|+|B| = 8. Clearly, we also have |C1 | ≥ 4,
|C2 | ≥ 3.
Case II.1: |C1 | = 5, |C2 | = 3. We have u + v = −1 or 3, and u = v.
Then B = {−1/2, 0, 1} or B = {0, 1, 3/2}, a contradiction.
Case II.2: |C1 | = |C2 | = 4. We have u + v = 0, 1, or 2, and u = v ± 1.
If u = v − 1, we have B = {0, 1/2, 1} or B = {0, 1, 3/2}, a contradiction. If
u = v + 1, we have B = {−1/2, 0, 1} or B = {0, 1/2, 1}, a contradiction.
Case III: |A| = |B| = 4.
Case III.1: A = {0, 1, 2, u}, B = {0, 1, 2, v}. By Lemma 7, A + B has
the two 1-components
C1 = {0, 1, 2, 3, 4} ∪ {u + v}, C2 = {u, u + 1, u + 2} ∪ {v, v + 1, v + 2}.
We have |C1 | + |C2 | = 8, |C1 | ≥ 5, |C2 | ≥ 3, so that |C1 | = 5, |C2 | = 3. Thus
u + v = 0, 1, 2, 3, or 4, and u = v. It follows that v = 1/2 or 3/2, so that
B = {0, 1/2, 1, 2} or B = {0, 1, 3/2, 2}, a contradiction.
Case III.2: A = {0, 1, u, u + 1}, B = {0, 1, 2, v}. Similarly to Case III.1,
we find that B = {0, 1/2, 1, 2} or B = {0, 1, 3/2, 2}, a contradiction.
Case III.3: A = {0, 1, u, u + 1}, B = {0, 1, v, v + 1}. By Lemma 7, A + B
has the two 1-components
C1 = {0, 1, 2} ∪ {u + v, u + v + 1, u + v + 2},
C2 = {u, u + 1, u + 2} ∪ {v, v + 1, v + 2}.
By symmetry, we can assume that |C1 | ≥ |C2 |. We have |C1 | + |C2 | = 8,
and |C2 | ≥ 3.
An inverse theorem mod p 261
Case III.3.1: |C1 | = 5, |C2 | = 3. We see that u + v = ±2, and that
u = v. Thus v = ±1, which is impossible.
Case III.3.2: |C1 | = |C2 | = 4. We have u + v = ±1, and u = v ± 1.
If u = v − 1, we get v = 0 or 1, which is impossible. If u = v + 1, we get
v = −1 or 0, which is also impossible.
5. Proof of Theorem 3, concluded. Assume the theorem is false, and
let (A, B) be a counterexample with |A| + |B| minimal and |A| ≥ |B|. Then
(1) holds, |A| ≥ 4, |B| ≥ 3, and A and B are not almost-progressions with
the same difference. By Lemma 5, neither A nor B is an almost-progression.
By Theorem 5, A is a double d-progression for some d. We can assume
d = 1. Thus A is a double 1-progression. By Lemma 4, so is B.
Let A1 , A2 be the two 1-components of A. By Lemma 8, we have |A| +
|B| ≥ 9, so that |A| ≥ 5. By Lemma 6, we have |Ai | ≥ 12 |A| − 1 ≥ 3/2,
so that |Ai | ≥ 2 for i = 1, 2. Hence, A = {0, 1} + A0 , where A0 is a double
1-progression with |A0 | = |A| − 2 ≥ 3.
Let k be the number of 1-components of A0 + B. If k = 1, then A0 + B
is a 1-progression, and so is A + B = {0, 1} + A0 + B. By Lemma 3, A is an
almost-progression, a contradiction. Hence k ≥ 2.
Since |A0 | ≥ 3 and B is not an arithmetic progression, we have by (1),
observation (V), and Theorems 1 and 2,
p − 4 ≥ |A| + |B| = |A + B| = |{0, 1} + A0 + B|
= |A0 + B| + k ≥ |A0 | + |B| + k = |A| − 2 + |B| + k,
so that k ≤ 2; hence k = 2. It follows that
7 ≤ |A0 + B| = |A0 | + |B| ≤ p − 6.
We also have |A0 | ≥ 3, |B| ≥ 3. By the minimality of |A| + |B|, we now
deduce that A0 and B are almost-progressions, a contradiction.
References
[1] A. L. C a u c h y, Recherches sur les nombres, J. École Polytech. 9 (1813), 99–116.
[2] S. C h o w l a, H. B. M a n n, and E. G. S t r a u s, Some applications of the Cauchy–
Davenport theorem, Norske Vid. Selsk. Forh. 32 (1959), 74–80.
[3] H. D a v e n p o r t, On the addition of residue classes, J. London Math. Soc. 10 (1935),
30–32.
[4] —, A historical note, ibid. 22 (1947), 100–101.
[5] G. A. F r e i m a n, Inverse problems of additive number theory. On the addition of sets
of residues with respect to a prime modulus, Dokl. Akad. Nauk SSSR 141 (1961),
571–573 (in Russian).
[6] —, Inverse problems of additive number theory. On the addition of sets of residues
with respect to a prime modulus, Soviet Math. Dokl. 2 (1961), 1520–1522.
262 Y. O. Hamidoune and Ø. J. Rødseth
[7] H. B. M a n n, Addition Theorems: The Addition Theorems of Group Theory and
Number Theory, Interscience Publ., New York, 1965.
[8] M. B. N a t h a n s o n, Additive Number Theory: Inverse Problems and the Geometry
of Sumsets, Springer, New York, 1996.
[9] A. G. V o s p e r, The critical pairs of subsets of a group of prime order, J. London
Math. Soc. 31 (1956), 200–205.
[10] —, Addendum to “The critical pairs of subsets of a group of prime order”, ibid. 31
(1956), 280–282.
E. Combinatoire Department of Mathematics
Université P. et M. Curie University of Bergen
4 Place Jussieu Johs. Brunsgt. 12
75005 Paris, France N-5008 Bergen, Norway
E-mail: yha@[Link] E-mail: rodseth@[Link]
Received on 16.4.1999
and in revised form on 30.9.1999 (3593)