LARGE SUM-FREE SETS IN ℤ/pℤ

VSEVOLOD F. LEV

Abstract. We show that if p is prime and A is a sum-free subset of ℤ/pℤ with n := |A| > 0.33p, then A is contained in a dilation of the interval [n, p − n](mod p).

1. Introduction

A subset A of an abelian group is said to be sum-free if a_{1}+a_{2} = a_{3} with a_{1}, a_{2}, a_{3} ∈ A is impossible; that is, if the equation x + y = z has no solutions in the elements of A. To our knowledge, sum-free sets were introduced by Schur whose celebrated result (considered now one of the origins of the Ramsey theory) is that the set of positive integers cannot be partitioned into finitely many sum-free sets. Further study of sum-free sets was motivated to a large extent by a famous conjecture of Cameron and Erdős, recently settled by Green [G04]. We refer the reader to [GR05, K98, L03, ŁLS01, WSW72] for an extended historical account, current state of the art, and the background motivating one’s interest in sum-free sets.

How large can a sum-free subset of a finite abelian group be? For some groups the answer has been known for over 35 years, see [DY69, RS70, Y72, Y75]; however, for a number of particularly “tough” groups the problem remained open until the recent paper by Green and Ruzsa [GR05]. Much effort has also been made to determine the structure of sum-free subsets of the maximum possible size; for numerous results of this sort and further references see [WSW72]. On the other hand, there were almost no attempts to advance further and to study sum-free subsets of size close to the maximum possible. We mention two exceptions. One is the remarkable paper by Davydov and Tombak [DT89], well-known to coding theorists and experts in finite geometries. As shown in [DT89], any sum-free subset A of the elementary abelian 2-group of rank r ≥ 4, such that |A| > 5·2^{r−4}, is contained in a proper coset. Another exception is [L05] where a result of this sort is established for elementary abelian 3groups. Similar in its spirit is the problem of classifying large integer sum-free subsets of the interval [1, n]; see [F92, DFST99].

2. The main result

In the present paper we consider the problem for cyclic groups of prime order which, following the number-theoretic tradition, are understood as the quotient groups ℤ/pℤ.

It is not difficult to prove that if A ⊆ ℤ/pℤ is sum-free, where p ≥ 2 is a (not necessarily prime) integer, then |A| ≤ ⌊(p + 1)/3⌋. This is best possible as one verifies easily considering appropriate intervals. More precisely, let φ_{p}: ℤ → ℤ/pℤ denote the canonical homomorphism and for a set S ⊆ ℤ write S_{p} := φ_{p}(S), the image of S under φ_{p}. (Here S can be substituted by a letter or any notation, customarily used for integer sets.) Then for a := ⌊(p + 1)/3⌋ the set [a, 2a − 1]_{p} is sum-free. Moreover, any subset of [a, 2a − 1]_{p} is sum-free, as well as any dilation of such a subset by a factor, co-prime with p. The aim of this paper is to establish the following result showing that if p is prime and a sum-free subset A ⊆ ℤ/pℤ is large, then A has the structure close to just described.

Theorem 1. Let p be a prime and suppose that A ⊆ ℤ/pℤ is sum-free. If n := |A| > 0.33p, then there exists an integer d such that A ⊆ {dz: z ∈ [n, p − n]_{p}}.

We notice that the interval [n, p − n]_{p} contains n + (p + 1 − 3n) elements of ℤ/pℤ, so that the set A of Theorem 1 is actually a very dense subset of a dilation of this interval.

What makes Theorem 1 non-trivial is that 0.33 < 1/3. The constant 0.33 is merely an artifact of our method, and it would be interesting to replace it with a smaller value. It is not quite clear to us how far can one go in this direction, though we have an example showing that it cannot be reduced to below 0.2. In contrast, the interval [n, p − n]_{p} is best possible, as we proceed to explain.

Given a subset A of an abelian group we write

2A := {a_{1} + a_{2} : a_{1}, a_{2} ∈ A}

(the sumset of A),

A − A := {a_{1} − a_{2} : a_{1}, a_{2} ∈ A}

(the difference set of A), and

d ∗ A := {da: a ∈ A}

