Asymmetric Rhythms, Tiling Canons, and Burnside’s Lemma

Year: 2004 Authors: Rachel W. Hall; Paul Klingsberg

Core claim

Burnside’s Lemma yields formulas for counting asymmetric rhythm cycles and r-note variants, with an application to constructing rhythmic tiling canons.

Topics

rhythm cycles, asymmetry, orbit counting, rhythmic tiling canons

Domains

combinatorics, group actions, Burnside’s Lemma, finite cyclic groups, music, ethnomusicology, rhythmic composition

Methods

binary encoding, group action counting, orbit enumeration, case analysis

Media

musical rhythm patterns, binary necklaces, drum tablature

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

BRIDGES Mathematical Connections in Art, Music, and Science

Asymmetric Rhythms, Tiling Canons, and Burnside’s Lemma

Rachel W. Hall Dept. of Math and C. S. Saint Joseph’s University 5600 City Avenue Philadelphia, PA 19131, USA E-mail: rhall@sju.edu

Paul Klingsberg Dept. of Math and C. S. Saint Joseph’s University 5600 City Avenue Philadelphia, PA 19131, USA E-mail: pklingsb@sju.edu

Abstract

A musical rhythm pattern is a sequence of note onsets. We consider repeating rhythm patterns, called rhythm cycles. Many typical rhythm cycles from Africa are asymmetric, meaning that they cannot be broken into two parts of equal duration. More precisely: if a rhythm cycle has a period of $2n$ beats, it is asymmetric if positions $x$ and $x+n$ do not both contain a note onset. We ask the questions (1) How many asymmetric rhythm cycles of period $2n$ are there? (2) Of these, how many have exactly $r$ notes? We use Burnside’s Lemma to count these rhythms. Our methods can also answer analogous questions involving division of rhythm cycles of length $\ell n$ into $\ell$ equal parts. Asymmetric rhythms may be used to construct rhythmic tiling canons, in the sense of Andreatta (2003).

1. Rhythm Patterns, Rhythm Cycles, and Asymmetry

Anyone who listens to rock music is familiar with the repeated drumbeat—ONE, two, THREE, four—based on a 4/4 measure. Fifteen minutes listening to a Top 40 radio station is evidence enough that most rock music has this basic beat, or its cousin: one, TWO, three, FOUR. But if we turn the radio dial, and if we’re lucky enough to live near immigrant communities, we may hear popular music with different characteristic rhythms: Latin, African, Indian—and even Macedonian. Although much of this music still is based on the 4/4 measure, some instruments play repeated patterns that do not synchronize with the “ONE, two, THREE, four” beat, creating an exciting tension between different components of the rhythm section. This article is concerned with classifying and counting rhythms that, even when shifted, cannot be synchronized with the division of a measure into two parts. In addition, we will discuss rhythms that cannot be aligned with other even divisions of the measure. Our result has an surprising application to rhythmic canons.

1.1. Rhythm patterns and cycles. A rhythm pattern is a sequence of note onsets. We will assume there is some basic, invariant unit pulse that cannot be divided; that is, every note onset occurs at the beginning of some pulse. We identify two rhythm patterns if they have the same sequence of onsets. For example,

$\downarrow \downarrow \downarrow \text{ and }\downarrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \text{ are equivalent.}$

Here, we consider only periodic rhythm patterns. In this case, it is natural to deem two rhythms equivalent if one is a shift of the other. For example,

$|:\downarrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow :|\text{is equivalent to}|:\uparrow \downarrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow :|$

We call the equivalence classes rhythm cycles. We will sometimes call one period of the cycle a measure.

190 2004 Bridges Proceedings

1.2. Asymmetry. Many rhythm cycles from Africa, Latin America, and Eastern Europe are asymmetric—that is, they cannot be broken into two parts of equal duration, where each part starts with a note onset. Asymmetric rhythm cycles are, in a sense, maximally syncopated: although they live in a world in which measures are naturally divided in half, they cannot be delayed so that note onsets coincide with both the beginning and midpoint of a measure. Asymmetric rhythms are always a little out of sync with our expectations.

1.3. Notation. Here are five different notations for the same rhythm cycle.

standard drum tablature binary .10010010..

binary necklace

The first line shows the standard Western musical notation. Since only note onsets, not durations, matter, we can represent the same pattern using x’s for note onsets and .‘s for rests—we’ll call this system drum tablature. Binary notation replaces the x’s by 1’s and the .‘s by 0’s. Repeat signs (”|:” and ”::|”) are used to bracket cycles. An especially suggestive notation is the representation of rhythm cycles as necklaces of black and white beads, with black beads corresponding to note onsets and white ones to rests. In this case, the cyclic shift becomes a rotation. There is extensive literature on such binary necklaces, to which our results contribute.

