Rhythmic canons (6)

This post is a follow-up on the subject of rhythmic canons and the last post. Today I will talk specifically about Vuza canons, i.e. non-periodic canons.

I’ll start with an example. Let’s take the motive $A=\{0,1,8,9,17,28\}$. Can this be a motive for a rhythmic canon, i.e. does it tile $\mathbb{Z}_n$ for some integer $n$ ? As we have seen in the previous post, this is not an easy question, and until the recent work of Coven and Meyerowitz, there was no easy way to determine if tiling would possible or not. We recall here the two conditions of Coven and Meyerowitz, and their therorems.

Given the factorization $A(X)=\Phi(X)M(X)$ of the polynomial corresponding to $A$, where $\Phi(X)$ is a product of a cyclotomic polynomials, we define the set $R_A$ to be the set of orders of the cyclotomic polynomials in $\Phi$, and the set $S_A$ to be the subset of $R_A$ consisting of prime powers. The two conditions (T1) and (T2) are as follows.

Condition (T1): $A(1)=\prod_{p^k \in S_A}p$

Condition (T2): If ${p_1}^{k_1}$, ${p_2}^{k_2}$, $\ldots$ are in $S_A$, then ${p_1}^{k_1}{p_2}^{k_2}\ldots$ is in $R_A$.

The results of Coven and Meyerowitz are then as follows.

• If $A$ tiles, then (T1) is true.
• If both (T1) and (T2) are true, then $A$ paves
• If $A(1)$ has only two prime factors, and $A$ paves, then condition (T2) is true.

With these results, it is easy to check that $A=\{0,1,8,9,17,28\}$ indeed tiles $\mathbb{Z}_{36}$. Here is our motive in a graphical representation, 0 being on top, and the order being clockwise. The entries are $E=\{0,6,12,18,24,30\}$, so we get the following tiling. Now, you probably have noticed that the set of entries is periodic in $\mathbb{Z}_{36}$. The immediate general question we could ask would be: is it always the case ?

The answer is a definite no, but not an obvious one.The first $n$ for which a non-periodic canon exists is $n=72$. In the mathematics/music community, canons which have no periodicity (either in the set of their entries, or in the set of the motive) are called Vuza canons, named after Dan Tudor Vuza, a romanian mathematician who spent almost 10 years between 1980 and 1990 working on rhythmic canons. Vuza published his work in a series of four papers in Perspectives of New Music, the references of given below.

• D. T. Vuza, “Supplementary sets and regular complementary unending canons”, Perspectives of
New Music. Part 1 : Vol. 29(2), 1991, p. 22-49. Part 2: Vol. 30(1), 1992, p. 184-207. Part 3: Vol. 30(2), 1992, p. 102-125. Part 4: Vol. 31(1), 1993, p. 270-305.

It was later found that Vuza had rediscovered by himself some known results of Hajos, Redeï, De Bruijn, etc. In particular, we have the following result, which characterizes the integers $n$ for which no Vuza canon exist.

Theorem: let $p,q,r,s$ be distinct prime numbers. If an integer $n$ is of the form $n=p^\alpha$, $n=p^\alpha q$, $n=p^2q^2$, $n=p^2qr$, or $n=pqrs$, then the canons which tile $\mathbb{Z}_n$ are periodic (i.e. non-Vuza).

Hence, the first integers $n$ for which Vuza canon may exist are 72, 108, 120, 144, 168, 180, 200, 216, 240, 252, 264, 270, 280, 288, 300, 312, 324, 336, 360, etc. From a musical point of view, Vuza canons are interesting since they introduce a certain degree of non-repetitiveness in a musical form which is repetitive by definition. Here is an example of a Vuza canon which tiles $\mathbb{Z}_{72}$. The motive is $A=\{0, 1, 5, 6, 12, 25, 29, 36, 42, 48, 49, 53\}$, which can be represented as follows. And the entries are $E=\{0, 8, 16, 18, 26, 34\}$ (non-periodic, as you can see), such that the final tiling can be represented as follows. It so happens that someone has posted on Youtube a realization of a Vuza canon of length 72 (which might not be identical to the one above, I have not checked), so this saves me the work of doing it. Check it out below.

Emmanuel Amiot has remarked that if one has canon (not necessarily Vuza) with motive $A$ and entries $E$, then one can form a new canon by repeating (concatenating) the motive, without changing the entries. For example, the motive $A=\{0,1,3,7,9\}$ paves $\mathbb{Z}_{10}$ with entries $E=\{0,5\}$. If one concatenate the motive once to get the new motive $A'=\{0,1,3,7,9,10,11,13,17,19\}$, then it paves $\mathbb{Z}_{20}$ with the same entries. Now, the results of Coven and Meyerowitz state that if a motive paves, then it has condition (T1) on one hand, and if conditions (T1) and (T2) are respected then a motive paves, on the other hand. The underlying conjecture here is whether the sole condition (T2) implies that a motive paves. Amiot has showed that if a motive $A'$ is obtained by concatenation of a motive $A$, then one has condition (T2) if and only if the other one has condition (T2). By definition of a Vuza canon, we can deduce that any rhythmic canon can be recursively deconcatenated to either a Vuza canon, or the trivial canon (with motive $A=\{0\}$ and entry $E=\{0\}$). Thus, if one wants to prove the implication (T2) $\implies$ tiling, it is enough to prove it for the Vuza canons.

