New York Journal of Mathematics

New York J. Math. 13 (2007) 97–106.

Measures of sum-free intersecting families

Neil Hindman and Henry Jordan

Abstract. Let α be the supremum of all δ such that there is a sequence ⟨A_{n}⟩_{n=1}^{∞} of measurable subsets of (0, 1) with the property that each A_{n} has measure at least δ and for all n, m ∈ ℕ, A_{n} ∩ A_{m} ∩ A_{n+m} = ∅. For k ∈ ℕ, let α_{k} be the corresponding supremum for finite sequences ⟨A_{n}⟩_{n=1}^{k}. We show that α = lim_{k→∞} α_{k} and find the exact value of α_{k} for k ≤ 41. In the process of finding these exact values, we also determine exactly the number of maximal sum free subsets of {1, 2, …, k} for k ≤ 41. We also investigate the size of sets ⟨A_{x}⟩_{x∈S} with A_{x} ∩ A_{y} ∩ A_{x+y} = ∅ where S is a subsemigroup of ((0, ∞), +).

Contents

1. Introduction 97 2. Computing α_{k} and maximal sum free sets 98 3. Proof of Theorem 1.2 101 4. Larger semigroups 105 References 106

1. Introduction

Recall that Schur’s Theorem [5] says that whenever the set ℕ of positive integers is partitioned into finitely many cells, one of these must contain n, m, and n + m for some n and m. And van der Waerden’s Theorem [8] says that whenever ℕ is partitioned into finitely many cells, one of these contains arbitrarily long arithmetic progressions. And Szemerédi’s Theorem [7] says that in fact any set with positive upper density contains arbitrarily long arithmetic progressions.

In his mathematical youth, when he was a student of Furstenberg (who had provided an ergodic theoretic proof [3] of Szemerédi’s Theorem) Vitaly Bergelson was thinking of possible density versions of Schur’s Theorem. Of course, the obvious density version is false because the set of odd integers has density \frac{1}{2}. However, he was able to establish a strong density statement which does have Schur’s Theorem

97^{ISSN 1076-9803/07}

Received September 8, 2006.

Mathematics Subject Classification. Primary 28A12; Secondary 05A15, 11B75, 05D10.

Key words and phrases. Sum-free, maximal sum-free, intersecting families.

The first author acknowledges support recieved from the National Science Foundation via Grant DMS-0554803.

as a corollary, namely that whenever ℕ is finitely partitioned, there is one cell C of the partition such that d({n ∈ C : d(C ∩ (C − n)) > 0}) > 0, where d is upper asymptotic density. (The statement of [1, Theorem 1.1] is actually stronger than this.)

At about the same time, Bergelson thought it would be nice if one could show that whenever ⟨A_{n}⟩_{n=1}^{∞} is a sequence of measurable subsets of (0, 1) each with positive measure, there would have to exist some m and n such that the measure of A_{n} ∩ A_{m} ∩ A_{n+m} is positive. Unfortunately, as he quickly noticed, this is easily seen to be false. In fact, if for each n ∈ ℕ one lets

A_{n} = \{x ∈ (0, 1) : ⌊nx⌋ + \frac{1}{3} < nx < ⌊nx⌋ + \frac{2}{3}\} ,

then for all n, m ∈ ℕ, A_{n} ∩A_{m} ∩A_{n+m} = ∅. Further, these sets are all quite simple, each being the finite union of open intervals.

This curious fact, called to the attention of the authors in conversation with Bergelson, is the starting point of this paper. One naturally wants to know whether measure \frac{1}{3} is as good as one can do. That is, if α is as defined below, is α = \frac{1}{3}? We write μ(A) for the Lebesgue measure of a subset of (0, 1).

Definition 1.1.

(a) α = sup{δ: there exists a sequence ⟨A_{n}⟩_{n=1}^{∞} of measurable subsets of (0, 1) such that for each n ∈ ℕ, μ(A_{n}) ≥ δ and for all n, m ∈ ℕ, A_{n} ∩A_{m} ∩A_{n+m} = ∅}.

(b) Let k ∈ ℕ. Then α_{k} = sup{δ: there exists a sequence ⟨A_{n}⟩_{n=1}^{k} of measurable subsets of (0, 1) such that for each n ∈ {1, 2, …, k}, μ(A_{n}) ≥ δ and for all n, m ∈ {1, 2, …, k}, if n + m ≤ k, then A_{n} ∩ A_{m} ∩ A_{n+m} = ∅}.

One of course has trivially that for each k ∈ ℕ, α_{k} ≥ α_{k+1} ≥ α. We in fact hoped that we could find some reasonably small k for which α_{k} = \frac{1}{3}. This turns out not to be the case (assuming that “reasonably small” means some number less than 42). We do however have the following theorem. Note that in particular, it tells us that the supremum in Definition 1.1 is obtained, and in a reasonably simple fashion.

Theorem 1.2. α = lim_{k→∞} α_{k}. There exist ⟨B_{t}⟩_{t=1}^{∞} such that for each t ∈ ℕ, B_{t} is a

union of at most 2^{t−1} open intervals in (0, 1), for each t ∈ ℕ, μ(B_{t}) ≥ α, and for all n, m ∈ ℕ, B_{n} ∩ B_{m} ∩ B_{n+m} = ∅.

