Enumeration of non-isomorphic canons

Harald Fripertinger

Abstract

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 \mathbbQ (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 Î \mathbbQ₊ | "r Î R-R   $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 + t p for a suitable integer t, i.e. the whole canon is contained in r + pZ Ì \mathbbQ. Because everything is periodic with period d(R), we can restrict to the factor space (r + p Z) / 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 Z_n: = 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 Í Z_n 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,

K = t È i = 1  Vi,

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

1. the set V_i can be obtained from V_j by a translation of Z_n,
2. there is only the identity translation which maps V_i to V_i,
3. the set of differences in K generates Z_n, i.e. áK-Kñ: = ák-l | k,l Î Kñ = Z_n.

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.[2,3]). Since we are interested in the attack times modulo n, we assume that K is a subset of Z_n. The set of translations of Z_n is the cyclic group C_n generated by the permutation s_n: = (0,1,...,n-1) which maps i to i+1 mod n. C_n acts in a natural way both on Z_n and on the set of all subsets of Z_n:

sn(i) = i+1,    i Î Zn, and sn(A) = { sn(i) | i Î A} ,    A Í Zn.

As usual we identify a subset A of Z_n with its characteristic function c_A:Z_n® { 0,1} given by

cA(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} ^Z_n let [`f] denote the subset f<sup>-1</sup>({ 1} ) of Z<sub>n</sub>, whence f = c<sub>[`f]</sub>.

Sometimes it is convenient to write functions f from Z_n to { 0,1} as vectors of the form (f(0),f(1),...,f(n-1)) using the natural order of the elements of Z_n, because then the set of all these functions is totally ordered by the lexicographic order. For functions f,g Î { 0,1} ^Z_n 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 C_n on the set of all subsets of Z_n described as an action on the set of all characteristic function is the following

Cn×{ 0,1} Zn® { 0,1} Zn       (snj,f)®f°sn-j.

