RECTIFICATION PRINCIPLES IN ADDITIVE NUMBER THEORY

YURI F. BILU, VSEVOLOD F. LEV, AND IMRE Z. RUZSA

To the memory of Paul Erdős

Abstract. We consider two general principles which allow one to reduce certain additive problems for residue classes modulo a prime to the corresponding problems for integers.

1. Introduction

It is well-known that additive problems in finite abelian groups are generally more difficult than analogous problems in ℤ. For instance, consider the following classical problem: given an abelian group G, describe all pairs of finite sets K, L ⊆ G such that

|K + L| < |K| + |L|.

When G = ℤ (or a torsion-free abelian group) the answer is almost trivial: K and L must be arithmetic progressions with the same difference. When G is a cyclic group of prime order, the answer is given by Vosper’s theorem [24], which is quite non-trivial. And when G is an arbitrary finite abelian group, one should turn to the extremely complicated recursive classification of Kemperman [14]. (A few years ago the problem was solved for torsion-free non-abelian groups [6, 13].)

Nevertheless, more than 30 years ago Freiman [10, Section 3.13] discovered that, at least for cyclic groups of prime order, certain additive problems can be reduced to corresponding problems in ℤ, provided the sets in consideration are “not very large.” Seemingly, this important observation did not receive much attention.

On the other hand, it was recently observed in [15] that there is another reduction method. It is weaker than Freiman’s one in that it requires the sets to be “very small” instead of “not very large.” However, unlike the method of Freiman it imposes no additional restrictions on the sets and handles easily the case of distinct summands, which makes it applicable when Freiman’s method fails.

The objective of this note is to popularize Freiman’s discovery along with the other reduction method mentioned above and to show how they can be applied to concrete additive problems.

Research of the first author supported by the SFB 170 “Geometrie und Analysis” at Göttingen.

Research of the third author supported by Hungarian National Foundation for Scientific Research, Grant No. 17433.

Acknowledgment We would like to thank Dani Berend and the referee for pointing out some inaccuracies in the manuscript.

2. Freiman’s rectification principle

For simplicity, we consider only the case of equal summands: K = L. Using [22, Lemma 3.3] one can extend the results to distinct summands.

We need the concept of F_{s}-isomorphism [10, 22]. Let G, H be abelian groups, and consider subsets K ⊂ G and L ⊂ H. The bijection φ: K → L is Freiman’s isomorphism of order s or, shortly, F_{s}-isomorphism, if for any a_{1}, …, a_{2s} ∈ K,

a_{1} + ⋯ + a_{s} = a_{s+1} + ⋯ + a_{2s}

if and only if

φ(a_{1}) + ⋯ + φ(a_{s}) = φ(a_{s+1}) + ⋯ + φ(a_{2s}).

It is easily seen that, if K and L are F_{s+1}-isomorphic, then they also are F_{s}- isomorphic. Clearly, two sets K and L are F_{1}-isomorphic if and only if |K| = |L|.

Theorem 2.1 (Freiman’s rectification principle). For any positive numbers σ ∈ ℝ and s ∈ ℤ there exists a positive constant c_{1} = c_{1}(σ, s) such that the following holds.

Let p be a prime number and let K ⊆ ℤ/pℤ satisfy |K| ≤ c_{1}p and

|K + K| < σ|K|.

Then there exists a set of integers K′ ⊂ ℤ such that the the canonical homomorphism ℤ → ℤ/pℤ induces an F_{s}-isomorphism of K′ onto K.

To put it briefly, this theorem asserts that if a set of residues has a small sumset and is not too large itself, then it is F_{s}-isomorphic to a set of integers.

A proof of Theorem 2.1 (for s = 2) is briefly sketched in [10, Section 3.12]. Our proof given below is simpler than the original, but requires no substantially new ideas.

The argument is based on the following result of Freiman.

Theorem 2.2 (Freiman). Let σ be a positive real number and let K be a finite set of integers satisfying