(the dilation of A by the factor d ∈ ℤ).

Example 1. For a prime p and a positive integer a ≤ (p + 1)/4 let

A := [a, 2a − 1]_{p} ∪ [p − 2a + 1, p − a]_{p}  (1)

so that the cardinality of A is n := 2a and

2A = [2a, 4a − 2]_{p} ∪ [p − a + 1, p + a − 1]_{p} ∪ [p − 4a + 2, p − 2a]_{p}.  (2)

If a ≤ (p + 1)/6 then the intervals in (1) are disjoint with those in (2), hence A is sum-free. Furthermore,

2 ∗ A = {2a, 2a + 2, …, 4a − 2}_{p} ∪ {p − 4a + 2, p − 4a + 4, …, p − 2a}_{p}

whence 2∗A ⊆ [n, p−n]_{p} and moreover, 2∗A is not contained in a proper subinterval of [n, p − n]_{p}. Finally we show that if a ≥ (p + 3)/8 then d ∗ A ⊈ [n, p − n]_{p} for any d ∈ [3, p − 3]. It suffices to prove that

(d ∗ [a, 2a − 1]_{p}) ∩ [−2a, 2a]_{p} = ∅  (3)

does not hold for 3 ≤ d ≤ (p − 1)/2. For d = 3 this is immediate from p − 2a ≤ 3(2a − 1) ≤ p + 2a. For d ≥ 4 we have

d ≤ \frac{p + 3}{2} − 2 ≤ 4a − 2 < (2a + 1) − (−2a − 1).

Thus if (3) were true then, taking into account that d ∗ [a, 2a − 1]_{p} is the image under φ_{p} of an arithmetic progression with the difference d between consecutive elements, we would conclude that

(2a − 1)d − ad ≤ (p − 2a − 1) − (2a + 1) = p − 4a − 2.

Equivalently,

(a − 1)d ≤ p − 6 − 4(a − 1),
(a − 1)(d + 4) ≤ p − 6,

and it would follow that a ≤ (p − 6)/8 + 1 < (p + 3)/8, contrary to the assumptions.

We now turn to the proof of Theorem 1. Our argument involves two parts. First, character sums are used to show that there is a dilation of A with unproportionally many elements in an interval of the form [u, u + p/2)_{p}. The standard tool to derive a conclusion of this kind is a classical lemma of Freiman [F62, Lemma 1], but unfortunately the estimate it yields is too weak for our purposes. For this reason we use [L, Corollary 2] instead, gaining a vital improvement in the constants. Secondly (and this is where the major difficulty lies), a combinatorial argument is employed to show that if u is suitably chosen, then in fact the whole set A is contained in [u, u + p/2)_{p} and, moreover, A ⊆ [n, p − n]_{p}. The proof is presented in Section 4; several auxiliary results are gathered in the next section.

3. The tools

We start with three lemmas dealing with the structure of the difference set A − A for the case where A is a dense set of integers.

Lemma 1. Let n and l be positive integers satisfying l ≤ 2n − 2 and suppose that A ⊆ [0, l] is a set of integers such that |A| = n. Then

[−(2n − 2 − l), 2n − 2 − l] ⊆ A − A.

Proof. If g > 0 is an integer with g ∉ A − A then A ∩ (g + A) = ∅ and both A and g + A are contained in [0, l + g], whence l + g + 1 ≥ 2n by the boxing principle and therefore g ≥ 2n − 1 − l. By symmetry, if g < 0 is an integer with g ∉ A − A, then in fact g ≤ −(2n − 1 − l). □

Lemma 2. Let n and l be positive integers satisfying l ≤ 2n − 2 and suppose that A ⊆ [0, l] is a set of integers such that |A| = n. Then for any integer k ≥ 1 we have

(\frac{l − n + 1}{k}, \frac{n}{k}) ⊆ A − A.

