20180902

The GAP Mined for Music

The previous post presented some introduction to (Balanced Incomplete) Block Designs with a simple musical application. It did not, however, provide much in the way of obtaining block designs in the first place, other than by using extant published material. It would be nice to find some software capable of producing block designs.

I've been aware of the GAP computer algebra software, and have even occasionally used it, for some years now but did not realise that it included software for block designs. Perhaps that should not come as a surprise as it is growing all the time.

It is free to download and install, is multi-platform and is fun to play with in any case. It's a command line console based system and therefore very useful for generating (and processing) text files. I'm certainly not going to say anything about it here - other than those bits of it I'll be using in this note. Don't ask me for any help on installation or use - I'll probably mislead you and, anyway, there are far more authoritative guides than I.

This post will present not just results of the use of GAP/DESIGN, but will attempt - at the risk of boring the already knowledgeable - to represent the voyage itself. Also note that I've taken a few liberties with the representation of GAP's typical output; which is a stream of unformatted text. There's certainly enough syntax to make the output completely unambiguous, but there's no syntactic sugar - it just flops out. So for clarity's sake I've tidied it up a bit.

The current (v4.9.2 at the time of writing) GAP release includes Soicher's DESIGN package (v1.6 @tow), but does not load it by default. For any particular GAP session you will therefore need to import the software with:

LoadPackage("design");

If the package loads successfully, then GAP reports 'true'. The method used by the package is based on what is known as the '*-construction' - far too abstruse to go into here but still available to the adventurous. Basically, one employs a slightly simpler t-(v-1,k-1,(k-t)λ) design to generate a bunch of t-(v,k,) designs, which will work (in our case, where we are interested in block sizes of 2, 3, 4 and 6) if n is the lowest common multiple of (k-t)C(2-t), (k-t)C(3-t), (k-t)C(4-t), (k-t)C(6-t), which is to say of k-2C0, k-2C1, k-2C2 and k-2C4 for each of the k with which we're treating. The DESIGN package will therefore require the use of an eleventh, not twelfth, order group which we will create with

G11:=CyclicGroup(IsPermGroup, 11);

The Two Tone Tour

First of all, we should verify the existence of the (12,2,1) design which essentially lists all 66 of the t=2 design's pitch class pairs. The above conditioning of n for k=2 requires only that it be the lowest common multiple of k-2C0 as it's the only one which can apply (yet). This clearly has n = 1 with a *-construction using 2-(11,1,0) - a trivial design used to generate a 2-(v=12,k=2,=1) design. We know that λ=1 and are required to provide this information by defining a record:

tlamb:=rec(t:=2, lambdas:=[1]);

which information is passed into another record specifying the desired block size and using the earlier defined permutation group:

basis:=rec(v:=12, blockSizes:=[2], tSubsetStructure:=tlamb, requiredAutSubgroup:=G11);

Once this basis is defined it may be used directly:

D:=BlockDesigns(basis);

upon which GAP emits the following list of length 1:

[ rec(autGroup:=Group([(1,2,3,4,5,6,7,8,9,10,11,12),(1,2)]),
blockNumbers:=[66], blockSizes:=[2],
blocks:=[ [1,2], [1,3], [1,4], [1,5], [1,6], [1,7], [1,8], [1,9], [1,10], [1,11], [1,12], [2,3], [2,4], [2,5], [2,6], [2,7], [2,8], [2,9], [2,10], [2,11], [2,12], [3,4], [3,5], [3,6], [3,7], [3,8], [3,9], [3,10], [3,11], [3,12], [4,5], [4,6], [4,7], [4,8], [4,9], [4,10], [4,11], [4,12], [5,6], [5,7], [5,8], [5,9], [5,10], [5,11], [5,12], [6,7], [6,8], [6,9], [6,10], [6,11], [6,12], [7,8], [7,9], [7,10], [7,11], [7,12], [8,9], [8,10], [8,11], [8,12], [9,10], [9,11], [9,12], [10,11], [10,12], [11,12] ],
isBinary:=true, isBlockDesign:=true, isSimple:=true, r:=11,
tSubsetStructure:=rec(lambdas:=[1], t:=2), v:=12) ]

And there you are. The information provided - as well as showing all possible pitch class pairs exactly once (λ=1) as requested - reports the number of blocks as (the expected) 66 and the r = 11, being the number of occurrences of each of the 12 pitch classes in all blocks (recall vr = bk, in this case 12×11 = 66×2).

Triadic Transitions

