A refinement of the Cameron-Erdős Conjecture

Introduction

What is the structure of a typical set of integers, of a given density, which avoids a certain arithmetic sub-structure? This fundamental question underlies much of Additive Combinatorics, and has been most extensively studied when the forbidden structure is a $k$-term arithmetic progression, see e.g. . General systems of linear equations have also been studied, beginning with Rado in 1933, and culminating in the recent advances of Green, Tao and Ziegler . The subject is extremely rich, and questions of this type have been attacked with tools from a wide variety of areas of mathematics, from Graph Theory to Number Theory, and from Ergodic Theory to Harmonic Analysis. See for an excellent introduction to the area.

In this paper we shall consider sum-free sets of integers, that is, sets of integers which contain no solution of the equation $x+y=z$. It is easy to see that the odd numbers and the set $\{\lfloor n/2\rfloor+1,\ldots,n\}$ are the largest such subsets of $[n]=\{1,\ldots,n\}$. Both of these sets have $\lceil n/2\rceil$ elements, and therefore there are at least $2^{\lceil n/2\rceil}$ sum-free sets in $[n]$. In 1990, Cameron and Erdős conjectured that this trivial lower bound is within a constant factor of the truth, that is, that the set $[n]$ contains only $O(2^{n/2})$ sum-free sets. Despite various attempts , their conjecture remained open for over ten years, until it was confirmed by Green and, independently, by Sapozhenko . We shall prove a natural generalization of the Cameron-Erdős Conjecture, by bounding the number of sum-free subsets of $[n]$ of size $m$, for all $1\leqslant m\leqslant\lceil n/2\rceil$. Moreover, we shall also give a quite precise structural description of almost all sum-free subsets of $[n]$ of size $m\geqslant C\sqrt{n\log n}$. Our proof uses a general bound on the number of independent sets of size $m$ in 3-uniform hypergraphs, proved in , which allows one to deduce asymptotic structural results in the sparse setting (in fact, for all $m\gg\sqrt{n}$) from stability results in the dense setting (see Theorem 2.1). The dense stability result we shall use (see Proposition 2.2) was proved by Green . The second main ingredient in the proofs of our main theorems will be some new bounds on the number of sets of integers with small sumset (see Theorems 1.3 and 1.4). Finally, we shall use Freiman’s $3k-4$ Theorem (see below) to count sets with an extremely small sumset.

For structural and enumerative results, such as our main theorem, results are known in only a few special cases. For example, Osthus, Prömel and Taraz proved that if $m\geqslant\big(\frac{\sqrt{3}}{4}+\varepsilon\big)n^{3/2}\sqrt{\log n}$, then almost all triangle-free graphs with $m$ edges are bipartite, and that the constant $\sqrt{3}/4$ is best possible. This result can be seen as a sparse version of the classical theorem of Erdős, Kleitman and Rothschild , which states that almost all triangle-free graphs are bipartite. In , the authors proved a sparse analogue of the result of Green and Ruzsa mentioned above, by showing that if $m\geqslant C(q)\sqrt{n\log n}$, then almost every sum-free $m$-subset An $m$-subset of a set $X$ is simply a subset of $X$ of size $m$. of $G$ is contained in some maximum-size sum-free set. We remark that there are only at most $|G|$ maximum-size sum-free subsets of such a group $G$, and that moreover they admit an elegant description.

In this paper we shall be interested in the corresponding question for the set $[n]$. As noted above, Cameron and Erdős conjectured, and Green and Sapozhenko proved, that there are only $O(2^{n/2})$ sum-free subsets of $[n]$. Our main result is the following ‘sparse analogue’ of this theorem.

If $m\geqslant\sqrt{n}$, then Theorem 1.1 is sharp up to the value of $C$, since in this case there is a constant $c>0$ such that there are at least $2^{cn/m}{n/2\choose m}$ sum-free $m$-subsets of $[n]$ (see Proposition 3.1). Note that if $m\leqslant\sqrt{n}$ then the result is trivial, since in this case our upper bound is greater than ${n\choose m}$. Since there are fewer than $2^{n/3}$ subsets of $[n]$ with at most $n/100$ elements, Theorem 1.1 easily implies the Cameron-Erdős Conjecture. However, Theorem 1.1 only implies that there are $O(2^{n/2})$ sum-free subsets of $[n]$, whereas Green and Sapozhenko proved that there are asymptotically $c(n)2^{n/2}$ such sets, where $c(n)$ takes two different constant values according to whether $n$ is even or odd. Since for us the parity of $n$ will not matter, we shall assume for simplicity throughout the paper that $n$ is even; the proof in the case $n$ is odd is identical.

