Maximally Even Sets

Year: 2000 Authors: Richard Krantz; Jack Douthett; John Clough

Core claim

Maximally even sets can be characterized by average chord length, spectra, and recursive construction, linking musical structure with physics and combinatorial ordering.

Topics

maximal evenness, pitch-class sets, average chord length, spectra, Bohlen-Pierce scale

Domains

combinatorics, geometry, number theory, mathematical music theory, music theory, sound design, visualization, education

Methods

circle-point arrangements, chord-length averaging, spectral analysis, iterative construction

Media

unit circle, pitch-class diagrams, seating arrangement figures, musical scales

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 Mathematical Connections in Art, Music, and Science

Maximally Even Sets

A discovery in mathematical music theory is found to apply in physics

Richard Krantz Department of Physics Metropolitan State College of Denver Denver, CO 80217 e-mail: krantzr@mscd.edu

Jack Douthett Department of Arts and Sciences TVI Community College Albuquerque, NM 87106 email: jdouthett@tvi.cc.nm.us

John Clough Department of Music SUNY Buffalo Buffalo, NY 14209 e-mail: clough@acsu.buffalo.edu

1. Introduction

We wish to seat eight dinner guests—four women and four men—about a round table so that the guests of each gender are distributed as evenly as possible. The obvious solution is to seat men and women alternately. Now suppose we have five women and three men. Ignoring rotations and reflections, there are essentially five ways to seat them (Fig. 1). Which of these is the most (maximally) even distribution? (We will see later that the optimum distribution for one gender guarantees the same for the other.)

On the basis of the informal “most even” criterion, the best choice seems to be Fig. 1e (which happens to be the only arrangement that avoids seating three or more women together). This is a relatively simple case, but “dinner table” cases with larger numbers also have a unique best solution. How can we formalize our intuition about evenness for all such cases?

1 a

1 b

1 c

1 d

1 e

Fig. 1: Seating Arrangements

2. Defining Maximal Evenness

There are many ways to define maximal evenness consistent with the dinner guest problem above. We will give three very different but equivalent ways of defining such an arrangement.

2.1 The Measurement.

Let us put this problem in a more abstract setting. Given $c$ equally spaced points around the circumference of a unit circle, we wish to select $d$ of these points to form a maximally even distribution that accords with intuition. One way is to choose a distribution that maximizes the average chord length between pairs of selected points when compared with all possible distributions of $d$ points [1]. In this way the selected points are, on average, pushed as far apart as possible. For the unit circumference circle with $c$ points, the length of the chord that connects points that are $n$ points apart is given by

194 Richard Krantz, Jack Douthett, and John Clough

The average chord length for men in Fig. 1 is worked out in Fig. 2, where the selected points are shown as filled circles. These configurations are listed from least to greatest average chord lengths and range from a minimally even set in Fig. 2a with an average of 0.98 to a maximally even set in Fig. 2e with an average of 1.70. Up to rotation and reflection, this figure lists all possible ways of selecting three out of eight points around the unit circle.

2a - 0.98

2b - 1.34

2c - 1.54

2d - 1.61

2e - 1.70

Fig. 2: Average Chord Length

Minimally even sets (sets whose average chord length is minimum) have comparatively simple structures; all the filled circles—and hence, all the open circles—are clustered together. Using Eq. 1 it is possible to construct an algorithm that, for a given $c$ and $d$, gives the minimum average chord length:

For the configuration in Fig. 2a, ${\mathrm{Ave}}_{\min }=0.98$. By comparison, the algorithm for calculating the average chord length of a maximally even set (sets whose average chord length is maximum) is considerably more complicated and involves a knowledge of floor functions, $\lfloor x\rfloor$, and fraction functions, $\{x\}$ [2]. The floor function, $\lfloor x\rfloor$, is the greatest integer less than or equal to $x$. The fraction function, $\{x\}$, is the fractional or decimal part of $x$. In addition, the function $[d|n]$ is 1 if $d$ divides $n$ and 0 otherwise; thus $[3|8]=0$ and $[4|8]=1$. The algorithm that, for a given $c$ and $d$, gives the maximum average length is

