Special Issue: Tiling Problems in Music Guest Editors’ Foreword

Following the two previous Special Issues of the Journal of Mathematics and Music, which were devoted to The Legacy of John Clough in Mathematical Music Theory (2007) and Computation (2008), we are happy to present a series of original contributions in a fascinating topic that constitutes one of the most striking examples of ‘mathemusical’ research: tiling problems in music theory and composition.

By coining the word ‘mathemusical’ in the early 1990s, we wanted to suggest that, although the history of relations between music and mathematics shows many examples of applications of mathematical models to music, there are also several examples showing that music can be sometimes a very important source of inspirational ideas for mathematicians. The aim was to balance the usual Leibnizian perspective of music as exercitium arithmeticae by proposing that also the reverse hypothesis holds according to which mathematics can be considered, in some special cases, as an exercitium musicae.

More precisely, even though it was commonly accepted that mathematical and computational methods naturally apply to music, examples of genuine musical problems that can be taken as a point of departure for purely mathematical research were, at that time, much less obvious. This attitude is wonderfully captured by the following passage of Xenakis’ art/sciences thesis defense, in which one of the jury members, Olivier Revault d'Allonnes, affirms that ‘sciences can bring infinitely more services, more illuminations, more fecundations to the arts and particularly to music than music can bring to scientific knowledge’ (see [1, p. 15]) and concludes that ‘given the relatively elementary level of mathematics [in the concepts employed] […] the interest is nil for mathematics.’

Recent years have seen the development of a more balanced perspective on the relationship between mathematics and music thanks to the progressive ‘emergence’ of several ‘mathemusical’ problems. These include examples such as the ramifications of diatonic theory (in particular the theory of maximally even sets and well-formed scales) in connection with open conjectures 2 and mathematical physics 3, or the unexpected relations between set-theoretical problems, such as the Z-relation, and the theory of homometric structures (see, for example, 4 5).

What characterizes a ‘mathemusical’ problem is the fact that settling the originally musical problem1 in an appropriate mathematical framework not only gives rise eventually to new mathematical results, but also paves the way to new musical constructions that would have been impossible to conceive without the process of ‘mathematization’. It is this double movement, from music to mathematics and backwards, which makes a ‘mathemusical’ problem so intriguing to both mathematicians and musicians.

By starting to work on ‘tiling problems in music’ about 15 years ago we had the chance to stumble upon a range of particularly intriguing mathemusical problems. By studying some of their metamorphoses, particularly by showing the unexpected underlying connections with some (still open) mathematical conjectures, we have been able, in the following years, to propose to composers a series of computational models that have been taken as a starting point for a variety of novel and stylistically very different compositional projects. We would like to take advantage from this Foreword by providing the reader with a personal account of the development of some aspects of ‘mathemusical’ research, focusing on the topic at the core of this special issue: the construction of rhythmic tiling canons. These are special musical forms which consist of a rhythmic pattern that completely tiles the musical time axis by temporal translations. When all the rhythmic voices have entered, there is one and only one voice to be heard at any given moment in time. We are aware that, by choosing this ‘canonical’ perspective on tiling problems in music, we focus on a special compositional construction which is not covering the space of all possible tiling structures in music theory, analysis and composition. For example, we disregard some important applications of tiling processes in the pitch domain, ranging from the geometric Tonnetz representation used in neo-Riemannian Theory, to tiling problems in a non-cyclic homogeneous pitch-spaces, as proposed by Jon Wild 6 or, to remain in the rhythmic domain, some very interesting compositional constructions, like Tom Johnson's ‘Perfect tilings’ and their unexpected relations with Langford and Skolem sequences, as pointed out by Jean-Paul Davalan 7.

There is probably no need here to explain in depth the relevance of canons to music. There are few musical concepts that have been used as extensively, well beyond the boundaries of the Western classical music tradition. Prominent examples range from the complex polyphonic structures of the Ars Nova to the canonic techniques in American minimalistic music, like in Steve Reich's Proverb. More present to us are probably the plentiful examples found in traditional/popular music: who did not sing at least once in his/her life the French nursery ‘Frère Jacques’, usually translated in English as ‘Brother John’? Interestingly, it has been shown by researchers in ethnomathematics and ethnomusicology that canonic constructions are also used in orally transmitted musical practices, for example in the harp Nzakara repertoire from the Central African Republic 8. Such an omnipresence may lead us to the hypothesis that canons may be considered a universal element in music.

