TOPICS
Search

Erdős Distinct Subset Sums Problem

The Erdős distinct subset sums problem asks whether there is an absolute constant c>0 such that every set of positive integers a_1<...<a_n having 2^n distinct subset sums satisfies a_n>=c2^n. It is problem 1 in the Erdős problems collection (Bloom 2026).

Let f(n) be the least possible largest element a_n of such a set. Its first values, for n=1, 2, ..., are 1, 2, 4, 7, 13, 24, 44, 84, 161, 309, ... (OEIS A276661). The powers of two give the elementary upper bound f(n)<=2^(n-1). Dubroff et al. (2021) proved

f(n)>=(n; |_n/2_|),
(1)

where |_x_| is the floor function. Hasratyan and Ruszinkó (2026) obtained, for n>=2, the alternative bound

f(n)>=2(n-1; |_(n-1)/2_|),
(2)

which is larger for odd n. Neither changes the leading asymptotic lower bound

f(n)>=(sqrt(2/pi)-o(1))(2^n)/(sqrt(n)).
(3)

A stronger finite bound follows from the graph bandwidth of the hypercube graph:

f(n)>=sum_(j=0)^(n-1)(j; |_j/2_|),
(4)

as shown by Costa and Della Fiore (2026). These estimates do not settle whether f(n)/2^n is bounded away from zero.

See also

Erdős Problems, Subset Sum

Explore with Wolfram|Alpha

References

Bloom, T. "Erdős Problem #1." Accessed Oct. 26, 2026. https://www.erdosproblems.com/1.Costa, S. and Della Fiore, S. "A Bandwidth Refinement of the Erdős Distinct Subset Sums Bound." 22 Aug 2026. https://arxiv.org/abs/2609.27941.Dubroff, Q.; Fox, J.; and Xu, M. W. "A Note on the Erdős Distinct Subset Sums Problem." SIAM J. Disc. Math. 35, 322-324, 2021. https://doi.org/10.1137/20M1385883.Hasratyan, A. and Ruszinkó, M. "New Approaches to the Erdős Distinct Subset Sums Problem." 23 Oct 2026. https://arxiv.org/abs/2610.32580.Sloane, N. J. A. Sequence A276661 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Erdős Distinct Subset Sums Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ErdosDistinctSubsetSumsProblem.html

Subject classifications