ON SUM-FREE SUBSETS OF THE TORUS GROUP

VSEVOLOD F. LEV

Dedicated with best wishes to Jean-Marc Deshouillers on the occasion of his 60th birthday

Abstract. Establishing the structure of dense sum-free subsets of the torus group ℝ/ℤ, we find an absolute constant α_{0} < 1/3 such that for any sum-free subset A ⊆ ℝ/ℤ with the inner measure μ(A) > α_{0} there exists an integer q ≥ 1 so that

A ⊆ ⋃_{j=0}^{q−1} [\frac{j + μ(A)}{q}, \frac{j + 1 − μ(A)}{q}] .

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 2A := {a′ + a′′: a′, a′′ ∈ A}. Introduced by Schur in 1916 (“the set of positive integers cannot be partitioned into finitely many sum-free subsets”), sum-free sets become now one of the central objects of study in additive combinatorics. We refer the reader to the papers in the References section and the pending citations for the history and overview of the subject area.

What is the largest possible size of a sum-free subset of a given finite abelian group? Having been studied for several decades, this problem was eventually given a complete solution by Green and Ruzsa in [GR05]. The next natural step is to classify sumfree subsets of the size, close to the largest possible; the ideology behind this problem is that small sum-free subsets can be sporadic and unstructured, while in order for a large subset to be sum-free it has to possess a rigid structure. As the classification depends heavily on the algebraic nature of the underlying group, this problem has been considered for a very limited number of groups only. In this connection we mention the papers [DT89] (elementary abelian 2-groups), [L05] (elementary abelian 3-groups), and [L06, DF06, DLS] (the group ℤ/pℤ of residues modulo a prime p). Particularly important in our present context are the last three papers, where the following result is established. Theorem 1.1 ([L06, DF06, DLS]). There exists an absolute constant α_{0} < 1/3 with the following property: if p is a sufficiently large prime and A ⊆ ℤ/pℤ is sum-free with n := |A| > α_{0}p, then there is d ∈ ℤ/pℤ such that A ⊆ {nd, (n + 1)d, …, (p − n)d}.

2000 Mathematics Subject Classification. Primary: 11P70; secondary: 11B75.

Key words and phrases. Sum-free sets.

As shown in [L06], Theorem 1.1 is essentially best possible of this sort, except for the value of the constant α_{0}. The result of [L06] establishes Theorem 1.1 with α_{0} = 0.33, and this was improved to α_{0} = 0.324 in [DF06] and further to α_{0} = 0.318 in [DLS].

In this paper we consider sum-free subsets of the torus group ℝ/ℤ. This infinite group is endowed with the Haar measure, so that the notion of “large” makes perfect sense. Let μ denote the inner measure, corresponding to the (normalized) Haar measure on ℝ/ℤ; thus, μ(ℝ/ℤ) = 1, and if A ⊆ ℝ/ℤ is open, then μ(A) can be interpreted as the Lebesgue measure of A.

By a result of Raikov [R39], for any A ⊆ ℝ/ℤ we have μ(2A) ≥ min{2μ(A), 1}. If A is sum-free, then A is disjoint with 2A, implying μ(A) + μ(2A) ≤ 1 and consequently μ(A) ≤ 1/3; this bound is sharp as it follows from the observation that the canonical image of the interval (1/3, 2/3) in ℝ/ℤ is sum-free. More generally, for v, w ∈ ℝ with v < w, denote by (v, w)_{𝕋} the image of the interval (v, w) under the canonical homomorphism ℝ → ℝ/ℤ. (Similar notation will be used for closed intervals.) For integer q ≥ 1 consider the set

A := ⋃_{j=0}^{q−1} (\frac{j + 1/3}{q}, \frac{j + 2/3}{q})_{𝕋} .

Then μ(A) = 1/3, and we claim that A is sum-free: for, if a_{1}, a_{2}, a_{3} ∈ A, then qa_{i} ∈ (1/3, 2/3)_{𝕋} for i ∈ [1, 3], whence qa_{1} + qa_{2} ≠ qa_{3} and therefore a_{1} + a_{2} ≠ a_{3}.

Our goal in this paper is to establish the structure of sum-free subsets A ⊆ ℝ/ℤ with μ(A) below 1/3 and show that this structure is close to that in the example just described.