We shall also prove the following structural description of a typical sum-free $m$-subset of $[n]$. Let $O_{n}$ denote the set of odd numbers in $[n]$.

where $S(I)=\{x\in I:x\leqslant n/2\}$, and $\omega(n)\to\infty$ arbitrarily slowly as $n\to\infty$.

We remark that the upper bounds on $|S(I)|$ and $k(I):=\sum_{a\in S(I)}(n/2-a)$ in Theorem 1.2 are sharp up to a constant factor (see Section 6). Indeed, we shall show that if $m=o(n)$, then almost all sum-free $m$-sets $I\subset[n]$ have $|S(I)|=\Omega(n/m)$ and $k(I)=\Omega(n^{3}/m^{3})$.

Our proof of Theorems 1.1 and 1.2 has two main components. The first is a bound on the number of independent $m$-sets in 3-uniform hypergraphs (see Theorem 2.1), which was proved in , and used there to determine the asymptotic number of sum-free $m$-subsets of a finite Abelian group $G$ such that $|G|$ has a prime factor $q\equiv 2\pmod{3}$, for every $m\geqslant C(q)\sqrt{n\log n}$. Using this theorem, together with a stability result from (which follows from a result of Lev, Łuczak and Schoen ) it will be straightforward to bound the number of sum-free $m$-sets which contain at least $\delta m$ even numbers, and at least $\delta m$ elements less than $n/2$.

The second component involves counting restricted integer partitions with small sumset. Recall that $p(k)$ denotes the number of integer partitions of $k$, so, for example, $p(3)=3$ since $3=2+1=1+1+1$. In 1918, Hardy and Ramanujan obtained an asymptotic formula for $p(k)$, proving that

Despite the enormous interest in such problems, very little seems to be known about the number of different sets with small sumset (see , for example). The following classical result, proved by Freiman in 1959, implies a bound for sets with so-called ‘doubling constant’ less than $3$.

Theorems 1.3 and 1.4 are sufficient for our purposes; however, we believe the following stronger bound to be true.

For every $\delta>0$, there exists $C>0$ such that the following holds. If $m\geqslant C\sqrt{N}$ and $m\geqslant C\log n$, then there are at most

sets $S\subset[n]$ with $|S|=m$ and $|S+S|\leqslant N$.

Since $|S+S|\leqslant N$ for every $m$-subset $S\subset[N/2]$, the conjecture (if true) is close to optimal. Note that the condition $m\geqslant C\log n$ implies that $n\leqslant 2^{m/C}$, and thus guarantees that the number of translates of a given set $S$ is negligible.

The rest of the paper is organised as follows. In Section 2, we shall recall the general structural theorem from and deduce from it a bound on the number of sum-free $m$-sets which contain at least $\delta m$ even numbers, and at least $\delta m$ elements less than $n/2$. In Section 3 we shall prove a lower bound on the number of sum-free $m$-subsets of $[n]$, and in Section 4 we shall use Janson’s inequality to bound the number of sum-free sets which contain at most $\delta m$ even numbers. In Section 5 we shall prove Theorems 1.3 and 1.4. Finally, in Section 6, we shall prove Theorems 1.1 and 1.2.

Preliminaries

In this section we shall recall some of the main tools we shall use in the proofs of Theorems 1.1 and 1.2, and deduce that almost all sum-free $m$-sets $I\subset[n]$ either contain at most $\delta m$ even elements, or satisfy $|I\setminus B|\leqslant\delta m$ for some interval $B$ of length $n/2$.

Roughly speaking, a sequence of hypergraphs $(\mathcal{H}_{n})$ is $(\alpha,\mathcal{B})$-stable if for every $A\subseteq V(\mathcal{H}_{n})$ such that $|A|$ is almost as large as the independence number for $\mathcal{H}_{n}$, the set $A$ is either very close to some ‘extremal’ set $B\in\mathcal{B}_{n}$, or it contains many (i.e., a positive fraction of all) edges of $\mathcal{H}_{n}$.

