THREE-FOLD RESTRICTED SET ADDITION IN GROUPS

VSEVOLOD F. LEV

Abstract. Let G be a finite abelian group with a “sufficiently small” proportion of elements of order two. We prove that for any subset A ⊆ G of cardinality |A| > \frac{5}{13} |G| and any group element g ∈ G, there exist pairwise distinct a_{1}, a_{2}, a_{3} ∈ A such that a_{1} + a_{2} + a_{3} = g — unless A is contained in a coset of an index two subgroup or in a union of two cosets of an index five subgroup. As an immediate corollary our result implies a recent conjecture of Gallardo, Grekos, Habsieger, Hennecart, Landreau, and Plagne, who addressed the group G = ℤ_{n} with n odd and sets of cardinality |A| > \frac{2}{5} n.

1. Introduction

Let A be a subset of an abelian group G and let h be a positive integer. We denote by hA the set of all elements of G representable as a sum of h not necessarily distinct elements of A, and by h · A the set of all elements of G representable as a sum of h pairwise distinct elements of A. The cardinality of A is denoted by |A|.

The following conjecture has been made recently (see [GGHHLP]) in connection with possible extensions of a well-known theorem of Erdős, Ginzburg, and Ziv:

If n is an odd integer and A ⊆ ℤ_{n} is a set of residues modulo n such that |A| > \frac{2}{5} n+c (where c is an appropriate absolute constant), then 3 · A = ℤ_{n}.

Taking n to be a multiple of five and letting A be a union of two cosets of the index five subgroup of ℤ_{n}, we obtain a set of cardinality \frac{2}{5} n such that 3A ≠ ℤ_{n} and all the more so, 3 · A ≠ ℤ_{n}. This shows that the coefficient \frac{2}{5} cannot be reduced.

Below we prove this conjecture and go beyond this, replacing ℤ_{n} by an (almost) arbitrary finite abelian group G and, in a seeming contradiction with the example above, replacing \frac{2}{5} by \frac{5}{13}. More precisely, we give a complete description of the structure of A assuming that |A| > \frac{5}{13}|G| and 3 · A ≠ G, and provided that G is not “too close” to the elementary abelian 2-groups ℤ_{2}^{r}. Still more precisely, we prove the following.

Main Theorem. Let A be a subset of a finite abelian group G. Suppose that

|A| > max \{\frac{5}{13} |G|, 120|G_{0}| + 355\} ,

2 VSEVOLOD F. LEV

where G_{0} = {g ∈ G: 2g = 0}. Then either 3 · A = G, or A is contained in a coset of an index two subgroup of G, or A is contained in a union of two cosets of an index five subgroup of G.

The factor \frac{5}{13} is not best possible and can be slightly reduced at the expense of the term 120|G_{0}| + 355. Can this latter be omitted? Plainly, this is the case if G_{0} is sufficiently small compared to G, say |G_{0}| ≤ |G|/320 (and |G| is large enough). In general, the situation is more delicate. An interesting observation is that there are subsets A ⊆ ℤ_{2}^{r} of cardinality |A| > 2^{r−1} such that 3 · A ≠ ℤ_{2}^{r}: for instance, if A = H ∪ {g_{0}}, where H < ℤ_{2}^{r} an index two subgroup and g_{0} ∈ ℤ_{2}^{r} \ H, then g_{0} ∉ 3 · A. To some extent, this justifies the presence of 120|G_{0}| + 355. However, in Section 3 we establish an analog of our Main Theorem for the group ℤ_{2}^{r}, which shows that the above example is essentially unique. This is a strong indication that there should be more elegant ways to deal with exceptions of this sort.

We now turn to the proof of the Main Theorem. For more results, open problems, and surveys on restricted set addition we refer the reader to [GGHHLP, L00a, L00b] or [L01] .

2. Proof of the Main Theorem

We assume that 3 · A ≠ G and show that then A is contained either in a coset of an index two subgroup, or in a union of two cosets of an index five subgroup.

