EP43

EP43: Euclidean Rhythms

Bjorklund Algorithm, Burnside's Lemma, and Necklace Equivalence

▶ 3:45 CombinatoricsNumber TheoryMusicology

前置知识

EP04 All-Interval Rows and ℤ₁₂ EP13 Polyrhythm and Rhythm-Pitch Duality

Overview / 概述

In 1999, Bjorklund published a timing algorithm for particle accelerator beam extraction at the Spallation Neutron Source. Five years later, musicologist Godfried Toussaint noticed that the algorithm’s outputs — binary sequences designed to distribute pulses as evenly as possible — exactly reproduced traditional rhythms from Cuba, West Africa, South India, and Brazil. The same Euclidean division that computes greatest common divisors encodes three thousand years of percussion.

This episode develops the mathematics from three angles. First, the Bjorklund algorithm is shown to be a direct realization of the Euclidean algorithm on binary sequences: remainder groups are iteratively appended until a single group remains, at each step mirroring the quotient-remainder structure of integer division. Second, the algorithm is verified against a table of world-music rhythms, showing that E(k, n) — the Euclidean rhythm placing k beats in n positions — reproduces the tresillo (Cuba), quintillo (Cuba), standard bell pattern (West Africa), and samba (Brazil). Third, Burnside’s lemma — the same counting tool used in EP04 for chord equivalence under transposition — is applied to rotation equivalence of binary necklaces of length n, yielding the exact count of distinct rhythmic patterns.

中文: “一九九九年，一个为粒子加速器写的定时算法，被音乐学家发现精确复现了三千年前非洲和古巴的传统鼓点。同一套辗转相除，连接核物理和古老节奏。”

The mathematical core is a single observation: uniform distribution under integer constraints forces the Euclidean algorithm. Whether the domain is neutron beam timing or drum patterns, the optimal even-placement problem has only one combinatorial solution, and finding it algorithmically requires exactly the structure of iterated subtraction.

Prerequisites / 前置知识

Euclidean Algorithm and GCD (EP13) — the iterated subtraction and remainder structure that the Bjorklund algorithm mirrors step-by-step
All-Interval Rows and ℤ₁₂ (EP04) — Burnside’s lemma applied to chord equivalence under cyclic group action; the same framework applies here to rotation equivalence of rhythm necklaces

Definitions

Definition 43.1 (Binary Rhythm Sequence)

A binary rhythm sequence of length $n$ with $k$ beats is a word $s \in \{0, 1\}^n$ with exactly $k$ ones (beats) and $n - k$ zeros (rests). The sequence is interpreted cyclically: position $i$ wraps to position $i \bmod n$ .

Example. The tresillo is the sequence $s = (1, 0, 0, 1, 0, 0, 1, 0)$ , with $n = 8$ , $k = 3$ , and inter-beat gaps $(3, 3, 2)$ .

Definition 43.2 (Euclidean Rhythm E(k, n))

The Euclidean rhythm $E(k, n)$ is the binary rhythm sequence of length $n$ with $k$ beats whose inter-beat gap sequence is as uniform as possible — that is, the gaps take at most two distinct values, differing by at most 1, and are distributed as evenly as possible around the cycle.

Formally, $E(k, n)$ is the output of the Bjorklund algorithm (Definition 43.3) applied to $k$ ones and $n - k$ zeros.

Example. $E(3, 8) = (1, 0, 0, 1, 0, 0, 1, 0)$ . Gaps are $\lfloor 8/3 \rfloor = 2$ or $\lceil 8/3 \rceil = 3$ , distributed as evenly as possible.

Non-example. Placing beats at positions 0, 1, 2 gives gaps $(1, 1, 6)$ , which is not Euclidean — the gaps are not as uniform as possible.

Definition 43.3 (Bjorklund Algorithm)

The Bjorklund algorithm constructs $E(k, n)$ by iterative redistribution:

Input: $k$ ones (majority group) and $r_0 = n - k$ zeros (minority group).

Step 0: Form $k$ groups of the form $[1]$ and $r_0$ groups of the form $[0]$ .

Iteration: While there are two or more distinct group types with count > 1:

Let $a$ = count of majority group, $b$ = count of minority group.
Append one minority group to each majority group: form $\min(a, b)$ new majority groups by concatenation.
The remainder $|a - b|$ groups become the new minority.

Output: Concatenate all final groups to read off the sequence.

This mirrors the Euclidean algorithm: the sizes $a, b$ follow the same quotient-remainder reduction as integer $\gcd(k, n)$ computation.

Worked example for E(3, 8):

Step 0: Three groups $[1]$ , five groups $[0]$ .
Round 1: Append one $[0]$ to each $[1]$ : three groups $[1,0]$ , remainder two groups $[0]$ .
Round 2: Append one $[1,0]$ to each of the two $[0]$ : two groups $[0,1,0]$ , remainder one group $[1,0]$ .
Single minority group remains. Concatenate: $[0,1,0] \; [0,1,0] \; [1,0]$ .
Flatten and rotate to start on a beat: $(1, 0, 0, 1, 0, 0, 1, 0)$ . $\square$

Definition 43.4 (Rhythm Necklace (Rotation Equivalence))

Two binary rhythm sequences $s, s' \in \{0, 1\}^n$ are rotation-equivalent if $s'$ is a cyclic rotation of $s$ :

$s \sim s' \iff \exists \; r \in \{0, 1, \ldots, n-1\} \text{ such that } s'_i = s_{(i+r) \bmod n} \text{ for all } i$

A rhythm necklace is an equivalence class under this relation. Musically, two rhythms in the same necklace class are identical up to where the cycle begins — they sound the same in a loop.

Example. The tresillo $(1,0,0,1,0,0,1,0)$ and $(0,1,0,0,1,0,0,1)$ (shifted by one position) are in the same necklace class.

Main Theorems / 主要定理

Theorem 43.1 (Bjorklund–Euclidean Correspondence)

The Bjorklund algorithm on input $(k, n)$ terminates in exactly $\lfloor \log_\phi n \rfloor$ rounds (where $\phi$ is the golden ratio), and the sequence of majority/minority counts at each round is identical to the quotient-remainder sequence produced by the Euclidean algorithm computing $\gcd(k, n-k)$ .

In particular, $E(k, n)$ is well-defined (the algorithm always terminates with one group), and the resulting pattern has inter-beat gaps taking values $\lfloor n/k \rfloor$ and $\lceil n/k \rceil$ only.

Proof.

At each round, let the majority count be $a$ and minority count be $b$ with $a \geq b$ . After one round, the new majority count is $b$ and the new minority count is $a - b$ . This is precisely the step $(a, b) \mapsto (b, a \bmod b)$ of the Euclidean algorithm: the pair $(a, b)$ decreases by the same rule that reduces $\gcd(a, b)$ . Since the Euclidean algorithm terminates at $\gcd(a, b)$ after $O(\log \min(a,b))$ steps, the Bjorklund algorithm terminates in the same number of rounds, ending with one group when the minority reaches zero.

For the gap claim: the algorithm never produces gaps outside $\{\lfloor n/k \rfloor, \lceil n/k \rceil\}$ because at every step the redistribution preserves total length and spreads the minority elements as evenly as possible across the majority groups. The exact argument is an induction on the number of rounds: the base case (one round with $b \leq a$ ) produces groups of size $q$ or $q+1$ , and this two-value property is preserved at each concatenation step. $\square$

Theorem 43.2 (Fixed-Point Count for Cyclic Rotations)

Let $X = \{0, 1\}^n$ be the set of all binary sequences of length $n$ , and let the cyclic group $\mathbb{Z}_n$ act on $X$ by rotation. The number of sequences in $X$ fixed by rotation by $r$ positions is:

$|X^r| = 2^{\gcd(r, n)}$

That is, a binary sequence of length $n$ is invariant under rotation by $r$ if and only if it consists of repetitions of a base block of length $\gcd(r, n)$ .

Proof.

Rotation by $r$ sends position $i$ to position $(i + r) \bmod n$ . A sequence $s$ is fixed if and only if $s_i = s_{(i+r) \bmod n}$ for all $i$ . This means $s$ is constant on each orbit of the permutation $i \mapsto (i + r) \bmod n$ .

