A REFINED BOUND FOR SUM-FREE SETS IN GROUPS OF PRIME ORDER

JEAN-MARC DESHOUILLERS AND VSEVOLOD F. LEV

Abstract. Improving upon earlier results of Freiman and the present authors, we show that if p is a sufficiently large prime and A is a sum-free subset of the group of order p, such that n := |A| > 0.318p, then A is contained in a dilation of the interval [n, p − n] (mod p).

1. Introduction

The subset A of an additively written semigroup is called sum-free if there do not exist a_{1}, a_{2}, a_{3} ∈ A with a_{1} + a_{2} = a_{3}; equivalently, if A is disjoint with its sumset A + A := {a_{1} + a_{2} : a_{1}, a_{2} ∈ A}. Introduced by Schur in 1916 (“the set of positive integers cannot be partitioned into finitely many sum-free subsets”), sum-free sets have now become a classical object of study in additive combinatorics; we refer the reader to [DF06, L06b] and the papers cited there for the history and overview of the subject area.

Let G be a finite abelian group. It is easy to see that a randomly chosen “small” subset of G is sum-free with high probability, while a randomly chosen “large” subset of G with high probability is not sum-free. Thus, small sum-free subsets of G can be unstructured, whereas large sum-free subsets possess a rigid structure. Unraveling this structure for various underlying groups G is a fascinating problem which received much attention during the last decade.

In the present paper, we consider groups of prime order p, which we identify with the quotient group ℤ/pℤ. Let φ_{p} denote the canonical homomorphism from ℤ onto ℤ/pℤ, and for a set S ⊆ ℤ let S_{p} denote the image of S under φ_{p}; here the letter S will often be substituted by the interval notation so that, for instance, [3, 6)_{11} = {−8, 4, 16}_{11} etc. The well-known Cauchy-Davenport inequality implies readily that if A ⊆ ℤ/pℤ is sum-free, then |A| ≤ ⌊(p + 1)/3⌋. This estimate is sharp, as for u = ⌊(p + 1)/3⌋, the set [u, 2u−1]_{p}, and consequently its dilates, are sum-free.

The main results of both [L06b] and [DF06] show that in fact for prime p, any large sum-free subset of ℤ/pℤ is close to a dilate of (p/3, 2p/3)_{p}. Specifically, it is proved in [L06b] for α_{0} = 0.33, and in [DF06] for α_{0} = 0.324 and p large enough, that if A is a

2000 Mathematics Subject Classification. 11P70 (primary), 11B75, 11T30 (secondary).

Key words and phrases. sum-free sets.

2 JEAN-MARC DESHOUILLERS AND VSEVOLOD F. LEV

sum-free subset of ℤ/pℤ with n := |A| > α_{0}p, then A is contained in a dilate of [n, p−n]_{p}. (As shown in [L06b], the interval [n, p − n]_{p} is best possible in this context.)

For an integer d and a subset A of an abelian group, let d ∗ A := {da: a ∈ A}. The goal of the present paper is to prove

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

The seemingly modest improvement of the constant from 0.324 to 0.318 requires a substantial effort and a number of new ideas, some at the level of Fourier analysis and others of a combinatorial nature; we believe that these ideas may actually be of more general interest than the improvement of the constant itself.

An example, presented in [L], shows that the constant in question cannot be reduced below 0.2. Indeed, Olof Sisask and Alex Dainiak (personal communication in both cases) have recently came up with examples of subsets of ℤ/pℤ of size n = 0.25p + O(1) which are not contained in a dilation of the interval [−n, n]_{p}. In this connection we notice that the value 0.318 is not the precise limit of our method; however, narrowing significantly the gap between 0.25 and 0.318 seems to be a rather non-trivial and exciting problem.

We did not try to work out exactly what is “sufficiently large” in Theorem 1: the crucial parameter for us is the size of A with respect to p.

2. Some lemmas

We gather here several auxiliary results used in the next section to prove Theorem 1. It is well-known that if a set is sum-free, then its characteristic function has a large

Fourier coefficient. Specifically, let e_{p} denote the character of the group ℤ/pℤ, defined by e_{p}(1) := exp(2πi/p), and given a set A ⊆ ℤ/pℤ and an integer z, write Â(z) := ∑_{a∈A} e_{p}(az). A standard argument shows that if A ⊆ ℤ/pℤ is sum-free with |A| > α_{0}p, then there exists z ∈ ℤ with φ_{p}(z) ≠ 0 such that |Â(z)| > \frac{α_{0}^{2}}{1−α_{0}} p. For α_{0} = 0.318, this leads to |Â(z)| > 0.148p, while the following lemma allows us to get |Â(z)| > 0.152p.

Lemma 1. Let κ > 0 and γ ∈ (0, 1) be real numbers, and write K := ⌊γ^{−1/κ}⌋. Suppose that P > K is an integer and v_{1}, …, v_{P} are non-negative real numbers, satisfying

∑_{i=1}^{P} v_{i} = 1 and ∑_{i=1}^{P} v_{i}^{1+κ} ≥ γ.

