Finite Stick Breaking Sequences

arXiv:2610.05067 · math.CO · Submitted 2026-10-04 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "Finite Stick Breaking Sequences".

Emmy: Here's the gist of the paper. In this work, finite sequences are considered to prove that an infinite sequence arising from De Bruijn and Erdős is unique in a certain sense This problem addresses the best ratio that can be maintained between the shortest and longest pieces during a stick-breaking process Problem Formulation The core problem investigates what is the best ratio we can maintain at every step when breaking a stick after N breaks This was inspired by a social-distancing experiment concerning how far apart people can sit at a round table Formally, the goal is to keep the ratio ρn(a) = Mn(a)/mn(a) as close to 1 as possible The average stick length after n breaks is 1/n, which is rescaled to unit length for analysis De Bruijn and Erdős Bounds De Bruijn and Erdős proved that the sequence bn = log2(2j−1) (mod 1) has the required property They established two bounds for the scaled maximum and minimum lengths: (1) lim sup n→∞ n·Mn(a) ≥ 1/log 2 and (2) lim inf n→∞ n·mn(a) ≤ 1/2 log 2 Therefore, it is impossible for the ratio ρn(a) to converge to 1, as De Bruijn and Erdős proved that the best possible ratio is 2 Uniqueness of the BET Sequence The paper focuses on proving that the sequence bn = log2(2j−1) (mod 1) is the only greedy stick-breaking sequence satisfying all three strict inequalities (4) These inequalities are: ρn(a) 1/2 log 2 The BET sequence is defined by the breakpoints b j = log2(n + j - 1) (mod 1), possibly in a different order Theorem 7 states that the BET sequence is the unique eventually greedy stick-breaking sequence that satisfies these bounds Finite Sequence Properties The paper investigates finite versions of the problem, defining (2n−1)-BET and 2n-BET sequences based on specific bounds for the maximum and minimum stick lengths Theorem 4 asserts that every (2n−1)-BET sequence has the same stick lengths after n breaks, namely those in (14) Furthermore, there is only one way to produce a 2n-BET sequence and it is greedy Higher Dimensional Extension The authors extend the stick-breaking argument to higher dimensions by considering partitioning a unit square into rectangular tiles Lemma 8 provides a bound for the ratio of the smallest to the largest tile area in this process, showing lim sup N→∞ NMN ≥ 3/log 4 The paper concludes by noting that an analogue of the BET sequence in higher dimensions may already have been discovered The research confirms the optimality of the BET sequence for finite stick-breaking problems The uniqueness proof relies on showing that any deviation from the greedy procedure violates the necessary bounds This work contributes to understanding fair distribution problems and their connections to other mathematical areas The authors acknowledge assistance from ChatGPT in improving the manuscript's wording and discussion of arguments.

Ada: References

1: M.

Emmy: Anholcer, B.

Ada: Bosek, J.

Paper summary: Ada: To recap what we just covered, we looked at "Finite Stick Breaking Sequences" by Brethouwer, Buijsrogge, and Fokkink. They focus on taking the infinite sequence problem from De Bruijn and Erdős and applying it to a finite stick-breaking process. Emmy The core thesis is that they can prove the existence of a unique sequence—the BET sequence—that satisfies three very specific strict inequalities at every step during this finite process.

Kolya: So, what exactly is the BET sequence they’re talking about? Is it just some random order of breaks, or does it have a defined rule behind its construction?

Ada: It's a specific sequence of break points defined by b j = two times two j minus one modulo one <ref:2610.05067#pg2>. Emmy The paper claims this sequence is the only greedy stick-breaking sequence that satisfies those three bounds simultaneously: the ratio being less than two, the scaled maximum length staying below one log two, and the scaled minimum length staying above one over half log two.

Kolya: So they are essentially saying that if you follow this specific rule at every step, you're getting as close as you can possibly get to that ideal ratio of one for a finite number of breaks.

Ada: That’s the implication. They prove that any deviation from this BET sequence immediately violates those necessary bounds they derived earlier in the work. Emmy This sequence is the unique eventually greedy stick-breaking sequence that satisfies those specific bounds, which is what makes it so important to them.

Kolya: From a probabilistic standpoint, what does this uniqueness mean for how we model these division problems? Does it simplify things when we're dealing with random breaks?

Ada: It tells us that even in a process that looks like it could be random, there is an underlying structure—this BET sequence—that dictates the best possible outcome. Emmy It anchors the abstract mathematical bounds to a concrete, deterministic sequence of breaks.

Kolya: So, it moves the needle from "the ratio is bounded" to "this specific process achieves this bound." That’s a clear distinction for practical applications.

Conclusion: Ada: We've been discussing the paper "Finite Stick Breaking Sequences" and its findings. The authors are confirming that the BET sequence is indeed optimal for finite stick-breaking problems. Emmy They’ve proven its uniqueness by showing that any other sequence violates the strict bounds they established, which ties back to those initial results from De Bruijn and Erdős on infinite sequences.

Kolya: So, what does this all mean when you look at the bigger picture? Does this work open up new avenues for understanding fair division problems in general?