|K + K| < σ|K|.

Then there exist positive integers r, b_{1}, …, b_{r} and non-zero integers g_{0}, g_{1}, …, g_{r} such that

r ≤ c_{2}(σ), b_{1} ⋯ b_{r} ≤ c_{3}(σ)|K|,

and

K ⊆ Π = Π(g_{0}; g_{1}, …, g_{r}; b_{1}, …, b_{r}) := {g_{0} + β_{1}g_{1} + ⋯ + β_{r}g_{r}: β_{i} = 0, …, b_{i} − 1},

where c_{2}(σ) and c_{3}(σ) are positive constants, depending only on σ.

There are two different proofs of this theorem. The first is Freiman’s original, see [10, 11, 3]. The second is due to Ruzsa, see [23, 20].

Proof of Theorem 2.1. We shall see that the theorem holds with

c_{1} = (2sc_{2}(2σ))^{−c_{2}(2σ)} (c_{3}(2σ))^{−1}.

Let K_{0} ⊆ {0, 1, …, p−1} be the pre-image of K under the canonical homomorphism ℤ → ℤ/pℤ. Then |K_{0} + K_{0}| ≤ 2|K + K| < 2σ|K_{0}|, whence by Theorem 2.2 we have K_{0} ⊆ Π(g_{0}; g_{1}, …, g_{r}; b_{1}, …, b_{r}), where r, b_{1}, …, b_{r} are positive integers satisfying

r ≤ c_{2}(2σ), b_{1} ⋯ b_{r} ≤ c_{3}(2σ)|K|,

and g_{1}, …, g_{r} ∈ ℤ.

Put ε_{i} = (2srb_{i})^{−1}. Then

pε_{1} ⋯ ε_{r} = p(2sr)^{−r}(b_{1} ⋯ b_{r})^{−1} ≥ p(2sc_{2}(2σ))^{−c_{2}(2σ)}(c_{3}(2σ))^{−1}|K|^{−1} = c_{1}p|K|^{−1} ≥ 1.

Hence by Minkowski’s theorem on linear inequalities [7, Appendix B, Theorem III], there exists a non-zero vector (a, a_{1}, …, a_{r}) ∈ ℤ^{r+1} such that

|a| < p,
(2.1)  |ag_{i}/p − a_{i}| ≤ ε_{i} (1 ≤ i ≤ r).

We have a ≠ 0, since otherwise it would follow from (2.1) that a_{1} = … = a_{r} = 0. Thus, the integer a satisfies

a ≢ 0 (mod p)
∥ag_{i}/p∥ ≤ ε_{i} (1 ≤ i ≤ r),

where ∥ · ∥ stands for the distance from the nearest integer. This gives

∥a(x − g_{0})/p∥ ≤ ∑_{i=1}^{r} b_{i} ∥ag_{i}/p∥ ≤ (2s)^{−1}

for any x ∈ K_{0}.

Let

K_{1} ⊆ {− ⌊p/(2s)⌋ , − ⌊p/(2s)⌋ + 1, …, ⌊p/(2s)⌋}

be the set of integers congruent modulo p to one of the numbers a(x − g_{0}) (for some x ∈ K_{0}). Clearly, K_{1} is mapped onto K by x ↦ ux+g_{0} mod p, where u is an arbitrary integer satisfying au ≡ 1 (mod p). It follows that K_{1} is F_{s}-isomorphic to K, for any algebraic sum of 2s elements of K_{1} which is 0 modulo p is also 0 in ℤ.

Finally, we define K′ = {ux + g_{0} : x ∈ K_{1}}. □

Freiman’s rectification principle allows one to reduce various additive problems in ℤ/pℤ to corresponding problems in ℤ. Unfortunately, we have to make the restrictive assumption |K| ≤ c_{1}p. Restricting to “not very large” sets is the price one has to pay for the use of such a powerful tool as Freiman’s Theorem 2.2. For instance, the main results of [4] and [5] also assume that sets in question are small enough.

