Rhythmic canons (5)

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 $\mathbb{Z}[X]$ and those in $\mathbb{F}_p[X]$ . 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 $A$ of $\mathbb{N}$ , can we pave $\mathbb{Z}$ by translates of $A$ ? In other words, is there a $C$ such that we have $A \bigoplus C = \mathbb{Z}$ ? The elements of $\mathbb{Z}$ represents here the musical beats.

Already this problem takes another formulation, owing to a theorem of De Bruijn, which claims that if we have $A \bigoplus C = \mathbb{Z}$ , then there exists $n \in \mathbb{N}$ and a subset $B$ such that $C = B \bigoplus n\mathbb{Z}$ . In other words, we get a periodic canon, meaning that all we have to do is to find a $B$ and an integer $n$ such that $A \bigoplus B = \mathbb{Z}_n$ .

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

To solve the problem of whether $A$ tiles and how, it is necessary to reformulate the problem in a more appropriate setting. We consider the polynomial $A(X)$ of $\mathbb{Z}[X]$ such that $A(X)=\sum_{k \in A} X^k$ . The polynomial $A(X)$ 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 $B(X)$ and $n \in \mathbb{N}$ such that we have

$A(X)B(X)=1+\ldots+X^{n-1}$ in $\mathbb{Z}[X]/(X^n-1)$ .

Compact and non-compact canons

Sometimes, imposing that we should work in $\mathbb{Z}[X]/(X^n-1)$ is not necessary. Consider for example the motive $A=\{0,3\}$ , i.e. $A(X)=1+X^3$ , represented graphically below.

Then $A$ tiles $\mathbb{Z}_6$ with $B=\{0,1,2\}$ , as shown below.

Indeed, $A(X)B(X) = (1+X^3)(1+X+X^2)$ is equal to

$A(X)B(X) = 1+X+X^2+X^3+X^4+X^5$ .

Observe that this multiplication holds in $\mathbb{Z}[X]$ alone (and therefore in $\mathbb{Z}[X]/(X^6-1)$ ). In general, if $A(X)B(X)=1+\ldots+X^{n-1}$ holds in $\mathbb{Z}[X]$ , then we say that we a have a compact rhythmic canon.

On the contrary, the motive $A=\{0,1,3,7,9\}$

tiles $\mathbb{Z}_{10}$ with $B=\{0,5\}$ , but in a non-compact way. Indeed, $A(X)B(X)=1+\ldots+X^9$ does not hold in $\mathbb{Z}[X]$ , as shown below.

However it holds in $\mathbb{Z}[X]/(X^{10}-1)$ , 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 $A(X)$ , find a 0-1 polynomial $B(X)$ and $n \in \mathbb{N}$ such that we have

$A(X)B(X)=1+\ldots+X^{n-1}$ in $\mathbb{Z}[X]/(X^n-1)$

This is quite difficult ! The polynomial $B(X)$ might not even exist. So, people have been thinking about a slightly similar problem, namely to replace $\mathbb{Z}$ , which is not even a field, by something easier, i.e. a finite field $\mathbb{F}_p$ .

The problem becomes

$A(X)B(X)=1+\ldots+X^{n-1}$ in $\mathbb{F}_p[X]/(X^n-1)$

Musically, this amounts to finding a canon where no beat is filled by more than one element mod p of $A$ or its translates. For example, in $\mathbb{F}_2[X]$ , $A=\{0,1,3\}$ tiles with $B=\{0,2,3\}$ giving a canon of length 7, as shown below.

Why is it easier ? Emmanuel Amiot was maybe the first to remark that any given $A$ tiles mod p. Indeed, it is not difficult to remark that, in the quotient ring $\mathbb{F}_p[X]/A$ , there always exists $n \in \mathbb{N}$ such that $X^n=1$ . This means that in $\mathbb{F}_p[X]$ , we have $X^n-1=A(X)C(X)$ for some polynomial $C(X)$ . Multiplying by $X-1$ , we get

$1+\ldots+X^{n-1}=A(X)B(X)$ in $\mathbb{F}_p[X]$ .

All this is very well, but the polynomial $B(X)$ is not necessarily a 0-1 polynomial. However, we have yet another trick to exploit from $\mathbb{F}_p[X]$ , namely that the coefficients of $B(X)$ are all positive. This means that we can rewrite $a_kX^k$ as $(a_k-1)X^k+X^{n+k}$ , and so on until all coefficients are 0 or 1, and thus obtain a polynomial $B'(X)$ such that

$A(X)B'(X)=1+\ldots+X^{n-1}$ in $\mathbb{F}_p[X]/(X^n-1)$

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 $\mathbb{F}_2[X]$ are always 0 or 1. She delved into the details of particular motives of the form $A(X)=1+X+X^{2^k}$ and $A(X)=1+X+X^{2^k+1}$ . 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 $B(X)$ . 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 $A(X)$ . 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 $\mathbb{F}_p[X]$ where $p$ is prime (except for $p=3$ ), (non-compact) canons of motive $A=1+X+X^{p^k}$ have a length of $n=p^{2^k}-1$ .