For brevity, we set γ = \frac{5}{13} and we denote the cardinality of A by m; therefore, m > max{γ|G|, 120|G_{0}| + 355}. Furthermore, we write G′ = {2g: g ∈ G}, the set of all elements of G representable as a doubling. It is easily seen that in fact each g′ ∈ G′ has precisely |G_{0}| such representations, and that |G′| = |G|/|G_{0}|.

Letters a, a′, a′′, a_{1}, a_{2}, a_{3} will denote the elements of A. For g ∈ G we let ν^{+}(g) = |{(a′, a′′): g = a′ + a′′}|, the number of representations of g as a sum of two elements of A. Similarly, we let ν^{−}(g) = |{(a′, a′′): g = a′ − a′′}|, the number of representations of g as a difference of two elements of A. Thus 2A = {g ∈ G: ν^{+}(g) > 0}, and we write A − A = {g ∈ G: ν^{−}(g) > 0}.

We split the proof of the Main Theorem in five parts.

(i) Fix an element g_{0} ∉ 3 · A. We claim that for any a ∈ A there is a set R_{a} ⊆ G of cardinality |R_{a}| ≤ |G_{0}| + 2 such that A + a − g_{0} ⊆ (G \ (−A)) ∪ R_{a}.

Indeed, if a_{1} + a − g_{0} ∉ (G \ (−A)) for some a_{1} ∈ A, then there exists a_{2} ∈ A satisfying a_{1} + a − g_{0} = −a_{2}, or equivalently a + a_{1} + a_{2} = g_{0}. By the choice of g_{0} we have either a_{1} = a, in which case a_{2} = g_{0} − 2a; or a_{2} = a; or a_{2} = a_{1}, and then

THREE-FOLD RESTRICTED ADDITION 3

a_{2} satisfies 2a_{2} = g_{0} − a. Totally, there are at most 2 + |G_{0}| options for a_{2}, which proves the claim.

Now suppose that d ∈ A − A; say, d = a′ − a′′. We have

ν^{−}(d) = |(A + a′ − g_{0}) ∩ (A + a′′ − g_{0})|
= 2|A| − |(A + a′ − g_{0}) ∪ (A + a′′ − g_{0})|
≥ 2|A| − |G \ (−A)| − |R_{a′}| − |R_{a′′}|
≥ 3|A| − |G| − 2(|G_{0}| + 2)
> (3 − γ^{−1})m − 2|G_{0}| − 4.

(ii) Consider the set S of all elements g ∈ G possessing more than two (hence, at least four) representations of the form g = a′ + a′′ with a′ ≠ a′′. It is easily seen that S + A ⊆ 3 · A and therefore S ∩ (g_{0} − A) = ∅, whence S ⊆ G \ (g_{0} − A) and |S| ≤ |G| − |A| < (γ^{−1} − 1)m. On the other hand, S is non-empty as otherwise we would have

|A|^{2} = ∑_{g∈G} ν^{+}(g) = ∑_{g∈G′} ν^{+}(g) + ∑_{g∈G\G′} ν^{+}(g)

≤ (|G_{0}| + 2)|G′| + 2|G \ G′| = |G_{0}||G′| + 2|G| = 3|G|

implying 120|G_{0}| + 355 < |A| < 3γ^{−1} = 39/5, a contradiction.

How many pairs (a′, a′′) are there such that a′ + a′′ ∉ S? We can estimate their number as follows:

|{(a′, a′′): a′ + a′′ ∉ S}| = ∑_{g∈G\S} |{(a′, a′′): a′ + a′′ = g}|

= ∑_{g∈G′\S} ν^{+}(g) + ∑_{g∈G\(G′∪S)} ν^{+}(g)

≤ (|G_{0}| + 2)|G′ \ S| + 2|G \ (G′ ∪ S)|

= (|G_{0}| + 2)(|G′| − |G′ ∩ S|) + 2(|G| − |G′ ∪ S|) = 3|G| + 2|G′| − |G_{0}||G′ ∩ S| − 2(|G′ ∩ S| + |G′ ∪ S|) ≤ 3|G| − 2|S|.

It follows that there are at least |A|^{2}−3|G|+2|S| pairs (a′, a′′) such that a′+a′′ ∈ S, hence there exists σ ∈ S satisfying