We shall prove Theorem 1.2 in Section 3. Section 2 is devoted to the computation of α_{k} for k ≤ 41. In Section 4 we consider the problem of finding ⟨A_{x}⟩_{x∈S} for other subsemigroups S of ((0, ∞), +) such that A_{x} ∩ A_{y} ∩ A_{x+y} = ∅ for all x, y ∈ S. We show for example that we can find ⟨A_{x}⟩_{x∈ℚ^{+}} with this property such that each μ(A_{x}) = \frac{1}{3}.

2. Computing α_{k} and maximal sum free sets

We see immediately that the problem of computing α_{k} is intimately related to finding all of the maximal sum free subsets of {1, 2, …, k}. It is a curiosity that while there is a substantial literature on sum free sets, as a quick search of MathSciNet will reveal, the only papers we have been able to find on maximal sum free subsets of {1, 2, …, k} are [4] and [2]. In particular, the number of maximal sum free subsets of {1, 2, …, k} was not on The online encylopedia of integer sequences [6] until we submitted it with this paper as a reference. The connection is given by Theorem 2.3. Before presenting this theorem we introduce some notation. Since we are dealing throughout this paper with subsets of (0, 1) we will adopt the convention that ⋂_{n∈∅} A_{n} = (0, 1). We denote the set of finite nonempty subsets of a set X by P_{f}(X).

Definition 2.1. Let H ∈ P_{f}(ℕ), let F ⊆ H, and let ⟨A_{n}⟩_{n∈H} be a sequence of subsets of (0, 1).

D(F, ⟨A_{n}⟩_{n∈H}) = ⋂_{t∈F} A_{t} \ ⋃_{t∈H\F} A_{t} .

If H = {1, 2, …, k} for some k ∈ ℕ, then we write D(F, ⟨A_{n}⟩_{n=1}^{k}) for D(F, ⟨A_{n}⟩_{n∈H}). Notice that D(F, ⟨A_{n}⟩_{n=1}^{k}) is that cell of the Venn diagram of ⟨A_{n}⟩_{n=1}^{k} determined by F. That is, given x ∈ (0, 1), x ∈ D(F, ⟨A_{n}⟩_{n=1}^{k}) if and only if

F = {n ∈ {1, 2, …, k} : x ∈ A_{n}} .

In particular, if D(F, ⟨A_{n}⟩_{n=1}^{k}) ∩ D(G, ⟨A_{n}⟩_{n=1}^{k}) ≠ ∅, then F = G.

Definition 2.2. Let k ∈ ℕ.

(a) F_{k} = {F ⊆ {1, 2, …, k}: there do not exist n and m such that {n, m, n + m} ⊆ F }.

(b) M_{k} is the set of maximal members of F_{k}.

The following theorem tells us that when calculating α_{k}, we need only be concerned with sequences ⟨A_{n}⟩_{n=1}^{k} for which the nonempty portions of the Venn diagram correspond to maximal sum free sets.

Theorem 2.3. Let k ∈ ℕ and let δ > 0. Assume that ⟨A_{n}⟩_{n=1}^{k} is a sequence of measurable subsets of (0, 1) such that for each n ∈ {1, 2, …, k}, μ(A_{n}) ≥ δ and whenever {n, m, n + m} ⊆ {1, 2, …, k} one has A_{n} ∩ A_{m} ∩ A_{n+m} = ∅. Then there exists a sequence ⟨B_{n}⟩_{n=1}^{k} of measurable subsets of (0, 1) such that for each n ∈ {1, 2, …, k}, μ(B_{n}) ≥ δ, whenever {n, m, n + m} ⊆ {1, 2, …, k} one has B_{n} ∩ B_{m} ∩ B_{n+m} = ∅, and for each F ⊆ {1, 2, …, k}, if D(F, ⟨B_{n}⟩_{n=1}^{k}) ≠ ∅, then F ∈ M_{k}.

Proof. For each F ∈ F_{k} pick H_{F} ∈ M_{k} such that F ⊆ H_{F}. For n ∈ {1, 2, …, k}, let B_{n} = ⋃{D(F, ⟨A_{t}⟩_{t=1}^{k}) : F ∈ F_{k} and n ∈ H_{F} }.

First we observe that for each n ∈ {1, 2, …, k}, A_{n} ⊆ B_{n}, so in particular μ(B_{n}) ≥ μ(A_{n}). To see this, let x ∈ A_{n} and let F = {t ∈ {1, 2, …, k} : x ∈ A_{t}}. Then x ∈ D(F, ⟨A_{t}⟩_{t=1}^{k}) and n ∈ F ⊆ H_{F} so x ∈ B_{n}.

Next assume that {n, m, n + m} ⊆ {1, 2, …, k} and suppose that we have x ∈ B_{n} ∩ B_{m} ∩ B_{n+m}. Pick F_{1}, F_{2}, and F_{3} in F_{k} such that n ∈ H_{F_{1}}, m ∈ H_{F_{2}}, n + m ∈ H_{F_{3}}, and x ∈ D(F_{1}, ⟨A_{t}⟩_{t=1}^{k}) ∩ D(F_{2}, ⟨A_{t}⟩_{t=1}^{k}) ∩ D(F_{3}, ⟨A_{t}⟩_{t=1}^{k}). But since this intersection is nonempty we have that F_{1} = F_{2} = F_{3} and so {n, m, n + m} ⊆ H_{F_{1}}, a contradiction.