Finally, for each $T\subset V(\mathcal{H}_{n})$, let $d_{\mathcal{H}_{n}}(T)=\big|\big\{e\in\mathcal{H}_{n}\,:\,T\subset e\big\}\big|$ and define

Note that if $\mathcal{H}_{n}$ encodes Schur triples in $[n]$, then $\Delta_{2}(\mathcal{H}_{n})\leqslant 2$.

The following theorem, which was proved in , shows that if $\mathcal{H}$ is $(\alpha,\mathcal{B})$-stable and $m\gg\sqrt{n}$, then there are very few independent sets (i.e., sum-free sets) in $\mathcal{H}_{n}$ of size $m$ which are far from every set $B\in\mathcal{B}_{n}$.

for some $\varepsilon=\varepsilon(\mathcal{H},\delta)>0$.

In the next subsection, we shall use this theorem, together with a result of Green , to deduce an approximate version of Theorem 1.2.

2. Green’s stability theorem

where, as before, $O_{n}$ denotes the odd numbers in $[n]$.

For any $\gamma>0$, if $\beta=\beta(\gamma)>0$ is sufficiently small, then the following holds. If $A\subset[n]$ with $|A|\geqslant(1/2-\beta)n$, then either $A$ contains at least $\beta n^{2}$ Schur triples, or $|A\setminus B|\leqslant\gamma n$ for some $B\in\mathcal{B}_{n}$.

Using Theorem 2.1 and Proposition 2.2, we easily obtain the following corollary.

sum-free subsets $I\subset[n]$ of size $m$ such that $|I\setminus B|>\delta m$ for every $B\in\mathcal{B}_{n}$.

In particular, for almost every sum-free set $I\subset[n]$ of size $m$, either $|I\setminus O_{n}|\leqslant\delta m$, or $|I\setminus B|\leqslant\delta m$ for some interval $B$ of length $n/2$.

Now, by Theorem 2.1, if $C=C(\delta)>0$ is sufficiently large, and $m\geqslant C\sqrt{n}$, then

for some $\varepsilon=\varepsilon(\delta)>0$. Since there are at least ${n/2\choose m}$ sum-free $m$-subsets of $[n]$, it follows that for almost every such set $I$ we have $|I\setminus B|\leqslant\delta n$ for some $B\in\mathcal{B}_{n}$, as required. ∎

We remark that it will be relatively straightforward to count the sets $I$ that contain fewer than $\delta m$ even elements, using Janson’s inequality (see Section 4), and those that contain more than $\delta m$ elements less than $n/2$, using induction on $n$ (see Section 6). Thus, Proposition 2.3 essentially reduces the problem of counting sum-free $m$-sets in $[n]$ to counting the sum-free sets that are almost contained in the interval $\{n/2+1,\ldots,n\}$.

3. Binomial coefficient inequalities

We shall make frequent use of some simple inequalities involving binomial coefficients; for convenience, we collect them here. Note first that ${a\choose b}\leqslant\big(\frac{ea}{b}\big)^{b}$ and that ${a\choose b}$ is increasing in $a$. Next, observe that if $a>b>c\geqslant 0$, then

We shall also use several times the observation that

where $\Gamma(\cdot)$ is Euler’s Gamma function, for some $C>c>0$ and every $a\geqslant 1$ and $b>0$.

For other standard probabilistic bounds, such as the FKG inequality and Chernoff’s inequality, we refer the reader to .

A lower bound on the number of sum-free sets

In this section we shall prove the following simple proposition, which shows that the bound in Theorem 1.1 is tight.

If $m\geqslant\sqrt{n}$, then there are $2^{\Omega(n/m)}{n/2\choose m}$ sum-free subsets of $[n]$ of size $m$.

Let $c>0$ be a sufficiently small absolute constant and set $a=cn^{2}/m^{2}$. We claim that if $S$ is a uniformly chosen random $m$-subset of $U=\{n/2-a,\ldots,n\}$, then

First observe that there are at most $a^{2}+a$ triples $\{x,y,z\}$ in $U$ with $x+y=z$, and at most $a+1$ pairs $\{x,y\}$ in $U$ with $2x=y$. Thus, by the FKG inequality,