It would be nice to find a proof of the rectification principle independent of Theorem 2.2. For σ < 2.4 and s = 2 such a proof is implicit in [10, Section 2.3], where the following result is obtained.

Theorem 2.3 (Freiman [10]). Let K ⊆ ℤ/pℤ satisfy |K +K| < 2.4|K|, and suppose, in addition, that |K| < p/35. Then K can be covered by a “short” arithmetic progression modulo p: There exist g_{0}, g_{1} ∈ ℤ/pℤ and a positive integer b ≤ |K + K| − |K| + 1 such that

(2.2)  K ⊆ {g_{0} + g_{1}β: β = 0, …, b − 1}.

Conjecturally, the assertion of this theorem is true for |K +K| ≤ max{p−1, 3|K|− 4}. Using Theorem 2.1, one can easily prove it for sufficiently small K.

Indeed, suppose that |K| < c_{1}p, where c_{1} = c_{1}(3, 2) is the constant of Theorem 2.1. Let K′ ⊂ ℤ be the set of integers which is F_{2}-isomorphic to K and is mapped onto K by the canonical mapping ℤ → ℤ/pℤ. Then K′ also satisfies |K′ + K′| ≤ 3|K′| − 4 (since |K′| = |K| and |K′ + K′| = |K + K| by the definition of F_{s}-isomorphism). By another and well-known result of Freiman [10, Theorem 1.9] (which has a relatively easy elementary proof; see also [17]), there exist a, d ∈ ℤ and a positive integer b ≤ |K′ + K′| − |K′| + 1 such that

K′ ⊆ {a + dβ: β = 0, …, b − 1}.

Now (2.2) is clearly satisfied if g_{0} and g_{1} are the elements of ℤ/pℤ congruent to a and d respectively.

This is a first illustrative example which shows how rectification methods can be used to reduce difficult additive problems in ℤ/pℤ to easier problems in ℤ.

3. Direct rectification

Theorem 2.1 shows that any (not too large) set of residues K ⊆ ℤ/pℤ with a small sumset is isomorphic to a set of integers. It turns out that this is true for any K, regardless of its sumset, provided that |K| is very small. Specifically, it is shown in [15] that any K ⊆ ℤ/pℤ of the cardinality k = |K| is contained in an arithmetic progression modulo p of at most

(3.1)  2k^{− \frac{1}{k−1}} p^{1− \frac{1}{k−1}} + 1

terms. If k ≤ log_{4} p + log_{4} log_{4} p (where log_{4} is the logarithm base 4), then the number (3.1) is less than p/2 + 1, whence K is F_{2}-isomorphic to a set of integers. Similarly, if k ≤ log_{2s} p + log_{2s} log_{2s} p, then K is F_{s}-isomorphic to a set of integers. Essentially the same can be obtained by a direct application of the idea we used in the proof of Theorem 2.1.

Theorem 3.1. Let K ⊆ ℤ/pℤ, where p is a prime. If |K| ≤ log_{2s} p then there exists a set of integers K′ ⊂ ℤ such that the canonical homomorphism ℤ → ℤ/pℤ induces an F_{s}-isomorphism of K′ onto K.

Proof. Let K = {g_{1}, …, g_{r}}, and put ε_{1} = … = ε_{r} = (2s)^{−1}. Since r ≤ log_{2s} p, we have pε_{1} ⋯ ε_{r} ≥ 1. Therefore, applying Minkowski’s theorem exactly in the same way as in the proof of Theorem 2.1, we find a ∈ ℤ satisfying

a ≢ 0 (mod p)
∥ag_{i}/p∥ ≤ (2s)^{−1} (1 ≤ i ≤ r).