Main Theorem. Suppose that α_{0} ∈ (2/7, 1/3) has the property, specified in Theorem 1.1. Then for any sum-free subset A ⊆ ℝ/ℤ with α := μ(A) > α_{0} there exists an integer q ≥ 1 such that

A ⊆ ⋃_{j=0}^{q−1} [\frac{j + α}{q}, \frac{j + 1 − α}{q}]_{𝕋} .

For brevity, we denote the union in the statement of the Main Theorem by C_{q}(α); observe, that this union is the complement in ℝ/ℤ of the Bohr neighborhood ⋃_{j=0}^{q−1} ((j − α)/q, (j + α)/q)_{𝕋} (corresponding to the character x ↦ exp(2πiqx)).

As it follows from the discussion above, the assertion of the Main Theorem holds true with α_{0} = 0.318, and it is worth pointing out that it becomes wrong for α_{0} < 0.2. To see this, fix α > 0 and consider the set A = (α/2, α)_{𝕋} ∪ (2α, (5/2)α)_{𝕋}. Since 2A = (α, 2α)_{𝕋} ∪ ((5/2)α, (7/2)α)_{𝕋} ∪ (4α, 5α)_{𝕋}, if α ≤ 2/9 (which is equivalent to 5α ≤ 1 + α/2), then A is sum-free. If, moreover, 2/11 < α < 1/5, then there is no integer q ≥ 1 such that A ⊆ C_{q}(α); for, assuming the opposite, we would have (1 − 2α)/q ≥ α/2, implying q ≤ 2/α − 4 < 7, and the remaining cases q = 1, …, 6 are not difficult to check “manually”. (We notice that if 1/5 ≤ α ≤ 2/9, then A is contained in C_{3}(α).)

We also mention, without going into detailed explanations, that the union in the statement of the Main Theorem is best possible of this sort. This follows, for instance, by considering the set ⋃_{j=0}^{q−1} ((j + α)/q, (j + 2α)/q)_{𝕋}: if q/(3q + 1) < α < 1/3, then this set is sum-free and not contained in any of the sets C_{s}(α + ε) with s ≥ 1 and ε > 0.

2. Proof of the Main Theorem

Given two subsets B and C of an additively written group, we write B − C := {b − c: b ∈ B, c ∈ C}.

We start with a somewhat technical auxiliary lemma.

Lemma 2.1. Let l and q be positive integers, and suppose that to every z ∈ ℤ/qℤ there corresponds an integer set A_{z} ⊆ [0, l]. Write n := q^{−1} ∑_{z∈ℤ/qℤ} |A_{z}|. If l < \frac{3}{2} n−1, then for any g ∈ ℤ/qℤ the union ⋃_{z∈ℤ/qℤ}(A_{z+g} − A_{z}) contains all integers from the interval (−n, n).

Proof. Clearly, it suffices to show that for any integer h ∈ [0, n) there exists z ∈ ℤ/qℤ such that h ∈ A_{z+g} − A_{z}; suppose, for the contradiction, that this is wrong.

For every z ∈ ℤ/qℤ the sets A_{z+g} and A_{z} + h are then disjoint subsets of the interval [0, l + h], whence |A_{z+g}| + |A_{z}| ≤ l + h + 1; averaging over all z, we obtain

2n ≤ l + h + 1  (1)

showing, in particular, that h > 0.

For integer u set Z^{(u)} := {z ∈ ℤ/qℤ: u ∈ A_{z}}. Since Z^{(u+h)} and Z^{(u)} + g are disjoint subsets of ℤ/qℤ, we have |Z^{(u+h)}| + |Z^{(u)}| ≤ q, which is equivalent to

∑_{z∈ℤ/qℤ}|A_{z} ∩ {u, u + h}| ≤ q.  (2)

For each j ∈ [0, h − 1] consider the arithmetic progression P_{h}(j) := {j, j + h, …, j + ⌊(l − j)/h⌋}, so that

[0, l] = ⋃_{j=0}^{h−1} P_{h}(j).  (3)

By (2), we have

∑_{z∈ℤ/qℤ}|A_{z} ∩ P_{h}(j)| ≤ ⌊\frac{|P_{h}(j)| + 1}{2}⌋ q = (1 + ⌊\frac{l − j}{2h} ⌋) q,

and taking into account (3) we conclude that