Now let G ⊆ {1, 2, …, k} and assume that we have some x ∈ D(G, ⟨B_{n}⟩_{n=1}^{k}). Then G = {n ∈ {1, 2, …, k} : x ∈ B_{n}} so by what we have just seen, G ∈ F_{k}. Let F = {n ∈ {1, 2, …, k} : x ∈ A_{n}}. We claim that G = H_{F} for which it suffices to show that H_{F} ⊆ G. So let n ∈ H_{F}. Since x ∈ D(F, ⟨A_{t}⟩_{t=1}^{k}) we have that x ∈ B_{n} so n ∈ G. □

At this stage we pause to establish a result which does not require computer assistance.

Theorem 2.4. α_{5} = α_{6} = α_{7} = \frac{4}{9}.

Proof. Let

\begin{aligned}A_{1} & = (0, \frac{1}{3}) ∪ (\frac{8}{9}, 1) \\ A_{2} & = (\frac{1}{3}, \frac{7}{9}) \\ A_{3} & = (0, \frac{1}{9}) ∪ (\frac{1}{3}, \frac{5}{9}) ∪ (\frac{7}{9}, \frac{8}{9}) \\ A_{4} & = (\frac{1}{9}, \frac{1}{3}) ∪ (\frac{7}{9}, 1) \\ A_{5} & = (0, \frac{1}{9}) ∪ (\frac{5}{9}, \frac{8}{9}) \\ A_{6} & = (\frac{1}{9}, \frac{1}{3}) ∪ (\frac{5}{9}, \frac{7}{9}) \\ A_{7} & = (0, \frac{1}{9}) ∪ (\frac{1}{3}, \frac{5}{9}) ∪ (\frac{8}{9}, 1) . \end{aligned}

This assignment establishes that α_{7} ≥ \frac{4}{9}.

Now assume that we have A_{1}, A_{2}, A_{3}, A_{4}, and A_{5} with each μ(A_{n}) ≥ δ and A_{n} ∩ A_{m} ∩ A_{n+m} = ∅ whenever {n, m, n + m} ⊆ {1, 2, 3, 4, 5}. By Theorem 2.3 we may assume that D(F, ⟨A_{n}⟩_{n=1}^{5}) = ∅ whenever F ∉ M_{5}.

Note that M_{5} = {{1, 4}, {2, 3}, {2, 5}, {1, 3, 5}, {3, 4, 5}}. Let

\begin{aligned}x_{1} & = μ(D(\{1, 4\}, ⟨A_{n}⟩_{n=1}^{5})) , \\ x_{2} & = μ(D(\{2, 3\}, ⟨A_{n}⟩_{n=1}^{5})) , \\ x_{3} & = μ(D(\{2, 5\}, ⟨A_{n}⟩_{n=1}^{5})) , \\ x_{4} & = μ(D(\{1, 3, 5\}, ⟨A_{n}⟩_{n=1}^{5})), and \\ x_{5} & = μ(D(\{3, 4, 5\}, ⟨A_{n}⟩_{n=1}^{5})) . \end{aligned}

Then we have that

\begin{aligned}δ & ≤ μ(A_{1}) = x_{1} + x_{4} , \\ δ & ≤ μ(A_{2}) = x_{2} + x_{3} , \\ δ & ≤ μ(A_{3}) = x_{2} + x_{4} + x_{5} , \\ δ & ≤ μ(A_{4}) = x_{1} + x_{5}, and \\ δ & ≤ μ(A_{5}) = x_{3} + x_{4} + x_{5} . \end{aligned}

Therefore we have

1 ≥ x_{1} + x_{2} + x_{3} + x_{4} + x_{5}

= \frac{1}{2}(x_{1} + x_{4}) + \frac{3}{4}(x_{2} + x_{3}) + \frac{1}{4}(x_{2} + x_{4} + x_{5}) + \frac{1}{2}(x_{1} + x_{5}) + \frac{1}{4}(x_{3} + x_{4} + x_{5})

≥ \frac{1}{2}δ + \frac{3}{4}δ + \frac{1}{4}δ + \frac{1}{2}δ + \frac{1}{4}δ

= \frac{9}{4}δ

so δ ≤ \frac{4}{9}. □

We now show that evaluating α_{k} can be reduced to a linear programing problem. We also see that α_{k}, which is defined as a supremum, is actually obtained as a value.

Theorem 2.5. Let k ∈ ℕ and let ⟨H_{n}⟩_{n=1}^{m} enumerate M_{k}. For i ∈ {1, 2, …, k} let G_{i} = {n ∈ {1, 2, …, m} : i ∈ H_{n}}. Let d be the minimum value of ∑_{n=1}^{m} x_{n} subject to the constraints x_{n} ≥ 0 for each n ∈ {1, 2, …, m} and ∑_{n∈G_{i}} x_{n} ≥ 1 for each i ∈ \{1, 2, …, k\}. Then α_{k} = \frac{1}{d}. Further, there exist ⟨A_{t}⟩_{t=1}^{k} such that each A_{t} is a finite union of open intervals contained in (0, 1), μ(A_{t}) ≥ α_{k} for each t ∈ {1, 2, …, k}, and whenever {n, m, n+m} ⊆ {1, 2, …, k}, A_{n} ∩A_{m} ∩A_{n+m} = ∅.

