TOPICS
Search

Erdős-Nicolas-Sárközy Conjecture


The Erdős-Nicolas-Sárközy conjecture concerns the number a(N) of nonempty admissible sets contained in {1,...,N}. An admissible set here requires that equal-sum subsets have equal cardinal number. The conjecture asserts that a(N)=exp(Theta(sqrt(N))) (Erdős et al. 1991), where Theta denotes big-Theta notation.

Wang and Yang (2026) proved that there are absolute constants c,C>0 such that

 exp(csqrt(N))<=a(N)<=exp(Csqrt(N))

for every integer N>=4. The same bounds hold for the number of admissible sets whose maximum is exactly N. The counting problem is distinct from maximizing the cardinal number of an admissible set.


See also

Admissible Set

Explore with Wolfram|Alpha

References

Erdős, P.; Nicolas, J.-L.; and Sárközy, A. "Sommes de sous-ensembles." J. Théor. Nombres Bordeaux 3, 55-72, 1991.Wang, G. and Yang, W. "Counting Admissible Sets of Integers: A Proof of the Erdős-Nicolas-Sárközy Conjecture." 25 Oct 2026. https://arxiv.org/abs/2610.34372.

Cite this as:

Weisstein, Eric W. "Erdős-Nicolas-Sárközy Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Erdos-Nicolas-SarkozyConjecture.html

Subject classifications