In contrast, the history of rhythmic canons, and in particular of those which tile the time axis in a mathematical sense, and the composers’ interest in this musical form are much more recent. The French composer Olivier Messiaen (1908–1992) made one of the most significant efforts in order to study canons by making abstraction from the pitch content and by only focusing on the underlying rhythmic structure. One of the seven volumes of his Traité de rythme, de couleur et d'ornithologie (1949–1992), namely the second ‘tome’, is entirely devoted to the study of rhythmic structures (e.g. non-invertible rhythms, augmentation and diminution, irrational values, etc.), giving particular attention to their relationship with the canonic form. The composer analyses in several passages two pieces that are constructed by applying the technique of non-invertible rhythms (or ‘rythmes non-retrogradables’ in his own vocabulary) in a canonic way. More precisely, he starts from a concatenation of three palindromic intervallic structures providing the main rhythmic line of a three-voices canon that the composer initially uses in Visions de l'Amen (1943) for two pianos, and later, with a simple change of the minimal rhythmic unit, in the piece Harawi (1945) for soprano and piano. In the composer's words, ‘it follows [from this construction] that the different sonorities mix together or oppose each other in a very different way, never at the same moment neither at the same place […]. It is an organized chaos’ 9.

Although Messiaen never refers explicitly to the role of geometry and tiling processes in music, it is clear that he aims at using a special family of (concatenations of) non-invertible rhythms (namely those obtained by palindromic rhythmic structures whose intervallic distances are prime numbers) in order to canonically organize the global musical form in such a way that the onsets of the different rhythmic voices never intersect. This is not exactly what happens in the real compositions, since voices frequently intersect and the rhythmic patterns do not recover any instant of time, but the use of the tiling concept in Messiaen's compositional technique is perhaps not so far from a rigorous definition.

Clearly, there is no connection, in general, between Messiaen's use of palindromic structures and the tiling process. However, there exist non-invertible rhythms, based on prime number sequences, that may eventually be taken as the ‘basic voice’ (or ‘inner rhythm’ in our terminology) of a rhythmic canon partially realizing the tiling of the time axis. Messiaen was, of course, unaware of the existence of concepts such as ‘group factorizations’ or ‘direct sums’ which are used today to elegantly describe the construction of tiling canons. This was one of Dan Tudor Vuza's major contributions to the subject which is rooted in a long-term collaboration with composer Anatol Vieru (1926–1998) and which led to a detailed formalization of his modal theory, in particular of the concept of composition of modal structures and its interpretation in the time domain.

There would be much to say about composition laws between modes and modal structures, a concept that resonates with some other compositional and analytical constructions, such as Pierre Boulez's ‘chord multiplication’ or the concept of ‘transpositional combinations’ in American set-theoretical tradition. Transposing one pitch-class set (or, more generally, an ordered or unordered subset of a given cyclic group) according to the intervallic content of a second pitch-class set is the ‘outside-of-time’ equivalent, as Xenakis would have put it, of rhythmic canons by translation. This only works once an appropriate isomorphism between the pitch and the rhythmic domain is constructed, as Vuza does in his mathematical model of periodic rhythm 10. The tiling property follows immediately by considering the special case of the composition of two modal structures (or, equivalently, the chord multiplication or the transpositional combination of two pitch-class sets) whose cardinalities, say m and n, divide the order of the underlying cyclic group, say c in such a way that c is equal to the product of m and n.

The interested reader would certainly benefit from analysing in detail the way in which Dan Tudor Vuza arrives at the concept of tiling canons (or ‘regular complementary canons of maximal category’, in short RCMC canons) starting from a formalization of Vieru's modal theory 11. The crucial point is that he builds a mathematical model of period rhythms which makes possible what Bourbaki would call the ‘transfer of structures’ from the modal (or pitch) universe to the time domain, as he clearly explains in his critical review of David Lewin's Generalized Musical Intervals and Transformations 12.

The next significant milestone in the development of the theory of tiling canons was marked by a series of papers published by Vuza in Perspectives of New Music in 1991/1992 13 containing the four parts theory of RCMC canons. Although there are today several examples of papers containing new mathematical theorems which are published in music theory journals, Vuza's series of articles and his use of non-elementary mathematical concepts, like characters and discrete Fourier transform applied to locally compact groups, still remains one of the most significant mathematical contributions to the musicological community.

