An Improved Lower Bound for the de Bruijn–Erdős Consecutive Gap Problem

Samuel Korsky · 2026

Read An Improved Lower Bound for the de Bruijn–Erdős Consecutive Gap Problem by Samuel Korsky (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30959.txt.

Introduction

Korsky improves a lower bound for the de Bruijn-Erdős gap problem, studying points placed on a unit circle. After n points are placed, the circle splits into n intervals, and largest and smallest r-interval totals are compared. A theorem gives a ratio of at least one plus one over r, sharp at one with factor two. Korsky proves a bound for r at least two: one plus r over r squared minus one. For two intervals, this gives five thirds, improving the classic three halves.

Catalog record

CREATORSamuel Korsky
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE13877
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30959

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Improved Lower Bound for the de Bruijn–Erdős Consecutive Gap Problem Samuel Korsky Abstract Let ( x n ) n ≥ 1 (x_{n})_{n\geq 1} be a sequence of distinct points on the unit circle. After the first n n points are inserted, the circle is divided into n n intervals. For a fixed integer r ≥ 1 r\geq 1 , let M n ( r ) M_{n}^{(r)} and m n ( r ) m_{n}^{(r)} denote respectively the largest and smallest total lengths of r r consecutive intervals. A theorem of de Bruijn and Erdős gives lim sup n → ∞ M n ( r ) m n ( r ) ≥ 1 + 1 r . \limsup_{n\to\infty}\frac{M_{n}^{(r)}}{m_{n}^{(r)}}\geq 1+\frac{1}{r}. The case r = 1 r=1 is sharp and gives the classical factor 2 2 . The cases r ≥ 2 r\geq 2 remain much less understood. We prove the improved lower bound lim sup n → ∞ M n ( r ) m n ( r ) ≥ 1 + r r 2 − 1 ( r ≥ 2 ) . \limsup_{n\to\infty}\frac{M_{n}^{(r)}}{m_{n}^{(r)}}\geq 1+\frac{r}{r^{2}-1}\qquad(r\geq 2). In particular, for two consecutive intervals the lower bound becomes 5 / 3 5/3 , improving the de Bruijn–Erdős bound 3 / 2 3/2 . 1 Introduction Let x_{1},x_{2},x_{3},\ldots be a sequence of distinct points on the circle \mathbb{T}=\mathbb{R}/\mathbb{Z} . After the first n points are inserted, they divide the circle into n intervals. We write these interval lengths in cyclic order as g_{1}^{(n)},g_{2}^{(n)},\ldots,g_{n}^{(n)}. For a positive integer r , define M_{n}^{(r)}=\max_{i}\left(g_{i}^{(n)}+g_{i+1}^{(n)}+\cdots+g_{i+r-1}^{(n)}\right) and m_{n}^{(r)}=\min_{i}\left(g_{i}^{(n)}+g_{i+1}^{(n)}+\cdots+g_{i+r-1}^{(n)}\right), where indices are taken cyclically. Thus M_{n}^{(r)} is the largest length of r consecutive intervals and m_{n}^{(r)} is the smallest length of r consecutive intervals. The problem goes back to de Bruijn and Erdős [ 1 ] . They proved that, for every sequence and every r\geq 1 , \limsup_{n\to\infty}\frac{M_{n}^{(r)}}{m_{n}^{(r)}}\geq 1+\frac{1}{r}. For r=1 , this says that the ratio between the largest and smallest interval length must be arbitrarily close to 2 infinitely often; this is sharp. This case has also recently been revisited from a finite-horizon perspective by DeLeo, Henderschedt, and Wells [ 2 ] . For r\geq 2 , the sharp answer appears to be open. Recent work of Clément and Steinerberger [ 3 ] studies this problem under the name “balanced stick breaking” and constructs sequences for which the corresponding ratio is at most 1+O\left(\frac{\log r}{r}\right). See also the expository slides of Gniecki [ 4 ] for an accessible account of the de Bruijn–Erdős problem and related quantities. The purpose of this note is to give a short improved lower bound. We prove the following. Theorem 1.1 . For every integer r\geq 2 and every sequence of distinct points on \mathbb{T} , \limsup_{n\to\infty}\frac{M_{n}^{(r)}}{m_{n}^{(r)}}\geq 1+\frac{r}{r^{2}-1}. Since \frac{r}{r^{2}-1}=\frac{1}{r}+\frac{1}{r(r^{2}-1)}, this strictly improves the de Bruijn–Erdős lower bound for every r\geq 2 . For r=2 , Theorem 1.1 gives \limsup_{n\to\infty}\frac{M_{n}^{(2)}}{m_{n}^{(2)}}\geq\frac{5}{3}. The proof exploits the local nature of the splitting dynamics: inserting a new point only splits one existing interval, so only the consecutive sums near that interval can change. We show that if the ratio M_{n}^{(r)}/m_{n}^{(r)} is assumed to stay below a fixed \rho , then a split which does not significantly decrease M_{n}^{(r)} creates a protected block of nearby intervals. None of the intervals in this block may be split again until M_{n}^{(r)} has decreased by a definite multiplicative factor. Counting these protected blocks over one multiplicative epoch gives the desired obstruction. 2 Notation and Basic Observations Fix r\geq 2 . Since r remains fixed throughout the proof, we suppress the superscript and write M_{n}=M_{n}^{(r)},\qquad m_{n}=m_{n}^{(r)},\qquad R_{n}=\frac{M_{n}}{m_{n}}. An r -block means a union of r consecutive intervals in the cyclic order. We shall repeatedly use the following elementary observation: Lemma 2.1 . The sequence M_{n} is nonincreasing. Proof. Suppose a gap \ell is split into two gaps x and y , where x+y=\ell . Consider any new r -block after the split. If the new block contains x but not y , then replacing x by \ell gives an old r -block whose length is at least as large. The same applies if the new block contains y but not x . If the new block contains both x and y , then merging them gives an old block with r-1 gaps; extending it by one adjacent old gap gives an old r -block whose length is at least as large. Hence every new r -block has length at most M_{n} , and therefore M_{n+1}\leq M_{n} . ∎ The average length of an r -block is exactly r/n , because each gap is counted in exactly r such blocks. Hence m_{n}\leq\frac{r}{n}\leq M_{n}. In particular, if R_{n}\leq\rho , then M_{n}\leq\rho\cdot\frac{r}{n}. 3 A Protected Block Lemma The next lemma is the local input. It says that a split which does not reduce M_{n} much creates a block of intervals that cannot be touched again until M_{n} has fallen by a definite factor. Throughout this section assume that, from some point onward, R_{n}\leq\rho. The proof of Theorem 1.1 will choose \rho below the claimed lower bound and derive a contradiction. Lemma 3.1 (Protected block) . Fix \eta\in(0,1) and suppose that the step n\to n+1 satisfies M_{n+1}\geq(1-\eta)M_{n} and R_{n+1}\leq\rho. Suppose the split gap is \ell=x+y . After the split, consider the 2r consecutive gaps h_{1},h_{2},\ldots,h_{2r}, where h_{r}=x,\qquad h_{r+1}=y, with r-1 gaps to the left of \ell and r-1 gaps to the right of \ell included. Set q=\frac{1-\eta}{\rho},\qquad\alpha=1-q=\frac{\rho-1+\eta}{\rho}. Then h_{j}\leq\alpha M_{n}\qquad(1\leq j\leq 2r). Moreover, suppose that at a later time T one of the gaps h_{j} is split, and that no gap among h_{1},\ldots,h_{2r} has been split before time T . If R_{T}\leq\rho , then M_{T}\leq\beta M_{n},\qquad\beta=(r-1)(\rho-1+\eta). Proof. First we prove ( 3.1 ). Since M_{n+1}\geq(1-\eta)M_{n} and R_{n+1}\leq\rho , we have m_{n+1}\geq\frac{M_{n+1}}{\rho}\geq\frac{1-\eta}{\rho}\cdot M_{n}=qM_{n}. Therefore every r -block after the split has length at least qM_{n} . For 1\leq i\leq r+1 , define the r -blocks W_{i}=h_{i}+h_{i+1}+\cdots+h_{i+r-1}. Then W_{i}\geq qM_{n}\qquad(1\leq i\leq r+1). For 1\leq i\leq r , define U_{i}=h_{i}+h_{i+1}+\cdots+h_{i+r}. Each U_{i} contains both x and y . If we merge x+y back into the old gap \ell , then U_{i} becomes an old r -block. Hence U_{i}\leq M_{n}\qquad(1\leq i\leq r). For 1\leq j\leq r , h_{j}=U_{j}-W_{j+1}\leq M_{n}-qM_{n}=\alpha M_{n}. For r+1\leq j\leq 2r , h_{j}=U_{j-r}-W_{j-r}\leq M_{n}-qM_{n}=\alpha M_{n}. This proves ( 3.1 ). Now suppose h_{j} is the first gap among the marked gaps to be split at time T . Since all other marked gaps are still intact just before time T , after the split of h_{j} there is an r -block consisting of the two pieces of h_{j} together with r-2 adjacent marked gaps. Its total length is at most (r-1)\alpha M_{n}. Thus m_{T}\leq(r-1)\alpha M_{n}. If also R_{T}\leq\rho , then M_{T}\leq\rho m_{T}\leq\rho(r-1)\alpha M_{n}=(r-1)(\rho-1+\eta)M_{n}. This is ( 3.1 ). ∎ The interpretation is that the marked block created at a slow split (a split that does not decrease M_{n} substantially) is frozen until M_{n} has fallen by the multiplicative factor \beta . 4 Counting Protected Blocks We now convert Lemma 3.1 into a global obstruction. Assume that R_{n}\leq\rho for all sufficiently large n . Choose \eta>0 and define \beta=(r-1)(\rho-1+\eta). We shall eventually choose \rho and \eta so that \beta<\frac{r}{r+1}. Call a step n\to n+1 slow if M_{n+1}\geq(1-\eta)M_{n}, and fast

Read the complete text