Then the equation Kx^{1+κ} + (1 − Kx)^{1+κ} = γ in the variable x has exactly one solution in the interval (1/(K + 1), 1/K], and denoting this solution by X, we have

max{v_{1}, …, v_{P} } ≥ X.

A REFINED BOUND FOR SUM-FREE SETS IN GROUPS OF PRIME ORDER 3

Proof. The existence and uniqueness of a solution is an immediate consequence of the intermediate value property: just notice that the function f(x) := Kx^{1+κ} + (1 − Kx)^{1+κ} is continuous and strictly increasing on [1/(K + 1), 1/K], and that

f(1/(K + 1)) = \frac{1}{(K + 1)^{κ}} < γ ≤ \frac{1}{K^{κ}} = f(1/K).

We now prove the second assertion. Let W denote the set of all those real vectors (w_{1}, …, w_{P}) ∈ ℝ^{P} with non-negative coordinates, satisfying

∑_{i=1}^{P} w_{i} = 1 and ∑_{i=1}^{P} w_{i}^{1+κ} ≥ γ

(so that (v_{1}, …, v_{P}) ∈ W). Observing that W is compact and max{w_{1}, …, w_{P} } is a continuous function on W, set

μ := min{max{w_{1}, …, w_{P} }: (w_{1}, …, w_{P}) ∈ W }

and

C := {(w_{1}, …, w_{P}) ∈ W: max{w_{1}, …, w_{P} } = μ}.

We notice that if (w_{1}, …, w_{P}) ∈ C, then

γ ≤ ∑_{i=1}^{P} w_{i}^{1+κ} ≤ μ^{κ} ∑_{i=1}^{P} w_{i} = μ^{κ},

whence

\frac{1}{μ} ≤ γ^{−1/κ} < K + 1.  (1)

On the other hand, it is readily verified that if w_{i} = 1/K for i ∈ [1, K] and w_{i} = 0 for i ∈ [K + 1, P], then (w_{1}, …, w_{P}) ∈ W, and hence μ ≤ 1/K, implying 1/μ ≥ K. Comparing this with (1), we derive that

⌊1/μ⌋ = K.  (2)

For δ ∈ ℝ and i, j ∈ [1, P] with i ≠ j, define the operator T_{ij}^{(δ)} : ℝ^{P} → ℝ^{P} by T_{ij}^{(δ)}(w_{1}, …, w_{P}) = (w′_{1}, …, w′_{P}), where w′_{i} = w_{i} + δ, w′_{j} := w_{j} − δ, and w′_{k} = w_{k} for k ∈ [1, P] \ {i, j}. Observe that if w_{i} < w_{j} and 0 < δ < (w_{j} − w_{i})/2, then ∑_{i=1}^{P}(w′_{i})^{1+κ} < ∑_{i=1}^{P} w_{i}^{1+κ}.

Note, that if (w_{1}, …, w_{P}) ∈ C, then not all coordinates w_{i} are equal to each other: else they all would be equal to 1/P, implying γ ≤ P · (1/P)^{1+κ} = P^{−κ} and hence contradicting P ≥ K + 1 > γ^{−1/κ}.

We claim now that if (w_{1}, …, w_{P}) ∈ C, then equality holds in ∑_{i=1}^{P} w_{i}^{1+κ} ≥ γ. Indeed, assuming that ∑_{i=1}^{P} w_{i}^{1+κ} > γ, find i, j ∈ [1, P] with w_{i} < w_{j} = μ and apply to (w_{1}, …, w_{P}) the transformation T_{ij}^{(δ)} with δ ∈ (0, (w_{j} − w_{i})/2) small enough to ensure that the resulting vector (w′_{1}, …, w′_{P}) satisfies ∑_{i=1}^{P}(w′_{i})^{1+κ} > γ. Repeating this

4 JEAN-MARC DESHOUILLERS AND VSEVOLOD F. LEV

procedure sufficiently many times, we eventually find a vector (u_{1}, …, u_{P}) ∈ W with max{u_{1}, …, u_{P} } < μ, contradicting the definition of μ.

Next, we observe that for any (w_{1}, …, w_{P}) ∈ C there is at most one index i ∈ [1, P] such that 0 < w_{i} < μ. For if 0 < w_{i} ≤ w_{j} < μ, where i, j ∈ [1, P] are distinct, then, applying to (w_{1}, …, w_{P}) the transformation T_{ij}^{(δ)} with δ negative and sufficiently small in absolute value, we obtain a vector (w′_{1}, …, w′_{P}) ∈ C with ∑_{i=1}^{P}(w′_{i})^{1+κ} > γ; however, we showed above that this is impossible.

Fix (w_{1}, …, w_{P}) ∈ C. As it follows from our last observation, there is an integer k ∈ [1, P − 1] such that, re-ordering the coordinates of (w_{1}, …, w_{P}), if necessary, we can write

μ = w_{1} = ⋯ = w_{k} > w_{k+1} ≥ 0 = w_{k+2} = ⋯ = w_{P} .

From

kμ ≤ ∑_{i=1}^{P} w_{i} < (k + 1)μ,