For k=3 block designs, which we used to construct a sequence of triads each carrying a common diad (to provide a binding musical integrity, some kind of voice-leading) between consecutive chords, we'll again need r=11 and v=12. The k=3 triadic requirement means we will expect 132/3 = 44 blocks. In this case n is required to be the lowest common multiple of both 1C0 and 1C1. As this is also just 1 there's no change there and remains unaffected. Setting up the required tSubsetStructure for a λ of 2, this time, and resetting basis to use the new record (otherwise it will - by default - remember the old value:

tlamb:=rec(t:=2, lambdas:=[2]);
basis:=rec(v:=12, blockSizes:=[3], tSubsetStructure:=tlamb, requiredAutSubgroup:=G11);

In fact you may skip the 'tlamb' construction and use its (now nameless) value directly, e.g:

basis:=rec(v:=12, blockSizes:=[3], tSubsetStructure:=rec(t:=2, lambdas:=[2]), requiredAutSubgroup:=G11);

Now you may generate the designs with the new basis:

D:=BlockDesigns(basis);

Alternatively you may skip the named 'basis' construction and use its value directly (although arguably with less clarity):

D:=BlockDesigns(rec(v:=12, blockSizes:=[3], tSubsetStructure:=rec(t:=2, lambdas:=[2]), requiredAutSubgroup:=G11));

The result is a list of five 2-(12,3,2) block designs, of which we'll display only the first and last:

[rec(autGroup:=Group([(1,11,10,9,8,7,6,5,4,3,2)]), blockNumbers:=[44], blockSizes:=[3],
blocks:=[[1,2,3], [1,2,11], [1,3,8], [1,4,7], [1,4,9], [1,5,7], [1,5,12], [1,6,9], [1,6,10], [1,8,12], [1,10,11], [2,3,4], [2,4,9], [2,5,8], [2,5,10], [2,6,8], [2,6,12], [2,7,10], [2,7,11], [2,9,12], [3,4,5], [3,5,10], [3,6,9], [3,6,11], [3,7,9], [3,7,12], [3,8,11], [3,10,12], [4,5,6], [4,6,11], [4,7,10], [4,8,10], [4,8,12], [4,11,12], [5,6,7], [5,8,11], [5,9,11], [5,9,12], [6,7,8], [6,10,12], [7,8,9], [7,11,12], [8,9,10], [9,10,11]], isBinary:=true, isBlockDesign:=true, isSimple:=true, r:=11, tSubsetStructure:=rec(lambdas:=[2], t:=2), v:=12),

… (three further records) …

rec(autGroup:=Group([(1,11,10,9,8,7,6,5,4,3,2)]), blockNumbers:=[44], blockSizes:=[3], blocks:=[[1,2,4], [1,2,6], [1,3,9], [1,3,11], [1,4,6], [1,5,11], [1,5,12], [1,7,8], [1,7,10], [1,8,12], [1,9,10], [2,3,5], [2,3,7], [2,4,10], [2,5,7], [2,6,12], [2,8,9], [2,8,11], [2,9,12], [2,10,11], [3,4,6], [3,4,8], [3,5,11], [3,6,8], [3,7,12], [3,9,10], [3,10,12], [4,5,7], [4,5,9], [4,7,9], [4,8,12], [4,10,11], [4,11,12], [5,6,8], [5,6,10], [5,8,10], [5,9,12], [6,7,9], [6,7,11], [6,9,11], [6,10,12], [7,8,10], [7,11,12], [8,9,11]], isBinary:=true, isBlockDesign:=true, isSimple:=true, r:=11, tSubsetStructure:=rec(lambdas:=[2], t:=2), v:=12)]

You may look for the usual things like Hamiltonian circuits.

Foursomes

Now we can get a little more adventurous and look for designs with tetrads (k=4), where the number of blocks in the design will be b = vr/k = 33. This will require n now being the lowest common multiple of 2C0, 2C1 and 2C2 which is again simply the value of 1 and thus we'll not be forced into more than the λ=r(k-1)/(v-1) = 3 that we wish for, which would require consequently larger b and r values (some simply impossible).

Upon entering into GAP the required calculation:

D:=BlockDesigns(rec(v:=12, blockSizes:=[4], tSubsetStructure:=rec(t:=2, lambdas:=[3]), requiredAutSubgroup:=G11));

We get a list of eight records of 2-(12,4,3) designs. Again, we'll show only the first and last:

[rec(autGroup:=Group([(1,9,6,3,11,8,5,2,10,7,4)]), blockNumbers:=[33], blockSizes:=[4], blocks:=[[1,2,4,5], [1,2,7,12], [1,2,9,10], [1,3,4,11], [1,3,5,8], [1,3,6,10], [1,4,8,10], [1,5,7,9], [1,6,7,12], [1,6,11,12], [1,8,9,11], [2,3,5,6], [2,3,8,12], [2,3,10,11], [2,4,6,9], [2,4,7,11], [2,5,9,11], [2,6,8,10], [2,7,8,12], [3,4,6,7], [3,4,9,12], [3,5,7,10], [3,7,9,11], [3,8,9,12], [4,5,7,8], [4,5,10,12], [4,6,8,11], [4,9,10,12], [5,6,8,9], [5,6,11,12], [5,10,11,12], [6,7,9,10], [7,8,10,11]], isBinary:=true, isBlockDesign:=true, isSimple:=true, r:=11, tSubsetStructure:=rec(lambdas:=[3], t:=2), v:=12),

… (six further records) …

rec(autGroup:=Group([(1,9,6,3,11,8,5,2,10,7,4)]), blockNumbers:=[33], blockSizes:=[4], blocks:=[[1,2,4,5], [1,2,6,8], [1,2,9,10], [1,3,4,11], [1,3,6,12], [1,3,7,8], [1,4,10,12], [1,5,6,10], [1,5,7,11], [1,7,9,12], [1,8,9,11], [2,3,5,6], [2,3,7,9], [2,3,10,11], [2,4,7,12], [2,4,8,9], [2,5,11,12], [2,6,7,11], [2,8,10,12], [3,4,6,7], [3,4,8,10], [3,5,8,12], [3,5,9,10], [3,9,11,12], [4,5,7,8], [4,5,9,11], [4,6,9,12], [4,6,10,11], [5,6,8,9], [5,7,10,12], [6,7,9,10], [6,8,11,12], [7,8,10,11]], isBinary:=true, isBlockDesign:=true, isSimple:=true, r:=11, tSubsetStructure:=rec(lambdas:=[3], t:=2), v:=12)]

Hexachords

The last designs we can attempt to find, without requiring large numbers of blocks, is the 22 block sized 2-(12,6,5) set of hexads. Remembering to check the lowest common multiple constraint, we see that when k=6, 4C0 = 1, 4C1 = 4, 4C2 = 6 and 4C4 = 1 yet again have us needing only an n=1. Thus we can expect the *-construction to work, as indeed it does.

D:=BlockDesigns(rec(v:=12, blockSizes:=[6], tSubsetStructure:=rec(t:=2, lambdas:=[5]), requiredAutSubgroup:=G11));

Yields a list of four 2-(12,6,5) designs.

[rec(autGroup:=Group([(1,11,10,9,8,7,6,5,4,3,2)]), blockNumbers:=[22], blockSizes:=[6],
blocks:=[[1,2,3,4,8,12], [1,2,3,7,11,12], [1,2,4,5,7,9], [1,2,4,6,9,10], [1,2,6,10,11,12], [1,3,4,6,8,11], [1,3,5,8,9,11], [1,3,6,7,9,10], [1,4,5,7,8,10], [1,5,6,7,8,12], [1,5,9,10,11,12], [2,3,4,5,9,12], [2,3,5,6,8,10], [2,3,5,7,10,11], [2,4,7,8,10,11], [2,5,6,8,9,11], [2,6,7,8,9,12], [3,4,5,6,10,12], [3,4,6,7,9,11], [3,7,8,9,10,12], [4,5,6,7,11,12], [4,8,9,10,11,12]],
isBinary:=true, isBlockDesign:=true, isSimple:=true, r:=11,
tSubsetStructure:=rec(lambdas:=[5], t:=2), v:=12),
rec(autGroup:=Group([(1,11,10,9,8,7,6,5,4,3,2)]), blockNumbers:=[22], blockSizes:=[6],
blocks:=[[1,2,3,4,7,12], [1,2,3,6,11,12], [1,2,4,6,8,9], [1,2,5,6,8,10], [1,2,5,10,11,12], [1,3,4,7,8,10], [1,3,5,6,9,10], [1,3,5,7,8,11], [1,4,5,7,9,11], [1,4,9,10,11,12], [1,6,7,8,9,12], [2,3,4,5,8,12], [2,3,5,7,9,10], [2,3,6,7,9,11], [2,4,5,8,9,11], [2,4,6,7,10,11], [2,7,8,9,10,12], [3,4,5,6,9,12], [3,4,6,8,10,11], [3,8,9,10,11,12], [4,5,6,7,10,12], [5,6,7,8,11,12]],
isBinary:=true, isBlockDesign:=true, isSimple:=true, r:=11,
tSubsetStructure:=rec(lambdas:=[5], t:=2), v:=12),
rec(autGroup:=Group([(1,5,8,2,3)(4,10,9,11,7),(1,4,9,10,8)(3,11,6,5,7)]), blockNumbers:=[22], blockSizes:=[6],
blocks:=[[1,2,3,5,6,8], [1,2,3,5,8,12], [1,2,4,5,7,11], [1,2,4,7,11,12], [1,2,4,8,9,10], [1,3,4,6,10,11], [1,3,6,10,11,12], [1,3,7,8,9,11], [1,4,8,9,10,12], [1,5,6,7,9,10], [1,5,6,7,9,12], [2,3,4,6,7,9], [2,3,4,6,9,12], [2,3,5,9,10,11], [2,5,9,10,11,12], [2,6,7,8,10,11], [2,6,7,8,10,12], [3,4,5,7,8,10], [3,4,5,7,10,12], [3,7,8,9,11,12], [4,5,6,8,9,11], [4,5,6,8,11,12]],
isBinary:=true, isBlockDesign:=true, isSimple:=true, r:=11,
tSubsetStructure:=rec(lambdas:=[5], t:=2), v:=12),
rec(autGroup:=Group([(2,3)(4,11)(5,6)(7,10),(2,3)(6,8)(7,12)(9,11),(1,3,2)(5,6,8)(7,10,12),(1,5,3)(4,9,12)(7,11,10),(1,2,3)(5,7,6,10,8,12)(9,11)]), blockNumbers:=[22], blockSizes:=[6],
blocks:=[[1,2,3,5,6,8], [1,2,3,7,10,12], [1,2,4,5,7,11], [1,2,4,8,9,10], [1,2,6,9,11,12], [1,3,4,5,9,12], [1,3,4,6,10,11], [1,3,7,8,9,11], [1,4,6,7,8,12], [1,5,6,7,9,10], [1,5,8,10,11,12], [2,3,4,6,7,9], [2,3,4,8,11,12], [2,3,5,9,10,11], [2,4,5,6,10,12], [2,5,7,8,9,12], [2,6,7,8,10,11], [3,4,5,7,8,10], [3,5,6,7,11,12], [3,6,8,9,10,12], [4,5,6,8,9,11], [4,7,9,10,11,12]],
isBinary:=true, isBlockDesign:=true, isSimple:=true, r:=11,
tSubsetStructure:=rec(lambdas:=[5], t:=2), v:=12)]

More Triads

We can present these block designs as 22 columns of 12 pitch classes, indicating presence or absence thereof with a blue ball. For example the fourth design would look like:

Fourth Block Design

Notice that, in deference to musicians, the blocks have been vertically flipped so that GAP's block design's set element labellings 1 … 12 read upwards from bottom to top and have simultaneously been re-labelled on the right with more familiar note names. Naturally, the corresponding pitch class numbers 0 … 11 may be read as starting from other than the conventional C.

What may be of some interest in this kind of block design is that it gives plenty of scope for ordering the blocks in such a way as to carry several pitch classes at once from one block to the next, were one minded to place the blocks in some 22 bar sequence. For example, there are 6C3 = 20 triads available from each hexad. GAP may be used to list them - for example the final design's first emitted block is [1,2,3,5,6,8] and we can get GAP to list all its 3-sets with:

T:=Combinations([1,2,3,5,6,8], 3);

And GAP obliges with the list of that hexad's 20 triads:

[ [1,2,3], [1,2,5], [1,2,6], [1,2,8], [1,3,5], [1,3,6], [1,3,8], [1,5,6], [1,5,8], [1,6,8], [2,3,5], [2,3,6], [2,3,8], [2,5,6], [2,5,8], [2,6,8], [3,5,6], [3,5,8], [3,6,8], [5,6,8] ]

If we pick another block, at random, out of that same design, say [2,4,5,6,10,12], we may list its triads:

T:=Combinations([2,4,5,6,10,12], 3);

And GAP provides:

[ [2,4,5], [2,4,6], [2,4,10], [2,4,12], [2,5,6], [2,5,10], [2,5,12], [2,6,10], [2,6,12], [2,10,12], [4,5,6], [4,5,10], [4,5,12], [4,6,10], [4,6,12], [4,10,12], [5,6,10], [5,6,12], [5,10,12], [6,10,12] ]

Visual inspection tells us that these two lists have only [2,5,6] in common, but GAP may be used to confirm this with

Intersection(Combinations([1,2,3,5,6,8], 3), Combinations([2,4,5,6,10,12], 3));

by emitting:

[ [2,5,6] ]

The DESIGN package presents what we need ideally suited for passing as arguments to GAP's more basic functions. For instance the aforementioned [1,2,3,5,6,8] and [2,4,5,6,10,12] are available to us directly from D as D[4].blocks[1] and D[4].blocks[15] and it's easy to see that we can find all common triads between each of the 22 hexads with a simple nested for loop:

for i in [1..21] do one:=Combinations(D[4].blocks[i], 3); for j in [i+1..22] do two:=Combinations(D[4].blocks[j], 3); Print(i, " - ", j, " : ", Intersection(one, two), "\n"); od; od;

And 21×22/2 = 231 lines of output are printed, almost all of which show exactly one triad common between each pair of hexads - excepting 11 cases where no triad is held in common. We can also discern that each of the remaining 220 common triads is distinct with no repeats. In fact all possible 12C3 = 12!/(9!3!) = 220 triads are accounted for (as common links between hexad pairs) in this structure. The 22 blocks may thus be represented as a 22 node graph wherein each node is a hexad with 20 triadic edges to other nodes. A complete 22 node graph would connect each node with its 21 neighbours. Our graph has, apparently, each node singling out one particular unloved neighbour. This latter property means that the nodes come in pairs because - for example - any node's one and only disconnected neighbour must be a node whose one and only disconnected neighbour must be that first node since it cannot be not-connected to a third, different, node.

Make GAP work for you

At this point it is worth defining our own GAP function to construct lists of node pairs connected by edges representing any commonly contained k-chords:

BlockLinks := function(des, k)
local blx, blc, lis, i, j, one, two, com;
blx := des.blocks;;
blc := des.blockNumbers[1];;
lis := [];;
for i in [1 .. blc-1] do
one := Combinations(blx[i], k);;
for j in [i+1 .. blc] do
two := Combinations(blx[j], k);;
com := Intersection(one, two);;
if Length(com) > 0 then Add(lis, [ i, j, com]);; fi;
od;
od;
return lis;
end;

By invoking this function in GAP with:

L43 := BlockLinks(D[4], 3);
Length(L43);

we can confirm that it generates a list with 220 members (the 11 'empties' have been filtered out), one of which is [1, 15, [[2,5,6]]], representing the fact that the first and fifteenth blocks in the fourth design each share the single common triad [2,5,6] - as noted above. Note that the items are no longer printed (one per line) with punctuating '-' and ':' marks as the output is now a proper GAP object.

Fourth Block Design reordered for Circuit

As this particular design, viewed as a graph of hexadic nodes and common-triadic edges between then is so well-connected, it's not at all difficult to find Hamiltonian Circuits. In fact the design as presented is almost such a circuit (i.e. from block 1 to block 2 via [1,2,3], from block 2 to block 3 via [1,2,5] … etc. One needs only to swap block 12 with 13 and block 21 with 22 to recover this design to the left.

The horizontal bars show the common triads linked across successive columns (vertically flipped as before), including the wraparound at the final column back to the first.

If we look at the third block design however, with a completely different set of 22 hexads -

L33 := BlockLinks(D[3], 3);
Length(L33);

We recover this time a list containing only 176 members. This time we can see that the inter-node triadic commonalities form a more complex network. Here is a 'bleeding chunk' of it, showing all non-empty triadic commonalities at node 14:


[1,14,[[2,3,5]]],
[2,14,[[2,3,5]]],
[3,14,[[2,5,11]]],
[5,14,[[2,9,10]]],
[6,14,[[3,10,11]]],
[7,14,[[3,10,11]]],
[8,14,[[3,9,11]]],
[10,14,[[5,9,10]]],
[12,14,[[2,3,9]]],
[13,14,[[2,3,9]]],
[14,15,[[2,5,9], [2,5,10], [2,5,11], [2,9,10], [2,9,11], [2,10,11], [5,9,10], [5,9,11], [5,10,11], [9,10,11]]],
[14,16,[[2,10,11]]],
[14,18,[[3,5,10]]],
[14,19,[[3,5,10]]],
[14,20,[[3,9,11]]],
[14,21,[[5,9,11]]],

We can see that not only is node 14 (corresponding to the hexad [2,3,5,9,10,11]) disconnected from five nodes instead of just one, it is connected to node 15 (hexad [2,5,9,10,11,12]) by ten common triads rather than just one. Furthermore, nodes 1 and 2 are connected to 14 by the same triad (as are nodes 6 and 7, 12 and 13 etc). Design 3 is clearly a very different musical animal to design 4.

Tetradic Bridges Across the Hexachords

We can use our homebrew function to look for common tetrad links between the hexads of the second design:

L24:=BlockLinks(D[2],4);
[[1,2,[[1,2,3,12]]],
[1,6,[[1,3,4,7]]],
[1,12,[[2,3,4,12]]],
[2,5,[[1,2,11,12]]],
[2,14,[[2,3,6,11]]],
[3,4,[[1,2,6,8]]],
[3,11,[[1,6,8,9]]],
[3,15,[[2,4,8,9]]],
[4,5,[[1,2,5,10]]],
[4,7,[[1,5,6,10]]],
[5,10,[[1,10,11,12]]],
[6,8,[[1,3,7,8]]],
[6,19,[[3,4,8,10]]],
[7,13,[[3,5,9,10]]],
[7,18,[[3,5,6,9]]],
[8,9,[[1,5,7,11]]],
[8,22,[[5,7,8,11]]],
[9,10,[[1,4,9,11]]],
[9,15,[[4,5,9,11]]],
[10,20,[[9,10,11,12]]],
[11,17,[[7,8,9,12]]],
[11,22,[[6,7,8,12]]],
[12,15,[[2,4,5,8]]],
[12,18,[[3,4,5,12]]],
[13,14,[[2,3,7,9]]],
[13,17,[[2,7,9,10]]],
[14,16,[[2,6,7,11]]],
[16,19,[[4,6,10,11]]],
[16,21,[[4,6,7,10]]],
[17,20,[[8,9,10,12]]],
[18,21,[[4,5,6,12]]],
[19,20,[[3,8,10,11]]],
[21,22,[[5,6,7,12]]]
]
Length(L24);
33

Second Block Design as (tetradically edged) Graph

The above GAP output looks reasonably promising for just 22 barsworth, and with three edges per node it seems worth presenting here, left, as a graph. We've distributed the 22 hexadic nodes evenly, in the design's order, circularly clockwise from the top. Then we've linked them by their common tetradic edges. There's no point in labelling anything yet.

This graph is connected enough to be worth running through Prof Dharwadker's Hamiltonian Circuit detection software

Second Block Design Reordered as (tetradically edged Circuit) Graph

The software finds eight circuits. Here is the fifth (clockwise through blocks 16 21 22 8 9 15 12 18 7 13 17 11 3 4 5 10 20 19 6 1 2 14 and back to 16 at top)

The light blue boxes carry the six pitch classes of the hexachord as a hexadecimal string where each of the design's block's set element value has been reduced by 1, to bring it into our more conventional modulo 12 territory. Thus block 16, at the top, originally presented as [2,4,6,7,10,11] is here notated as 13569A. The common tetrads between joined nodes are similarly hexadecimally reduced and lie midway along the edge adjoining the two nodes sharing the tetrad.

It has not escaped our attention that the remaining 11 non-circuit edges (i.e. those edges not on the circumference but crossing the circle) of the re-ordered block exhibit an unexpected symmetry along the diametrically dividing line situated from 4 to 15 on the 22 hour clock topped at 0 (or at roughly ten past two across to ten past eight on a 12 hour clock). This rather suggests that a musical composition might start on one of those nodes - it would then, halfway through the run, essentially reverse.

Second Block Design Reordered

The design looks like this, with the design's blocks reordered according to the discovered Hamiltonian circuit, and with the aforementioned symmetry point (originally block [1,4,9,10,11,12], now labelled as 0389AB) moved to the first place.

We can also rotate the graph to make its tetradic-link symmetry more plain as a north-south reflection. The leftmost, westernmost, 9 o'clockiest point corresponds to that new first block, and it thence clockwisely follows the new block order.

Second Block Design Graph Rotated

The Tetrads common to the successive Hexachords in the re-ordered Block Design #2

The Tetrads common to successive Hexachords

Common Pentads - A Bridge too far?

If we now have a look at common pentads between the hexads, by invoking BlockLinks(D[4], 5), we get a completely disconnected graph - there are no common pentads between any of the hexads. But if we try the third design we have a little more luck:

L35:=BlockLinks(D[3],5);
[[1,2,[[1,2,3,5,8]]],
[3,4,[[1,2,4,7,11]]],
[5,9,[[1,4,8,9,10]]],
[6,7,[[1,3,6,10,11]]],
[8,20,[[3,7,8,9,11]]],
[10,11,[[1,5,6,7,9]]],
[12,13,[[2,3,4,6,9]]],
[14,15,[[2,5,9,10,11]]],
[16,17,[[2,6,7,8,10]]],
[18,19,[[3,4,5,7,10]]],
[21,22,[[4,5,6,8,11]]]
]

But just not very much. One might expect that 5 is possibly a little too close to 6 for common PC sets in such a small population of 22 blocks. But remember that the initial purpose of block designs was to provide sufficiently large test environments for conducting experiments without introduction of accidental bias. One is quite free to bump up the λ and the r values (subject to those constraints between the parameters) and generate designs with large numbers of blocks, and which still give equal opportunity to all pitch classes and intervals.

So, musically speaking, there's an awful lot to play with here and GAP can help you research the features you may wish to examine. As for converting these designs and any derivatives or transformations thereof into actual music, well, you know what to do. At the risk of pointing out the obvious, all of the integers in these set representations are ranged from 1 to 12, so just subtract 1 from each to recover the musician's traditional PC modulo 12 notations - or just live with it and treat the 12 as a 0. Everything else is just transposition anyway.

Remember that block designs are not restricted to using 12-sets and there's no need to bind yourself inside a twelve-tone universe.

More GAP code

A modification of the BlockLinks function can also provide an adjacency matrix since it may as well be calculated at the same time as the common subsets. First of all, we provide an 'object labelling' function:

OrdList36 := function(lords)
  local s, l, i, u;

  s := [];;
  u := "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  if IsList(lords) then
    l := Length(lords);;
    if l > 0 then
      if IsInt(lords[1]) then
        for i in [1 .. l] do
          Add(s, u[lords[i]]);;
        od;
      else
        for i in [1 .. l] do
          Add(s, OrdList36(lords[i]));;
        od;
      fi;
    fi;
  fi;
  return s;
end;

This provides us with PC-Set friendly labels, allowing us to replace the rather bulky (and 1-based) set denotations such as [1,3,5,7,10,11] with a sugar-free (and 0-based, hex-encoded) label 02469A.

The new function, BlockDesignGraph, produces a record carrying node and edge counts and names using the friendlier labels as well as an adjacency matrix which may be used to find those Hamiltonian paths and circuits:

BlockDesignGraph := function(design, subsiz)
  local blx, blc, lis, i, j, k, len, one, two, com, mat;
  blx := design.blocks;;
  blc := design.blockNumbers[1];;
  mat := NullMat(blc, blc);
  lis := [];;
  for i in [1 .. blc-1] do
    one := Combinations(blx[i], subsiz);;
    for j in [i+1 .. blc] do
      two := Combinations(blx[j], subsiz);;
      com := Intersection(one, two);;
      len := Length(com);
      if len > 0 then
        for k in [1 .. len] do
          Add(lis, [ i, j, OrdList36(com)[k]]);;
        od;
        mat[i][j] := mat[i][j] + len;;
        mat[j][i] := mat[j][i] + len;;
      fi;
    od;
  od;
  return rec(nNames:= OrdList36(blx), nCount := Length(blx), eNames:=lis, eCount:=Length(lis), incidenceMatrix:=mat);
end;

20180815

Pitching Democracy

The term twelve tone music suggests we treat each of those tones equally to eliminate bias. But this does not limit us to any of the 836017[1] essential patterns of serial music's twelve tone rows, with their derivative inversions, retrogrades, retrograde-inversions and cyclic-shiftings, all regarded as equivalencies. There are numerous other ways of 'democratising' twelve elements, for example statistically rather than serially.

We could have equal numbers of instances of each of the twelve elements and throw them up into the air. The resultant scatter will be expected to be uniformly distributed. And very likely musically uninteresting. We need some way of introducing structure by building composite objects out of those elements, but without giving undue weight to any particular one of them.

… that all intervals are created equal

The next obvious candidate (many will argue it's actually the principal) is the interval, characterised as a set of pitch class pairs, a duple, pij ≝ {pipj}. We need hardly state explicitly that j ≠ i and pij ≡ pji (but there it is anyway). There are nC2 = n(n-1)/2 such pairs chooseable from n objects in general, so from 12 pitch classes (labelled 0 … 11) we have:

{0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,7}, {7,8}, {8,9}, {9,10}, {10,11}, {0,2}, {1,3}, {2,4}, {3,5}, {4,6}, {5,7}, {6,8}, {7,9}, {8,10}, {9,11}, {0,3}, {1,4}, {2,5}, {3,6}, {4,7}, {5,8}, {6,9}, {7,10}, {8,11}, {0,4}, {1,5}, {2,6}, {3,7}, {4,8}, {5,9}, {6,10}, {7,11}, {0,5}, {1,6}, {2,7}, {3,8}, {4,9}, {5,10}, {6,11}, {0,6}, {1,7}, {2,8}, {3,9}, {4,10}, {5,11}, {0,7}, {1,8}, {2,9}, {3,10}, {4,11}, {0,8}, {1,9}, {2,10}, {3,11}, {0,9}, {1,10}, {2,11}, {0,10}, {1,11}, {0,11}

This is a well-defined set of sets in that it comprises a complete accounting of all possible 2-sets contained within a 12-set. As such, it is a simple enough animal. But simple things are ofttimes just manifestations of something more complicated.

A Confederacy of Duples

This animal is also an instance of a more complex artifice comprising - more generally - 66 subsets of 2 elements each, drawn from a set of 12 elements, each of which appears 11 times and where each and every 2-form appears exactly 1 time.

These specifications - which will first seem a rather over-engineered-for-purpose definition - make it more than just a set of sets. This structure also happens to be, and is known as, a balanced incomplete block design. This one is specifically a 2-design and the above specifying quantities, or enumerations, are usually notated with the following letters (ordered as they're found within the above description):

  • b66 subsets …
  • k2 elements …
  • v12 elements …
  • r11 times …
  • t2-form …
  • λ1 time …

Hitherto we've used n to denote the size of the pitch class universe, and also k for the smaller sizes of pitch class sets used for scales or chords. Block (or t-) design combinatorics (for that is where we are now) continues to use k for the subset size, but uses v instead of n. The structure itself is notated as the 5-tuple (v,b,r,k,λ) - where the t is understood to be 2. Often it's just the triple (v,k,λ) when b and r are inferred from the specific construction.

It's important to be aware that t is not the same as k, though they have - in this case coincidentally - the same value of 2. The t refers to the size of the duple (the size of the pitch class pair, the abstract 2-form - represented by another 2-set - it's what this structure is 'about'). The k, on the other hand, refers to the size of the subsets containing it (or, in general, them). The above set of 2-sets, each in one to one correspondence with its 2-form, is the simplest, most transparent design one could have.

The above structure carries each of the 66 possible duples exactly once. If we wished to instantiate a piece of music from that, then what could we do with such a collection? Again, like the elements themselves (the pitch classes available in the simpler structure, the universal 12-set that we started with), we could maybe play the 66 dichords, or (admittedly rather tiny) scale patterns, in some order with some rhythm and with some dynamics.

Or we could decide we need more instances of the pairs, to give us a little more scope to play with. Such as two of each duple - we can't single any one of them out, so each duple should appear in equal quantity. Naturally this could mean just using two of these structures and we'd have 132 little musical objects to deploy in some interesting way.

Repackaging without Bias

However, we might notice that 3-sets can carry 3 duples (i.e. p1~p2, p2~p3, p3~p1) in one bag, as it were. So instead of toting around 132 bags we can manage with only a third of them - i.e. 44 (admittedly 50% bigger) bags. We can't toss just any old trio of elements into each bag (which we'll call a block from now on) but must arrange their contents in such a way as to ensure that exactly two instances of each of our 66 duples (t-forms) turn up altogether. In other words we must construct a design out of b=44 blocks of k=3-sets (drawn from our universe of the v=12 set) so that exactly λ=2 of each duple/interval appear in it. Thus the t-set is no longer explicitly visible, whereas the k-set remains very much so.

It should be relatively easy to see that, when forming an exhaustive b sized list of k-sized subsets of v elements, you'll need r = bk/v each of the elements to build it. We have seen that vr = 12×11 = 132 = 2×66 = kb. With 3-sets we can instead have 132 = 3×44 = kb. Which is an illustration of the invariance of vr = kb within such systems.

We note that there are 12C3 = 220 possible triples, which is 5 times as many as we want/need. So how do we go about gathering a valid collection of exhaustively and non-preferentially distributed embedded duples? We could start with the whole 220, list all the duples implied in each, and (very carefully) remove 176 triples carrying exactly 8 each of the 66 duples. Or find some other algorithm to start from the bottom up. But sometimes the simple answer is that we just find them in the literature[2].

Redistribution of Assets

Consider this set of (so far, magically generated) 44 3-sets, which happens to be such a (12,44,11,3,2) block design:

{0,1,3}, {1,2,4}, {2,3,5}, {3,4,6}, {4,5,7}, {5,6,8}, {6,7,9}, {7,8,10}, {0,8,9}, {1,9,10}, {0,2,10}, {4,5,9}, {5,6,10}, {0,6,7}, {1,7,8}, {2,8,9}, {3,9,10}, {0,4,10}, {0,1,5}, {1,2,6}, {2,3,7}, {3,4,8}, {2,6,8}, {3,7,9}, {4,8,10}, {0,5,9}, {1,6,10}, {0,2,7}, {1,3,8}, {2,4,9}, {3,5,10}, {0,4,6}, {1,5,7}, {7,10,11}, {0,8,11}, {1,9,11}, {2,10,11}, {0,3,11}, {1,4,11}, {2,5,11}, {3,6,11}, {4,7,11}, {5,8,11}, {6,9,11}

If you cared to, you could verify that the 11 instances of each of our 12 pitch classes are present. For example pitch class 3 turns up in {0,1,3}, {2,3,5}, {3,4,6}, {3,9,10}, {2,3,7}, {3,4,8}, {3,7,9}, {1,3,8}, {3,5,10}, {0,3,11} and {3,6,11}. You might also check that each of the 66 pitch class pairs turn up twice each, e.g. {4,8} ⊂ {3,4,8} and {4,8} ⊂ {4,8,10} but in no others.

Abstraction to Application

One moderately musically interesting result of this latter property (a consequence of λ=2) is that we may conceivably write a piece of music comprising a sequence of triads (the blocks) in which each triad leads to the next carrying a common interval with the third pitch guaranteed as changing. For example the two successive bars with the above {4,8} (conventionally enough taking PC4 as E and PC8 as G#) in common:

We may then choose the common pair {3,4} or {3,8} for the preceding bar's common interval connection, and either {8,10} or {4,10} for the following bar's. After electing {3,8} to the left (introducing PC3 = E♭) and {8,10} to the right (introducing PC10 = B♭) we'd get:

Now we're forced to complete the left hand bar with the only remaining triad containing {3,8} that we're assured we have by the design (i.e. {1,3,8}, introducing PC1 = C#) and also to complete the right hand bar as the only remaining triad containing {8,10}, which is {7,8,10} (bringing in a PC7 = G):

Here's what (a), (b) and (c) sound like:

At this point we can pick either of {1,3} or {1,8} to continue the leftward process (since by now we have consumed both {3,8}) and either of {7,8} or {7,10} for the rightward (likewise both {8,10}).

I.e. what remains is:

{0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,7}, {7,8}, {8,9}, {9,10}, {10,11}, {0,2}, {1,3}, {2,4}, {3,5}, {4,6}, {5,7}, {6,8}, {7,9}, {8,10}, {9,11}, {0,3}, {1,4}, {2,5}, {3,6}, {4,7}, {5,8}, {6,9}, {7,10}, {8,11}, {0,4}, {1,5}, {2,6}, {3,7}, {4,8}, {5,9}, {6,10}, {7,11}, {0,5}, {1,6}, {2,7}, {3,8}, {4,9}, {5,10}, {6,11}, {0,6}, {1,7}, {2,8}, {3,9}, {4,10}, {5,11}, {0,7}, {1,8}, {2,9}, {3,10}, {4,11}, {0,8}, {1,9}, {2,10}, {3,11}, {0,9}, {1,10}, {2,11}, {0,10}, {1,11}, {0,11}

{0,1,3}, {1,2,4}, {2,3,5}, {3,4,6}, {4,5,7}, {5,6,8}, {6,7,9}, {7,8,10}, {0,8,9}, {1,9,10}, {0,2,10}, {4,5,9}, {5,6,10}, {0,6,7}, {1,7,8}, {2,8,9}, {3,9,10}, {0,4,10}, {0,1,5}, {1,2,6}, {2,3,7}, {3,4,8}, {2,6,8}, {3,7,9}, {4,8,10}, {0,5,9}, {1,6,10}, {0,2,7}, {1,3,8}, {2,4,9}, {3,5,10}, {0,4,6}, {1,5,7}, {7,10,11}, {0,8,11}, {1,9,11}, {2,10,11}, {0,3,11}, {1,4,11}, {2,5,11}, {3,6,11}, {4,7,11}, {5,8,11}, {6,9,11}

The obvious question is whether or not we can continue in this fashion to consume all 44 triads exactly once without breaking the common duple rule tying successive bars together. I.e is there a Hamiltonian path, with the 3-sets regarded as the nodes of a graph? Or - even better - a Hamiltonian circuit in which the final, 44th, bar links neatly back to the 1st bar with a common duple.

Since at each stage of this construction we have two choices at both left and right edges, and bearing in mind that there are 44 3-sets to consume, along with 44 of the 66 duples (leaving 22 of them unemployed - one of the hazards of democracy?), it seems unlikely that the current example will succeed since it was begun somewhat arbitrarily, and grown via what amounts to a sequence of coin-tosses.

So, rather than (possibly) waste time working blindly, we can attempt to draw a graph of the design, with the 44 3-sets as nodes and the 66 duples as edges. Each edge will therefore connect two nodes (a direct consequence of λ=2) and each node will carry three edges (since each 3-set contains 3 2-sets and the 2-sets match the edges). With such a graph (although it's a bit of a mess) it may be easier to visualise a path or circuit which visits each (blue) node exactly once. We've emphasised the three edges we've used so far with three heavy reddish lines.

But visual path detection seems by no means such an easy task. It would be helpful if we could find some software to do this. It doesn't take long to dig up an algorithm from the early 2000s (thank you Ashay Dharwadker). All this particular piece of software requires is a text file containing an incidence matrix for the graph, which takes only minutes to prepare.

With our graph, the program produces 45 results almost instantly. Searching those results for circuits with the particular choices made above - perhaps not surprisingly - reveals nothing. However, the single circuit presented employs our last three bars (blocks {3,8,4} via {4,8} to {4,8,10} via {8,10} to {7,8,10}). Had we chosen {3,4} rather than the {3,8} we did, the previous bar (the first of four, above) would have been {3,4,6} instead of {3,1,8}, and we would at that point have remained on course - doubtless to hit the rocks not much later. But now we know better and the complete circuit is

{0,1,3}, {1,3,8}, {1,7,8}, {1,5,7}, {4,5,7}, {4,5,9}, {2,4,9}, {1,2,4}, {1,2,6}, {1,6,10}, {5,6,10}, {3,5,10}, {2,3,5}, {2,5,11}, {2,10,11}, {0,2,10}, {0,4,10}, {0,4,6}, {3,4,6}, {3,4,8}, {4,8,10}, {7,8,10}, {7,10,11}, {4,7,11}, {1,4,11}, {1,9,11}, {1,9,10}, {3,9,10}, {3,7,9}, {2,3,7}, {0,2,7}, {0,6,7}, {6,7,9}, {6,9,11}, {3,6,11}, {0,3,11}, {0,8,11}, {5,8,11}, {5,6,8}, {2,6,8}, {2,8,9}, {0,8,9}, {0,5,9}, {0,1,5}

Which, as you can see, cycles from the final {0,1,5} via a {0,1} to the initial {0,1,3} (not that {0,1,3} must be initial - we could now start anywhere).

In the following figure, we present the circuit - labeling the edges only - with the triads occupying 44 nodes as blue discs. We do not need to clutter-label the nodes as the three pitch classes within each disc simply comprise the union of the pitch class pairs on the large circle's arcs on either side of it. For example, right at the top we have a disc/node with {0,1} to its left and {1,3} to its right, so we know this block is {0,1,3}. Note that the third edge's (every disc supports three edges) label, i.e. {0,3}, can be found halfway along the line tracing off down and to the left towards block/disc {0,3,11}.

Placing edge labels automatically (halfway) may occasionally lead to confusion. Beware, for example, the {1,5} in proximity to the {1,3,8} node at the top. This may appear to suggest, erroneously, that pitch class 5 should be in that block. In fact that {1,5} labels an edge from two completely different nodes on either side and just happens to land inconveniently close by. It's true third edge's label, {3,8} is halfway along a line tracing to the south east.

Here is a simple musical manifestation of the circuit, along with a pair of audio files

The second playable example is a faster manifestation with tuned percussion and a bit of rhythmic interest (just not very much). It lasts longer only because it's played twice around the Hamiltonian circuit.

Note that the above block design - essentially the set of 44 3-sets, from which we have serialised the blocks in a sequence of our own choosing to satisfy some musical whim is only one of the 242995846[3] purported (12,44,11,3,2) block designs. One may apprehend the size of the solution space by considering the 22 unused edges criss-crossing the large circle above. There is no obvious pattern and one should not expect one. Indeed it would be a little unnerving to find one.

The Higher Strata

Other factorisations of the vr=bk invariant (in this case equal to 132) allow us to propose designs of 33 blocks of 4-sets (tetrachords or tetratonic scales/arpeggios), for example the following (12,33,11,4,3) design, where our 66 duples each turn up 3 times (there are more than 17 million[3] of these, this is just one of them):

{0,1,3,7}, {1,2,4,8}, {2,3,5,9}, {3,4,6,10}, {0,4,5,7}, {1,5,6,8}, {2,6,7,9}, {3,7,8,10}, {0,4,8,9}, {1,5,9,10}, {0,2,6,10}, {2,4,9,10}, {0,3,5,10}, {0,1,4,6}, {1,2,5,7}, {2,3,6,8}, {3,4,7,9}, {4,5,8,10}, {0,5,6,9}, {1,6,7,10}, {0,2,7,8}, {1,3,8,9}, {5,6,8,11}, {6,7,9,11}, {7,8,10,11}, {0,8,9,11}, {1,9,10,11}, {0,2,10,11}, {0,1,3,11}, {1,2,4,11}, {2,3,5,11}, {3,4,6,11}, {4,5,7,11}

There's another invariant of such systems, viz. λ(v-1) = r(k-1). The first has 1×(12-1) = 11×(2-1) and the last 5×(12-1) = 11×(6-1). You may wish to confirm this with the other two designs.

Designs comprising 22 blocks of 6-sets (hexachords and/or hexatonic arpeggios) exist. E.g. the (12,22,11,6,5) design where our 66 duples each turn up 5 times (1 of 11603[3] possible designs):

{0,2,3,4,8,10}, {0,1,3,4,5,9}, {1,2,4,5,6,10}, {0,2,3,5,6,7}, {1,3,4,6,7,8}, {2,4,5,7,8,9}, {3,5,6,8,9,10}, {0,4,6,7,9,10}, {0,1,5,7,8,10}, {0,1,2,6,8,9}, {1,2,3,7,9,10}, {1,5,6,7,9,11}, {2,6,7,8,10,11}, {0,3,7,8,9,11}, {1,4,8,9,10,11}, {0,2,5,9,10,11}, {0,1,3,6,10,11}, {0,1,2,4,7,11}, {1,2,3,5,8,11}, {2,3,4,6,9,11}, {3,4,5,7,10,11}, {0,4,5,6,8,11}

In a block design such as this, transitioning between blocks via duples would be modelled by a graph with the 22 blocks (nodes) and 165 (duples) edges, with each node carrying 6C2 = 15 edges.

At first glance a design using 5-sets, with pentatonics, seems impossible since k=5 doesn't divide evenly into v=12. But we may accomodate pentatonic designs by relaxing the vr=132 constraint (it must still equal bk though!). I.e. have r=55 of each pitch class turn up in a (rather larger) structure of b=132 k=5-sets with λ=20 instances each of our intervalic duples in a (12, 132, 55, 5, 20) design.

Realpolitik

We finally note here that - with these 2-designs - no particular pitch classes or intervals stand out against each other in the design. But particular musical applications of it may - for example by keeping 22 nominally equal citizens out of work as we did above. Other musical economies may be more successful in employing everyone. Additionally, in any application of a particular design, it will be the case that one (12,44,11,3,2) block design will draw attention to only 44 of the 220 possible triads mentioned above. And another will favour a different 44. It's fair(-ish) to say, then, that musical democracy extends upwards in the aggregations of all possible 2-designs, i.e. not simply any one of them. Naturally, you may actually democratise triples by building 3-designs, quadruples with 4-designs, etc. The problem with 'equal opportunities' for a design employing all 220 3-set citizens in equal numbers (via that design's λ value) is that no pre-singularity human being will be able to apprehend the structure. It's certainly not likely that even the 'mere' 44-ness presented here would be noticed as some kind of integrable musical idea - the 40 parts available to listeners of Spem In Alium notwithstanding (thanks due to Hans Jacobi for this thought).

I'm extremely grateful to Tom Johnson, with whom I spent a pleasant and mathematically engrossing couple of hours at the end of June, 2018. For it was he who introduced me to the world of block designs, both at his fortress of solfège-étude and via his book[4]. The field presents a vast source of ideas, with which I'm now mildly obsessed.

[1] Combinatorial problems in the theory of music, R C Read, Elsevier Discrete Mathematics 1997, table 2 page 547.

[2] A Survey of Resolvable Solutions of Balanced Incomplete Block Designs, Kageyama Sanpei, Longman Int Stat Rev Vol 40#3 1972, table on page 270.

[3] Handbook of Combinatorial Designs, IIed, Charles J Colbourn and Jeffrey H Dinitz, CRC Press 2010, page 37.

[4] Other Harmony - beyond tonal and atonal, Tom Johnson, Editions 75 2014, block designs page 191.

20180705

All The Intervals

The so-called 'all interval tetrachord' is not exactly news to musicians, although that this news is only dozens, and not hundreds, of years old is possibly surprising. Its (or more accurately their, since there's more than one) 'interestingness' having been exposed only (relatively) recently is due to pitch class set theorists who invented the 'interval-class-vector' (scare-quotes because of course it's in only the loosest, most informal, mathematically-anathematical, way any kind of a vector). This intervalency is the thing which usually turns up in PC set theory as a comma separated list of numbers between a pair of angled brackets, such as <2,5,4,3,6,1>. It lists - in order - the frequency of occurence of differences between each pair of pitch classes in the set it's being used to characterise, where the differences range from 1 to 6 in the 12 tone system (because the shortest distance between any two 'hour points' on a clock is always going to be between 1 and 6).

History

Although it would have easily been possible for any (say) 15th century musician to notice that the tetrad comprising (say) the pitches B, C, E♭ and F carried (between B and C, B and E♭, B and F, C and E♭, C and F, E♭ and F) respective separations of 1, 4, 6, 3, 5, 2 semitones - which is to say exactly one of each possible separation between any pair of notes, it's not clear that this would have been considered in any way remarkable.

Indeed there seems little evidence that musicians - or even mathematicians - were considerate of the number of possible tetrachords (or chords of any size) possible within a universe of twelve pitches before the middle of the 19th century. Luigi Verdi's survey article of proto, pre-USAnian if you will, pitch class set theories "The History of Set Theory from a European point of view" is well worth a read in this regard. There are, by the way, 43 such tetrachords and only 4 of these have this property.

Note that when we say 43, it depends on what you are counting - in this case it's all of the distinct shapes, their reflections, and homometries. If you ignore reflections (i.e. if you accept the essential identity of congruent shapes regardless of mirroring) it drops to 29 since 15 of the quadrilaterals have (at least) bilateral symmetry, and the remaining 28 turn up as 14 asymmetric mirror-image pairs. If, further, you ignore homometries (differently-shaped tetrads with the same intervalency) it drops to 28 because 2 of those 14 pairs of mutually inversional tetrads - which happen to be the subject of this very post - carry the same interval-class distribution, which is to say one instance of each interval class 1 to 6.

The 'classic' case

The Four All-Interval Tetratonic sets out of 12
1 3 2 6 2 3 1 6 1 2 4 5 4 2 1 5
The above four PC sets applied as chords (with F ≡ Pitch Class 0)
PC Sets 4-Z15 and 4-Z29

1326 chord (rooted on 440Hz)

1245 chord (rooted on 440Hz)

Wherefore art thou audio?

So what exactly is so remarkable about these chords anyway? They don't sound all that great, especially when instantiated in their most compacted forms as a Fortean Prime Form Cluster (4-Z15 ≡ {0, 1, 4, 6} and 4-Z29 ≡ {0, 1, 3, 7}). One may, reasonably easily, see in the second of these forms certain jazziness since the root, minor 3rd, 5th and (the '1' being bumped up an octave) the minor 9th are applicable (sans the 7th). And an inversion of the first set (subtracting 1 from each element makes its second member a new root) {11, 0, 3, 5} carries a minor 3rd, a 4th and a major 7th in plain sight, as it were.

A pair of jazzy applications of 4-Z29A and 4Z-15A
A Displacement and an Inversion

But mainly the interest is in its very rarity as a musical (or geometric) object, in that out of all possible PC sets (351 distinct polygonal shapes, 223 distinct polygonal congruences, 200 distinct polygonal homometries) that one may pull out of a 12 pitch class universe, only these 4 (2 if you equivalence reflections, 1 if you equivalence intervalencies) have the property that the frequency distribution (or, more simply, 'counts') of differences between every single pair of pitch classes in the set occur exactly once.

Actually, the term 'all-interval set' is rather a weak description of the kind of object we're considering since, with enough pitch class pairs to play with (i.e. given sufficiently large k for a particular N), it's almost impossible to avoid all interval (classes) turning up between them. A better term would bring out not only the completeness of the coverage but also its parsimony, i.e. with exactly one instance of each. It's that property which makes these objects interesting, and this term doesn't really do it justice. The closest we seem to have is from Gamer and Wilson, in 2003, who recognise and define "a difference set (modulo n) to be a set of distinct integers c1, …, ck (modulo n) for which the differences ci − cj (for ij) include each non-zero integer (modulo n) exactly once" - but these are not the words you are looking for. Combinatorial Mathematics has the term "planar difference set", but this terminology would likely be completely opaque to a musician.

Such a property cannot simply happen for any set. Firstly, the things being counted are difference classes (i.e. the smaller of the two values |ci-cj| and N-|ci-cj| separating numbers ci and cj on an N-houred clock) between pairs of integers (ci, cj in the range 0 … N-1) drawn from the finite set N. In the above example, N is of course 12 and only (absolute) differences of 1 to 6 may turn up. In general, the number of possible values one may have for differences is N/2 for even N and (N-1)/2 for odd N. For instance, when N = 13 the differences from the 'top of the clock, at 0 [or any multiple of 13]' range from 1 - 0 to 6 - 0 clockwise, then 7 - 0 (having passed the halfway point of 6½) is the same distance or separation as 13 - 7 = 6; 8 - 0 is the same separation as 13 - 8 = 5, etc.

Secondly, the number of interval classes is not arbitrary. A set containing k pitch classes (i.e. a set Pk = { c1, c2, c3, … ck-1, ck }) can carry only k(k-1)/2 - a triangular number - pitch class differences |ci - cj| (i ≠ j). Thus if the distribution of these k(k-1)/2 differences is to be a k(k-1)/2 length list of 'all-exactly' 1s, it's clear that the only tonalities which can possibly carry these objects are modelled by 2, 3, 6, 7, 12, 13, 20, 21, 30, 31, etc where the corresponding all-interval k-sets are of dichords in 2 & 3, trichords in 6 & 7, tetrachords in 12 & 13, pentachords in 20 & 21, hexachords in 30 & 31 etc.

As it happens, 13 has a similar quartet:

The Four All-Interval Tetratonic sets out of 13
1 3 2 7 2 3 1 7 2 1 4 6 4 1 2 6

It's evident that the shapes are pretty similar to those found in 12. That they are in adjacent tonalities does not necessarily mean that 'all interval' shapes would be expected to be broadly similar.

Interval Strings

The white numerical annotations (along the polygonal edges) are simply the number of skips between each pitch class in the ordered set (the polygonal vertices). This interval skip, or interval string notation is a vastly superior method of denoting pitch class sets, far out-transparenting the structure-hiding and equivalence-hiding opacity of listing pitch class numbers between braces - which should only ever be needed when you're on the verge of committing music to paper (performers do - after all - usually need to know what actual notes to play).

Its superiority as an 'interval showcase' is achieved by first tabulating all of its k(k-1) substrings (k of length 1, k of length 2, k of length 3 … k of length k-2 and k of length k-1), e.g. for one of the modes of 2317, such as 1723 (a mode being just a rotation of the set's polygonal representation within its 'N hour clock' space, keeping its top, 'noon', slot occupied):

substrings of '1723' of length
123
117172
772723
223317
331231

Then we just 'sum' each substring (by adding up its digits):

substring sums
1810
7912
2511
346

It is then evident by inspection that each interval in the set 1, 2, … 10, 11, 12 turns up exactly once. You may satisfy yourself that this works also for the pattern 2146 and any of its rotations. Pick any other interval string consistent with 13 and you will easily see either missing or duplicated intervals in the sum table.

As a matter of (possibly minor - since the tonal universes are so small) interest, the tonal space 6 - in which the all-interval sets are perforce triads - is the only space where an all-interval set could be the same size as its complementary set. As it happens there are a pair of such sets, 132 and 123 (interval string-wise) which are indeed not only self-inverse but self-complementary. If you insist on explicit Pitch Class Set representations (where their inversional relationships are much less immediately evident), they are {0,1,4} and {0,1,3}. The heptaphonic space 7 also admits of a pair of all-interval sets 142 and 124 ({0,1,5} and {0,1,3}) - also clearly (from their interval string representations) mutual inverses.

More solutions

The next possible tonality where we could find an all-interval set would be where the triangular number is 10 (where k = 5), which would have to be half the number of possible interval classes carried by it (i.e. where N = 20 or 21). But it turns out that there are no such sets to be found in 20. There is, however a single pair of mutually inverse 5-sets in 21 and it is 2513A (and its inverse 3152A), in interval-string denotation (where 'A' stands for an interval of 10). These are PC sets {0, 2, 7, 8, 11} and {0, 3, 4, 9, 11} in what would be their prime form, had Forte considered tonalities other than dodecaphonic, with a corresponding intervalency (interval-vector »choke«) of <1,1,1,1,1,1,1,1,1,1>. We can draw their polygons, but cannot reasonably represent them on a musical staff without use of microtonal notations.

The only pair of all-interval pentachords in 21ville
2 5 1 3 A 3 1 5 2 A

By now, we can see a definite 'meat cleaver' shape common to many of these polygons (the triangles from 6 and 7, being so geometrically limited, could be said to resemble either 4-Z15 or 4-Z29).

Next up would be 30, but again there are no sets to be found. This is somewhat over-compensated for in 31 where we jump to 5 homometric pairs - 13278A and 87231A, 47215C and 51274C, 12546D and 64521D, 17324E and 42371E, and finally 13625E and 52631E. Here they are (though this time we'll place the inversions underneath rather than to the right), each carrying exactly one instance of interval classes 1 to 15:

Five pairs of all-interval hexachords in 31ville
1 3 2 7 8 A 8 7 2 3 1 A 4 7 2 1 5 C 5 1 2 7 4 C 1 2 5 4 6 D 6 4 5 2 1 D 1 3 6 2 5 E 5 2 6 3 1 E 1 7 3 2 4 E 4 2 3 7 1 E

13625E hexachord (rooted on 440Hz)

17324E hexachord (rooted on 440Hz)

12546D hexachord (rooted on 440Hz)

47215C hexachord (rooted on 440Hz)

13278A hexachord (rooted on 440Hz)

The polygons are ordered in, again, what would be their Fortean prime forms; i.e. interval strings are descending reverse alphabetically ordered horizontally (which is, essentially, how prime form is calculated) and vertically (the upper reverse-sorting before its corresponding lower inversion). Note that by 'reverse alphabetically' we mean the reversed strings are ordered descendingly. Blame Forte.

It is the author's fancy that the meat cleaver remains visible in one of these pairs.

Systematic Solutions

Jedrzejewski and Johnson's useful 2013 paper, The Structure of Z-Related Sets, presents polynomials capable of representing both pitch class sets and their consequent intervalic distributions. These derive from the realm of crystallography and Patterson Functions. Briefly, it means that a pitch class set {p1, p2, … pk-1, pk} - as usual of size k and drawn from a tonality of order n - and its inversion may be represented by a polynomial in x:

P(x; k, n) = xp1 + xp2 + … + xpk-1 + xpk

P-1(x; k, n) = P(x-1; k, n) = x-p1 + x-p2 + … + x-pk-1 + x-pk

where, without loss of generality, 0 ≤ p1 < p2 < … pk-1 < pk < n are the k pitch classes in the set and where the consequent interval distribution between those pairs of pitch classes is measured as the coefficients of the k(k-1) powers of x in the expression P(x; k, n)P-1(x; k, n). Note that all exponents of x are taken modulo n. Thus x-p2, for example, may be rewritten as xn-p2 to regain positive exponents.

In our particular case we seek pitch class sets which carry exactly one instance of each interval from 1 to n-1. For this purpose we don't particularly care whether or not the set is in prime form (since we can always turn it into its prime form after we have found it) and so we might as well fix the first two pitch classes as 0 and 1 - or in other words have our sets be at least in normal form (with pitch class 0 at the beginning) and with the shortest interval of 1 - between those two pitch classes - right at the beginning of the set. Thus we seek those particular P(x; k, n) looking like:

1 + x + xp3 + … + xpk-1 + xpk

with 3 ≤ p3 < … pk-1 < pk < n. We can assume p3 > 2 since we've already accounted for the interval of 1 which would otherwise appear twice due to x2 and x. And of course k fixes n (as either the even k(k-1) or the odd k(k-1) + 1) because we're looking specifically for the resultant interval polynomial P(x; k, n)P(x-1; k, n)

= (1 + x + xp3 + … + xpk-1 + xpk)(1 + x-1 + x-p3 + … + x-pk-1 + x-pk)
= (1 + x-1 + x-p3 + … + x-pk-1 + x-pk) + (x + 1 + x1-p3 + … + x1-pk-1 + x1-pk)
+ (xp3 + xp3-1 + 1 + … + xp3-pk-1 + xp3-pk) + … + (xpk + xpk-1 + xpk-p3 + … + xpk-pk-1 + 1)

which we would wish to have equal k + x + x2 + x3 + x4 + … + x-3 + x-2 + x-1 by finding the right k-2 values for the remaining pi

We note that when k = 7, the consequent embedding tonality will be either 42 or 43. All-interval sets from the latter would, one supposes, be especially interesting to fans of Harry Partch.

Here are the solutions we get for k = 3 to 9. The pi are the pitch classes in the set and the iString column presents the interval string representation of the set (letters A-Z representing intervals of 10 to 35) from which one may readily recover prime forms by rotating the largest letters to the end of the string, and thence unpacking into the explicit set, if desired.

k = 3, n = 6 k = 3, n = 7
p1 p2 p3 p4 p5 p6 p7 p8 p9 iString p1 p2 p3 p4 p5 p6 p7 p8 p9 iString
0 1 3   123 0 1 3   124
0 1 4   132 0 1 5   142
k = 4, n = 12 k = 4, n = 13
p1 p2 p3 p4 p5 p6 p7 p8 p9 iString p1 p2 p3 p4 p5 p6 p7 p8 p9 iString
0 1 3 7   1245 0 1 3 9   1264
0 1 4 6   1326 0 1 4 6   1327
0 1 6 10   1542 0 1 5 11   1462
0 1 7 9   1623 0 1 8 10   1723
k = 5, n = 20 k = 5, n = 21
p1 p2 p3 p4 p5 p6 p7 p8 p9 iString
no solutions 0 1 4 14 16   13A25
  0 1 6 8 18   152A3
k = 6, n = 30 k = 6, n = 31
p1 p2 p3 p4 p5 p6 p7 p8 p9 iString
no solutions 0 1 3 8 12 18   12546D
  0 1 3 10 14 26   1274C5
  0 1 4 6 13 21   13278A
  0 1 4 10 12 17   13625E
  0 1 6 18 22 29   15C472
  0 1 8 11 13 17   17324E
  0 1 11 19 26 28   1A8723
  0 1 14 20 24 29   1D6452
  0 1 15 19 21 24   1E4237
  0 1 15 20 22 28   1E5263
k = 7, n = 42 k = 7, n = 43
no solutions no solutions
k = 8, n = 56 k = 8, n = 57
p1 p2 p3 p4 p5 p6 p7 p8 p9 iString
no solutions 0 1 3 13 32 36 43 52   12AJ4795
  0 1 4 9 20 22 34 51   135B2CH6
  0 1 4 12 14 30 37 52   1382G7F5
  0 1 5 7 17 35 38 49   142AI3B8
  0 1 5 27 34 37 43 45   14M7362C
  0 1 6 15 22 26 45 55   15974JA2
  0 1 6 21 28 44 46 54   15F7G283
  0 1 7 19 23 44 47 49   16C4L328
  0 1 7 24 36 38 49 54   16HC2B53
  0 1 9 11 14 35 39 51   1823L4C6
  0 1 9 20 23 41 51 53   18B3IA24
  0 1 13 15 21 24 31 53   1C2637M4
k = 9, n = 72 k = 9, n = 73
p1 p2 p3 p4 p5 p6 p7 p8 p9 iString
no solutions 0 1 3 7 15 31 36 54 63 1248G5I9A
  0 1 5 12 18 21 49 51 59 14763S28E
  0 1 7 11 35 48 51 53 65 164OD32C8
  0 1 9 21 23 26 39 63 67 18C23DO46
  0 1 11 20 38 43 59 67 71 1A9I5G842
  0 1 12 20 26 30 33 35 57 1B86432MG
  0 1 15 23 25 53 56 62 69 1E82S3674
  0 1 17 39 41 44 48 54 62 1GM23468B

Odd tonalities appear to be favoured systems for all-interval chords. Except for the absence of solutions for 43 - almost as if it had been singled out. Also, it has not escaped our notice that the above solution for 21 appears to violate the Prime Power Conjecture. Answers on a postcard, please, as to why it does not.

We can just squeeze out one more table for the 6 (inversional) pairs of all-interval sets using 10 pitch classes, in a 91 tonality (there are none in 90). This now breaks at least one 'limit' (albeit an artificial one of our own making), which is to say the one involved in displaying the PC set's interval string. The alphabet is no longer big enough to carry one of the intervals and consequently an asterisk (*) is employed to represent an interval of 36 - just over the range provided by a letter Z.

k = 10, n = 91
p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 iString
0139274956617781126IM75G4A
01413243038404573139B6825SI
0157273544677780142K89NA3B
0158182029435965143A29EG6Q
01610232634415355154D387C2*
01716275660687073169BT4823I
0111153136436583891A4G57MI62
0112152548576585871B3AN98K24
0119222432366576851I3284TB96
0119475254626879881IS5286B93
0127334963727484871Q6GE92A34
0137395158666982861*2C783D45