Proof. Fix an integer g > 0 and for j ∈ [0, g − 1] consider the arithmetic progression P_{j} := {j, j +g, …, j +(2k−1)g}. If g ∉ A−A then of any two consecutive elements of each P_{j} at most one belongs to A so that |P_{j} ∩A| ≤ k, implying |A∩[0, 2kg−1]| ≤ kg. If l ≤ 2kg − 1 this gives n ≤ kg whence g ≥ n/k; if l ≥ 2kg then one derives easily that n ≤ kg + (l + 1 − 2kg) whence g ≤ (l + 1 − n)/k. In any case g does not fall into the “forbidden” interval ((l − n + 1)/k, n/k). □

Lemma 3. Let n and l be positive integers and suppose that A ⊆ [0, l] is a set of integers such that |A| = n. If l < \frac{2k−1}{k} n − 1 with an integer k ≥ 2, then

(−\frac{n}{k − 1}, \frac{n}{k − 1}) ⊆ A − A.

Proof. This follows from Lemma 2 and the observation that if κ ≥ k then l < \frac{2κ−1}{κ} n − 1 which is equivalent to \frac{n}{κ} > \frac{l−n+1}{κ−1}. □

It can be shown that Lemmas 1– 3 are best possible in the sense that the intervals of these lemmas cannot be extended.

Our next lemma is the “difference version” of a well-known result of Freiman; it follows readily, for instance, from [LS95, Theorem 2].

Lemma 4. Let l and n be positive integers and suppose that A ⊆ [0, l] is a set of integers such that |A| = n, 0 ∈ A, l ∈ A, and gcd(A) = 1. Then

|A − A| ≥ min{l + n, 3n − 3}.

We notice that Lemmas 1–3 remain valid if A is a subset of ℤ/pℤ (rather than ℤ), the condition A ⊆ [0, l] is replaced by A ⊆ [u, u+l]_{p} with integer u and l < p, and the intervals in the conclusions of the lemmas are replaced with their images under φ_{p}. Similarly, the estimate of Lemma 4 remains valid if A ⊆ [u, u + l]_{p} with integer u and l < p/2 and given that the set φ_{p}^{−1}(A) ∩ [u, u + l] is not contained in an arithmetic progression of length smaller than l.

We finish this section with a reformulation of [L, Corollary 2]. We use the standard notation e_{p}(z) = exp(2πiz/p) where p is a positive integer and z is either an integer or an element of ℤ/pℤ.

Lemma 5. Let p be a positive integer and suppose that A ⊆ ℤ/pℤ. Write n := |A| and S := ∑_{a∈A} e_{p}(a). Then there exists an integer u such that

|A ∩ [u, u + p/2)_{p}| ≥ \frac{n}{2} + \frac{p}{2π} arcsin (|S| sin \frac{π}{p} ).

4. Proof of Theorem 1

We break the proof into a number of steps.

1) If p < 100 then n > 0.33p > (p − 1)/3 whence in view of 2A ∩ A = ∅ we have |2A| ≤ p − n < 2n. Thus |2A| ≤ 2n − 1 and by a well-known theorem of Vosper, A is an arithmetic progression; replacing it with a suitable dilation we can write A = [u, u + n − 1]_{p}, with an integer 0 < u ≤ p − n. One now verifies easily that the fact that A is sum-free implies u ≥ n and u + n − 1 ≤ p − n, concluding the proof in this special case. For the rest of the proof we assume that p > 100.

2) Define α > 0.33 by n = αp and for integer z write Â(z) := ∑_{a∈A} e_{p}(az); thus Â(z) are the Fourier coefficients of the indicator function of A. Since A is sum-free we have ∑_{z=0}^{p−1} Â(z)|Â(z)|^{2} = 0 whence using the Parseval identity we obtain

n^{3} ≤ ∑_{z=1}^{p−1} |Â(z)|^{3} ≤ max_{1≤z≤p−1} |Â(z)| · ∑_{z=1}^{p−1} |Â(z)|^{2} = n(p − n) max_{1≤z≤p−1} |Â(z)|.

Dilating A as necessary, we can assume that

|Â(1)| ≥ \frac{n^{2}}{p − n} = \frac{α^{2}}{1 − α} p

and then by Lemma 5 there is an integer u such that the interval [u, u+p/2)_{p} contains at least

