Problem 1

If $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\subseteq A$ then

N \gg 2^{n}.

Source: erdosproblems.com/1

Number theory
Additive combinatorics

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

DISPROVED (FORMALIZED), the site's label. In fact, for every $\varepsilon>0$ there are examples of arbitrarily large cardinality with $N\leq\varepsilon2^{|A|}$ . The claim pages are the 2026 GPT-6 Astra disproof, posted on the proof-claim tab by the site's curator, and the dyadic-graph Lean disproof in Boris Alexeev's lean-proofs repository, which gives an explicit bound at every cardinality. Both are accepted on their Lean developments, each pinned by its repository's comparator challenge, which this corpus built and checked, so the problem stands solved and disproved here; the curator's label and credit are not an independent review of a proof claim the curator submitted, and neither route has a refereed write-up.

Bo98b: Bohman, T., A construction for sets of integers with distinct subset sums. Electron. J. Combin. 5 (1998), Research Paper 3, doi:10.37236/1341. The site's commentary credits the bound $N\le0.22002\cdot2^n$ to Bohman under its key [Bo98], which the site's reference record resolves to Bollobás, B., To prove and conjecture: Paul Erdős and his mathematics, Amer. Math. Monthly (1998), 209--237, a different paper; the record above is the paper the commentary describes, cited as [Bo98b] in the site's proof exposition. Library home: Bohman 1997.
CoGu68: J. H. Conway and R. K. Guy, Sets of natural numbers with distinct sums. Notices Amer. Math. Soc. (1968), 345.
DFX21: Dubroff, Q. and Fox, J. and Xu, M. W., A note on the Erdős distinct subset sums problem. SIAM Journal on Discrete Mathematics (2021), 322-324.
Er56: Erdős, P., Problems and results in additive number theory. Colloque sur la Théorie des Nombres, Bruxelles, 1955 (1956), 127-137.
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) (1973), 117-138.
Er80: Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115.
Er85c: Erdős, P., On some of my problems in number theory I would most like to see solved. Number theory (Ootacamund, 1984) (1985), 74-84.
Er98: Erdős, Paul, Some of my new and almost new problems and results in combinatorial number theory. Number theory (Eger, 1996) (1998), 169-180.
ErGr80: Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).
ErSp74: Erdős, Paul and Spencer, Joel, Probabilistic methods in combinatorics. Akadémiai Kiadó (1974).
Gr71: Graham, R. L., On sums of integers taken from a fixed sequence. Proceedings of the Washington State University Conference on Number Theory (1971), 22--40; Question 8, printed p. 35, asks the real variant (subset sums differing by at least 1) and calls it a strengthening of Erdős's conjecture. Library home: Graham 1971.
Gu04: Guy, Richard K., Unsolved problems in number theory. 3rd ed., Problem Books in Mathematics, Springer, New York (2004), xviii+437 pp. Section C8 "Sets with distinct sums of subsets", printed p. 174: "Erdős has asked for the maximum number, $m$ , of positive integers $a_1<a_2<\cdots<a_m\le2^k$ , with all sums of subsets distinct. With Leo Moser he showed that $k+1\le m<k+\frac12\log k+2$ where the logarithm is to base 2. Noam Elkies improved the constant 2 on the right to $\frac12\log\pi<0.826$ ", then the Conway--Guy sequence, its set of $k+2$ integers conjectured to have distinct subset sums, $m\ge k+2$ for $k\ge21$ , the conjecture that $m=k+2$ is best possible, and "Erdős offered $500.00 for a proof or disproof of $m=k+O(1)$ ". Library home: Guy 2004.
Gu82: Guy, Richard K., Sets of integers whose subsets have distinct sums. (1982), 141-154.
Ru99: Ruzsa, I., Erdős and the Integers. Journal of Number Theory 79 (1999), 115--163, doi:10.1006/jnth.1999.2395; § 16, The kitchen sink, printed p. 151 (PDF p. 37 of the open-archive file at that DOI), states the problem as the "$300 problem" of Erdős and Spencer's book and records the bounds $1+[\log_2n]\le g(n)\le\log_2n+\log_2\log_2n+o(1)$ on the largest number $g(n)$ of integers in $[1,n]$ with distinct subset sums, the Erdős--Moser halving of the $\log_2\log_2n$ term and the Conway--Guy improvement of the lower bound by one for $n\ge2^{21}$ ; it states no result beyond these bounds. Library home: Ruzsa 1999.
St23: Steinerberger, S., Some remarks on the Erdős distinct subset sums problem. arXiv:2208.12182 (2023).

Problem 1

Status

Proof claims

Discussion