For the configuration in Fig. 2e, ${\mathrm{Ave}}_{\max }=1.70$. The configuration of filled circles in Fig. 3b, below, is also a maximally even set. Using the Pythagorean Theorem, it is not difficult to observe that the average chord length for this figure is $(2+2\sqrt{2})/3$. Using the algorithm in Eq. 2, ${\mathrm{Ave}}_{\max }=(2+2\sqrt{2})/3$ as well.

Fig. 3: Spectra

${\mathrm{D}}_2$ ${\mathrm{D}}_3$ ${\mathrm{D}}_4$ ${\mathrm{D}}_5$ ${\mathrm{D}}_6$ ${\mathrm{D}}_7$

Maximally Even Sets 195

2.2 The Spectra. A particularly important property of maximally even distributions as defined above (important both to music and physics) involves what some music theorists call a spectrum [3,4]. Count, always moving clockwise, the number of points from one selected point (i.e., filled circle) to another in two different ways—by counting only the selected points and by counting all of the points between. The first of these measurements is called the generic length and the second the specific length. The generic length from a selected point to the next selected point is 1; if there is a selected point between them, the generic length is 2; if there are two selected points between them, the generic distance is 3; etc. For example, if the filled circles marked ${\mathrm{D}}_0$, ${\mathrm{D}}_1$, ${\mathrm{D}}_2$, and ${\mathrm{D}}_3$, in Fig. 3a are the selected points, the generic lengths from ${\mathrm{D}}_0$ to ${\mathrm{D}}_1$, from ${\mathrm{D}}_1$ to ${\mathrm{D}}_2$, from ${\mathrm{D}}_2$ to ${\mathrm{D}}_3$, and from ${\mathrm{D}}_3$ to ${\mathrm{D}}_0$ are all 1; from ${\mathrm{D}}_0$ to ${\mathrm{D}}_2$, from ${\mathrm{D}}_1$ to ${\mathrm{D}}_3$, from ${\mathrm{D}}_2$ to ${\mathrm{D}}_0$, etc. are 2, and from ${\mathrm{D}}_0$ to ${\mathrm{D}}_3$, from ${\mathrm{D}}_1$ to ${\mathrm{D}}_0$, etc. are 3. The specific length from one point to another is simply the total number of points between them (technically, if the endpoints are included, the length is one less than the number of points; if the endpoints are not included, the length is one more than the number of points). That is, the specific length from ${\mathrm{D}}_0$ to ${\mathrm{D}}_1$ is 3, from ${\mathrm{D}}_0$ to ${\mathrm{D}}_2$ is 4, from ${\mathrm{D}}_1$ to ${\mathrm{D}}_2$ is 1, from ${\mathrm{D}}_0$ to ${\mathrm{D}}_3$ is 5, etc.

The spectrum of a generic length is the set of specific lengths associated with that generic length. In Fig. 3a the set of specific lengths associated with the generic length of 1 is $\{1,3\}$, since the specific lengths from ${\mathrm{D}}_0$ to ${\mathrm{D}}_1$ and from ${\mathrm{D}}_3$ to ${\mathrm{D}}_0$ are 3 and the specific length from ${\mathrm{D}}_1$ to ${\mathrm{D}}_2$ and from ${\mathrm{D}}_2$ to ${\mathrm{D}}_3$ is 1. This is written <1> = \{1, 3\}, where the number inside the angled-bracket represents the generic length and the numbers inside the curly-bracket represent the associated specific lengths. There are 3 specific lengths associated with a generic length of 2; <2> = \{2, 4, 6\}. Similarly <3> = \{5, 7\}.