n ≤ h + ∑_{j=0}^{h−1} ⌊\frac{l − j}{2h} ⌋ .  (4)

Along with the assumption h < n, the last estimate implies that l ≥ 2h, and we set j_{0} := l − 2h. Observe, that by (1) we have

h ≥ 2n − l − 1 > \frac{1}{3} (l + 1)

and hence j_{0} < h−1 and furthermore, all the summands ⌊(l − j)/2h⌋ in the right-hand side of (4) equal to either 0, or 1. Moreover, the number of those summands, equal to 1, is j_{0} + 1, and using (1) we obtain

n ≤ h + (j_{0} + 1) = l − h + 1 ≤ 2l − 2n + 2.

Therefore 3n ≤ 2(l + 1), contradicting the assumptions of the lemma.

□

Corollary 2.2. Let q be a positive integer and let v and w be real numbers with v < w. Suppose that to every z ∈ ℤ/qℤ there corresponds an open set A_{z} ⊆ (v, w) of measure α_{z}, and write ν := q^{−1} ∑_{z∈ℤ/qℤ} α_{z}. If w − v < \frac{3}{2} ν, then for any g ∈ ℤ/qℤ we have

(−ν, ν) ⊆ ⋃_{z∈ℤ/qℤ}(A_{z+g} − A_{z}).

Proof. Normalizing the sets A_{z}, we can assume without loss of generality that v = 0 and w = 1, whence ν > \frac{2}{3}. Let p be a prime. For every z ∈ ℤ/qℤ set

A_{z}^{(p)} := \{u ∈ [0, p − 1]: (\frac{u}{p}, \frac{u+1}{p}) ⊆ A_{z}\} ,

so that |A_{z}^{(p)}| ≥ α_{z}p(1 + o(1)) and therefore

n^{(p)} := q^{−1} ∑_{z∈ℤ/qℤ}|A_{z}^{(p)}| ≥ νp(1 + o(1))

as p → ∞. From ν > \frac{2}{3} it follows now that p < \frac{3}{2} n^{(p)} for all sufficiently large p, and applying Lemma 2.1 with l = p − 1 we conclude that every integer from the interval (−n^{(p)}, n^{(p)}) is contained in ⋃_{z∈ℤ/qℤ}(A_{z+g}^{(p)} − A_{z}^{(p)}). Since for an integer u the inclusion

u ∈ A_{z+g}^{(p)} − A_{z}^{(p)} implies that (\frac{u−1}{p}, \frac{u+1}{p}) ⊆ A_{z+g} − A_{z}, we obtain

⋃_{z∈ℤ/qℤ}(A_{z+g} − A_{z}) ⊇ (\frac{−n^{(p)}}{p} , \frac{n^{(p)}}{p} ) ⊇ (−ν + o(1), ν + o(1)),

implying the result. □

Clearly, the assertion of Corollary 2.2 remains valid if in the statement of the corollary the sets A_{z} are open subsets of the torus group, and the intervals (v, w) and (−ν, ν) are replaced with (v, w)_{𝕋} and (−ν, ν)_{𝕋}, respectively.

We are eventually ready to prove the Main Theorem. Throughout the proof we use the following notation. Let m be a positive integer. For u ∈ ℤ/mℤ by \frac{u}{m} we denote the image of u under the group homomorphism ℤ/mℤ → ℝ/ℤ, defined by 1 ↦ \frac{1}{m}. For v, w ∈ ℝ with v < w by [v, w]_{m} we denote the image of the set [v, w] ∩ ℤ under the canonical homomorphism ℤ → ℤ/mℤ. Finally, for integer q ≥ 1 and a subset A of an abelian group we write q ∗ A := {qa: a ∈ A}.

Proof of the Main Theorem. As a first step, we prove the Main Theorem under the additional assumption that A is open.

Fix a prime p which will be assumed large enough (the o() and O()-notation will correspond to p → ∞) and set

A^{(p)} := \{u ∈ ℤ/pℤ: \frac{u}{p} ∈ A\} .

Since A ⊆ ℝ/ℤ is sum-free, so is A^{(p)} ⊆ ℤ/pℤ, and since A is open we have

n^{(p)} := |A^{(p)}| ≥ αp(1 + o(1)).  (5)

