Metraipolis › archive › dc_620f12d52b2d
Optimal Finite Interval Discrepancy via Binary Refinement — arXiv:2608.08431
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.08431
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T09:08:53.654Z
- SHA-256 of the archived text
8d3549bcf6b83f4ef40aff0ca13d188b76eeaa664aaf93791fe9772ac35708a3- Stable URL of this page
https://metraipolis.com/documento/dc_620f12d52b2d
How to cite
Optimal Finite Interval Discrepancy via Binary Refinement — arXiv:2608.08431 — arXiv (en), https://arxiv.org/abs/2608.08431 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_620f12d52b2d (Metraipolis archive dc_620f12d52b2d, sha256 8d3549bcf6b83f4ef40aff0ca13d188b76eeaa664aaf93791fe9772ac35708a3)
BibTeX
@misc{dc620f12d52b2d,
title = {Optimal Finite Interval Discrepancy via Binary Refinement — arXiv:2608.08431},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.08431},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_620f12d52b2d; sha256 8d3549bcf6b83f4ef40aff0ca13d188b76eeaa664aaf93791fe9772ac35708a3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.08431. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
DeLeo, Henderschedt, and Wells introduced a finite-horizon version of the classical de Bruijn--Erdos interval discrepancy problem. Starting from the unit interval, one repeatedly splits an existing interval into two until $n$ intervals are present, and one minimizes the largest ratio between the longest and shortest intervals over all intermediate partitions. They constructed the lex-merge strategy, whose discrepancy is $2^{1-1/\lceil n/2\rceil}$, and conjectured that this value is optimal for every $n$. We prove the conjecture. More generally, we establish a sharp lower bound for arbitrary binary refinement processes of positive masses: any process that starts with one positive mass, repeatedly replaces one mass by two positive masses with the same total, and terminates with $n$ masses must at some stage have largest-to-smallest ratio at least $2^{1-1/\lceil n/2\rceil}$. The proof tracks the minimum mass under refinement and uses the forced survival of a piece near the midpoint of the process. We also record the corresponding universal lower bound for $r$-ary refinements.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.08431 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:05:33.557Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).