A finite victory over de Bruijn-Erd\H{o}s in interval discrepancy

Chris Wells; Jared DeLeo; Owen Henderschedt

arxiv: 2605.29166 · v1 · pith:TXMFJOX3new · submitted 2026-05-27 · 🧮 math.CO

A finite victory over de Bruijn-ErdH{o}s in interval discrepancy

Jared DeLeo , Owen Henderschedt , Chris Wells This is my paper

Pith reviewed 2026-06-29 11:00 UTC · model grok-4.3

classification 🧮 math.CO

keywords interval discrepancylex-mergede Bruijn-Erdősdisc(n)interval splittingdiscrepancy boundsfinite discrepancy

0 comments

The pith

Lex-merge improves the finite interval discrepancy upper bound to 2 minus 4 ln 2 over n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies repeated splitting of the unit interval until n subintervals result, with discrepancy defined as the maximum ratio of longest to shortest interval across all stages of the process. de Bruijn and Erdős showed that any such process must have this ratio tend to 2, and gave a construction achieving an upper bound of 2 minus 3 over 2n plus higher-order terms. The authors define the lex-merge strategy and prove it yields the stronger upper bound 2 minus 4 ln 2 over n plus O of 1 over n squared. They complement this with a lower bound of 2 minus 6 ln 2 over n minus O of 1 over n squared, establishing that the first-order improvement has the correct magnitude. The authors conjecture that lex-merge achieves the minimal possible discrepancy for every finite n.

Core claim

The lex-merge strategy for successively splitting intervals satisfies disc(n) ≤ 2 − (4 ln 2)/n + O(1/n²), while every splitting process satisfies the matching-order lower bound disc(n) ≥ 2 − (6 ln 2)/n − O(1/n²). This refines the de Bruijn–Erdős upper bound of 2 − 3/(2n) + O(1/n²) by replacing the coefficient 3/2 with 4 ln 2 ≈ 2.77 and shows that the leading correction term after the constant 2 must be of size Θ((ln 2)/n).

What carries the argument

the lex-merge strategy, a specific rule for choosing which interval to split at each step that controls the evolution of length ratios

If this is right

Any splitting process has disc(n) at least 2 − 6 ln 2 / n minus O(1/n²).
The lex-merge process has disc(n) at most 2 − 4 ln 2 / n plus O(1/n²).
The difference 2 − disc(n) is Θ((ln 2)/n) rather than Θ(1/n).
If the conjecture holds, lex-merge realizes the exact minimal disc(n) for each finite n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Numerical simulation of lex-merge for moderate n could determine the constant term in the O(1/n²) expansion.
The same splitting rule might be adapted to produce low-discrepancy partitions in higher dimensions or on other measure spaces.
The gap between the 4 ln 2 and 6 ln 2 coefficients leaves room for a tighter asymptotic constant if a different strategy exists.

Load-bearing premise

The lex-merge rule can be defined explicitly and its maximum observed ratio across all stages satisfies the stated upper bound.

What would settle it

Explicit computation of all successive length ratios under the lex-merge rule for some n larger than 1000, yielding a maximum ratio larger than 2 − 4 ln 2 / n plus a reasonable multiple of 1/n².

Figures

Figures reproduced from arXiv: 2605.29166 by Chris Wells, Jared DeLeo, Owen Henderschedt.

read the original 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\H{o}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 $\text{disc}(n)\leq 2-\frac{3}{2n}+O(1/n^2)$. In this paper, we improve the first-order term of this bound. Specifically, we construct a strategy, called \emph{lex-merge}, with $\text{disc}(n)\leq 2-\frac{4\ln 2}{n}+O(1/n^2)$. We prove also the lower bound $\text{disc}(n)\geq 2-\frac{6\ln 2}{n}-O(1/n^2)$, showing that the first-order term in this improvement over the de Bruijn--Erd\H{o}s construction has the correct order of magnitude. We conjecture that the lex-merge strategy is optimal for every $n$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper improves the 1/n coefficient in the classic de Bruijn-Erdős interval discrepancy bound from 3/2 to 4 ln 2 via an explicit lex-merge construction, with a separate lower bound of order 6 ln 2 showing the improvement is the right magnitude.

read the letter

The main point is that they beat the 1949 construction on the finite-n version of the problem. Their lex-merge strategy produces a sequence of splits where the longest-to-shortest ratio stays below 2 - 4 ln 2 / n plus lower-order terms, which is a clear step up from the earlier 3/(2n) coefficient. They also prove a matching lower bound of 2 - 6 ln 2 / n minus O(1/n²), so the first-order improvement is not an artifact of loose analysis.

The construction itself is deterministic and explicit, which is useful. The analysis appears to rest on a recurrence for the discrepancy under lex-merge together with a continuum approximation that controls the error terms. The lower-bound argument is independent and uses a different counting or potential method. No circularity shows up in the structure, and the constants come out cleanly from the logs.

The gap between the 4 ln 2 upper and 6 ln 2 lower coefficients is the obvious soft spot; it leaves open whether lex-merge is truly optimal or whether a better strategy exists. They conjecture optimality but do not close the gap. The O(1/n²) remainder is stated but not expanded in detail, which is minor for an asymptotic result but worth a referee check.

This is aimed at people working in combinatorial discrepancy who want concrete finite-n improvements rather than asymptotic existence results. The evidence is grounded enough—an explicit construction plus separate lower bound—to merit a serious referee. I would send it to peer review.

Referee Report

0 major / 3 minor