\frac{n}{2} + \frac{p}{2π} arcsin (|Â(1)| sin \frac{π}{p} ) ≥ (\frac{α}{2} + \frac{1}{2π} arcsin (\frac{α^{2}}{1 − α} p sin \frac{π}{p} )) p  (4)

elements of A.

Set A_{0} := A ∩ [u, u + p/2)_{p} and n_{0} := |A_{0}| and write the right-hand side of (4) as g(α, p)p. Since p > 100 (see Step 1) and α > 0.33 and since g(α, p) is an increasing function of both α and p, we have

n_{0} > g(0.33, 100)p > 0.25p.

3) We have shown that there are integer u and 0 < l_{0} < p/2 such that, letting A_{0} := A ∩ [u, u + l_{0}]_{p}, we have n_{0} := |A_{0}| > 0.25p. Without loss of generality we can assume that, moreover,

(i) n_{0} ≥ |A ∩ [u′, u′ + p/2)_{p}| for any integer u′; (ii) u, u + l_{0} ∈ A_{0}; (to simplify the notation we occasionally identify integers with

their images under φ_{p}); (iii) 0 < u < p; (iv) φ_{p}^{−1}(A_{0}) ∩ [u, u + l_{0}] is not contained in an arithmetic progression of length

smaller than l_{0}.

We notice that (iv) follows from the observation that A can be replaced with its dilations, and that (i) implies

A ∩ (u + l_{0} − p/2, u)_{p} = A ∩ (u + l_{0}, u + p/2)_{p} = ∅.  (5)

4) Set δ := |A\(−A)|. Since A is sum-free we have A∩(A−A) = (−A)∩(A−A) = ∅ and hence

n + δ = |A ∪ (−A)| ≤ p − |A − A| ≤ p − |A_{0} − A_{0}|.  (6)

To estimate |A_{0} − A_{0}| we apply Lemma 4 (see also the remark following the lemma); this gives

p − n − δ ≥ |A_{0} − A_{0}| ≥ min{l_{0} + n_{0}, 3n_{0} − 3}.

Assuming l_{0} ≥ 2n_{0} − 3 we then obtain

p ≥ n + δ + 3n_{0} − 3 > (0.33 + 3 · 0.25)p − 3 = 1.08p − 3,

contradicting the assumption p > 100. Thus

l_{0} ≤ 2n_{0} − 4,  (7)
|A_{0} − A_{0}| ≥ l_{0} + n_{0},  (8)

and p − n − δ ≥ l_{0} + n_{0} whence

l_{0} ≤ p − n − n_{0} − δ.  (9)

Notice that this gives

l_{0} ≤ p − n − n_{0} = \frac{7}{4} n_{0} − (n + \frac{11}{4} n_{0} − p)

< \frac{7}{4} n_{0} − (0.33 + 11 · 0.25^{2} − 1)p = \frac{7}{4} n_{0} − 0.0175p < \frac{7}{4} n_{0} − 1

and hence

(−\frac{n_{0}}{3} , \frac{n_{0}}{3} )_{p} ⊆ A_{0} − A_{0}  (10)

by Lemma 3 as applied with k = 4.

5) We observe that to complete the proof it suffices to show that

l_{0} < \frac{3}{2} n_{0} − 1.  (11)

Indeed, if this holds then (−n_{0}, n_{0})_{p} ⊆ A_{0} − A_{0} by Lemma 3 whence

A ⊆ [n_{0}, p − n_{0}]_{p} ⊆ (p/4, 3p/4)_{p}

(as A is disjoint with A_{0} − A_{0}) and therefore A_{0} = A by assumption (i) of Step 2. This gives n_{0} = n and A ⊆ [n, p − n]_{p}, as required.

6) We claim that

0 ∉ [u, u + l_{0}]_{p};  (12)

for otherwise A_{0} and A_{0} − A_{0} are disjoint subsets of [−l_{0}, l_{0}]_{p} so that

2l_{0} + 1 ≥ |A_{0}| + |A_{0} − A_{0}| ≥ l_{0} + 2n_{0}

by (8), contradicting (7). On the other hand, modifying slightly (6) and using the Cauchy-Davenport inequality we can write