The problem is: we don’t know how to construct all Vuza canons. Harald Fripertinger has enumerated all Vuza canons of length 72 and 108, which you can find here:

And here are his research papers on the enumeration of rhythmic canons:

• H. Fripertinger, “Enumeration of non-isomorphic canons”, Tatra Mt. Math. Publ., 23, p. 47-57,
2001.
• H. Fripertinger, “Remarks on Rhythmical Canons”, 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, p. 73-90.
• H. Fripertinger, “Tiling problems in music theory”, in G. Mazzola, Th. Noll, and E. LluisPuebla,
editors, Perspectives in Mathematical and Computational Music Theory, pages 153-168. epOs
Music, Osnabrück, 2004.

Some algorithms are known to compute Vuza canons; in particular Franck Jedrzejewski has published new constructions and extended the enumeration of Vuza canons for longer lengths.

In fact, if you look at the tables in Jedrzejewski’s paper, you will notice that the number of Vuza canons can be quite large. This has been observed by Kolountzakis and Matolcsi in the following paper, in which they also give an algorithm for constructing non-periodic canons.

• Kolountzakis, M.N., Matolcsi, M., “Algorithms for translational tiling”, Journal of Mathematics and Music, 3:2 (2009), pp. 85-97, DOI: 10.1080/17459730903040899

Their algorithm works as follows. Pick sufficiently large prime numbers $p$ and $q$ and consider the integer $n=2 \cdot 3 \cdot 5 \cdot p \cdot q$. We are going to consider the group $\mathbb{Z}_n$ as being isomorphic to $\mathbb{Z}_{2} \times \mathbb{Z}_{3p} \times \mathbb{Z}_{5q}$ and work in this group. For the specific purpose of this post, I will take here $p=3$ and $q=3$, meaning that we are going to build a Vuza canon of length 270.

We consider the motive $A=\{(i,j,0), i \in \{0,1,2\}, j \in \{0,1,2,3,4\}\}$ and the entries $B=\{(3i,5j,k), i \in \{0,1,2\}, j \in \{0,1,2,3,4\}\}$. We can represent it graphically as follows, with the motive in orange and the entries in green, bearing in mind that the two planes are in fact toruses (they wrap at the edges), and the vertical direction also wraps. So far so good, but this is clearly a periodic tiling. The idea of Kolountzakis and Matolcsi is to perturbate this arrangement by shifting the entries in the lower and upper planes. More specifically, we shift the first column by one in the lower plane, and the the first row by one in the upper plane, so that the entries are now (0,0,0),(3,0,0),(6,0,0),(1,5,0),(4,5,0),(7,5,0),(0,10,0),(3,10,0),(6,10,0), and (0,0,1),(0,5,1),(0,10,1),(3,4,1),(3,9,1),(3,14,1),(6,0,1),(6,5,1),(6,10,1), which can be represented as follows. The tiling has now become non-periodic, and you can use your favorite isomorphism from $\mathbb{Z}_{2} \times \mathbb{Z}_{9} \times \mathbb{Z}_{15}$ to $\mathbb{Z}_{270}$ to get the final Vuza canon.

I will conclude this post with some personal observations, which look similar to the work of Kolountzakis and Matolcsi. Consider the Vuza canon of length 72 with motive $A=\{0,1,5,6,12,25,29,36,42,48,49,53\}$, and entries $E=\{0,8,16,18,26,34\}$. We have an isomorphism between $\mathbb{Z}_{72}$ and $\mathbb{Z}_{8} \times \mathbb{Z}_{9}$ so that, similarly as above, we can represent the motive and entries on a 8 x 9 torus, as follows.

In this representation, it is clear that the motive is non-periodic, but not so far from being so. In fact, if you were to shift the fourth column by two, you would get the following motive, which paves $\mathbb{Z}_{72}$ with the same entries, but is now a (non-Vuza) periodic rhythmic canon. The Vuza motive where the third column has been shifted by two units.

I am unsure if this is a general phenomenon for all Vuza canons. For example, the Vuza canon of length 180 with motive A=0,6,16,17,25,26,34,35,36,42,43,44,52,53,72,78,106,107,108,114,115,116,124,125,133,134,142,143,144,150, and entries E=0,12,24,45,57,69, can be represented as such.

But sometimes, shifting columns give a Vuza canon anyway ! For example, if we take the Vuza canon of length 180 with motive A= 0,5,6,12,13,17,21,29,36,42,48,65,72,73,77,78,81,84,89,108,114,120,125,133,137,141,144,149,150,156, and entries E=0,18,20,38,40,58, it can be represented as such in $\mathbb{Z}_{9} \times \mathbb{Z}_{20}$. It has a motive A=0,5,6,12,17,21,29,36,42,48,53,65,72,77,78,81,84,89,108,113,114,120,125,137,141,144,149,150,156,173, and the same entries, and is non-periodic.