In these terms, it has been shown that the average chord length is maximized precisely when each generic length is associated with either one or two consecutive specific lengths [1]. The arrangement in Fig. 3a does not qualify for two reasons; the spectra do not contain a single or consecutive integers, and <2> contains more than two integers. Fig. 3b, however, does qualify since each spectrum consists of a single integer. The 3 in 8 arrangements of Figs. 1 and 2 are reproduced in Fig. 4 with the spectra listed. The only arrangement for which each spectrum consists of one or two consecutive integers (i.e., each generic length corresponds to one or two consecutive specific lengths) is that shown in Fig. 4e, which is the same arrangement that maximizes the average chord length.

Fig. 4: “Seating” Spectra

2.3 The ME Algorithm. If we label $c$ sites evenly spaced on the circumference of a circle consecutively with integers 0 through $c-1$ then the maximally even (ME) algorithm provides a convenient way of selecting $d$ points distributed in a maximally even way [5]

Let $i$ be a fixed integer such that $0\le i\le c-1$, and assign the selected points to sites with labels $\lfloor (ck+i)/d\rfloor$ where $k=0,1,\dots ,d-1$ and $\lfloor x\rfloor$ is the floor function.

196 Richard Krantz, Jack Douthett, and John Clough

Clough and Douthett [5] have shown that, for any given $c$ and $d$ and for each $i$ , $0\le i\le c-1$ , this algorithm generates all and only the distributions for which each spectrum consists of one or two consecutive integers. These authors have also shown that all such sets are equivalent under rotation and that $i$ , called the index, determines the rotation. In view of the discussion above, concerning the connection between average chord length and sets whose spectra consist of one or two consecutive integers, there are now three equivalent ways to define a maximally even set:

1. A maximally even set with parameters $c$ and $d$ is a set that, when compared with all other $d$ -point distributions on $c$ points, has a maximum average chord length.
2. A maximally even set is a set in which every spectrum consists of one or two consecutive integers.
3. A maximally even set with parameters $c$ and $d$ is a set whose integer elements are $\lfloor (ck+i)/d\rfloor$ where $k=0,1,\dots ,d-1$ and $i$ is a fixed integer such that $0\le i\le c-1$ .

If we reproduce the arrangement of Fig. 4e and label the sites with integers 0 through 7 (see Fig. 5) then the set of labels of the selected points is $\{0,3,6\}$ . This corresponds to the maximally even set with $c=8$ , $d=3$ , and $i=2$ . Other values of $i$ produce rotations of the distribution shown. For the maximally even set in

Fig. 3b, $c=8$ , $d=4$ , and $i=0$ .

Fig. 5: Selected Points

2.4 Summary. The above provides three equivalent definitions for maximal evenness; one in terms of average chord length, another in terms of spectra, and the third in terms of the algorithm. In the original work on maximally even sets, the spectra definition was adopted [5]. In that work it was shown that the complement of a ME set is also a ME set. Since ME sets maximize average chord length, it must also be true that the average chord length of the open-circle pairs in Fig. 2e is greater than that of any of the other distributions in Fig. 2. This can be seen in Table 1 where the averages for the filled-circle chords and open-circle chords (chords connecting filled and open circles, respectively) are listed in the first two rows for all the configurations in Figs. 2 and 4. Note that as the average chord lengths for filled-circle sets increase from one configuration to the next, so do the averages of their complementary open-circle sets; it can be shown that this is generally the case [2]. The filled-circle set of the configuration in Fig. 2e has the greatest average chord length, and hence, so does its complementary open-circle set. In addition (since the complement of a maximally even set is maximally even), each spectrum of the open-circle distributions in Figs. 3b and 4e consists of one or two consecutive integers, and for $c=8$ and $d=5$ there exists an integer $i$ , $0\le i\le 7$ , such that the open-circle labels in Fig. 5 can be computed via the ME algorithm. The ME algorithm can also be used to compute the open-circle set in Fig. 3b. It is left to the reader to verify that this is in fact the case.

Table 1 - Average Chord Lengths