The orbit of position 0 under this permutation has size $\text{ord}_n(r) = n / \gcd(r, n)$ . Every orbit has the same size, so there are exactly $\gcd(r, n)$ distinct orbits. A fixed sequence must be constant on each orbit, so it is determined by choosing one binary value per orbit. Therefore the number of fixed sequences is $2^{\gcd(r, n)}$ . $\square$

Theorem 43.3 (Burnside Count of Rhythm Necklaces)

The number of distinct binary rhythm necklaces of length $n$ (over all beat counts $k = 0, 1, \ldots, n$ ) is:

$\frac{1}{n} \sum_{r=0}^{n-1} 2^{\gcd(r, n)}$

For $n = 8$ : the number of distinct necklaces is $\dfrac{1}{8}(2^8 + 2^1 + 2^2 + 2^1 + 2^4 + 2^1 + 2^2 + 2^1) = \dfrac{288}{8} = 36$ .

Proof.

By Burnside’s lemma (Cauchy–Frobenius lemma), the number of equivalence classes under a group action equals the average number of fixed points:

$|X / \mathbb{Z}_n| = \frac{1}{|\mathbb{Z}_n|} \sum_{g \in \mathbb{Z}_n} |X^g| = \frac{1}{n} \sum_{r=0}^{n-1} |X^r|$

Substituting $|X^r| = 2^{\gcd(r, n)}$ from Theorem 43.2 gives the formula. For $n = 8$ , the values $\gcd(r, 8)$ for $r = 0, 1, \ldots, 7$ are $8, 1, 2, 1, 4, 1, 2, 1$ , so the fixed-point counts are $256, 2, 4, 2, 16, 2, 4, 2$ , summing to $288$ . Dividing by $8$ gives $36$ necklaces. $\square$

Prop 43.1 (Uniqueness of E(k,n) in its Necklace Class)

Among all necklaces of length $n$ with exactly $k$ beats, the Euclidean rhythm $E(k, n)$ is the unique necklace class whose inter-beat gap sequence takes only the two values $\lfloor n/k \rfloor$ and $\lceil n/k \rceil$ .

In particular, for $n = 8$ , $k = 3$ : among the 7 distinct necklace classes with exactly 3 beats, the tresillo $E(3, 8)$ is the unique maximally-even one.

Proof.

Suppose two distinct necklace classes both have inter-beat gaps in

\{\lfloor n/k \rfloor, \lceil n/k \rceil\}

. Then they differ only in the arrangement of the two gap values. But the number of each gap value is fixed: if there are

a

long gaps (

\lceil n/k \rceil

) and

b = k - a

short gaps, the total is

a\lceil n/k \rceil + b\lfloor n/k \rfloor = n

, which uniquely determines

a = n \bmod k

. Two sequences with the same gap multiset are cyclic rotations of each other (by a Lyndon-word argument: the Euclidean sequence is the lexicographically smallest rotation), hence in the same necklace class.

\square

Numerical Examples

Tracing E(3, 8) step by step:

The Bjorklund algorithm applied to 3 ones and 5 zeros:

Round	Majority groups	Count	Minority groups	Count
0	$[1]$	3	$[0]$	5
1	$[1,0]$	3	$[0]$	2
2	$[1,0,0]$	2	$[1,0]$	1
Done	—	—	one group remains	—

Concatenate in order: $[1,0,0] \; [1,0,0] \; [1,0]$ , yielding $(1,0,0,1,0,0,1,0)$ .

The parallel with $\gcd(3, 5)$ : the count pairs are $(3,5) \to (3,2) \to (2,1) \to (1,0)$ , precisely the Euclidean algorithm steps.

Burnside computation for n = 8:

$\gcd(0,8)=8, \quad \gcd(1,8)=1, \quad \gcd(2,8)=2, \quad \gcd(3,8)=1$ $\gcd(4,8)=4, \quad \gcd(5,8)=1, \quad \gcd(6,8)=2, \quad \gcd(7,8)=1$

