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

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 (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 , 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 + p . Because everything is periodic with period d(R), we can restrict to the factor space (r + p)/d(R) which may be identified with /n, the residue class ring of modulo n.

From now on, we consider the whole canon within Z_{n} := /n 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,

such that for all i, j

- the set V
_{i}can be obtained from V_{j}by a translation of Z_{n}, - there is only the identity translation which maps V
_{i}to V_{i}, - the set of differences in K generates Z
_{n}, i.e. <K - K> := <k - l | k, l K> = Z_{n}.

We prefer to write a canon K as a set of its subsets V _{i}. Two canons K = and
L = are called isomorphic if s = t and if there exists a translation T of Z_{n} and
a permutation in the symmetric group S_{t} such that T (V _{i}) = W _{(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.[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 _{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}:

As usual we identify a subset A of Z_{n} with its characteristic function _{A} : Z_{n} given
by

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

Sometimes it is convenient to write functions f from Z_{n} to 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 ^{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 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

As the canonical representative of the orbit C_{n}(f) = we choose the
function f_{0} C_{n}(f) such that f_{0} __<__ g for all g C_{n}(f). Moreover, we choose _{0} as the
canonical representative of the orbit C_{n}( ) = . 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 f0 denotes a function from Z
_{n}to , then the canonical representative f_{0}of the orbit C_{n}(f) fulfills f_{0}(n - 1) = 1.

A function f ^{Zn} (or the corresponding vector and the set ) 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 C_{n}(f) are acyclic
as well, and we call C_{n}(f) an acyclic orbit.

From the first two properties of a canon we derive that all voices V _{i} belong to the same
orbit C_{n}(V _{1}) and that each voice is acyclic. For that reason, we can describe a canon
K = as a pair (L, A) where L is the Lyndon word, which is the canonical
representative of the orbit C_{n}(_{V 1}), and A = is a t-subset of Z_{n} such that
V _{i} = _{n}^{ai}(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 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 L0 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 , 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 Z_{n}. The
group of translations of Z_{n} acts on S according to

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_{0}) where A_{0} is the
canonical representative of C_{n}(A). From Lemma 1 we already know that _{A0}(n - 1) = 1 and
L(n - 1) = 1 if L0. This together with Lemma 2 proves

- Lemma 3. Let L0 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_{A0}(i) = 1 implies i d - 1 mod d, where A_{0}is the canonical representative of C_{n}(A).

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

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

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 _{A0} are elements of _{d}( ^{Zn/d
}).

Some properties of _{d} are collected in the next

- Lemma 4. Let f, g be functions from Z
_{r}to . Then_{d}(f) =_{d}(g) if and only if f = g._{d}(f o_{r}) =_{d}(f) o_{rd}^{d}._{d}(C_{r}(f)) C_{rd}(_{d}(f)).- f < g if and only if
_{d}(f) <_{d}(g). - f
_{0}is the canonical representative of C_{r}(f) if and only if_{d}(f_{0}) is the canonical representative of C_{rd}(_{d}(f)). _{d}describes a bijection between the C_{r}-orbits on^{Zr}and the C_{ rd}-orbits on^{Zrd}which have non-empty intersection with_{ d}(^{Zr}), thus- f0 is acyclic if and only if
_{d}(f) is acyclic. _{d}describes a bijection between the acyclic C_{r}-orbits on^{Zr}and the acyclic C_{rd}-orbits on^{Zrd}which have non-empty intersection with_{ d}(^{Zr}), thus- Both f and
_{d}(f) have the same number of components which are 1.

- Proof. Since
_{d}is an injective mapping from each component of f into the set , the first statement is clear.In order to show that the second item is true, assume that

_{d}(f o_{r})(j) = 1 for some j Z_{rd}. According to the definition of_{d}, this is equivalent to j = sd - 1 and (f o_{r})(s - 1) = 1 for some s . In other words, j = sd - 1 and f(s) = 1, which is equivalent to j = sd - 1 and_{d}(f)((s + 1)d - 1) = 1. This, however, is the same as_{d}(f)(j + d) = 1, whence (_{d}(f) o_{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,_{d}(f(i)) = 0^{d}and_{ d}(g(i)) = 0^{d-1}1. Hence,_{d}(f)(j) =_{d}(g)(j) for j < id-1 and_{d}(f)(id-1) = 0 < 1 =_{d}(g)(id-1), and consequently_{d}(f) <_{d}(g). If, conversely,_{d}(f) <_{d}(g), then there exists an i Z_{rd}such that_{d}(f)(j) =_{d}(g)(j) for all j < i and_{d}(f)(i) <_{d}(g)(i), whence_{d}(g)(i) = 1 and i -1 mod d. Assume that i is of the form sd - 1. Then_{d}(f(j)) =_{d}(g(j)) for j < s, and_{d}(f(s)) = 0^{d}whereas_{ d}(g(s)) = 0^{d-1}1. Since_{ 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

_{d}(f_{0}) <_{d}(f_{0}o_{r}^{j}) =_{d}(f_{0}) o_{rd}^{dj}for all j . Moreover, if n / 0 mod d, then (_{d}(f_{0}) o_{rd}^{n})(rd - 1) =_{d}(f_{0})(n - 1)1, since n - 1 / -1 mod d. According to Lemma 2, the representative_{d}(f_{0}) o_{rd}^{n}cannot be the canonical representative of the orbit C_{rd}(_{d}(f_{0})). Hence, the canonical representative is_{d}(f_{0}).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 ^{Zr} 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_{1}, ..., z_{r} over given by

where is the Euler totient function. Replacing each indeterminate z_{i} in C(C_{r}, Z_{r}) by
, which is equal to 2, we compute the number of all C_{r}-orbits on ^{Zr}
as

If we replace z_{i} by 1 + z^{i}, where z is an indeterminate over , then the number of C_{
r}-orbits
of k-sets A Z_{r} is the coefficient of z^{k} in

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

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 ^{Zr} or, what is equivalent to this, to enumerate all
Lyndon words of length r over the alphabet . For r > 1, this number is given as (for the
definition of (r) see 8. in Lemma 4)

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

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

In the case r = 1 there are two Lyndon words, namely f_{0} = (0) and f_{1} = (1). The first one is
the characteristic function of the empty set in Z_{1} so we don’t want to count it. For that
reason, we must set (1) = 1. Moreover, it should be mentioned that f_{0} is the unique Lyndon
word such that _{d}(f_{0}) 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 , (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

From Lemma 4 we deduce that _{d} describes a bijection between M_{n,d} and M_{n/d,1},
thus

which is the number of possibilities to choose L and C_{n}(A) according to the desired
properties of M_{n,d}. Finally, let _{n} be the set of isomorphism classes of canons in
Z_{n},

From Lemma 3 we deduce that

- Theorem. The number of isomorphism classes of canons in Z
_{n}is

- Proof. First we prove that the set M
_{n,1}is the disjoint unionwhere

and

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))_{n/d}we haveFinally, 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(d1,d2)}.) Then there exists (L', C_{ n/d}(A')) M_{ n/d,1}such that L =_{d}(L') and_{A0}=_{d}(_{A0' }) for the canonical representatives A_{0}and A_{0}' of C_{ n}(A) and C_{n/d}(A'). Moreover, (L', C_{ n/d}(A'))_{ 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,

and by Moebius inversion we get

which finishes the proof.

If and are replaced by the corresponding generating functions

and

then the coefficient of y^{s}z^{t} in

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:

Finally, we have a closer look at the 13 isomorphism classes of canons in Z_{4}, which
can be classified according to their number of voices and attack times per voice by
z^{4}y^{3} + z^{4}y^{2} + z^{4}y + z^{3}y^{3} + z^{3}y^{2} + z^{3}y + 2z^{2}y^{3} + 2z^{2}y^{2} + z^{2}y + zy^{3} + zy^{2}. 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_{1}, L_{2}, L_{3} of length 4 over and five
representatives f_{1}, ..., f_{5} of the C_{4}-orbits of non empty subsets of Z_{4}:

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_{4}, which is the outer rhythm. Only L_{1} can be
constructed as _{4}((1)) or _{2}((0, 1)) from shorter Lyndon words, so all pairs (L_{i}, f_{j}) for
i and j describe canons in Z_{4}. Since f_{1} = _{4}((1)) = _{2}((0, 1)) and
f_{3} = _{2}((1, 1)), and (1), (0, 1), and (1, 1) are necklaces of length 1 or 2 over ,
the pairs (L_{1}, C_{4}(f_{1})) = _{4}((1), C_{1}(1)) and (L_{1}, C_{4}(f_{3})) = _{2}((0, 1), C_{2}(1, 1)) do
not belong to _{4}. But the pairs (L_{1}, f_{j}) for j describe again canons in
Z_{4}.

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 . Then each pair (L_{i}, f_{j}) must be tested whether there
exists some d > 1 such that (L_{i}, f_{j}) = (_{d}(L'), _{
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

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

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]).

[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 |