# Rhythmic canons modulus p

Hello again ! Today, I’d like to talk about some recent work of Hélianthe Caure, a Ph.D. student working at IRCAM. The subject of her thesis is about rhythmic canons, and in particular rhythmic canons modulus p. You can read her preprint on Arxiv here:

• “Modulus $p$ Vuza canons: generalities and resolution of the case $\{0,1,2^k\}$ with $p =2$, Caure, H., arXiv:1505.06930
• Check also her presentation in Mamux (in French) here.
• And a more accessible presentation here (still in French)

For this blog, explanations are in order.

Take a simple rhythm like the one represented below, on a 12-beat measure.

Now, get two friends, and ask them to play the same pattern, but with a one (resp. two) beat shift. You will get this rhythmic pattern below:

Since all of you are playing the same initial rhythm, but with different entry points, we get a rhythmic canon, and more importantly we say that it tiles $\mathbb{Z}_{12}$, because, informally speaking, each element of $\mathbb{Z}_{12}$ receives one and only one beat.

Instead of using the cyclic representation of above, I’ll use the linear one represented in the picture below (and we implicitly assume that the rhythm we consider is periodic, i.e. it can go on ad infinitum).

Let’s be a bit formal here. First, for any set theoretic operation $\star$ we define $\star_N$ as $A \star_N B = \{a \star b \mod N, a \in A, b \in B\}$. We consider rhythmic canons on $\mathbb{Z}_N$. A rhythmic pattern $A$ is a subset of $\mathbb{Z}_N$ containing 0. We say that $A$ tiles $\mathbb{Z}_N$ if there exists a rhythmic pattern $B$ such that the direct sum $A \bigoplus_N B$ is equal to $\mathbb{Z}_N$. We will call $(A,B)_N$rhythmic canon for $\mathbb{Z}_N$In addition, we say that a rhythmic canon $(A,B)_N$ is compact if $A \bigoplus_N B = A \bigoplus B$.

So, in the example above, $A=\{0,3,6,9\}$ and $B=\{0,1,2\}$. Obviously, if $A$ tiles $\mathbb{Z}_N$ with $B$, then $B$ also tiles with $A$.

Vuza canons

Now, among all rhythmic canons, we find periodic ones, the example above being an example of such. In general, we say that a rhythmic canon $(A,B)_N$ is periodic, if there exists $0 such that either $A +_N \{k\} = A$, or $B +_N \{k\} = B$. Again, the example above is periodic with $k=3$.

I know you are immediately going to ask: can a canon be non-periodic ? The answer is yes, but if you try finding an example by hand, you are likely going to fail. We call such canons Vuza canons, from Dan Tudor Vuza who pioneered their study in the field of mathematical music theory in the 80s, rediscovering independently some work by Hajos, De Bruijn and Sands. The reason you are not going easily to find one is that the first one appears for $N=72$, the next one for $N=108$, then $N=120, 144, 168...$. The subject of Vuza canons is rather complicated, and I am going to save it for another post. If you are interested in a quick introduction, check out this preprint by Franck Jedrzejewski:

• “Enumeration of Vuza Canons”, Jedrzejewski, F., arxiv.org/1304.6609
• Check also the early papers of Emmanuel Amiot, like this one: “Rhythmic canons and galois theory”, Amiot, E., In H. Fripertinger and L. Reich (eds.), Proceedings of the Colloquium on Mathematical Music Theory, Grazer Mathematische Berichte, vol. 347, p. 1-25, Graz, Austria, 2005

Vuza canons are analogues of prime numbers or prime knots, in the sense that any rhythmic canon can be deduced by concatenation and duality from Vuza canons and the trivial canon (this is a theorem by Emmanuel Amiot).

Modulus p Vuza canons

Hélianthe has looked at a weaker form of tiling, by considering tiling modulus $p$where $p$ is a prime number. Informally speaking, we say that $A$ tiles $\mathbb{Z}_N$ with $B$ modulus $p$ if each element of $\mathbb{Z}_N$ receives one beat modulus $p$

Take for example $A=\{0,1,3\}$ and $B=\{0,2,3\}$. It tiles $\mathbb{Z}_7$ modulus 2, as we can see on the picture below.

Rhythmic canons modulus $p$ are easier to manipulate. For example, a theorem of Warusfel says that if $A$ is a rhythmic pattern, and $p$ is a prime number, then there exists an integer $N$ and $B$ such that $(A,B)_N$ is a rhythmic canon modulus $p$.

One of the main results of the work of Hélianthe Caure is a greedy algorithm for finding $B$ and $N$, which she proves is optimal, in the sense that it gives $B$ with the smallest cardinality (and thus the smallest value of $N$). The algorithm works as follows:

• Take your rythmic pattern $A$, place it on the first beat:

• Find the next position which is not covered by exactly one beat modulo $p$. Place $A$ on this beat. In this case, with $p=2$, the next beat is 2, so we’ll place $A$ there:

• Check if, for the length of the current canon, it is compactly tiled. Repeat otherwise. In this case, no, since position 4 is not coverered by any beat. Incidentally, going back to step 2, this is where we’ll place $A$:

• Now, we can check that for $N=7$, every position before 7 is covered by exactly one beat modulo 2 so the algorithm stops here, and we obtain $B$.

Here is what this canon sounds like (when played on three stones):

Here is another example with $A=\{0,2,5\}$, which tiles $\mathbb{Z}_{31}$, with $B=\{0, 1, 4, 6, 7, 9, 10, 11, 12, 14, 16, 20, 23, 24, 25\}$.

And again another, more complex, example with $A=\{0,2,7\}$. It tiles $\mathbb{Z}_{93}$, with B={0, 1, 4, 5, 7, 10, 12, 13, 14, 18, 20, 23, 24, 25, 27, 28, 30, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 44, 46, 48, 52, 56, 57, 59, 60, 65, 67, 68, 71, 76, 77, 78, 81, 82, 83, 84, 85}.

Then Hélianthe has looked in particular at rhythmic patterns $A$ of the form $A=\{0,1,n\}$, and she calculated the length of the compact canons modulus 2 for the first values of $n$, which you can find in the table below.

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 3 7 15 21 63 127 63 73 889 1533 3255 7905 11811 32767 255

Notice anything particular ? Well, this is the second main result of Hélianthe: the rhythmic canons modulus 2 with $A=\{0,1,2^k\}$ have length $4^k-1$, the rhythmic canons modulus 2 with $A=\{0,1,2^k+1\}$ have length $4^k+2^k+1$. So clearly, the growth of rhythmic canons with $A=\{0,1,2^k\}$ or $A=\{0,1,2^k+1\}$ is different than from the rest of the cases.

In fact, any rhythmic canon modulus 2 with rhythmic pattern $A_{2^k}=\{0,1,2^k\}$ can directly be deduced from the rhythmic canon modulus 2 with rhythmic pattern $A_{2^k-1}=\{0,1,2^k-1\}$. To see this, we arrange the entries of $B_{2^k}$ in a table $T_{2^k}$ (it’s not a matrix, there is no algebraic structure on these tables) of $2^k-1$ rows and $2^k$ columns, filling the rows one after the other. For example, $A_{4}=\{0,1,4\}$ tiles modulus 2 with $B_{4}=\{0,2,5,6,8,9,10\}$. So the table $T_4$ will look like this:

$T_4 = \begin{pmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0\end{pmatrix}$

And Hélianthe shows that the general form of the $T_{2^k}$ tables is the following:

$T_{2^k} = \begin{pmatrix} T_{2^{k-1}} & T_{2^{k-1}} \\ \tilde{T_{2^{k-1}}} & \begin{matrix} 1 & 1 & \ldots & 1 & 0 \\ 1 & 1 & \ldots & 1 & 0 \\ \vdots & \vdots & & \vdots \\ 1 & 1 & \ldots & 1 & 0 \end{matrix} \end{pmatrix}$

where $\tilde{T_{2^{k-1}}}$ is obtained by adding a first row containing $2^k$ zeros, then filling with the $2^{k-1}-1$ rows of $T_{2^{k-1}}$, and finally replacing all numbers in the last column by 1s.

Note that a similar recursive form exists for the tables $T_{2^k+1}$. Pretty neat, isn’t it ? So, in fact, the greedy algorithm of Hélianthe, which was able to give the rhythmic canons modulus $p$ in linear time, can be sped up in these particular cases to give the rhythmic canons in logarithmic time !

But what about these tables for rhythmic patterns which are not of the form $A_{2^k}=\{0,1,2^k\}$ or $A_{2^k+1}=\{0,1,2^k+1\}$ ? Well, we don’t know actually, and there are interesting perspectives for finding canons more rapidly than in linear time. One thing which is particularly striking for me is what those tables look like. Here is the beginning of the table $T_{34}$:

When I first saw this, I immediately thought about the Rule 110 for cellular automata. Hélianthe did too when I contacted her to share this information. It turns out that this is more complicated, and what is really going on is not known currently.

I hope you enjoyed this little trip in the domain of rhythmic canons, and I think that Hélianthe’s work has opened some very interesting perspectives for their study.