Summary. The paper studies the finite-n version of the interval discrepancy problem, in which one starts with the unit interval and repeatedly splits intervals until n intervals are obtained. The discrepancy disc(n) is the maximum ratio of longest to shortest interval over all prefixes of the process. The authors introduce an explicit strategy called lex-merge and prove the improved upper bound disc(n) ≤ 2 − (4 ln 2)/n + O(1/n²), together with the matching-order lower bound disc(n) ≥ 2 − (6 ln 2)/n − O(1/n²). They conjecture that lex-merge is optimal for every n.

Significance. If the stated bounds hold, the result sharpens the first-order correction to the classical de Bruijn–Erdős limit of 2. The explicit construction together with a separate lower-bound argument that recovers the correct coefficient (up to the constant factor 4 versus 6) constitutes a substantive finite-n improvement. The manuscript supplies the definition of the strategy, the governing recurrence, and the asymptotic analysis controlling the error terms; these elements allow direct verification of the claimed coefficients.

minor comments (3)

The O(1/n²) remainder in the upper bound (lex-merge analysis) and the lower bound are stated with the same notation but arise from different approximations; a short remark clarifying whether the implied constants are independent of the strategy would remove any ambiguity.
Figure 1 (or the first illustrative figure) compares the lex-merge ratios with the de Bruijn–Erdős construction; the caption should explicitly state the range of n shown and whether the plotted values are exact or computed via the recurrence.
The conjecture that lex-merge is optimal for every finite n is stated at the end of the abstract and again in the conclusion; a brief sentence indicating the computational evidence (if any) supporting the conjecture for small n would strengthen the claim without altering the main theorems.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, which correctly summarizes our main contributions on the finite-n interval discrepancy problem, the lex-merge construction, and the matching-order lower bound. We note the recommendation of minor revision and will make any editorial adjustments required.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents an explicit construction (lex-merge) whose definition and recurrence are stated directly, followed by an independent asymptotic analysis that produces the coefficient 4 ln 2 in the upper bound and a separate lower-bound argument that produces 6 ln 2. Neither coefficient is obtained by fitting a parameter to data and then relabeling the fit as a prediction, nor does any load-bearing step reduce to a self-citation whose content is itself unverified. The de Bruijn–Erdős theorem is invoked only as an external benchmark whose construction is improved upon; the improvement itself is derived from the new strategy and its analysis. The derivation chain is therefore self-contained against the stated assumptions and does not collapse by construction to its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence and discrepancy analysis of the lex-merge strategy, which is introduced but not described in the abstract; no free parameters, invented entities, or non-standard axioms are mentioned.

axioms (1)

standard math Standard real-number properties of interval lengths and binary splitting operations
The problem is defined on the unit interval with repeated splits; this is background mathematics.

pith-pipeline@v0.9.1-grok · 5780 in / 1252 out tokens · 56204 ms · 2026-06-29T11:00:41.989800+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

An Improved Lower Bound for the de Bruijn--Erd\H{o}s Consecutive Gap Problem
math.CO 2026-05 unverdicted novelty 6.0

Improved lower bound of 1 + r/(r²-1) on limsup M_n^{(r)}/m_n^{(r)} for r≥2 in the de Bruijn-Erdős consecutive gap problem.

Reference graph

Works this paper leans on

6 extracted references · cited by 1 Pith paper

[1]

Balanced stick breaking, 2025

Fran¸ cois Cl´ ement and Stefan Steinerberger. Balanced stick breaking, 2025

2025
[2]

N. G. de Bruijn and P. Erd˝ os. Sequences of points on a circle.Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam, 52:14–17, 1949

1949
[3]

On the equitable distribution of points on the circle

Hamza Barakat Habib. On the equitable distribution of points on the circle. PhD thesis, University of Wollongong, July 2014

2014
[4]

Springer-Verlag, Berlin, 1999

Jiˇ r´ ı Matouˇ sek.Geometric Discrepancy, volume 18 ofAlgorithms and Combinatorics. Springer-Verlag, Berlin, 1999. An illustrated guide

1999
[5]

On the gap structure of sequences of points on a circle.Indagationes Mathematicae (Proceedings), 81(1):527–541, 1978

Lyle Ramshaw. On the gap structure of sequences of points on a circle.Indagationes Mathematicae (Proceedings), 81(1):527–541, 1978

1978
[6]

van Ravenstein

T. van Ravenstein. Optimal spacing of points on a circle.The Fibonacci Quarterly, 27(1):18–24, 1989. 17

1989

[1] [1]

Balanced stick breaking, 2025

Fran¸ cois Cl´ ement and Stefan Steinerberger. Balanced stick breaking, 2025

2025

[2] [2]

N. G. de Bruijn and P. Erd˝ os. Sequences of points on a circle.Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam, 52:14–17, 1949

1949

[3] [3]

On the equitable distribution of points on the circle

Hamza Barakat Habib. On the equitable distribution of points on the circle. PhD thesis, University of Wollongong, July 2014

2014

[4] [4]

Springer-Verlag, Berlin, 1999

Jiˇ r´ ı Matouˇ sek.Geometric Discrepancy, volume 18 ofAlgorithms and Combinatorics. Springer-Verlag, Berlin, 1999. An illustrated guide

1999

[5] [5]

On the gap structure of sequences of points on a circle.Indagationes Mathematicae (Proceedings), 81(1):527–541, 1978

Lyle Ramshaw. On the gap structure of sequences of points on a circle.Indagationes Mathematicae (Proceedings), 81(1):527–541, 1978

1978

[6] [6]

van Ravenstein

T. van Ravenstein. Optimal spacing of points on a circle.The Fibonacci Quarterly, 27(1):18–24, 1989. 17

1989