ν^{+}(σ) ≥ \frac{|A|^{2} − 3|G|}{|S|} + 2 > \frac{m^{2} − 3γ^{−1}m}{(γ^{−1} − 1)m} + 2 = \frac{γ}{1 − γ} m − \frac{1 + 2γ}{1 − γ} .

(iii) We have

((3 − γ^{−1})m − 2|G_{0}| − 4) + (\frac{γ}{1 − γ} m − \frac{1 + 2γ}{1 − γ} )

= (\frac{m}{40} − 3|G_{0}| − \frac{71}{8}) + (m + |G_{0}| + 2) > m + |G_{0}| + 2.

Therefore, for any d ∈ A − A there are at least |G_{0}| + 3 pairs of representations d = a′ − a′′, σ = a_{1} + a_{2} with a′′ = a_{2}. This yields at least |G_{0}| + 3 representations d + σ = a′ + a_{1}, meaning that d + σ ∈ S. Since d is an arbitrary element of A − A, we have A − A + σ ⊆ S. Thus,

|A − A| ≤ |S| < (γ^{−1} − 1)|A| = \frac{8}{5} |A|.

(iv) Recall, that the period of a subset B ⊆ G is defined by

H(B) = {g ∈ G: B + g = B};

this is the maximal subgroup H ≤ G such that B is a union of H-cosets.

We consider H := H(A−A), the period of the difference set A−A, and invoke a basic theorem of Kneser (see [K53, K55]) which says that for any finite non-empty subsets B and C of an abelian group one has either |B + C| ≥ |B| + |C| − 1, or |B + C| = |B + H| + |C + H| − |H|, where H is the period of B + C. In our situation B = A, C = −A, and in view of \frac{8}{5} |A| < 2|A| − 1 we obtain

|A − A| = 2|A + H| − |H|.

Now we have

2|A + H| − |H| < \frac{8}{5} |A| ≤ \frac{8}{5} |A + H|,

|A + H| < \frac{5}{2}|H|,

and since |A + H| is a multiple of |H| it follows that either |A + H| = |H|, or |A + H| = 2|H|.

Suppose first that |A + H| = |H|; that is, A is contained in an H-coset. As |H| ≥ |A| > \frac{5}{13} |G|, the index of H in G is one or two. If H is of index two, we have obtained the desired structure and the proof is over. If H = G, then A − A = G by the definition of H, hence

|G| = |A − A| < \frac{8}{5} |A|, |A| > \frac{5}{8} |G|

and therefore

ν^{+}(g) = |A ∩ (g − A)| ≥ 2|A| − |G| = \frac{8}{5} |A| + \frac{2}{5} |A| − |G|

> \frac{2}{5} |A| > 48|G_{0}| + 142 > |G_{0}| + 2

for any g ∈ G. This shows that S = G, whence G = S +A ⊆ 3·A, a contradiction.

(v) We can assume, therefore, that |A+H| = 2|H|; that is, A meets exactly two Hcosets. Furthermore, without loss of generality we can assume that A ⊆ H∪(g+H) for some g ∈ G \ H: this can be achieved by the appropriate shift of A.

What is the index of H in G? Since 2|H| ≥ |A| > \frac{5}{13} |G|, we have [G : H] = |G|/|H| < 26/5; thus, 2 ≤ [G : H] ≤ 5. Accordingly, we consider four cases.

1) Suppose that [G : H] = 2. Since A intersects both H and g + H, so does A − A. Therefore A − A = H ∪ (g + H) = G, contradicting the definition of H as the period of A − A.

2) Suppose that [G : H] = 3. In this case

\frac{8}{5} |A| > |A − A| = 2|A + H| − |H| = 3|H| = |G|,

whence |A| > \frac{5}{8} |G|. As above, this leads to a contradiction.

3) Suppose that [G : H] = 4. Write A = A_{0} ∪ (g + A_{1}), where A_{0}, A_{1} ⊆ H and g ∈ G \ H. Observe that 2g ∉ H: otherwise A − A = H ∪ (g + H) is a subgroup and it is this subgroup (and not H!) that is the period of A − A. Thus, G/H is cyclic and g + H is its generator.

