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 Vuza canons: generalities and resolution of the case with “*, 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* , because, informally speaking, each element of 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 we define as . We consider rhythmic canons on . A *rhythmic pattern *is a subset of containing 0. We say that *tiles* if there exists a rhythmic pattern such that the direct sum is equal to . We will call a *rhythmic canon for . *In addition, we say that a rhythmic canon is *compact* if .

So, in the example above, and . Obviously, if tiles with , then also tiles with .

**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 is *periodic*, if there exists such that either , or . Again, the example above is periodic with .

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 , the next one for , then . 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 , *where is a prime number. Informally speaking, we say that tiles with *modulus * if each element of receives one beat *modulus . *

Take for example and . It tiles modulus 2, as we can see on the picture below.

Rhythmic canons modulus are easier to manipulate. For example, a theorem of Warusfel says that if is a rhythmic pattern, and is a prime number, then there exists an integer and such that is a rhythmic canon modulus .

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

- Take your rythmic pattern , place it on the first beat:

- Find the next position which is not covered by exactly one beat
*modulo .*Place on this beat.

- 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 :

- Now, we can check that for , every position before 7 is covered by exactly one beat
*modulo 2*so the algorithm stops here, and we obtain .

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

Here is another example with , which tiles , with .

And again another, more complex, example with . It tiles , 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 of the form , and she calculated the length of the compact canons *modulus 2 *for the first values of , 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 have length , the rhythmic canons modulus 2 with have length . So clearly, the growth of rhythmic canons with or is different than from the rest of the cases.

In fact, any rhythmic canon *modulus 2* with rhythmic pattern can directly be deduced from the rhythmic canon *modulus 2* with rhythmic pattern . To see this, we arrange the entries of in a table (it’s not a matrix, there is no algebraic structure on these tables) of rows and columns, filling the rows one after the other. For example, tiles *modulus 2* with . So the table will look like this:

And Hélianthe shows that the general form of the tables is the following:

where is obtained by adding a first row containing zeros, then filling with the rows of , and finally replacing all numbers in the last column by 1s.

Note that a similar recursive form exists for the tables . Pretty neat, isn’t it ? So, in fact, the greedy algorithm of Hélianthe, which was able to give the rhythmic canons *modulus * 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 or ? 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 :

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.