it follows then that k ≤ 1/μ < k + 1, whence k = ⌊1/μ⌋ = K by (2), and consequently, w_{k+1} = 1 − Kμ. This yields

Kμ^{1+κ} + (1 − Kμ)^{1+κ} = γ,

so that in fact μ = X, implying the second assertion of the lemma and, indeed, showing that the estimate of the lemma is sharp. □

As indicated at the beginning of this section, Lemma 1 will be used to show that if A ⊆ ℤ/pℤ is sum-free with |A| > 0.318p, then there exists z ∈ ℤ with φ_{p}(z) ≠ 0 and |Â(z)| > 0.152p. A well-known result of Freiman then leads to the conclusion that there is an interval of the form [u, u + p/2)_{p}, with an integer u, containing at least (|A| + |Â(z)|)/2 > 0.235p elements of the dilation z ∗ A. Our next lemma, which is a reformulation of [L06a, Corollary 2], allows us to improve this to 0.238p.

Lemma 2 ([L06a, Corollary 2]). Let p be a positive integer and suppose that A ⊆ ℤ/pℤ. If 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} ).

For a subset A of an additively written abelian group, write

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

The following lemma follows readily from the results of [F62]; see also [LS95, Theorem 2].

A REFINED BOUND FOR SUM-FREE SETS IN GROUPS OF PRIME ORDER 5

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

|A − A| ≥ min{ℓ + m, 3m − 3}.

The next two lemmas deal with the structure of the difference set A − A in the case where A is a dense set of integers.

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

(\frac{ℓ − m + 1}{k}, \frac{m}{k}) ⊆ A − A.

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

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

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

The next lemma is a restatement of a particular case of a ℤ/pℤ-version of [DF06, Lemma 3].

Lemma 6. Let p be a prime and let 1 ≤ ℓ < p and u be integers. Suppose that A ⊆ ℤ/pℤ is sum-free and that A_{0} ⊆ [u, u + ℓ]_{p} ∩ A, and write m := |A_{0}|. If ℓ ≤ 2m − 2, then for any integer a ∈ (ℓ/4, ℓ/2] with φ_{p}(a) ∈ A we have

[2a − (2m − ℓ − 2), 2a + (2m − ℓ − 2)]_{p} ∩ (A ∪ (−A)) = ∅.

For the convenience of the reader, we provide a proof.

Proof of Lemma 6. Since |{z, z + a}_{p} ∩ A| ≤ 1 for any integer z, the set A_{0} has at most a elements in each of the intervals [u, u + 2a − 1]_{p} and [u + (ℓ − 2a + 1), u + ℓ]_{p}, and consequently we have

|A_{0} ∩ [u + 2a, u + ℓ]_{p}| ≥ m − a and |A_{0} ∩ [u, u + (ℓ − 2a)]_{p}| ≥ m − a.  (3)

Assuming now that there exists an integer x ∈ [2a − (2m − ℓ − 2), 2a + (2m − ℓ − 2)] with φ_{p}(x) ∈ A ∪ (−A), we will obtain a contradiction.

6 JEAN-MARC DESHOUILLERS AND VSEVOLOD F. LEV

Suppose first that x > 2a and consider in this case the two-element sets

{u, u + x}_{p}, {u + 1, u + 1 + x}_{p}, …, {u + ℓ − x, u + ℓ}_{p}.

(We notice that (3), along with a ≤ ℓ/2 < m, implies that m − a ≤ ℓ − 2a + 1, whence ℓ ≥ a + m − 1 and consequently, ℓ − x ≥ ℓ − (2a + (2m − ℓ − 2)) = 2(ℓ − a − m + 1) ≥ 0.) These sets are pairwise disjoint (as u + ℓ − x < u + x in view of 2x > 4a ≥ ℓ) and they all are contained in [u, u + ℓ − 2a]_{p} ∪ [u + 2a, u + ℓ]_{p}. Since at most one element out of each of these ℓ − x + 1 sets belongs to A_{0}, we conclude that

|[u, u + ℓ − 2a]_{p} \ A_{0}| + |[u + 2a, u + ℓ]_{p} \ A_{0}| ≥ ℓ − x + 1.

Therefore

|[u, u + ℓ − 2a]_{p} ∩ A_{0}| + |[u + 2a, u + ℓ]_{p} ∩ A_{0}| ≤ 2(ℓ − 2a + 1) − (ℓ − x + 1)
≤ ℓ − 4a + (2a + (2m − ℓ − 2)) + 1
= 2(m − a) − 1,

contradicting (3).

Similarly, if x < 2a, then we obtain a contradiction with (3) considering the l−4a+x+1 sets

{u + 2a − x, u + 2a}_{p}, {u + 2a − x + 1, u + 2a + 1}_{p}, …, {u + l − 2a, u + l − 2a + x}_{p}

which, again, are pairwise disjoint and contained in [u, u + l − 2a]_{p} ∪ [u + 2a, u + l]_{p}. □

Lemma 7. Let p be a prime and suppose that A ⊆ ℤ/pℤ is sum-free. Write n := |A|. If

