Thursday, April 10, 2014

Partition Puzzle 5: Feldman Analysis of Z-rels mod 31

Yesterday David Feldman left a comment on a previous E&EN blog entry. I felt it ought to be brought forward as a post of its own so it doesn't get overlooked. He has agreed to let me post it here as a Preliminary Report.

[Jon Wild wrote:]

"There is a quintuplet of Z-related hexachords in 31-tone equal
temperament whose interval vectors consist solely of 1s--they are all interval hexachords, expressing 15 interval classes in just six pitches. This set of 5 hexachords can be packed into the 31-tone aggregate leaving only one pitch uncovered. The odds that this is by chance are astronomical-there is some other principle at work, related to the observations Stephen has started to make, but I don't know what that principle is."

Here is a description of [this] example which may remove some of the mystery.

Modulo 31, the five sets can be written as[1]         

{3^0 , 3^10, 3^20, 3^3,  3^13, 3^23}         
{3^2 , 3^12, 3^22, 3^5,  3^15, 3^25}         
{3^4 , 3^14, 3^24, 3^7,  3^17, 3^27}         
{3^6 , 3^16, 3^26, 3^9,  3^19, 3^29}      
{3^8 , 3^18, 3^28, 3^11, 3^21, 3^31}

In the language of abstract algebra,
              {3^0 , 3^10, 3^20}
constitutes a subgroup of the multiplicative group of the field with 31elements and
              {3^3,  3^13, 3^23}

one of it's cosets.
              {3^0 , 3^6, 3^12, 3^18, 3^24}
constitutes a disjoint subgroup with 5 elements.

The five sets come from the first by multiplication, as one see quickly if one keeps in mind the congruence of 3^30 with 1 modulo 31.  Multiplication permutes intervals,but preserves all interval hexachords.

One could still argue that {3^0 , 3^10, 3^20, 3^3,  3^13, 3^23} giving an all-interval hexachord seems miraculous, but one surely gets all the intervals if no interval occurs twice. So write
            A = {3^0 , 3^10, 3^20}  B = {3^3 ,  3^13 , 3^23}
Obviously distinct pairs in A give distinct intervals (or the interval would have to be preserved by multiplication by 3^10); similarly distinct pairs in B; similarly a pair in A compared with a pair in B similarly two pairs each crossing A to B. 
Thus the only not obvious case would be a pair in A, say, and a pair crossing from A to B.  One can also rule out some of these cases a priori, and reduce the total number by symmetry, but in any case one doesn't have so many cases that the non-occurrence of an equality seems miraculous anymore.
– David Victor Feldman
9 April 2014 


[1] For a direct relationship to these sets in more recognizable integer notation, it may be helpful to use the following distribution of 3^n as an overlay:
1 25 5 27 24 11
9 8 14 26 30 6
19 10 2 17 22 23
16 28 18 29 12 21
20 4 7 13 15 3
If X is any one of these five sets,
V(X) = [6111111111111111]
V(X, complX) = [0 a a a a a a a a a a a a a a a]  (a=10)
remembering that complX always includes 0, the odd man out.

Sunday, April 6, 2014

Partition Puzzle 4: Knight's Gambit*

King Knight's Gambit

There appear to be two knotty issues in attempting to find a general solution to the homometric partition puzzle. First is the obvious problem posed by n-tuples. It is well known that z-related sets don't only come in pairs; there are z-related triples, quadruples, etc. This appears to be the most difficult problem. I'll put it on hold for now.

Second is a more subtle conjunct-disjunct problem. If two z-related sets S and T can be rotated or reflected (transposed or inverted) so they are in positions disjunct from one another, then we can always find a partition solution by the basic partition theorem given in the previous post. However, there are many cases for which two z-related sets cannot be positioned such that they are disjunct.

The easy case is when S and T have cardinalities larger than half the size of their K-space, but they are z-related because their smaller complements are z-related. A corollary to the basic partition theorem takes care of this type of case:

An example can be taken from K12. S={0,1,4,5,7} and T={3,6,9,10,11} are z-related. Q={2,8} and V(S,Q)=V(T,Q)=[0,2,2,2,2,2,0]. Their z-related complements are S'={2,3,6,8,9,10,11} & T'={0,1,2,4,5,7,8}, and Q'={0,1,3,4,5,6,7,9,10,11}. V(S',Q')=V(T',Q')=[5,12,12,12,12,12,5]. (Remember the first element of the spanning vector is the number of 0's (harmonic/melodic unisons, rhythmic simultaneities).)