since $c>0$ is sufficiently small, by our choices of $a$ and $p$. Next, note that, by Chernoff’s inequality,

which proves (5). Hence the number of sum-free $m$-sets in $\{n/2-a,\ldots,n\}$ is at least

where the inequality follows from (2) and the fact that $\big(1+\frac{2a}{n}\big)\geqslant e^{a/n}$. ∎

Janson argument

In this section, we shall count the sum-free sets that have few even elements. Recall that $O_{n}$ denotes the odd numbers in $[n]$.

We remark that an argument similar to the one presented in this section was used in in a somewhat more general context, see also . Indeed, the following result was proved in .

There exists constants $\delta>0$ and $C>0$ such that the following holds for every $m\geqslant C\sqrt{n\log n}$. There are at most

sum-free subsets $I\subset[n]$ with $|I|=m$ and $|I\setminus O_{n}|\leqslant\delta m$.

Proposition 4.2 clearly implies Proposition 4.1 in the case $m\geqslant C\sqrt{n\log n}$. Furthermore, the proposition is trivial if $m\leqslant O\big(\sqrt{n}\big)$, since then the claimed upper bound is greater than $\binom{n}{m}$. Thus, we need only consider the case $C\sqrt{n}\leqslant m\leqslant C\sqrt{n\log n}$.

Recall the following well-known result, which is an easy corollary of Janson’s inequality (see ), combined with Pittel’s inequality (see ). We refer the reader to [3, Section 5] for a proof.

Suppose that $\{U_{i}\}_{i\in J}$ is a family of subsets of an $n$-element set $X$ and let $m\in\{0,\ldots,n\}$. Let

where the second sum is over ordered pairs $(i,j)$ such that $i\neq j$ and $U_{i}\cap U_{j}\neq\emptyset$. Let $R$ be a uniformly chosen random $m$-subset of $X$. Then

We now turn to the proof of Proposition 4.1.

Let $C>0$ be a sufficiently large constant, and recall that we may assume that $C\sqrt{n}\leqslant m\leqslant C\sqrt{n\log n}$. We begin by proving the following claim.

For some constant $c>0$, there are at most

sum-free $m$-sets $I\subset[n]$ with $|I\setminus O_{n}|=k\leqslant\delta m$.

Let $k\leqslant\delta m$ and let $S$ be an arbitrary $k$-subset of $[n]\setminus O_{n}$. Let $\{U_{i}\}_{i\in J}$ be the collection of pairs $\{x,y\}\subset O_{n}$ such that either $x+y=z$ or $x-y=z$ for some $z\in S$. In order to bound the number of sum-free $m$-sets $I$ with $I\setminus O_{n}=S$, we shall apply the Hypergeometric Janson Inequality to the collection $\{U_{i}\}_{i\in J}$ and the set $X=O_{n}$, with $R$ a uniformly chosen random $(m-k)$-subset of $X$. Note that if $S\cup R$ is sum-free, then $U_{i}\nsubseteq R$ for all $i\in J$.

Let $\mu$ and $\Delta$ be the quantities defined in the statement of Lemma 4.3, and observe that for every even number $z$, there are either at least $n/10$ pairs $\{x,y\}\subset O_{n}$ with $x+y=z$ (if $z\geqslant n/2$), or at least $n/5$ such pairs with $x-y=z$ (if $z\leqslant n/2$). Thus $nk/20\leqslant|J|\leqslant nk$, since each pair can be counted at most twice. Observe that each vertex $x\in O_{n}$ lies in at most $2k$ of the $U_{i}$. Hence

By the Hypergeometric Janson Inequality, if $c=10^{-4}$ then there are at most

sets $R\subset O_{n}$ of size $m-k$ such that $S\cup R$ is sum-free. Summing over choices of $S$, we obtain the claimed bound. ∎

Now, by (2) and since $m\leqslant C\sqrt{n\log n}\leqslant n/6$, if $k\geqslant n/m$ then (6) is at most

assuming $\delta>0$ is sufficiently small. However, if $k\leqslant n/m$ then (6) is at most

