The Music and Mathematics of Maximal Evenness in Graphs
Year: 2024 Authors: Neal Bushaw; Brent Cody; Luke Freeman; Tobias Whitaker
Core claim
A physics-inspired energy measure generalizes maximal evenness to finite simple connected graphs while matching the classical cycle case.
Topics
maximal evenness, graph theory, music theory, majorization, electric potential energy
Domains
graph theory, majorization, discrete mathematics, mathematical physics, music theory, rhythm, ethnomusicology
Methods
J-representations, distance sums, potential energy model, graph generalization
Media
graphs, musical rhythms, pitch-class sets
Paper text
The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.
Bridges 2024 Conference Proceedings
The Music and Mathematics of Maximal Evenness in Graphs
Neal Bushaw, Brent Cody, Luke Freeman , and Tobias Whitaker
Virginia Commonwealth University, Richmond, Virginia, USA; nobushaw@vcu.edu Virginia Commonwealth University, Richmond, Virginia, USA; bmcdy@vcu.edu Virginia Commonwealth University, Richmond, Virginia, USA; freemanln@vcu.edu University of Richmond, Richmond, Virginia, USA; twhitak2@richmond.edu
Abstract
We use the concept of electric potential energy from physics, the mathematical field of graph theory, and the notion of majorization to study maximal evenness in a broader mathematical context than what was previously possible, so that we can go beyond the well-known one-dimensional maximally even sets into higher dimensional and more geometrically complex territory. We investigate musical connections between certain generalizations of maximally even sets, one of the oldest Puerto Rican musical traditions of African origin called bomba, and with certain scales ranging from the familiar to the esoteric.
Introduction
Maximally even sets, which arose as part of Clough and Douthett’s study [5] of musical scales, and which have gained in popularity more recently due to the rhythmic connections discovered by Toussaint [21], manifest in musical traditions across cultures in the form of interesting scales and rhythms. In a remarkable turn of events, Clough and Douthett’s research in music theory has found applications in mathematics [10, 20], computer science [13], mathematical physics [8], and even in the design of particle accelerators [2]. Up until now, maximally even sets have always been assumed to exist within a “cyclic” context. For example, scales are often viewed as a particular subsets of the twelve standard pitch classes arranged around a circle, and repeating rhythms are often visualized as a collection of beats and rests arranged in a circular pattern. It is natural to view the cyclic contexts of pitch classes and rhythms as being graphs (i.e. collections of vertices and edges): the twelve pitch classes corresponds to the vertices of the 12-cycle (Figure 1a) and a rhythm of length twelve can be viewed as a particular subset of . In this article we address the following two questions. First, to what extent can the definitions and techniques used to study maximal evenness in the cyclic context be generalized to other graphs, such as squares of cycles (Figure 1b), Möbius ladders (two representations of which are given in Figure 1c), or hypercubes (Figure 1d)? Second, are there musical connections to be found by considering maximal evenness in graphs other than cycles?
(a)
(b)
(c)
Figure 1: Various finite graphs: (a) a 12-cycle , (b) a 12-cycle squared , (c) two isomorphic representations of the Möbius ladder , and (e) a hypercube.
(d)
Maximal Evenness
Suppose we want to write a repeating rhythm for a single drum which contains five onsets (i.e. hits on the drum) and seven rests, for a total of twelve beats in our measure, where each onset is denoted by “” and each rest by “.” Further suppose that we want the onsets to be spaced out “as evenly as possible” within the twelve available beats. As a first attempt, we might begin by calculating , and since is closer to than to , we might try placing an onset on every two beats like this: . But one quickly realizes that the onsets can be “more evenly spaced” by writing , which is indeed a “maximally even” configuration of onsets. Since this is a repeating rhythm, it can be visualized as a particular set of vertices in the graph (see Figure 2), and is called a maximally even set or a Euclidean rhythm [6, 21].
There are many equivalent algorithms that generate maximally even sets [5, 6, 10], but perhaps one of the most straightforward, which we take as our definition, is that involving -representations, which is due to Clough and Douthett [5]. Before stating the definition, let us consider an example of a -representation of the maximally even set in , which one can think of as being a formula for . Clough and Douthett defined the notation , and with a little simplification we see that . Let us note that one can view the definition of as being a “fix” of the inadequate first attempt made above in which we computed and placed onsets every two beats.
Definition 1.
A set of vertices in with cardinality is maximally even if it is of the form for some integer with .
Let us note that the in Definition 1 can be thought of as a rotation parameter, and reflects the fact that any rotation of a maximally even set is still maximally even. For example, (which is a rotation of ). Using Definition 1, one can easily compute many instances of maximally even sets.
The Energy of a Set of Vertices
A graph is a collection of vertices together with a collection of edges connecting the vertices. An edge connecting vertex to vertex is viewed as a pair . For our purposes, we will assume all graphs are finite and simple (i.e. there will never be more than one edge between any two vertices and no edge starts and ends at the same vertex). Given two vertices with , a path from to is any finite sequence of edges such that there is a sequence of distinct vertices with , , and for . The length of a path from to is the number of edges in the path. For two vertices and , the distance from to is the length of a shortest path from to . We say that is connected if for all vertices and in with , there is a path from to .
Let us return to one of our motivating questions: given a finite simple connected graph , can we define some useful notion of “maximally even” set of vertices in ? One would hope that some characterization of maximal evenness in cycles might generalize to other graphs. However, upon a careful examination of the known characterizations of maximal evenness [5, 6, 10], one quickly realizes that all of these characterizations seem to rely on features of cycle graphs that do not hold in a broader context. Let us note that one measure of evenness, namely the sum of pairwise distances (see Definition 2), does easily generalize to finite simple connected graphs, but as is well known, this measure cannot be used to characterize maximal evenness (maximizers of the sum of distances need not be maximally even, as we will see below).
To address this, using a simple idea from basic physics, we develop a new way to measure evenness which applies in any finite simple connected graph, and which is equivalent to maximal evenness in cycles.
Recall that charged particles, whose charges are of the same sign, repel one another. The electric potential energy of a system of two charged particles, each of charge , i.e. massless unit point charges, is equal to
The Music and Mathematics of Maximal Evenness in Graphs
where is the distance between the two particles; so when these particles are close to each other the potential energy will be large, and when they are far apart the potential energy will be small. The potential energy of a system of more than two charged particles, each of charge 1, can be calculated by taking the sum of the reciprocals of the distances between each pair of particles in the system. So, if we place five protons on a circle in such a way that their motion is constrained to the circle, the protons will move away from each other until they reach an equilibrium configuration, as in Figure 2. One way to understand this process is by using potential energy. This system of five particles on the circle starts out with some relatively large potential energy, the system evolves over time and eventually reaches a configuration of minimal potential energy.
Our new measure of evenness can be thought of as the electrostatic potential energy of a system of unit point charges constrained to the vertices of a finite simple connected graph, using the notion of distance that comes with the graph.
Definition 2. Suppose is a finite simple connected graph and is a set of vertices in with . The distance vector of is the tuple of all distances between pairs of elements of with , where . Then the energy of is . We say that is a minimizer of (or has minimal energy) if is less than or equal to the energy of all sets of vertices in of the same cardinality as . The sum of distances of is . We say that is a maximizer of (or has maximal sum of distances) if is greater than or equal to the sum of distances of all sets of vertices in of the same cardinality as .
Figure 2: Evolution of systems of unit charges on a circle and on a 12-cycle.
Example 1 (Cycles and other graphs). Let us calculate the sum of distances and energy of a particular subset of . The maximally even set (see Figure 2) has distance vector . This means that and . Indeed, is a minimizer of and a maximizer of . Let us point out that every minimizer of of size 5 on is a rotation of , while there are maximizers of of size 5 on that are not rotations of .
Similar calculations can be carried out in any finite simple connected graph using any standard mathematical software. For example, using the open source mathematical programming language SageMath, we can compute distance vectors and energies of all sets of vertices of size 7 in a hypercube, and then select a minimizer as in Figure 3d. Let us note that this technique indeed produces sets of vertices which are “spaced out as evenly as possible.”
Example 2 (Musical connections involving ). The graph (see Figure 1b) can be obtained from the 12-cycle by adding an edge between any pair of vertices of which are at distance 2 from each other in . Thus, although and have the same vertices, distance calculations made in will differ from those made in because of the extra edges. This means that the two graphs and will have different minimizers of ; in some sense, the extra edges in lead to minimal energy sets which are “smeared” versions of maximally even subsets of . There are exactly three minimizers of with size 7 on (up to reflections and rotations), all of which are shown in Figure 3a-3c, and indeed, none of these sets are
Bushaw et al.
maximally even. Hence by Theorem 1, none of these sets are minimizers of on . However, these sets do have musical significance. In all of the following examples, we will view sets of vertices as scales which begin at vertex 0 and proceed in a clockwise direction unless otherwise noted. The set in Figure 3a, corresponds to the harmonic minor scale [C, D, Eb, F, G, Ab, B, C] whose sequence of steps is [W, H, W, W, H, WH, H], where W means whole step, H means half step and WH means three half steps; whereas the same set read starting on vertex 7 and going counter clockwise corresponds to the harmonic major scale. The set in Figure 3b corresponds to the Chitrambari scale of Carnatic music, which has sequence of steps [W, H, W, H, W, WH, H]. The set in Figure 3c corresponds to the double harmonic scale in western classical music, in which the sequence of steps is [H, WH, H, W, H, WH, H]. This same scale also corresponds to indian ragas, namely the Mayamalavagowla Raga of Carnatic music and the Bhairav Raga of Hindustani classical music.
(a)
(b)
(c)
Figure 3: The minimizers of of size 7 on and the corresponding musical scales are depicted in (a)-(c), and the minimizer of of size 7 on the hypercube appears in (d).
(d)
Example 3 (Musical connections involving Möbius ladder graphs: Möbius Rhythms). The Möbius ladder graph on vertices can be obtained from the standard ladder graph on vertices by adding two edges joining the two ends of the ladder with a twist (see the first graph in Figure 1c). The same graph can be obtained from a cycle graph by adding an edge between any pair of vertices and with equal to (see in Figure 1c). Thus, vertices which are on opposite sides of the cycle at distance from each other will be distance 1 from each other in . This means that minimizers of on will tend to not contain pairs of vertices which are opposite each other whenever possible. Let us describe an interesting connection between Möbius ladder graphs and one of the oldest Puerto Rican musical traditions of African origin called bomba. Two of the most popular rhythmic variations of this tradition are bomba yubá and bomba sicá, which are typically played on the barril de bomba (see Figure 4d). The set depicted in Figure 4a is the unique (up to reflections and rotations) minimizer of of size 4 on and, when read starting on vertex 0 and proceeding clockwise, corresponds to the bomba yuba, a 6/8-based beat which pairs well with many rhythms from Cuba and Africa [16]. The set shown in Figure 4b is the unique (up to reflections and rotations) minimizer of of size 4 on and corresponds to the bomba sicá [16]. The set in Figure 4c, is one of two (up to reflections and rotations) minimizers of of size 6 on and corresponds to a timbal bell (cencerro) pattern often played in bomba [17].
Minimal Energy, Maximal Evenness, and Majorization
The examples discussed above suggest that the notion of minimal energy is a good candidate for a possible generalization of maximal evenness from -cycles to arbitrary finite simple connected graphs. In this section
The Music and Mathematics of Maximal Evenness in Graphs
(a)
(b)
(c)
Figure 4: Some minimizers of on Möbius ladders and a barril de bomba.
(d) [22]
we present more evidence along these lines in the form of several general theorems, proofs of which are essentially combinatorial and will appear in a forthcoming article. Along the way we introduce another previously unknown technique for measuring the evenness of a set of vertices of a graph: majorization. The first theorem we would like to present (which is similar to but distinct from [9, Theorem 7]) says that when we restrict our attention to -cycles, minimal energy is equivalent to maximal evenness. Thus, our notion of minimal energy set of vertices in a graph is a direct generalization of Clough and Douthett’s maximal evenness.
Theorem 1. For any positive integer , a set of vertices of an -cycle has minimal energy if and only if it is maximally even.
It is well known that the complement of a maximally even set is maximally even (see [5, Theorem 3.3], [6, Corollary 1], or [11, Theorem 3.1]). Since we are claiming that the notion of minimal energy set provides a good generalization of the notion of maximal evenness, it is desirable that the complement of a minimal energy set also has minimal energy. However, this is not true in general. For example, the subset of the path graph on four vertices consisting of the two endpoints has minimal energy , whereas its complement has energy , which is clearly not minimal. This being said, there is a wide class of graphs, namely the distance degree regular graphs introduced by Bloom et al. [3], in which complements of minimal energy sets always have minimal energy. Given a vertex in , the distance vector of is the vector of length of all distances from to other vertices in the graph, where . A graph is distance degree regular if whenever we have . Notice that squares of cycles, Möbius ladders, and the hypercube are all distance degree regular graphs, so by the following theorem the complements of the sets in Figure 3, and Figure 4 are also minimizers of .
Theorem 2. Suppose is a finite connected simple graph which is distance degree regular. Then a set of vertices of has minimal energy if and only if its complement has minimal energy.
One of the main tools used in the proof of Theorem 1 is the idea of majorization (see Definition 3), which provides us with another way to measure the evenness of a set of vertices in finite connected graphs. Since its origin over one-hundred years ago in Muirhead’s 1902 study of mathematical inequalities [18] and in Lorenz’s 1905 study of wealth inequality [14], majorization has played an important role in many areas of research [15], such as linear algebra [1], operator theory [7], and brownian motion [4]. Let us consider an example. Suppose we need to distribute twenty apples among four people. We’d like to have a way of comparing the equity of such distributions. For example, one such distribution can be denoted by and another by , where the th coordinate of each tuple is the number of apples received by person . Which distribution is more equitable? The idea is that is more equitable than because can be obtained from via a Robinhood transfer, meaning that we can start with and transfer one apple from
Bushaw et al.
some person to some other person who has fewer apples, thus obtaining . The tuple is majorized by (i.e. is more equitable than) . Of course, the most equitable distribution in this example would be , which can be obtained by performing a finite sequence of Robinhood transfers on any vector of nonnegative integers whose entries sum to twenty.
The general definition of majorization, which we discuss now, provides an efficient way to compare the “equity” of -tuples when viewed as wealth distributions. Given an -tuple we let denote the -tuple which has the same entries as but .
Definition 3. Suppose and are -tuples of real numbers. We say that is majorized by and write x < y if and only if (1) for we have and (2) .
But what does majorization have to do with the energy of a set of vertices? How is majorization used to prove Theorem 1? The following theorem, due to the great Issai Schur [19] and independently to the eminent team of mathematicians consisting of Hardy, Littlewood, and Pólya [12], provides a connection between majorization and the energy of subsets of graphs, and in particular cycles.
Theorem 3 (Schur [19]; Hardy, Littlewood, and Polya [12]). Suppose is an interval, and is defined by . Then x < y implies . Moreover, if x < y and is not a permutation of then it follows that \phi(x) < \phi(y) .
The intuition provided by Theorem 3 is that if and are sets of vertices in a finite connected graph , and if (as in Definition 2) is majorized by , then is more equitable than , and that the vertices in are spaced out “more evenly” than those in . This intuition is further justified by the following.
Theorem 4. Suppose is an integer and . Let be the collection of all sets of vertices of of cardinality which maximize the sum of distances . Then a set of vertices of size is maximally even if and only if \vec{D}(A) < \vec{D}(B) for all .
The sum of distances, the notion of energy, and also majorization all provide different ways to measure the evenness of a set of vertices. Rather than declaring one measure of evenness preferable to another, we tend to view these three notions as working well together, with part of the picture remaining hidden if one or more of the measures is discarded. Let us consider a few examples that involve musical connections and illustrate the way in which the nonlinear structure of the majorization order fits together with the sum of distances and the notion of energy.
Figure 5: Majorization order on distance vectors of three-note chords that maximize the sum of distances.
Example 4. Using the notation of Theorem 4, each set in has cardinality 3, has a distance vector of length and corresponds to a musical chord (see Figure 5), whereas each set in has cardinality
The Music and Mathematics of Maximal Evenness in Graphs
7, has a distance vector of length and corresponds to a musical scale (see Figure 6). Let us consider the majorization order on the distance vectors of sets in and .
In both Figure 5 and Figure 6, the set on the left is maximally even, has minimal energy and its distance vector is majorized by the distance vector of every other set in the diagram. The energies of the displayed sets increase from left to right and each line indicates a majorization between the distance vectors of the displayed sets, where one can “compose” majorization by transitivity. For example in Figure 5, (3,4,5) < (2,5,5) and (3,4,5) < (2,4,6) . It is worth noting that the majorization order on both sets of distance vectors is nonlinear. For example, in Figure 5, the distance vector is not comparable to , i.e. and . Let us also point out that reading Figure 6 from left to right, each time a new minor third (i.e. an interval consisting of three half steps) appears, a split in the majorization order occurs.
Figure 6: Majorization order on distance vectors of seven-note scales that maximize the sum of distances.
Summary and Conclusions
The notion of energy of a set of vertices serves as a suitable measure of evenness in any finite simple connected graph. Indeed, due to the mathematical theorems discussed above, the notion of minimal energy set of vertices is a faithful mathematical generalization of maximal evenness. We see the connections between Möbius ladder graphs and bomba, between and various scales as well as between the majorization order and scales, as providing evidence that our notion of energy, the sum of distances and majorization are worth studying in both the cyclic and the non-cyclic more geometrically complex context.
Acknowledgements
Special thanks to Jason Laferrera for creating software that allowed us to listen to minimal energy sets.
References
[1] T. Ando. “Majorization, doubly stochastic matrices, and comparison of eigenvalues.” Linear Algebra Appl., vol. 118, 1989, pp. 163-248.
Bushaw et al.
[2] E. A. Bjorklund. “The Theory of Rep-Rate Pattern Generation in the SNS Timing System.” SNS ASD Technical Note SNS-NOTE-CNTRL-100. Los Alamos National Lab- oratory, Los Alamos, U.S.A., 2004.
[3] G. S. Bloom, L. V. Quintas, and J. W. Kennedy. “Distance degree regular graphs.” The theory and applications of graphs (Kalamazoo, Mich., 1980). Wiley, New York, 1981. pp. 95–108.
[4] D. L. Burkholder. “Exit times of Brownian motion, harmonic majorization, and Hardy spaces.” Advances in Math., vol. 26, no. 2, 1977, pp. 182–205.
[5] J. Clough and J. Douthett. “Maximally Even Sets.” Journal of Music Theory, vol. 35, no. 1/2, 1991, pp. 93–173.
[6] E. D. Demaine, F. Gomez-Martin, H. Meijer, D. Rappaport, P. Taslakian, G. T. Toussaint, T. Winograd, and D. R. Wood. “The distance geometry of music.” Comput. Geom., vol. 42, no. 5, 2009, pp. 429–454.
[7] R. G. Douglas. “On majorization, factorization, and range inclusion of operators on Hilbert space.” Proc. Amer. Math. Soc., vol. 17, 1966, pp. 413–415.
[8] J. Douthett and R. Krantz. “Energy extremes and spin configurations for the one-dimensional antiferromagnetic Ising model with arbitrary-range interaction.” J. Math. Phys., vol. 37, no. 7, 1996, pp. 3334–3353.
[9] J. Douthett and R. Krantz. “Maximally even sets and configurations: common threads in mathematics, physics, and music.” J. Comb. Optim., vol. 14, no. 4, 2007, pp. 385–410.
[10] J. Douthett and R. J. Krantz. “Dinner tables and concentric circles: a harmony of mathematics, music, and physics.” College Math. J., vol. 39, no. 3, 2008, pp. 203–211.
[11] F. Gómez-Martín, P. Taslakian, and G. Toussaint. “Interlocking and Euclidean rhythms.” J. Math. Music, vol. 3, no. 1, 2009, pp. 15–30.
[12] G. H. Hardy, J. E. Littlewood, and G. Pólya. “Some simple inequalities satisfied by convex function.” Messenger Math., vol. 58, 1929, pp. 145–152.
[13] R. Klette and A. Rosenfeld. “Digital straightness—a review.” Discrete Appl. Math., vol. 139, no. 1-3, 2004, pp. 197–230.
[14] M. O. Lorenz. “Methods of Measuring the Concentration of Wealth.” Publications of the American Statistical Association, vol. 9, no. 70, 1905, pp. 209–219.
[15] A. W. Marshall, I. Olkin, and B. C. Arnold. Inequalities: theory of majorization and its applications, 2nd ed. ser. Springer Series in Statistics. Springer, New York, 2011.
[16] E. Martínez. Raíz: A practical guide to develop modern rhythms using traditional afrocaribbean styles. CreateSpace Independent Publishing Platform, 2018.
[17] R. Mauleón. Salsa Guidebook: For Piano and Ensemble. Sher Music Co., 2005.
[18] R. F. Muirhead. “Some Methods applicable to Identities and Inequalities of Symmetric Algebraic Functions of n Letters.” Proceedings of the Edinburgh Mathematical Society, vol. 21, 1902, p. 144–162.
[19] I. Schur. “Über eine Klasse von Mittelbildungen mit Anwendungen auf die Determinantentheorie.” Sitzungsberichte der Berliner Mathematischen Gesellschaft, vol. 22, no. 9-20, 1923, p. 51.
[20] G. Toussaint. “The geometry of musical rhythm.” Discrete and computational geometry. ser. Lecture Notes in Comput. Sci. Springer, Berlin, 2005. vol. 3742. pp. 198–212.
[21] G. T. Toussaint. “The Euclidean Algorithm Generates Traditional Musical Rhythms.” Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science. vol. 99. 2005. pp. 47–56.
[22] Yolydia. Barril de Cuña. [Photograph], 2008. https://commons.wikimedia.org/wiki/File:Barril_de_Cu%C3%B1a.JPG.