Sharp enumeration and growth of admissible sets of integers
math.CO
Submitted: 2026-10-25
Updated: 2026-11-19
License: http://creativecommons.org/licenses/by/4.0/
The gist: A set of positive integers is admissible if equal sums of finite subsets always have equal numbers of summands.
Terminology
Abstract
A set of positive integers is admissible if equal sums of finite subsets always have equal numbers of summands. Let a(N) count the nonempty admissible subsets of 1,,N, and let b(N) count those with maximum N. We prove a(N) about b(N) aboutπ sqrt 2N/3, establishing the sharp logarithmic asymptotic proposed by Nicolas. More generally, let Q h(N) count the subsets for which each integer has subset-sum representations of at most h distinct cardinalities. Uniformly for all positive integers h,N, we prove Q h(N) N, sqrt hN with absolute implied constants. Every infinite set satisfying the same condition for some fixed h has counting function o(sqrt x). At h=1, the latter two results settle conjectures of Erdős, Nicolas and Sárközy, strengthening the proposed vanishing lower limit to a full limit. The proofs record each subset sum together with its cardinality and use the counting theorem of Campos and the structure theorem of Carpenter, Defant and Kravitz. The sharp count also uses Nicolas's partition enumeration and an elementary construction of a long restricted-sum progression. Finally, we give an exact partition formula for the odd sets with separated alternate cardinality layers suggested by Nicolas.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality