SUM-FREE SETS IN ABELIAN GROUPS

VSEVOLOD F. LEV, TOMASZ ŁUCZAK, AND TOMASZ SCHOEN

Abstract. We show that there is an absolute constant δ > 0 such that the number of sum-free subsets of any finite abelian group G is

(2^{ν(G)} − 1) 2^{|G|/2} + O(2^{(1/2−δ)|G|}), where ν(G) is the number of even order components in the canonical decomposition of G into a direct sum of its cyclic subgroups, and the implicit constant in the O-sign is absolute.

1. Introduction

A subset A ⊆ G of an (additively written) group G is said to be sum-free if no a_{1}, a_{2}, a_{3} ∈ A satisfy the equation a_{1}+a_{2} = a_{3}. In [A91], Alon proved that the number of sum-free subsets of any group G of cardinality n = |G| is at most 2^{(1/2+o(1))n} (as n → ∞) and asked about the sharp form of this result. In the present paper we answer Alon’s question for G abelian.

Theorem 1. There is an absolute constant δ > 0 such that the number of sum-free subsets of any abelian group G of cardinality n = |G| is

(2^{ν(G)} − 1) 2^{n/2} + O(2^{(1/2−δ)n}),

where ν(G) is the number of even order components in the canonical decomposition of G into a direct sum of its cyclic subgroups, and the implicit constant in the O-sign is absolute.

Throughout the rest of the paper, G is a finite abelian group of cardinality n; whenever appropriate, we tacitly assume n to be sufficiently large. We write SF[G] for the set of all sum-free subsets of G. Let H ⊆ G be a subgroup, and let Ā ∈ SF[G/H]. Suppose that a subset A ⊆ G satisfies φ_{H}(A) = Ā, where φ_{H}: G → G/H is the canonical homomorphism. Then plainly A ∈ SF[G], and we say that A is induced by Ā. For H = G, no non-empty sum-free subset of G is induced by a sum-free subset of G/H. If [G : H] = 2 (that is, H is an index two subgroup of G), then the sum-free subsets of G induced by a sum-free subset of G/H are all sets A ⊆ G \ H; it will be seen that it is these sets that contribute the main term to the asymptotic formula of Theorem 1. On the other hand, let SF^{∗}[G] be the family of all A ∈ SF[G] not induced by any Ā ∈ SF[G/H], where H is an index two subgroup. We prove that this set is small; more precisely, we have Main Lemma. There is an absolute constant δ > 0 such that

The first author was partially supported by the Edmund Landau Center for Research in Mathematical Analysis and Related Areas, sponsored by the Minerva Foundation (Germany). The second author was partially supported by KBN grant 2 P03A 021 17.

|SF^{∗}[G]| = O(2^{(1/2−δ)n}),

where the implicit constant in the O-sign is absolute.

In particular, the number of all “primitive” sum-free subsets of G (not induced by any Ā ∈ SF[G/H] for a non-zero subgroup H) is O(2^{(1/2−δ)n}). A result due to two of the present authors ([LS, Theorem 1]) shows that for p prime, |SF[ℤ_{p}]| ≫ 2^{p/3} p; therefore, 1/2 − δ in the exponent cannot be replaced by 1/3.

Theorem 1 will be deduced from the Main Lemma in Section 2, and the Main Lemma will be proved in Sections 3–7.

We now make several historical comments.

The first to consider sum-free sets was probably Schur with his celebrated theorem which states that it is impossible to partition the interval [1, n] into a fixed number of sum-free subsets, provided that n is large enough compared to the number of subsets. In [CE90], Cameron and Erdős investigated some properties of sum-free subsets of [1, n] and conjectured that the number of such subsets is O(2^{n/2}). (The motivation for this conjecture is that the vast majority of sum-free sets A ⊆ [1, n] are actually believed to be subsets of either the set {1, 3, …, 2⌊(n − 1)/2⌋ + 1}, or the set [⌈(n + 1)/2⌉, n].) Having attracted much attention, the conjecture of Cameron and Erdős is, nevertheless, still open. One can expect that the problem gets easier if the condition a_{1} + a_{2} ≠ a_{3} (a_{i} ∈ [1, n]) is replaced by the stronger and more restrictive condition a_{1} + a_{2} ≢ a_{3} (mod n); that is, if sum-free subsets of [1, n] are replaced by sum-free subsets of ℤ_{n}. Indeed, Theorem 1 implies at once that |SF[ℤ_{n}]| = O(2^{n/2}), which can be viewed as a weak form of the conjecture.

For a survey of other results concerning sum-free sets and their generalizations we refer the reader to [B98, LS]. The rest of the paper is devoted to the proofs of Theorem 1 and the Main Lemma.

2. Deduction of Theorem 1 from the Main Lemma

Lemma 1. The number of subgroups of G is at most 2^{(log_{2} n)^{2}}.

Proof. Plainly, any subgroup of G can be generated by at most ⌊log_{2} n⌋ elements. If we do not require the elements to be distinct, then exactly ⌊log_{2} n⌋ generators can be used. Thus, the number of subgroups does not exceed the number of ways to choose ⌊log_{2} n⌋ elements of G, which is at most

n^{⌊log_{2} n⌋} ≤ 2^{(log_{2} n)^{2}}.
□

Lemma 2. The number of index two subgroups of G is 2^{ν(G)} − 1, where ν(G) is the number of even order components in the canonical decomposition of G into a direct sum of its cyclic subgroups.

Proof. Let N(G) be the sought number of index two subgroups, so that for instance, N(G) = 0 if G is cyclic of odd order and N(G) = 1 if G is cyclic of even order. It suffices to prove that N(G_{1} ⊕ G_{2}) + 1 = (N(G_{1}) + 1)(N(G_{2}) + 1) for any two finite abelian groups G_{1} and G_{2}. For this, notice that if H_{1} and H_{2} are index two subgroups of G_{1} and G_{2}, respectively, then each of

H_{1} ⊕ G_{2}, G_{1} ⊕ H_{2}, and (H_{1} ⊕ H_{2}) ∪ ((G_{1} \ H_{1}) ⊕ (G_{2} \ H_{2}))