2. Rhythms as Functions

We will now translate into mathematical terms. A rhythm pattern can be represented as a function $f:Z\to \{0,1\}$, where $f(x)=1$ if there is a note onset on pulse $x$ and $f(x)=0$ otherwise. The function $f$ represents a periodic rhythm of period $p$ if $f(x)=f(x+p)$ for all $x\in Z$; thus, $f$ can be identified with a function with domain $Z/pZ$ or $Z_p$. A rhythm cycle is defined to be an equivalence class of $p$-periodic functions modulo the shift $(s\cdot f)(x)=f(x-1)$.

Finally, we want to consider not all rhythm patterns but only the asymmetric ones. The notion of an asymmetric rhythm pattern makes sense only if the period is even. We say that a rhythm pattern of period $p=2n$ is asymmetric mod $2n$ if when a note onset occurs at beat $x$, no onset occurs at beat $x+n$. That is, $f(x)=1$ only if $f(x+n)=0$. In total, there are $3^n$ asymmetric rhythm patterns. Indeed, if we partition the elements of $Z_{2n}$ into $n$ pairs $\{\{0,n\},\{1,n+1\},\dots ,\{n-1,2n-1\}\}$, then constructing a function $f\in S_{2n}$ corresponds to choosing, for each pair, one of the following three possibilities:

Choice 1. $f=0$ for both members of the pair.

Choice 2. $f=1$ for the first element and $f=0$ for the second element.

Choice 3. $f=0$ for the first element and $f=1$ for the second element.

We count the total number of asymmetric rhythm cycles of period $2n$ by starting with the set $S_{2n}$ of all $3^n$ asymmetric rhythm patterns of period $2n$,

and counting the number of equivalence classes modulo the shift. Similarly, we count the number of $r$-note asymmetric rhythms of period $2n$ by starting with the subset $S_{2n}^r$ of $r$-note asymmetric rhythm patterns of period $2n$,

Mathematical Connections in Art, Music, and Science 191

and counting equivalence classes modulo cyclic shift.

In both cases, the equivalence classes are orbits induced by a group action.¹ For rhythm cycles, the group is $Z_{2n}$, and element $m\in Z_{2n}$ acts on a cycle by shifting it through $m$ positions. On the level of functions: for $f\in S_{2n}$ (respectively $f\in S_{2n}^r$), the function $m\cdot f$ is given by $(m\cdot f)(x)=f(x-m)$, where addition is modulo $2n$. Because the equivalence classes are orbits, we can apply Burnside’s Lemma. The statement of this lemma is as follows; for a proof, see [3].

Burnside’s Lemma 1 Let a finite group $G$ act on a finite set $S$; for each $\beta \in G$, define $\mathrm{fix}(\beta )$ to be the number of elements $s\in S$ such that $\beta \cdot s=s$. Then the number of orbits that $G$ induces on $S$ is given by

3. The Total Number of Asymmetric Rhythm Cycles

Theorem 1 The number of asymmetric rhythm cycles of period $2n$ is given by

where $\varphi (d)$ is the number of integers $1\le x\le d$ such that $x$ is relatively prime to $d$.

Proof. With the group $Z_{2n}$ acting on the set $S_{2n}$, the number of orbits (i.e. cycles) is $(1/2n){\sum }_{\beta \in Z_{2n}}\mathrm{fix}(\beta )$ by Burnside’s Lemma. We need to determine $\mathrm{fix}(\beta )$. For each divisor $d$ of $2n$, we will find the elements $\beta$ of order $d$ and determine $\mathrm{fix}(\beta )$, which will depend only on $d$. Pick a divisor $d$ of $2n$, and let $k=2n/d$. The elements of order $d$ in $Z_{2n}$ are the elements of $Z_{2n}$ that generate $kZ/2nZ\simeq Z_d$,—that is, the subgroup of multiples of $k\mathrm{mod}2n$. These are the elements $\beta =kj$, where $1\le j\le d$ and $\gcd (j,d)=1$, so there are $\varphi (d)$ of them. Moreover, for each $\beta$ of order $d$, $\beta \cdot f=f$ if and only if $f(x+k)=f(x)$ for all $x$; that is, $\mathrm{fix}(\beta )$ is the number of $k$-periodic functions in $S_{2n}$.

Two cases arise: either $k$ divides $n$ (in which case $d$ is even); or $k$ does not divide $n$ (in which case $d$ is an odd divisor of $n$ and $k$ is even).

Case 1. If $k$ divides $n$ and $\beta \cdot f=f$, then for each $x$ in $Z_{2n}$, $f(x)=f(x+k)$ which implies $f(x)=f(x+n)=0$—that is, $f(x)\equiv 0$. Thus, in this case, only the function $f(x)\equiv 0$ is fixed by $\beta$, so $\mathrm{fix}(\beta )=1$.