Now let m_{i} ∈ {− ⌊p/(2s)⌋ , − ⌊p/(2s)⌋ + 1, …, ⌊p/(2s)⌋} be defined from m_{i} ≡ ag_{i} (mod p), and put K′ = {um_{1}, …, um_{k}} where u is any integer, inverse to a in ℤ/pℤ. Then the canonical homomorphism ℤ → ℤ/pℤ maps K′ onto K, and this mapping is an F_{s}-isomorphism, which follows immediately from |m_{i}| < p/(2s) (as in the proof of Theorem 2.1). □

This theorem is nearly best possible: here is an example which shows that there exists a set K ⊆ ℤ/pℤ of cardinality |K| ≤ 2 log_{2} p + 1 which is not F_{2}-isomorphic to any set of integers (This example can easily be generalized to produce a set of cardinality at most 2 log_{s} p + 1 which is not F_{s}-isomorphic to any set of integers.)

Put N = ⌊log_{2} p⌋, and write p = 2^{d_{1}} + 2^{d_{2}} + ⋯ + 2^{d_{t}}, where 0 ≤ d_{1} < d_{2} < ⋯ < d_{t}, t ≤ N + 1. We define

K = {0} ∪ {1, 2, 4, …, 2^{N}} ∪ {2^{d_{1}} + 2^{d_{2}}, 2^{d_{1}} + 2^{d_{2}} + 2^{d_{3}}, …, 2^{d_{1}} + 2^{d_{2}} + ⋯ + 2^{d_{t−1}}}

(all the numbers are considered as residues modulo p), so that |K| ≤ 2N + 1. We assume that K is F_{2}-isomorphic to a set of integers

K′ = {0} ∪ {a_{0}, a_{1}, a_{2}, …, a_{N}} ∪ {b_{2}, b_{3}, …, b_{t−1}}

and obtain a contradiction. Let φ: K → K′ be the isomorphism. As the notation suggests, we suppose (which does not restrict the generality) that φ(0) = 0 and that a_{i}, b_{i} are the images in K′ of the corresponding elements of K. Then for any i ∈ [0, N − 1], the equality in ℤ/pℤ

0 + 2^{i+1} = 2^{i} + 2^{i}

implies

0 + a_{i+1} = a_{i} + a_{i},

which yields subsequently

a_{1} = 2a_{0}, a_{2} = 4a_{0} , …, a_{N} = 2^{N}a_{0}.

Next, from

0 + (2^{d_{1}} + 2^{d_{2}}) = 2^{d_{1}} + 2^{d_{2}}

we obtain

b_{2} = (2^{d_{1}} + 2^{d_{2}})a_{0},

and then from

0 + (2^{d_{1}} + ⋯ + 2^{d_{i}} + 2^{d_{i+1}}) = (2^{d_{1}} + ⋯ + 2^{d_{i}}) + 2^{d_{i+1}}

for i = 2, …, t − 2 we obtain

b_{i+1} = b_{i} + a_{d_{i+1}},

which yields

b_{3} = (2^{d_{1}} + 2^{d_{2}} + 2^{d_{3}})a_{0} , …, b_{t−1} = (2^{d_{1}} + 2^{d_{2}} + ⋯ + 2^{d_{t−1}})a_{0}.

But this is a contradiction in view of

b_{t−1} + a_{d_{t}} = a_{0}p ≠ 0 + 0 in ℤ,
(2^{d_{1}} + 2^{d_{2}} + ⋯ + 2^{d_{t−1}}) + 2^{d_{t}} = 0 + 0 in ℤ/pℤ.

To show how Theorem 3.1 can be applied in the case of distinct summands, consider the following problem: given s sets K_{1}, …, K_{s} in an abelian group G, how many representations of the form

(3.2)  x = a_{1} + ⋯ + a_{s}; a_{i} ∈ K_{i} (i = 1, …, s)

can an element x ∈ G have? We assume here that the cardinalities |K_{i}| are preassigned. For G = ℤ, we have the following result:

Theorem 3.2 ([16, Theorem 1]). Let K_{1}, …, K_{s} ⊆ ℤ be finite sets of integers. Then the number of solutions of (3.2) is maximized, when x = 0, and K_{i} are the sets of consecutive integers

K_{i} = {α_{i}, α_{i} + 1, …, γ_{i}} (i = 1, …, s),

where integers α_{i}, γ_{i} are chosen in such a way that

γ_{i} − α_{i} + 1 = |K_{i}|, |α_{i} + γ_{i}| ≤ 1 (i = 1, …, s),
|(α_{1} + γ_{1}) + ⋯ + (α_{s} + γ_{s})| ≤ 1.

Using direct rectification we can easily transfer Theorem 3.2 to small subsets of ℤ/pℤ.

Theorem 3.3. Let K_{1}, …, K_{s} ⊆ ℤ/pℤ be sets of residues modulo prime p, and assume that |K_{1}| + ⋯ + |K_{s}| ≤ log_{2s} p. Then the number of solutions of (3.2) is maximized, when x = 0, and K_{i} are the sets of consecutive residues

K_{i} = {α_{i}, α_{i} + 1, …, γ_{i}} (mod p) (i = 1, …, s),

where integers α_{i}, γ_{i} are chosen in such a way that

γ_{i} − α_{i} + 1 = |K_{i}|, |α_{i} + γ_{i}| ≤ 1 (i = 1, …, s), (3.3) |(α_{1} + γ_{1}) + ⋯ + (α_{s} + γ_{s})| ≤ 1. (3.4)

Proof. For any abelian group G and for any L_{1}, …, L_{s} ⊆ G, x ∈ G denote by N_{x}(L_{1}, …, L_{s}) the number of solutions of

a_{1} + ⋯ + a_{s} = x; a_{i} ∈ L_{i},

and let

N(L_{1}, …, L_{s}) = max_{x∈G} N_{x}(L_{1}, …, L_{s}).

Define K = K_{1} ∪ … ∪ K_{s}. Let φ: K′ → K be an F_{s}-isomorphism of a set of integers K′ ⊆ ℤ onto K, and let K′_{i} be the pre-image of K_{i} in K′ (i = 1, …, s). Then evidently an equality

a′_{1} + ⋯ + a′_{s} = a′_{s+1} + ⋯ + a′_{2s}

with a′_{i}, a′_{s+i} ∈ K′_{i} holds if and only if

φ(a′_{1}) + ⋯ + φ(a′_{s}) = φ(a′_{s+1}) + ⋯ + φ(a′_{2s})

holds, and it follows that

N(K_{1}, …, K_{s}) = N(K′_{1}, …, K′_{s}).

By Theorem 3.2, the right-hand side can only increase if for all i = 1, …, s we replace K′_{i} by K′′_{i} = {α_{i}, α_{i} + 1, …, γ_{i}} ⊆ ℤ, where α_{i}, γ_{i} satisfy (3.3) and (3.4):

N(K′_{1}, …, K′_{s}) ≤ N(K′′_{1}, …, K′′_{s}).

Now, let \overline{K}_{i} be the images of K′′_{i} under the canonical homomorphism ℤ → ℤ/pℤ. The assertion of the theorem follows from the observation that for any integer x ∈ \{− ⌊p/2⌋ , − ⌊p/2⌋ + 1, …, ⌊p/2⌋\} with the corresponding residue \overline{x} ∈ ℤ/pℤ,

N_{x}(K′′_{1}, …, K′′_{s}) = N\overline{x}(\overline{K}_{1}, …, \overline{K}_{s}),

and thus

N(K′′_{1}, …, K′′_{s}) = N(\overline{K}_{1}, …, \overline{K}_{s}).
□

Notice, that in the proof above one could not apply Theorem 2.1 not only because the sets K_{i} are distinct, but also (and mainly) because there are no restrictions on the cardinalities |2K_{i}|. However, Theorem 3.1 works perfectly in this situation.