\frac{1}{8}\bigl(2^8 + 2^1 + 2^2 + 2^1 + 2^4 + 2^1 + 2^2 + 2^1\bigr) = \frac{256 + 2 + 4 + 2 + 16 + 2 + 4 + 2}{8} = \frac{288}{8} = 36

So there are 36 distinct binary necklaces of length 8 in total (across all beat counts k = 0 through 8).

Counting with exactly k = 3 beats:

By direct enumeration, $\binom{8}{3} = 56$ sequences with 3 beats, falling into 7 distinct necklace classes. Of these 7 classes, only the tresillo $E(3,8)$ satisfies the maximally-even property.

中文: “代入长度八：不动点个数分别是二的八、一、二、一、四、一、二、一次方。求和二百八十八除以八等于三十六。旋转等价下三十六种项链——这是所有重拍数的总计。其中恰好含三个重拍的，直接枚举有七种，最均匀的只有一种：特雷西洛。”

Musical Connection / 音乐联系

音乐联系

E(k, n) and World Percussion

The Euclidean algorithm does not merely approximate traditional rhythms — it reproduces them exactly (up to rotation). Toussaint (2005) documents over twenty correspondences. The most prominent:

Pattern	Sequence	Tradition
E(3, 8)	(1,0,0,1,0,0,1,0)	Cuban tresillo — the foundational rhythm of son, salsa, and jazz
E(5, 8)	(1,0,1,1,0,1,1,0)	Cuban quintillo; also the West African standard bell pattern
E(7, 12)	(1,0,1,1,0,1,0,1,1,0,1,0)	West African standard bell (agogo); South Indian chapu tala
E(7, 16)	(1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0)	Brazilian samba
E(5, 6)	(1,0,1,1,0,1)	Rumanian folk rhythm
E(3, 4)	(1,0,1,1)	Cumbia, calypso tresillo (compressed form)

中文: “验证一下。三拍八格，输出一零零一零零一零，古巴特雷西洛，拉丁音乐最基础的节奏型。五拍八格，输出一零一一零一一零，古巴昆蒂略。七拍十二格是非洲铃鼓的标准节奏，也出现在南印度的恰普节奏中。七拍十六格是巴西桑巴的核心节奏。图桑二零零五年BRIDGES论文列举了二十余种对应——一个粒子加速器算法，精确复现了跨越非洲、拉丁美洲、南亚的传统节奏。”

Why should a particle accelerator algorithm know about drum patterns?

Both problems share the same optimization criterion: distribute $k$ events as uniformly as possible among $n$ slots. For neutron beam extraction, the slots are timing windows; for percussion, they are metric positions. The optimal solution under integer constraints is unique in each necklace class, and computing it requires exactly the structure of Euclidean division.

Necklace equivalence as musical equivalence:

The cyclic rotation symmetry of necklaces has direct musical meaning. When a drummer plays the tresillo, the loop has no fixed starting point — the pattern recurs indefinitely, and each performance may begin at any phase. Two rotations of the same pattern are therefore musically indistinguishable in steady state. Necklace equivalence is the formal statement of this musical fact.

This contrasts with the EP04 use of Burnside’s lemma for chords: there, the group action was transposition (shifting all pitches by a fixed interval), and the equivalence captured pitch-class invariance. Here, the group is cyclic rotation (shifting the phase of the rhythm), and the equivalence captures temporal invariance. Same counting machinery, different musical symmetry.

Limits and Open Questions / 局限性与开放问题

