Ernst Bacon Redux (2)

In the logician's voice:

an algorithm is

a finite procedure,

written in a fixed symbolic vocabulary,

governed by precise instructions,

moving in discrete steps, 1, 2, 3, ...,

whose execution requires no insight, cleverness,

intuition, intelligence, or perspicuity,

and that sooner or later comes to an end.

– David Berlinsky

The Advent of the Algorithm

There is no interesting new math lurking in this or related posts. The math used is elementary. The goal here is not the math, but to describe a simple logical procedure that can produce/reveal increasingly complex and possibly useful structures. I have used variations of this procedure for the past 30 years, initially to generate "set-class lists" of any size which can then be sorted and queried in various ways such as sorting by interval-class vector or listing all the z-related semiquaver rhythmic structures possible within a measure of 12/8 (the next post will describe a partition puzzle revealed by the list of tetrads generated in the next post). The whole edifice is built from a few elementary ideas and does not demand an understanding of more advanced underlying concepts such as the Polya enumeration theorem, although the results of Polya (calculated by others and readily available) are essential in checking that no string has been omitted from the list, especially when one is working out a complete list quasi "by hand" using a spreadsheet.[1]

Summarizing and extending the previous post, when there are just three integers x,y,z making up an interval string (typically, in music, a trichord or a 3-onset rhythm the procedure for listing all combinatorial possibilities is relatively simple, no matter what size chromatic space you are working in,[2]

1. Since there are k=3 intervals in each string, list the partitions of 3:
   1.  2+1
   2.  1+1+1
   3.  3
[3]
2. Next, write out three independent equations using the three partitions of 3 from step 1 as coefficients:
   1.  2x + 1y = m    (x≠y)
   2.  1x + 1y + 1z = m    (x≠y≠z)
   3.  3x = m
Each 3-string in the final list must be a unique cyclic permutation of one of the positive integer solutions to one of these Diophantine equations. So finally:
3. Substitute the solution of step 2, which will be the 3-partitions[4] of m, into the following corresponding cyclic-permutation equivalence classes

   1.  (x,x,y⤸

   2.  (x,y,z⤸, (y,x,z⤸

   3.  (x,x,x⤸

It's a simple matter of filling in the blanks.

If we set m=12 as in the previous post, we get the 19 possible 3-strings in 12-space as first listed in comparable order by Ernst Bacon. Now beginning to step beyond Bacon, if we set m=6, the solutions to the same equations in step 2 are

   1.  x=1, y=4

   2.  x=1, y=2, z=3

   3.  x=2

which can then be substituted into the permutation classes in step 3 to yield the 4 possible specific permutations in 6-space:

   1.  (1,1,4⤸

   2.  (1,2,3⤸, (2,1,3⤸

   3.  (2,2,2⤸
Note that not all of the general permutation classes listed in step 3 are always used. For example, if m=8 we have

   1.  (1,1,6⤸, (2,2,4⤸, (3,3,2⤸

   2.  (1,2,5⤸, (2,1,5⤸, (1,3,4⤸, (3,1,4⤸

   3.  N/A! (There is no positive integer x that satisfies 3x = 8)

If we set m=24, we can write out the complete list of 85 transposition classes of 3-note chords (in interval string form) in the quarter-tone scale. Even done by hand, while this is a boring task, it doesn't take overly long once you realize all you are doing is filling in the blanks based on a simple set of instructions – the essence of algorithm. Once the task is set up correctly (a task in logic), actually doing it (running the algorithm) "requires no insight, cleverness, intuition, intelligence, or perspicuity." But now we need to widen the application.

Continued in next post, Ernst Bacon Redux (3)

____________________________

[1] The need for keeping track of counts using results from the Polya theorem was brought home to me rather painfully after I wrote the following in an article in Perspectives of New Music:

"... assuming the search for new sonorities will continue, we have to assume that, say, in the quartertone universe, the tonal and atonal possibilities we have discovered in twelvetone are sufficient to deal with 24 notes and 337,697 set classes (the last figure is an actual count, not an inflated guess)."

It was in fact an "actual count." So I was somewhat mortified when, after publication, I received an email from a colleague, noted mathematical music theorist Jay Hook, politely telling me that according to the Polya theorem, there are actually 352,698. Subtracting 1 (for the null string I ignored) from the total Jay gave me, my total was short exactly 15,000 set classes! This nice round figure might seem a little unexpected for an error in an adding-machine calculation like this, but due to the algorithm I was using it allowed me to figure out fairly easily what sets of strings I had missed and why I missed them, and without having to start all over from scratch. Of course it would have been silly to ask PMN to print a correction in a following edition. After all, my point, here anyway, was not the exact number, but the magnitude of difference between numbering the planets and numbering the stars. But why would I have not checked the Polya count before publishing my "actual count"? The answer is simple and, again, a bit embarrassing. The relevant enumeration theorem was first published by John Howard Redfield in 1927. It was independently discovered and published by Polya in 1937. The 18-year old Bacon accomplished his feat in 1916, before Redfield's and Polya's work. And he got it right. (You don't think it was a feat? Lock yourself in a room with nothing but pencil and paper and try writing out all the set classes mod 13.) I, on the other hand, when I was trying this for the first time, was not only ignorant of the Polya theorem, I had never heard of young Ernst Bacon's essay. Not having a brain comparable to his, I got it wrong at first.

[2] The task itself, while simple, admittedly does get more tedious the larger the chromatic space, so by-hand calculations become progressively more prone to error. A computer, however, would accurately produce the list of all 3-ads mod500 in relatively short time – if you have a need or desire to examine such a list. A Very Big Universe may become less absurd if we wish to create/investigate relationships between/within large scale musical patterns or discover connections to non-musical structures.

[3] Normally, the order would be 3, 2+1, 1+1+1 (reverse lex), but in this particular case I am listing the 3 at the end only because I started out with this order for generating trichords in the previous post which I thought more closely follows Bacon's chart where 3 is at the bottom. I'll return to the more "traditional" ordering now when 4-ad strings make their appearance below.

[4] NB: Partitioning in this algorithm is used in two separate steps & not to be confused. If we have a string with k components that sum to m, first partition k in step 1 in order to derive the general equations in step 2. Then partition m in step 2, the k-partitions of m, to get all possible specific solutions for substitution in step 3.

Ernst Bacon Redux (3)

Continued from Ernst Bacon Redux (2)

Here is Bacon's "Table III; N=4" from "Our Musical Idiom" tracing his "calculation" of tetrachords:

Take the eight "combinations" (listed in the left-most column as 2,3,4,6,9,10,12,14). These all have one thing in common relative to this discussion. Each of them represents an interval string (our terminology, not Bacon's) that contains two intervals that are the same along with two intervals that are different – e.g., C.2 represents all interval strings (in 12tET) that are made up of two 1's (minor seconds), one 2 (major second), and one 8 (minor sixth). The H column tells us that there are just three distinct "harmonies" (cycle-class interval strings) that can be made from those intervals by permutation. Similarly, C.3 shows that there are three "harmonies" that can be derived from permutations of 1,1,3,7. And the same idea follows for C.4,6,9,10,12,14. All 8 of these represent solutions of 2a + b + c = 12.

Here is how the algorithm introduced in the previous post (which can be viewed as a "completion" of Bacon's method) gets to all 43 (Tn) "harmonies" in Z12:

1. List the partitions of 4:
  1.          4
  2.         31
  3.         22
  4.       211
  5.     1111
2. Generate equations from step 1:
  1.                4a = m
  2.         3a + b = m
  3.        2a + 2b = m
  4.    2a + b + c = m
  5. a + b + c + d= m
3. Pull out the equivalence classes (distinct cyclic permutations) from step 2 (or call from a template "library" of k-length cyclic permutation classes, not shown here):
  1. (a,a,a,a⤸
  2. (a,a,a,b⤸
  3. (a,b,b,a⤸, (a,b,a,b⤸
  4. (a,a,b,c⤸, (b,a,a,c⤸, (a,b,a,c⤸
  5. (a,b,c,d⤸, (c,b,a,d⤸, (b,c,a,d⤸,(a,c,b,d⤸,(c,a,b,d⤸,(b,a,c,d⤸
4. Set m=12 & list solutions to step 2:
  1. (3)
  2. (1,9),(2,6)
  3. (1,5),(2,4)
  4. (1,2,8),(1,3,7),(1,4,6),(2,1,7),(2,3,5),(3,1,5),(3,2,4),(4,1,3)
  5. (1,2,3,6),(1,2,4,5)
5. Substitute results of step 4 into the templates listed in step 3:
  1. 3333
  2. 1119 2226
  3. 1551 1515 2442 2424
  4. 1128 2118 1218 1137 3117 1317 1146 4116 1416 2217 1227 2127 2235 3225 2325
      3315 1335 3135 3324 2334 3234 4413 1443 4143
  5. 1236 3216 2316 1326 3126 2136 1245 4215 2415 1425 4125 2145

The most significant step in the algorithm is no. 3, because once you have worked it out for one chromatic universe (the template library alluded to), it is the same for any other. While the list of strings grows dramatically as m increases (the number of partitions of m increase as m grows larger), the number of templates in step 3 remains the same because k, the length of any string in the list, is constant. 

Eliminating mirror-equivalent strings from step 3 will result in the usual TnI set-class list. For the results of setting k=4 and running m from 4 to 24, see "Tetrads mod 4 through 24."

Ernst Bacon Redux (1)

Gold is rarely discovered

by one who has not got

the lay of the land.[1]

– Norwood Russell Hanson

Patterns of Discovery

In 1916, Ernst Lecher Bacon, at the age of 18, submitted a technical article for publication to The Musical Quarterly. The editor of MQ at the time, Oscar Sonneck, declined to publish Bacon's article, but not because it was untutored or incompetent or poorly written or that it offered nothing original. While he may not have followed the math (the how of the article), Sonneck understood what Bacon had done and knew quite well that it was an astonishing accomplishment.

Still, he rejected the article on the grounds that MQ's primary readership – historians, analysts and others in the musicology orbit – even if they could follow the math (a big leap in the music world, even today), would find it irrelevant (again, even today). But, recognizing the genius of this accomplishment, Sonneck did not simply write a brief rejection. He wrote back an encouraging letter (via Bacon's mentor, Glenn Dillard Gunn) suggesting that Bacon submit the article to the philosophy journal The Monist. It appeared in the October 1917 issue of that journal under the title "Our Musical Idiom."[2] Unlike events in the political world of October 1917, Bacon's groundbreaking work inspired neither a revolution nor a war. Here's what happened:

It was virtually ignored.

What Bacon had done was create a combinatorial algorithm for listing all the sonorities – represented as  transposition classes – in the 12-note chromatic scale.[3] Then, using common music notation, he proceeded to list all 350 "prime-position" sonorities (he omitted the empty set and the singleton which he thought of as trivial). It was a bit like snatching the gold ring, when hardly anyone else on the merry-go-round knew there was a gold ring to snatch. Here's how he did it.

First, he stopped thinking in terms of notes or pitches (or pitch-classes) as the primary musical objects  and began thinking in terms of the intervals between notes. This is the single move that takes the task from nearly impossible to tractable. So chords or scales were not his quarry, but abstract strings of intervals.

It's the difference between, say, a C-major triad (a concrete structure which consists of the three notes/pitch-clases C and E and G) and an icon representing any triad in the same relationship as the notes in the set {C,E,G}. This unique icon simply names the chromatic intervals between notes in some circular permutation. Using Howard Hanson's notation from Harmonic Materials of Modern Music, we might represent a C-major triad within an octave span as:

C4E3G5(C).

Dropping the referential note-names, the collection of all major triads can be described abstractly by a circular permutation of the interval string 4-3-5. (This relationship must hold (mod12) if you are to respond correctly to the question, "Go to the piano keyboard and play any major triad.") This interval string notation is precisely how Bacon calculates and names all distinct transposition classes mod 12. Here is his table listing all the trichords[4]:

Note that he uses an abbreviated "name" for each unique "harmony." This is a convention that he uses throughout for sonorities of any cardinality. E.g., here the name for C.1 (Combination 1) is given as 1-1 instead of the complete 1-1-10. Since all the intervals in a string in 12tET must sum to 12, the final interval can be left off and still identify the same unique transposition class.[5] Working backward, we now ask, just how did he generate these 19 trichords? Take a look at his chart summarizing his derivation of trichords (ignore the column "Calculations of Harmonies" for the moment):

This chart for trichords represents the solutions to the three equations to the left of the arrows:

(1)     2a + b = 12    →   a-a-b (1-1-10, 2-2-8, 3-3-6, 5-5-2)

(2) c + d + e = 12   →   c-d-e (1-2-9, 1-3-8, 1-4-7, 1-5-6, 2-3-7, 2-4-6, 3-4-5)

(3)            3f = 12     →   f-f-f (4-4-4)

with the stipulation that all the solutions are positive integers less than 12. The mathematician will immediately recognize these equations as simple linear Diophantine equations, and the triples to the right of the arrows (the exact solutions) represent the 3-partitions of 12 (all the triples of integers that add up to 12).[6]

Translating to music, all the integers a,b,c,d,e,f represent intervals less than an octave (measured in number of chromatic steps). To the right of the arrows, the triples represent interval strings. If we stopped here we would have the familiar list of 12 trichord set classes, but like most musicians Bacon wants to distinguish between inversions – e.g., major and minor triads are different animals. So all these results are permuted until all the unique permutations have been discovered. This final process sorts the trichords into symmetric and asymmetric (among other things – see the next post). Permutations of the asymmetric sets (C.2,3,4,5,7,8,11) add the respective inversions, so 1-2-9 is joined by its inversion 2-1-9 (or, what's the same, 1-9-2 using Bacon's preferred ordering). So the complete list of 19 trichords Bacon generated (in integer notation) is:

(1') a-a-b: 1-1-10;  2-2-8;  3-3-6;  5-5-2

(2') c-d-e: 1-2-9, 2-1-9;  1-3-8, 3-1-8;  1-4-7, 4-1-7;  1-5-6, 5-1-6;  2-3-7, 3-2-7;

                2-4-6, 4-2-6;  3-4-5, 4-3-5

(3') f-f-f:   4-4-4

which (for those who don't recognize them) appear in abbreviated notation in his list of "harmonies" (see above). Using Bacon's ordering:

1-1    1-2    1-9    1-3    1-8    1-4

1-7    1-5    1-6    2-2    2-3    2-7

2-4  2-6   2-5   3-3  3-4  3-5   4-4

(To be continued)

________________________

[1] The context for the quote can be found online (Ch.1 of Patterns of Discovery). But the context is important enough to quote a bit more here: "It is the sense in which Tycho and Kepler do not observe the same thing which must be grasped if one is to understand disagreements within microphysics. Fundamental physics is primarily a search for intelligibility – it is philosophy of matter. Only secondarily is it a search for objects and facts (though the two endeavors are as hand and glove). Microphysicists seek new modes of conceptual organization.  If that can be done the finding of new entities will follow. Gold is rarely discovered by one who has not got the lay of the land. . . . It is important to realize ... that sorting out differences about data, evidence, observation, may require more than simply gesturing at observable objects. It may require a comprehensive reappraisal of one's subject matter. This may be difficult, but it should not obscure the fact that nothing less than this may do." [my emphases] Does this apply to music theory? Recall Lewin: "This is the methodological point: We must conceive the formal space of a GIS as a space of theoretical potentialities, rather than as a compendium of musical practicalities." (GMIT 2.3.2)

[2] I'm going from memory in this entire account, having last read the source material 4-5 years ago. I no longer have direct access to the correspondence in the Bacon, Gunn and Sonneck papers in the Music Division at the Library of Congress which are the basis for the story of the publication of "Our Musical Idiom." I should have made private copies or taken extensive notes, but I didn't.

[3] Catherine Nolan has written extensively on the history of this particular aspect of the connection between music and mathematics. Available on line, as one example, is her 2000 Bridges paper "On Musical Space and Combinatorics."

[4] I will henceforth try to remember to use "triad" when referring to the familiar, historically-conceived major, minor, diminished and augmented triads. I will use "trichord" to refer to the (ahistorically-conceived) set of any 3-voice sonority, usually the list of 12 trichord set classes or the list of 19 trichord transposition classes in 12tET. This is exactly backward from how I would prefer to use these terms since trichord suggests sonority and leaves no room for extensions of the concept such as 3-point rhythmic structures; and triad, a more abstract term that could refer to any set of 3 things, has been historically usurped within music to refer to traditional Western 3-voice chords built of superimposed thirds (or however you wish to construe/generate them). So any triad is also a trichord, but not all trichords are triads. No, this does not make any sense, but I didn't create this particular mess.

[5] This shorthand is useful but can easily result in errors such as mistaking a symmetry as an asymmetry leading one to think there is a distinct inversion where there is none. E.g., listing the tetrachords 1-1-5 and 5-1-1 as distinct inversions when citing the "full" name, 1-5-5-1, reveals it is a symmetry & has no distinct abstract inversion. So reader beware.

[6] Readers who have not previously encountered the idea of using numerical partitions to generate chord lists may wish to go to the interactive page for partitions at the Combinatorial Object Server and plug in random values for k and n (ignore m) to quickly get an idea of how important this simple idea is. Start with n=12 then increase n to get partitions (the math term for what Bacon calls "Combinations") for larger musical universes. E.g., for partitions leading to listing hexachords in 12tET set n=12 & k=6 to get 11 partitions to work from; for hexachords in quartertone space set n=24 & k=6 to get 199 partitions to work from.