Maximally Even Sets 197

Finally, it can be shown that if the average distance between men (and hence, the average distance between women), in our dinner party example, is maximum then the average distance between members of the opposite gender is minimum [2,6]. Thus, if our dinner party is meant to be a “mixer” the optimal seating is also a maximally even distribution. This too can be seen in Table 1 in which the last row lists the average mixed chord (a chord connecting a filled circle and an open circle) length for the configurations in Figs. 2, and 4. Thus, maximum average chord length for filled-circle chords, maximum average chord length for open-circle chords, and minimum average chord length for mixed chords occur simultaneously and occur precisely when one—and hence, both—of the sets are maximally even.

3. Even(ness) in Physics

The simplest description of the pairwise interaction of “spins” on a lattice is given by the Ising model [7]. The “spins” may represent angular momentum, intrinsic electron spin, or any two-state variable. In this model, spins at each lattice site, represented by the arrows in Figs. 6, 7, and 9 may take on the values $\pm 1$ depending on whether the spin orientation is up (+1) or down (-1). The spins interact pairwise according to some convex distance dependent interaction energy. An exponentially decreasing function that depends only on distance between pairs of spins is an example of such a convex distance dependent interaction [e.g., $\mathrm{J}(|i-j|)\propto \exp (-|{\mathrm{x}}_{\mathrm{i}}-{\mathrm{x}}_{\mathrm{j}}|)$]. Of particular interest are systems in which the interaction favors the antiparallel arrangement of spin pairs (i.e., spins that preferentially line up opposite to one another due to their pairwise interaction). Such a system is said to be “antiferromagnetic.”

The so-called configurational energy, $U$, of an arrangement of $N$ spins interacting antiferromagnetically by a pairwise distance dependent interaction energy $J(|i-j|)$ is attained by adding the contributed energy of all distinct pairs:

where $i$ and $j$ represent the lattice points 0 through $N-1$. The sum is over all distinct pairs of spins. The argument of $J$ is written as an absolute value to indicate that the interaction depends only on the distance between spin pairs. The $\sigma$‘s take on the values $+1$ or $-1$ depending on whether the spin at a particular lattice site is up $(+1)$ or down $(-1)$.

Consider the arrangement of spins shown in shown Fig. 6. For any given arrangement of up and down spins, all spin pairs cannot be antiparallel. Therefore, some distribution of up and down spins must result. This arrangement of up and down spins must minimize the energy defined in Eq. 3. In physics, analysis of a one-dimensional system as shown in Fig. 6 is simplified by considering the system shown in Fig. 7.

Fig. 6: Spins on a one-dimensional lattice

Fig. 7: Periodic Boundary Conditions

198 Richard Krantz, Jack Douthett, and John Clough

In other words, a one-dimensional lattice of up and down spins can be thought of as a cycle of lattice sites, some of which are occupied by up-spins and the rest are occupied by down-spins; technically, this is referred to as “invoking periodic boundary conditions.” This simplification is, in fact, an approximation that introduces some error into the calculation of the configurational energy for small values of $N$. It can be shown that as $N$ gets large, the error in the configurational energy introduced by invoking periodic boundary conditions can be neglected.

Comparison of Figs. 4 and 7 suggests that the problem of distributing up and down spins on a lattice is analogous to the “seating” arrangement problem analyzed above. It turns out that the solution to our spin distribution problem is also analogous to the solution of the dinner seating problem [6].

If the lattice consists of $N$ lattice sites ($c$ in our seating problem) $N+$ of which are occupied by up-spins ($d$ in our seating problem) then the up-spins occupy sites (up to rotation and inversion) defined by the ME algorithm. In other words, the distribution of up-spins (or equivalently, down-spins), in which all pairwise interactions are antiferromagnetic, is maximally even.

