Permutation Descents and Euclidean Rhythms

A collection of drums. — A medley of drums.

Following from my previous post, here’s another surprising crossover between maths and music. Did you know that some composers use number theory to write music? We can think of a rhythm as notes distributed in a measure of fixed length. We’ll ignore syncopation for the sake of simplicity. For example, in a measure of 4/4 time, there are four positions in which a crotchet could be written (or a quarter note for my fellow Americans). I claim it’s possible to determine a rhythm by using the Euclidean algorithm. The main idea is that equally distributing notes in a measure is equivalent to finding the gcd of the length of the measure and the number of notes (not rests).

Now, if you accept my premise that musical application of Euclid is possible, it would still be fair to ask whether the results are worth listening to. This is a subjective question, and personally I would lean towards “yes”. However, I am not alone in the sentiment. It turns out that many of these Euclidean rhythms have been part of traditional music for hundreds of years. Whether or not the traditional rhythms are considered to be mathematical in their home cultures is far outside the scope of this post.

In 2005, Godfried Toussaint wrote a survey of Euclidean rhythms as they appear in Cuban, Persian, South African, and Turkish music, to name a few. Since then, the concept has found popularity composer’s circles, particularly the experimental and electronic groups I dabble in.

How to Write a Euclidean Rhythm

Toussaint describes an algorithm for producing Euclidean rhythms in his paper. This method looks the most like Euclid; the algorithm recursively allocates blocks of notes and rests until the remainder goes to zero. It was originally developed by E. Bjorklund to solve a problem in control systems theory. There, the goal is to evenly space events in a discrete time setting. For example, a circuit may need to be activated five out of every nine clock ticks, spaced as equally as possible to minimise wear and tear.

The Wikipedia article on Euclidean rhythms notes that another algorithm, Bresenham’s line-drawing algorithm, produces equivalent results. Both of these methods have publicly available pseudocode, but I find them to be opaque. Instead, I’d like to offer an approach involving permutation descents that I cooked up while trying to understand Bresenham’s algorithm.

Residue Sequences

Recall that in permutation theory, an ascent is an adjacent pair of permutation entries $n_i, n_{i+1}$ with the property that $n_i < n_{i+1}$ . Likewise, a descent satisfies the inequality $n_i > n_{i+1}$

Here is my method. Given a length $N$ and a number of notes $0 \leq k \leq N$ to place, construct the sequence $(-k, 0, k, 2k, \ldots, (N-1)k)$ . This arithmetic sequence begins at $-k$ and consists of $N+1$ terms.

Next, reduce these integers modulo $N$ to their representatives in the set $\{0, 1, 2, \ldots, N-1\}$ . This gives a sequence of $N+1$ integers. That is, we have $N$ adjacent pairs to work with. Read left to right, each adjacent pair corresponds to a position in a measure of music $N$ beats long. To produce the rhythm, place a note in a position whenever the corresponding pair is a descent.

For example, if $N = 9$ and $k = 5$ , the residue sequence is $(4, 0, 5, 1, 6, 2, 7, 3, 8, 4)$ , and the rhythm is ♩_♩_♩_♩_♩. This is exactly the Euclidean rhythm E(5,9) as documented here. (It is standard to treat rhythms as a cycles in this context, so that rotating the starting point does not change the rhythm.)

Under the Hood

Why does this work? I have a geometrical argument, likely related to the idea that Bresenham had in 1962. Consider a line segment drawn in the plane from $(1, -k)$ to $(N+1, kN-k)$ . It has slope $k$ . The points $(x, y)$ along this segment where $x$ is an integer have integer $y$ coordinates, which exactly reproduce the arithmetic sequence I described above, before reduction. Every crossing between this segment and a horizontal line where $y$ is an integer multiple of $N$ corresponds to a descent in the reduced sequence, and there are exactly $k$ such crossings.

I’ve implemented this algorithm in Python here. There are some other versions of the algorithm in the same directory.

Question

How does this relate to gcds? Well, consider a rhythm, say ♩__♩__, which is E(2,6). All rhythms can be considered to be periodic. From that point of view, then $\gcd(k, N)$ is equal to the number of occurrences of the minimal period of the Euclidean rhythm E(k,N) in a duration of $N$ beats. Here, we verify that $\gcd(2, 6) = 2$ . More broadly, there is a way we can extract the results of the extended Euclidean algorithm from the method described above. As a challenge, how would you look at a sequence like $(4, 0, 5, 1, 6, 2, 7, 3, 8, 4)$ and use it find integers $a$ and $b$ so that $ak + bN = \gcd(k,N)$ ?