[−(p − n + 1)/3, (p − n + 1)/3]_{p} ∩ A = ∅,

then A ⊆ [n, p − n]_{p}.

Proof. Set

μ := min{|z|: z ∈ ℤ, φ_{p}(z) ∈ A},  (4)

so that μ > (p − n + 1)/3. Clearly, for any a ∈ [μ, 2μ)_{p} ∩ A we have a + μ ∈ [2μ, 3μ)_{p} \ A, which gives

|[μ, 3μ)_{p} ∩ A| ≤ μ.

Assuming that μ < p/4, we get then

n ≤ μ + |[3μ, p − μ]_{p}| ≤ μ + (p − 4μ + 1) = p − 3μ + 1,

whence 3μ ≤ p − n + 1, contradicting the assumptions. We have therefore μ > p/4 and then 3μ > p − μ, implying

n = |A ∩ [μ, 3μ)_{p}| ≤ μ;

that is, [0, n − 1]_{p} ∩ A = ∅. In a similar way (or applying the argument above to the set −A := {−a: a ∈ A}) we obtain [p − (n − 1), p]_{p} ∩ A = ∅. The result follows. □

3. Proof of Theorem 1

Suppose that p is a prime and A ⊆ ℤ/pℤ is a sum-free set with n := |A| > 0.318p. The computations below tacitly assume that p is sufficiently large.

Recalling the definition of Â(z) from the beginning of Section 2, we start with

Claim 1. There exists an integer z_{0} with φ_{p}(z_{0}) ≠ 0 such that |Â(z_{0})| > 0.152p.

Proof. Let α := n/p, so that α > 0.318. By the Parseval identity, we have

∑_{z=1}^{p−1} |Â(z)|^{2} = ∑_{z=0}^{p−1} |Â(z)|^{2} − |Â(0)|^{2} = α(1 − α)p^{2}.  (5)

Using the fact that |Â(p − z)| = |Â(z)| for any z ∈ ℤ and letting P := (p − 1)/2, we re-write (5) as

∑_{z=1}^{P} \frac{|Â(z)|^{2}}{α(1 − α)p^{2}/2} = 1.

On the other hand, since A is sum-free, we have

∑_{z=0}^{p−1} |Â(z)|^{2}Â(z) = 0,

whence

∑_{z=1}^{p−1} |Â(z)|^{3} ≥ − ∑_{z=1}^{p−1} |Â(z)|^{2}Â(z) = |Â(0)|^{2}Â(0) = α^{3}p^{3}

and consequently,

∑_{z=1}^{P} (\frac{|Â(z)|^{2}}{α(1 − α)p^{2}/2})^{3/2} ≥ \sqrt{2} (\frac{α}{1 − α})^{3/2} > 0.4502.

Applying Lemma 1 with κ = 0.5 and γ = 0.4502 (which leads to K = 4), we conclude that there exists z_{0} ∈ [1, P] with

\frac{|Â(z_{0})|^{2}}{α(1 − α)p^{2}/2} > 0.2131

and accordingly

|Â(z_{0})| > \sqrt{0.2131 α(1 − α)/2} p > 0.152p.
□

8 JEAN-MARC DESHOUILLERS AND VSEVOLOD F. LEV

Dilating A, if necessary, we assume that, in fact,

|Â(1)| > 0.152p.  (6)

Choose an integer u_{0} such that the number of elements of A in [u_{0}, u_{0} + p/2)_{p} is maximized, set A_{0} := A ∩ [u_{0}, u_{0} + p/2)_{p} and m := |A_{0}|, and let B_{0} := φ_{p}^{−1}(A_{0}) ∩ [u_{0}, u_{0} + p/2). Furthermore, put ℓ := max B_{0} − min B_{0}; thus A_{0} is contained in a block of ℓ + 1 consecutive elements of ℤ/pℤ and

m = max{|A ∩ [u, u + p/2)_{p}|: u ∈ ℤ}.

We notice that the last equality implies that

n − m ≤ |A ∩ [u, u + p/2)_{p}| ≤ m  (7)

for all real u.

By Lemma 2, we have

m ≥ \frac{n}{2} + \frac{p}{2π} arcsin (|Â(1)| sin \frac{π}{p} ) > (0.159 + \frac{1}{2π} arcsin(0.1519π))p > 0.238p. (8)

Since B_{0} is a subset of an interval of length ℓ < p/2, this shows that B_{0} is not contained in an arithmetic progression with difference greater than 2, and we now dispose of the case where B_{0} is contained in an arithmetic progression with difference 2.

Claim 2. If B_{0} is contained in an arithmetic progression with difference 2, then the conclusion of the theorem holds true.

Proof. If B_{0} is contained in an arithmetic progression with difference 2, then there is an integer u and a set C ⊆ ℤ/pℤ such that C ⊆ [u, u + p/4)_{p} and either A_{0} = 2 ∗ C, or A_{0} = 2∗C +1. By (8), we have ⌊p/4⌋ < \frac{3}{2} m−1, whence (−m, m)_{p} ⊆ C −C by Lemma 5 (see also the remark after the lemma), implying 2 ∗ (−m, m)_{p} ⊆ A_{0} − A_{0}. Since A is sum-free, we derive that the set 2 ∗ (−m, m)_{p} is disjoint with A, and replacing A with its dilation by the factor (p − 1)/2, we obtain A ⊆ [m, p − m]_{p}. The assertion now follows from Lemma 7, as