When we get to K13 we run into a situation that at first appears to defy any attempt to apply any variation of the approach taken by the HPT. There are just two pairs of z-related hexads in K13.  {0,1,2,4,5,8} & {0,3,4,5,6,9} share the ICV [6323322] and {0,1,3,5,7,8} & {0,1,2,4,7,9} share ICV [6232233]. There are several notable things here. K13 is the first K-space with an odd number of nodes in which z-related sets appear. And 13 is not only odd, it's prime. Also, note the peculiar relationship between the vectors: their non-zero entries appear to be related by exchanging the ic cardinalities 2 and 3. Even though you may know why these two pairs are related this way, please stick with me through the following exposition which will lead off on a path that, at least within music theory (to my knowledge), is untrodden.i

Recall that in K12 there is a sort of sub-canonical atonal operation, usually denoted M5, which is simply multiplication by 5 mod 12. One of the interesting properties of this operation is that by modding back to 12 it exchanges interval classes 1 and 5, so if the ICV of some random set X is [aBcdeFg], the ICV of 5X will be [aFcdeBg], no matter how the operation may warp the shape of the set. And if B=F, X and 5X will also be Tn, TnI, or z-related. In K12 this operation only "works" (i.e., yields a full chromatic cycle) for multiplication by 1, 5, 7, and 11 because these are the only integers available that are co-prime with the modulus 12.

But since 13 is a prime number, in K13 all available integers 1 through 13 are co-prime with 13. For example, if X={0,1,2,4,5,8}, then 2X(mod13)={0,2,4,8,10,3}, so that V(X)=[6323322] and V(2X)=[6232233] (Figure 1).
Figure 1
So there isn't really an exchange of components between the vectors of these two pairs of sets, but a shuffle permutation that, in this example, gives a first-blush impression of such an exchange.[1] All of this is familiar territory to seasoned music theorists, even those who have never considered this particular case in K13 before.

Now comes the break-out question that might help us generalize the basic partition theorem to any pair of homometric sets, whether or not they are disjunct, and whether or not they appear in an even or odd K-space. Here's the question:

What if we don't mod out after multiplication?

In the example at hand, such a shift in procedure, rather than keeping us in K13, maps us into the subset consisting of only the even-numbered elements of K2X13 (i.e., K26). Furthermore, this shift retains the original ICV on the even-numbered components of the ICV of the transformed set(s) (Figure 2).
Figure 2
To reiterate & make the next move more clear, switch to a pictorial description. Look at the inscribed hexagons X={0,1,2,4,5,8} (the red hexagon) and Y={0,3,4,5,6,9} (blue hexagon) situated in K13 (Figure 3).
Figure 3
To apply the HPT we would like to rotate or reflect one of these hexagons such that X and Y are disjunct, leaving a singleton set for Q. Unfortunately, there is no way to do this – unless we think outside the circle, so to speak. Multiplying by 2 (without modding back into K13) yields the situation shown in Figure 4.
Figure 4
This gives us X'=2X={0,2,4,8,10,16} and Y'=2Y={0,6,8,10,12,18}.
The shapes of the hexagons in both cases are identical (invariant under a linear homothetic transformation). What has changed is that now they are situated only on the even numbered nodes, leaving us with an additional 13 nodes (the odd ones) to play with (Figure 5).
Figure 5
Rotating or reflecting either hexagon to odd-numbered nodes will guarantee that the two are disjunct. So let's move the blue hexagon by one click clockwise (Figure 6)
Figure 6
and ...

(1) we now have two hexagons with the same shape[2] as those we started with in K13;
(2) the K13 homometric relation is carried over into K26;
(3) the initial interval-class vector shared by X and Y in K13 is retained in the even components of the K26 vector for X' and Y' as well as any transposition of Y' (Figure 2);
and, finally, what is gained by this transformation,
(4) X' & Y' are disjunct and the basic partition theorem HPT can be applied. And ... voilà!