is, evidently, an index two subgroup of G_{1} ⊕ G_{2}. The number of all these subgroups is N(G_{1}) + N(G_{2}) + N(G_{1})N(G_{2}), and we leave it to the reader to verify that any index two subgroup of G_{1} ⊕ G_{2} has this form. □

By the Main Lemma, to prove Theorem 1 we only need to count all sum-free A ⊆ G induced by some Ā ∈ SF[G/H], where H is an index two subgroup. For H fixed, such A are those subsets of G contained in the complement of H, and their number is 2^{n/2}. Furthermore, if H_{1} and H_{2} are distinct index two subgroups and A is contained in both complements G \ H_{i}, then A ⊆ G \ (H_{1} ∪ H_{2}); for H_{1} and H_{2} fixed, the number of such A is at most 2^{n/4}. Now by the inclusion-exclusion argument and Lemmas 1 and 2, the number of A in question is

∑_{\begin{matrix}H⊆G \\ [G:H]=2 \end{matrix}} 2^{n/2} − O( ∑_{\begin{matrix}H_{1},H_{2}⊆G \\ [G:H_{i}]=2 \end{matrix}} 2^{n/4}) = (2^{ν(G)} − 1) 2^{n/2} − O(2^{n/4+2(log_{2} n)^{2}}).

Theorem 1 follows.

3. Auxiliary results

We collect here some facts that will be used in the proof of the Main Lemma. Let A be a subset of G. The period, or stabilizer of A is the subgroup of G defined

by

H(A) := {g ∈ G: A + g = A}.

In other words, H(A) is the maximal subgroup of G such that A is a union of H(A)- cosets. The following theorem is essentially due to Kneser [Kn53, Kn55]; the version presented below can be found, for instance, in [Ke60, Theorem 3.1]. (In fact, it can be derived easily from Kneser’s original result.)

Theorem 2. Let A and B be finite, non-empty subsets of an abelian group G. Suppose that |A + B| ≤ |A| + |B| − 1. Then

|A + B| = |A + H| + |B + H| − |H|,

where H = H(A + B).

Lemma 3. Let B ⊆ G be a finite, non-empty subset of G, not contained in a coset of a proper subgroup. Suppose, moreover, that |B| ≤ \frac{2}{3}|G|. Then there exists an element b ∈ B such that |(B + b) ∩ B| ≤ \frac{5}{6}|B|.

Proof. For g ∈ G, define f_{B}(g) := |(B + g) \ B| = |B| − |(B + g) ∩ B|. This function is often referred to as the function of Erdős-Heilbronn-Olson; its basic properties include

f_{B}(−g) = f_{B}(g),  (1)
f_{B}(g_{1} + g_{2}) ≤ f_{B}(g_{1}) + f_{B}(g_{2}),  (2)

and

∑_{g∈B−B} f_{B}(g) = |B||B − B| − |B|^{2}.  (3)

(All this is easy to verify.) By averaging, we derive from (3) that there exist b_{1}, b_{2} ∈ B such that

f_{B}(b_{1} − b_{2}) ≥ |B| (1 − \frac{|B|}{|B − B|}) ,

and since f_{B}(b_{1} − b_{2}) ≤ f_{B}(b_{1}) + f_{B}(b_{2}) by (1) and (2), we have

f_{B}(b) ≥ \frac{1}{2} |B| (1 − \frac{|B|}{|B − B|})

either for b = b_{1} or for b = b_{2}. Now

|(B + b) ∩ B| = |B| − f_{B}(b) ≤ \frac{1}{2} |B| (1 + \frac{|B|}{|B − B|}) ,

and it remains to observe that |B − B| ≥ \frac{3}{2}|B| by Theorem 2: otherwise, letting H := H(B − B), we get

\frac{3}{2}|B + H| ≥ \frac{3}{2}|B| > |B − B| = 2|B + H| − |H|,

|B + H| < 2|H|,

whence |B+H| = |H| and B is contained in a coset of H. Thus H = G or equivalently, B − B = G and therefore \frac{3}{2}|B| > |G|, a contradiction. □

Lemma 4. For any positive integer y and real x ≥ y − 1 we have

\binom{x}{y} < (\frac{x}{y} e)^{y} .

Proof. Using induction by y (or by a quantitative version of the Stirling formula) one obtains y! > (y/e)^{y}, hence

\binom{x}{y} ≤ \frac{x^{y}}{y!} < (\frac{x}{y} e)^{y} .

□

We will need an estimate for the tails of binomial and hypergeometric distributions. Recall that X is distributed binomially with parameters k and p if it attains values from the interval [0, k] with probabilities Prob \{X = i\} = \binom{k}{i}p^{i}(1 − p)^{k−i}, and in this case its expectation is EX = kp. Furthermore, X has a hypergeometric distribution with parameters N, k, and m, if it attains values from the interval [0, N] with probabilities Prob \{X = i\} = \binom{k}{i}\binom{m}{N−i}/\binom{k+m}{N}; the expectation of such a random variable is EX = mk/N.

Lemma 5 ([JLR00, Theorems 2.1 and 2.10]). Suppose that X has either a binomial or a hypergeometric distribution. Then for any 0 ≤ ε ≤ 1 we have

Prob \{X ≤ (1 − ε)EX\} ≤ exp(−\frac{ε^{2}}{2} EX),

and

Prob \{X ≥ (1 + ε)EX\} ≤ exp(−\frac{ε^{2}}{3} EX).

4. Popular differences

We continue our preparations for the proof of the Main Lemma. Kneser’s theorem shows that “normally”, the sumset A + B contains at least |A| + |B| − 1 elements. In this section we consider the case B = −A so that A + B becomes the difference set A − A and show that “normally”, this set contains at least 2|A|(1 − o(1)) elements with large number of representations as a difference of two elements of A.

For a subset A ⊆ G of any (not necessarily finite) abelian group G and a nonnegative integer K, we denote by D_{K}(A) the set of all those elements g ∈ G which have at least K distinct representations as g = a_{1} − a_{2} (with a_{1}, a_{2} ∈ A).

Proposition 1. Let A ⊆ G, K ∈ ℤ^{+}, and D_{K}(A) be as above. Suppose that

|D_{K}(A)| ≤ 2|A| − 5\sqrt{K|A − A|}.

Then there is a subset A′ ⊆ A such that