|A_{0} ∪ (−A_{0})| ≤ p − |A − A| ≤ p − (2n − 1) < 2n_{0} = |A_{0}| + | − A_{0}|

(notice that 2n + 2n_{0} > 2(0.33 + 0.25)p = 1.16p > p + 1), hence A_{0} ∩ (−A_{0}) ≠ ∅. Along with (12) and assumption (iii) of Step 3 this shows that

0 < u < p/2 < u + l_{0} < p  (13)

and our next claim is that

p/4 < u < p/2.  (14)

For a contradiction, suppose that 0 < u < p/4. As

l_{0} + 1 − n_{0} ≤ p/4 − (n + 2n_{0} − 3p/4) + 1 < p/4 − (0.33 + 2 · 0.25 − 0.75)p + 1 = p/4 − 0.08p + 1 < p/4

by (9) and the assumption p > 100 and since

(l_{0} + 1 − n_{0}, p/4)_{p} ⊆ (l_{0} + 1 − n_{0}, n_{0})_{p} ⊆ A_{0} − A_{0}

by Lemma 2, we have then u ≤ l_{0} + 1 − n_{0} in view of u ∈ A_{0}. Furthermore, writing [u, p/4)_{p} = [u, l_{0} + 1 − n_{0}]_{p} ∪ (l_{0} + 1 − n_{0}, p/4)_{p} and (3p/4, p − u]_{p} = (3p/4, p − (l_{0} + 1 − n_{0})]_{p} ∪ (p − (l_{0} + 1 − n_{0}), p − u]_{p} we obtain

|A ∩ [u, p/4)_{p}| ≤ l_{0} + 2 − n_{0} − u,  (15)
|A ∩ (3p/4, p − u]_{p}| ≤ l_{0} + 2 − n_{0} − u.  (16)

We also have

|A ∩ (p/4, 3p/4)_{p}| ≤ n_{0},  (17)

by Step 3, assumption (i). Adding together (15), (16), and (17) we obtain

|A_{0} ∪ (−A_{0})| ≤ |A ∩ [u, p − u]_{p}| + δ ≤ n_{0} + 2(l_{0} + 2 − n_{0} − u) + δ.  (18)

On the other hand, since A_{0} ∩ (−A_{0}) ⊆ [p − u − l_{0}, u + l_{0}]_{p} (as follows from (13)), we have

|A_{0} ∩ (−A_{0})| ≤ (u + l_{0}) + 1 − (p − u − l_{0})  (19)

in a trivial way. Summing up (18) and (19) we get

2n_{0} ≤ (2l_{0} + 4 − n_{0} − 2u + δ) + (2u + 2l_{0} + 1 − p),

that is 3n_{0} + p ≤ 4l_{0} + 5 + δ. Taking into account (9) we derive that

3p + 5 ≥ 7n_{0} + 4n > (7 · 0.25 + 4 · 0.33)p = 3.07p

which contradicts the assumption p > 100.

Thus (14) is established and by symmetry (more precisely, since A can be replaced by −A and u by p − u − l_{0} in the above argument) we also have u + l_{0} < 3p/4. Comparing with (13) we obtain

p/4 < u < p/2 < u + l_{0} < 3p/4.  (20)

7) If l_{0} < p/3 then l_{0}/n_{0} < 4/3 whence

l_{0} < \frac{3}{2} n_{0} − \frac{1}{6} n_{0} < \frac{3}{2} n_{0} − 1

so that (11) holds true and the proof is over. Suppose now that

l_{0} > p/3.  (21)

By (5) we have A \ A_{0} ⊆ (u − p/2, u + l_{0} − p/2)_{p} and we represent A \ A_{0} as a disjoint union A_{1} ∪ A_{2} ∪ A_{3} where

A_{1} := A ∩ (u − p/2, p − 2l_{0} − u)_{p},
A_{2} := A ∩ [p − 2l_{0} − u, l_{0} − u]_{p},  (22)
A_{3} := A ∩ (l_{0} − u, u + l_{0} − p/2)_{p}.

(Observe that A_{1} and A_{3} are well-defined as u−p/2 < p−2l_{0}−u and l_{0}−u < u+l_{0}−p/2 by (20), and A_{2} is well-defined as p − 2l_{0} − u < l_{0} − u by (21).) We have

u + A_{3} ⊆ (l_{0}, 2u + l_{0} − p/2)_{p}, (u + l_{0}) + A_{1} ⊆ (2u + l_{0} − p/2, p − l_{0})_{p}

so that the four sets A_{0} − A_{0} ⊆ [−l_{0}, l_{0}]_{p}, u + A_{3}, (u + l_{0}) + A_{1}, and A are pairwise disjoint and therefore

p ≥ |A_{1}| + |A_{3}| + |A_{0} − A_{0}| + |A| ≥ |A_{1}| + |A_{3}| + (l_{0} + n_{0}) + n = l_{0} + 2n − |A_{2}|

by (8). Consequently,

|A_{2}| ≥ l_{0} + 2n − p.  (23)

8) We now claim that

l_{0} < \frac{5}{3} n_{0} − 1.  (24)

Assuming this is wrong, let

I := [\frac{n_{0}}{3} , \frac{l_{0} − n_{0} + 1}{2}]_{p} and J := [\frac{n_{0}}{2} , l_{0} − n_{0} + 1]_{p};  (25)

these intervals are well-defined as

\frac{l_{0} − n_{0} + 1}{2} − \frac{n_{0}}{3} = \frac{1}{2} (l_{0} − \frac{5}{3} n_{0} + 1) ≥ 0

and

(l_{0} − n_{0} + 1) − \frac{n_{0}}{2} = l_{0} − \frac{3}{2} n_{0} + 1 ≥ 0.  (26)

Since ((l_{0} − n_{0} + 1)/2, n_{0}/2)_{p}, (l_{0} − n_{0} + 1, n_{0})_{p} ⊆ A_{0} − A_{0} by Lemma 2 and taking into account (10) we get

A_{2} ⊆ A ∩ (−p/4, p/4)_{p} ⊆ (−J) ∪ (−I) ∪ I ∪ J,

with A_{2} defined by (22).

We distinguish two cases. First, suppose that both intervals −J and J contain elements of A_{2}. Since A_{2} contains no elements in the “gaps” between −J, −I, I, and J, and is itself contained in an interval of length (l_{0} − u) − (p − 2l_{0} − u), we have in this case

|A_{2}| < (l_{0} − u) + 1 − (p − 2l_{0} − u) − 2(\frac{n_{0}}{2} − \frac{l_{0} − n_{0} + 1}{2} − 1) − (2 · \frac{n_{0}}{3} − 1)

= 4l_{0} − \frac{8}{3} n_{0} − p + 5.

Comparing with (23) we get

l_{0} + 2n − p < 4l_{0} − \frac{8}{3} n_{0} − p + 5,
2n + \frac{8}{3} n_{0} < 3l_{0} + 5

whence by (9)

3p + 5 > 5n + \frac{17}{3} n_{0} > (5 · 0.33 + (17/3) · 0.25)p > 3.06p,

contradicting the assumption p > 100.

Now suppose that at least one of the intervals −J and J contains no elements of A_{2}; say, A_{2} ∩ (−J) = ∅. Since for any a ∈ A_{2} ∩ I we have 2a ∈ J \ A_{2}, it follows that

|A_{2} ∩ I| + |A_{2} ∩ J| ≤ |J| ≤ l_{0} − \frac{3}{2} n_{0} + 2

and hence

|A_{2}| = |A_{2} ∩ (−I)| + |A_{2} ∩ I| + |A_{2} ∩ J|

≤ (\frac{l_{0} − n_{0} + 1}{2} − \frac{n_{0}}{3} + 1) + (l_{0} − \frac{3}{2} n_{0} + 2)

= \frac{3}{2} l_{0} − \frac{7}{3} n_{0} + \frac{7}{2}.

Combining this with (23) and (9) we get

l_{0} + 2n − p ≤ \frac{3}{2} l_{0} − \frac{7}{3} n_{0} + \frac{7}{2},
4n + \frac{14}{3} n_{0} ≤ l_{0} + 2p + 7,
3p + 7 ≥ 5n + \frac{17}{3} n_{0}.

