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
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
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
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.