|A \ A′| ≤ \sqrt{K|A − A|} and A′ − A′ ⊆ D_{K}(A).

The proof of Proposition 1 relies upon the following graph-theoretic lemma.

Lemma 6. For any graph Γ = (V, E) of average degree d̄ ≥ (1 − λ)|V |, there exists an induced subgraph Γ′ = (V′, E′) such that

i) |V′| ≥ (1 − \sqrt{λ})|V |;

ii) δ(Γ′) > (1 − 2\sqrt{λ})|V | (where δ(Γ′) is the minimal degree of Γ′).

Proof. We define Γ′ to be the subgraph of Γ, induced by all vertices v ∈ V of degree d(v) > (1 − \sqrt{λ})|V |. We have

d̄|V | = ∑_{d(v)≤(1−\sqrt{λ})|V |} d(v) + ∑_{d(v)>(1−\sqrt{λ})|V |} d(v)

≤ (1 − \sqrt{λ})|V |(|V | − |V′|) + |V ||V′|,
(1 − λ)|V | ≤ (1 − \sqrt{λ})(|V | − |V′|) + |V′|,
= (1 − \sqrt{λ})|V | + \sqrt{λ}|V′|,
|V′| ≥ (1 − \sqrt{λ})|V |,

which proves the first assertion. To prove the second assertion, notice that the degree in Γ′ of any vertex v′ ∈ V′ is greater than

(1 − \sqrt{λ})|V | − (|V | − |V′|) = |V′| − \sqrt{λ}|V | ≥ (1 − 2\sqrt{λ})|V |.
□

Proof of Proposition 1. We can assume that K ≤ |A|, as otherwise \sqrt{K|A − A|} > |A| and the assertion is trivial.

Consider the graph Γ = (A, E) on the system of vertices A, where (a_{1}, a_{2}) ∈ E if and only if a_{1} − a_{2} ∈ D_{K}(A). The edges of the complement of Γ correspond to elements c ∈ (A − A) \ D_{K}(A). Any such element yields at most K − 1 edges, and elements c and −c yield the same edge. Therefore, the number of edges of the complement is at most

\frac{1}{2} (K − 1)|(A − A) \ D_{K}(A)| ≤ \frac{1}{2} (K − 1)|A − A|,

the number of edges of Γ is at least

\binom{|A|}{2} − \frac{1}{2} (K − 1)|A − A|,

the average degree of Γ is at least

|A| − 1 − (K − 1)|A − A|/|A| ≥ |A| − K|A − A|/|A| = |A|(1 − K|A − A|/|A|^{2}),

and by Lemma 6 there is a subgraph Γ′ = (A′, E′) such that

|A′| ≥ |A|(1 − \sqrt{K|A − A|/|A|^{2}}) = |A| − \sqrt{K|A − A|},

and for any a′ ∈ A′ the neighborhood N(a′) of a′ in Γ′ is “large”:

|N(a′)| > |A| − 2\sqrt{K|A − A|}.

Assume that A′ − A′ ⊈ D_{K}(A) (otherwise we are done). Then there exist two elements a′_{1} and a′_{2} of A′ such that a′_{2} − a′_{1} ∉ D_{K}(A), and hence the number of representations of a′_{2} − a′_{1} as a difference of two elements of A does not exceed K − 1. It follows that

|(a′_{1} − N(a′_{1})) ∩ (a′_{2} − N(a′_{2}))| ≤ K − 1,

and since a′_{j} − N(a′_{j}) ⊆ D_{K}(A) (j = 1, 2), we conclude that

|D_{K}(A)| ≥ |N(a′_{1})| + |N(a′_{2})| − (K − 1)

> 2|A| − 4\sqrt{K|A − A|} − K > 2|A| − 5\sqrt{K|A − A|}.

□

Why are we interested in the elements of A − A with a large number of representations? Suppose that any A ∈ SF[G] contains a “small” subset R, such that its difference set R − R is “large”. Since the number of possible sets R is small (as |R| is small), and since the number of sets A corresponding to a given R is small also (as A ⊆ G \ (A − A) ⊆ G \ (R − R)), this would help us to bound the the total number of A possible. Indeed, it is easy to show that there exists a “small” R such that R − R contains the set D_{K}(A) with a suitably chosen K.

Lemma 7. For any A ⊆ G, any p ∈ (0, 1), and any integer K ≥ 0 such that p^{2}K ≥ 6 ln n, there exists a subset R ⊆ A with the following properties:

i) |R| ≤ 2p|A|;

ii) D_{K}(A) ⊆ R − R.

Proof. Let R ⊆ A be a random subset of A for which the elements of A are chosen randomly and independently with probability p each. Plainly, the expected cardinality of R is p|A|, and by Markov’s inequality, i) holds with probability at least 1/2.

Fix d ∈ D_{K}(A). For any representation d = a_{1} − a_{2} (a_{1}, a_{2} ∈ A) there are at most two other representations of d of this form in which a_{1} or a_{2} are used (there can be one representation d = a_{3} − a_{1} and one d = a_{2} − a_{4}). As the total number of representations is at least K, we can select at least K/3 representations disjoint in the sense that no a ∈ A is used in two distinct representations. The probability that a given representation “survives” in R is p^{2}, the probability that it is destroyed is 1 − p^{2}, the probability that all selected representations are destroyed is less then or equal to (1 − p^{2})^{K/3}; thus,

Prob \{d ∉ R − R\} ≤ (1 − p^{2})^{K/3} < e^{−p^{2}K/3} ≤ \frac{1}{n^{2}} ,

whence

Prob \{D_{K}(A) ⊈ R − R\} ≤ ∑_{d∈D_{K}(A)} Prob \{d ∉ R − R\} ≤ \frac{1}{n}.

Therefore, ii) holds with probability at least 1−1/n > 1/2, and the result follows. □

Below we choose K = ⌊n^{2/3}⌋, p = n^{−1/7}/2, and think of R as being associated with A uniquely; in other words, for each A we select and fix one particular set R of all those, the existence of which is guaranteed by Lemma 7. We abbreviate D_{K}(A) by D; thus, we have

|R| < n^{6/7}, D ⊆ R − R.  (4)

5. Proof of the Main Lemma, I. Small sum-free sets

