Problem 787

Let $g(n)$ be maximal such that given any set $A\subset \mathbb{R}$ with $\lvert A\rvert=n$ there exists some $B\subseteq A$ of size $\lvert B\rvert\geq g(n)$ such that $b_1+b_2\not\in A$ for all $b_1\neq b_2\in B$ .

Estimate $g(n)$ .

Source: erdosproblems.com/787

Additive combinatorics

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label. The bounds in hand are $(\log n)^{1+c}\ll g(n)\ll\exp(O(\sqrt{\log n}))$ , each an accepted partial claim: the lower bound is Theorem 1.2 of Sanders (Canad. J. Math. 73 (2021), refereed; its claim page (Sanders, 2018)), with a second proof and the explicit range $c<1/68$ in Theorem 1.2 of Beker's 2025 preprint, accepted by Int. Math. Res. Not. (a pending partial claim on its claim page (Beker, 2025)); the upper bound is the Theorem of Ruzsa's 2005 paper (Ramanujan J., refereed; its claim page (Ruzsa, 2005)), $l(n)\ll e^{c\sqrt{\log n}}$ for every $c>\sqrt{8\log2}$ over sets of positive integers, by a construction from dilated lattice balls that Sanders describes as Behrend's. Between them lie Klarner's $\gg\log n$ (Erdős 1965, stated without proof), Choi's $\ll n^{2/5+o(1)}$ (1971, not held, attested by Erdős 1973 and the later papers; its claim page (Choi, 1971)) and the refereed refinement $O(n^{2/5}(\log n)^{2/5})$ of Baltz, Schoen and Srivastav (2000), which has no claim page of its own because the site does not cite it and Ruzsa's bound supersedes it. No result determines the order of growth, and the search whose scope the Current assessment records found no proof claim, no citing paper improving either bound and no adoption of any such result by the site. This is a bounded negative finding, not a certificate of openness.

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 $\phi(n)$ passage, printed p. 187; the later Additions, printed p. 190. Library home: Erdos 1965; result page the $\phi(n)$ passage.
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, display (9.2), 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 c). Library home: Various 1999; result page Problem 1.22.
Ch71: Choi, S. L. G., On a combinatorial problem in number theory. Proc. London Math. Soc. (3) 23 (1971), no. 4, 629--642, DOI 10.1112/plms/s3-23.4.629 (Crossref record). Not held; its bounds and its integer reduction are quoted from [Er73], [BSS00], [Sa21] and [Be25].
Ru05: Ruzsa, I. Z., Sum-avoiding subsets. Ramanujan J. 9 (2005), no. 1--2, 77--82, DOI 10.1007/s11139-005-0826-4 (received August 27, 2002; accepted December 23, 2002). The definitions of $\lambda(A)$ and $l(n)$ and the Theorem, display (1.1), printed p. 77; the proof of the upper estimate, pp. 78--79; the proof of the lower estimate and the greedy example, pp. 79--82. Library home: Ruzsa 2005; result page Theorem.
BSS00: Baltz, A., Schoen, T. and Srivastav, A., Probabilistic construction of small strongly sum-free sets via large Sidon sets. Colloq. Math. 86 (2000), no. 2, 171--176, DOI 10.4064/cm-86-2-171-176 (Crossref record). Corollary 3, printed p. 174. Not a key of the site's page. Library home: Baltz, Schoen and Srivastav 2000; result page Corollary 3.
Sa21: Sanders, T., The Erdős--Moser sum-free set problem. Canad. J. Math. 73 (2021), no. 1, 63--107, DOI 10.4153/S0008414X1900049X (published online 23 September 2019; Crossref record); arXiv:1804.03356 (v1 10 April 2018; v3 31 July 2019, 47 pages, "Corrections and clarifications"). Theorem 1.1 (Ruzsa, quoted), p. 1; Theorem 1.2, p. 2. Library home: Sanders 2021; result pages Theorem 1.2 and Theorem 1.1.
Be25: Beker, A., The Erdős--Moser sum-free set problem via improved bounds for $k$ -configurations. arXiv:2501.10203v1 (17 January 2025; 23 pages); v2 of 2 October 2026 (24 pages) is the final version, which its arXiv comment says incorporates the referee's comments, corrects an error in the proof of Lemma 2.2 of v1 and is to appear in Int. Math. Res. Not.; Theorems 1.1 and 1.2 are unchanged. Theorem 1.1, p. 3; Theorem 1.2, p. 3. Library home: Beker 2025; result page Theorem 1.2.

Problem 787

Status

Proof claims

Discussion