Optimal Finite Interval Discrepancy via Binary Refinement

Abstract

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.

6 pages; Isabelle/HOL formalization available at https://doi.org/10.5281/zenodo.21856255