Ada: It contributes to understanding fair distribution problems by showing that the optimal structure is not just an abstract idea, but a specific, identifiable sequence of actions. Emmy Plus, they extend this idea to higher dimensions—partitioning a square into rectangular tiles—suggesting that this type of optimal structure might be more general than just the one-dimensional stick problem.

Kolya: So for anyone listening who doesn't deal with discrete sequences, the main point is that for any finite stick breaking scenario, there’s a single best way to break it.

Ada: Exactly. It shows that even under constraints, we can find a specific structure that maximizes our performance in terms of the shortest versus longest pieces.

JAN-TINO BRETHOUWER, ANNE BUIJSROGGE, ROBBERT FOKKINK

Technical University Delft

math.CO

Submitted: 2026-10-04

Updated: 2026-11-03

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 64/100

The gist: In this work, finite stick-breaking sequences are considered to prove that an infinite sequence due to De Bruijn, Erdős…

Key concepts

Ratio ρn(a)
This measures how close the longest stick length (Mn(a)) is to the shortest stick length (mn(a)) after n breaks. The goal is to keep this ratio as close to 1 as possible, but the established bounds show it cannot converge exactly to 1.
BET Sequence
This specific sequence, defined by $b_j = ext{log}_2(n + j - 1) mod 1$, is a greedy stick-breaking sequence that satisfies strict inequalities related to the maximum and minimum stick lengths. The paper proves this sequence is the only one satisfying these conditions.
De Bruijn–Erdős Bounds
These are mathematical limits proven by De Bruijn and Erdős showing that for any infinite sequence, the scaled maximum length ($n imes M_n(a)$) must be at least $1/ ext{log } 2$, and the scaled minimum length ($n imes m_n(a)$) must be at most $1/2 ext{log } 2$. This proves a best possible ratio of 2.
Finite Sequence Properties
The paper examines specific finite versions of the problem, like $(2n-1)$-BET sequences. It finds that for these finite cases, all sequences satisfying the required bounds result in the exact same set of stick lengths after n breaks, and only one way to achieve this is through a greedy procedure.

Terminology

Summary

In this work, finite stick-breaking sequences are considered to prove that an infinite sequence due to De Bruijn, Erdős, and Toulmin is in some sense unique The best possible ratio is 2

Problem Formulation

The problem involves breaking a unit stick into pieces at each step to keep the ratio between the shortest and longest piece as close to 1 as possible The goal is to maintain the ratio ρn(a) = Mn(a)/mn(a) as close to 1 as possible De Bruijn and Erdős proved that for any sequence (a), the best possible ratio is 2 They also established bounds on the scaled maximum and minimum lengths, showing lim sup n→∞ n·Mn(a) ≥ 1/log 2 and lim inf n→∞ n·mn(a) ≤ 1/2 log 2

The BET Sequence

The De Bruijn–Erdős–Toulmin (BET) sequence, defined by bj = log2(2j−1) (mod 1), is the sequence that satisfies all three strict inequalities: ρn(a) 1/2 log 2 This sequence is optimal because Anholcer et al. [1] proved that the BET sequence is optimal The BET sequence can be characterized by stick lengths Mn(b) = log2(1 + 1/n) and mn(b) = -log2(1 - 1/2n)

Uniqueness of Finite Sequences

Theorem 4 states that every (2n−1)-BET sequence has the same stick lengths after n breaks, namely the lengths in (14) This uniqueness is established by showing that the inequalities in Lemma 1 must both be equalities, leading to specific stick length distributions Theorem 5 further proves there is only one way to produce a 2n-BET sequence and it is greedy

Infinite Sequence Characterization

The BET sequence is the unique eventually greedy stick-breaking sequence that satisfies the bounds in (4) This uniqueness stems from Theorem 7, which shows that for every n ≥ N, ln = log2(n + 1)/n The reconstruction of earlier stages by gluing sticks is shown to be unique through induction

Higher Dimensions

The argument extends to higher dimensions, where partitioning a unit square into four tiles at each step yields a limit for the ratio of smallest to largest tile area The resulting lower bound is lim inf N→∞ CN ≥ 3/log 4 However, the paper does not explicitly state an analogue of the BET sequence in higher dimensions

Conclusion

The paper concludes by noting that while the restriction to eventually greedy stick-breaking can be dropped for non-strict inequalities, the BET sequence remains unique under those strict conditions The work also touches upon extensions of stick-breaking to higher dimensions and related problems concerning consecutive sticks

References

[1] M. Anholcer, B. p. 0

Where the paper says it

This problem was introduced and solved by De Bruijn and Erdős [6]. It was revisited by Ramshaw [12] and, more recently, by Anholcer et al.

Bosek, J. Grytczuk, G. Gutowski, J. Przybyło, R. Pyzik, and M. Zając

[2] J. F. Brethouwer, Contemporary Conflicts and Crises: A Mathematical Approach, PhD thesis

[3] A. Buijsrogge, J. p. 0

Where the paper says it

