Problem 748

Let $f(n)$ count the number of sum-free $A\subseteq \{1,\ldots,n\}$ , i.e. $A$ contains no solutions to $a=b+c$ with $a,b,c\in A$ . Is it true that

f(n)=2^{(1+o(1))\frac{n}{2}}?

Source: erdosproblems.com/748

Number theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site labels the problem PROVED and credits Green [Gr04] and Sapozhenko [Sa03], who independently proved the stronger bound $f(n)\ll2^{n/2}$ of the Cameron–Erdős conjecture, and in fact the asymptotic $f(n)\sim c_n2^{n/2}$ with $c_n$ taking one of two values according to the parity of $n$ . The displayed statement itself dates from Calkin [Ca90] and Alon [Al91]: with the trivial lower bound $f(n)\ge2^{\lceil n/2\rceil}$ from the subsets of $(n/2,n]$ , each of their upper bounds $2^{n/2+o(n)}$ gives $f(n)=2^{(1+o(1))n/2}$ . Problem 877 is the maximal case. Claim pages: Calkin 1990 (accepted, refereed in Bull. London Math. Soc.), Alon 1991 (accepted, refereed in Israel J. Math.), and, as the later and stronger results, Green 2003 (accepted, refereed in Bull. London Math. Soc. 2004) and Sapozhenko 2003 (accepted, refereed in Discrete Math. 2008 after a Doklady note of 2003; neither held here). The unpublished proof of Erdős and Granville has no posting and so no claim page.

Gr04: Green, B., The Cameron-Erdős conjecture. Bull. London Math. Soc. 36 (2004), no. 6, 769--778, DOI 10.1112/S0024609304003650.
Sa03: Sapozhenko, A. A., The Cameron-Erdős conjecture. Dokl. Akad. Nauk 393 (2003), no. 6, 749--752.
Sa08: Sapozhenko, A. A., The Cameron–Erdős conjecture. Discrete Math. 308 (2008), no. 19, 4361--4369, DOI 10.1016/j.disc.2007.08.103; the full version of [Sa03].
Ca90: Calkin, N. J., On the Number of Sum-Free Sets. Bull. London Math. Soc. 22 (1990), no. 2, 141--144, DOI 10.1112/blms/22.2.141.
Al91: Alon, N., Independent sets in regular graphs and sum-free subsets of finite groups. Israel J. Math. 73 (1991), no. 2, 247--256, DOI 10.1007/BF02772952.
CaEr90: Cameron, P. J. and Erdős, P., On the number of sets of integers with various properties. Number theory (Banff, AB, 1988), de Gruyter, Berlin, 1990, 61--79.
Er94b: Erdős, P., Some problems in number theory, combinatorics and combinatorial geometry. Math. Pannon. 5 (1994), no. 2, 261--269.
Er98: Erdős, P., Some of my new and almost new problems and results in combinatorial number theory. Number theory (Eger, 1996), de Gruyter, Berlin, 1998, 169--180.

Problem 748

Status

Proof claims

Discussion