4. Erdős-Heilbronn conjecture

Let h ≥ 2 be an integer and let K be a subset of the set of elements of an abelian group. Denote by hˆ K the set of all sums of h distinct elements from K:

hˆ K = {a_{1} + ⋯ + a_{h}: a_{1}, …, a_{h} ∈ K and a_{i} ≠ a_{j} for 1 ≤ i < j ≤ h}.

Let p be a prime. Erdős and Heilbronn (see [9, page 95]) conjectured that any K ⊆ ℤ/pℤ satisfies

(4.1)  |2ˆ K| ≥ min{2|K| − 3, p}.

Note that the inequality |2ˆ K| ≥ 2|K| − 3 trivially holds for K ⊆ ℤ (and for finite subsets of torsion-free abelian groups). In general, we have

Proposition 4.1 (folklore).

a) For any positive integer h and any finite set K ⊆ ℤ we have

(4.2)  |hˆ K| ≥ h|K| − h^{2} + 1.

b) If |K| ≥ max{h + 2, 5} then equality in (4.2) holds if and only if K is an arithmetic progression.

For a proof see [19, Theorems 1 and 2], [5, Appendix C], or [20, Theorem 1.10]. After a number of partial results, say, [12, 18, 21] (see [2] for more references), Erdős-

Heilbronn conjecture (4.1) was finally settled by Dias da Silva and Hamidoune [8]. Another proof was suggested in [1]. Actually, Dias da Silva and Hamidoune proved a more general inequality

(4.3)  |hˆ K| ≥ min{h|K| − h^{2} + 1, p}

for arbitrary h ≥ 2 and K ⊆ ℤ/pℤ.

Recently Alon, Nathanson and Ruzsa [2] obtained a fairly general additive theorem which contains inequality (4.3) as a particular case.

However, to the best of our knowledge, the problem of when the equality in (4.3) holds is still open. Here we obtain an answer for sufficiently small K ⊆ ℤ/pℤ as a direct consequence of Proposition 4.1 (b) and Theorem 2.1.

Theorem 4.1. For any h ≥ 2 there exists a constant c_{4} = c_{4}(h) with the following property. For any prime p and any set of residues K ⊆ ℤ/pℤ such that

(4.4)  max{h + 2, 5} ≤ |K| ≤ c_{4}p,

the equality

(4.5)  |hˆ K| = h|K| − h^{2} + 1

holds if and only if K is an arithmetic progression.

Proof. Put c_{4}(h) = min {h^{−1}, c_{1}(2h, h)}, where c_{1} is defined in Theorem 2.1. If K ⊆ ℤ/pℤ is an arithmetic progression and |K| ≤ p/h then (4.5) obviously holds.

Conversely, assume that K ⊆ ℤ/pℤ satisfies (4.4) and (4.5). Fix an (h−2)-element subset H ⊆ K and denote L = K \ H. Then |2ˆ L| ≤ |hˆ K| < h|K|. Therefore

|K + K| ≤ |2ˆ K| + |K| ≤ |2ˆ L| + |H + K| + |K| < h|K| + (h − 2)|K| + |K| < 2h|K|.

By Theorem 2.1, the set K is F_{h}-isomorphic to a set of integers K′ ⊆ ℤ. Then clearly |hˆ K′| = |hˆ K| = h|K′| − h^{2} + 1, and by Proposition 4.1 (b), K′ is an arithmetic progression. Then so is K. □

Freiman, Low and Pitman [12] applied similar “rectification” approach for h = 2. Their technique is quite different and not based on Theorem 2.2, and for h = 2 their result is much stronger than Theorem 4.1 above. However, the method of [12] does not extend to h ≥ 3. See also Rödseth [21].