To see the final inequality, observe that (since $xe^{-x/n}\leqslant n$) we have $me^{-cm^{2}/n}\leqslant n/cm$, and use the fact that $k\mapsto(a/k)^{k}$ is maximized when $k=a/e$. This completes the proof of Proposition 4.1.

Partitions and sumsets

In this section we shall prove Theorems 1.3 and 1.4. Recall that

To prove this, observe that there are $|S|\cdot|S+S|$ pairs $(a,b)$ with $a\in S$ and $b\in S+S$, and that if (8) holds then $a+y=b$ for at least $(1-\delta)|S|$ pairs $(a,b)\in S\times(S+S)$. For each pair $(a,b)$ there is at most one such $y$, and so there are at most $\frac{|S|\cdot|S+S|}{(1-\delta)|S|}$ elements $y$ which satisfy (8), as claimed.

and hence $\textup{span}(B_{j})\approx\textup{span}(S_{j})$. This would imply that $\min(S_{j})+B_{j}$ and $\max(S_{j})+B_{j}$ are (almost) disjoint, since

But now, if $B_{j}+S_{j}\approx S_{j}+S_{j}$, then

Let $c\geqslant c_{0}>0$ and $\delta>0$, and note that without loss of generality we may assume that $\delta=\delta(c_{0})$ is sufficiently small. Let $C=C(\delta,c_{0})>0$ be sufficiently large; with foresight, we remark that $C=1/\delta^{13}$ will suffice. Note also that if $c\geqslant 3e/2$, then the theorem follows immediately from Lemma 5.1; we shall therefore assume that $c<3e/2$.

Case 1: $\max\big\{t^{*},t_{*}\big\}\geqslant 1/\delta^{2}$.

Case 2: $\max\big\{t^{*},t_{*}\big\}\leqslant 1/\delta^{2}$.

where $J$ was defined in (11), and define

But by (13) we have $\textup{span}(J)\geqslant\sqrt{\delta}\big(J^{*}+J_{*}\big)$, so (15) follows.

Now $S_{j}\subset J$, and so $2\cdot\textup{span}(J)\geqslant\textup{span}(S_{j}+S_{j})$, which, together with (15), implies that

and hence $|A|\geqslant(1-\delta^{5})|S_{j}|$. Let $A_{*}=\min A$ and $A^{*}=\max A$, and consider the set

where the second inequality follows by (13), and the fact that $2\cdot\textup{span}(S_{j})\geqslant\textup{span}(J)$. Thus, by (16),

and so $\left|\big(A_{*}+B_{j}\big)\cap\big(A^{*}+B_{j}\big)\right|\leqslant|B_{j}|/2$, which easily implies the subclaim. ∎

Finally, observe that $|D\setminus(S_{j}+S_{j})|\leqslant 2\delta|B_{j}|$ by the definition of $A$. Hence

Thus, by the Claim, and setting $q=|Q|$, the number of choices for $S$ is at most

Finally, note that the summand in (17) is bounded above by

where $\gamma=\gamma(\delta,c_{0})\to 0$ as $\delta\to 0$ for any fixed $c_{0}>0$. Since we chose $\delta=\delta(c_{0})$ to be sufficiently small, the theorem follows. ∎

The proof of Theorem 1.4 is almost identical to the proof of Theorem 1.3 given above; we need only to add the following observations: that $S_{j}\subset B_{j}$, and that $a_{j+1}\not\in S_{j}$.

We are therefore in the setting of Theorem 1.3, and hence we can repeat the proof above up to (17), except replacing $\delta$ everywhere by $\delta^{3}$. Using the observations that $S_{j}\subset B_{j}$ and $a_{j+1}\not\in S_{j}$, we deduce that the number of choices for $S$ is at most

has size roughly $3|B_{j}|/2$, and so in this case the subclaim is sharp.

Proof of Theorems 1.1 and 1.2

We are now ready to prove Theorem 1.1, which generalizes the Cameron-Erdős Conjecture to sum-free sets of size $m$, and its structural analogue, Theorem 1.2. Both theorems will follow from essentially the same proof; we shall first prove Theorem 1.1, and then point out how the proof can be adapted to deduce Theorem 1.2. As noted earlier, we shall for simplicity assume throughout that $n$ is even.

