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

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.

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 ^Z_n 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 ^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

As the canonical representative of the orbit C_n(f) = we choose the function f₀ C_n(f) such that f₀ < g for all g C_n(f). Moreover, we choose ₀ 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₀ of the orbit C_n(f) fulfills f₀(n - 1) = 1.

A function f ^Z_n (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 ₁) 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^a_i(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₀) where A₀ 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₀ is the canonical representative of C_n(A).

In the next part we show that functions f ^Z_n with the property f(i) = 1 implies i -1 mod d (for d | n, d > 1) can be constructed from functions in ^Z_n/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 ^Z_r by replacing each component 0 in f by 0^d and each component 1 by 0^d-11, we get a vector _d(f) ^Z_rd 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( ^Z_n/d ).

Some properties of _d are collected in the next

Lemma 4. Let f, g be functions from Z_r to . Then

1. _d(f) = _d(g) if and only if f = g.
2. _d(f o _r) = _d(f) o _rd^d.
3. _d(C_r(f)) C_rd(_d(f)).
4. f < g if and only if _d(f) < _d(g).
5. f₀ is the canonical representative of C_r(f) if and only if _d(f₀) is the canonical representative of C_rd(_d(f)).
6. _d describes a bijection between the C_r-orbits on ^Z_r and the C _rd-orbits on ^Z_rd which have non-empty intersection with _d( ^Z_r), thus
   

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

9. 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-11. 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-11. 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₀) < _d(f₀ o _r^j) = _d(f₀) o _rd^dj for all j . Moreover, if n / 0 mod d, then (_d(f₀) o _rdⁿ)(rd - 1) = _d(f₀)(n - 1)1, since n - 1 / -1 mod d. According to Lemma 2, the representative _d(f₀) o _rdⁿ cannot be the canonical representative of the orbit C_rd(_d(f₀)). Hence, the canonical representative is _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 ^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 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 ^Z_r as

If we replace z_i by 1 + zⁱ, 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 ^Z_r 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₁ components 1 and r - r₁ components 0 is

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

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 (1) = 1. Moreover, it should be mentioned that f₀ is the unique Lyndon word such that _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 , (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 union

where

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 have

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(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₀ and A₀' 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^sz^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₄, 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 and five representatives f₁, ..., f₅ of the C₄-orbits of non empty subsets of Z₄:

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 ₄((1)) or ₂((0, 1)) from shorter Lyndon words, so all pairs (L_i, f_j) for i and j describe canons in Z₄. Since f₁ = ₄((1)) = ₂((0, 1)) and f₃ = ₂((1, 1)), and (1), (0, 1), and (1, 1) are necklaces of length 1 or 2 over , the pairs (L₁, C₄(f₁)) = ₄((1), C₁(1)) and (L₁, C₄(f₃)) = ₂((0, 1), C₂(1, 1)) do not belong to ₄. But the pairs (L₁, f_j) for j 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 . 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

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,

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