Even when our one-dimensional antiferromagnetic spin system is put in an external magnetic field (H) the spin distribution that minimizes the energy is still maximally even. In an external magnetic field a spin acquires an additional energy proportional to $\sigma \cdot \mathrm{H}$ due to its interaction with the field. For our Ising spins $(\sigma =\pm 1)$ the direction of the external magnetic field defines the plus-direction and the energy becomes:

The last sum accounts for the energy of all the individual spins due to the interaction of each one with the external field.

Notice that spins aligned along the field $(\sigma =+1)$ reduce the energy in Eq. 4, while spins aligned opposite to the field $(\sigma =-1)$ increase the energy due to the minus sign on the last sum. At the same time, in the first sum, pairs of spins aligned in the same direction increase the energy while spins aligned in the opposite direction decrease the energy. Therefore, there is a competition between the field contribution to the energy trying to align spins in the plus-direction and the pairwise interaction energy trying to align spins in opposite directions. Equilibrium is established when the total energy, Eq. 4, is a minimum. Remarkably, Krantz, Douthett, and Doty [8] have shown that a maximally even distribution of up and down spins minimizes this total energy even when an external field is applied. Specifically, when the external magnetic field is small, one-half of the spins are up and one-half are down. They are distributed, in a maximally even way, with alternate spins up and down. As the external magnetic field is increased, the number of up spins $(N+)$ increases relative to the number of down spins $(N-)$, but the distribution is still maximally even. As the external field is increased further, eventually, all the spins align along the field. The field at which this occurs is the, so-called, “critical magnetic field.”

4. Even(ness) in Music

As cited above, the discovery of the ME algorithm occurred in the mathematics of music theory. In music, a pitch class is the class of all pitches named “C,” including “middle C” and all higher and lower C’s. For Western music in general, we recognize just 12 such pitch-classes, corresponding to the pattern of 12 piano keys that repeats several times to form the full keyboard. This system can be thought of as the hours on a clock, but with 0 replacing 12. We need only map the 12 pitch-classes to the integers 0, 1, …, 11—for example all the C’s to pitch-class 0, all the ${\mathrm{C}}^4/{\mathrm{D}}^{\mathrm{b}}$ s to 1, D’s to 2, …, B’s to 11 (see Fig. 8). Then the set of white keys maps to the set $\{0,2,4,5,7,9,11\}$ and the black keys to the set $\{1,3,6,8,10\}$.

Maximally Even Sets 199

Fig. 8: Pitch Class

The connection between the Ising model and the 12 pitch-classes can be described as follows; if 7 out of every 12 spins are up (and, 5 out of every 12 are down) and the lattice energy is minimum, then the spin configuration of the lattice is the same as the white and black key configuration on the piano keyboard (see Fig. 9).

Fig. 9: Piano Keyboard and Up/Down Spins

Fig. 10: Piano Keyboard (White Keys Numbered)