To prove the Main Lemma we split the family of all sum-free subsets of G into several sub-families and show that each of them contains not more than 2^{(1/2−δ)n} sets for some constant δ > 0. In this sections we estimate the number of sum-free subsets of cardinality less than (1 − ε)n/4, where ε is a positive constant. We follow closely Alon’s argument from [A91] and use some of his intermediate results.

Recall that a graph Γ is r-regular if each vertex of Γ has degree r, and that a subset A ⊆ V (Γ) is independent if it induces an empty subgraph of Γ.

Lemma 8. Let ε > 0 be fixed. Assuming r to be large enough, for any r-regular graph Γ on n vertices the number of independent sets of at most (1 − ε)n/4 vertices of Γ is smaller than 2^{n/2−ε^{2}n/6}.

Proof. Alon [A91, Corollary 3.2] showed that there is a spanning bipartite subgraph Γ′ ⊆ Γ such that the degree of any vertex of Γ′ is between r/2−r^{5/8}/2 and r/2+r^{5/8}/2. Let E be the edge set, and let U and V be the partite sets of Γ′, labeled so that |U| ≤ |V |. Then evidently

|V | (r/2 − r^{5/8}/2) ≤ |E| ≤ |U| (r/2 + r^{5/8}/2),
|V | (r − r^{5/8}) ≤ (n − |V |) (r + r^{5/8}),

whence

|V | ≤ m := ⌊n(1 + r^{−3/8})/2⌋.

Let I(s, t) denote the number of all t element subsets of U which have exactly s neighbors in V. By [A91, Corollary 2.5], there exists an absolute constant C such that for every t ≥ 2m/\sqrt{r} we have

I(s, t) ≤ \binom{s + Cmr^{−1/7}}{t}.

On the one hand, the number of independent sets A with at most ℓ := ⌊(1 − ε)n/4⌋ elements satisfying t := |A ∩ U| < ⌈2m/\sqrt{r}⌉ is bounded from above by

∑_{0≤t<⌈2m/\sqrt{r}⌉} \binom{m}{t}\binom{m}{ℓ} < n\binom{m}{⌈2m/\sqrt{r}⌉}\binom{m}{ℓ} ≤ nr^{2m/\sqrt{r}}\binom{m}{ℓ}.

On the other hand, the number of independent sets A of cardinality i := |A| ≤ ℓ with t := |A ∩ U| ≥ 2m/\sqrt{r} does not exceed

∑_{i=⌈2m/\sqrt{r}⌉}^{ℓ} ∑_{t=⌈2m/\sqrt{r}⌉}^{i} ∑_{s=0}^{|V |+t−i} I(s, t)\binom{|V | − s}{i − t}

≤ ∑_{i=⌈2m/\sqrt{r}⌉}^{ℓ} ∑_{s=0}^{|V |} ∑_{t=0}^{i} \binom{s + Cmr^{−1/7}}{t}\binom{|V | − s}{i − t}

= ∑_{i=⌈2m/\sqrt{r}⌉}^{ℓ} ∑_{s=0}^{|V |} \binom{|V | + Cmr^{−1/7}}{i}

≤ n^{2}\binom{m + Cmr^{−1/7}}{ℓ}

≤ n^{2}e^{Clr^{−1/7}} \binom{m}{ℓ}.

Thus, the total number of independent sets with at most ℓ vertices is bounded from above by

nr^{2m/\sqrt{r}}\binom{m}{ℓ} + n^{2}e^{Clr^{−1/7}} \binom{m}{ℓ} ≤ n^{2} 2^{Cnr^{−1/7}} \binom{m}{ℓ}

≤ n^{2} 2^{Cnr^{−1/7}+m} ∑_{i=0}^{ℓ} \binom{m}{i} 2^{−m}.

The latter sum is the probability that a random variable, distributed binomially with parameters m and 1/2, attains value not larger than ℓ ≤ (1 − ε)n/4 ≤ (1 − ε)m/2; by Lemma 5, this sum does not exceed e^{−0.25ε^{2}m}, and it remains to observe that

n^{2} 2^{Cnr^{−1/7}+m} e^{−0.25ε^{2}m} ≤ 2^{n/2−ε^{2}n/8 ln 2+2Cnr^{−1/7}} ≤ 2^{n/2−ε^{2}n/6}.
□

Lemma 9. Let ε > 0 be fixed. Assuming n to be large enough, we have

#{A ∈ SF[G]: |A| ≤ (1 − ε)n/4} = O(2^{(1/2−ε^{2}/7)n})

(where the implicit constant in the O-sign depends on ε only.)

Proof. Let r = ⌊log n⌋. Given a sum-free set A ⊆ G of cardinality 2r ≤ |A| ≤ (1 − ε)n/4, select an r-element subset B ⊆ A so that B ∩ (−B) = ∅. Consider the graph on the vertex set G, in which two vertices u and v are adjacent if and only if u − v ∈ ±B. This graph is (2r)-regular, and each A ∈ SF[G] containing B is its independent set. (Otherwise, we would have a′ − a′′ ∈ B ⊆ A for some a′, a′′ ∈ A.) Thus, by Lemma 8 the number of A ∈ SF[G] with at most (1 − ε)n/4 elements does not exceed

∑_{i=0}^{2r−1} \binom{n}{i} + \binom{n}{r}2^{(1/2−ε^{2}/6)n} = O_{ε}(2^{(1/2−ε^{2}/7)n}).

□

It is worth pointing out that our Lemma 9 is “parallel” to a result of Bilu [B98, Theorem 1.1], where a similar estimate for the number of sum-free subsets of the interval [1, n] is established. Bilu’s result implies at once the desired estimate for the group ℤ_{n}; however, his approach, based on Szemerédi’s theorem, is not applicable for a generic abelian group G.

6. Proof of the Main Lemma, II. Small (popular) difference sets

First, we estimate the number of A ∈ SF^{∗}[G] for which D is “small”.

Lemma 10. The number of A ∈ SF^{∗}[G] satisfying

|D| ≤ 2|A| − 5n^{5/6}

is O(2^{0.46n}).

Proof. As 2|A| − 5n^{5/6} ≤ 2|A| − 5\sqrt{K|A − A|}, by Proposition 1 for any A under consideration there exists A′ ⊆ A such that

