A bandwidth refinement of the Erdős distinct subset sums bound

Abstract

Let f(n) be the least possible largest element of an n-element set of positive integers with pairwise distinct subset sums. Dubroff, Fox and Xu proved the finite lower bound f(n)≥ binomn⌊ n/2⌋ by applying a vertex-boundary estimate to the 2ⁿ⁻¹ subsets whose sums lie below half of the total sum. We instead order all 2ⁿ subsets by increasing subset-sum value. We prove that the bandwidth of this numbering is at most the largest element of the set, so the exact formula for the bandwidth of the hypercube gives the stronger finite bound f(n)≥ H_n:=∑_j=0ⁿ⁻¹binomj⌊ j/2⌋. An exact identity for H_n in terms of Catalan numbers yields H_n/(binomn⌊ n/2⌋) = 1+2/3n+O(n⁻²),& n even, [5pt] 1+4/3n+O(n⁻²),& n odd. For every n≥3, this bound is strictly larger than the central-binomial bound. As a separate corollary, a first-order asymptotic formula for factorials rewrites this lower bound as a multiple of √(2/π) 2ⁿ/√n; the coefficients of 1/n are 5/12 in even dimension and 7/12 in odd dimension.

New approaches to the Erdős Distinct Subset Sums Problem
Aren Hasratyan, Miklós Ruszinkó
arXiv23 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Gaussian Lower Bounds for Distinct Subset Sums in Higher Dimensions
Zijie Gu
arXiv18 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
A near-quadratic lower bound for the Brown--Erdős--Sós (9,6)-problem
Xiangliang Kong, Chong Shangguan, Xin Wang
arXiv3 Nov 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
A tyro's approach to the tilted sieve: beyond the Erdős--Rankin bound
Tristan Freiberg
arXiv23 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
The Erdős--Ginzburg--Ziv constant of C_n^r for even n: rigid sequences, products, and growth beyond Harborth's bound
Christian Elsholtz
arXiv27 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theory Combinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{costa2026bandwidth,
  title = {{A bandwidth refinement of the Erdős distinct subset sums bound}},
  author = {Simone Costa and Stefano Della Fiore},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.27941},
  eprint = {2609.27941},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.27941},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - A bandwidth refinement of the Erdős distinct subset sums bound
AU  - Simone Costa
AU  - Stefano Della Fiore
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.27941
UR  - https://arxiv.org/abs/2609.27941
AB  - Let f(n) be the least possible largest element of an n-element set of positive integers with pairwise distinct subset sums. Dubroff, Fox and Xu proved the finite lower bound f(n)≥ binomn⌊ n/2⌋ by applying a vertex-boundary estimate to the 2^n−1 subsets whose sums lie below half of the total sum. We instead order all 2^n subsets by increasing subset-sum value. We prove that the bandwidth of this numbering is at most the largest element of the set, so the exact formula for the bandwidth of the hypercube gives the stronger finite bound f(n)≥ H_n:=∑_j=0^n−1binomj⌊ j/2⌋. An exact identity for H_n in terms of Catalan numbers yields H_n/(binomn⌊ n/2⌋) = 1+2/3n+O(n^−2),& n even, [5pt] 1+4/3n+O(n^−2),& n odd. For every n≥3, this bound is strictly larger than the central-binomial bound. As a separate corollary, a first-order asymptotic formula for factorials rewrites this lower bound as a multiple of √(2/π) 2^n/√n; the coefficients of 1/n are 5/12 in even dimension and 7/12 in odd dimension.
ER  -

Abstract

Related

Cite