(p − n + 1)/3 < 0.238p < m

by (8). □

In what follows, we assume that B_{0} is not contained in an arithmetic progression with difference greater than 1.

Since the sets A and A − A are disjoint, we have

n ≤ p − |A − A| ≤ p − |A_{0} − A_{0}|.

To estimate |A_{0} − A_{0}|, we apply Lemma 3; this gives

p − n ≥ |A_{0} − A_{0}| ≥ min{ℓ + m, 3m − 3}.  (9)

Assuming that ℓ ≥ 2m − 3 and using (8), we then obtain

p ≥ n + 3m − 3 > (0.318 + 3 · 0.238)p − 3 = 1.032p − 3,

a contradiction. Thus

ℓ ≤ 2m − 4,  (10)
|A_{0} − A_{0}| ≥ ℓ + m,  (11)

and p − n ≥ ℓ + m by (9), whence

ℓ ≤ p − n − m.  (12)

We assume, furthermore, that

ℓ ≥ \frac{3}{2} m − 1;  (13)

for otherwise (−m, m)_{p} ∩A = ∅ by Lemma 5, and consequently A ⊆ [n, p−n]_{p} (as at the end of the proof of Claim 2). Assumption (13) will eventually lead us to a contradiction.

Claim 3. We have

A ∩ (−m/2, m/2)_{p} = ∅.

Proof. Let μ be defined by (4); we want to show that μ ≥ m/2. Notice that by (10) and Lemma 4 we have ((ℓ − m + 1)/2, m/2)_{p} ⊆ A_{0} − A_{0} ⊆ A − A, and consequently ((ℓ − m + 1)/2, m/2)_{p} ∩ (A ∪ (−A)) = ∅; thus, it actually suffices to prove that μ > (ℓ − m)/2. Assume that this is wrong, and hence

cos π \frac{μ}{p} ≥ cos π \frac{ℓ − m}{2p} ≥ cos π \frac{p − n − 2m}{2p} = sin π \frac{n + 2m}{2p}  (14)

holds by (12).

Let μ̃ := φ_{p}(μ), so that μ̃ ∈ A ∪ (−A) and therefore A ∩ (A + μ̃) = ∅. Hence |A ∪ (A + μ̃)| = 2n and

| ∑_{a∈A∪(μ̃+A)} e_{p}(a)| = |(1 + e_{p}(μ̃)) Â(1)| = 2|Â(1)| cos π \frac{μ}{p}.  (15)

We distinguish two cases. Assume first that m > 0.25p. From (15) we get

2|Â(1)| cos π \frac{μ}{p} ≤ | ∑_{z=0}^{2n−1} e_{p}(z)| = \frac{sin 2πn/p}{sin π/p}

which, along with (14), (6), and the assumption m > 0.25p, implies

sin 2π \frac{n}{p} ≥ 2|Â(1)| cos π \frac{μ}{p} sin \frac{π}{p}

> 0.954 \frac{|Â(1)|}{0.152p} · \frac{sin π/p}{3.141/p} · cos π \frac{μ}{p}

> 0.954 sin π \frac{n + 2m}{2p}

> 0.954 sin \frac{π}{2} (\frac{n}{p} + 0.5) ,

where we have used the fact that sin π/p ≥ π/p − (π/p)^{3}/6 ≥ 3.141/p holds true for all sufficiently large p. It is easy to verify, however, that the function

sin 2πx − 0.954 sin \frac{π}{2} (x + 0.5)

is negative for any x ∈ (0.318, 0.334), a contradiction.

Assume now that m < 0.25p. In this case, we apply Lemma 2 to the set A ∪ (A + μ), observing that by (7) any interval of the form [u, u + p/2)_{p} with integer u contains at most 2m elements of this set; in view of (15), this yields

2m ≥ n + \frac{p}{2π} arcsin (2|Â(1)| cos π \frac{μ}{p} sin \frac{π}{p} ) ,

and hence

2π \frac{2m − n}{p} ≥ arcsin (2|Â(1)| cos π \frac{μ}{p} sin \frac{π}{p} ) .

Since 2π(2m − n)/p ≤ 2πm/p < π/2, we obtain

sin 2π \frac{2m − n}{p} ≥ 2|Â(1)| cos π \frac{μ}{p} sin \frac{π}{p} ,

which, as above, yields

sin 2π \frac{2m − n}{p} > 0.954 cos π \frac{μ}{p} > 0.954 sin π \frac{n + 2m}{2p}.  (16)

On the other hand, it is not difficult to see that the function

sin 2π(2y − x) − 0.954 sin \frac{π}{2} (x + 2y)

is negative in the region x ∈ (0.318, 0.334), y ∈ (0.23, 0.25), a contradiction again. □

Set