The proof is fairly long and technical so, in order to aid the reader, we shall start by giving a brief sketch. The argument is broken into a series of six claims, each relying on the earlier ones; the first five being relatively straightforward, and the last being somewhat more involved.

denote the collection of elements of $I$ which are at most $n/2$, as in the statement of Theorem 1.2. Moreover, given a set $S\subset[n/2]$, let $S^{\prime}=\big\{x\in S:x>n/4\big\}$.

The following claim follows easily from the Hypergeometric Janson Inequality.

sum-free $m$-sets $I\subset[n]$ such that $S(I)=S$.

In the calculation below, we shall on several occasions wish to make the assumption that $n-2m\geqslant\delta n$. The next claim deals with the complementary case.

We shall divide into two cases, depending on the size of $S(I)\cap[n/4]$.

where $t=n/2-m\leqslant\delta n$. By Claim 1, the right-hand side of (21) is an upper bound on the number of sum-free $m$-sets $I\subset[n]$ with $S(I)=S$.

From now on we shall assume that $n-2m\geqslant 2\delta n$. Recall that Claim 1 allows us to count sum-free sets with at most $\delta m$ elements less than $n/2$. We shall use the induction hypothesis to count the sets $I$ that have more than $\delta m$ elements in $[n/2]$.

There are at most $\delta\cdot 2^{Cn/m}{n/2\choose m}$ sum-free $m$-sets $I\subset[n]$ with at least $\delta m$ elements less than $n/2$.

Recall that $m\geqslant C^{1/3}\sqrt{n}$ and that $C=C(\delta)>0$ is sufficiently large. Thus, by Proposition 2.3, there exists $\varepsilon=\varepsilon(\delta)>0$ such that all but $2^{-\varepsilon m}{n/2\choose m}$ sum-free $m$-sets $I\subset[n]$ satisfy either $|I\setminus O_{n}|\leqslant\delta m$, or $|I\setminus B|\leqslant\delta m$ for some interval $B$ of length $n/2$. Moreover, since $\delta>0$ is sufficiently small, by Proposition 4.1 there are at most $2^{Cn/2m}{n/2\choose m}$ sum-free $m$-sets $I\subset[n]$ with $|I\setminus O_{n}|\leqslant\delta m$. We may therefore restrict our attention to the collection $\mathcal{X}$ of sum-free $m$-sets $I\subset[n]$ that satisfy $|I\setminus B|\leqslant\delta^{3}m$ for some interval $B$ of length $n/2$.

First, we shall show that there are only few sets in $\mathcal{X}$ which contain more than $\delta^{3}m$ elements less than $n/2-2\delta^{2}n$. Indeed, such a set contains at most $\delta^{3}m$ elements of the interval $\{n-2\delta^{2}n+1,\ldots,n\}$ and hence, by the induction hypothesis and (3), there are at most

such sets with $s\leqslant\delta^{3}m$ elements greater than $n-2\delta^{2}n$. Summing over $s$, and recalling that $n-2m\geqslant\delta n$, it follows that there are at most

such sets, which is at most $\delta^{2}\cdot 2^{Cn/m}{n/2\choose m}$, since $\delta>0$ was chosen sufficiently small and $m\geqslant C^{1/3}$ is sufficiently large.

It only remains to count the sets in $\mathcal{X}$ which contain at least $\delta m-\delta^{3}m>\delta m/2$ elements of the interval $\{n/2-2\delta^{2}n,\ldots,n/2\}$, and at most $\delta^{3}m$ elements less than $n/2-2\delta^{2}n$. Note that $m\leqslant 5\delta n$ (else there are no such sets), and so by (3) we have

such sum-free sets. But by (23) this is at most

so this completes the proof of the claim. ∎

From now on, we may restrict our attention to those sum-free subsets $I\subset[n]$ for which $|S(I)|\leqslant\delta^{3}m$. The remainder of the proof involves some careful counting using Theorems 1.3 and 1.4 and Lemma 5.1. We shall break up the calculation into three claims. In the first two, which are fairly straightforward, we count the sets $I$ for which $|S(I)|$ is small (Claim 4) or $\sum_{a\in S(I)}(n/2-a)$ is large (Claim 5). Finally in Claim 6, which is much more delicate, we count the remaining sets.