|A′| ≥ |A| − \sqrt{K|A − A|} ≥ |A| − n^{5/6}, A′ − A′ ⊆ D,  (5)

and then

|A′ − A′| ≤ |D| ≤ 2|A| − 5n^{5/6} ≤ 2|A′| − 3n^{5/6}.

Thus, letting H := H(A′ − A′), by Theorem 2 we get |A′ − A′| = 2|A′ + H| − |H|, whence

2(|A′ + H| − |A′|) ≤ |H| − 3n^{5/6}

and we conclude that

|H| ≥ 3n^{5/6} and |A′ + H| − |A′| < |H|/2.  (6)

We now observe that [G : H] ≠ 1, since otherwise A′ − A′ = G (contradicting the fact that A′ is sum-free), and similarly [G : H] ≠ 2, since otherwise A′ − A′ = H, A ⊆ G\(A′ −A′) = G\H and A is contained in the complement of an index two subgroup. Therefore, we have

|H| ≤ n/3.  (7)

Furthermore, we note that

|A′ + H| ≤ n/2  (8)

(else for any g ∈ G by the pigeonhole principle holds (A′ + H) ∩ (g + (A′ + H)) ≠ ∅, hence g ∈ (A′ + H) − (A′ + H) implying that A′ − A′ = (A′ + H) − (A′ + H) = G), and that by (6) and (7)

|A′ + H| − |A′| < n/6.  (9)

We now make the counting. To each A there correspond a set A′ and a subgroup H. The number of subgroups H possible is, by Lemma 1, less than 2^{(log_{2} n)^{2}}, and for any H given the number of sets A′ + H possible is at most 2^{n/|H|}; thus, by (6) the number of choices for A′ + H is at most 2^{(log_{2} n)^{2}} 2^{(n^{1/6}/3)} = 2^{o(n)}. Next, by (8) and (9) for any A′ + H given, the number of sets A′ possible is at most

∑_{0≤i<n/6} \binom{n/2}{i} = O(2^{0.4592n}).

Finally, by (5) for any A′ there are at most

∑_{0≤i≤n^{5/6}} \binom{n}{i} = 2^{o(n)}

corresponding sets A. Putting everything together, we see that the total number of A is at most

2^{0.4592n+o(n)} = O(2^{0.46n}).
□

Having established Lemma 10, we can concentrate on sets A such that

|D| > 2|A| − 5n^{5/6}.  (10)

Moreover, by Lemma 9 we can restrict ourselves to studying the sets A of cardinality

|A| > n/4 − 10^{−8}n.  (11)

In our next lemma we count A which, in addition to these two properties, have “small” difference set.

Lemma 11. The number of A ∈ SF^{∗}[G] satisfying (10), (11), and

|A − A| ≤ n/2 + 10^{−7}n

is O(2^{0.42n}).

Proof. Consider the set R ⊆ A with properties (4). By (10), (11) and the assumptions of the lemma we have

|R − R| ≥ |D| > 2|A| − 5n^{5/6} > n/2 − 3 · 10^{−8}n ≥ |A − A| − 2 · 10^{−7}n,

hence one can add to R at most 4 · 10^{−7}n elements of A to obtain a set A′′ ⊆ A of cardinality |A′′| ≤ |R| + 4 · 10^{−7}n ≤ 5 · 10^{−7}n such that A′′ − A′′ = A − A. Clearly, such an A′′ can be chosen from G at no more than n\binom{n}{⌊5·10^{−7}n⌋} ways.

We put B := A′′ − A′′ = A − A and note that for every a ∈ A holds A ⊆ a − B. If B is contained in a coset of a subgroup H ⊂ G, then so is A, and in this case

k := [G : H] ≥ 3: otherwise, A and A − A are disjoint subsets of H, whence

\frac{1}{2} n = |H| ≥ |A − A| + |A| ≥ |D| + |A| > 3|A| + o(n) > \frac{3}{4} n − 4 · 10^{−8}n,

a contradiction. For H given, the number of A contained in an H-coset is at most k2^{|H|} = k2^{n/k} < n2^{n/3}, hence by Lemma 1 the total number of A ∈ SF^{∗}[G] for which B is contained in a coset of a proper subgroup is O(2^{0.34n}).

Suppose now that B is not contained in a coset of a proper subgroup. Applying then Lemma 3 to the set B, we find an element b = a_{1} − a_{2} (a_{1}, a_{2} ∈ A) with the property that

|(a_{1} − B) ∩ (a_{2} − B)| = |(−B) ∩ (−(a_{1} − a_{2}) − B)| = |B ∩ (b + B)| ≤ \frac{5}{6} |B|.

Thus, once a_{1}, a_{2}, and A′′ are selected, the remaining elements of A are to be chosen from the set (a_{1} − B) ∩ (a_{2} − B) of cardinality at most \frac{5}{6}(n/2 + 10^{−7}n). Consequently, the number of possible sets A satisfying the assumptions of the lemma is at most

n^{3} \binom{n}{⌊5 · 10^{−7}n⌋} 2^{\frac{5}{6} (1/2+10^{−7})n} = O(2^{0.42n}).

□

7. Proof of the Main Lemma, III. Conclusion

We now take care of the remaining and most complicated case, that of A, A − A, and D all “large”. More precisely, by Lemmas 9, 10 and 11, to conclude the proof of the Main Lemma it suffices to count A ∈ SF[G] such that (10), (11) and

|A − A| > n/2 + 10^{−7}n  (12)

hold.

Since the proof is somewhat technical, we first describe briefly its main idea. To construct A we first choose the small subset R ⊆ A. The remaining elements of A must then be selected from the set G\(R−R), the cardinality of which is n−|R−R| ≤ n − |D| < n/2 + 3 · 10^{−8}n (only slightly exceeding n/2 in the worst case). We select A \ R in two rounds, first choosing a set Z ⊆ A of ⌊|A|/2⌋ elements, and then finding A\(R∪Z). If Z is chosen “at random”, then each element d ∈ A−A with probability at least 1/4 belongs to Z − Z. Hence, we can expect that

|(Z − Z) \ (R − R)| ≥ \frac{1}{4} |(A − A) \ (R − R)|

= \frac{1}{4} |A − A| − \frac{1}{4} |R − R|,

|(R ∪ Z) − (R ∪ Z)| ≥ |(Z − Z) ∪ (R − R)|