At that time, one of the authors of this foreword was working on problems of group factorization and the possible musical application of geometrical and algebraic methods, in the spirit of Guerino Mazzola's Mathematische Musiktheorie 14. In the attempt to understand Vuza's model of RCMC canons from a geometrical perspective, a profound connection with an old famous conjecture by Minkowski became evident. As originally shown in 15, the RCMC canons, which are obtained through the factorization of a cyclic group into two non-periodic subsets, were the musical metamorphoses of a tessellation problem initially raised by Minkowski in a number-theoretical form in his Geometrie der Zahlen 16 and reformulated some years later by himself in a geometrical way 17. In the geometrical version of the problem, Minkowski conjects that any simple tiling of the n-dimensional Euclidean space by unit cubes (i.e. any collection of congruent cubes that cover the space in such a way that the cubes do not have interior intersection and that the translation vectors form a lattice) has the property that some pairs of cubes (actually an infinite number of pairs) must share a complete (n−1)-dimensional face.

Recalling the history of Fermat's last theorem, which was solved more than two centuries and a half after its first formulation, this problem might be called Minkowski's last theorem. In fact, like his French colleague, Minkowski was largely underestimating the difficulties of the n-dimensional version of a problem that he had no difficulty to prove in two or three dimensions. Indeed, the problem turned out to be so difficult that its solution, provided by Hajós some 40 years later 18, has been described as ‘the most dramatic work in factoring’ 19. Hajós’ solution to Minkowski's conjecture not only clearly showed the interplay between the geometry of tiling and the algebra of group factorizations 20, but also paved the way to the classification of groups featuring the property that they cannot be factorized into a direct sum of subsets without at least one of the factors being periodic. This factorization property, obliging one of the factors to be periodic, is also called ‘Hajós property’. It distinguishes the family of the so-called Hajós (or good) groups whose exhaustive classification engaged many mathematicians, including Hajós himself, for more than 20 years. Cyclic groups, which are the relevant ones for the construction of tiling canons, can be either good or bad, i.e. non-Hajós, groups. A particularly difficult problem arises with the latter, presented by the difficulty of obtaining their factorizations into non-periodic subsets. The family of Vuza's RCMC canons corresponds precisely to this difficult case.

Unfortunately, Dan Tudor Vuza was not aware of all this research around the Minkowski/Hajós problem when he proposed the model of RCMC canons, as we realized after discussing with him in 1994 when he was Visiting Professor at the ‘Istituto per Applicazioni della Matematica’ at the CNR in Naples. Starting from a purely musical problem, Vuza was not only unexpectedly coming across a domain of group-theoretical research with profound intersections with the geometry of tessellations, but he was also providing an original contribution in the field of non-Hajós groups. To only mention one of these new results, he proved that the tiling property in rhythmic canons is invariant up to musical augmentations, which can be mathematically expressed by saying that if a non-Hajós cyclic group ℤ _n admits a factorization into two subsets A and B, it also admits the factorizations into the subsets kA and B (or equivalently A and kB) for any k coprime with the period n of the group.

Published in Perspectives of New Music, this result had almost no chance to be noticed by professional mathematicians, which explains that it was rediscovered several years later as a purely mathematical problem and proved in different ways, first by Tijdeman 21 and later by Coven and Meyerowitz 22. The first employed a combinatorial argument, whilst the latter provided a proof of this ‘fundamental Lemma’ in a polynomial ring. Note that Vuza's original proof makes use of convolutions and discrete Fourier transforms. The pertinence of these tools in music theory was pointed out in the late 1950s by David Lewin and they are now commonly applied in mathematical music theory, as the three articles of this Special Issue demonstrate. Before presenting these three contributions in more detail, we would like to add two more important elements to the tiling rhythmic construction as a ‘mathemusical’ problem: the relevance of the computational perspective and the connections with one open mathematical conjecture.

The previous Special Issue on Computation provided many examples of the use of computing methodologies in Musicology in a broad sense, including research in music theory, analysis, composition and performance. In the case of RCMC canons, the implementation of Vuza's algorithm in OpenMusic visual programming language2 raised several questions which were not explicitly addressed in the original theory: is the algorithm exhaustive for any non-Hajós cyclic group ℤ _n ? How big is the solution space? Can the same computational model be taken as a starting point for stylistically different compositional processes?

