Problem 790

Let $l(n)$ be maximal such that if $A\subset\mathbb{Z}$ with $\lvert A\rvert=n$ then there exists a sum-free $B\subseteq A$ with $\lvert B\rvert \geq l(n)$ - that is, $B$ is such that there are no solutions to

a_1=a_2+\cdots+a_r

with $a_i\in B$ all distinct.

Estimate $l(n)$ . In particular, is it true that $l(n)n^{-1/2}\to \infty$ ? Is it true that $l(n)< n^{1-c}$ for some $c>0$ ?

Source: erdosproblems.com/790

Additive combinatorics

Wiki page

Status

ClaimedAnswered

A full solution has been claimed but not yet accepted. Settled in another form, for example when its parts resolve differently or the question is open-ended.

Open, the site's label. The bounds in hand are the Theorem of Choi, Komlós and Szemerédi (Trans. Amer. Math. Soc. 212 (1975), refereed; an accepted partial claim on its claim page (Choi, Komlós and Szemerédi, 1975)), $(n\log n/\log\log n)^{1/2}\ll l(n)\ll n/\log n$ , which answer the first displayed question affirmatively and leave the second open; the paper's closing remark that it is "conceivable that $f(n)>n^{1-\epsilon}$ for every $\epsilon$ " (p. 313) is the conjecture $l(n)\ge n^{1-o(1)}$ that the site attributes to the authors. Erdős's $l(n)\ge(n/2)^{1/2}$ (1965, inequality (30)) and Choi's improvement (Proc. Amer. Math. Soc. 39 (1973), refereed, not held; an accepted partial claim on its claim page (Choi, 1973)) are the earlier lower bounds; the site, following Erdős 1973, writes Choi's bound as $(1+c)n^{1/2}$ , while the zbMATH review of the paper gives $\frac{35}{36}n^{1/2}$ . Erdős's 1965 claim that $l(n)=o(n)$ was withdrawn in 1973, the year Choi proved $l(n)\ll n(\log\log n)^{-1/2}$ (Proc. Amer. Math. Soc. 41 (1973), 415--418). Inequality (30) and the second 1973 paper have no claim pages: (30) appeared in a proceedings volume with only a sketch of its proof and is superseded by Choi's refereed bound, and the site does not credit the second paper, whose bound the 1975 Theorem supersedes. A full proof claim on the site's tab (13 September 2026), declaring the use of GPT Astra, claims $l(n)\gg n/(\log n)^2$ and is recorded as a pending claim on its claim page (Korsky, 2026); the site's label was OPEN on 2026-09-18 and on 2026-10-06, and its commentary does not mention the claim. The search whose scope the Current assessment records found no refereed improvement of either bound. This is a bounded negative finding, not a certificate of openness.

CKS75: Choi, S. L. G., Komlós, J. and Szemerédi, E., On sum-free subsequences. Trans. Amer. Math. Soc. 212 (1975), 307--313, DOI 10.1090/S0002-9947-1975-0376594-1 (Crossref record accessed); the Theorem, display (1.1), printed p. 307; the closing remark, printed p. 313. Library home: Choi and Szemerédi 1975; result page Theorem.
Er65: Erdős, P., Extremal problems in number theory. Proc. Sympos. Pure Math. VIII (Theory of Numbers), Amer. Math. Soc. (1965), 181--189, DOI 10.1090/pspum/008/0174539; the $g(n)$ passage with inequality (30), printed p. 188; the Additions (a later layer), printed p. 190. Library home: Erdos 1965; result page inequality (30).
Er73: Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971), North-Holland (1973), 117--138; Section 9, the $l(n)$ paragraph, printed p. 130. Library home: Erdos 1973; result page Section 9.
Va99: Various, Some of Paul's favorite problems. Booklet for the conference "Paul Erdős and his mathematics", Budapest, July 1999; item 1.22 b). Library home: Various 1999; result page Problem 1.22.
Ch73: Choi, S. L. G., The largest sum-free subsequence from a sequence of $n$ numbers. Proc. Amer. Math. Soc. 39 (1973), no. 1, 42--44, DOI 10.1090/S0002-9939-1973-0313216-3: for the real-number function, the bound $g(n)>\frac{35}{36}n^{1/2}$ for $n\ge n_0$ , as the zbMATH review (Zbl 0248.10041) states it, where [Er73] reports $l(n)>(1+c)n^{1/2}$ ; and On sequences not containing a large sum-free subsequence, Proc. Amer. Math. Soc. 41 (1973), no. 2, 415--418, DOI 10.1090/S0002-9939-1973-0325563-X: for $n$ large, a sequence of $n$ integers whose largest sum-free subsequence has at most $cn(\log\log n)^{-1/2}$ integers (the abstract, Crossref record), so that $l(n)=o(n)$ . Not held; listed as references 2 and 4 of [CKS75] and in the Additions of [Er65].

Problem 790

Status

Proof claims

Discussion