I’m going to continue today on the subject of rhythmic canons, which I first introduced here. I have mainly focused on *rhythmic canons mod p*, but today I’d like to speak about rhythmic canons in general and, from a mathematical point of view, look at the differences between rhythmic canons in and those in . I will define again rhythmic canons, and in doing so I will probably overlap my previous post, but I think this is necessary for clearly explaining the stakes.

**Rhythmic canons**

The subject of rhythmic canons can be mathematically, and informally, formulated as follows: given a finite subset of , can we pave by translates of ? In other words, is there a such that we have ? The elements of represents here the musical beats.

Already this problem takes another formulation, owing to a theorem of De Bruijn, which claims that if we have , then there exists and a subset such that . In other words, we get a *periodic* canon, meaning that all we have to do is to find a and an integer such that .

Observe that we are defining rhythmic canons in a very specific way, where no beat is filled by more than one element of or its translates.

To solve the problem of whether tiles and how, it is necessary to reformulate the problem in a more appropriate setting. We consider the polynomial of such that . The polynomial has coefficients either 0 or 1, what we will call from now on a *0-1 polynomial. *The problem is now to find a 0-1 polynomial and such that we have

in .

**Compact and non-compact canons**

Sometimes, imposing that we should work in is not necessary. Consider for example the motive , i.e. , represented graphically below.

Then tiles with , as shown below.

Indeed, is equal to

.

Observe that this multiplication holds in alone (and therefore in ). In general, if holds in , then we say that we a have a *compact rhythmic canon*.

On the contrary, the motive

tiles with , but in a non-compact way. Indeed, does not hold in , as shown below.

However it holds in , as shown below (the red lines indicate the periodicity of the canon).

**Why do we consider rhythmic canons mod p ?**

Let’s recall our problem. Given , find a 0-1 polynomial and such that we have

in

This is quite difficult ! The polynomial might not even exist. So, people have been thinking about a slightly similar problem, namely to replace , which is not even a field, by something easier, i.e. a finite field .

The problem becomes

in

Musically, this amounts to finding a canon where no beat is filled by more than one element *mod p* of or its translates. For example, in , tiles with giving a canon of length 7, as shown below.

Why is it easier ? Emmanuel Amiot was maybe the first to remark that any given tiles *mod p*. Indeed, it is not difficult to remark that, in the quotient ring , there always exists such that . This means that in , we have for some polynomial . Multiplying by , we get

in .

All this is very well, but the polynomial is not necessarily a 0-1 polynomial. However, we have yet another trick to exploit from , namely that the coefficients of are all positive. This means that we can rewrite as , and so on until all coefficients are 0 or 1, and thus obtain a polynomial such that

in

The work of Hélianthe Caure, which I talked about in previous posts, focused on rhythmic canons *mod 2*. Observe that in that case, all the canons are compact since the coefficients in are always 0 or 1. She delved into the details of particular motives of the form and . What is particularly interesting (and a bit amazing if you ask me) is that she was able to precisely give a general formula for the lengths of the rhythmic canons formed upon these motives, as well as a very efficient way of finding the polynomial . The above result simply indicates that such a canon exists but does not give any general indication about its length. It is always possible to calculate it explicitly, but this has to be done for each . The beauty of Hélianthe’s work lies in its generality.

Toying around with her work, here are some open conjectures I propose on rhythmic canons *mod p*:

* Conjecture: *In where is prime (except for ), (non-compact) canons of motive have a length of .

* Conjecture: *In , canons of motive have a length of .

* Conjecture: *In , canons of motive have a length of .

* Conjecture: *In , canons of motive have a length of .

* Conjecture: *In , canons of motive have a length of .

And so on…

**Back to rhythmic canons**

We now return to the problem

in

Unfortunately, we cannot use the same approach as for , namely considering the quotient ring , because we are not guaranteed here that we would find a such that , and even if we did, the polynomial is not guaranteed to have 0-1 coefficients.

For example, consider . Since (where is the k-th cyclotomic polynomial), we have in , and thus , but has negative coefficients and we cannot use the trick exposed above anymore.

Any polynomial in can be factorized as , where is a product of a cyclotomic polynomials, and is an ordinary non-cyclotomic polynomial. In , there exists a such that . We can thus get a necessary condition on whether tiles or not: if tiles with length , then we have

in

For example, consider , which factorizes as

.

If tiles, it does with a length which is a multiple of 12. However, in , which is the finite ring , the sum is equal to , thus showing that does not pave with a length 12.

However, this is only a necessary condition, and not a very strong one. For example, consider , which factorizes as

.

In the finite ring , which is in fact the finite field , the sum is equal to 0. Yet we know (see below) that is unable to pave.

**The conditions of Coven and Meyerowitz**

Recently, Coven and Meyerowitz have significantly advanced the understanding of the tiling problem (i.e. rhythmic canons). The reference is the following paper.

- Ethan M. Coven, Aaron D. Meyerowitz, “Tiling the integers with translates of one finite set”, available on Arxiv.

First, some definitions. Given the factorization , where is a product of a cyclotomic polynomials, we define the set to be the set of orders of the cyclotomic polynomials in , and the set to be the subset of consisting of prime powers.

We then introduce the two conditions (T1) and (T2).

* Condition (T1)*:

* Condition (T2)*: If , , are in , then is in .

And now for the results of Coven and Meyerowitz.

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

This is much better !

For example, let’s consider again which factorizes as

We have , and which is not equal to 2, thus we can immediately conclude that does not pave.

Inversely, consider (this example is taken from Amiot) which factorizes as

with

.

We have , and . So condition (T1) is true, since , and condition (T2) is also true since . Thus we conclude that tiles. And indeed it does, with a length of 36, and .

To conclude this post, it should be noted that in all known rhythmic canons, condition (T2) is verified. Whether it is always true that tiles implies that condition (T2) is true, remains an open problem. The tiling problem is also related to the spectral conjecture of Fuglede, which I will not explain here. If you want to know more, please consult the following excellent references by Emmanuel Amiot, on which this post was largely based.

- Emmanuel Amiot, “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
- Emmanuel Amiot, “Structures, Algorithms, and Algebraic Tools for Rhythmic Canons”, Perspectives of New Music, Vol. 49, No. 2 (Summer 2011), pp. 93-142