An analog of Freiman’s theorem in groups

Imre Z. Ruzsa *

Abstract. It is proved that in a commutative group G, where the order of elements is bounded by an integer r, any set A having n elements and at most αn sums is contained in a subgroup of size Cn with C = f(r, α) depending on r and α but not on n. This is an analog of a theorem of G. Freiman which describes the structure of such sets in the group of integers.

Let A be a set of integers, |A| = n, and suppose that |A + A| ≤ cn. A famous theorem of Freiman [1, 2] provides a certain structural description of these sets; in one of the possible formulations, it says that A can be covered by a generalized arithmetic progression

{a + q_{1}x_{1} + q_{2}x_{2} + ... + q_{d}x_{d} : 0 ≤ x_{i} ≤ l_{i} − 1},

where d < c and ∏ l_{i} ≤ Cn with C depending on c.

One can ask for a description of sets with few sums in every Abelian group. In this paper we consider groups which are in a sense very far from N.

Theorem. Let r ≥ 2 be an integer, and let G be a commuative group in which the order of every element is at most r. Let A ⊂ G be a finite set, |A| = n. If there is another B ⊂ G such that |B| = n and |A+B| ≤ αn (in particular, if |A+A| ≤ αn or |A−A| ≤ αn), then A is contained in a subgroup H of G such that

|H| ≤ f(r, α)n,

where

f(r, α) = α^{2}r^{α^{4}}.

The proof goes along similar lines to my proof of Freiman’s theorem [3, 4], but is considerably simpler.

For a nonnegative integer k and a set A ⊂ G we introduce the notation

kA = A + ... + A, k summands,
0A = {0}, 1A = A.

* This paper was finished while author was wisiting DIMACS, Rutgers University. The author gratefully acknowledges support by DIMACS.

Lemma. If A, B ⊂ G, |B| = n and |A + B| ≤ αn, then for arbitrary nonnegative integers k, l we have

|kA − lA| ≤ α^{k+l}n.

See [3], Lemma 3.3. Observe the asymmetric role of A and B. No a priori bound is assumed for |A|; an alternative formulation (like in the Theorem) woul be “if A is such that the union of n suitable translations has at most αn elements, then A is so small that even the sets kA − lA are small”.

Proof of the Theorem. Let b_{1}, b_{2}, ..., b_{k} be a maximal collection of elements such that b_{i} ∈ 2A − A and the sets b_{i} − A are all disjoint. We have

b_{i} − A ⊂ 2A − 2A,

hence

| ⋃(b_{i} − A) |= kn ≤ |2A − 2A| ≤ α^{4}n

(the last inequality follows from the Lemma). This implies k ≤ α^{4} .

Take an arbitrary x ∈ 2A − A. Since the collection b_{1}, ..., b_{k} was maximal, there must be an i such that

(x − A) ∩ (b_{i} − A) ≠ ∅,

that is, x − a_{1} = b_{i} − a_{2} with some a_{1}, a_{2} ∈ A, which means

x = b_{i} + a_{1} − a_{2} ∈ b_{i} + (A − A).

Hence

2A − A ⊂ ⋃(b_{i} + (A − A)) = B + A − A,  (1)

where B = {b_{1}, ..., b_{k}} .

Now we prove

jA − A ⊂ (j − 1)B + A − A (j ≥ 2)  (2)

by induction on j. By (1), this holds for j = 2. Now we have

(j + 1)A − A = (2A − A) + (j − 1)A
⊂ B + A − A + (j − 1)A by (1)
= B + (jA − A)
⊂ B + (j − 1)B + A − A
= jB + A − A,

which provides the inductive step.

Let H and I be the subgroups generated by A and B, respectively. By (2) we have

jA − A ⊂ I + (A − A)  (3)

for every j. We have also

⋃(jA − A) = H,  (4)

which easily follows from the fact that the order of elements of G is bounded. (3) and (4) imply that

H ⊂ I + (A − A).

Since I is generated by k elements of order ≤ r each, we have

|I| ≤ r^{k} ≤ r^{α^{4}},

consequently

|H| ≤ |I||A − A| ≤ α^{2}r^{α^{4}}n

(the estimate for |A − A| follows from the Lemma). QED

Remarks.

Take a group of the form G = Z_{r}^{m}, where Z_{r} is a cyclic group of order r, and a set A ⊂ G of the form

A = (a_{1} + G′) ∪ ... ∪ (a_{k} + G′)

with a subgroup G′. Here |A| = n = k|G′|, and if all the sums a_{i} + a_{j} lie in different cosets of G′, then

|A + A| = \frac{k(k + 1)}{2}|G′| = αn, α = \frac{k + 1}{2}.

The subgroup generated by A can have as many as r^{k}|G′| elements, hence our function

f(r, α) = α^{2}r^{α^{4}}

cannot be replaced by anything smaller than

r^{k} = r^{2α−1}.

Conjecture. The Theorem holds with f(r, α) = r^{Cα} with a suitable constant C. The following conjecture of Katalin Marton would yield a more efficient covering in a

slightly different form.

Conjecture. If |A| = n, |A + A| ≤ αn, then there is a subgroup H of G such that |H| ≤ n and A is contained in the union of α^{c} cosets of H, where the constant c may depend on r but not on n or α.

This also suggests that perhaps in Freiman’s original problem a better result can be formulated in terms of covering by a small number of generalized arithmetical progressions than just one.

References [1] G. A. Freiman, Foundations of a structural theory of set addition, Translation of Math.

Monographs vol. 37, Amer. Math. Soc., Providence, R. I., USA, 1973.

[2] G. A. Freiman, What is the structure of K if K + K is small?, in: Lecture Notes in Mathematics 1240, Springer-Verlag, New York – Berlin 1987, 109–134.

[3] I. Z. Ruzsa, Arithmetical progressions and the number of sums, Periodica Math. Hung. 25 (1992), 104–111.

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

Imre Z. Ruzsa Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Pf. 127,

H-1364 Hungary e-mail: ruzsa@math-inst.hu