Now, using (4) to bound the sum over $k$, this is at most

The following claim now completes the proof of Theorem 1.1.

To prove (28), we shall partition into two sets by setting

In order to complete the calculation, we break into cases according to the order of magnitude of $m$. We begin with the central range.

Case 1: $C\sqrt{n\log n}\leqslant m\leqslant\delta n$.

Thus, by Theorem 1.3 and (3), it follows that

By the same argument as before, this is at most

Putting together the various cases, we see that (28) is bounded above by

and since $2/3<3/2\sqrt{e}$, this proves the claim for $C\sqrt{n\log n}\leqslant m\leqslant\delta n$.

We next observe that the case $m\leqslant C\sqrt{n\log n}$ can be easily reduced to the case above.

Case 2: $C^{1/3}\sqrt{n}\leqslant m\leqslant C\sqrt{n\log n}$.

as claimed. This completes the proof of the claim for all $C^{1/3}\sqrt{n}\leqslant m\leqslant\delta n$.

Finally, we turn to the case $m=\Theta(n)$. We shall assume first that $m\leqslant n/4$, and then (in Case 4) show how the result for $m>n/4$ follows by the same argument.

Case 3: $\delta n\leqslant m\leqslant n/4$.

The calculation in this case is similar to that in Case 1, except we shall use Theorem 1.4 in place of Theorem 1.3. Indeed, recall that $C=C(\delta)$ is sufficiently large, and observe that

For those with $|S^{\prime}+S^{\prime}|\geqslant|S^{\prime}|/\delta^{3}$, we apply Lemma 5.1 to obtain, exactly as in (35), a bound of

The final inequality again follows by simple calculus: the left-hand side is bounded from above by its value with $\lambda=3$ and $m=n/4$. Since $4/e^{3/2}<3/2\sqrt{e}$, the claim follows in this case also.

The proof is essentially complete; all that remains is to show that case $m\geqslant n/4$ can be deduced easily from the case above.

Case 4: $n/4\leqslant m\leqslant(1/2-\delta)n$.

as required. This completes the proof of Claim 6. ∎

We now sketch how the above proof may be adapted in order to prove Theorem 1.2.

Suppose first that $m\geqslant\big(\frac{1}{2}-\delta\big)n$. Then, by the proof of Claim 2, there are $o{n/2\choose m}$ such sets with $a(I)\geqslant\sqrt{\omega}=\sqrt{\omega(n)}$, which implies that $|S(I)|\leqslant\sqrt{\omega}$ and $k(I)\leqslant\omega$ for almost every sum-free $m$-set in $[n]$, as required. Hence we may assume that $m\leqslant\big(\frac{1}{2}-\delta\big)n$.

Next, we observe the following strengthening of Claim 3 when $m\geqslant C\sqrt{n\log n}$.

If $m\geqslant C\sqrt{n\log n}$, then there are $o{n/2\choose m}$ sum-free subsets $I\subset[n]$ of size $m$ with $I\not\subset O_{n}$ and at least $\delta m$ elements less than $n/2$.

The proof is almost identical to that of Claim 3. The only difference is that when we bound the number of sum-free $m$-sets $I$ such that $1\leqslant|I\setminus O_{n}|\leqslant\delta m$, we replace Proposition 4.1 by Proposition 4.2, which holds for $m\geqslant C\sqrt{n\log n}$, and implies that there are at most $o{n/2\choose m}$ such sets. When bounding the size of the collection $\mathcal{X}$ of sum-free $m$-sets $I\subset[n]$ that satisfy $|I\setminus B|\leqslant\delta^{3}m$ for some interval $B$ of length $n/2$, we use (22) and note that

since $\delta^{3}m>Cn/m$ for $m\geqslant C\sqrt{n\log n}$. The rest of the proof is exactly the same. ∎

such sets. Now, recall that $n-2m\geqslant\delta m$ and note that (41) is decreasing exponentially in $k$. Thus if $m=o(n)$, then (41) is at most

and if $m=\Theta(n)$ then (41) is at most

such sum-free sets $I$, as required. This completes the proof of Theorem 1.2. ∎

Acknowledgements

The third and fourth authors would like to thank Simon Griffiths and Gonzalo Fiz Pontiveros for several useful discussions.

References