When Erdős-Heilbronn conjecture was proved, it has been conjectured by the second author that in fact a much more general result holds. Specifically, let K and L be subsets of an abelian group, such that |K| ≤ |L|, and let τ: K → L be an arbitrary mapping from K to L. Define K +^{τ} L to be the set of all the sums a + b (where a ∈ K, b ∈ L) such that b ≠ τ(a):

K +^{τ} L = {a + b: a ∈ K, b ∈ L, and b ≠ τ(a)}.

Conjecture 4.1 (Lev). Let K and L be subsets of ℤ/pℤ satisfying |K| ≤ |L|, and let τ: K → L be an arbitrary mapping from K to L. Then

|K +^{τ} L| ≥ min{|K| + |L| − 3, p}.

Using Theorems 2.1 or 3.1 we are able to prove this for small K, L. First, we need a corresponding result in ℤ.

Theorem 4.2. Let K and L be finite subsets of ℤ satisfying |K| ≤ |L|, and let τ: K → L be an arbitrary mapping from K to L. Then

|K +^{τ} L| ≥ |K| + |L| − 3.

Proof. Write down the elements of K and L in ascending order: K = {a_{1}, …, a_{k}} and L = {b_{1}, …, b_{l}}, where a_{i} < a_{j} and b_{i} < b_{j} for i < j.

We first assume that |K| < |L|. Then there exists b_{j} ∈ L which is not an image of an element of K under τ. Therefore among the k + l − 1 distinct sums

a_{1} + b_{1} < a_{1} + b_{2} < ⋯ < a_{1} + b_{j−1}

< a_{1} + b_{j} < a_{2} + b_{j} < ⋯ < a_{k} + b_{j}

< a_{k} + b_{j+1} < a_{k} + b_{j+2} < ⋯ < a_{k} + b_{l},

at most one sum in the first row and at most one sum in the last row are excluded by the condition b ≠ τ(a). At least k + l − 3 remaining sums fall into K +^{τ} L.

Now assume |K| = |L|. Then either there exists b_{j} ∈ L which has no pre-image in K, and we can repeat the argument above; or τ is a bijection, in which case we consider k + l − 1 distinct sums

a_{1} + b_{1} < a_{1} + b_{2} < ⋯ < a_{1} + b_{l} < a_{2} + b_{l} < a_{3} + b_{l} < ⋯ < a_{k} + b_{l}

and observe again, that at most two of them may not fall into K +^{τ} L. □

Theorem 4.3. The assertion of Conjecture 4.1 holds provided that either L = K and |K| = |L| ≤ c_{5}p (with a sufficiently small absolute constant c_{5}), or |K| + |L| ≤ log_{4} p.

Proof. In the first case (L = K, |K| = |L| ≤ c_{5}p) we observe that

|K + K| ≤ |K +^{τ} K| + |K| ≤ 3|K| − 4,

assuming |K +^{τ} K| < 2|K| − 3. Then by Theorem 2.1, K is F_{2}-isomorphic to a set of integers K′. Let τ′: K′ → K′ be the mapping induced by τ. Then K′ satisfies

|K′ +^{τ′} K′| < 2|K′| − 3, which, as Theorem 4.2 shows, is impossible for K′ ⊆ ℤ.

In the second case (|K| + |L| ≤ log_{4} p), we find, as in Theorem 3.3, a set of integers M ⊆ ℤ which is F_{2}-isomorphic to the union K ∪ L, define K′, L′ ⊆ M to be the pre-images of K, L respectively and define τ′: K′ → L′ to be the mapping induced by τ. Then by Theorem 4.2,

|K +^{τ} L| = |K′ +^{τ′} L′| ≥ |K′| + |L′| − 3 = |K| + |L| − 3.

□

Using [22, Lemma 3.3] the last theorem can be extended to all sets K and L such that ε|L| ≤ |K| ≤ |L| ≤ c_{6}(ε)p for any ε > 0.

As a concluding remark, we note that the rectification method can be used not only for the group ℤ/pℤ: for instance, in [4] it is applied for the torus ℝ^{m}/ℤ^{m}.