A_{1}^{+} := A ∩ [m/2, ℓ − m + 1]_{p} ,  A_{2}^{+} := A ∩ [m, p/4)_{p} ,
A_{1}^{−} := A ∩ [−(ℓ − m + 1), −m/2]_{p} , A_{2}^{−} := A ∩ (−p/4, −m]_{p} ,

and

A_{1} := A_{1}^{+} ∪ A_{1}^{−} ,  A_{2} := A_{2}^{+} ∪ A_{2}^{−},

so that

A ∩ [0, p/4)_{p} = A_{1}^{+} ∪ A_{2}^{+} and A ∩ (−p/4, 0]_{p} = A_{1}^{−} ∪ A_{2}^{−}  (17)

by Lemma 4 (applied with k = 1) and Claim 3; observe also that m/2 ≤ ℓ − m + 1 by (13), and that A_{2} = ∅ if m > 0.25p. For definiteness, we assume for the rest of the proof that

|A_{1}^{+}| ≥ |A_{1}^{−}|,  (18)

and hence A_{1}^{+} ≠ ∅: otherwise, by (7) and the definitions of A_{2}^{+} and A_{2}^{−}, we would have

n − m ≤ |A_{2}| ≤ max{0, (p + 3)/2 − 2m},

leading to either m = n (in which case we are done by Lemma 7), or n + m < (p + 3)/2 (which contradicts (8)).

Given two subsets S_{1} and S_{2} of an additively written semigroup, we write

S_{1} + S_{2} := {s_{1} + s_{2} : s_{1} ∈ S_{1}, s_{2} ∈ S_{2}}.

It is well-known and easy to prove that if S_{1} and S_{2} are finite non-empty sets of integers, then |S_{1} + S_{2}| ≥ |S_{1}| + |S_{2}| − 1 holds (see, for example, [N96, Theorem 1.2]). Clearly, this inequality remains valid also if S_{1} and S_{2} are non-empty subsets of ℤ/pℤ, contained in two intervals of total length smaller than p.

Our next claim refines estimate (12).

Claim 4. We have

ℓ ≤ p − n − m − 2|A_{2}| + 2.

Proof. The assertion follows from the fact that the sets A and

A_{2}^{+} + A_{2}^{+} ⊆ [2m, p/2)_{p} , A_{2}^{−} + A_{2}^{−} ⊆ (p/2, p − 2m]_{p} , A_{0} − A_{0} ⊆ [−ℓ, ℓ]_{p}

are pairwise disjoint, estimate (11), and the observation that |A_{2}^{+} + A_{2}^{+}| ≥ 2|A_{2}^{+}| − 1 and |A_{2}^{−} + A_{2}^{−}| ≥ 2|A_{2}^{−}| − 1. □

Write I := [−(2m − ℓ − 2), 2m − ℓ − 2]_{p} and J := 2 ∗ A_{1}^{+} + I. We observe that

J ∩ A = (−J) ∩ A = ∅  (19)

by Lemma 6 (which is applicable since A_{1}^{+} ⊆ [m/2, ℓ − m + 1]_{p} ⊆ [ℓ/4, ℓ/2]_{p}, as it follows from (10)). Let k := |A_{1}^{+}|, write A_{1}^{+} = {a_{1}, …, a_{k}}, where the elements are so numbered that their inverse images in [m/2, ℓ − m + 1] under φ_{p} form an increasing sequence, and

12 JEAN-MARC DESHOUILLERS AND VSEVOLOD F. LEV

for i ∈ [1, k], set S_{i} := 2 ∗ {a_{1}, …, a_{i}} + I. We have then S_{1} = |I| = 4m − 2ℓ − 3 and |S_{i+1} \ S_{i}| ≥ 2 for i ∈ [1, k − 1], and it follows that

|J| = |S_{k}| ≥ (4m − 2ℓ − 3) + 2(k − 1) = 2|A_{1}^{+}| + 4m − 2ℓ − 5.  (20)

We are now in a position to complete the proof showing that the above-made assumptions (see the remark following (13)) lead to a contradiction. We consider separately two cases: m < 0.244p and m > 0.244p.

Case I: m < 0.244p. We revisit the proof of Claim 3, defining μ by (4) and observing that (16) gives

μ > \frac{1}{π} arccos (1.049 sin 2π(\frac{2m}{p} − 0.318))p.  (21)

This estimate is stronger than μ ≥ m/2 for small values of m, and in particular for m < 0.244p. A routine investigation (values at the endpoints and convexity) shows that (21) yields

μ > 1.348p − 5m; m ∈ [0.238p, 0.244p].  (22)

Since A_{1}^{+} ⊆ [μ, ℓ − m + 1]_{p}, we have

J ⊆ [ℓ − 2m + 2μ + 2, ℓ]_{p}.

Hence, (19) and (20) give

|[ℓ − 2m + 2μ + 2, ℓ]_{p} \ A| ≥ 2|A_{1}^{+}| + 4m − 2ℓ − 5,

and similarly, (20), (18), and (19) give