Proof. We first show that α_{k} ≤ \frac{1}{d}. Suppose instead that α_{k} > \frac{1}{d} and pick γ such that α_{k} > γ > \frac{1}{d}. Pick ⟨A_{t}⟩_{t=1}^{k} such that each A_{t} is a measurable subset of (0, 1), μ(A_{t}) ≥ γ for each t ∈ {1, 2, …, k}, and whenever {n, m, n + m} ⊆ {1, 2, …, k}, A_{n} ∩ A_{m} ∩ A_{n+m} = ∅. By Theorem 2.3 we may presume that D(F, ⟨A_{t}⟩_{t=1}^{k}) = ∅ whenever F ⊆ {1, 2, …, k} and F ∉ M_{k}.

For each n ∈ \{1, 2, …, m\}, let x_{n} = \frac{1}{γ} · μ(D(H_{n}, ⟨A_{t}⟩_{t=1}^{k})). Then each x_{n} ≥ 0 and, given i ∈ {1, 2, …, k}, γ ≤ μ(A_{i}) = ∑_{n∈G_{i}} μ(D(H_{n}, ⟨A_{t}⟩_{t=1}^{k})) = ∑_{n∈G_{i}} γ·x_{n} so ∑_{n∈G_{i}} x_{n} ≥ 1. Also, ∑_{n=1}^{m} x_{n} = \frac{1}{γ} · ∑_{n=1}^{m} μ(D(H_{n}, ⟨A_{t}⟩_{t=1}^{k})) ≤ \frac{1}{γ}, so d ≤ \frac{1}{γ}, a contradiction.

Now we show that α_{k} ≥ \frac{1}{d} and simultaneously that the last sentence of the theorem is valid. Choose ⟨x_{n}⟩_{n=1}^{m} such that ∑_{n=1}^{m} x_{n} = d, ∑_{n∈G_{i}} x_{n} ≥ 1 for each i ∈ {1, 2, …, k}, and x_{n} ≥ 0 for each n ∈ {1, 2, …, m}.

Let a_{0} = 0 and for n ∈ \{1, 2, …, m\}, let a_{n} = \frac{1}{d} ·∑_{t=1}^{n} x_{t}, so that a_{n}−a_{n−1} = \frac{x_{n}}{d}. For i ∈ {1, 2, …, k}, let A_{t} = ⋃{(a_{n−1}, a_{n}) : t ∈ H_{n}}, so that D(H_{n}, ⟨A_{t}⟩_{t=1}^{k}) = (a_{n−1}, a_{n}) and if F ⊆ {1, 2, …, k} and F ∉ M_{k}, then D(F, ⟨A_{t}⟩_{t=1}^{k}) = ∅. Then for each t ∈ \{1, 2, …, k\}, μ(A_{t}) = ∑_{n∈G_{t}}(a_{n} − a_{n−1}) = ∑_{n∈G_{t}} \frac{x_{n}}{d} ≥ \frac{1}{d}. □

We computed α_{k} for 8 ≤ k ≤ 41 as follows. We ran a Pascal program which found all maximal sumfree subsets of {1, 2, …, k} and prepared a text file as input for the Mathematica LinearProgramming program. We took the Mathematica results and processed them with another Pascal program. We present the results in the Table 1. As we indicated earlier, the exact value of |M_{k}| is of independent interest so we record that count. Further it is known that ⌊\frac{k}{4} ⌋ ≤ log_{2}(|M_{k}|) ≤ \frac{k}{2} − 2^{−28}k. (The first inequality is from [2]. The second inequality is from [4], where it is said to hold for all sufficiently large k, though it almost certainly holds for all k.) For 5 ≤ k ≤ 41, \frac{log_{2}(|M_{k}|)}{k} varies from approximately .4644 to approximately .3974.

It is interesting to note that the sets ⟨A_{t}⟩_{t=1}^{k} obtained from the linear programing problem have a relatively small number of sets H ∈ M_{k} with D(H, ⟨A_{t}⟩_{t=1}^{k}) ≠ ∅. For example, |M_{41}| = 80256 and |{H ∈ M_{41} : D(H, ⟨A_{t}⟩_{t=1}^{k}) ≠ ∅}| = 39.

3. Proof of Theorem 1.2

As we have noted, it is trivial that α ≤ α_{k+1} ≤ α_{k} for each k ∈ ℕ. In this section we set out to show that α = lim_{k→∞} α_{k} and, furthermore, that α is actually achieved

in a quite simple fashion via sets ⟨A_{n}⟩_{n=1}^{∞} each with measure at least α and each consisting of a finite union of intervals.

Our approach is via assignments of weight to ⋂_{t∈F} A_{t} for each F ∈ P_{f}(ℕ). Recall that we are interpreting ⋂_{t∈∅} A_{t} as (0, 1).

Lemma 3.1. For all H ∈ P_{f}(ℕ), every sequence ⟨A_{t}⟩_{t∈H} of subsets of (0, 1), and all F ⊆ H,

μ(D(F, ⟨A_{t}⟩_{t∈H})) = ∑_{G⊆H\F} (−1)^{|G|} · μ(⋂_{t∈F ∪G} A_{t}) .

