Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. For all sufficiently large nn,

fm(n)≤2n/2−2−28n,f_m(n)\le2^{n/2-2^{-28}n},

where fm(n)f_m(n) counts the maximal sum-free subsets of {1,…,n}\{1,\ldots,n\} as in Problem 877. Since the exponent is cncn with c<1/2c<1/2, this gives fm(n)=o(2n/2)f_m(n)=o(2^{n/2}) and answers the displayed question yes. The source is T. Łuczak and T. Schoen, On the number of maximal sum-free sets, Proc. Amer. Math. Soc. 129 (2001), no. 8, 2205--2207, cited as [LuSc01] on the problem page. The paper is not held: the bound is quoted from the introductions of the two later papers of Balogh, Liu, Sharifzadeh and Treglown, which state it in this form and say that it answered the question of Cameron and Erdős. As an estimate the bound is an upper bound only; the exact order of fm(n)f_m(n) is the later claim on its own page. The formal-conjectures statement file for the problem (added 2026-09-21) carries a variant luczak_schoen, some c<1/2c<1/2 with fm(n)≤2cnf_m(n)\le2^{cn} for all large nn, whose formal_proof link points to the Lean development described on the page of Balogh, Liu, Sharifzadeh and Treglown, the theorem erdos_877_exponential_bound with an explicit exponent below 1/21/2 obtained by a deletion count of the Łuczak--Schoen kind; that development names the four later authors, not Łuczak and Schoen, as its informal authors, so it is not a formalization of this paper.

Depends on. No wiki page; the claim rests on the cited paper.

Acceptance. Refereed: the paper is a research article in the Proceedings of the American Mathematical Society (Crossref record read: published online 28 December 2000, the date that names this page; volume 129, issue 8, 2001). Reviewed: the site's curator, Thomas Bloom, marks the problem proved on erdosproblems.com and credits Łuczak and Schoen with a bound fm(n)<2cnf_m(n)<2^{cn} for some c<1/2c<1/2 that settles the question; the two refereed papers of 2015 and 2018 cite the result as the answer to the question. The paper's read status is unread, so no further evidence is listed.