FINITE STICK-BREAKING SEQUENCES JAN-TINO BRETHOUWER, ANNE BUIJSROGGE, AND ROBBERT FOKKINK Abstract. In 1949, De Bruijn and Erdős considered infinite stick-breaking sequences.

-T. Brethouwer, A. p. 0
Where the paper says it

FINITE STICK-BREAKING SEQUENCES JAN-TINO BRETHOUWER, ANNE BUIJSROGGE, AND ROBBERT FOKKINK Abstract. In 1949, De Bruijn and Erdős considered infinite stick-breaking sequences.

van de Rijt, and R. p. 0
Where the paper says it

In a different direction, Kakutani proposed a random stick-breaking process. His conjecture about the distribution of the break points was proved by van Zwet; Pyke and van Zwet later obtained further convergence results [11].

Lindelauf

[4] I. Carbone, M. p. 0

Where the paper says it

His conjecture about the distribution of the break points was proved by van Zwet; Pyke and van Zwet later obtained further convergence results [11]. Carbone, Iaco, and Volčič considered the ergodic properties of Kakutani’s stick-breaking process [4].

R. Iaco, and A. p. 0
Where the paper says it

His conjecture about the distribution of the break points was proved by van Zwet; Pyke and van Zwet later obtained further convergence results [11]. Carbone, Iaco, and Volčič considered the ergodic properties of Kakutani’s stick-breaking process [4].

Volčič

[5] F. Clément and S. p. 0

Where the paper says it

[1], who connected it to a problem of Steinhaus on fair division [14]. De Bruijn and Erdős also considered a more general problem, taken up recently by Clément and Steinerberger and by Korsky [5, 8].

Steinerberger, Balanced stick breaking

[6] N. G. de Bruijn and P. p. 0

Where the paper says it

FINITE STICK-BREAKING SEQUENCES JAN-TINO BRETHOUWER, ANNE BUIJSROGGE, AND ROBBERT FOKKINK Abstract. In 1949, De Bruijn and Erdős considered infinite stick-breaking sequences.

Erdős, Sequences of points on a circle

[7] M. Drmota and M. Infusino, On the discrepancy of some generalized Kakutani’s sequences of partitions

[8] S. Korsky, A resolution of the de Bruijn–Erdös consecutive-gap problem

[9] H. Niederreiter, On a measure of denseness for sequences

[10] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods

[11] R. Pyke and W. p. 0

Where the paper says it

In a different direction, Kakutani proposed a random stick-breaking process. His conjecture about the distribution of the break points was proved by van Zwet; Pyke and van Zwet later obtained further convergence results [11].

R. van Zwet, Weak convergence results for the Kakutani interval splitting procedure

[12] L. Ramshaw, On the gap structure of sequences of points on a circle

[13] L. Spiegelhofer, Discrepancy results for the van der Corput sequence

[14] H. Steinhaus, Sur la division pragmatique

[15], One hundred problems in elementary mathematics, Courier Corporation

[16] G. Toulmin, Subdivision of an interval by a sequence of points

[17] J. G. van der Corput, Verteilungsfunktionen. p. 3

Where the paper says it

The ratio first reaches 2 when there are three sticks, so ρn = 2 for all n ≥ 3. These lengths are the same as those obtained from the classical van der Corput sequence [17], which remains a subject of study today [13].

I. Mitteilung

[18] M.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. stick-breaking optimization for fair division in sequential resource allocation: The system can determine if a sequence of breaks on a unit circle is optimal for keeping the ratio between the shortest and longest piece as close to 1 as possible, mimicking practical problems like social distancing or seat assignment.

  2. identification of unique optimal sequences: The AI can identify the unique De Bruijn-Erdős-Toulmin (BET) sequence, which is the only greedy stick-breaking sequence satisfying all three strict inequalities: The BET sequence is the only greedy stick-breaking sequence satisfying all three strict inequalities.

  3. prediction of performance bounds for finite processes: The system can calculate the exact maximum possible ratio for a given number of breaks N by finding the best possible ratio that can be maintained at every step, using formulas derived from Lemma 1.

  4. construction of optimal finite sequences: The AI can construct specific (2n-1)-BET sequences with fixed maximum lengths by employing the greedy stick-gluing procedure, ensuring that for a given set of initial breaks, the resulting sequence is optimal: Theorem 4. Every (2n-1)-BET sequence has the same stick lengths after n breaks, namely the lengths in (14).

  5. verification of greedy algorithms: The system can verify if a given stick-breaking procedure is greedy by checking if it adheres to the rule: at every step, it breaks a longest stick into two pieces.

  6. analysis of higher dimensional partitioning ratios: The system can predict the limit supremum for the ratio of smallest to largest tile area when partitioning a unit square into four repeatedly, finding that lim sup N→∞ CN ≥ 3/ log 4.

Abstract

In 1949, De Bruijn and Erdős considered infinite stick-breaking sequences. In this work, we consider finite sequences and prove that an infinite sequence that is due to De Bruijn, Erdős, and Toulmin is in some sense unique.

Sources

Related papers