The Cameron–Erd˝os Conjecture Ben Green1 Abstract

Voir le pdf : http://arxiv.org/pdf/math/0304058.pdf

 

arXiv:math/0304058v1 [math.NT] 4 Apr 2003 The Cameron–Erd˝os Conjecture Ben Green1 Abstract A subset A of the integers is said to be sum-free if there do not exist elements x,y,z ∈ A with x+y = z. It is shown that the number of sum-free subsets of {1,... ,N} is O(2N/2 ), confirming a well-known conjecture of Cameron and Erd˝os. 1. Introduction. If A is any subset of an abelian group then we say that A is sum-free if (A + A) ∩ A = ∅, that is if there do not exist x, y, z ∈ A for which x + y = z. The study of such sets goes back at least 30 years, and over 10 years ago Cameron and Erd˝os [4, 5] raised the question of enumerating the sum-free subsets of [N] = {1, . . . , N}. They noted that any set of odd integers is sum-free, as is any subset of {⌈N/2⌉, . . . , N}, but that it is hard to think of many sum-free sets which are not essentially of this form. Thus they advanced the following conjecture. Conjecture 1 (Cameron–Erd˝os) The number of sum-free subsets of [N] is O(2N/2 ). There has been some progress on this conjecture. Writing SF(N) for the collection of sum-free subsets of [N], Alon [1], Calkin [2] and Erd˝os and Granville (unpublished) showed independently that |SF(N)| = 2N/2+o(N) . (1) Results in a rather different direction were obtained by Freiman [7] and by Deshouillers, Freiman, S´os and Temkin [6]. In [7], for example, it was shown that the number of sum-free subsets of [N] with cardinality at least 5N/12 + 2 is at most O(2N/2 ). Let us also mention that Calkin and Taylor [3] showed that the number of subsets of [N] containing no solutions to x + y + z = w is O(22N/3 ), an estimate which is basically sharp. It is natural to ask for estimates for SF(Γ), the number of sum-free subsets of some finite abelian group Γ. When Γ = Z/pZ (p prime) this question is perhaps even more natural than the question of Cameron and Erd˝os. It was first considered explicitly by Lev and Schoen [12], who showed that |SF(Z/pZ)| ≤ 2 0.498p . Their result was improved by Ruzsa and the author [9], who obtained the estimate |SF(Z/pZ)| ≤ 2 p/3+o(p) . This is tight except for the o(p) term. For more general abelian groups Γ, work started by Lev, Luczak and Schoen [11] in the case |Γ| even was continued by Ruzsa and the author 1Supported by a Fellowship of Trinity College, Cambridge and a grant from the EPSRC, United Kingdom. Mathematics Subject Classification: 11B75. 1 [10], who obtained reasonably precise estimates for all abelian groups. The objective of the present paper is to prove the conjecture of Cameron and Erd˝os. Theorem 2 The number of sum-free subsets of [N] is asymptotically c(N)2N/2 , where c(N) takes two different constant values according as N is odd or even. It is extremely likely that our methods extend to give, for example, much tighter bounds on |SF(Z/pZ)| but we do not pursue such matters here. 2. A strategy for counting sum-free sets. The purpose of this section is to outline the broad strategy that we will use to count sum-free subsets of [N]. Our method falls conveniently into two parts, which are dealt with in detail in the two sections immediately following this one. We have tried to make these sections as independent as possible. Our strategy, then, is as follows. Part I. We find some family F of subsets of [N] with the following properties. Firstly, each A ∈ F is almost sum-free, meaning that the number of additive triples (triples with x+y = z) in A is o(N2 ). Secondly, F does not contain too many sets; in fact, |F| = 2o(N) . Finally, every sum-free subset of [N] is contained in some member of F. Part II. Given A ∈ SF(N), we consider some set A′ ∈ F with A ⊆ A′ . As F is so small, the number of A for which |A′ | ≤ 1 2 − 1 120
N is o(2N/2 ). If, however, |A′ | ≥ 1 2 − 1 120
N then it is possible to say something about the structure of A ′ , and hence about the structure of almost all A ∈ SF(N). What we will actually show is that almost all A ∈ SF(N) consist either entirely of odd numbers, or else are contained in the interval {⌈(N+1)/3⌉, . . . , N}. The author was delighted to discover that, in their original paper [4], Cameron and Erd˝os gave an elegant argument leading to an estimate for the number of sum-free subsets of {⌈(N + 1)/3⌉, . . . , N}. This argument, together with our work in the present paper, constitutes an affirmative solution to Conjecture 1. 3. Construction of F. Granularizations. In this section we complete Part I of the program outlined in §2 by constructing the family F. This was basically achieved in the paper of Ruzsa and the author [9]. Since it is not quite a trivial matter to isolate results from that paper in the form that we need them, we repeat some of the material from [9] here. We begin with a small amount of notation concerning Fourier transforms. We will be working on the group G = Z/pZ, where p is a prime. If f : G → C is a function and if r ∈ G then we define the Fourier transform ˆf by ˆf(r) = X x∈G f(x)e(rx/p) 2 where, as usual, e(θ) = e 2πiθ. If f, g are two functions then we define their convolution f ∗ g by (f ∗ g)(x) = X y∈G f(y)g(x − y). Observe that (f ∗ g)ˆ(r) = ˆf(r)ˆg(r). Finally, we remark that if A ⊆ G then we will identify A with its characteristic function: that is, we write A(x) = 1 if x ∈ A and A(x) = 0 otherwise. Observe that if A, B ⊆ G are two sets then (A ∗ B)(x) is the number of representations of x as a + b with a ∈ A, b ∈ B. Let p ∈ [2N, 4N] be a prime, let M be a positive integer, and let d ∈ (Z/pZ) ∗ . Let A ⊆ [N] be a set, and regard A as a subset of Z/pZ in the obvious manner. Suppose that |A| = αp. Consider a partition of Z/pZ into arithmetic progressions Ii , i ∈ Z/MZ, of common difference d defined by Ii = ( λd : ip M ≤ λ < (i + 1)p M ) , (2) where i denotes the least positive residue of i. Each of these progressions has length either L or L − 1, where L = ⌈p/M⌉. Let ǫ1 > 0 be a real number, and let T = {i ∈ Z/MZ | |A ∩ Ii | ≥ ǫ1|Ii |}. Finally, define the granularization A′ of A (with respect to the length d and the parameter ǫ1) by A ′ = [ i∈T Ii . It is easy to see that we have |A ′ A| ≤ ǫ1p. (3) One of the key results of [9] is that, provided d has a certain property (for which we will use the term “good length”) the set A′ retains some of the additive features of A. In fact, we will be able to show that A′ is almost sum-free. Let us now say what we mean by the statement “d is a good length”. Let ǫ2, ǫ3 > 0 be two further real numbers and set δ = 1 16 ǫ 2 1 ǫ2ǫ 1/2 3 α −1/2 . Let R, |R| = k, be the set of all r 6= 0 for which |Aˆ(r)| ≥ δp. We say that d is a good length for A (with respect to the parameters ǫ1, ǫ2, ǫ3) if kdr/pk ≤ 1 4L δp |Aˆ(r)| !1/2 (4) for all r ∈ R. The following proposition was (essentially) the main result of [9]. It clarifies the rˆole of ǫ2 and ǫ3, which have not so far featured. 3 Proposition 3 Suppose that d is a good length for A. Then the granularization A′ has the property that A + A contains all x for which A′ ∗ A′ (x) ≥ ǫ2p, with at most ǫ3p exceptions. Proof. We claim that if d is a good length then the function g(x) = 1 2L − 1 X L−1 j=−(L−1) e(jdx/p) (5) satisfies |Aˆ(x)||1 − g(x) 2 | ≤ δp (6) for all x. This automatically holds for x = 0, as g(x) = 1, and also whenever |Aˆ(x)| ≤ δp, since g(x) ∈ [−1, 1]. For any x ∈ Z/pZ we may estimate 1 − g(x) as follows. Writing ktk for the distance of t from the nearest integer we have the inequality 1 − cos 2πt ≤ 2π 2ktk 2 . It follows that 1 − g(x) = 2 2L − 1 X L−1 j=1  1 − cos 2πjdx p  ≤ 4π 2 2L − 1 X L−1 j=1 jdx p 2 ≤ 4π 2 2L − 1 dx p 2 X L−1 j=1 j 2 ≤ 2π 2L 2 3 dx p 2 . (7) Hence |Aˆ(x)||1 − g(x) 2 | ≤ 2|Aˆ(x)||1 − g(x)| ≤ 14L 2 kdx/pk 2 |Aˆ(x)| It is now easy to see that d being a good length is exactly the property required to make (6) hold. Now to establish the proposition we define a function a1 by a1(n) = 1 |P| (A ∗ P)(n) = 1 |P| |A ∩ (P + n)|, where P = {−(L − 1)d, . . . , 0, d, 2d, . . . ,(L − 1)d}. Observe that ˆa1(x) = Aˆ(x)g(x). Thus we 4 have, by two applications of Parseval’s identity, that X n |(A ∗ A)(n) − (a1 ∗ a1)(n)| 2 = p −1X x    Aˆ(x) 2 − aˆ1(x) 2    2 = p −1X x |Aˆ(x)| 4 1 − g(x) 2
2 ≤ p −1  sup x |Aˆ(x)||1 − g(x) 2 | 2 X x |Aˆ(x)| 2 = αp  sup x |Aˆ(x)||1 − g(x) 2 | 2 . (8) (6) therefore implies that X n |(A ∗ A)(n) − (a1 ∗ a1)(n)| 2 ≤ αδ2 p 3 . (9) Now if n ∈ A′ then there is a progression of common difference d and length L containing n which contains at least ǫ1L/2 points of A. This progression is contained in [n − (L − 1)d, . . . , n + (L − 1)d]. Hence a1(n) is certainly at least ǫ1/4, and so a1(n) ≥ ǫ1A(n)/4 for all values of n. It follows immediately that (a1 ∗ a1)(n) ≥ ǫ 2 1 (A′ ∗ A′ )(n)/16 for all n, and hence that if A′ ∗ A′ (n) ≥ ǫ2p then a1 ∗ a1(n) ≥ ǫ 2 1 ǫ2p/16. We are to show that there are not many points n for which this is true whilst A ∗ A(n) = 0. Letting B denote the set of these “bad” points, observe that n ∈ B implies that |(A ∗ A)(n) − (a1 ∗ a1)(n)| 2 ≥ ǫ 4 1 ǫ 2 2p 2 256 . Substituting into (9) gives the bound |B| ≤ 256αδ2 ǫ 4 1 ǫ 2 2 p ≤ ǫ3p (this explains our choice of δ). We defer for a while the issue of whether there are any good lengths. Our next result says that the conclusion of Proposition 3 is enough to guarantee that if A is sum-free then A′ is almost sum-free. Proposition 4 Suppose that A is sum-free. Let ǫ > 0, set ǫ1 = ǫ, ǫ2 = ǫ 2 /144, ǫ3 = ǫ 2 /80 and let A′ be the granularization of A with respect to some good length d. Then A′ contains at most ǫp2 triples (x, y, z) with x + y = z. 5 Proof. The choice of p (that is, p ≥ 2N) guarantees that A is sum-free when considered as a subset of Z/pZ. Suppose without loss of generality that d = 1, and suppose for a contradiction that the proposition is false. Recall the notation we set up at the start of the section, particularly the definitions of the intervals Ii and the set T ⊆ Z/mZ. We begin by claiming that there are at least ǫM2/4 triples (i, j, k) ∈ T 3 for which i + j = k or k + 1. Indeed note that if x+y = z and if x ∈ Ii , y ∈ Ij and z ∈ Ik then i+j = k or k +1. However for a fixed triple (i, j, k) with this property there are at most 4p 2/M2 triples (x, y, z), so our claim follows from a simple double count. For definiteness suppose that there are at least ǫM2/8 triples (i, j, k) ∈ T 3 with i + j = k (the argument when there are many triples with i + j = k + 1 is very similar). Let K be the set of all k ∈ T for which T ∗ T(k) ≥ ǫM/16 so that, by an easy averaging argument, we have |K| ≥ ǫM/16. Suppose that i + j = k with i, j, k ∈ T, and suppose that z lies in the middle (1 − ǫ/2) of Ik. Then the number of representations of z as x + y with x ∈ Ii , y ∈ Ij is at least ǫp/8M. Therefore if k ∈ K we have A′ ∗A′ (z) ≥ ǫ 2p/144. Note, however, that since k ∈ T the middle (1 − ǫ/2) of Ik contains at least ǫp/4M points of A. We have now shown that there are at least ǫ 2 p/64 elements x ∈ A for which A ′ ∗ A ′ (x) ≥ ǫ 2p/144. By the property of A′ described in Proposition 3 we see that A + A contains an element of A, contrary to our assumption that A is sum-free. We now look at the issue of finding a good length. Proposition 5 Let A ⊆ Z/pZ have cardinality αp. A good length for A with parameters ǫ1, ǫ2, ǫ3 exists if p > (4L) 256α 2 ǫ −4 1 ǫ −2 2 ǫ −1 3 . (10) Proof. It follows by a standard application of the pigeonhole principle that a d satisfying (4) exists if p > (4L) k Y r∈R |Aˆ(r)| δp !1/2 . (11) We claim that this inequality is a consequence of the hypothesis on p, L, ǫ1, ǫ2 and ǫ3 in the statement of the proposition. Indeed, observe that Parseval’s identity implies that X r∈R |Aˆ(r)| 2 ≤ αp2 , (12) from which the arithmetic-geometric mean inequality gives Y r∈R |Aˆ(r)| ≤  αp2 k k/2 . It follows that the right side of (11) is at most (4Lα1/4 δ −1/2 k −1/4 ) k , (13) 6 which is an increasing function of k in the range k <  256L4 e  α δ 2 . However another consequence of (12) is the inequality k < α/δ2 , and hence (13) is itself bounded above by (4L) α/δ2 . Recalling our choice of δ confirms the claim, and hence there is a d for which (4) holds. To get the conclusion of Proposition 4 we required ǫ1 = ǫ, ǫ2 = ǫ 2 /144 and ǫ3 = ǫ 2 /80. It is an easy but slightly tedious task to check that if we put ǫ = (log N) −1/11 and M =  N exp(−(log N) 1/12)  then, at least for N sufficiently large, A has at least one good length. For the remainder of the section we assume that the parameters ǫ and M take these values. We are now in a position to define our family of sets F. Take F to consist of all sets which can be formed in the following manner. For all d ∈ (Z/pZ) ∗ consider the decomposition (2) of Z/pZ into progressions Ii (i ∈ Z/mZ) with common difference d. Let G be the collection of sets which are unions of progressions Ii , for some d. Now throw away from G all those sets which have more than ǫp2 additive triples, giving a new collection H. Finally, let F consist of all subsets of [N] which can be obtained by adding at most ǫp elements to some H ∩ [N], H ∈ H. This may seem complicated. It turns out, however, that we can rather easily establish the following rather clean proposition concerning F which contains all the information we need for subsequent sections. Proposition 6 The family F has the following properties: (i) Every member of F has at most o(N2 ) additive triples; (ii) If A is sum-free then A is contained in some member of F; (iii) |F| ≤ 2 o(N) . Proof. (i) By definition every set in H has at most ǫp2 additive triples, and thus the same is true of sets of the form H ∩ [N], H ∈ H. By adding ǫp elements to such an H, we cannot create more than 3ǫp2 new additive triples. The result follows from the fact that p ≤ 4N. (ii) Set ǫ1 = ǫ, ǫ2 = ǫ 2/144 and ǫ3 = ǫ 2/80. Choose a good length d for A with respect to ǫ1, ǫ2, ǫ3, and consider the granularization A′ with respect to d and ǫ1. By Proposition 4 this lies in H, and the result follows from (3). (iii) There are p −1 choices for d, and then 2M ways to pick elements of G. Thus |H| ≤ p2 M, and so |F| is at most p2 M times the number of subsets of [N] of size at most ǫN. This is clearly 2o(N) . 4. The structure of almost sum-free sets. In this section we study large almost sumfree sets. The results may be regarded as “almost” versions of the results of Freiman [7]. Freiman’s methods do not seem to generalise easily to almost sum-free sets, so we have been forced to devise our own arguments. We will need one further piece of notation. If K is a positive real number and if A ⊆ G is a subset of an abelian group, we will write D(A, K) for the set of all x ∈ G which have at least K representations as a − a ′ with a, a′ ∈ A. We call 7 this the set of K-popular differences of A. In this section the objects Ii , M and ǫ are not the same as in the previous section. Proposition 7 Let ǫ = o(N) and suppose that A ⊆ [N] has at most ǫN2 additive triples, and that |A| = ( 1 2 − η)N where η ≤ 1/50 (η is allowed to be negative). Then one of the following alternatives occurs: (i) With the possible exception of at most 32ǫ 1/8N elements, A is contained in some interval of length ( 1 2 + 3η + 60ǫ 1/8 )N; (ii) At most 54ǫ 1/8N elements of A are even. Throughout what follows we shall assume that |A| = ( 1 2 − η)N, η ≤ 1/50 and that A has at most ǫN2 additive triples. Lemma 8 We have 1 2 |D(A, ǫ1/2N)| + |A| ≤ N(1 + 2ǫ 1/2 ). (14) Proof. We have   D(A, ǫ1/2N) ∩ Z>0
∩ A   ≤ ǫ 1/2N, or else A would contain more than ǫN2 additive triples. The result follows quickly from this and the observation that d is K-popular if and only if −d is. Lemma 9 For all but at most 8ǫ 1/4N values of a, at least |A| − 16ǫ 1/4N of the differences a − a ′ with a ′ ∈ A lie in D(A, 32ǫ 1/2N). Proof. Consider the graph on vertex set A in which a is joined to a ′ if a − a ′ is not in D(A, 32ǫ 1/2N). It has at most 64ǫ 1/2N2 edges. The number of vertices with degree more than 16ǫ 1/4N is thus at most 8ǫ 1/4N. The next lemma, which is an application of basic graph theory, is [11], §4, Proposition 1. We specialise the result to the case we need. Lemma 10 (Lev, Luczak, Schoen) Let S be a subset of an abelian group Γ, |Γ| ≤ N. Suppose that |D(S, 8ǫ 1/2N)| ≤ 2|S| − 16ǫ 1/4N. Then there is a set X ⊆ S, |S X| ≤ 4ǫ 1/4N, with X − X ⊆ D(S, 8ǫ 1/2N). Now partition [N] into intervals Ii such that the smallest element of Ii is ⌊2iǫ1/8N⌋. Let j be minimal so that Ij contains at least 9ǫ 1/4N points of A. Then, by Lemma 9, there is some m ∈ Ii such that at least |A| − 16ǫ 1/4N of the differences a − m, a ∈ A, lie in D(A, 32ǫ 1/2N). Let k be maximal so that Ik contains at least 9ǫ 1/4N points of A. Again, there is M ∈ Ik so that at least |A| − 16ǫ 1/4N of the differences a − m, a ∈ A, lie in D(A, 32ǫ 1/2N). Clearly for at least |A| − 32ǫ 1/4N values of a both a − m and a − M are popular. Furthermore |A ∩ [1, m]| ≤ 9ǫ 1/4N ǫ 1/8 ≤ 9ǫ 1/8N, and a similar inequality holds for |A ∩[M, N]|. Thus there is a set B ⊆ A, with the following properties: 8 (i) B is contained in {m + 1, . . . , M}; (ii) |B| ≥ |A| − 50ǫ 1/8N; (iii) For all b ∈ B the differences b − m and b − M are both in D(A, 32ǫ 1/2N). Observe that the first and second of these points imply that M − m > N/4. Now let t = M − m. Following Lev and Smeliansky [13], consider the projection map π : Z → Z/tZ. We note some simple facts about this map in a lemma. Lemma 11 (i) |π(A)| ≥ |A| − 50ǫ 1/8N; (ii) Let δ > 0. If d ∈ D(A, 4δN) then π(d) ∈ D(π(A), δN); (iii) If d ∈ D(π(A), 8δN) then some element of π −1 (d) lies in D(A, δN). Proof. (i) Clearly |π(A)| ≥ |π(B)| = |B|. (ii) If d = a−a ′ then π(d) = π(a)−π(a ′ ). For different representations of d as a−a ′ , certain of these representations of π(d) may be the same. However, since t > N/4, no element of Z/tZ has more than 4 preimages under π which lie in A. The result follows. (iii) If π(d) = π(ai) − π(a ′ i ) then ai − a ′ i = d + λit for some λi ∈ Z. As t > N/4 and −N < ai − a ′ i < N there are at most 8 possible values for λi . Thus for at least one value of i there are δN solutions to ai − a ′ i = d + λit. It is immediate from part (iii) of this lemma that |D(A, δN)| ≥ |D(π(A), 8δN)|. However we can do better than this, since for several d at least two of the elements π −1 (d) are popular differences. Indeed, for any b ∈ B we have b−m, b−M ∈ D(A, 32ǫ 1/2N), but b−m ≡ b−M (mod t). Certainly π(b − m) ∈ D(π(A), 8ǫ 1/2N) by Lemma 11(ii). Thus, by Lemma 11(iii), we have |D(A, ǫ1/2N)| ≥ |D(π(A), 8ǫ 1/2N)| + |B| ≥ |D(π(A), 8ǫ 1/2N)| + |A| − 50ǫ 1/8N. (15) Combining this with (14) gives |D(π(A), 8ǫ 1/2N)| ≤ 2N(1 + 30ǫ 1/8 ) − 3|A|. (16) Now we must have |D(π(A), 8ǫ 1/2N)| ≤ 2|π(A)| − 16ǫ 1/4N, since otherwise (16) and Lemma 11(i) would give |A| ≤ ( 2 5 + 100ǫ 1/8 )N, which is contrary to our assumption about |A|. Thus Lemma 10 applies, and we may pass to a subset X ⊆ π(A) with |X| ≥ |A| − 54ǫ 1/8N (17) and X − X ⊆ D(π(A), 8ǫ 1/2N). (18) We distinguish three further cases. 9 Case 1. |X| ≥ t/2. Then X − X is all of Z/tZ, and so (16) and (18) yield t ≤ 1 2 + 3η + 60ǫ 1/8
N. (19) But we know that, with at most 18ǫ 1/8N exceptions, the elements of A lie in the interval {m + 1, . . . , M} which has length t. This is alternative (i) of Proposition 7. Case 2. |X − X| ≥ 2|X| − t/3. Then (16),(17) and (18) give |A| ≤ ( 7 15 + 40ǫ 1/8 )N, contrary to assumption. Case 3. |X − X| < 2|X| − t/3. Then, by Kneser’s theorem on the addition of sets in abelian groups (see [14], Theorem 4.2), X−X is a union of cosets of some subgroup H ≤ Z/tZ of index 2. Thus t is even and π −1 (X) consists of integers of just one parity. That is, either at least |A|−54ǫ 1/8N elements of A are odd, or else at least that many are even. The latter possibility is, however, easily excluded; any subset of {2, 4, 6, . . . , 2⌊N/2⌋} of cardinality at least 12N/25 contains at least N2/100 additive triples. This concludes the proof of Proposition 7. An immediate corollary of Propositions 6 and 7 is the following result of Alon [1], Calkin [2] and Erd˝os and Granville (unpublished). Proposition 12 (Alon,Calkin,Erd˝os–Granville) |SF(N)| = 2N/2+o(N) . Proof. It follows from Proposition 7 that if F ⊆ [N] has o(N2 ) triples then |F| ≤ ( 1 2+o(1))N. The result now follows from Proposition 6. A much more important corollary for us will be the following description of almost all sum-free subsets of [N]. Corollary 13 With o(2N/2 ) exceptions, all sum-free subsets of [N] consist entirely of odd numbers, or else are contained in {⌈(N + 1)/3⌉, . . . , N}. Proof. Let A ∈ SF(N), and let F ∈ F contain A. The number of A for which |F| ≤ 1 2 − 1 120
N is certainly o(2N/2 ), so suppose that |F| ≥ 1 2 − 1 120
N. Proposition 7 then applies. Suppose first of all that alternative (ii) of that proposition holds, so that A contains o(N) even numbers. Suppose that A contains at least one even number, t say. If t < N/2 then we may select ⌊N/8⌋ disjoint pairs (x, x + t) of odd numbers, and A cannot contain both of the elements of any of them since it is sum-free. The number of choices for A is thus no more than 2N/4+o(N) 3 N/8 = o(2N/2 ). If t ≥ N/2 then a very similar argument applies with pairs (x, t − x). Thus all but o(2N/2 ) of the sum-free sets with o(N) even numbers consist entirely of odd numbers. Now suppose that alternative (i) of Proposition 7 holds. If  A ∩ 1 − 1 120
N, N  ≤ 32ǫ 1/8N (20) 10 then, using the fact that A ∩ [1, 1 − 1 120
N] is sum-free together with Theorem 12, we see that there are just o(2N/2 ) possibilities for A. Suppose, then, that (20) fails to hold. Since Proposition 7, (i), holds we infer that A is contained in the interval [ 1 2 − 1 30 − 256ǫ 1/8
N, N] with the exception of at most 32ǫ 1/8N elements. Suppose that A contains some element t ∈ {1, . . . , ⌊(N + 1)/3⌋}. Then we may select ⌊N/12⌋ − 4 totally disjoint pairs (x, x + t) with x ≥ N/2, and A can contain at most one element from each of them. This means that the number of choices for A is no more than 3N/122 ( 1 3 + 1 30 +o(1))N which, it can be checked, is o(2N/2 ). As we remarked in the introduction, Cameron and Erd˝os [4] addressed the issue of counting sum-free subsets of {⌈(N + 1)/3⌉, . . . , N}. They discovered that the number of such sets is asymptotically c(N)2N/2 , where c(N) takes two different constant values depending on whether N is odd or even. Combining their result with the work of this paper, then, leads to Theorem 2. Concluding remarks. The paper [4] of Cameron and Erd˝os can be hard to locate and so we have written up their argument and posted it on the web [8]. The author would like to thank Imre Ruzsa for the many conversations which led to the papers [9, 10] and which, naturally, have had a significant bearing on the present work. References [1] Alon, N., Independent sets in regular graphs and sum-free subsets of abelian groups, Israel Jour. Math. 73 (1991) 247 – 256. [2] Calkin, N.J.,On the number of sum-free sets, Bull. London Math. Soc. 22 (1990), no. 2, 141–144. . [3] Calkin, N. J., Taylor, A. C. Counting sets of integers, no k of which sum to another, J. Number Theory 57 (1996), no. 2, 323–327. [4] Cameron, P.J; Erd˝os, P. On the number of sets of integers with various properties, Number theory (Banff, AB, 1988), 61–79, de Gruyter, Berlin, 1990. [5] Cameron, P.J and Erd˝os, P. Notes on sum-free and related sets, Recent trends in combinatorics (M´atrah´aza, 1995), 95–107, CUP, Cambridge, 2001. [6] Deshouillers, J-M; Freiman, G. A; S´os, V; Temkin, M; On the structure of sum-free sets. II, Structure theory of set addition. Ast´erisque 258, (1999), xii, 149–161. [7] Freiman, G. A. On the structure and the number of sum-free sets, Journ´ees Arithm´etiques, 1991 (Geneva). Ast´erisque 209, (1992), 13, 195–201. 11 [8] Green, B.J. Notes on an argument of Cameron and Erd˝os, available at: http://www.dpmms.cam.ac.uk/˜bjg23/papers/ce.pdf. [9] Green, B.J. and Ruzsa, I.Z. Counting sumsets and sum-free sets in Z/pZ, preprint. [10] Green, B.J. and Ruzsa, I.Z. Counting sum-free sets in abelian groups, preprint. [11] Lev, V.F., Luczak, T. and Schoen, T. Sum-free sets in abelian groups, Israel Jour. Math. 125(2001) 347 – 367. [12] Lev, V.F. and Schoen, T. Cameron-Erd˝os modulo a prime, Finite Fields Appl. 8 (2002), no. 1, 108–119. [13] Lev, V. F. and Smeliansky, P. Y. On addition of two distinct sets of integers, Acta Arith. 70 (1995), no. 1, 85–91. [14] Nathanson, M.B. Additive number theory: inverse problems and the geometry of sumsets, Graduate Texts in Mathematics 165, Springer-Verlag, New York 1996. Ben Green Trinity College, Cambridge, England. email: [e-mail] 12