After the initial belief that Vuza's algorithm was exhaustive, we soon realized that the family of factorizations of non-Hajós cyclic groups into two non-periodic subsets, commonly called ‘Vuza canons’, is generally larger than the family of RCMC canons obtained by Vuza's historic algorithm. The catalogue for the smallest non-Hajós group, i.e. , using Vuza's algorithm, happens to be exhaustive 24. This has been verified by Harald Fripertinger by exhaustive testing of all possible factorizations. But already for the next order, i.e. n=108, Emmanuel Amiot and Harald Fripertinger found independently 252 new canons that were not constructible using Vuza's original algorithm. Again, by exhaustive testing Fripertinger showed that these are all the tiling canons that have to be added to the catalogue of RCMC canons in order to complete the list of Vuza canons for n=108. At this point we had the complete catalogue of Vuza canons corresponding to the two first non-Hajós cyclic groups. By using the invariance of the tiling process up to affine transformations, as we mentioned before, we computed the 30 non-isomorphic solutions for the subsets with 18 elements (usually representing the voices or ‘inner rhythms’ of the canon) and three non-isomorphic solutions for the subsets with six elements (called ‘outer rhythms’ and providing the entries of the voices of the canon). There are thus 90 non-isomorphic Vuza canons for the non-Hajós group . The number of solutions dramatically decreases for , with only one non-isomorphic 12-elements inner rhythm and two non-isomorphic solutions for outer rhythms with six elements. This leads to the astonishing result that there are only two different Vuza canons with period 72 (always up to affine transformations).

By giving such a detailed description of computational results concerning the exhaustiveness of Vuza's original model of tiling canons we would like to stress one of the major ingredients of contemporary mathemusical research. Building computational models of formal constructions may radically change the perspective on a given music-theoretical problem by emphasizing its experimental component. In the case of the construction of tiling canons, having a computer-aided model made evident a series of properties that would have been difficult to perceive by relying purely on the original theoretical model. For example, one can show computationally that in non-Hajós groups almost all ‘outer rhythms’ obtained by Vuza's algorithm have the property of being inversionally symmetric (palindromes). This is the case, for example, for all the solutions that we obtained for n=72 and 108. Although transpositional symmetry is forbidden in both factors, making these canonic forms very difficult to grasp for the listener, the palindromic character of one of the factors can eventually become a structural element in a compositional application of the model. This is what actually happened once we established the first catalogues of solutions and made them accessible to composers.

Surprisingly, we realized that in spite of the rigid form of rhythmic tiling canons, every composer was interpreting the catalogue of solutions in a different way, leading to a variety of stylistically very different compositional projects. Among the most interesting uses of Vuza canons we mention the orchestral piece Coïncidences (1999) by Fabien Lévy. He makes use of complex musical objects which fill the underlying rhythmic grid provided by a Vuza canon in such a way that the global perceptual result is not that of a contrapuntal listening but a continuous information flow where timber melodies spontaneously emerge by the combinatorial play of the different voices of the canon.

Some years later, a very different use of the catalogues of Vuza canons was made by Georges Bloch in several compositional projects. These range from the piece Empreinte sonore pour la Fondation Beyeler (2001), a guided music tour for an exhibition of the Beyeler Foundation in Basel, Switzerland 25, to the recent experiments in computer-aided improvisations using the OMax program developed at Ircam and combining OpenMusic formal models and Max/MSP real-time functions. Those who believe that Vuza canons only address contemporary classical music will be surprised to discover that they can be applied to jazz standards, as Georges Bloch did with Thelonius Monk's ‘Well You Needn't’, whose melodic line and harmonic content can be opportunely adapted (through constraint programming) to follow the rhythmical grid of different Vuza canons!

This short description of compositional applications of Vuza's model is an illustrative example of the importance of closely connecting theoretical research and computational modelling. Moreover, as we suggested earlier in our description of ‘mathemusical problems’, the same music-theoretical construction may intersect with a number of different mathematical problems. This is precisely what is happening in the case of Vuza's model, which, beyond the Minkowski/Hajós problem3, calls upon a still open conjecture in functional analysis: the Fuglede or spectral conjecture 27. This conjecture deals with the relation between the spectral property of a domain in the n-dimensional Euclidean space and its tiling character. It states that such a domain admits a spectrum if it tiles ℝ ⁿ by translation. But conversely to the case of the Minkowski/Hajós problems, the cases which are the most difficult to tackle and still remain unsolved correspond to the two lowest dimensions, i.e. n=1 and 2. Once again, Vuza canons are precisely the musical constructions that could help mathematicians to give an answer to this open conjecture, at least for the one-dimensional case.

More precisely, building on the fact that it is possible to reduce the tiling of the real line to the case of tiling a cyclic group without loss of generality, Emmanuel Amiot could show that if a subset R of a cyclic group ℤ _n exists which tiles the space by translation without being spectral, then R is essentially the inner rhythm of a Vuza canon. In other words, a possible counterexample of the spectral conjecture may already exist within the yet unwritten pages of the catalogues of all possible (and still unheard) Vuza canons. This Special Issue, containing articles written by leading mathematicians in the field, attempts to explore and encourage some new ideas and ventures in this direction, as we will now see by briefly introducing the content of each article.

The articles in this issue

