# Tiling problems in music composition: Theory and Implementation

Skip other details (including permanent urls, DOI, citation information)This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License. Please contact mpub-help@umich.edu to use this work in a way not covered by the license. :

For more information, read Michigan Publishing's access and usage policy.

Page 00000156 Tiling problems in music composition: Theory and Implementation. Moreno Andreatta, Carlos Agon, Emmanuel Amiot. IRCAM, Centre Georges Pompidou, France email: { andreatta, agon } @ircam.fr - chucky @wanadoo.fr Abstract This paper aims at presenting an application of algebraic methods in computer assisted composition. We show how a musical problem of construction of rhythmic canons can be formalized algebraically in two equivalent ways: factorization of cyclic groups and products of polynomials. These methods lead to the classification of some musical canons having the property of tiling the time axis (tiling rhythmic canons). They generalize a compositional model originally proposed by the French composer Olivier Messiaen. The implementation of a large family of tiling rhythmic canons in the visual programming language OpenMusic offers to the composer a wide spectrum of new compositional applications. 1 Introduction Although algebraic methods have been consciously applied to music composition since the '60, their wide possibilities in the field of computer assisted composition have been taken in consideration only recently. Nevertheless, the abstract power of all these concepts enables the composer to work in a very general conceptual space, with some natural applications in the pitch- as well in the rhythmic domain. In this paper we show how a partition problem, in the pitch domain, can be viewed rhythmically in terms of musical canons tiling the time axis. This model generalizes a compositional idea of the French composer Olivier Messiaen who proposed to consider canons just as a polyphony of rhythmic voices (independently from the melodic contour or of the harmonic content). All voices have the same rhythmic pattern, but they are translated in the time axis. We present a formalized model of such rhythmic canons, especially for those having the property of tiling the time axis (tiling rhythmic canons). In particular, we discuss some musicallyrelevant mathematical properties that enable to concentrate the study in a very special family of tiling rhythmic canons, called Regular Complementary Canons of Maximal Category (Vuza, 1991-). Since Vuza's original papers, tiling rhythmic canons have become a very interesting object of study for musicologists and composers. The implementation of this model in the visual programming language OpenMusic (Assayag et al., 1999) increases the possibilities of fruitful interactions between musicologists, computer-scientists and composers, as one may infer from a recent workshop on this topic organized at IRCAM (Amiot, 2002; Johnson, 2002). This paper aims at presenting the main results of an algebraic-oriented approach on tiling problems in music. In order to present this model, we need some preliminary definitions that are provided in Section 2. Section 3 introduces and discusses the concept of tiling rhythmic canons. In Sections 4 and 5 we present two main algebraic approaches in the formalization of tiling rhythmic canons: the groupfactorization and the polynomial approach. In Section 6 we show how to generalize the previous two models of tiling rhythmic canons by considering canons where voices are not only simple translations of a given rhythmic pattern. This remark opens the problem of classifying more general types of tiling canons, the so-called augmented canons. Some of these questions are discussed in the final section. 2 Some preliminary definitions One of the first attempts to formalize rigorously the construction process of rhythmic canons has been made by the Rumanian mathematician Dan Tudor Vuza (Vuza, 1985 and Vuza, 1991-). We present shortly some elements of his model that have been used in the OpenMusic implementation of tiling rhythmic canons. 156