References

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

[2] N. Alon, M.B. Nathanson, I.Z. Ruzsa, The Polynomial Method and Restricted Sums of Congruence Classes, J. Number Theory, 56 (1996), 404–417.

[3] Yu. Bilu, Structure of sets with small sumsets, Mathématiques Stochastiques, Univ. Bordeaux 2, Preprint 94-10, Bordeaux, 1994.

[4] Yu. Bilu, The (α + 2β)-inequality on the torus, J. London Math. Soc., to appear.

[5] Yu. Bilu, Addition of sets of integers of positive density, J. Number Theory, to appear.

[6] L.V. Brailovski, G.A. Freiman, On a Product of Finite Subsets in a Torsion-Free Group, J. Algebra 130 (1990), 462–476.

[7] J.W.S. Cassels, An Introduction to Diophantine Approximations, Cambridge Tracts in Math. and Math. Physics 45, Cambridge Univ. Press, 1965.

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

[9] P. Erdős, R.L. Graham, Old and New Problems and Results in Combinatorial Number Theory, L’Enseignement Mathématique, Geneva, 1980.

[10] G.A. Freiman, Foundations of a Structural Theory of Set Addition (Russian), Kazan’, 1966; English translation: Translation of Mathematical Monographs 37, Amer. Math. Soc., Providence, 1973.

[11] G.A. Freiman, What is the structure of K if K + K is small?, in D.V. Chudnovsky et al. (eds.), Number Theory, New York 1984–1985, Lecture Notes in Math. 1240, 109–134, Springer, 1987.

[12] G.A. Freiman, L. Low, J. Pitman, The proof of Paul Erdős’ conjecture of the addition of different residue classes modulo a prime number, in Structure Theory of Set Addition, preprint volume, Tel Aviv–Marseilles, 1992/93.

[13] Y.O. Hamidoune, An Isoperimetric Method in Additive Theory, J. Algebra 179 (1996), 622– 630.

[14] I.H.B. Kemperman, On small sumsets in an abelian group, Acta Math. 103 (1960), 63-88.

[15] V.F. Lev, Simultaneous approximations and covering by arithmetic progressions in 𝔽_{p}, in preparation.

[16] V.F. Lev, On the number of solutions of a linear equation over finite sets, Submitted.

[17] V.F. Lev, P.Yu. Smeliansky, On addition of two distinct sets of integers, Acta Arith. LXX.1 (1995), 85–91.

[18] R. Mansfield, How many slopes in a polygon? Israel J. Math. 39 (1981), 265–272.

[19] M.B. Nathanson, Inverse theorems for subset sums, Trans. Amer. Math. Soc. 347 (1995), 1409–1418.

[20] M.B. Nathanson, Additive Number Theory: 2. Inverse Theorems and the Geometry of Sumsets, Graduate Texts in Math. 165, Springer, New York, 1996.

[21] Ö.J. Rödseth Sums of distinct residues modp, Acta Arith. LXV.2 (1993), 181–184.

[22] I.Z. Ruzsa, Arithmetical progressions and the number of sums, Per. Math. Hung. 25 (1) (1992), 105–111.

[23] I.Z. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar. 65 (4) (1994), 379–388.

[24] A. G. Vosper, The critical pairs of subsets of a group of prime order. J. London Math. Soc. 31 (1956), 200–205, 280–282.

Yuri F. Bilu, Forschungsinstitut für Mathematik, ETH-Zentrum, CH-8092 Zurich, Switzerland

  E-mail address: yuri@@math.ethz.ch

Vsevolod F. Lev, Dept. of Mathematics, University of Georgia, Athens, GA 30602, USA

  E-mail address: seva@@math.uga.edu

Imre Z. Ruzsa, Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Pf. 127, H-1364 Hungary

  E-mail address: ruzsa@@math-inst.hu