Enumeration of non-isomorphic canons

Harald Fripertinger

Abstract

In this note we describe how to apply group actions in order to enumerate the isomorphism classes of rhythmic canons.

The notion of a rhythmic canon was originally formalized by O. Messiaen. He proposed to study canonical musical forms in which the imitation between the different voices concerns only rhythmical aspects, independent from melody or harmony. The first mathematical investigation of rhythmic canons goes back to Vuza’s papers [79810] in which he actually introduced even much more complicated families of canons, the “Regular Complementary Canons of Maximal Category” (in short RCMC-canons). Their definition will be given below.

Before describing rhythmic canons in cyclic time, we view them as they may appear within a musical composition, in free linear time which has no cyclicity. Like in a melodic canon, one has several voices that may enter one after the other until all voices are present. As in the case of a melodic canon, all voices are just copies of a ground voice that is suitably translated in the time axis. For simplicity we suppose here that all voices are extended in both directions of the time axis ad infinitum. We further suppose that the ground voice is a periodic rhythm that we will call the inner rhythm. Following Vuza’s definition, a periodic rhythm is an infinite subset R of the rationals Q (marking the attack times, or onsets) with R = R + d for a suitable period d. Furthermore, R is supposed to be locally finite (i.e. the intersection of R with every time segment [a, b] (of finite length b - a > 0) is finite). The period of a periodic rhythm R is the smallest positive rational number d = d(R) satisfying R = R + d. We also mention another important characteristic of a periodic rhythm, its pulsation p = p(R). It is defined as the max {q  (-  Q+ |  A r  (-  R - R  E z  (-  Z : r = zq}, in other words, it is the biggest rational q such that all distances between the attack points of R are integer multiples of q. Obviously, the period d is an integer multiple of the pulsation p.

Let A be the set of all rational numbers a such that the attack times of the voices of the canon can be expressed as R + a. Then A itself is a periodic rhythm, called the outer rhythm of the canon, with period d(A), where d(R) is an integer multiple of d(A). Note that R and A may have different pulsations p(R) and p(A). Hence, the pulsation of a canon is defined as the greatest rational number p such that both p(R) and p(A) are integer multiples of p.

In order to switch from linear time to circular time the fraction n = d(R)/p must be computed. Let r denote a fixed attack time within the inner rhythm R. Then each attack time in any of the voices is of the form r + tp for a suitable integer t, i.e. the whole canon is contained in r + pZ < Q. Because everything is periodic with period d(R), we can restrict to the factor space (r + pZ)/d(R)Z which may be identified with Z/nZ, the residue class ring of Z modulo nZ.

From now on, we consider the whole canon within Zn := Z/nZ and assume that R, A, and V a denote the projections of the inner rhythm, the outer rhythm, and the voices of a canon.

The concept of a canon used in the present paper is described by G. Mazzola in [4] and was presented by him to the author in the following way: A canon is a subset K  (_ Zn together with a covering of K by pairwise different subsets, the voices, V i/= for 1 < i < t, where t > 1 is the number of voices of the canon,

      U t
K =     Vi,
     i=1

such that for all i, j  (- {1, ...,t}

  1. the set V i can be obtained from V j by a translation of Zn,
  2. there is only the identity translation which maps V i to V i,
  3. the set of differences in K generates Zn, i.e. <K - K> := <k - l | k, l  (- K> = Zn.

We prefer to write a canon K as a set of its subsets V i. Two canons K = {V1,...,Vt} and L = {W1, ...,Ws} are called isomorphic if s = t and if there exists a translation T of Zn and a permutation p in the symmetric group St such that T (V i) = W p(i) for 1 < i < t. Then obviously T (K) = L.

The aim of this note is to determine the number of non-isomorphic canons for given n. First we present the definition of canons in more details and give a short description of group actions, which are the standard tool to describe isomorphism classes of different objects (cf.[23]). Since we are interested in the attack times modulo n, we assume that K is a subset of Zn. The set of translations of Zn is the cyclic group Cn generated by the permutation sn := (0, 1, ..., n - 1) which maps i to i + 1 mod n. Cn acts in a natural way both on Zn and on the set of all subsets of Zn:

sn(i) = i + 1, i  (-  Zn, and sn(A) = {sn(i) |i  (-  A},  A   (_  Zn.

As usual we identify a subset A of Zn with its characteristic function xA : Zn --> {0,1} given by

        {
xA(i) =   1  if i  (-  A
          0  otherwise.

The set of all functions from a set X to a set Y will be indicated as Y X. For arbitrary f  (- {0,1} Zn let f denote the subset f-1({1}) of Z n, whence f = xf .

Sometimes it is convenient to write functions f from Zn to {0,1} as vectors of the form (f(0), f(1), ..., f(n - 1)) using the natural order of the elements of Zn, because then the set of all these functions is totally ordered by the lexicographic order. For functions f, g  (- {0,1} Zn we say f < g if there exists an i  (- Z n such that f(j) = g(j) for 0 < j < i and f(i) < g(i). The group action of Cn on the set of all subsets of Zn described as an action on the set of all characteristic function is the following

Cn  {0,1}Zn -->  {0,1}Zn      (sj,f) '-->  f o s -j.
                               n            n

As the canonical representative of the orbit Cn(f) = {f o sj |0 < j < n -  1}
      n we choose the function f0  (- Cn(f) such that f0 < g for all g  (- Cn(f). Moreover, we choose f 0 as the canonical representative of the orbit Cn(f ) = {  j                  }
 s n(f)| 0 < j < n - 1. In general, representatives of orbits Cn(f) of functions f under the action of the cyclic group Cn are called necklaces.

Lemma 1. If f/=0 denotes a function from Zn to {0,1}, then the canonical representative f0 of the orbit Cn(f) fulfills f0(n - 1) = 1.

A function f  (- {0,1} Zn (or the corresponding vector and the set f ) is called acyclic if C n(f) consists of n different objects. The canonical representative of the orbit of an acyclic function is usually called a Lyndon word. If f is acyclic, then all elements in the orbit Cn(f) are acyclic as well, and we call Cn(f) an acyclic orbit.

From the first two properties of a canon we derive that all voices V i belong to the same orbit Cn(V 1) and that each voice is acyclic. For that reason, we can describe a canon K = {V1,...,Vt} as a pair (L, A) where L is the Lyndon word, which is the canonical representative of the orbit Cn(xV 1), and A = {a1, ...,at} is a t-subset of Zn such that V i = snai(L). In other words, L describes the inner rhythm and A the outer rhythm of K.

Now we analyse in which situations a pair (L, A), as described above, is not a canon, i.e. when it fails to fulfill the third property. Assume that (L, A) is not a canon, then the differences K - K generate a proper subgroup of Zn. This subgroup is isomorphic to Zn/d where d > 1 is a divisor of n. In other words, d is a divisor of all differences k - l for all k, l  (- K. We write d | r in order to express that the integer d is a divisor of the integer r. (It is not connected with division in the ring Zn.) It is easy to prove the following

Lemma 2. Let L/=0 be a Lyndon word of length n, and let A be a t-subset of Zn. The pair (L, A) does not describe a canon in Zn if and only if there exists an integer d > 1 such that d | n, d | k - l for all k, l  (- L, and d | k - l for all k, l  (- A.

Consider the set S of all pairs (L, A) where L is a Lyndon word and A is a t-subset of Zn. The group of translations of Zn acts on S according to

                   j                j
Cn   S -->  S     (s n,(L,A)) '-->  (L, sn(A)).

If (L, A) is a canon, then the orbit Cn(L, A) = (L, Cn(A)) describes the isomorphism class of (L, A). In general, the canonical representative of Cn(L, A) is (L, A0) where A0 is the canonical representative of Cn(A). From Lemma 1 we already know that xA0(n - 1) = 1 and L(n - 1) = 1 if L/=0. This together with Lemma 2 proves

Lemma 3. Let L/=0 be a Lyndon word of length n, and let A be a t-subset of Zn. The pair (L, A) does not describe a canon in Zn if and only if there exists a divisor d > 1 of n such that L(i) = 1 implies i  =_ d - 1 mod d, and xA0(i) = 1 implies i  =_ d - 1 mod d, where A0 is the canonical representative of Cn(A).

In the next part we show that functions f  (- {0, 1} Zn with the property f(i) = 1 implies i  =_ -1 mod d (for d | n, d > 1) can be constructed from functions in {0, 1} Zn/d . Let yd be a function defined on {0,1}, such that yd(0) is the vector (0, 0, ..., 0) consisting of d entries of 0, and yd(1) = (0, ..., 0, 1) is a vector consisting of d - 1 entries of 0 and 1 in the last position. We write the values of yd in the form

         d               d-1
yd(0) = 0 ,     yd(1) = 0   1.

If we apply yd to each component of a vector f  (- {0,1} Zr by replacing each component 0 in f by 0d and each component 1 by 0d-11, we get a vector y d(f)  (- {0, 1} Zrd and

        Zr    {          Zrd                                }
yd({0,1}  ) =   f  (-  {0,1}   |f(i) = 1 implies i  =_  - 1 mod d  .

From Lemma 3 we conclude that (L, A) does not describe a canon if and only if there exists a d > 1 which divides n such that both L and xA0 are elements of yd({0,1} Zn/d ).

Some properties of yd are collected in the next

Lemma 4. Let f, g be functions from Zr to {0,1}. Then
  1. yd(f) = yd(g) if and only if f = g.
  2. yd(f o sr) = yd(f) o srdd.
  3. yd(Cr(f)) < Crd(yd(f)).
  4. f < g if and only if yd(f) < yd(g).
  5. f0 is the canonical representative of Cr(f) if and only if yd(f0) is the canonical representative of Crd(yd(f)).
  6. yd describes a bijection between the Cr-orbits on {0, 1} Zr and the C rd-orbits on {0,1} Zrd which have non-empty intersection with y d({0,1} Zr), thus
    |{Crd(A) | A  (_  Zrd, A /= , d |k - l  A k,l  (-  A} |=

    |{Cr(A)  |A   (_  Zr, A /= }|=: a(r).

  7. f/=0 is acyclic if and only if yd(f) is acyclic.
  8. yd describes a bijection between the acyclic Cr-orbits on {0,1} Zr and the acyclic Crd-orbits on {0,1} Zrd which have non-empty intersection with y d({0, 1} Zr), thus
    |{Crd(A)  |A   (_  Zrd, A /= , d| k-  l  A k, l  (-  A, A acyclic}|=

    |{Cr(A)  |A  (_  Zr, A /=  , A acyclic} |=: c(r).

  9. Both f and yd(f) have the same number of components which are 1.
Proof.  Since yd is an injective mapping from each component of f into the set {0d,0d-11}, the first statement is clear.

In order to show that the second item is true, assume that yd(f o sr)(j) = 1 for some j  (- Zrd. According to the definition of yd, this is equivalent to j = sd - 1 and (f o sr)(s - 1) = 1 for some s  (- {1,...,r}. In other words, j = sd - 1 and f(s) = 1, which is equivalent to j = sd - 1 and yd(f)((s + 1)d - 1) = 1. This, however, is the same as yd(f)(j + d) = 1, whence (yd(f) o srdd)(j) = 1. If f = 0 the assertion is always true.

The third part is an immediate consequence of the second.

If f < g, then there exists i  (- Zr such that f(j) = g(j) for all j < i and f(i) < g(i), whence f(i) = 0 and g(i) = 1. For that reason, yd(f(i)) = 0d and y d(g(i)) = 0d-11. Hence, yd(f)(j) = yd(g)(j) for j < id-1 and yd(f)(id-1) = 0 < 1 = yd(g)(id-1), and consequently yd(f) < yd(g). If, conversely, yd(f) < yd(g), then there exists an i  (- Zrd such that yd(f)(j) = yd(g)(j) for all j < i and yd(f)(i) < yd(g)(i), whence yd(g)(i) = 1 and i  =_ -1 mod d. Assume that i is of the form sd - 1. Then yd(f(j)) = yd(g(j)) for j < s, and yd(f(s)) = 0d whereas y d(g(s)) = 0d-11. Since y d is an injective mapping, f(j) = g(j) for j < s and f(s) = 0 < 1 = g(s), which implies that f < g.

From the definition of the canonical representative of an orbit and from the items 4. and 2. it follows immediately that yd(f0) < yd(f0 o srj) = yd(f0) o srddj for all j  (- {1, ...,r- 1}. Moreover, if n / =_ 0 mod d, then (yd(f0) o srdn)(rd - 1) = yd(f0)(n - 1)/=1, since n - 1 / =_ -1 mod d. According to Lemma 2, the representative yd(f0) o srdn cannot be the canonical representative of the orbit Crd(yd(f0)). Hence, the canonical representative is yd(f0).

Then 6. is a trivial consequence of 5. Similar arguments can be applied for proving 7. and 9. Item 8. follows immediately from 7.       []

In order to compute the number of all Cr-orbits on {0,1} Zr we apply Pólya’s theory cf. [2356]. In the present situation we have to compute the cycle index of the group Cr acting on Zr which is a polynomial in z1, ..., zr over Q given by

            1  sum 
C(Cr, Zr) = --    f(s)zrs/s,
            r  s|r

where f is the Euler totient function. Replacing each indeterminate zi in C(Cr, Zr) by |{0, 1}|, which is equal to 2, we compute the number of all Cr-orbits on {0, 1} Zr as

                    1  sum        r/s
C(Cr, Zr,zi :=  2) = --   f(s)2   .
                    r s|r

If we replace zi by 1 + zi, where z is an indeterminate over Q, then the number of C r-orbits of k-sets A  (_ Zr is the coefficient of zk in

                           sum 
C(C  ,Z ,z := 1 + zi) = 1-    f(s)(1 + zi)r/s.
    r  r  i             r
                           s|r

In conclusion (for the definition of a(r) see 6. in Lemma 4)

a(r) = C(Cr, Zr,zi :=  2)- 1,

since we don’t count the orbit of the empty set. Similar methods can be applied to enumerate the number of acyclic Cr-orbits on {0,1} Zr or, what is equivalent to this, to enumerate all Lyndon words of length r over the alphabet {0,1}. For r > 1, this number is given as (for the definition of c(r) see 8. in Lemma 4)

        1  sum        r/s
c(r) =  --   m(s)2   ,
        r s|r

where m is the classical Moebius function. Moreover, the number of Lyndon words of length r over {0, 1} having r1 components 1 and r - r1 components 0 is

                (     )
1-    sum            r/s
r           m(s)  r1/s  .
 s|gcd(r- r1,r1)

And the generating function of Lyndon words of length r over the alphabet {0,1} with r1 components 1 is of the form

      (                (     ))
1 r sum -1       sum             r/s      r1
r-                 m(s) r /s     y .
  r1=1   s|gcd(r-r1,r1)      1

In the case r = 1 there are two Lyndon words, namely f0 = (0) and f1 = (1). The first one is the characteristic function of the empty set in Z1 so we don’t want to count it. For that reason, we must set c(1) = 1. Moreover, it should be mentioned that f0 is the unique Lyndon word such that yd(f0) is not a Lyndon word for d > 1.

Finally, we have to combine all these results for enumerating the isomorphism classes of canons. Let n > 1 be an integer. For any divisor d > 1 of n, let Mn,d be the set of all pairs (L, Cn(A)), where L is a Lyndon word of length n over {0,1}, (in the case n = 1 different from 0) such that L(i) = 1 implies i  =_ -1 mod d, and A is a non-empty subset of Zn, such that d | k - l for all k, l  (- A. Hence

        {                                                                }
M    =   (L, C (A)) |  L Lyndon  word,  L /= 0, L(i) = 1 ==>  i  =_  - 1 mod d   .
  n,d         n        A  (_  Zn, A /= , d |k - l  A k,l  (-  A

From Lemma 4 we deduce that yd describes a bijection between Mn,d and Mn/d,1, thus

         ||      ||
|Mn,d| =  Mn/d,1 =  c(n/d)a(n/d),

which is the number of possibilities to choose L and Cn(A) according to the desired properties of Mn,d. Finally, let kn be the set of isomorphism classes of canons in Zn,

kn = {(L, Cn(A))  (-  Mn,1 |(L,A)  describes a canon}.

From Lemma 3 we deduce that

             U 
kn = Mn,1 \    Mn,d.
            d>1
            d|n

Theorem. The number of isomorphism classes of canons in Zn is
       sum 
|kn |=     m(d)c(n/d)a(n/d).
       d|n

Proof.  First we prove that the set Mn,1 is the disjoint union
         .
Mn,1  =  U  yd(kn/d),
        d|n

where

            {                                   }
yd(kn/d) =   yd(L, Cn/d(A)) |(L, Cn/d(A))  (-  kn/d

and

                             -------
yd(L, Cn/d(A)) = (yd(L), Cn( yd(xA))).

It is clear that Mn,1 contains this union. Moreover, this union is disjoint, since for a canon K = (L, Cn/d(A))  (- kn/d we have

<K - K > = Zn/d ~=  <yd(K) -  yd(K) >.

Finally, we have to show that each element of Mn,1 belongs to this union. If (L, Cn(A))  (- Mn,1, then choose the biggest d such that (L, Cn(A)) belongs to Mn,d. (I.e. (L, Cn(A)) does not belong to Mn,dd' for d' > 1. It is always possible to find such d, since, if (L, Cn(A)) belongs both to Mn,d1 and Mn,d2, then it also belongs to Mn,lcm(d1,d2).) Then there exists (L', C n/d(A'))  (- M n/d,1 such that L = yd(L') and xA0 = yd(xA0' ) for the canonical representatives A0 and A0' of C n(A) and Cn/d(A'). Moreover, (L', C n/d(A'))  (- k n/d because otherwise there would be some d' > 1 which is a divisor of n/d such that (L', C n/d(A'))  (- M n/d,d' . But then (L, Cn(A)) also belongs to Mn,dd' , which is a contradiction to the choice of d.

Hence,

          sum   |    |   sum 
|Mn,1| =     |kn/d|=     |kd|,
          d|n          d|n

and by Moebius inversion we get

       sum                    sum       |      |    sum                 sum 
|kn |=     m(n/d) |Md,1| =     m(d)|Mn/d,1| =     m(d)|Mn,d| =     m(d)c(n/d)a(n/d),
       d|n                 d|n                d|n               d|n

which finishes the proof.       []

If c and a are replaced by the corresponding generating functions

       {         (                       )
         1  sum r -1 s um            m(s)(r/s)  yr1  if r > 1
c(r) =   r   r1=1    s|gcd(r-r1,r1)     r1/s
         y                                      if r = 1

and

                           i
a(r) =  C(Cr, Zr,zi := 1 + z )- 1,

then the coefficient of yszt in

 sum 
    m(d)c(n/d)a(n/d)
 d|n

gives the number of non-isomorphic canons in Zn which consist of t voices where each voice contains exactly s attack times.

For example the numbers of isomorphism classes of canons in Zn for 1 < n < 10 are:

      |
   n  |1  2  3  4   5   6    7    8      9     10
-|k-|-|1--1--5--13--41--110--341--1035---3298--10550--
   n  |

Finally, we have a closer look at the 13 isomorphism classes of canons in Z4, which can be classified according to their number of voices and attack times per voice by z4y3 + z4y2 + z4y + z3y3 + z3y2 + z3y + 2z2y3 + 2z2y2 + z2y + zy3 + zy2. From this list we can read, for instance, that there are exactly three classes of canons with 4 voices which have 1, 2, or 3 attack times per voice. Or we see that there are five classes of canons with 2 voices, two of them having 3 attack times per voice, two of them having 2 attack times per voice, and only one having 1 attack time in each of its two voices.

We can even compute the canonical representative of each isomorphism class. For instance, there are exactly three Lyndon words L1, L2, L3 of length 4 over {0,1} and five representatives f1, ..., f5 of the C4-orbits of non empty subsets of Z4:

L1 = (0,0,0, 1)                 f1 = (0,0,0,1)
L  = (0,0,1, 1)                 f =  (0,0,1,1)
 2                               2
L3 = (0,1,1, 1)                 f3 = (0,1,0,1)
                                f4 = (0,1,1,1)
                                f5 = (1,1,1,1)

The Lyndon words describe the distribution of the attack times in one voice (i.e. the inner rhythm of the canon), the necklaces describe the distribution of the voices over the complete period, here in this example over Z4, which is the outer rhythm. Only L1 can be constructed as y4((1)) or y2((0, 1)) from shorter Lyndon words, so all pairs (Li, fj) for i  (- {2,3} and j  (- {1,...,5} describe canons in Z4. Since f1 = y4((1)) = y2((0, 1)) and f3 = y2((1, 1)), and (1), (0, 1), and (1, 1) are necklaces of length 1 or 2 over {0,1}, the pairs (L1, C4(f1)) = y4((1), C1(1)) and (L1, C4(f3)) = y2((0, 1), C2(1, 1)) do not belong to k4. But the pairs (L1, fj) for j  (- {2,4,5} describe again canons in Z4.

From this example we also see how to compute complete lists of isomorphism classes of canons in Zn for arbitrary n. There exist fast algorithms for computing all Lyndon words and all necklaces of length n over {0,1}. Then each pair (Li, fj) must be tested whether there exists some d > 1 such that (Li, fj) = (yd(L'), y d(f')) for a Lyndon word L' and a necklace f' of length n/d.

There exist more complicated definitions of canons. A pair (R, A) of inner and outer rhythm defines a rhythmic tiling canon with voices V a for a  (- A in Zn if and only if

  1. the voices V a cover entirely the cyclic group Zn,
  2. the voices V a are pairwise disjoint.

It is obvious that periods and pulsations can be determined in cyclic time as well. Rhythmic tiling canons with the additional property,

  1. the periods d(R) and d(A) coincide,

are called regular complementary canons of maximal category. So far we were not dealing with that kind of canons.

Acknowledgment: The author wants to express his thanks to Guerino Mazzola for pointing his attention to the problem of classification of canons. He is also grateful to Moreno Andreatta, who provided very useful historic and background information about different definitions of canons (cf [1]).

References

[1]   M. Andreatta, Th. Noll, C. Agon, and G. Assayag. The geometrical groove: rhythmic canons between theory, implementation and musical experiment. In Les Actes des 8e Journées d’Informatique Musicale, Bourges 7-9 juin 2001, pages 93-97, 2001.

[2]   A. Kerber. Algebraic Combinatorics via Finite Group Actions. B.I. Wissenschaftsverlag, Mannheim, Wien, Zürich, 1991. ISBN 3-411-14521-8.

[3]   A. Kerber. Applied Finite Group Actions, volume 19 of Algorithms and Combinatorics. Springer, Berlin, Heidelberg, New York, 1999. ISBN 3-540-65941-2.

[4]   G. Mazzola. Topos of music. To appear.

[5]   G. Pólya. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica, 68:145 - 254, 1937.

[6]   G. Pólya and R.C. Read. Combinatorial Enumeration of Groups, Graphs and Chemical Compounds. Springer Verlag, New York, Berlin, Heidelberg, London, Paris, Tokyo, 1987. ISBN 0-387-96413-4 or ISBN 3-540-96413-4.

[7]   D.T. Vuza. Supplementary sets and regular complementary unending canons (part one). Perspectives of New Music, 29(2):22-49, 1991.

[8]   D.T. Vuza. Supplementary sets and regular complementary unending canons (part three). Perspectives of New Music, 30(2):102-125, 1992.

[9]   D.T. Vuza. Supplementary sets and regular complementary unending canons (part two). Perspectives of New Music, 30(1):184-207, 1992.

[10]   D.T. Vuza. Supplementary sets and regular complementary unending canons (part four). Perspectives of New Music, 31(1):270-305, 1993.

Harald Fripertinger
Institut für Mathematik
Karl Franzens Universität Graz
Heinrichstr. 36/4
A-8010 Graz, AUSTRIA
harald.fripertinger@uni-graz.at