Rotation vs. reflection equivalence. The necklace count of 36 for n = 8 treats clockwise and counterclockwise rotations as different if they produce distinct sequences. Including reflections (time reversal) gives a smaller count via Burnside applied to the dihedral group $D_n$ rather than $\mathbb{Z}_n$ . Musically, whether time reversal should count as the “same” rhythm is genre-dependent: in some traditions, retrograde patterns are considered distinct.
Maximally even vs. most uniform. The tresillo $(1,0,0,1,0,0,1,0)$ has gaps $(3,3,2)$ . This is the most uniform possible under integer constraints. However, perceptually “uniform” and mathematically “maximally even” diverge when beats interact with meter: a pattern of gaps $(3,3,2)$ in a 4/4 meter is heard differently from the same gaps in a 6/8 meter. Extending the framework to metered contexts requires coupling the circular model with a hierarchical meter structure.
Euclidean rhythms and Christoffel words. The binary sequences produced by the Bjorklund algorithm are exactly the Christoffel words (lower mechanical sequences) of slope $k/n$ in combinatorics on words. This connects the problem to the theory of Sturmian sequences and continued-fraction expansions, providing a purely combinatorial characterization independent of the algorithm. The full equivalence has been established (Clough & Douthett 1991; Carey & Clampitt 1989), but a complete proof in the language of the Bjorklund steps requires working through the correspondence between algorithm rounds and continued-fraction convergents.
Higher-dimensional generalizations. The problem “place k beats as evenly as possible in n positions” has a natural 2D analogue: distribute k points as evenly as possible on a 2D lattice grid. This connects to the theory of quasicrystals and Penrose tilings. Whether a higher-dimensional Bjorklund-like algorithm exists that efficiently constructs the optimal 2D pattern is an open algorithmic question.

Conjecture (Perceptual Optimality of Euclidean Rhythms)

Among all binary necklaces of length $n$ with exactly $k$ beats, $E(k, n)$ is the pattern that human listeners identify as most “groove-inducing” or “danceable” at moderate tempos.

Reasoning: The maximally-even structure of $E(k, n)$ minimizes the variance of inter-beat intervals, which psychoacoustic models of rhythm perception (Large & Jones 1999) predict should maximize neural entrainment and motor synchrony.

Falsification criterion: A controlled perception experiment with a representative set of binary necklaces of fixed $(k, n)$ , rated by naive listeners on perceived regularity and groove, would falsify this conjecture if a non-Euclidean pattern consistently scores higher than $E(k, n)$ for some common $(k, n)$ pair (e.g., $(3, 8)$ or $(5, 8)$ ).

Academic References / 参考文献

Bjorklund, E. (2003). The Theory of Rep-Rate Pattern Generation in the SNS Timing System. Technical Report, Spallation Neutron Source, Los Alamos National Laboratory.
Toussaint, G. T. (2005). The Euclidean algorithm generates traditional musical rhythms. In Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science, pp. 47–56. Banff.
Toussaint, G. T. (2013). The Geometry of Musical Rhythm: What Makes a “Good” Rhythm Good? CRC Press.
Clough, J. & Douthett, J. (1991). Maximally even sets. Journal of Music Theory 35(1–2), 93–173.
Carey, N. & Clampitt, D. (1989). Aspects of well-formed scales. Music Theory Spectrum 11(2), 187–206.
Lothaire, M. (2002). Algebraic Combinatorics on Words. Cambridge University Press. Ch. 2 (Sturmian words and Christoffel words).
Burnside, W. (1897). Theory of Groups of Finite Order. Cambridge University Press. (Lemma first stated in this form by Cauchy–Frobenius; the counting technique appears explicitly in Burnside’s 1897 text.)
Large, E. W. & Jones, M. R. (1999). The dynamics of attending: How people track time-varying events. Psychological Review 106(1), 119–159.
Demaine, E. D., Gomez-Martin, F., Meijer, H., Rappaport, D., Taslakian, P., Toussaint, G. T., Winograd, T., & Wood, D. R. (2009). The distance geometry of music. Computational Geometry 42(5), 429–454.
Taslakian, P., Toussaint, G. T., & Wood, D. (2009). Algorithms for computing musical rhythmic similarity. In Proceedings of the International Symposium on Music Information Retrieval (ISMIR).
Frigo, M. & Toussaint, G. T. (2007). Formal diatonic interval theory and trichords. Journal of Mathematics and Music 1(2), 117–137.
Noll, T. (2009). Ionian theorem. Journal of Mathematics and Music 3(3), 137–151.
Agustín-Aquino, O. A., Junod, J., & Mazzola, G. (2015). Computational Counterpoint Worlds: Mathematical Theory, Software, and Experiments. Springer. Ch. 7 (Euclidean rhythms and combinatorics on words).