≥ \frac{3}{4} |R − R| + \frac{1}{4} |A − A|

≥ \frac{3}{4} |D| + \frac{1}{4} (n/2 + 10^{−7}n)

≥ \frac{3}{2} |A| + \frac{1}{8} n + \frac{1}{4} 10^{−7}n − 4n^{5/6}

≥ \frac{1}{2} n + (\frac{1}{4} 10^{−7} − \frac{3}{2} 10^{−8}) n − 4n^{5/6}

> \frac{1}{2} n + δn

(with some δ > 0). As A ⊆ G\((R∪Z)−(R∪Z)), we expect that after choosing Z, the set A\(R∪Z) is to be chosen from at most n−|(Z ∪R)−(Z ∪R)| < n/2−δn elements of G; hence, the number of choices for A \ (R ∪ Z) is bounded from above by 2^{n/2−δn}. This is small enough to compensate for the choices of R and Z. Unfortunately, a fair amount of work is needed to make the above argument rigorous. The main difficulty is that if d_{1}, d_{2} ∈ A − A and Z is a random subset of A \ R, then the events that d_{i} ∈ (Z ∪ R) − (Z ∪ R) for i = 1, 2 are not independent. Hence our main task will be, roughly speaking, to approximate |(Z ∪ R) − (Z ∪ R)| by a sum of independent random variables.

For A (and therefore, R = R(A)) given, let X = X(A) be a set of pairs (b′_{i}, b′′_{i}) (b′_{i}, b′′_{i} ∈ A) which satisfies the following conditions and is maximal subject to these conditions:

i) all differences b′_{i} − b′′_{i} are pairwise distinct and do not belong to R − R;

ii) {b′_{i}, b′′_{i}} ∩ {b′_{j}, b′′_{j}} ⊆ R (for any i ≠ j).

We put X^{b} = ∪_{i}{b′_{i}, b′′_{i}} so that by the maximality of X, for any d ∈ A − A there is a representation d = a′ − a′′ such that either a′ ∈ R ∪ X^{b}, or a′′ ∈ R ∪ X^{b}. (To see this, consider separately the cases d ∈ R − R; d = b′_{i} − b′′_{i} for some i; and d ∉ R − R, d ≠ b′_{i} − b′′_{i}.)

Next, we introduce yet another set of pairs associated with A: specifically, let Y = Y (A) be a set of pairs (c′_{i}, c′′_{i}) (c′_{i} ∈ R ∪ X^{b}, c′′_{i} ∈ A \ (R ∪ X^{b})) which satisfies and is maximal subject to the following conditions:

i) all differences c′_{i} − c′′_{i} are pairwise distinct and do not belong to (R ∪ X^{b}) − (R ∪ X^{b});

ii) c′′_{i} ≠ c′′_{j} (for any i ≠ j).

We put Y^{c} = ∪_{i}{c′′_{i}} and note that R ∪ X^{b} ∪ Y^{c} ⊆ A and moreover,

(R ∪ X^{b} ∪ Y^{c}) − (R ∪ X^{b} ∪ Y^{c}) = A − A.  (13)

(To verify, assume that d ∈ (A − A) \ ((R ∪ X^{b}) − (R ∪ X^{b})) and write d = a′ − a′′, where exactly one of a′, a′′ belongs to R ∪ X^{b}. Now if d = ±(c′_{i} − c′′_{i}) for some i, then d ∈ ±((R ∪ X^{b}) − Y^{c}); otherwise (a′, a′′), (a′′, a′) ∉ Y and the maximality of Y shows that of the elements a′ and a′′ one which does not belong to R ∪ X^{b}, belongs to Y^{c} — whence again d ∈ ±((R ∪ X^{b}) − Y^{c}).) We mention again that R, X and Y are considered uniquely associated with the set A.

We split the proof into three cases, depending on the cardinalities of X and Y. We set m = |A − A| and m_{0} = ⌊n/2 + 10^{−7}n⌋; thus, m ≥ m_{0} by (12).

Case 1. |X| < (m − n/2)/10^{6} and |Y | < (m − n/2)/100.

To construct A, we first choose the set R∪X^{b}∪Y^{c} of cardinality i := |R∪X^{b}∪Y^{c}| ≤ (m − n/2)/99 and then select the other elements of A. By (13) and in view of A ∩ (A − A) = ∅, the number of sets A satisfying all of the assumptions is at most

∑_{m≥m_{0}} ∑_{i=1}^{⌊(m−n/2)/99⌋} \binom{n}{i}2^{n−m} ≤ n^{2} max_{m≥m_{0}} \binom{n}{⌈(m − n/2)/99⌉}2^{n−m}

≤ n^{2} max_{m≥m_{0}} (\frac{99ne}{m − n/2})^{(m−n/2)/99+1} 2^{n−m}

≤ n^{2} max_{m≥m_{0}}(2.7 · 10^{9})^{(m−n/2)/99+1} 2^{n−m}

≤ n^{2} max_{m≥m_{0}} 2^{((m−n/2)/99+1) ln(2.7·10^{9})/ ln 2+(n−m)}

≤ max_{m≥m_{0}} 2^{0.32(m−n/2)+(n−m)+32}

= 2^{0.32(m_{0}−n/2)+(n−m_{0})+32}

= O(2^{n/2−0.68·10^{−7}n}).

Case 2. |X| < (m − n/2)/10^{6} and |Y | ≥ (m − n/2)/100.

Again, we build a set A in several steps. First we choose R and X^{b}. Then, we select ⌊|A|/2⌋ elements of A \ (R ∪ X^{b}) and, finally, the remaining |A| − |R ∪ X^{b}| − ⌊|A|/2⌋ elements of A. More formally, for a given R and X, instead of counting sum-free sets A with A ⊇ (R∪X^{b}), we shall estimate the number w of pairs of sets (Z, A\(R∪X^{b}∪Z)), where Z ⊆ A \ (R ∪ X^{b}) and |Z| = ⌊|A|/2⌋. Our hope is that, since Z contains half of the elements of A, it will contain a considerable fraction of elements of Y^{c} and thus substantially decrease the number of choices for the elements from A \ (R ∪ X^{b} ∪ Z).