|[−ℓ, −(ℓ − 2m + 2μ + 2)]_{p} \ A| ≥ 2|A_{1}^{+}| + 4m − 2ℓ − 5
≥ 2|A_{1}^{−}| + 4m − 2ℓ − 5.

Adding up these estimates, we obtain

|[ℓ − 2m + 2μ + 2, p − (ℓ − 2m + 2μ + 2)]_{p} \ A| ≥ 2|A_{1}| + 8m − 4ℓ − 10,

and it follows that

|[ℓ − 2m + 2μ + 2, p − (ℓ − 2m + 2μ + 2)]_{p} ∩ A| ≤ p − 2|A_{1}| + 2ℓ − 4m − 4μ + 7. (23)

Assume for a moment that

ℓ − 2m + 2μ + 1 < 0.25p,  (24)

and hence

|[−(ℓ − 2m + 2μ + 1), ℓ − 2m + 2μ + 1]_{p} ∩ A| ≤ |A_{1}| + |A_{2}|

holds. Taking the sum of the last inequality and (23), using the estimate of Claim 4, and observing that |A_{1}| + |A_{2}| ≥ n − m by (7), we get

n ≤ p − |A_{1}| + |A_{2}| + 2ℓ − 4m − 4μ + 7
≤ 3p − |A_{1}| − |A_{2}| − 2n − 6m − 4μ + 11
≤ 3p − 3n − 5m − 4μ + 11.

Substituting (22), we obtain

n ≤ 3p − 3n − 5m − 5.392p + 20m + 11,

which leads to

2.392p ≤ 15m − 4n + 11 ≤ (15 · 0.244 − 4 · 0.318)p + 11 = 2.388p + 11,

a contradiction.

Thus (24) does not hold; that is,

ℓ − 2m + 2μ + 1 > 0.25p.  (25)

By (17), we have

|A ∩ (−0.25p, 0.25p)_{p}| = |A_{1}| + |A_{2}|.  (26)

By (25), the set J is included in [0.25p, ℓ]_{p}, and, in view of (19) and (20), we have

|A ∩ ([0.25p, ℓ]_{p} ∪ [p − ℓ, 0.75p]_{p})| ≤ 2ℓ − 0.5p − 4|A_{1}^{+}| − 8m + 4ℓ + 12.  (27)

Furthermore, since A is sum-free, we have (A_{2} + A_{2}) ∩ A = ∅, which implies ((A_{2}^{+} + A_{2}^{+}) ∪ (A_{2}^{−} + A_{2}^{−})) ∩ A = ∅. Since (A_{2}^{+} + A_{2}^{+}) ∪ (A_{2}^{−} + A_{2}^{−}) is included in (ℓ, p − ℓ)_{p}, the above-mentioned lower bound for the sum of two subsets of ℤ/pℤ leads to

|A ∩ (ℓ, p − ℓ)_{p})| ≤ p − 2ℓ − 2|A_{2}| + 1.  (28)

We now put together (26), (27), and (28) and recall (7), (18) and (12) to get

n ≤ |A_{1}| + |A_{2}| + 6ℓ − 0.5p − 4|A_{1}^{+}| − 8m + p − 2ℓ − 2|A_{2}| + 13
≤ 4ℓ + 0.5p − 8m − (|A_{1}| + |A_{2}|) + 13
≤ 4.5p − 12m − 4n − (n − m) + 13,

whence

4.5p ≥ 6n + 11m − 13 > (6 · 0.318 + 11 · 0.238)p − 13 > 4.526p − 13,

a contradiction settling Case I.

Case II: m > 0.244p. Recalling (18) we get

|A_{1}^{+}| ≥ \frac{1}{2} |A_{1}| = \frac{1}{2} (|(−p/4, p/4)_{p} ∩ A| − |A_{2}|) ≥ \frac{1}{2} (n − m − |A_{2}|)  (29)

by (7) and the definitions of A_{1} and A_{2}. We also observe that

|A_{1}^{+}| ≤ (ℓ − m + 1) − m/2 + 1

≤ p − n − \frac{5}{2} m + 2

= (n − m) − (2n + \frac{3}{2} m − p) + 2

< (n − m) − (2 · 0.318 + 1.5 · 0.244 − 1)p + 2

< n − m  (30)

by (12).

Using Claim 4, we derive from (29) that

|[m/2, ℓ − m + 1]_{p} \ A_{1}^{+}| ≤ (ℓ − \frac{3}{2} m + 2) − \frac{1}{2} (n − m − |A_{2}|)

= ℓ − m − \frac{1}{2} n + \frac{1}{2} |A_{2}| + 2

= 2(2m − ℓ − 2) + 3ℓ − 5m − \frac{1}{2} n + \frac{1}{2} |A_{2}| + 6

≤ 2(2m − ℓ − 2) + 3p − 8m − \frac{7}{2} n + 12

< 2(2m − ℓ − 2) − (8 · 0.244 + 3.5 · 0.318 − 3)p + 12 < 2(2m − ℓ − 2) + 1,

and it follows that the set J is an interval in ℤ/pℤ. By (7), Claim 3, the definition of A_{1}^{+}, Lemma 4 (with k = 1), and (19), we have