Conjecture: In $\mathbb{F}_2[X]$ , canons of motive $A=1+X+X^{2^{2k}+2^k+1}$ have a length of $n=\sum_{i=0}^{6} 2^{ki}$ .

Conjecture: In $\mathbb{F}_2[X]$ , canons of motive $A=1+X+X^{\sum_{j=0}^{3} 2^{jk}}$ have a length of $n=\sum_{i=0}^{14} 2^{ki}$ .

Conjecture: In $\mathbb{F}_2[X]$ , canons of motive $A=1+X+X^{\sum_{j=0}^{4} 2^{jk}}$ have a length of $n=\sum_{i=0}^{20} 2^{ki}$ .

Conjecture: In $\mathbb{F}_2[X]$ , canons of motive $A=1+X+X^{\sum_{j=0}^{5} 2^{jk}}$ have a length of $n=\sum_{i=0}^{62} 2^{ki}$ .

And so on…

Back to rhythmic canons

We now return to the problem

$A(X)B(X)=1+\ldots+X^{n-1}$ in $\mathbb{Z}[X]/(X^n-1)$

Unfortunately, we cannot use the same approach as for $\mathbb{F}_p[X]$ , namely considering the quotient ring $\mathbb{Z}[X]/A$ , because we are not guaranteed here that we would find a $n$ such that $X^n=1$ , and even if we did, the polynomial $B(X)$ is not guaranteed to have 0-1 coefficients.

For example, consider $A(X)=1+X^2+X^3+X^5+X^6+X^8$ . Since $A(X)=\Phi_4(X)\Phi_9(X)$ (where $\Phi_k(X)$ is the k-th cyclotomic polynomial), we have $X^{36}=1$ in $\mathbb{Z}[X]/A$ , and thus $1+\ldots+X^{35}=A(X)B(X)$ , but $B(X)$ has negative coefficients and we cannot use the trick exposed above anymore.

Any polynomial $A(X)$ in $\mathbb{Z}[X]$ can be factorized as $A(X)=\Phi(X)M(X)$ , where $\Phi(X)$ is a product of a cyclotomic polynomials, and $M(X)$ is an ordinary non-cyclotomic polynomial. In $\mathbb{Z}[X]/\Phi$ , there exists a $n$ such that $X^n=1$ . We can thus get a necessary condition on whether $A$ tiles or not: if $A$ tiles with length $n$ , then we have

$1+\ldots+X^{n-1}=0$ in $\mathbb{Z}[X]/(X^n-1,M)$

For example, consider $A=\{0,3,4,6,7,9\}$ , which factorizes as

$A(X)=\Phi_2(X)\Phi_6(X)(X^6+X^4+1)$ .

If $A$ tiles, it does with a length which is a multiple of 12. However, in $\mathbb{Z}[X]/(X^{12}-1,X^6+X^4+1)$ , which is the finite ring $(\mathbb{Z}/9\mathbb{Z})[X]/(X^2+5)$ , the sum $1+\ldots+X^{11}$ is equal to $6+6X$ , thus showing that $A$ does not pave with a length 12.

However, this is only a necessary condition, and not a very strong one. For example, consider $A=\{0,2,5,8,10,13\}$ , which factorizes as

$A(X)=\Phi_{16}(X)(X^5+X^2+1)$ .

In the finite ring $\mathbb{Z}[X]/(X^{16}-1,X^5+X^2+1)$ , which is in fact the finite field $\mathbb{F}_7[X]/(X^2+4X+6)$ , the sum $1+\ldots+X^{15}$ is equal to 0. Yet we know (see below) that $A$ 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 $A(X)=\Phi(X)M(X)$ , 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.

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

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$ .

And now for the results of Coven and Meyerowitz.

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.

This is much better !

For example, let’s consider again $A=\{0,2,5,8,10,13\}$ which factorizes as

$A(X)=\Phi_{16}(X)(X^5+X^2+1)$

We have $S_A=\{2^4\}$ , and $A(1)=6$ which is not equal to 2, thus we can immediately conclude that $A$ does not pave.

Inversely, consider $A=\{0,1,8,9,17,28\}$ (this example is taken from Amiot) which factorizes as

$A(X)=\Phi_{2}(X)\Phi_{3}(X)\Phi_{6}(X)\Phi_{12}(X)\Phi_{18}(X)M(X)$

with

$M(X)=1+X^3-X^4-X^7+X^8-X^9+X^{11}-X^{12}+X^{13}$ .

We have $R_A=\{2,3,6,12,18\}$ , and $S_A=\{2,3\}$ . So condition (T1) is true, since $A(1)=6=2 \times 3$ , and condition (T2) is also true since $6 \in R_A$ . Thus we conclude that $A$ tiles. And indeed it does, with a length of 36, and $B=\{0,6,12,18,24,30\}$ .

To conclude this post, it should be noted that in all known rhythmic canons, condition (T2) is verified. Whether it is always true that $A$ 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

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

alpof

Random thoughts about music and math, science and sometimes legos…

Rhythmic canons (5)

Leave a Reply

Rhythmic canons (5)

Share this:

Like this:

Related

Leave a Reply