The sharp support–concentration bound for subset sums
Let $n \ge 1$, let $w = (w_1, \dots, w_n) \in \mathbb{R}^n$, where weights may be repeated, negative or zero, and let $S_w = \sum_{i=1}^n w_i X_i$ with $X_1, \dots, X_n$ independent and uniform on $\{0, 1\}$. Let $N(w)$ be the number of distinct values of $S_w$, the distinct subset sums, and $\rho(w) = \max_{t \in \mathbb{R}} \mathbb{P}(S_w = t)$; equivalently $\rho(w) = 2^{-n} M(w)$, where $M(w)$ is the largest number of subsets of $\{1, \dots, n\}$ with a common sum. In terms of the Rényi entropies $H_0(S_w) = \log N(w)$ and $H_\infty(S_w) = -\log \rho(w)$, the inequality $N(w)\rho(w)^2 \le 1$ reads $H_0(S_w) \le 2 H_\infty(S_w)$. For $w = (1, \dots, 1)$, $N(w) = n + 1$ and $\rho(w) = 2^{-n}\binom{n}{\lfloor n/2 \rfloor}$, so $H_0(S_w)/H_\infty(S_w) \to 2$ as $n \to \infty$. Nederlof, Pawlewicz, Swennenhuis and Węgrzycki showed that $\rho(w) \ge 2^{-\varepsilon n}$ implies $N(w) \le 2^{\delta(\varepsilon) n}$ with $\delta(\varepsilon) \to 0$ as $\varepsilon \to 0$, for an algorithm for bin packing with a fixed number of bins. Jain, Sah and Sawhney proved that $\rho(w) \ge e^{-\varepsilon n}$ implies $N(w) \le e^{C\sqrt{\varepsilon}\, n}$ for $n \ge \varepsilon^{-1/2}$, with $C$ an absolute constant. Li proved, for $w$ with $m \ge 1$ nonzero weights, $$H_0(S_w) \le \min\Bigl\{\log_2(m + 1),\ 2 + \log_2\frac{m \log 2}{H_\infty(S_w)}\Bigr\}\, H_\infty(S_w).$$
Problem. Is $N(w)\rho(w)^2 \le 1$, that is $H_0(S_w) \le 2 H_\infty(S_w)$, for every $n \ge 1$ and every $w \in \mathbb{R}^n$?
Source: Jain, Sah and Sawhney (2021), the conjecture δ(ε) ≤ 2ε following their Question 1.1; in this exact form, Li (2026), Conjecture 1.1, communicated to Li by Madiman.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO, IT
- Keywords
- AIM Open Applied Problems, anticoncentration, Rényi entropies, subset sums
References
@article{jain2021,
author = {Jain, Vishesh and Sah, Ashwin and Sawhney, Mehtaab},
title = {Anticoncentration versus the number of subset sums},
journal = {Adv. Comb.},
year = {2021},
pages = {Paper No. 6, 10 pp.},
doi = {10.19086/aic.24872},
eprint = {2101.07726},
archivePrefix = {arXiv},
}
@misc{li2026,
author = {Li, Jiange},
title = {Multiplicative comparisons of {R}{\'e}nyi entropies for weighted {B}ernoulli sums},
year = {2026},
eprint = {2609.01529},
archivePrefix = {arXiv},
}
@article{nederlof2023,
author = {Nederlof, Jesper and Pawlewicz, Jakub and Swennenhuis, C{\'e}line M. F. and W{\k{e}}grzycki, Karol},
title = {A faster exponential time algorithm for bin packing with a constant number of bins via additive combinatorics},
journal = {SIAM J. Comput.},
volume = {52},
number = {6},
year = {2023},
pages = {1369--1412},
doi = {10.1137/22M1478112},
eprint = {2007.08204},
archivePrefix = {arXiv},
}
@misc{aim-subset-sum-support-concentration,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The sharp support–concentration bound for subset sums}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/345-subset-sum-support-concentration.md},
note = {Entry 345 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00308, "The sharp support–concentration bound for subset sums", clopen.solutions.