Skip to content
DraconiticResearch
Search Sources API
203,948 studies31 sourcesUpdated 23 min ago
PreprintCC BY-NC-SA 4.0arXiv

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

  • Jared DeLeo
  • Owen Henderschedt
  • Chris Wells
Open at sourcePDFDOICite

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→∞, and they give a sharp construction achieving this bound. For fixed n, their construction gives the upper bound disc(n)≤ 2−3/2n+O(1/n2). In this paper, we prove that disc(n)=21−1/⌈ n/2⌉=2−(4ln 2)/n+O(1/n2) for every n.

Related

  1. A Resolution of the de Bruijn--Erdős Consecutive-Gap Problem
    Samuel Korsky
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. The Erdős--Ginzburg--Ziv theorem for finite groups
    Yongke Qu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Generalized Erdős--Ginzburg--Ziv Constants for finite abelian groups of rank three
    Hanbin Zhang, Shiwen Zhang
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. DL, DQ Spectrum and Eigenvalue-free Interval of Cayley Graphs over Finite Nilpotent Groups
    Pallabi Manna, Santanu Mandal
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  5. Concatenation trees: A framework for efficient universal cycle and de Bruijn sequence constructions
    Joe Sawada, Jackson Sears, A. Trautrim +1
    Discrete Applied MathematicsPeer-reviewedLicence not statedFull text6 citedCombinatorics & discrete mathematicsOpenAlex

Cite

BibTeXRIS
BibTeX
@misc{deleo2026finite,
  title = {{A finite victory over de Bruijn-Erdős in interval discrepancy}},
  author = {Jared DeLeo and Owen Henderschedt and Chris Wells},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2605.29166},
  eprint = {2605.29166},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.29166},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - A finite victory over de Bruijn-Erdős in interval discrepancy
AU  - Jared DeLeo
AU  - Owen Henderschedt
AU  - Chris Wells
PY  - 2026
DA  - 2026/09/24
PB  - arXiv
DO  - 10.48550/arxiv.2605.29166
UR  - https://arxiv.org/abs/2605.29166
AB  - 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→∞, and they give a sharp construction achieving this bound. For fixed n, their construction gives the upper bound disc(n)≤ 2−3/2n+O(1/n^2). In this paper, we prove that disc(n)=2^1−1/⌈ n/2⌉=2−(4ln 2)/n+O(1/n^2) for every n.
ER  -