This Special Issue begins with Emmanuel Amiot's ‘New perspectives on rhythmic canons and the spectral conjecture’. After briefly introducing some basic definitions, this article provides a state of the art of Vuza canons and their profound connections with Coven and Meyerowitz conditions (in short CM conditions), and with Fuglede's conjecture. In particular, it shows how both, the CM conditions and the spectral property, are preserved by a family of musical transformations on tiling canons, most of which came from the intuition of several composers working on Vuza canons. In the third and fourth section, the author analyses some new techniques developed by Mihail N. Kolountzakis and Máté Matolcsi and highlights their connections with some other existing algorithms that produce Vuza canons. Amiot applies Kolountzakis’ and Matolcsi's new techniques in order to provide the complete catalogue of Vuza canons of period 120. This part anticipates the content of the second paper of this issue, written by Kolountzakis and Matolcsi on ‘Algorithms for translational tiling’.

After some preliminary definitions on translational tiling and some related topics (e.g. periodicity, good and bad groups, dual groups, cyclotomic polynomials and CM conditions), Kolountzakis and Matolcsi provide a detailed description of tiling processes in terms of the theory of calculability. The main result of the following section is a theorem proving the existence of a new algorithm to decide whether a given set of integers does or does not satisfy the CM conditions. This algorithm runs in time polynomial in the diameter of the set. After providing a ‘local’ version of CM conditions, which is particularly useful in the case of tiling of a cyclic group, the authors focus on the constructions of Vuza canons by showing that the number of non-periodic factorizations of a non-Hajós group, and therefore the length of the catalogue of Vuza canons, may be quite large. In the remaining part of the paper the authors apply these new techniques in order to obtain the complete list of Vuza canons of period 144. They conclude by suggesting that the proposed algorithm may be instrumental in finding all non-periodic factorizations for larger non-Hajós groups.

In the third and last article of the issue, Franck Jedrzejewski focuses on the construction of Vuza canons by means of cyclotomic polynomials. After an introductory section, the author describes in detail his algorithm for producing a Vuza canon for any given non-Hajós cyclic group, which he calls ‘tame canon’. The algorithm, which is based on tensor products, was originally introduced in a presentaion which Franck Jedrzejewski gave some years ago at the MaMuX Seminar at Ircam4 and was later published in his book Mathematical Theory of Music 28. In the remaining part of the article, the author provides a very detailed study of the cyclotomic structures of the tame canon by showing some remarkable affinities with the cyclotomic structure of a Vuza canon whose underlying factorization was originally proposed by Jeffrey C. Lagarias and Sándor Szabó as a counterexample of Tijdeman's conjecture on the factorization of cyclic groups.

Although we initially believed that we should encourage the authors of the articles to revise their papers by making uniform all the notations and avoid the redundancy in the different presentations, we quickly realized that this would make the three presentations mutually dependent in a way which hinders, rather than helps, the reader. We hope that, especially in the case of technical subjects like the present one, the reader might profit from some repetitions and profound intersections between the three articles and feel free to start the reading of this Special Issue in any one of the three entries of this beautiful three-voices ‘canon by variations’.

Acknowledgements

We thank the Editors-in-Chief, Thomas Noll and Robert Peck, for accepting our proposal to devote a Special Issue to the fascinating topic of tiling problems in music. We are grateful to the authors for having taken the time to make their current research available for a wider audience. We are particularly grateful to Mihail N. Kolountzakis and Máté Matolcsi for submitting a paper which hopefully initiates close interaction between pure mathematicians and ‘mathemusical’ researchers. We would also like to thank Wiebke Drenckhan for critically revising this Foreword by suggesting major changes and finally convincing the authors to put an end to what might otherwise have reached untoward proportions. Last but not least, many thanks to the production editor of Taylor & Francis, Astrid Stevens, for doing everything possible in order to have this issue ready for the MCM 2009/John Clough Memorial Conference in Yale. This special issue is dedicated to Dan Tudor Vuza, with profound gratitude for providing a timeless subject around which mathematics and music naturally meet.

Notes

‘Musical problem’ should be taken in a broad sense, including Music Theory, Analysis, Composition and Performance, as rightly suggested by the subtitle of our Journal of Mathematics and Music.

See 23 for a first account of the implementation and 24 for a more detailed presentation of the computational aspects of Vuza's algorithm including the catalogues of solutions for the first periods.

For a more recent discussion on the connections between Vuza's model and the Minkowski/Hajós problem, see 26.

Most of the presentations at the tiling sessions of the MaMuX Seminar, as well as related online material, are available at http://recherche.ircam.fr/equipes/repmus/mamux/IrcamTilingResearch.html.