By Theorem 1.1 there exists an integer q^{(p)} ∈ [1, p/2) with

q^{(p)} ∗ A^{(p)} ⊆ [n^{(p)}, p − n^{(p)})]_{p}.  (6)

Fix v, w ∈ ℝ with v < w so that the interval (v, w)_{𝕋} is entirely contained in A. Corresponding to this interval is a block I^{(p)} of (w − v + o(1))p consecutive elements of ℤ/pℤ, contained in A^{(p)}. Now q^{(p)} ∗ I^{(p)} ⊆ [n^{(p)}, p − n^{(p)})]_{p} ⊆ (p/4, 3p/4)_{p} implies that q^{(p)} < p/(2(|I^{(p)}| − 1)) = O_{v,w}(1), so that there is an infinite sequence of primes p, sharing the same common value of q^{(p)}. In what follows we denote this common value by q and assume that p are so chosen that q^{(p)} = q.

Fix arbitrarily a ∈ A and find u^{(p)} ∈ ℤ/pℤ satisfying

a − \frac{u^{(p)}}{p} ∈ [−\frac{1}{2p}, \frac{1}{2p}]_{𝕋} .  (7)

If p is large enough, then we have u^{(p)} ∈ A^{(p)}, whence

q \frac{u^{(p)}}{p} ∈ (α + o(1), 1 − α + o(1))_{𝕋}

by (6) and (5). Along with (7) this yields qa ∈ (α+o(1), 1−α+o(1))_{𝕋}, and consequently qa ∈ [α, 1 − α]_{𝕋}.

We have shown that

q ∗ A ⊆ [α, 1 − α]_{𝕋},

and this is equivalent to A ⊆ C_{q}(α), as wanted.

To complete the proof we drop now the assumption that A is open and turn to the general case. Let I be an arbitrarily fixed open interval, contained in A. Fix ε > 0 and find an open subset B ⊆ A such that I ⊆ B and β := μ(B) > max{α_{0}, α − ε}. By the above, there is an integer q ≥ 1 with B ⊆ C_{q}(β), and we observe that then μ(I) ≤ (1−2β)/q, implying that q is bounded by a constant, depending only on I. Accordingly, there is a sequence of values of ε, converging to 0, so that the corresponding values of q are all equal to each other, and we assume below that ε is chosen to be an element of this sequence.

For z ∈ ℤ/qℤ let

B_{z} := (B − \frac{z}{q} ) ∩ (\frac{β}{q} , \frac{1 − β}{q} )_{𝕋} ,

so that B = ⋃_{z∈ℤ/qℤ} (\frac{z}{q} + B_{z}) and consequently,

B − B = ⋃_{g∈ℤ/qℤ}(\frac{g}{q} + ⋃_{z∈ℤ/pℤ}(B_{z+g} − B_{z})).

As

q^{−1} ∑_{z∈ℤ/qℤ}μ(B_{z}) = \frac{β}{q} > \frac{α − ε}{q} > \frac{2}{3} \frac{1 − 2(α − ε)}{q} > \frac{2}{3} \frac{1 − 2β}{q}

for sufficiently small ε (it is here that the assumption α_{0} > 2/7 is used), we can apply Corollary 2.2 and obtain that

B − B ⊇ ⋃_{g∈ℤ/qℤ}(\frac{g}{q} + (−\frac{β}{q} , \frac{β}{q} )_{𝕋}) .  (8)

Since A is sum-free and B ⊆ A, the sets A and B − B are disjoint, and hence (8) gives

A ⊆ ⋃_{g∈ℤ/qℤ}(\frac{g}{q} + [\frac{β}{q} , \frac{1 − β}{q} ]_{𝕋}) .

As β > α − ε and ε can be chosen arbitrarily small, this implies that indeed

A ⊆ ⋃_{g∈ℤ/qℤ}(\frac{g}{q} + [\frac{α}{q}, \frac{1 − α}{q}]_{𝕋}) = C_{q}(α),

completing the proof. □

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.

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

[DLS] J.-M. Deshouillers, V.F. Lev, and K. Srinivas, More on large sum-free subsets of primeorder groups, manuscript in preparation.

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

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

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

[R39] D. Raikov, On the addition of point-sets in the sense of Schnirelmann, Rec. Math. [Mat. Sbornik] 5 (47) (1939), 425–440.

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

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