Case 2. If $k$ does not divide $n$, then $0\not\equiv n\mathrm{mod}k$, but $0\equiv 2n\mathrm{mod}k$ because $k$ divides $2n$. This implies that $n\equiv k/2\mathrm{mod}k$.

Now, if $f$ is $k$-periodic, then $f$ is determined by its values on the subset $\{0,1,\dots ,k-1\}$ of $Z_{2n}$. If we partition this subset into $k/2$ pairs $\{\{0,k/2\},\dots ,\{k/2-1,k-1\}\}$, then constructing a $k$-periodic function $f\in S_{2n}$ corresponds to making one of the same three choices listed above for each of these pairs. Thus

¹Recall: if group $G$ acts on set $S$ and $s\in S$, the orbit of $s$ is the set $\{g\cdot s\mid g\in G\}$.

2004 Bridges Proceedings

$\mathrm{fix}(\beta )=3^{k/2}=3^{n/d}$ . Putting together the two cases now yields the result:

4. The Number of $r$-beat Asymmetric Rhythm Cycles

The argument here is analogous to that in the previous section; we let $Z_{2n}$ act on $S_{2n}^r$, and we count the orbits. In the (exceptional) case $r=0$, there is obviously one asymmetric cycle; below, we restrict our attention to $r\ge 1$.

Theorem 2 For any $1\le r\le n$, the number of asymmetric $r$-beat rhythm cycles is given by

Proof. In outline, the proof is similar to that of Theorem 1. As in that proof: choose a divisor $d$ of $2n$; put $k=2n/d$; and let $\beta \in Z_{2n}$ be of order $d$. For any $f\in S_{2n}^r$, as before, $\beta \cdot f=f$ if and only if $f$ is $k$-periodic. In the present context, though, there are three cases, not two:

• Case 1. $k$ divides $n$;
• Case 2. $k$ does not divide $n$ and $d$ does not divide $r$;
• Case 3. $k$ does not divide $n$ and $d$ divides $r$.

Case 1. If $k$ divides $n$ and $\beta \cdot f=f$, then for each $x$ in $Z_{2n}$, $f(x)=f(x+k)$, which implies $f(x)=f(x+n)$, so $f(x)=0$ for all $x$. However, since $r\ge 1$, the zero function is not in $S_{2n}^r$. In Case 1, $\mathrm{fix}(\beta )=0$.

Case 2. In order for $f\in S_{2n}^r$ to be $k$-periodic, the number of elements $x$ such that $f(x)=1$ would have to be a multiple of $d$. But $r$ is not a multiple of $d$; so in Case 2 also, $\mathrm{fix}(\beta )=0$.

Case 3. If $k$ does not divide $n$ and $d$ divides $r$, then the asymmetry condition again implies that each $f\in S_{2n}$ fixed by $\beta$ is constructed by making the same three choices on the pairs $\{0,k/2\}\dots \{k/2-1,k-1\}$, but in order to ensure that there are exactly $r$ 1’s, one must make Choices 2 or 3 for exactly $r/d$ of the pairs and Choice 1 for the rest. To construct such a function, then, one must:

1. Choose $r/d$ of the $n/d$ pairs. This can be done in $\left(\genfrac{}{}{0ex}{}{n/d}{r/d}\right)$ ways.
2. For each of the selected pairs, make either Choice 2 or Choice 3. This sequence of choices can be made in $2^{r/d}$ ways.
3. Make Choice 1 for all the pairs you did not select in step 1.

Thus, in Case 3, $\mathrm{fix}(\beta )=\left(\genfrac{}{}{0ex}{}{n/d}{r/d}\right)2^{r/d}$. Putting the three cases together now yields $(†)$.

Mathematical Connections in Art, Music, and Science 193

In general, the complement of a rhythm cycle is the cycle formed by exchanging beats and rests. On the level of functions, the complement of $f$, $f^c$, equals $1-f$. The maximum number of beats in an asymmetric rhythm cycle of length $2n$ is $n$. Asymmetric cycles of $n$ notes have an additional property: they are complementary—that is, equivalent to their own complements—since $f(x)=1$ if and only if $f(x+n)=0$, which implies $(-n)\cdot f(x)=f(x+n)=1-f(x)$. Finally, putting $r=n$ in $(†)$ gives the number of complementary asymmetric rhythm cycles.

Corollary 3 The number of complementary asymmetric rhythm cycles is given by $\frac{1}{2n}{\sum }_{\begin{array}{c}d|n\\ d\text{odd}\end{array}}\varphi (d)2^{n/d}$.

5. Generalization to $\ell$-Asymmetry

