Problem 877

Let $f_m(n)$ count the number of maximal sum-free subsets $A\subseteq\{1,\ldots,n\}$ - that is, there are no solutions to $a=b+c$ in $A$ and $A$ is maximal with this property. Estimate $f(n)$ - is it true that $f_m(n)=o(2^{n/2})$ ?

Source: erdosproblems.com/877

Additive combinatorics

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The displayed question has the answer yes: $f_m(n)=2^{(1/4+o(1))n}$ by Theorem 1.1 of Balogh, Liu, Sharifzadeh and Treglown (Proc. Amer. Math. Soc. 143 (2015), 4713--4721; refereed, cited from the arXiv version), which is $o(2^{n/2})$ , and the estimate is settled by the same authors' Theorem 1.1 of 2018 (J. Eur. Math. Soc. 20 (2018), 1885--1911; refereed, cited from the arXiv version): for each $1\le i\le4$ there is a constant $C_i$ with $f_m(n)=(C_i+o(1))2^{n/4}$ for $n\equiv i\pmod4$ , the $C_i$ computable to any additive error. The first resolution of the displayed question, $f_m(n)\le2^{n/2-2^{-28}n}$ for large $n$ by Łuczak and Schoen (Proc. Amer. Math. Soc. 129 (2001), 2205--2207), is not held and is quoted second-hand from the introductions of [BLST15] and [BLST18], as is Wolfovitz's intermediate bound $f_m(n)\le2^{3n/8+o(n)}$ (European J. Combin. 30 (2009), 1718--1723). Label and sources agree. The four accepted claims are recorded on their claim pages: Łuczak and Schoen, Wolfovitz, the exponent one quarter and the sharp asymptotic.

BLST15: Balogh, J., Liu, H., Sharifzadeh, M. and Treglown, A., The number of maximal sum-free subsets of integers. Proc. Amer. Math. Soc. 143 (2015), no. 11, 4713--4721, DOI 10.1090/S0002-9939-2015-12615-9 (Crossref record read). Cited from arXiv:1409.5661v1 (19 September 2014, 10 pp., "to appear in the Proceedings of the American Mathematical Society"); Theorem 1.1, p. 2 of the preprint; the journal text not compared. Library home: Balogh et al. 2015; result page Theorem 1.1.
BLST18: Balogh, J., Liu, H., Sharifzadeh, M. and Treglown, A., Sharp bound on the number of maximal sum-free subsets of integers. J. Eur. Math. Soc. (JEMS) 20 (2018), no. 8, 1885--1911, DOI 10.4171/JEMS/802 (Crossref record read). Cited from arXiv:1502.07605v2 (11 May 2018, 25 pp., "to appear in the Journal of the European Mathematical Society"); Theorem 1.1, p. 2 of the preprint; the journal text not compared. Library home: Balogh et al. 2018; result page Theorem 1.1.
LuSc01: Łuczak, T. and Schoen, T., On the number of maximal sum-free sets. Proc. Amer. Math. Soc. 129 (2001), no. 8, 2205--2207, DOI 10.1090/S0002-9939-00-05815-9 (Crossref record read; published online 28 December 2000). Not held. Its bound is quoted from [BLST15], p. 2, and [BLST18], p. 2.
Wo09: Wolfovitz, G., Bounds on the number of maximal sum-free sets. European J. Combin. 30 (2009), no. 7, 1718--1723, DOI 10.1016/j.ejc.2009.03.015 (Crossref record read: record created 9 April 2009, print issue October 2009). An extended abstract with the same title appeared in Electron. Notes Discrete Math. 29 (2007), 321--325, DOI 10.1016/j.endm.2007.07.055. Neither is held; the bound is quoted from [BLST15], p. 2, and [BLST18], p. 2. Claim page: Wolfovitz's bound.
CaEr90: Cameron, P. J. and Erdős, P., On the number of sets of integers with various properties. Number Theory (Banff, 1988), de Gruyter, Berlin (1990), 61--79 (the Crossref record, DOI 10.1515/9783110848632-008, gives pp. 61--80). Not held. The site's key for the problem; [BLST15] and [BLST18] cite it for the conjecture $f(n)=O(2^{n/2})$ .
CaEr99: Cameron, P. J. and Erdős, P., Notes on sum-free and related sets. Combin. Probab. Comput. 8 (1999), 95--107. Not held; the reference of [BLST15] and [BLST18] for the question and the lower bound $2^{\lfloor n/4\rfloor}$ .
Er98: Erdős, P., Some of my new and almost new problems and results in combinatorial number theory. Number theory (Eger, 1996), de Gruyter (1998), 169--180. Not held.
OEIS: Hindman, N., Sequence A121269, The On-Line Encyclopedia of Integer Sequences (2006; entry last modified 10 May 2025, server time): "Number of maximal sum-free subsets of $\{1,2,\ldots,n\}$ ", $1,1,2,2,4,5,6,8,13,17,23,\ldots$ from $n=0$ , with a table to $n=80$ ; JSON record of 2026-09-18. A data lead only.

Problem 877

Status

Proof claims

Discussion