Thus, the set of white key pitch-classes is a maximally even set as is the set of black key pitch-classes. In addition, many other important musical scales and chords are maximally even in the universe of 12 pitch-classes: the augmented triads are characterized by three equally spaced pitch-classes in the twelve pitch-class universe (e.g., $\{0,4,8\}$ representing the notes C, E, and $G^{\#}$). Similarly, diminished seventh chords have four equally spaced pitch-classes (e.g., $\{0,3,6,9\}$ representing the notes C, $E^{\mathrm{b}}$, $F^{\#}$ and A). These pitch-class collections are commonly used in the music of the 18th and 19th centuries. Debussy, a well known composer who lived at the turn of the last century, used the whole-tone scale, which is a collection of six equally spaced pitch-classes (e.g., $\{0,2,4,6,8,10\}$ representing the notes C, D, E, $F^{\#}$, $G^{\#}$, and $B^{\mathrm{b}}$). In the 20th century many composers, including Stravinsky, used the octatonic scale, which is characterized by pairs of consecutive pitch-classes with skips between them (e.g., $\{0,1,3,4,6,7,9,10\}$ representing the notes C, $C^{\#}$, $E^{\mathrm{b}}$, E, $F^{\#}$, G, A, and $B^{\mathrm{b}}$). All are maximally even sets! Many interesting scale structures in

200 Richard Krantz, Jack Douthett, and John Clough

microtonal systems (systems with other than 12 pitch-classes) are, also, maximally even. Most notably, Bohlen [9] and Mathews, Roberts, and Pierce [10, 11] proposed a 13 pitch-class system with a scale of 9 pitch-classes (the, so called, Bohlen-Pierce scale). Although the concept of maximally even sets had not yet been advanced, the properties required of the Bohlen-Pierce scale (most importantly, generalization of the cycle of fifths) forced its construction to be maximally even.

Whereas no three-note sets embedded in the C-major scale (the white keys) are maximally even within the 12 pitch-class universe (only the augmented triad is maximally even), some three-note sets are maximally even with respect to the white keys. Many historically important structures in music consist of three white keys spaced in a maximally even way within the seven white key universe. Suppose the white keys C through B are labeled 0 through 6, respectively (see Fig. 10). Then, for those with a musical background, the major triads C, F, and G correspond to the sets of labels {0, 2, 4} (i = 0 in the ME algorithm), {0, 3, 5} (i = 2), and {1, 4, 6} (i = 5), the minor triads Dm, Em, and Am to {1, 3, 5} (i = 3), {2, 4, 6} (i = 6), and {0, 2, 5} (i = 1), and Bdim to {1, 3, 6} (i = 4). All these are maximally even with respect to the white key universe. Such sets are known as iterated ME sets [12] since they are the maximally even “children” of a maximally even “parent” (3 in 7 in 12). In addition to these triads, historically important four note collections (seventh-chords in musical parlance) are also iterated ME sets (4 in 7 in 12). Iterations may even go deeper (maximally even “grand children”). Such an iterated substructure of triads can be observed in the Bohlen-Pierce 13-pitch-class system (3 in 4 in 9 in 13) [11, 13].

5. Coming Full Circle

We conclude with yet another example of maximally even ordering:

Let $c$ and $d$ be positive integers such that d < c. Place $d$ white points equidistantly around the circumference of one circle, and place $c-d$ black points equidistantly around another. Assume that the radii of the circles are the same. Superimpose the circles so that no two points occupy the same space. Pick any point as a starting point, and label the points consecutively clockwise with the integers 0 through $c-1$. Then, the set of black point labels (and hence the set of white point labels) is a maximally even set [2,5].

References

[1] S. Block and J. Douthett, Journal of Music Theory, 37, 21, (1993). [2] J. Douthett, Ph.D. Dissertation, University of New Mexico, (1999). [3] J. Clough and G. Myerson, Am. Math. Mon. 93(9), 695, (1986). [4] J. Clough and G. Myerson, Journal of Music Theory, 29, 249, (1985). [5] J. Clough and J. Douthett, Journal of Music Theory, 35, 93, (1991). [6] J. Douthett and R. Krantz, J. Math. Phys. 37(7), 3334, (1996). [7] J. Simon, The Statistical Mechanics of Lattice Gases (Princeton University Press, 1993). [8] R. Krantz, J. Douthett, and S. Doty, J. Math. Phys. 39(9), 4675, (1998). [9] H. Bohlen, Acoustica, 39, 76, (1978). [10] M. V. Mathews, L. A. Roberts, and J. R. Pierce, J. Acoust. Soc. Am. 75, S10 (1984). [11] M. Mathews, J. Pierce, and L. Roberts, “Harmony and new scales,” in Harmony and Tonality (J. Sundberg - ed.), Royal Swedish Academy of Music (Pub. No. 54), (Stockholm 1987). [12] J. Clough, J. Cuciurean, and J. Douthett, Journal of Music Theory, 41(1), 67, (1997). [13] M. Mathews, J. R. Pierce, A. Reeves, and L. A. Roberts, J. Acoust. Soc. Am. 84, 1214, (1988).