Since n_{0} ≥ (p + 1)/4 we derive that

3p + 7 ≥ (5 · 0.33 + (17/3) · 0.25)p + (17/12) > 3.06p + 1,

a contradiction again. This proves (24).

9) We are now in a position to establish (11), completing the proof of Theorem 1. Suppose that (11) does not hold and define then J as in (25); computation (26) shows that this definition is correct. By (24) and Lemma 3, we have

( − \frac{n_{0}}{2} , \frac{n_{0}}{2} )_{p} ⊆ A_{0} − A_{0}

and by Lemma 2,

(l_{0} − n_{0} + 1, n_{0})_{p} ⊆ A_{0} − A_{0}.

These two inclusions along with the definition of J show that

A_{2} ⊆ A ∩ (−p/4, p/4)_{p} ⊆ (−J) ∪ J.

On the other hand, A_{2} is contained in an interval of length

(l_{0} − u) − (p − 2l_{0} − u) = 3l_{0} − p < (l_{0} − n_{0} + 1) − (−n_{0}/2)

(an easy verification based on (9) is left to the reader), hence

|A_{2}| ≤ |J| ≤ l_{0} − \frac{3}{2} n_{0} + 2

which by (23) and (9) implies

l_{0} + 2n − p ≤ l_{0} − \frac{3}{2} n_{0} + 2,

p + 2 ≥ 2n + \frac{3}{2} n_{0} > (2 · 0.33 + (3/2) · 0.25)p = 1.035p,

a contradiction proving (11).

Acknowledgement

The author is grateful to Gregory Freiman for fruitful discussions.

References

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

[DFST99] J.-M. Deshouillers, G. Freiman, V. Sós, and M. Temkin, On the structure of sum-free sets. II, Astérisque 258 (1999), xii, 149–161.

[DY69] P.H. Diananda and H.P. Yap, Maximal sum-free sets of elements in finite groups, Proc. Japan Acad. 45 (1969), 1–5.

[F62] G.A. Freiman, Inverse problems of additive number theory, VII. On addition of finite sets, IV, Izv. Vyss. Ucebn. Zaved. Matematika 6 (31) (1962), 131–144.

[F92] , On the structure and the number of sum-free sets, Astérisque 209 (1992), 13, 195–201.

[G04] B. Green, The Cameron-Erdős Conjecture, Bull. London Math. Soc. 36 (6) (2004), 769–778.

[GR05] B. Green and I.Z. Ruzsa, Sum-free sets in abelian groups, Israel J. Math. 147 (2005), 157–188.

[K98] K.S. Kedlaya, Product-free subsets of groups, Amer. Math. Monthly 105 (10) (1998), 900–906.

[L03] V.F. Lev, Sharp estimates for the number of sum-free sets, Journal für die reine und angewandte Mathematik (Crelle’s Journal) 555 (2003), 1–25.

[L05] , Large sum-free sets in ternary spaces, Journal of Combinatorial Theory, Ser. A 111(2) (2005), 337–346.

[L] , Distribution of points on arcs, INTEGERS, to appear.

[LS95] V.F. Lev and P.Y. Smeliansky, On addition of two distinct sets of integers, Acta Arithmetica 70 (1) (1995), 85–91.

[ŁLS01] T. Łuczak, V.F. Lev, and T. Schoen, Sum-free sets in abelian groups, Israel Journal

of Mathematics 125 (2001), 347–367.

[RS70] A.H. Rhemtulla and A.P. Street, Maximal sum-free sets in finite abelian groups, Bull. Austral. Math. Soc. 2 (1970), 289–297.

[WSW72] J.S. Wallis, A.P. Street, and W.D. Wallis, Combinatorics: Room squares, sum-free sets, Hadamard matrices, Lecture Notes in Mathematics 292 (1972), Springer-Verlag.

[Y72] H.P. Yap, Maximal sum-free sets in finite abelian groups. IV, Nanta Mathematica 5 (3) (1972), 70–75.

[Y75] , Maximal sum-free sets in finite abelian groups. V, Bull. Austral. Math. Soc. 13 (3) (1975), 337–342.

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

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