For given positive integers k and ℓ, let us count such pairs with |A| = k and |R ∪ X^{b}| = ℓ. We first estimate the number w′_{k,ℓ} of the pairs (Z, A \ (R ∪ X^{b} ∪ Z)) for which

|Z ∩ Y^{c}| ≤ |Y |/3 .  (14)

Thus, we fix set A and count the number of all subsets Z of A with Z ⊆ A\(R ∪X^{b}), |Z| = ⌊k/2⌋ for which (14) holds. Equivalently, we may estimate the probability that for the random subset Z, chosen uniformly at random from all subsets of A\(R∪X^{b}) with ⌊|A|/2⌋ elements, we have |Z ∩ Y^{c}| ≤ |Y |/3. Note that the random variable Y = |Z ∩ Y^{c}| has the hypergeometric distribution with parameters |A| − |R ∪ X^{b}|, |Y |, and ⌊|A|/2⌋. In particular, for the expectation of Y we get

\frac{|Y | · ⌊|A|/2⌋}{|A| − |R ∪ X|} > \frac{|Y |}{2} .

Hence, Lemma 5 gives

Prob {|Z ∩ Y^{c}| ≤ |Y |/3} = Prob {|Y| ≤ |Y |/3}

≤ exp(−|Y |/100) ≤ exp(−\frac{m_{0} − n/2}{10^{4}}) .

Thus, to estimate w′_{k,ℓ}, it is enough to bound the number of choices for A and multiply

the result by \binom{k−ℓ}{⌊k/2⌋} exp(−\frac{m_{0}−n/2}{10^{4}}). Consequently, from the assumptions we have |R − R| ≥ n/2 − 3 · 10^{−17}n, and ℓ ≤ 3(m − n/2)/10^{6}, so that

\frac{w′_{k,ℓ}}{\binom{k−ℓ}{⌊k/2⌋}} ≤ ∑_{m≥m_{0}} \binom{n}{ℓ}2^{n/2+3·10^{−17}n} exp(−\frac{m_{0} − n/2}{10^{4}})

≤ n\binom{n}{⌈3(m_{0} − n/2)/10^{6}⌉}2^{n/2+3·10^{−17}n} exp(−\frac{m_{0} − n/2}{10^{4}})

≤ n(\frac{10^{6}n}{m_{0} − n/2} · e^{−32})^{3(m_{0}−n/2)/10^{6}+1}2^{n/2+3·10^{−17}n}

= O(n(10^{13}e^{−32})^{3·10^{−13}n} 2^{n/2+3·10^{−17}n}) = O(2^{n/2−2·10^{−13}n}).  (15)

Now we estimate the number of pairs w′′_{k,ℓ} (|A| = k and |R ∪ X^{b}| = ℓ) for which (14) does not hold. Note that in this case

|(R ∪ X^{b} ∪ Z) − (R ∪ X^{b} ∪ Z)| ≥ |R − R| + |Y |/3
≥ n/2 − 3n/10^{17} + (m − n/2)/300
≥ n/2 + (m − n/2)/400 .

Hence, choosing first R ∪ X^{b}, then Z from at most n − |(R ∪ X^{b}) − (R ∪ X^{b})| elements and, finally, selecting A \ (R ∪ X^{b} ∪ Z) from the available set of not more than n/2 − (m − n/2)/400 − ⌊|A|/2⌋ elements, we arrive at

w′′_{k,ℓ} ≤ ∑_{m≥m_{0}} \binom{n}{ℓ}\binom{n/2 + 3 · 10^{−17}n}{⌊k/2⌋}\binom{n/2 − (m − n/2)/400 − ⌊k/2⌋}{k − ℓ − ⌊k/2⌋} .

Because of the combinatorial identity

\binom{n/2 + 3 · 10^{−17}n}{⌊k/2⌋}\binom{n/2 + 3 · 10^{−17}n − ⌊k/2⌋}{k − ℓ − ⌊k/2⌋} = \binom{n/2 + 3 · 10^{−17}n}{k − ℓ}\binom{k − ℓ}{⌊k/2⌋} ,

we can bound \frac{w′′_{k,ℓ}}{\binom{k−ℓ}{⌊k/2⌋}} from above by

2^{n/2+3·10^{−17}n} ∑_{m≥m_{0}} \binom{n}{ℓ}\begin{matrix}( & {n/2−(m−n/2)/400−⌊k/2⌋ \atop k−ℓ−⌊k/2⌋} & ) \\ ( & {n/2+3·10^{−17}n−⌊k/2⌋ \atop k−ℓ−⌊k/2⌋} & ) \end{matrix}

≤ 2^{n/2+3·10^{−17}n} ∑_{m≥m_{0}}(\frac{en}{⌈3(m − n/2)/10^{6}⌉})^{3(m−n/2)/10^{6}+1}

× (\frac{n/2 − (m − n/2)/400 − ⌊k/2⌋}{n/2 + 3 · 10^{−17}n − ⌊k/2⌋})^{0.1n}

≤ n2^{n/2+3·10^{−17}n}(\frac{en}{3(m_{0} − n/2)/10^{6}} )^{3(m_{0}−n/2)/10^{6}+1}(1 − \frac{m_{0} − n/2}{200n})^{0.1n}

= O(n2^{n/2+3·10^{−17}n}10^{4(m_{0}−n/2)/10^{5}}2^{−(m_{0}−n/2)/2·10^{3}}) = O(2^{n/2−10^{−12}n}).  (16)

Note that if by σ_{k,ℓ} we denote the number of all sum-free sets A with |A| = k and |R ∪ X^{b}| = ℓ, then

σ_{k,ℓ}\binom{k − ℓ}{⌊k/2⌋}

