A finite victory over de Bruijn-Erdős in interval discrepancy

Abstract

We study a finite form of the classical interval discrepancy problem. Starting from the unit interval, one repeatedly splits an existing interval into two until $n$ intervals have been produced. The discrepancy of such a process is the maximum, over all intermediate stages, of the ratio between the longest interval and the shortest interval. A theorem of de Bruijn and Erdős from 1949 shows that this ratio must approach $2$ as $n\to \infty$, and they give a sharp construction achieving this bound. For fixed $n$, their construction gives the upper bound $\mathrm{disc}(n)\le 2-\frac{3}{2n}+O\left(\frac{1}{n^2}\right)$. In this paper, we prove that $\mathrm{disc}(n)=2^{1-1/\lceil n/2\rceil }=2-\frac{4\ln 2}{n}+O\left(\frac{1}{n^2}\right)$ for every $n$.

Added an improved lower bound showing tightness of the lex-merge algorithm