Table 1 ; \begin{aligned}k & α_{k} & |M_{k}| & k & α_{k} & |M_{k}| \\ 1 & 1 & 1 & 21 & \frac{3623}{9483} ≈ .38205 & 471 \\ 2 & \frac{1}{2} = .50000 & 2 & 22 & \frac{26393}{69755} ≈ .37837 & 598 \\ 3 & \frac{1}{2} = .50000 & 2 & 23 & \frac{26393}{69755} ≈ .37837 & 797 \\ 4 & \frac{1}{2} = .50000 & 4 & 24 & \frac{26393}{69755} ≈ .37837 & 1043 \\ 5 & \frac{4}{9} ≈ .44444 & 5 & 25 & \frac{3748414}{9981749} ≈ .37553 & 1378 \\ 6 & \frac{4}{9} ≈ .44444 & 6 & 26 & \frac{3517985}{9376079} ≈ .37521 & 1765 \\ 7 & \frac{4}{9} ≈ .44444 & 8 & 27 & \frac{3517985}{9376079} ≈ .37521 & 2311 \\ 8 & \frac{3}{7} ≈ .42857 & 13 & 28 & \frac{2130392}{5683115} ≈ .37486 & 3064 \\ 9 & \frac{3}{7} ≈ .42857 & 17 & 29 & \frac{115338484}{307691643} ≈ .37485 & 3970 \\ 10 & \frac{2}{5} = .40000 & 23 & 30 & \frac{6023718}{16172311} ≈ .37247 & 5017 \\ 11 & \frac{90}{227} ≈ .39648 & 29 & 31 & \frac{6023718}{16172311} ≈ .37247 & 6537 \\ 12 & \frac{90}{227} ≈ .39648 & 37 & 32 & \frac{69394069}{186601165} ≈ .37188 & 8547 \\ 13 & \frac{112}{283} ≈ .39576 & 51 & 33 & \frac{35492659}{95630427} ≈ .37114 & 11020 \\ 14 & \frac{453}{1150} ≈ .39391 & 66 & 34 & \frac{9351744259}{25226495604} ≈ .37071 & 14007 \\ 15 & \frac{453}{1150} ≈ .39391 & 86 & 35 & \frac{598841590}{1617567693} ≈ .37021 & 18026 \\ 16 & \frac{551}{1403} ≈ .39273 & 118 & 36 & \frac{598841590}{1617567693} ≈ .37021 & 23404 \\ 17 & \frac{203}{517} ≈ .39265 & 158 & 37 & \frac{598841590}{1617567693} ≈ .37021 & 30026 \\ 18 & \frac{435}{1108} ≈ .39260 & 201 & 38 & \frac{4962276726}{13411951105} ≈ .36999 & 37989 \\ 19 & \frac{435}{1108} ≈ .39260 & 265 & 39 & \frac{4962276726}{13411951105} ≈ .36999 & 48945 \\ 20 & \frac{3623}{9483} ≈ .38205 & 359 & 40 & \frac{428070802153}{1167464566698} ≈ .36667 & 62759 \\ & & & 41 & \frac{428070802153}{1167464566698} ≈ .36667 & 80256 \end{aligned}

Proof. We proceed by induction on |H \ F |. If F = H, then both sides are equal to μ(⋂_{t∈H} A_{t}). So assume that |H \ F | > 0 and the lemma is true for smaller values.

Pick k ∈ H \F. Then D(F, ⟨A_{t}⟩_{t∈H})∪D(F ∪{k}, ⟨A_{t}⟩_{t∈H}) = D(F, ⟨A_{t}⟩_{t∈H\{k}}) and D(F, ⟨A_{t}⟩_{t∈H}) ∩ D(F ∪ {k}, ⟨A_{t}⟩_{t∈H}) = ∅. So

\begin{aligned}μ(D(F, ⟨A_{t}⟩_{t∈H})) & = μ(D(F, ⟨A_{t}⟩_{t∈H\\{k\}})) − μ(D(F ∪ \{k\}, ⟨A_{t}⟩_{t∈H})) \\ & = ∑_{G⊆(H\\{k\})\F} (−1)^{|G|} · μ(⋂_{t∈F ∪G} A_{t}) \\ & − ∑_{G⊆H\(F ∪\{k\})} (−1)^{|G|} · μ(⋂_{t∈F ∪\{k\}∪G} A_{t}) \\ & = ∑_{G⊆(H\\{k\})\F} (−1)^{|G|} · μ(⋂_{t∈F ∪G} A_{t}) \\ & + ∑_{G∪\{k\}⊆H\F} (−1)^{|G|+1} · μ(⋂_{t∈F ∪(G∪\{k\})} A_{t}) \\ & = ∑_{G⊆H\F} (−1)^{|G|} · μ(⋂_{t∈F ∪G} A_{t}). \end{aligned}  □

We shall be interested in the following lemma in the case M = {1, 2, …, k} and t = k for some k ∈ ℕ. The more general version is needed for the proof.

Lemma 3.2. Let M ∈ P_{f}(ℕ) and let γ : P(M) → [0, 1]. For F ⊆ M define δ(M, F) = ∑_{G⊆M\F} (−1)^{|G|} · γ(F ∪ G).

(a) If F ⊊ M and t ∈ M \ F, then δ(M, F) + δ(M, F ∪ {t}) = δ(M \ {t}, F).

(b) If H ⊆ M, then ∑_{H⊆F ⊆M} δ(M, F) = γ(H).

Proof. (a) We have

δ(M, F) = ∑_{G⊆(M\{t})\F} (−1)^{|G|} · γ(F ∪ G)
+ ∑_{G⊆(M\{t})\F} (−1)^{|G|+1} · γ(F ∪ G ∪ {t})
= δ(M \ {t}, F) − ∑_{G⊆M\(F ∪{t})} (−1)^{|G|} · γ(F ∪ {t} ∪ G)
= δ(M \ {t}, F) − δ(M, F ∪ {t}) .

