Problem 789

Let $h(n)$ be maximal such that if $A\subseteq \mathbb{Z}$ with $\lvert A\rvert=n$ then there is $B\subseteq A$ with $\lvert B\rvert \geq h(n)$ such that if $a_1+\cdots+a_r=b_1+\cdots+b_s$ with $a_i,b_i\in B$ then $r=s$ .

Estimate $h(n)$ .

Source: erdosproblems.com/789

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 supported by sources in hand are $n^{1/3}(\log n)^{1/3}\ll h(n)<\tfrac4{\sqrt3}n^{1/2}+1$ for all $n$ , with the sharper $h(n)\le2\sqrt{n+1/4}-1$ for all $n\ge N_0$ : the upper bounds are Straus's square-root bound in the form proved by Erdős, Nicolas and Sárközy (Lemme 2, applied to the admissible subsets of $\{1,\ldots,n\}$ ; an accepted partial claim on Straus's claim page (1966)) and Theorem 1 of Deshouillers and Freiman (Astérisque 258 (1999), refereed), applied to the same witness $\{1,\ldots,n\}$ ; the lower bound is Choi's estimate (1) (J. Number Theory 6 (1974), 105--111, refereed; an accepted partial claim on Choi's claim page (1974)), which sharpens Erdős's 1965 inequality (31), $h(n)\ge n^{1/3}$ . Erdős's 1962 Theorem IV gives the weaker $h(n)<Cn^{5/6}$ (an accepted partial claim on its claim page (Erdős, 1962)). Inequality (31) and the theorem of Deshouillers and Freiman have no claim pages: (31) 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 1999 theorem, which sharpens only the constant of Straus's bound. A full proof claim of 12 September 2026 on the site's tab, declaring the use of GPT Astra, claims $h(n)\gg(n\log\log n/\log n)^{1/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 adopt the claim; the formal-conjectures catalog has carried a third-party formal proof of that lower bound since 2026-09-29, which the corpus has not built, and the catalog's main statement erdos_789 stays open. The exponent of $h(n)$ is open between $1/3$ and $1/2$ on the accepted evidence; this is a bounded negative finding, not a certificate of openness. The frontmatter standing, claimed with the claim value answered, derives from the pending full claim; the accepted claims are partial.

Er62c: Erdős, P., Számelméleti megjegyzések, III. Néhány additív számelméleti problémáról (Remarks on number theory III). Mat. Lapok 13 (1962), 28--38 (Hungarian, with Russian and English summaries; Zbl 0123.25503, zbMATH record). Condition (1') and Theorem IV, printed p. 34; the proof pp. 35--36; the English summary p. 38. Library home: Erdős 1962; result page Theorem IV.
St66: Straus, E. G., On a problem in combinatorial number theory. J. Math. Sci. 1 (1966), 77--80 (the zbMATH record gives this citation; no DOI). Not held. Its Theorems 2 and 4 are quoted, with a proof of the second from the first, in [ENS91], pp. 56--57, and its results are reported in [DeFr99], p. 141.
Ch74b: Choi, S. L. G., On an extremal problem in number theory. J. Number Theory 6 (1974), no. 2, 105--111, doi:10.1016/0022-314X(74)90048-1 (Crossref record; the record carries the publisher's open-archive license dated 2013). The definition of $h(n)$ for $n$ nonzero integers and the estimate (1), $h(n)\gg n^{1/3}(\log n)^{1/3}$ , printed p. 105 (PDF p. 1 of the publisher's open-archive scan); the proof pp. 109--111 (PDF pp. 5--7). Library home: Choi 1974; result page Estimate (1).
Er65: Erdős, P., Extremal problems in number theory. Proc. Sympos. Pure Math. VIII, Amer. Math. Soc. (1965), 181--189; displays (29)--(31) on printed p. 188 and the later "Additions" on printed p. 190. Library home: Erdos 1965; result page Inequality (31).
Er73: Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Fort Collins, 1971), North-Holland (1973), 117--138; Section 9, printed p. 130. Library home: Erdos 1973; result page Section 9.
ENS91: Erdős, P., Nicolas, J.-L. and Sárközy, A., Sommes de sous-ensembles. Sém. Théor. Nombres Bordeaux (2) 3 (1991), no. 1, 55--72, doi:10.5802/jtnb.42. Lemme 1 and Lemme 2, pp. 56--57. Library home: Erdős, Nicolas and Sárközy 1991; result page Lemme 2.
DeFr99: Deshouillers, J.-M. and Freiman, G. A., On an additive problem of Erdős and Straus, 2. Astérisque 258 (1999), 141--148; the account of Straus's bound, p. 141; Theorem 1, p. 142. Library home: Deshouillers 1999; result page Theorem 1.
CFP23: , [PhZa24] Conlon, D., Fox, J. and Pham, H. T., Homogeneous structures in subset sums and non-averaging sets, arXiv:2311.01416v1 (2023), and Pham, H. T. and Zakharov, D., Sharp bound for the Erdős--Straus non-averaging set problem, Geom. Funct. Anal. 35 (2025), 1712--1738: the sources of the site's cross-reference [186], on non-averaging sets, a different problem; neither states a bound for this $h(n)$ . Library homes: Conlon, Fox and Pham 2023, Pham and Zakharov 2024.

Problem 789

Status

Proof claims

Discussion