Rhythmic asymmetry may be generalized: we say that a periodic rhythm of period $\ell n$ is $\ell$-asymmetric if when position $x$ contains a note onset, then all other positions $y$, where $y\equiv x\mathrm{mod}n$, do not contain note onsets. Our previous definition of asymmetry corresponds to $\ell$-asymmetry when $\ell =2$. For example, the 12-periodic rhythm 100000100101 is 3-asymmetric ($n=4$).

Let $R_{\ell }(n,r)$ denote the number of $r$-note, $\ell$-asymmetric rhythms. Using Burnside’s Lemma, we prove

If we remove the restriction that the rhythms have $r$ note onsets, then the number of $\ell$-asymmetric rhythms of length $\ell n$ is

6. Applications

6.1. Rhythmic tiling canons.

A canon, or round, is a musical figure produced when two or more voices play the same melody, with each voice offset by a fixed time interval from the others. Popular rounds include “Frère Jacques” and “Row, row, row your boat.” A rhythmic canon is a canon in which each voice plays the same rhythm pattern offset by a number of beats. A rhythmic tiling canon is a canon of rhythm cycles with the restriction that when all voices are played, the resultant rhythm has exactly one note onset per unit.²

Suppose one wishes to construct a cycle that forms a 12-periodic rhythmic tiling canon when played by three voices, offset from each other by four beats. Here is an example of a possible tiling canon, generated by the cycle $|:x\dots x\dots x:|$ (that is, 100000100101):

²This term is due to Andreatta [1]. It is equivalent to Vuza’s regular complementary canon [6]

2004 Bridges Proceedings

Observe that the positions $x$, $x+4$, and $x+8$ must contain exactly one drumhit, where addition is done mod 12. In other words, this is a four-note 3-asymmetric rhythm cycles of length 12. Using our formula for the number of $r$-beat rhythm cycles, where $\ell =3$, $n=4$, and $r=n=4$, we see that there must be eight such cycles, as shown.

1. | : xxxx … … : |

2. | : xxx … x … : |

3. | : xx … xx … : |

4. | : xx.x … .x. : |

5. | : xx.x . . x … : |

6. | : x … . x . . x : |

7. | : x.x . . x … : |

8. | : x … x … x . . : |

Audio recordings of all these rhythms are available at www.sju.edu/~rhall/bridges.html. Notice that Patterns 3 and 6 are not primitive, meaning that they can be realized using a smaller period (Pattern 3 has primitive period 6, and Pattern 8 has primitive period 4). Patterns 5 and 6 are inversions of each other (that is, Pattern 5 is Pattern 6 played backwards); all other patterns are symmetric with respect to inversion. It is interesting to listen to how the degree of asymmetry affects the sound of the resulting canon; Patterns 5 and 6 sound the “most asymmetric.”

In general, any $\ell n$-periodic rhythm with $n$ note onsets which is $\ell$-asymmetric forms a tiling canon of $\ell$ voices, offset by multiples of $n$ notes. The number of such rhythmic tiling canons may be found by substituting $r=n$ in $(\ast )$.

6.2. Rhythmic oddity. Simha Arom [2] pointed out that certain asymmetric rhythms played by peoples of the Central African Republic possess what he denotes the rhythmic oddity property. The rhythms Arom studied have the additional restriction that all note onsets are spaced by 2 or 3 units, and that the period is $4n$, thus ensuring that the rhythm splits into two patterns of length $2n-1$ and $2n+1$. Chemillier [4] and Chemillier and Truchet [5] has developed an algorithm to generate all rhythms formed from 2- or 3-unit notes having the rhythmic oddity property. The question of a formula for the number of rhythms with the oddity property is still open.

References

[1] Moreno Andreatta. Méthodes algébriques en musique et musicologie du XXe siècle : aspects théoriques, analytiques et compositionnels, 2003. PhD thesis. Under the direction of Alain Poirer. École des Hautes Études en Sciences Sociales.

[2] Simha Arom. African polyphony and polyrhythm: musical structure and methodology. Cambridge University Press, Cambridge, MA, 1991.

[3] Kenneth P. Bogart. Introductory combinatorics. Harcourt/Academic Press, San Diego, CA, third edition, 2000.

[4] Marc Chemillier. Ethnomusicology, ethnomathematics. The logic underlying orally transmitted artistic practices. In Mathematics and music (Lisbon/Vienna/Paris, 1999), pages 161–183. Springer, Berlin, 2002.

[5] Marc Chemillier and Charlotte Truchet. Computation of words satisfying the rhythmic oddity property (after Simha Arom’s works). Information Processing Letters, 86:255–261, 2003.

[6] Dan Tudor Vuza. Supplementary sets and regular complementary unending canons I–IV. Perspectives of New Music, 29(2)–31(1), 1991–1993.