(b) We prove this statement by induction on |M \ H|. If H = M, this is the definition of δ(M, H), so assume that H ⊊ M, t ∈ M \ H, and ∑_{H⊆F ⊆M\{t}} δ(M \ {t}, H) = γ(H). Then

\begin{aligned}∑_{H⊆F ⊆M} δ(M, F) & = ∑_{H⊆F ⊆M\\{t\}} δ(M, F) + ∑_{H∪\{t\}⊆F ⊆M} δ(M, F) \\ & = ∑_{H⊆F ⊆M\\{t\}} (δ(M \ \{t\}, F) − δ(M, F ∪ \{t\})) \\ & + ∑_{H∪\{t\}⊆F ⊆M} δ(M, F) \\ & = ∑_{H⊆F ⊆M\\{t\}} δ(M \ \{t\}, F) \\ & = γ(H). \end{aligned}  □

In the following we write [ℕ]^{<ω} for the set of finite subsets of ℕ. Thus [ℕ]^{<ω} = P_{f}(ℕ) ∪ {∅}.

Lemma 3.3. Let γ : [ℕ]^{<ω} → [0, 1] and for k ∈ ℕ and F ⊆ {1, 2, …, k} let δ({1, 2, …, k}, F) = ∑_{G⊆{1,2,...,k}\F} (−1)^{|G|} · γ(F ∪ G). Assume that for all k ∈ ℕ and all F ⊆ {1, 2, …, k}, δ({1, 2, …, k}, F) ≥ 0. Then we can choose for each k ∈ ℕ and each F ⊆ {1, 2, …, k}, a(k, F) and b(k, F) in [0, 1] such that:

(a) a(1, ∅) = 0, b(1, ∅) = a(1, {1}) = δ({1}, ∅), and b(1, {1}) = δ({1}, ∅) + δ({1}, {1}) = γ(∅).

(b) For k ∈ ℕ and F ⊆ {1, 2, …, k}, b(k, F) = a(k, F) + δ({1, 2, …, k}, F).

(c) For k ∈ ℕ and F ⊆ {1, 2, …, k}, a(k + 1, F) = a(k, F), b(k + 1, F) =

a(k + 1, F ∪ {k + 1}), and b(k + 1, F ∪ {k + 1}) = b(k, F). If for each t ∈ ℕ, B_{t} = ⋃_{{t}⊆F ⊆{1,2,...,t}} (a(t, F), b(t, F)), then for each H ∈ P_{f}(ℕ) with max H = k, ⋂_{t∈H} B_{t} = ⋃_{H⊆F ⊆{1,2,...,k}} (a(k, F), b(k, F)) so μ(⋂_{t∈H} B_{t}) = γ(H).

Proof. To see that one can make the assignments as in (a), (b), and (c), observe that by Lemma 3.2(a), for any k ∈ ℕ and any F ⊆ {1, 2, …, k}, we have that

δ({1, 2, …, k + 1}, F) + δ({1, 2, …, k + 1}, F ∪ {k + 1}) = δ({1, 2, …, k}, F).

Next observe that if F, G ∈ P_{f}(ℕ), k = max F, l = max G, and l ≤ k, then:

(i) If k = l and F ≠ G, then (a(k, F), b(k, F)) ∩ (a(k, G), b(k, G)) = ∅.

(ii) If l < k and (a(k, F), b(k, F)) ∩ (a(l, G), b(l, G)) ≠ ∅, then

G = F ∩ {1, 2, …, l} and (a(k, F), b(k, F)) ⊆ (a(l, G), b(l, G)).

We show that ⋂_{t∈H} B_{t} = ⋃_{H⊆F ⊆{1,2,...,k}} (a(k, F), b(k, F)) for H ∈ P_{f}(ℕ) with max H = k by induction on |H|. If H = {k} this is the definition of B_{k}. So assume that |H| > 1, let L = H \ {k}, and let l = max L. Then

⋂_{t∈H} B_{t} = B_{k} ∩ ⋂_{t∈L} B_{t}

= ( ⋃_{{k}⊆F ⊆{1,2,...,k}} (a(k, F), b(k, F))) ∩ ( ⋃_{L⊆G⊆{1,2,...,l}} (a(l, G), b(l, G))) = ⋃_{H⊆F ⊆{1,2,...,k}} (a(k, F), b(k, F)).

To verify the last equality, notice that if {k} ⊆ F ⊆ {1, 2, …, k}, L ⊆ G ⊆ {1, 2, …, l}, and x ∈ (a(k, F), b(k, F)) ∩ (a(l, G), b(l, G)), then G = F ∩ {1, 2, …, l} so H ⊆ F. Also, if H ⊆ F ⊆ {1, 2, …, k} and G = F ∩ {1, 2, …, l}, then L ⊆ G.

Finally,

μ (⋂_{t∈H} B_{t}) = ∑_{H⊆F ⊆{1,2,...,k}} δ({1, 2, …, k}, F) = γ(H)

by Lemma 3.2(b). □

We now restate Theorem 1.2.

Theorem 3.4. α = lim_{k→∞} α_{k}. There exist ⟨B_{t}⟩_{t=1}^{∞} such that for each t ∈ ℕ, B_{t} is a