As the canonical representative of the orbit C_n(f) = { f°s_n^j | 0 £ j £ n-1} we choose the function f₀ Î C_n(f) such that f₀ £ g for all g Î C_n(f). Moreover, we choose [`f]<sub>0</sub> as the canonical representative of the orbit C<sub>n</sub>([`f]) = { s_n^j([`f]) | 0 £ j £ n-1} . In general, representatives of orbits C_n(f) of functions f under the action of the cyclic group C_n are called necklaces.

[

]Lemma 1. If f ¹ 0 denotes a function from Z_n to { 0,1} , then the canonical representative f₀ of the orbit C_n(f) fulfills f₀(n-1) = 1.

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 Z_n. This subgroup is isomorphic to Z_n/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 Z_n.) 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 Z_n. The pair (L,A) does not describe a canon in Z_n 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.

Cn×S® S       (snj,(L,A))® (L,snj(A)).

If (L,A) is a canon, then the orbit C_n(L,A) = (L,C_n(A)) describes the isomorphism class of (L,A). In general, the canonical representative of C_n(L,A) is (L,A₀) where A₀ is the canonical representative of C_n(A). From Lemma 1 we already know that c_A0(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 Z_n. The pair (L,A) does not describe a canon in Z_n if and only if there exists a divisor d > 1 of n such that L(i) = 1 implies i º d-1 mod d, and c_A0(i) = 1 implies i º d-1 mod d, where A₀ is the canonical representative of C_n(A).

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

If we apply y_d to each component of a vector f Î { 0,1} ^Z_r by replacing each component 0 in f by 0^d and each component 1 by 0^d-11, we get a vector y_d(f) Î { 0,1} ^Z_rd and

yd({ 0,1} Zr) = { f Î { 0,1} Zrd | 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 c_A0 are elements of y_d({ 0,1} ^Z_n/d). Some properties of y_d are collected in the next

[

]Lemma 4. Let f,g be functions from Z_r to { 0,1} . Then

1. y_d(f) = y_d(g) if and only if f = g.
2. y_d(f°s_r) = y_d(f)°s_rd^d.
3. y_d(C_r(f)) Ì C_rd(y_d(f)).
4. f < g if and only if y_d(f) < y_d(g).
5. f₀ is the canonical representative of C_r(f) if and only if y_d(f₀) is the canonical representative of C_rd(y_d(f)).
6. y_d describes a bijection between the C_r-orbits on { 0,1} ^Z_r and the C_rd-orbits on { 0,1} ^Z_rd which have non-empty intersection with y_d({ 0,1} ^Z_r), thus

   
   

   | { Crd(A) | A Í Zrd, A ¹ Æ, d | k-l "k,l Î A} | =

   
   

   | { Cr(A) | A Í Zr, A ¹ Æ} | = :a(r).

7. f ¹ 0 is acyclic if and only if y_d(f) is acyclic.
8. y_d describes a bijection between the acyclic C_r-orbits on { 0,1} ^Z_r and the acyclic C_rd-orbits on { 0,1} ^Z_rd which have non-empty intersection with y_d({ 0,1} ^Z_r), thus

   
   

   | { Crd(A) | A Í Zrd, A ¹ Æ, d | k-l "k,l Î A, A acyclic} | =

   
   

   | { Cr(A) | A Í Zr, A ¹ Æ, A acyclic} | = :l(r).

9. Both f and y_d(f) have the same number of components which are 1.

In order to show that the second item is true, assume that y_d(f°s_r)(j) = 1 for some j Î Z_rd. According to the definition of y_d, this is equivalent to j = sd-1 and (f°s_r)(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 y_d(f)((s+1)d-1) = 1. This, however, is the same as y_d(f)(j+d) = 1, whence (y_d(f)°s_rd^d)(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 Î Z_r 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, y_d(f(i)) = 0^d and y_d(g(i)) = 0^d-11. Hence, y_d(f)(j) = y_d(g)(j) for j < id-1 and y_d(f)(id-1) = 0 < 1 = y_d(g)(id-1), and consequently y_d(f) < y_d(g). If, conversely, y_d(f) < y_d(g), then there exists an i Î Z_rd such that y_d(f)(j) = y_d(g)(j) for all j < i and y_d(f)(i) < y_d(g)(i), whence y_d(g)(i) = 1 and i º -1 mod d. Assume that i is of the form sd-1. Then y_d(f(j)) = y_d(g(j)) for j < s, and y_d(f(s)) = 0^d whereas y_d(g(s)) = 0^d-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 y_d(f₀) < y_d(f₀°s_r^j) = y_d(f₀)°s_rd^dj for all j Î { 1,...,r-1} . Moreover, if n\not º 0 mod d, then (y_d(f₀)°s_rdⁿ)(rd-1) = y_d(f₀)(n-1) ¹ 1, since n-1\not º -1 mod d. According to Lemma 2, the representative y_d(f₀)°s_rdⁿ cannot be the canonical representative of the orbit C_rd(y_d(f₀)). Hence, the canonical representative is y_d(f₀).

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 C_r-orbits on { 0,1} ^Z_r we apply Pólya's theory cf. [2,3,5,6]. In the present situation we have to compute the cycle index of the group C_r acting on Z_r which is a polynomial in z₁,...,z_r over \mathbbQ given by

C(Cr,Zr) = 1 r å s | r  j(s) zsr/s,

where j is the Euler totient function. Replacing each indeterminate z_i in C(C_r,Z_r) by | { 0,1} |, which is equal to 2, we compute the number of all C_r-orbits on { 0,1} ^Z_r as

C(Cr,Zr,zi: = 2) = 1 r å s | r  j(s)2r/s.

If we replace z_i by 1+zⁱ, where z is an indeterminate over \mathbbQ, then the number of C_r-orbits of k-sets A Í Z_r is the coefficient of z^k in

C(Cr,Zr,zi: = 1+zi) = 1 r å s | r  j(s)(1+zi)r/s.

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 C_r-orbits on { 0,1} ^Z_r 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 l(r) see 8. in Lemma 4)

l(r) = 1 r å s | r  m(s)2r/s,

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

1 r å s | gcd(r-r1,r1)  m(s) æ ç è r/s r1/s ö ÷ ø .

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

1 r r-1 å r1 = 1  æ ç è å s | gcd(r-r1,r1)  m(s) æ ç è r/s r1/s ö ÷ ø ö ÷ ø yr1.

In the case r = 1 there are two Lyndon words, namely f₀ = (0) and f₁ = (1). The first one is the characteristic function of the empty set in Z₁ so we don't want to count it. For that reason, we must set l(1) = 1. Moreover, it should be mentioned that f₀ is the unique Lyndon word such that y_d(f₀) 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 M_n,d be the set of all pairs (L,C_n(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 Z_n, such that d | k-l for all k,l Î A. Hence

Mn,d = ì í î (L,Cn(A)) | L Lyndon word, L ¹ 0, L(i) = 1Þ i º -1 mod d A Í Zn, A ¹ Æ, d | k-l "k,l Î A ü ý þ .

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

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

which is the number of possibilities to choose L and C_n(A) according to the desired properties of M_n,d. Finally, let k_n be the set of isomorphism classes of canons in Z_n,

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

From Lemma 3 we deduce that

kn = Mn,1\ È [d > 1 || d | n]  Mn,d.

[

]Theorem. The number of isomorphism classes of canons in Z_n is

| kn| = å d | n  m(d)l(n/d)a(n/d).

Mn,1 = \ldotp È   d | n  yd(kn/d),

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(cA)   )).

It is clear that M_n,1 contains this union. Moreover, this union is disjoint, since for a canon K = (L,C_n/d(A)) Î k_n/d we have

áK-Kñ = Zn/d @ áyd(K)-yd(K)ñ.

Finally, we have to show that each element of M_n,1 belongs to this union. If (L,C_n(A)) Î M_n,1, then choose the biggest d such that (L,C_n(A)) belongs to M_n,d. (I.e. (L,C_n(A)) does not belong to M_n,dd¢ for d¢ > 1. It is always possible to find such d, since, if (L,C_n(A)) belongs both to M_n,d1 and M_n,d2, then it also belongs to M_{n, lcm
\nolimits (d1,d2)}.) Then there exists (L¢,C_n/d(A¢)) Î M_n/d,1 such that L = y_d(L¢) and c_A0 = y_d(c_A0¢) for the canonical representatives A₀ and A₀¢ of C_n(A) and C_n/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,C_n(A)) also belongs to M_n,dd¢, which is a contradiction to the choice of d.

Hence,

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

and by Moebius inversion we get

| kn| = å d | n  m(n/d)| Md,1| = å d | n  m(d)| Mn/d,1| = å d | n  m(d)| Mn,d| = å d | n  m(d)l(n/d)a(n/d),

which finishes the proof.       ^[¯]

If l and a are replaced by the corresponding generating functions

l   (r) = ì ï ï í ï ï î 1 r r-1 å r1 = 1  æ ç è å s | gcd(r-r1,r1)  m(s) æ ç è r/s r1/s ö ÷ ø ö ÷ ø yr1 if r > 1 y if r = 1

and

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

then the coefficient of y^sz^t in

å d | n  m(d) l   (n/d) a   (n/d)

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

For example the numbers of isomorphism classes of canons in Z_n for 1 £ n £ 10 are:

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

Finally, we have a closer look at the 13 isomorphism classes of canons in Z₄, which can be classified according to their number of voices and attack times per voice by z⁴y³ + z⁴y² + z⁴y + z³y³ + z³y² + z³y + 2z²y³ + 2z²y² + z²y + zy³ + zy². 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 L₁, L₂, L₃ of length 4 over { 0,1} and five representatives f₁,...,f₅ of the C₄-orbits of non empty subsets of Z₄:

L1 = (0,0,0,1) f1 = (0,0,0,1) L2 = (0,0,1,1) f2 = (0,0,1,1) 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 Z₄, which is the outer rhythm. Only L₁ can be constructed as y₄((1)) or y₂((0,1)) from shorter Lyndon words, so all pairs (L_i,f_j) for i Î { 2,3} and j Î { 1,...,5} describe canons in Z₄. Since f₁ = y₄((1)) = y₂((0,1)) and f₃ = y₂((1,1)), and (1), (0,1), and (1,1) are necklaces of length 1 or 2 over { 0,1} , the pairs (L₁,C₄(f₁)) = y₄((1),C₁(1)) and (L₁,C₄(f₃)) = y₂((0,1),C₂(1,1)) do not belong to k₄. But the pairs (L₁,f_j) for j Î { 2,4,5} describe again canons in Z₄.

From this example we also see how to compute complete lists of isomorphism classes of canons in Z_n for arbitrary n. There exist fast algorithms for computing all Lyndon words and all necklaces of length n over { 0,1} . Then each pair (L_i,f_j) must be tested whether there exists some d > 1 such that (L_i,f_j) = (y_d(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 Z_n if and only if

1. the voices V_a cover entirely the cyclic group Z_n,
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,

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

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.