n − m ≤ |(−m/2, (p − m)/2)_{p} ∩ A|
= |A_{1}^{+}| + |[m, (p − m)/2)_{p} ∩ A|
≤ |A_{1}^{+}| + |[m, (p − m)/2)_{p} \ J|.  (31)

Since J ⊆ [ℓ−m+2, ℓ]_{p} (as is immediate from the definitions of J and A_{1}^{+}) is an interval, we have

|[m, (p − m)/2)_{p} \ J| ≤ max{|[m, (p − m)/2)_{p} \ J_{1}|, |[m, (p − m)/2)_{p} \ J_{2}|},

where

J_{1} := [ℓ − m + 2, ℓ − m + |J| + 1]_{p} and J_{2} := [ℓ + 1 − |J|, ℓ]_{p}

A REFINED BOUND FOR SUM-FREE SETS IN GROUPS OF PRIME ORDER 15

(so that J_{1} and J_{2} are subintervals of the interval [ℓ − m + 2, ℓ]_{p} with |J_{1}| = |J_{2}| = |J|, adjacent to the endpoints of this interval). Accordingly, from (31) we deduce that

|[m, (p − m)/2)_{p} \ J_{i}| ≥ n − m − |A_{1}^{+}|  (32)

holds true, with either i = 1 or i = 2.

By (30), assuming that (32) holds with i = 1, we obtain

n − m − |A_{1}^{+}| ≤ (p − m)/2 − (ℓ − m + |J| + 1) + 1.

Using (20), (29), and Claim 4, we now get

|A_{1}^{+}| + 4m − 2ℓ − 5 ≤ |J| − |A_{1}^{+}| ≤ 0.5p + \frac{3}{2} m − n − ℓ,

|A_{1}^{+}| ≤ 0.5p − \frac{5}{2} m − n + ℓ + 5 ≤ 1.5p − \frac{7}{2} m − 2n − 2|A_{2}| + 7,

\frac{5}{2} n + 3m ≤ 1.5p + 7,

which is wrong since

\frac{5}{2} n + 3m > (2.5 · 0.318 + 3 · 0.238)p = 1.509p.

Assume now that (32) holds with i = 2. Since

\frac{1}{2} (n − m − |A_{2}|) ≤ |A_{1}^{+}| ≤ ℓ − \frac{3}{2} m + 2

by (29) and the definition of A_{1}^{+}, we have

ℓ ≥ \frac{1}{2} n + m − \frac{1}{2} |A_{2}| − 2 = \frac{1}{2} (p − m) + \frac{1}{2} (n + 3m − p − |A_{2}|) − 2 > \frac{1}{2} (p − m),

as |A_{2}| ≤ max{0, 0.5p − 2m + 2} and

n + 3m > (0.318 + 3 · 0.238)p = 1.032p,
n + 5m > (0.318 + 5 · 0.238)p = 1.508p.

Similar to the above, we now obtain from (32) and (30)

n − m − |A_{1}^{+}| ≤ (ℓ + 1 − |J|) − m + 1

and, using (20), (29), and Claim 4, derive that

|A_{1}^{+}| + 4m − 2ℓ − 5 ≤ |J| − |A_{1}^{+}| ≤ ℓ − n + 2,

|A_{1}^{+}| ≤ 3ℓ − 4m − n + 7 ≤ 3p − 7m − 4n − 6|A_{2}| + 13,

3p + 13 ≥ \frac{9}{2} n + \frac{13}{2} m > (4.5 · 0.318 + 6.5 · 0.244)p = 3.017p,

a contradiction, as wanted.

Acknowledgements

The authors are grateful to Dr. K. Srinivas for helpful discussions, to Prof. R. Balasubramanian and the referee for pointing out an inaccuracy in the first version of this paper, to the referee for his very careful reading of the manuscript and remarks, and to Olof Sisask and Alex Dianiak for communicating to us their examples of sum-free sets, mentioned in the Introduction.

References

[DF06] J.-M. Deshouillers and G. A. Freiman, On sum-free sets modulo p, Functiones et Approximatio XXXV (2006), 7–15.

[F62] G. A. Freiman, Inverse problems in additive number theory, VI. On the addition of finite sets, III. Izv. Vyss. Ucebn. Zaved. Matematika 3 (28) (1962), 151–157 (in Russian).

[L06a] V.F. Lev, Distribution of points on arcs, Integers 5 (2) (2005), A11, 6 pp. (electronic).

[L06b] , Large sum-free sets in ℤ/pℤ, Israel Journal of Math. 154 (2006), 221–234.

[L] , On sum-free subsets of the torus group, Functiones et Approximatio, 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.

[N96] M.N. Nathanson, Additive Number Theory (Inverse Problems and the Geometry of Sumsets), Graduate texts in Mathematics 165, Springer (1996).

  E-mail address: jean-marc.deshouillers@math.u-bordeaux1.fr

Institut Mathématique de Bordeaux, UMR 5251, Universités Bordeaux 1 et 2 et CNRS, 33405 Talence, France.

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

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