Page 00000157 2.1 Definition of a periodic rhythm A periodic rhythm is a periodic locally finite subset R of the set Q of rational numbers, i.e.: 1. It exists a positive rational number t such that t+R=R (periodicity) 1. For a, b in Q with a<b, the set Rn[a,b[ is finite, where [a,b[={{x e Q: a<<x<b}. This is the socalled locally finiteness. The least positive rational number satisfying condition 1. is called the period of R whereas the greatest positive rational number dividing all differences r1-r2 with ri belonging to R is called minimal division of R. Example 1. Consider the following rhythm: 3 5 8 5 3 In Vuza's model, this rhythm can be considered a periodic rhythm corresponding to the following infinite subset R of rational numbers: R = {0, 3/16, 1/2, 1, 21/16}+(3/2)Z where aZ= {ax: x e Z}. Its period is equal to 3/2 and its minimal division is equal to 1/16. We will see in Section 3 how Messiaen has used this pattern for the construction of a rhythmic canon having some remarkable geometric properties. 2.2 Definition of a group. By definition a group is a set G of elements together with a binary operation "*" such that the four following properties are satisfied: 1. Closure: acb belongs to G for all a and b in G. 2. Associativity: (a*b)*c = a*(b*c) for all a, b, c belonging to G. 3. Identity: There exists a unique element e in G such that ace = e*a = a for all a in G. 4. Inverses: For each element a in G there exists a unique element a'in G such that aea' = a'*a = a 2.3 Cyclic groups A cyclic group of n elements (i.e. of order n) is a group (G,*) in which there exists an element g (usually more than one) such that each element of G is equal to g*g*... *g, where the group law "*" is applied a finite number of times. In other words, G is generated by g. In general a cyclic group of order n is generated by all integers d which are relatively primes with n (i.e. 1 is the only common divisor of n and d). Usually a cyclic group of order n is represented the set { 0,1,...,n-1 } of integers (modulo n) and it will be indicated as Z/nZ. Geometrically, a cyclic group can be represented by a circle. Integers 0,..., 11 are distributed uniformly, as in a clock. One may go from an integer to another simply by rotating the circle around his center by an angle equal to a multiple of 30'. Musically speaking, rotations are equivalent to transpositions and reflection through a diameter correspond to inversions. Transpositions (i.e. rotations) define equivalent relations between chords (i.e. between subsets of cyclic groups). Two chords are equivalent if the latter is the transposition of the former (or conversely). Chords which are equivalent up to transpositions and inversions are the well-known pitch-class sets (Forte, 1973). In analogy with the case of transposition classes of chords, we can consider rhythmic classes as transposition classes of rhythms, where the transposition factor is a rational number, instead of an element of Z/nZ. Moreover, a periodic rhythm can be associated with a subset of the cyclic group Z/nZ where n is depending on the numerical invariants of a rhythm that we already introduced i.e. the period and the minimal division. Figure 1 shows two circular representations of the rhythmic pattern discussed in the example 1. 24 48 Figure 1: Circular representations The natural way to build a correspondence between a rhythmic pattern and a subset of a cyclic group is obtained by taking the least n such that the rhythm is a non-periodic subset of Z/nZ. We will also say that the rhythm R is naturally associated with a subset of a cyclic group with order n equal to p/m where p is the period of R and m is its minimal division (which is equal to 24 in the case of the rhythm of Figure 1). The fact that we associate a rhythm with a nonperiodic subset of a cyclic group enables to restrict 157

Page 00000158 the study of rhythmic tiling canons to a special family of them. This condition reduce the great number of possible tiling canons of a given period, as it has been shown recently by H. Fripertinger (Fripertinger, 200 1). 3 Tiling rhythmic canons. Before discussing the formal model of a tiling rhythmic canon, we present an example that goes in the direction of this model, although without achieving it. This example is quoted from Messiaen's piece Halrawi (part no. 7, Adieu). Figure 2: A Messiaen' s three-voices canon in the piece Harawi From a rhythmic point of view, the previous example realizes a canon in three voices, each voice being the concatenation of three non-retrogradable rhythms, as it is shown in figure 3: i I II I I1 3 5 8 5 4 3 7 34 223 5 32 2 Figure 3: Rhythmic pattern of Harawi In Messiaen's words, this musical structure realizes a kind of "organized chaos" (Messiaen, 1992; p. 46), for the voices have no onset-point in common. This is only partially true, as it is clear from the following representation of the canon in a grid in which points correspond to the onset-times of the voices. There are instants of time in which no voice is playing and, conversely, there are moments in which two or more voices are playing together (Figure 4). Rhythmic pattern Onset time of voices 358534334 (024 F iiigue4 Gid~ repreentaion fHaai now eqult 2hnt.Fgr 5 show th foma Figure 5: A tree-voices cntion i Vsonsd lA meni. 3.1 Definition o t at tilingm grhythmics caenons By defsian it ion, a rhytmictlng canon ies angs rhyhmi cainon such tht ats any time ther isl onfe (and conlyoe)n voie playing. An exampl of h rhythm w ic i tlngw cqan on is given in Figure 6. hw hefra Figur 6: Example of a tiling rhythmic canon. Iht mis canon inc 4ha voce obtained byer th e time trnslatione vof te platteng R=( 8 2)in te onset-times 0, 5, 6, 11. The first rhythmic pattern is called inner rhythm, whereas the pattern of coming in of voices is 158

Page 00000159 called outer rhythm (Andreatta et al., 1999). Inner and outer rhythms replace Vuza's original ground and metric classes (Vuza, 1991), a terminology that could give rise to some confusions for what extends the characterization of rhythmic and metric properties of such global musical structures. This tiling condition implies that time axis is provided with a minimal division which holds as well for the inner and for the outer rhythm. Rhythmic canons verifying the tiling condition are also called, in Vuza's terminology, Regular Complementary canons. In fact, voices are all complementary (there is no intersection between them) and once the last voice has come in, one hears only a regular pulsation (there are no holes in the time axis). 4. Canons as group factorizations Algebraically, the problem of construction of a regular complementary canon is equivalent to the factorization of a cyclic group Z/nZ in a direct sum of two subsets. Figure 7 shows the factorization of the cyclic group Z/12Z that gives rise to the tiling canon shown in Figure 6. - -++ ++! may easily see that they have no equal period. In fact S is a periodic pattern with period equal to 6, whereas R has period equal to 12. By adding the condition that both R and S should have the same period, we obtain the so-called Regular Complementary Canons of Maximal Category (shortly Vuza-canons). Vuza proved that canons of this type only exist for periods n which can be decomposed in a product of 5 numbers p, q, x, y, z where: * p, q are distinct primes * The product px is relatively prime with the product qy * x, y and z are greater or equals to 2. Such periods n can also be characterized by the fact that they satisfy the following 5 negative conditions: 1. They are no powers of a prime number 2. They are no products of a power of a prime number by a power of a different prime number 3. They are no products of squares of two distinct primes 4. They are no products of two distinct primes by a third different prime (or by its square). 5. They are no products of four different primes. Figure 8 shows some numbers n satisfying the previous conditions. canon-n (72 108 120 144 168 180 good 200 216 240 252 264 270 periods 280 288 300 312 324 336 360 378 392 396 400 408 420 432 440 450 456 468 480 500) Figure 8: periods for Vuza-Canons. For any given n of this type, there exists a VuzaCanon with inner and outer rhythms of period n. Moreover, the decomposition of n as a product of the five numbers p, q, x, y, z with the previous conditions gives some information about the formal structure of the canon. For example, the number of voices of the canon will be always the product of x and y. The first n satisfying the previous conditions is 72=2-3-2-3-2; as a consequence 6 is the least number of voices for a regular complementary canon of maximal category. + is won 41ý 1 j Figure 7: Factorization of Z/12Z in two subsets. In the previous example the two subsets are respectively A={0,8,10} and B={0,5,6,11}. Factorizing a cyclic group in a direct sum of subsets A and B means that every element of Z/12Z can be expressed in a unique way as a sum of an element of A and an element of B. Musically, this means that at every instant of time there is one (and only one) voice playing. By looking more carefully at the structure of the inner and outer rhythms of the previous canon, we 159

Page 00000160 The implementation of Vuza's algorithm in OpenMusic enables to calculate the complete list of canons for a given n. Figure 9 shows the inner and outer rhythms with period 72. Figure 9: All solutions for n=72. Vuza-canons have some major properties: 1. Every inner rhythm can be combined with all outer rhythm. 2. For a given solution R=(al, a,...am) every circular permutation is also a solution. This corresponds to a shift in the time axis. 3. Inversions R'=(am, am1,... al) of a given solution are solutions too. This corresponds to listen to the canon from the end to the beginning. In conclusion, there are 9 classes of equivalence of Vuza-canons with period 72. Figure 10 shows an example of Vuza-Canon of period 72, with R=(1 4 1 6 13 4 7 6 6 1 4 19) and S=(8 10 8 14 18 14). 1( 4 1 6 13 4 7 6 6 1 4 19 (8 10 8 814 4) F 0: A V c' wt p r 1 -i Figure 10: A Vuza-canon with period 72. 5. Rhythmic canons as product of polynomials This model of rhythmic canons has been developed by one of the authors (Amiot, 2002) after a concept originally introduced by A. Tangian (Tangian, 2001). It makes use of the notion of 0-1 polynomials i.e. polynomials with coefficients 1 or 0. For example P(x)= 1+x+x4 and Q(x)= + x2are two 0-1 polynomials of degree 4 and 2 respectively. Rhythmic canons can be defined in terms of polynomials by means of the common notion of product of polynomials. A rhythmic canon is a 0-1 polynomial which is the product of two 0-1 polynomials. For example, the product of P(x)= 1+x+x4 and Q(x)= l+x2 defines the following 0-1 polynomial: T(x)=l+x+x2+x32+x4+x6. Musically, the polynomial T(x) gives rise to the rhythmic canon in Figure 11: (0 1 4) ( 2) z i i I i -P T(x)=1+x+x2+x3+x4+x6 Figure 11: A rhythmic canon generated by the product of two 0-1 polynomials. Note that the previous canon is not a tiling canon. The tiling condition is well-expressed in terms of product of 0-1 polynomials: a tiling rhythmic canon is a polynomial T which is product of two 0-1 polynomials and which has all coefficients equal to 1. Example 2. Consider the two 0-1 polynomials P(x)= 1+x+x4+x5 and Q(x)= 1+x2+x8+x+x16+x18 of degree 5 and 18 respectively: Their product is the polynomial T(x)= 1+x+xZ+...+x3 corresponding to the following tiling canon (Figure 12): 160

Page 00000161 P(x)=1+x+x4+x5 Q(x)-1+x2+x+x 1 O+x 16+x18 (0145) (028101618) I AD- _40 T(x)=1 +x+x2+...+x23 Figure 12: A tiling rhythmic canon generated by the product of two 0-1 polynomials This example belongs to the family of regular complementary canons that do not have maximal category, as discussed in Section 3.1. The periodicity in the outer rhythm is due to the fact that the polynomial Q(x) is, in reality, a periodic-polynomial, i.e. it is a polynomial in the variable x2 instead of being a polynomial in the variable x. Until now we simply considered tiling rhythmic canons obtained by some translations of a given inner rhythm in the time axis. In other words, we worked in a paradigm that is entirely embedded in the structure of the cyclic group Z/nZ. The next session provides some elements leading to a new family of tiling rhythmic canons: the augmented canons. 6. Toward a generalized model of tiling rhythmic canons Consider the following hexachord in the 12 tempered division of the octave: In the terminology introduced by the American music-theorist Milton Babbitt (1955), such a chord is called an inversional combinatorial structure. This means that its complement cannot be obtained by simple transposition. An inversion is necessary, as it is clear from Figure 14. -A-.. I.. k at,---- A _ ^ --- -,, ^. ^, A._ ----.----- -- Figure 14: An inversional combinatorial hexachord. The rhythmic interpretation of the previous hexachord leads to the construction of rhythmic canons in which different voices could be translation or inversions of a given rhythmic pattern (Figure 15). 2 4 I4 4|: | 4 2 | 4 4 4 Figure 15. The 'canonical' realisation of an inversional combinatorial hexachord. The property of tiling completely the time axis, without intersection nor holes between the voices enables to speak of regular complementary canons by inversion. More generally, voices may be obtained through a stretching process applied to a given rhythmic pattern. Musically, it corresponds to the well-known canonical techniques of augmentations and diminutions. Mathematically, these operations are described by affine transformations. By definition an affine transformation from Z/nZ into itself is a function f which transforms a pitch-integer x into ax+b (modulo n) where a is an integer relatively prime with n and b belongs to Z/nZ. In the special case of n=12, the multiplying factor a belongs to the set U= {1,5,7,11}. Note that an affine transformation reduce to a simple transposition by taking a= 1. On the other side, inversions are affine transformations with a= 11. Canons obtained by affine...- -....f.. " --if t. (0146810) 12 c2chrd Figure 13: A 'special' hexachord. 161

Page 00000162 transformations applied to a given rhythmic pattern are called augmented canons (Andreatta et al. 2001)'. With the OpenMusic function ag-canoniof o we can ask for a given period and a given cardinality of a rhythmic pattern (i.e. the number of attacks) all possible affine transformations that can be applied on a particular inner rhythm in order to have tiling canons. Figure 13 shows the answer for canons with period 12 and inner rhythms with cardinality 6. ((0 12346)1(1l 11))) L~~1 r (0 23457) ((1 11r)11 1))) ag-caon i fo I ((0 1 2 3 67)((1 11r ))) ((0 13 469) ((1 11r)11l5))) ((0 1 3679)1((1 10)(15))) ((01 2567 ) ((1 7r)(1 7)5))) ((235)) ((0 1 4568) ((r1 11)(1 7)))11 )) ((01 245 67) ((1 5) I )) ( 7 ((0 145)(l7(15)(1 1))) ((0 1245 8) (1(1 1))) ((01246 8)1((111)11r7))) ((0 2 3 468) ((1 1 1))) ((02468 10)1(1 11)117)11 5)111 ))) Figure 16: Rhythmic patterns and stretching factors for augmented canons. For example, the solution ((0 1 2 4 5 7) ((1 5))) means that the rhythmic pattern R=(0 1 2 4 5 7) may be stretched by factors 1 (i~e. the identity) and factor 5. To obtain the translation part b of the affine transformation ax +b we need the function all--canonsaff which takes as parameters the inner rhythm R and the stretching factors (Figure 17): I~ (01 2457) Figure 17: Affine transformations associated with the rhythmic pattern R=(0 1 2 4 5 7) The implementation of the family of augmented canons in OpenzMusic represents an open field of research in collaborations with the group MaMuTh of the University of Berlin coordinated by Thomas Noll. We get as answers the values (1 0), corresponding to the identity affine transformation and (5 1) corresponding to the affine transformation f(x)=5x+10. The function augmented-canon uses the previous information to constrnct the augmented canon. The tiling condition is realized by repeating the augmented voice a number of times equal to the stretching factor. In this case we obtain an augmented canon in 6 voices, with one original inner rhythm and 5 augmented voices (Figure 18). = *7.~~ Cocuion th uicale form ofagmn tiling ryhi canons The f virst sone uses soegroup-theoretical methods ina order toe express tiling rhythmic canons as factorizations of cyclic groups. In an equivalent way, tiling rhythmic canons may be defined in terms of product of special polynomials. In both cases, the implementation of some theoretical concepts, as we have done in OpenMusic, offers to the composer a wide family of new interesting musical strnctures. From a mathematical point of view, rhythmic canons like those discussed in this paper are but special cases of a more general family of tiling canons in which voices are obtained via affine transformations: the augmented canons. The problem of a complete classification of these musical strnctures represents an open field of research in the domain of formalization and implementation of new interesting musical strnctures. 162

Page 00000163 Acknowledgments Perspectives of New Music, nos 29(2) pp.22-49; 30(1), pp.184-207; 30(2), pp. 102-125; 31(1), pp.270-305. We would like to express our thanks to all people working in tiling rhythmic canons, especially to Thomas Noll, Andranik Tangian, Harald Fripertinger and Guerino Mazzola. A special thanks to the composers Fabien Levy, George Bloch and Tom Johnson, who materialize all this ideas as music. References Amiot, E. 2002. "On some rhythmic canons." Seminaire Mathematiques, Musique et relations avec d'autres disciplines, IRCAM (unpublished paper). Andreatta, M., C. Agon and M. Chemillier 1999. "OpenMusic et le probleme de la construction de canons musicaux rhythmiques." Actes des sixiemes Journees d'Informatique Musicale, Paris, pp. 179-185. Andreatta, M., T. Noll, C. Agon, G. Assayag, G. 2001. "The geometrical groove: rhythmic canons between theory, implementation and musical experiments." Actes des huitiemes Journees d'Informatique Musicale, Bourges, pp. 93-98. Assayag G., C. Rueda, M. Laurson, A. Agon, O. Delerue. 1999. "Computer Assisted Composition at Ircam: PatchWork & OpenMusic". Computer Music Journal 23(3). Babbitt, M. 1955. "Some Aspects of Twelve-Tone Composition", Score, 12, pp. 53-61. Chemillier, M. 1997. "Monoide libre et musique premiere partie: les musiciens ont-ils besoin des mathematiques?" Informatique theorique et Applications, 21(3), pp. 341-371. Forte, A. 1973. The Structure of Atonal Music. New Haven: Yale University Press. Fripertinger, H. 2001. "Enumeration of non-isomorphic canons", Tatra Mt. Mathematical Publications, 23. Johnson, T. 2002. "Tiling the line in Theory and Practice" Seminaire Mathematiques, Musique et relations avec d'autres disciplines, IRCAM (unpublished paper). Mazzola, G. The Topos of Music (to be published by Birkhauser Verlag, Basel, 2002). Messiaen, 0. 1992. Traite de Rythme, de Couleur et d'Ornithologie, tome 2, Alphonse Leduc, Editions Musicales, Paris. Tangian, A. 2001. "The sieve of Eratosthene for Diophantine equations in integer polynomials and Johnson's problem". Discussion paper No. 309 of the FernUniversity of Hagen. Vuza, D. T. 1985. "Sur le rythme pdriodique", Revue Roumaine de Linguistique, CLTA, XXII, 1, pp.73-103.. Vuza, D.T. 1991-. "Supplementary Sets and Regular Complementary Unending Canons"(In four parts). 163