union of at most 2^{t−1} open intervals in (0, 1), for each t ∈ ℕ, μ(B_{t}) ≥ α, and for all n, m ∈ ℕ, B_{n} ∩ B_{m} ∩ B_{n+m} = ∅.

Proof. Since for each k ∈ ℕ, α_{k} ≥ α_{k+1} ≥ α, we have that η = lim_{k→∞} α_{k} exists and

η ≥ α. It thus suffices to show that there exist ⟨B_{t}⟩_{t=1}^{∞} such that for each t ∈ ℕ, B_{t} is a union of at most 2^{t−1} open intervals in (0, 1), for each t ∈ ℕ, μ(B_{t}) ≥ η, and for all n, m ∈ ℕ, B_{n} ∩ B_{m} ∩ B_{n+m} = ∅.

For each k ∈ ℕ, pick a sequence ⟨A_{k,t}⟩_{t=1}^{k} of measurable subsets of (0, 1) such that for each t ∈ {1, 2, …, k}, μ(A_{k,t}) ≥ α_{k} and for all n and m, if {n, m, n+m} ⊆ {1, 2, …, k}, then A_{k,n} ∩ A_{k,m} ∩ A_{k,n+m} = ∅. (By Theorem 2.5 this can be done.) If t > k, let A_{k,t} = ∅.

Since P_{f}(ℕ) is countable, we may choose an increasing sequence ⟨m(n)⟩_{n=1}^{∞} such that for each F ∈ P_{f}(ℕ), lim_{n→∞} μ(⋂_{t∈F} A_{m(n),t}) exists. For F ∈ P_{f}(ℕ) let γ(F) =

lim_{n→∞} μ(⋂_{t∈F} A_{m(n),t}). Since whenever m(n) ≥ t, μ(A_{m(n),t}) ≥ α_{m(n)} ≥ η, we have

that for each t, γ({t}) ≥ η.

As in Lemma 3.3 let for each k ∈ ℕ and each F ⊆ {1, 2, …, k},

δ({1, 2, …, k}, F) = ∑_{G⊆{1,2,...,k}\F} (−1)^{|G|} · γ(F ∪ G) .

Let k ∈ ℕ and let F ⊆ {1, 2, …, k}. We claim that δ({1, 2, …, k}, F) ≥ 0. Suppose instead that δ({1, 2, …, k}, F) < 0 and let ϵ = −δ({1, 2, …, k}, F). Let s = k − |F |. Pick n ∈ ℕ such that m(n) > k and for each G ⊆ {1, 2, …, k} \ F,

|μ(⋂_{t∈F ∪G} A_{m(n),t}) − γ(F ∪ G)| < \frac{ϵ}{2^{s}}. Then by Lemma 3.1

0 ≤ μ(D(F, ⟨A_{m(n),t}⟩_{t=1}^{k}))

= ∑_{G⊆{1,2,...,k}\F} (−1)^{|G|} · μ(⋂_{t∈F ∪G} A_{m(n),t})

< ∑_{G⊆\{1,2,...,k\}\F} ((−1)^{|G|} · γ(F ∪ G) + \frac{ϵ}{2^{s}} )

= δ({1, 2, …, k}, F) + ϵ

= 0 ,

a contradiction.

For k ∈ ℕ and F ⊆ {1, 2, …, k}, choose a(k, F), b(k, F), and B_{k} as in Lemma 3.3. Then given H ∈ P_{f}(ℕ), if k = max H, then μ(⋂_{t∈H} B_{t}) = γ(H). Then for each t ∈ ℕ, μ(B_{t}) = γ({t}) ≥ η. Now let r, s ∈ ℕ. If m(n) ≥ r + s, then ⋂_{t∈{r,s,r+s}} A_{m(n),t} = ∅ so γ({r, s, r + s}) = 0 and so μ( ⋂_{t∈{r,s,r+s}} B_{t}) = 0. Since each B_{t} is a finite union of open intervals, B_{r} ∩ B_{s} ∩ B_{r+s} = ∅. □

4. Larger semigroups

One can ask whether one can get ⟨A_{t}⟩_{t∈ℝ^{+}} with each A_{t} a relatively large measurable subset of (0, 1) such that for all t, r ∈ ℝ^{+}, A_{t} ∩ A_{r} ∩ A_{t+r} = ∅. We cannot answer this question. However, we shall see in Theorem 4.2 that one can find such sets for t ∈ ℚ^{+}. And we see now that we can come close for t ∈ ℝ^{+}.

Theorem 4.1. Let δ, ϵ > 0. Then there exist sets B_{t} for all t ∈ (δ, ∞) such that each B_{t} is a finite union of open intervals in (0, 1), B_{t} ∩ B_{r} ∩ B_{t+r} = ∅ whenever t, r ∈ (δ, ∞), and μ(B_{t}) > \frac{1}{3} − ϵ whenever t ∈ (δ, ∞).

Proof. For t ∈ (1, ∞), let A_{t} = \{x ∈ (0, 1) : ⌊tx⌋ + \frac{1}{3} < tx < ⌊tx⌋ + \frac{2}{3}\}. Then for all t, r ∈ (1, ∞), A_{t} ∩ A_{r} ∩ A_{t+r} = ∅. Also, if t ∈ (1, ∞) and k = ⌊t − \frac{2}{3}⌋, then