We have

\frac{8}{5} |A| > |A − A| = 3|H|,

|A_{0}| + |A_{1}| = |A| > \frac{15}{8} |H|,

whence

min\{|A_{0}|, |A_{1}|\} > \frac{7}{8} |H| ≥ \frac{1}{2} |H| + \frac{3}{16} |A| > \frac{1}{2} (|H| + |G_{0}|) + 1.

Using the boxing principle it is easy to derive that 3·A_{0} = 2·A_{0}+A_{1} = A_{0}+2·A_{1} = 3 · A_{1} = H. Therefore

3 · A = (3 · A_{0}) ∪ (g + 2 · A_{0} + A_{1}) ∪ (2g + A_{0} + 2 · A_{1}) ∪ (3g + 3 · A_{1}) = G,

a contradiction.

4) Finally, if [G : H] = 5, then A is contained in a union of two cosets of an index five subgroup, as required.

3. Three-fold addition in ℤ_{2}^{r}

The less elements of order two there are in the group G, the stronger is the conclusion of the Main Theorem. For the group G = ℤ_{2}^{r} it yields no non-trivial conclusion at all. However, for this particular group a remarkable result of Davydov and Tombak [DT89] can be used to obtain a comprehensive description of large sets A satisfying 3 · A ≠ G.

Theorem 1. Let A be a subset of the group ℤ_{2}^{r} of cardinality |A| > \frac{5}{16} 2^{r} + 1. Then either 3 · A = ℤ_{2}^{r}, or there exist an index two subgroup H < ℤ_{2}^{r} and elements g_{0}, g_{1} ∈ ℤ_{2}^{r}, exactly one of which belongs to H, such that A ⊆ {g_{0}} ∪ (g_{1} + H).

Proof. Suppose that 3 · A ≠ ℤ_{2}^{r} and fix an element g_{0} ∉ 3 · A. We claim that 0 ∉ 3((A + g_{0}) \ {0}). Indeed, assuming that (a_{1} + g_{0}) + (a_{2} + g_{0}) + (a_{3} + g_{0}) = 0 we get g_{0} = a_{1} + a_{2} + a_{3}, whence two of a_{1}, a_{2}, a_{3} equal each other and one of them equals g_{0}; consequently, one of a_{1} + g_{0}, a_{2} + g_{0}, a_{3} + g_{0} equals zero.

The theorem of Davydov and Tombak (independently re-established in [CP92, Theorem 1]) asserts that if B ⊆ ℤ_{2}^{r} is a set of cardinality |B| > \frac{5}{16} 2^{r} satisfying 3B ≠ ℤ_{2}^{r}, then there exist an index two subgroup H and an element g ∉ H such that B ⊆ g + H. We apply this to the set B = (A + g_{0}) \ {0} to get A + g_{0} ⊆ {0} ∪ (g + H), which implies the result. □

References

[CP92] W. Clark and J. Pedersen, Sum-Free Sets in Vector Spaces over GF (2), Journal of Combinatorial Theory, Series A 61(4) (1992), 222–229.

[DT89] A. Davydov and L. Tombak, Quasi-perfect linear binary codes with distance 4 and and complete caps in projective geometry, Problemy Peredachi Informatzii 25(4) (1989), 11–23.

[GGHHLP] L. Gallardo, G. Grekos, L. Habsieger, F. Hennecart, B. Landreau, and A. Plagne, Restricted addition in ℤ/nℤ and an application to the Erdős-Ginzburg-Ziv problem, J. London Math. Society, to appear.

[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.

[L00a] V.F. Lev, Restricted set addition in groups. I. The classical setting, J. London Math. Soc. (2) 62 (1) (2000), 27–40.

[L00b] , Restricted set addition in groups. II. A generalization of the Erdős-Heilbronn conjecture, Electron. J. Combin. 7 (1) (2000), Research Paper 4, 10 pp. (electronic).

[L01] , Restricted set addition in groups. III. Integer sumsets with generic restrictions, Period. Math. Hungar. 42 (1–2) (2001), 89–98.

Department of Mathematics, University of Haifa at Oranim, Tivon 36006, Israel

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