= |{(Z, A \ (R ∪ X^{b} ∪ Z) : |A| = k, |R ∪ X^{b}| = ℓ, A ∈ SF[G]}| = w′_{k,ℓ} + w′′_{k,ℓ} .

Hence, from (15) and (16) we infer that the number of subsets A ∈ SF[G], for which |X| < (m − n/2)/10^{6} but |Y | ≥ (m − n/2)/100, is bounded from above by

∑_{k} ∑_{ℓ} \frac{w′_{k,ℓ} + w′′_{k,ℓ}}{\binom{k−ℓ}{⌊k/2⌋}} = O(n^{2}(2^{n/2−2·10^{−13}n} + 2^{n/2−10^{−12}n})) = O(2^{n/2−10^{−13}n}).

Case 3. |X| > (m − n/2)/10^{6}.

As in the previous case we first select all elements from R and then count pairs (Z, A \ (R ∪ Z)), where Z ⊆ A \ R and |Z| = ⌊|A|/2⌋.

Thus, fix k = |A| and ℓ = |R|. Let w̃′_{k,ℓ} count pairs (Z, A \ (R ∪ Z)) such that Z ⊆ A \ R, |Z| = ⌊|A|/2⌋, and the number s(Z, A) of elements (b′, b′′) ∈ X for which b′, b′′ ∈ R ∪ Z is at most |X|/10. As before, we estimate s(Z, A) for the random subset Z of A \ R of ⌊|A|/2⌋ elements.

The distribution of s(Z, A) is neither hypergeometric nor binomial, so we cannot apply Lemma 5 directly. Thus, instead of Z, we study the random set X, obtained by putting an element x ∈ A \ R into X with probability 2/5, independently for each x ∈ A \ R. Since the function s(·, A) is non-decreasing, we have

Prob {s(Z, A) ≤ |X|/10} ≤ Prob {|X | ≥ |Z|}+

+ Prob {{s(X , A) ≤ |X|/10} ∧ {|X | ≤ |Z|}}

≤ Prob {|X | ≥ ⌊|A|/2⌋} + Prob {s(X , A) ≤ |X|/10}.

Note that X is a binomially distributed random variable with expectation

E X = \frac{2}{5}|A \ R| ≤ \frac{2}{5}|A| .

Furthermore, the random variable s(X , A) is the sum of |X| zero-one independent random variables {I_{d} : (b′, b′′) ∈ X}, where for each (b′, b′′) ∈ X,

Prob {I_{d} = 1} = (2/5)^{2−|{b′,b′′}∩(A\R)|},

so that

E s(X , A) ≥ \frac{4}{25}|X| .

Hence, Lemma 5 implies that

Prob {s(Z, A) ≤ |X|/10} ≤ exp(−|A|/50) + exp(−|X|/100)

≤ 2 exp(−|X|/100) ≤ 2 exp(−\frac{m_{0} − n/2}{10^{6}}) .

Thus, as in the Case 2, since |R − R| ≥ n/2 − 3 · 10^{−17}n, one obtains

\begin{matrix} & w̃′_{k,ℓ} \\ ( & {k−ℓ \atop ⌊k/2⌋} & ) \end{matrix} ≤ ∑_{m≥m_{0}} \binom{n}{ℓ}2^{n−|R−R|}2 exp(−\frac{m_{0} − n/2}{10^{6}})
≤ n^{n^{6/7}}2^{n/2+4·10^{−17}n+1} exp(−10^{−16}n)
= O(2^{n/2−10^{−17}n}) .

In order to estimate the number w̃′′_{k,ℓ} of pairs (Z, A \ (R ∪ Z)) such that |A| = k, |R| = ℓ and s(Z, A) > |X|/10, we remark that in this case

|(R ∪ Z) − (R ∪ Z)| ≥ |R − R| + \frac{|X|}{10} ≥ \frac{n}{2} + \frac{n}{10^{15}} .

Hence

\begin{matrix} & w̃′′_{k,ℓ} \\ ( & {k−ℓ \atop ⌊k/2⌋} & ) \end{matrix} ≤ ∑_{m≥m_{0}} \binom{n}{ℓ}\binom{n/2 + 3 · 10^{−17}n}{⌊k/2⌋}\binom{n/2 − (2m − n)/3 · 10^{7} − ⌊k/2⌋}{k − ℓ − ⌊k/2⌋} .

Thus, arguing as in Case 2, one can bound \binom{k−ℓ}{⌊k/2⌋}^{w̃′′_{k,ℓ}} from above by

n^{n^{6/7}} ∑_{m≥m_{0}}2^{n/2+3·10^{−17}n}(\frac{n/2 − n/10^{15}}{n/2 + 3 · 10^{−17}n})^{k−ℓ−⌊k/2⌋}

≤ n^{n^{6/7}}2^{n/2+4·10^{−17}n}(1 − \frac{1}{10^{15}} )^{0.1n}

≤ n^{n^{6/7}}2^{n/2+4·10^{−17}n}2^{−10^{−15}n} = O(2^{n/2−10^{−16}n}).

Consequently, as in the previous case, one can bound the number of sum-free subsets A of G with |X| > (m − n/2)/10^{6} by

∑_{k} ∑_{ℓ} \frac{w̃′_{k,ℓ} + w̃′′_{k,ℓ}}{\binom{k−ℓ}{⌊k/2⌋}} = O(n^{2}(2^{n/2−10^{−17}n} + 2^{n/2−10^{−16}n})) = O(2^{n/2−10^{−18}n}).

This completes the proof of the Main Lemma.

References

[A91] N. Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel J. Math. 73 (1991), 247–256.

[B98] Y. Bilu, Sum-free sets and related sets, Combinatorica 18 (4) (1998), 449–459.

[CE90] P. J. Cameron and P. Erdős, On the number of sets of integers with various properties. In Number Theory (R. A. Mollin, Ed.), de Gruyter, Berlin, 1990, 61–79.

[JLR00] S. Janson, T. Łuczak, and A. Ruciński, Random Graphs, Wiley, New York, 2000.

[Ke60] J.H.B. Kemperman, On small sumsets in Abelian group, Acta Math. 103 (1960), 63–88.

[Kn53] M. Kneser, Abschtzung der asymptotischen Dichte von Summenmengen, Math. Zeit. 58 (1953), 459–484.

[Kn55] M. Kneser, Ein Satz über abelschen Gruppen mit Anwendungen auf die Geometrie der Zahlen, Math. Zeit. 61 (1955), 429–434.

[LS] V. Lev and T. Schoen, Cameron-Erdős modulo a prime, submitted.

Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel.

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

Department of Mathematics, Adam Mickiewicz University, Poznań, Poland.

  E-mail address: tomasz@amu.edu.pl

Department of Mathematics, Christian Albrecht University, Kiel, Germany

and Department of Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland.

  E-mail address: tos@numerik.uni-kiel.de