For the situation shown in Figure 6, X'={0,2,4,8,10,16}, Y"=T1(Y')={1,7,9,11,13,19}, = compl(X'UY") = {3,5,6,12,14,15,17,18,20,21,22,23,24,25}, and by the BPT:
V(X',Q') = V(Y",Q') = [06658866658785].

Obviously, this can also work in reverse, given the right initial conditions. If(!) two homometrically related figures can be rotated so that they are both placed on the even nodes of a K2n-space, whether that rotation makes them disjunct or conjunct, after the entire space is divided by two, in the resulting Kn-space the original figures will appear retaining their same shape and homometric relationship, as well as the same vector (with the zeros removed).

☛ Note to self & others: Lack of formality is still making this whole edifice unstable. It's still in a sense a CIP,  a conjecture-in-process.


* If the metaphorical connection of the title to the post content is unclear after reading, the answer will be provided in the next post.

[1] In passing, it's no secret that modded-out multiplication of pitch classes and interval classes can be alternatively expressed as permutations. Multiplication of ic's by 6 (mod 13) is summarized by the permutation (0)(615243), a spiral permutation in the same category as the sestina poetry form and the Klondike card shuffle. I'll be returning later to a few unusual but significant 20-21st century examples of permutations as compositional tools.

[2] A note from Charles Ives re escaping Diatony's gravitational pull: It may be helpful at first to understand "shape" as "chord." Example: If you have an augmented triad {0,4,8} in 12tET it can be described by its intervals expressed in semitones as (4,4,4). If you multiply by 2 mod 12, you get the same augmented triad {0,8,4}. Now, if you multiply by 2 without modding back into 12tET, you effectively still end up with a triad that sounds exactly the same as the initial {0,4,8} triad, but now "spelled" {0,8,16} in 24tET and described as an interval string using quarter tones, (8,8,8). If multiply-by-2 is all you do, you gain nothing - the two triads sound the same whether you claim to be in 12tET or 24tET - until a second augmented triad comes along that occupies 24tET's odd-numbered nodes, say it's spelled {9,17,1}.  At that point you have gained a trichord relationship with the voice-leading (spanning) vector [0300000303000] - and a hexachord ({0,1,8,9,16,17} w/string (1,7,1,7,1,7)) - not possible in 12tET, even though the generating "shapes" (augmented triads), considered individually, are indistinguishable. This is just the general idea. I used much more complex relationships in an experiment a while back.

Thursday, April 3, 2014

Partition Puzzle 3: A Homometric Partition Theorem

The following theorem is a corollary of the more intuitive "ICV summation" theorem for any three disjunct sets A,B,C which states
V(AUBUC) = V(A) + V(B) + V(C) + V(A,B) + V(A,C) + V(B,C).

Adding the stipulation of vector equivalence between A & B and requiring their cardinalities be less than half the modulus (so the cardinality of C is not empty) creates a tri-partition of any K-space, and the following theorem emerges.

The following proof comes from David Victor Feldman[1]. Using David Lewin's interval function, we are looking for IFUNC(A,C)=IFUNC(B,C). For clarity abbreviate IFUNC(X,Y)(i) as #XY, i.e., the number of intervals (i) up (clockwise) from an element in X to an element in Y. Display all the spanning possibilities for A,B,C as follows:
#AA  #AB  #AC
#BA  #BB  #BC
#CA  #CB  #CC
The sum of all nine entries in this matrix for any i, will be the corresponding i-entry in V(AUBUC); but since A and B have the same cardinality, we have four equal numbers: the sums of the first two rows and the sums of the first two columns. (For example, the sum of the first row must give the number of elements in A because the interval i up from an element in A must land in A, B, or C.) So in particular we have #AA + #AB + #AC = #AB + #BB + #CB. By elimination, #AA + #AC = #BB + #CB. Since we have stipulated that V(A)=V(B), we also have #AA=#BB, so we are left with #AC + #CB. Likewise, working from the equal sums of the first column and the second row, we get #CA = #BC. Thus #AC + #CA = #BC + #CB. Or, summarily for all values of i, V(A,C) = V(B,C).∎

Note that the theorem does not require A and B to be z-related (i.e., the relationship between A and B is not exclusively non-trivially homometric.) In a music theoretic context, A and B may be related by transposition and/or inversion (see Example 1 and 2 below) as well as by the z-relation (Example 3). But there are still surprises (Example 2). So we can identify the theorem as defining partitions that involve homometric pairs generally rather than being limited to the non-trivial case of the z-relation.

Example 1. In K12/12tET, A={C,E,G}, B={F#,A#,C#}. B=T6A so V(A)=V(B); C={D,D#,F,G#,A,B} and V(A,C) = V(B,C) = [0442440] as expected. But if instead B={G,B,D} and C={C#,D#,F,F#,G#,A,A#}, while V(A)=V(B), A & B are not disjunct & so A,B,C is not a partition of K. Calculating all values of i, we come out with V(A,C)=[0544323] and V(B,C)=[0543423] – close but no cigar.[2]

Example 2. Staying in K12/12tET, again let A={C,E,G}, but now B={F#,A,C#}. Now B=I1A so still V(A)=V(B); C={D,D#,F,G#,A#,B} and V(A,C)=V(B,C)=[0442431]. If B={E,G,B}, then C={C#,D,D#,F,F#,G#,A,A#}; V(A,C)=[ 0564333]=V(B,C) even though A and B are not disjunct! The theorem doesn't say this can't happen outside the theorem – which will become important as we go deeper. In this case, C is reflectively symmetric and therefore C's complement, the union of A & B, is also reflectively symmetric, and the symmetry is carried over in the spanning vectors, leading to future speculations about a role for neo-Riemannian transformations where L, P and R all result in reflectively symmetric tetrachords, as well as maximally even pitch structures (including  their twin "Euclidean rhythms"), and reflectively symmetric sets generally.

Example 3. Now, still in K12, let A={0,1,3,7}, B={10,11,2,4}, two AITs (z-related) whose union is not the octatonic this time. C={5,6,8,9} and V(A,C)=V(B,C)=[0232342]. But if instead B={0,1,4,6} so C={2,5,8,9,10,11}, again V(A)=V(B) but A and B are not disjunct and V(A,C)=[0463551] n.e. V(B,C)=[0453651].

The point of including the contrast between disjunct and conjunct A & B in the examples is to emphasize that the theorem identifies homometricity of pairs as a relationship of two sets to a third "reference" set, and not just a relationship between two sets. HPT won't work on just any random partition where  cardA=cardB.

Next in this thread, a transformation KmKn extending the HPT to virtually any homometric pair for any modulus.

[1] Private correspondence 19 March 2014.
[2] In comments to me just before I put this entry on line, David Feldman also noted the following:
All I can get now without disjointness is: V(A,C)-V(A,A∩B) =V(B,C)-V(B,A∩B)In Example 1, this explains the "close" in "close but no cigar" since a small A∩B will make for small V(A,A∩B) and V(B,A∩B).In Example 2, V({C,E,G},{E,G})=V({E,G,B},{E,G}) because the whole story on the left inverts to the story on the right. So V(A,A∩B) =V(B,A∩B)and the theorem (in the form V(A,C)-V(A,A∩B) =V(B,C)-V(B,A∩B) ) really *does* explain (and not merely not preclude) V(A,C) =V(B,C) in this instance.

Saturday, March 15, 2014

Partition Puzzle 2: Spanning Vectors

You will have to brace yourselves for this –
not because it is difficult to understand,
but because it is absolutely ridiculous:
All we do is draw little arrows
on a piece of paper –
that's all!
~ Richard Feynman
(QED: The Strange Theory of Light and Matter, 1985, p. 24)

~ David Lewin
(Generalized Musical Intervals and Transformations, 1987, Figure 0.1)

Now that I finally have my computer back from the shop and have restored or recreated most files from the defunct hard drive, I can jump back in to the partition puzzle.

A good place to start is with a thank you to Jeremiah Goyette for pointing out to me the mistake I made in the final example in my first partition puzzle blog entry. While repositioning a (2146) tetragon inscribed in K13, it came out as a (2155) tetragon, displacing one of the vertices by one click.  My enthusiasm for this neatly-fitting result convinced me there was no need to even consider the possibility of a clumsy error. But the blunder has turned out to be a reminder to me to look past a search for superficial symmetries into deeper sub-surface symmetries.

The main thing that came to mind was the basis for an article, "The T-hex Constellation" (JMT, Fall 1998, 42.2, pp. 207-16). The relevant page is reprinted here:



The idea that grabbed me after re-visiting this passage and, as usual, reading some Lewin[1] was a "ghost set" conjecture that has remained undeveloped in the back of my mind for years: Given two disjoint sets S and T that are related by V(S) = V(T), there exists some set Q such that V(S,Q) = V(T,Q).  And/or vice versa: if V(S,Q) = V(T,Q) then necessarily V(S) = V(T). And if a strong form of this conjecture were not true, then, given it does work in many specific cases, what are the further conditions that make it true in those cases?

This might be a useful alternative way of defining homometricity. Instead of only looking for identical ic counts within two separate objects S and T, it would be primarily a search for a "ghost" object Q under conditions C that defines a spanning  relationship (S-to-Q) ↔ (T-to-Q).

To clarify by example:

Musically, this would be like finding that the total voice-leading possibilities between chord S and chord Q are identical to those between chords Q and T. In fact, there are examples of this (albeit hypothetical – at this point I know of nowhere in the literature that a composer has actually used these directly). We already know that the all-interval tetrachords C-C#-D#-G and E-F#-A-A# are z-related. And since together these particular transpositions form the octatonic scale, the ghost set Q here ought to be the complement of the octatonic, the diminished-7th chord G#-B-D-F. And that's exactly the case:
Figure 1
Between S and Q there are four each ic1, ic2, ic4, ic5, and no instances of ic0, ic3 or ic6. And the same between T and Q. Summarizing this as an interval-class spanning vector relationship:

V(S,Q) = V(T,Q) = [0440440].
[NB! Unless noted otherwise, spanning vectors will include the cardinality of ic0. So in the usual 12tET chromatic, vectors will have seven places rather than six. Thus in the current example of AITs, not only V(S,Q) = [0440440] but also V(S) = V(T) = [4111111] (see article above). In this case S and T are disjunct (i.e., card(ic0) spanning S and T is 0), so, calculating V(S,T) = [0226222][1], we have one of the many possible "decompositions" of the octatonic set: V(octatonic) = V(SUT) = V(S)+V(T)+V(S,T) = 2[4111111]+[0226222] = [8448444]. A formal algebra for spanning vectors will be interesting to work out, but intuition with examples is enough to get by for now.]

Extending to any selection of four pitches from the octatonic, the partition principle for the above example results in the same ic spanning vector [0440440] ; for example, Figure 2 shows {dom7, dim7, halfdim7}, a quasi-tonal cover of the chromatic.
Figure 2
Again, V(S,Q) = V(T,Q) = [0440440]. This tidy factoid will not always be the case.

Returning to K13, Figure 3 shows one (now correct) version of the tri-partition of K13 by the two z-related sets S = {5,7,8,12} and T = {9,11,1,2} and the "ghost" set Q = K–(SUT) = {10,0,3,4,6}.

Figure 3

Figure 4 separates the three figures to show the n-gon "shape" and complete interval-class structure of each set.
Figure 4a                               Figure 4b                               Figure 4c

Correcting S meant losing a ghost set that was the maximally even 5-in-13 symmetry. Playing with various rotations (transpositions) and reflections (inversions) of S and T that leave them disjunct, it is now apparent that all possible shapes for Q are asymmetric. But this makes the possible partition solutions here much more tantalizing because a deeper symmetry begins to reveal itself in the spanning vectors. Taking the case in hand from Figure 4, we get
V(S,Q) = V(T,Q) = [0442352].
Holding T constant and rotating (transposing) S by –2, we get T = {3,5,6,10} resulting in Q = {0,4,7,8,12} with the string (14143). V(S) still equals V(T), but now
V(S,Q) = V(T,Q) = [0354224].
The "answer"to V(X,Q) has changed, but the relationship remains the same, suggesting that the equivalence per se is an invariant under certain (we know not yet what) conditions. One more test. What if we hold T constant again and this time reflect S (invert by I2) to {3,7,8,10} resulting in Q = {0,4,5,6,12} (string=(14116))? Of course V(S) = V(T) as usual, but this time
V(S,Q) = V(T,Q) = [0245432].
Again, the values of these spanning vectors have changed, but the relationship between the two is invariant.

Obviously, there's still a lot more ground to cover. What happens when S∩T≄∅? What about homometric triples, quadruples? Etc. Will the "ghost" turn out to be just another ignis fatuus?


[1] E.g., "Going even further, we may ask under what conditions among the four sets X1, Y1, X2, and Y2 we will have the relation IFUNC(X1,Y1) = IFUNC(X2,Y2).... This is all a vast open ground for mathematical and musical inquiry, even in atonal set-theory." (GMIT, p.103) The reader will note many of Lewin's ideas running through the threads here – way too many to sort out at this point.

[2] Calculating spanning vectors by hand is cumbersome and distracting. I've devised a simple spreadsheet "calculator" for quickly determining spanning vectors for any two sets in any K-space. I'll send this via email to anyone requesting it (at no charge), but you must have Microsoft Excel to use it. Send your request to: essaysandendnotes at icloud dot com.

Saturday, February 22, 2014

Thursday, February 13, 2014

Observations from Jon Wild on the Partition Puzzle

Many thanks to Jon Wild for the following e-mail. It was also posted on the SMT list on 2.10.14, but I wanted to copy it here in situ for reference & so it wouldn't get lost or forgotten.

* * *
Stephen Soderberg posted to propose the following puzzle regarding Z-related tetrachords in higher equal temperaments:

No one responded (at least not on-list, and there is no comment section on the blog) so I have dusted off some Z-sets from an old hard drive, and can offer the following (without even the hint of a claim to musical relevance):

Stephen investigated up to 24-tone equal temperament. Going higher, in 28-tone equal temperament we find there are three pairs of Z-related tetrachords. We can take one representative from each of the six set-classes, along with the maximally even set-class [0,7,14,21], to form the 28-tone aggregate--in fact we can do so in 416 distinct ways--so your hypothesis holds, in that case.

I don't have the data for 32-tone ET, but we can test other generalisations of your hypothesis, involving pc-sets larger than tetrachords:

Mod 24, there are 9 triples of Z-related heptachords. Of the 9, two can be packed into the aggregate alongside the maximally even set [0,8,16]. (Each of the two triples that works can be rearranged around [0,8,16] in eight inequivalent ways, so there are 16 solutions in all.) These have very much the same flavour as the partitionings on your blog. One such partitioning: {0,1,3,5,7,8,16} + {6,14,17,19,21,22,23} + {4,9,11,12,13,15,20} + {2,10,18}.

Mod 18, there is a triple of Z-related pentachords: [0,1,3,6,10], [0,1,4,7,9] and [0,2,3,6,11]. It would be nice if we could partition the 18-tone aggregate into one each of these, leaving just the maximally even set [0,6,12]. But we can't! There are 6 ways we can pack the three pentachords into the aggregate; each way, though, leaves an [0,3,6] uncovered. This remainder of [0,3,6] is suggestive in connection with the following case:

Mod 30, there are 1090 triples of Z-related nonachords. Of these 1090 triples, only 19 can be packed into the aggregate at all (i.e. regardless of what trichordal set they leave uncovered). Of these 19, none can be packed into the aggregate in a way that leaves uncovered a set whose primeform is [0,10,20]. But: seven triples can be packed into the aggregate leaving the set [0,5,10].

(Interpolating between the last two cases--18-tET leaving [0,3,6] and 30-tET leaving [0,5,10]--we could predict that in the mod 24 case above, it should also have been possible to pack Z-related heptachord triples leaving behind the set [0,4,8]. And sure enough this is possible, in plenty of ways. I bet there is a family of such solutions that exists for each ET cardinality of the form 6n (greater than 12), using three Z-related (2n-1)-chords and leaving a remainder of [0,n,2n].)

Here are some other case studies for you:

Mod 27, there are three Z-related triples of hexachords. Each triple can be packed into the maximally even set {0,1,3,4,6,7,9,10 ... 24,25} leaving behind the set {2,5,8,11,14,17,20,23}.

For example, the triple of prime forms {0,1,6,10,12,19}, {0,1,7,9,13,18}, and {0,2,8,9,14,18} can be combined as follows: {0,1,6,10,12,19} + {4,9,13,15,21,22} + {3,7,16,18,24,25}. (This is one of two ways--the other triples also have two or three ways each of being combined to form the same maximally even 18-out-of-27 set.)

Mod 28, there are 81 Z-related triples of octachords. Of these 81, only 12 can be packed into the aggregate at all, covering 24 of its 28 pitches. And none of the 12 leave an uncovered set whose primeform is the maximally even [0,7,14,21].

This is my favourite example: there is a quintuplet of Z-related hexachords in 31-tone equal temperament whose interval vectors consist solely of 1s--they are all-interval hexachords, expressing 15 interval classes in just six pitches. This set of 5 hexachords can be packed into the 31-tone aggregate leaving only one pitch uncovered. The odds that this is by chance are astronomical--there is some other principle at work, related to the observations Stephen has started to make, but I don't know what that principle is. I suspect that Z-related sets with flat or near-flat distribution of intervals--like these 31-tone hexachords and the familiar all-interval tetrachords--will generally work better in such tiling problems than those Z-related sets whose interval vectors are very unbalanced.

And now back to some lovely Schubert for my class tomorrow...

--Jon Wild, McGill University

Wednesday, February 5, 2014

Partition Puzzle

'No wonder kids grow up crazy. A cat's cradle is nothing but
a bunch of X's between somebody's hands, and little kids look
and look and look at all those X's ...'
'No damn cat, and no damn cradle.'
– Kurt Vonnegut, Cat's Cradle

To explain this partition puzzle (I know how to find the cats, but can I find cradles for all of them?), it's helpful to begin with a motivating example or two. First take a look at Table 1.

Table 1

This list of z-related[1] pairs of tetrads was extracted from the list I posted recently of the 1,591 tetrads from K4 through K24. Musicians can relate to the complete tetrad list in practical terms as either the complete tetrachord content in all harmonic spaces from the single tetrachord in the equal 4-division of the octave (4tET) through the 256 tetrachords in quartertone space (24tET), or all 4-onset rhythms possible in a single measure of 4 beats through a measure of 24 beats (disallowing rhythmic tuplets). I tend to think of it as an uninterpreted "event space" leaving it open to other applications both inside and outside the music domain.

Next take a look at this fairly simple diagram (Example 1) which represents the entry at the top of Table 1 as two tetragons inscribed in K8-space[2]:

Example 1

This is the first appearance of z-related sets in any K-space[3]. The box to the lower left indicates two "descriptions" – shape and content – of the figures inscribed in the K8-space. On the left are the interval strings for the two figures, (1214⤸ and (1331⤸ which describe the unique shapes of the inscribed polygons. All intervals in a string are measured clockwise. On the right in the box is the interval-class vector [2121] common to both strings. An interval class (ic) is defined as the shortest distance between two nodes, whether that is measured clockwise or counterclockwise. And the interval-class vector of any inscribed polygon describes the total ic content of the polygon. Examples 2a & 2b demonstrate the ic-vector equivalence of the two figures.

Example 2a: (1214⤸                                    Example 2b: (1331⤸
(ic content in both figures is [2121]:
two ic1's,one ic2, two ic3's & one ic4)

Example 1 is also the first appearance of z-related sets that can be explained by the Babbitt "hexachord theorem." Of course, the theorem does not only apply in K12-space where it was first observed. It  should be thought of as a set-complement theorem that applies in any K2n-space (i.e., any K-space with an even number of nodes). An informal generalized statement of the theorem might be:
Babbitt Complement Theorem. When you choose any n nodes from any K2n-space that define a structure S, their complement – the n remaining nodes – will define a structure T that has the same interval-class vector as S.
The two figures described by the two complementary sets of n nodes in K2n-space might be transformationally related by rotation (musical transposition) or reflection (musical inversion)[5]; but if they are not, they are said to be z-related. Example 3a shows (1124⤸↔(4211⤸ by reflection; Example 2 shows (2123⤸↔(2123⤸ by rotation (as well as reflection). (1133⤸ and (1214⤸ in Example 3c are not related by any (known) transformation, but because they are complements, by the theorem their ic-vectors are nevertheless identical – z-related.

Example 3a                         Example 3b                        Example 3c 

So far I have presented nothing new. It's been no more than a review, a generalization – to point to basic concepts beneath applications. Now, with one very slight adjustment in nomenclature, I can present the puzzle. The generalized hexachord theorem above is based on the idea of complementation which assumes a bifurcation – placing all the elements of a set into one or the other of  two baskets. The Babbitt Theorem for pairs of tetrads only applies in K8. But could it be that the Babbitt Complement Theorem is a special case of a more general partition theorem such that z-related tetrads appearing in K-spaces other than K8 can be arranged as a partition of the space in which they are found?

First, the simplest case. What happens if we double the size of the space in the previous example from K8 to K16? Obviously, any figure in K8 will appear as a congruence (simply multiplied by 2) in K16, and any z-relation in K8 will be carried over to K16. So: (1214⤸ → (2428⤸; (1331⤸ → (2662⤸; and (2428⤸ & (2662⤸ will be z-related (but only indirectly because of the Babbitt Theorem), sharing the same ic vector [02010201]. But looking back at Table 1, we see that there is also a new pair of z-related figures, (1357⤸ and (3418⤸, not congruent to any figure in K8. Inverting (3418⤸ to (1438⤸ and experimenting with the placement of both z-pairs in  K16, we discover (empirically) that we can partition K16 with its z-related tetrads (Example 4).[6]
Example 4

Now this is getting interesting. Tripling K8 to K24 and looking back at Table 1 again, we find K24 has exactly three pairs of z-related figures, and all of these taken together can partition K24 (Example 5).
Example 5

(363C⤸ & (3993⤸ are the result of tripling from K8, and (157B⤸ & (165C⤸ are new, but this partition brings in another player, the familiar pair of all-interval tetrads found in K12 appear doubled in K24: (4215⤸ → (842A⤸ & (2316⤸ → (462C⤸.[7]

But this is as far as you can go using the tetrad relationships in Table 1. For one thing, the only z-related tetrads in K12, the all-interval tetrad pair, can't partition K12. But this glitch actually opens up to an even more interesting possibility. As it happens, the well-known octatonic string in K12, (12121212⤸, acts just like the entire space in which it is embedded with respect to the Babbitt Complement Theorem (see "Z-Related Sets as Dual Inversions," PNM, 39.1 (1995), §3.18). Choose any 4-element substring in the octatonic, and its complement with respect to the octatonic will have the same ic vector. This includes the all-interval pair:

Example 6

The complement of the octatonic string is (3333⤸ – in 12tET, the diminished 7th chord – indicated in Example 6 as a gray square. So K12 can be partitioned by two z-related all-interval tetrads and the maximally even tetrad (3333⤸. This suggests a remote possibility that any K-space might be partitioned by combinations of z-related and maximally even sets. It becomes surprisingly less bizarre when we note how all the tetrads possible in K20 can be situated around a dilation of that same maximally even square:

Example 7

Actually, this might work if you consider the previous Examples 1, 4 and 5 to be z-sets situated around a maximally even set of order zero. Ah, but what about that one z-related structure in Table 1 that we've ignored – the pair in K13. Well, it works with a different max even set (32323⤸. Here it is:

And that accounts for all the z-related tetrad pairs listed in Table 1. Now it gets complicated.

[Correction & remarks coming soon]

To be continued.........


[1] While it is tempting here to point to the recent important (and surprising) music–crystallography connection noted by others in the music theory literature by replacing "z-related" with the much more descriptive "homometric" used in crystallography, graph theory & elsewhere, unfortunately "homometric" comes with its own set of baggage, not all of which do I understand adequately enough to reference with confidence. But the real problem that Forte, evidently unwittingly, set up by calling this phenomenon the "Z-relation" is that it immediately becomes confused with Zn, the set of all congruence classes of the integers Z for the relation congrunce mod n. This forces tortured locutions such as "the set of all Z-related sets in the set Zn." My solution here (which I remain unhappy with) is to keep the "z-relation" designation in its current meaning in music theory (but in an expanded sense and use) and refer to pitch–/rhythm– (event–) space as K–space or more specifically as Kn–space.  Kn–space can be represented visually as the 1-dimensional space defined by n nodes equally spaced around the circumference of a circle.   The nodes in Kn–space may be labelled, as in the venerable circle of fifths (C, G, D, ..., Bb, F, (C)), or unlabelled, as it is throughout this blog entry.

[2] vid. note [1]. For the curious: I'm using "K" for two personal reasons. First, a reference I once read (I believe it was by Nick Collins) referred to these as "Krenek circles" but I rather doubt Krenek was the first to use them in a music theory context. The other, more whimsical, reference is to the Greek κύκλος (kyklos) from Archimedes' last words to the Roman soldier who was about to kill him: "μή μου τοὺς κύκλους τάραττε" – Do not disturb my circles! (Probably apocryphal, but I like to believe it.)

[3] First used by Arthur Lindo Patterson to illustrate homometric structures (our z-related sets) in the phase problem in X-ray crystallography. [Cite: ______]

[4] For those who need an immediate "real" application in music, the diagram can be interpreted rhythmically this way:
Where the symbols "(" and "⤸" indicate that the measure can be "recycled" to begin on any of the eight notes, just as the same symbols were previously used to indicate the equivalence class of cyclically related permutations.

[5] – or dilation mod 2n (along with rotation to achieve a complement relationship), a kind of quasi-homothetic transformation that warps the K–space into itself. (Music's special case for dilation in 12tET is multiplication by 5 or 7 mod 12). But there is no need to introduce this complication here.

[6] NB: For all of these cases there is likely more than one way to partition any space with z-sets. In this first case, for example, the entire partition can be mirrored.

[7] A=10, B=11, C=12, etc.

Tuesday, January 14, 2014

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

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