⋃_{s=0}^{k} \frac{1}{t}(s + \frac{1}{3}, s + \frac{2}{3}) ⊆ A_{t} ⊆ ⋃_{s=0}^{k+1} \frac{1}{t}(s + \frac{1}{3}, s + \frac{2}{3})

and so lim_{t→∞} μ(A_{t}) = \frac{1}{3}. Pick k such that for all t ≥ k, μ(A_{t}) > \frac{1}{3} − ϵ and for t ∈ (δ, ∞), let B_{t} = A_{kt/δ}. □

By restricting ourselves to a countable subsemigroup of (0, ∞), we see that we can replace both δ and ϵ by 0 in Theorem 4.1.

Theorem 4.2. There exist sets B_{t} for all t ∈ ℚ^{+} such that each B_{t} is a finite union of open intervals in (0, 1), B_{t} ∩ B_{r} ∩ B_{t+r} = ∅ whenever t, r ∈ ℚ^{+}, and μ(B_{t}) ≥ \frac{1}{3} whenever t ∈ ℚ^{+}.

Proof. Choose φ : ℕ⟶_{onto}^{1-1}ℚ^{+}. For each n ∈ ℕ, let δ(n) = min φ[{1, 2, …, n}]. Pick by Theorem 4.1 ⟨B_{n,t}⟩_{t∈(δ(n),∞)} such that for all t ∈ (δ(n), ∞), μ(B_{n,t}) > \frac{1}{3} − \frac{1}{n} and B_{n,t} ∩ B_{n,r} ∩ B_{n,t+r} = ∅ whenever t, r ∈ (δ(n), ∞). Choose an increasing sequence ⟨m(n)⟩_{n=1}^{∞} such that for each F ∈ P_{f}(ℕ), lim_{n→∞} μ(⋂_{t∈F} B_{m(n),φ(t)}) exists and let

γ(F) = lim_{n→∞} μ(⋂_{t∈F} B_{m(n),φ(t)}). Then for each t ∈ ℕ one has γ(\{t\}) ≥ \frac{1}{3}.

As in the proof of Theorem 1.2 we have that for each k ∈ ℕ and each F ⊆ {1, 2, …, k}, ∑_{G⊆{1,2,...,k}\F} (−1)^{|G|} · γ(F ∪ G) ≥ 0. Choose by Lemma 3.3 a sequence ⟨C_{t}⟩_{t=1}^{∞} such that each C_{t} is a finite union of open intervals in (0, 1) and for each F ∈ P_{f}(ℕ), μ(⋂_{t∈F} C_{t}) = γ(F). In particular, for each t ∈ ℕ, μ(C_{t}) ≥ \frac{1}{3}.

106 Neil Hindman and Henry Jordan

For t ∈ ℚ^{+}, let B_{t} = C_{φ^{−1}(t)}. To complete the proof, let t, r ∈ ℚ^{+}. Let F = {φ^{−1}(t), φ^{−1}(r), φ^{−1}(t + r)}. Then B_{t} ∩ B_{r} ∩ B_{t+r} = ⋂_{s∈F} C_{s}. Also, if m(n) ≥ max F, so that for all s ∈ F, φ(s) ≥ δ(m(n)),

⋂_{s∈F} B_{m(n),φ(s)} = B_{m(n),t} ∩ B_{m(n),r} ∩ B_{m(n),t+r} = ∅

and so γ(F) = 0. Therefore μ(⋂_{s∈F} C_{s}) = 0 so B_{t} ∩ B_{r} ∩ B_{t+r} = ∅. □

We cannot prove that the value \frac{1}{3} in Theorem 4.2 is best possible, but trivially this cannot be raised above α and we know α ≤ α_{41} ≈ .36667

References

[1] Bergelson, Vitaly. A density statement, generalizing Schur’s theorem. J. Comb. Theory (Series A) 43 (1986), 338–343. MR0867659 (87k:05014), Zbl 0607.10040.

[2] Cameron, Peter J.; Erdős, Paul. On the number of sets of integers with various properties. Number theory (Banff, AB, 1988), 61–79, de Gruyter, Berlin, 1990. MR1106651 (92g:11010), Zbl 0695.10048.

[3] Furstenberg, Harry. Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions. J. d’Analyse Math. 31 (1977), 204–256. MR0498471 (58 #16583), Zbl 0347.28016.

[4] Łuczak, Tomasz; Schoen, Tomasz. On the number of maximal sum-free sets. Proc. Amer. Math. Soc. 129 (2001), 2205–2207. MR1823901 (2002a:11015), Zbl 1056.11011.

[5] Schur, I. Über die Kongruenz x^{m} + y^{m} = z^{m} (mod p). Jahresbericht der Deutschen Math.- Verein. 25 (1916), 114–117. JFM 46.0193.02.

[6] Sloan, Neil J. A. The on-line encyclopedia of integer sequences.

http://www.research.att.com/˜ njas/sequences/.

[7] Szemerédi, Endre. On sets of integers containing no k elements in arithmetic progression. Acta. Arith. 27 (1975), 199–245. MR0369312 (51 #5547), Zbl 0303.10056.

[8] van der Waerden, B. L. Beweis einer Baudetschen Vermutung. Nieuw Arch. Wiskunde 19 (1927), 212–216. JFM 53.0073.12.

Department of Mathematics, Howard University, Washington, DC 20059 nhindman@aol.com http://members.aol.com/nhindman

henryjordan59@hotmail.com

This paper is available via http://nyjm.albany.edu/j/2007/13-6.html.