20200228

The Unreasonable Ubiquity of Dodecatonicity

Symmetries

The symmetries of the dodecagon, the regular 12-sided polygon used in models of Pitch Class Set Theory, are well known. Viewed as a dihedral group (of order 24), it has a class index

$$P_{D_{12}}(\textbf{x}) = \frac{1}{24} \left( x_1^{12} + 7 x_2^6 + 2 x_3^4 + 2 x_4^3 + 2 x_6^2 + 4 x_{12} + 6 x_1^2 x_2^5 \right)$$

which sheds some light upon the 2, 3, 4 and 6-fold symmetries of 12-sided figures. This can be used to enumerate all the essentially different (equivalent under rotations and reflections) shapes of all (mostly) irregular polygons of all orders - from 0 to 12 - inscribable within it. One simply replaces every $x_i$ with $(1 + t^i)$ in the above (Pólya Enumeration) to recover the following degree 12 polynomial in t:

$$E_{12}(t) = 1 + t + 6 t^2 + 12 t^3 + 29 t^4 + 38 t^5 + 50 t^6 + 38 t^7 + 29 t^8 + 12 t^9 + 6 t^{10} + t^{11} + t^{12}$$

which counts the number of essentially different k-gonal shapes - as the coefficient of tk - corresponding to all 224 Pitch Class Sets of different sizes available to Twelve Tone Music.

If you count non-symmetric shapes twice (i.e. as distinct from their reflections) rather than just once, the Cyclic Group polynomial enumerator - $1 + t + 6 t^2 + 19 t^3 + 43 t^4 + 66 t^5 + 80 t^6 + 66 t^7 + 43 t^8 + 19 t^9 + 6 t^{10} + t^{11} + t^{12}$ - is the appropriate one to use. This aggregates 352 distinct shapes (evaluate the polynomial at t = 1). Because it counts mirror-pairs (musically inverted PC sets) as distinct, this enumeration reveals that there are (352 - 224) = 128 pairs of non-symmetric shapes and 352 - 2 × 128 = 96 symmetric ones.

So far, so standard (this blog also catalogues them all here).

Most of these tk coefficients are rather haphazard (like, say, 29 and 38) and have no particularly friendly relations with the polygon they inhabit - rather to be expected. However, we see that the number of 3-sided shapes is 12, a number very friendly indeed to the enclosing dodecagon. It means that there's a possibility that all the different 3-sided shapes - and here they all are - might be enticed to exactly fit, four at a time, into three separate dodecagons.

Symmetric 3-sets
(equilateral and isosceles triangles)
Asymmetric 3-sets
(scalene triangles)
The 12 Dihedrally Equivalent PC Sets

Set Coverings

Note that the coefficient 6 (of t2) is also '12 friendly'. But tilt and move them as you will, it's impossible to fit the 6 different 'diangles' into one dodecagon, so that each occupies a different dodecagonal vertex pair. It's not possible to cover (or partition) the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} with 6 non-intersecting 2-sets where each such 2-set represents each of the six possible differences (on the dodecagon, i.e. modulo 12 differences) between the 12-set's points.

⇐?
12-Tone Interval Classes cannot cover the 12-Set

Octatonality

If we drop back to a tonality in which only 8 Pitch Classes are available, the Class Index of this system is

$$P_{D_{8}}(\textbf{x}) = \frac{1}{16} \left( x_1^8 + 4 x_1^2 x_2^3 + 5 x_2^4 + 2 x_4^2 + 4 x_8 \right)$$

we find its catalogue of (30) essentially different sub-polygons is enumerated by

$$E_{8}(t) = 1 + t + 4 t^2 + 5 t^3 + 8 t^4 + 5 t^5 + 4 t^6 + t^7 + t^8$$

One notices that the t2 term has coefficient 4, indicating that octatonicity's 4 interval classes 1, 2, 3 and 4, might be capable of covering itself in a single bound. And indeed it is. Interval class 1 can cover pitch classes 2, 3 and (switching to abbreviations) IC 2 can cover PCs 6, 8, IC 3 can cover PCs 4, 7 and finally IC 4 can cover PCs 1, 5. It's the only way of doing it with regard to equivalence of rotational and reflective symmetries.

1 2 3 4 5 6 7 8
Octaconicity's Interval Class Coverage

But as a musical transformer - say, as the PC permuter (1,5)(2,3)(4,7)(6,8) - it's not very interesting since all it can do is exchange pitch classes. As such a transformation is an interval-preserving operation, it's pretty much a do-nothing, musically speaking. This is why, in general, we don't regard any tonality covers with PC Sets containing fewer than 3 pitch classes as interesting

But we're not quite done yet with the octagon since there's another friendly coefficient in the 8t4 which indicates that we may have a quadruple covering of the octagon with its four pairs of tetragons (possibly more commonly referred to as quadrilaterals). However such hopes are quickly dashed since one of the 8 quadrilaterals must be a square, and placing a square inside an octagon requires a second square to complete the cover, thus violating our règle du jeu that each shape be used exactly once. We don't even need to bother with the other shapes as we're already dead in the water.

This is a general upper limit to the size of an 'inner polygon'. Once we reach the halfway point of an evenly sized polygon, a subset of exactly half the size which covers every other vertex can complete a cover only with a duplicate of itself to soak up the remaining 'every-other' vertices. Beyond the halfway point of course, there's no possibility of coverage since too few vertices remain.

Our mission, then, is to find the 'special' values of n and k (2 < k < n/2) where rotationally and reflectionally equivalent binary colourings of n-gons (creatures known as necklaces) carry Cn,k (generally irregular) k-sized sub-polygons. We require that k divides both n (permitting n-set coverings with p = n/k of its k-sized subsets) and Cn,k itself (permitting use of all equivalent k-gons) and where p divides Cn,k (permitting complete coverage of Cn,k/p separate n-gons).

The Triumph of the Dodecagon

And so, by this definition, the first polygon where there's even a possibility that a complete set of dihedrally equivalent Pitch Set Classes will be capable of covering its own tonality is the dodecatonic. It's the first one large enough.

It's reasonably obvious that tonalities with a prime number of pitch classes don't even get a look-in with regard to subset covering. So goodbye to 17TET, 19TET, 31TET etc. The 15TET, non-prime, system is quite popular but none of its subset shape collections occur in quantities appropriate to such coverages. The only candidates for tonalities up to 64TET are presented here:

Tonicity
n
Subset Size
k
Multiplicity
p
Count
C
Coverages
C/p
1234123
16447218
2438486
324862478
328416528841322
363121089
3666274744579
404101240124
441148716175621790439
4831619212
48863936144656024
48124725782644181445661
5010510274988020549976
564143472248
6032030015
6321321920189045065573067296816885
644165216326
6488345976804324710
Catalogue of possible n-gon coverings by p distinct k-sets

Coverings and Applications

The power of the enumerative polynomial lies in its proof of existence of such potential coverings. But it's non-constructive and cannot tell us how to build the things it counts. Still less does it tell us anything about their set-covering capabilities.

So, given the unlikelihood of coverage indicated by the previously shown impossibility of 'dianglising a dodecagon' (in musical terms, 'interval-covering a chromatic scale'), and despite the very real lack of interest we have in covering polygons with anything smaller than triangles in any case, the big question is can all 12 triangles (musical triads) - taken four at a time - fit into three dodecagons so that none of their vertices occupy the same dodecagonal vertex (musical pitch class) as another's?

Covering the first dodecagon is easy since there's so much choice. Even with only 8 triangles left, a second cover remains only mildly troublesome. But with only four remaining triangles, a final cover is hard to find since there are so many ways to rotate and reflect them. By the time you have four left, if your earlier choices are unsuitable then the final cover will likely be impossible.

But there are many solutions. Thousands, in fact. Here is one.

Tri-Dodeca-Tetra-Tri-Coverage

In fact this particular solution is not found by trial-and-error but is rather special even in terms of the game itself. We've used the computer algebra system, GAP, to find solutions. Of the thousands of solutions, this is one from a tiny subset of 20 of them. All of the others, except one, which is really special, are of the same class.

The vast majority of triple-set coverings by triad quadruples are found as an example of the Alternating Group on 12 symbols (usually notated as A12). This is a simple group of order 12!/2 = 239500800. Despite the term 'simple' (a term of Group Theory meaning that it has a simple structure and is akin to a prime number in Number Theory) the way this group can fling things about is prodigious, as the number of its operations suggests.

But the configuration above is an example of an arguably more interesting group discovered in the 19th century. It's one of the sporadic simple groups, specifically the Mathieu Group M12. But it is somewhat less flingy as its order is a paltry 95040. And from an applicative point of view it's often nicer to have fewer choices (the apparently paradoxical idea behind 'constraint sets you free') since it's easier to actually make a beginning.

The way the group features into these arrangements is by way of construction. If we take the first of the three coverings we can use it as a permutation - specifically (1,2,3)(4,5,7)(6,9,11)(8,10,12), the four clockwise tricycles in the covering - to generate a group. If we regard the numbers as pitch classes (it's usually 0 to 11 in musical PC Set theory but we can equivalence 12 and 0 with impunity) then we may operate upon any musical segment (the choice of what constitutes a segment is completely up to the applier) by permuting its pitch classes with that permutation. Each pitch class moves (conventionally clockwise) around the triad it finds itself on. For example we might have a segment with pitch classes { 1, 4, 8, 11 } - which could represent a $C\sharp m7$ chord. The aforementioned permutation moves 1 to 2, 4 to 5, 8 to 10 and 11 to 6 (the wraparound) and thereby produces the new set { 2, 5, 10, 6 } - re-presented as { 2, 5, 6, 10 }. This set may - if interpreted as rooted on pitch class 6 (PC Set theory conventionally $F\sharp$) - be perceived as $F\sharp^{+} Maj 7$.

Such a transformation may be applied to any musical segment, such as the one shown below.

A first transmutation
A first segmental transformation

A second use of the same permutation would then transform the PC Set from { 2, 5, 6, 10 } to { 3, 7, 9, 12 } (perhaps $Am7\flat5$?). By the way, that's 3 of the seven sevenths, so this - admittedly tiny - orbit fixes some kind of seventhiness, if you will.

Two transmutations
Permutation product as transformation composition

And a third application will of course return us to the initial set, since all cycles are of the same size, i.e. the order of the permutation is 3. This single permutation has a class index of $x_3^4$ (being a product of 4 3-cycles) and the group it generates is the tiny simple cyclic group of order 3, C3.

The Group M12 is generated when all three coverings are used to construct permutations. The other two are - respectively from the above figure - (1,4,7)(2,5,9)(3,8,10)(6,11,12) and (1,5,9)(2,3,6)(4,8,10)(7,11,12) and although each is a simple $x_3^4$ cycle, when allowed to operate together by composition the group of permutations has the class index

\begin{split} P_{M_{12}}(\textbf{x}) = \frac{1}{95040} ( x_1^{12} + 495 x_1^4 x_2^4 &+ 2970 x_1^4 x_4^2 + 1760 x_1^3 x_3^3 + 396 x_2^6 + 11880 x_1^2 x_2 x_8\\ &+ 9504 x_1^2 x_5^2 + 15840 x_1 x_2 x_3 x_6 + 2970 x_2^2 x_4^2 + 2640 x_3^4 + 17280 x_1 x_{11}\\ &+ 9504 x_2 x_{10} + 11880 x_4 x_8 + 7920 x_6^2 ) \end{split}

If we label these three permutations with the letters 'a', 'd', and 'm' - for no particular reason - then the successive application of, say m followed by a followed by d would be written as mad. It would be the permutation (2,4,3)(5,12,7,11,10,9)(6,8), which is one of the $15840 x_1 x_2 x_3 x_6$ permutations with that particular shape (the $x_1$ in this case representing the point 1, or pitch class $C\sharp$, which happens to be fixed by this particular permutation).

If we apply this mad operation to a fairly well-known melodic segment, we obtain the following:

transgression transmutation
A transformed copyright problem

To recover the original, one would apply the inverse operation $(mad)^{-1} = d^{-1}a^{-1}m^{-1}$ - which is of course the 'undoing' permutation (2,3,4)(5,9,10,11,7,12)(6,8). Because such transformations operate only upon pitch classes however, there can be no indication of which particular octave the original pitch class was in and such information is lost.

There are also relationships between the group's generators. One such relation is found when we look at dm-1 = (1,10,2)(3,4,12)(6,7,9), one of the $1760 x_1^3 x_3^3$ which - in this case - fixes the triad {5, 8, 11}. Since this is clearly an operation of order 3 (comprising exclusively 3-cycles) then any set acted upon by it thrice will reappear. This means that dm-1dm-1dm-1 = (dm-1)3 = (), the group's identity operation. It's also (dm2)3 because the square of any of the generators is also the generator's inverse (two clockwise turns gets you to the same place as one anticlockwise turn).

One might wish to verify that the rather unpleasant looking d2amad2m2a2md2ma2 is also, in fact, a 'do nothing'.

Addendum

As we're on the subject of the Mathieu Group M12, Dave Benson's book mentions that Messiaen's piano piece Ile de Feu 2 uses the 2 permutations (1,7,10,2,6,4,5,9,11,12)(3,8) and (1,6,9,2,7,3,5,4,8,10,11) to transform both tones and durations. The first permutation being one of the $9504 x_2 x_{10}$ and the second one of the $17280 x_1 x_{11}$, they are themselves nothing directly to do with dodecatonic coverages by triads. It's extremely unlikely that the particular triplet of generators we're using here (out of the 20 possible coverages we've found) has any correspondence, pitch-class-wise, with Messiaen's. But it is nonetheless possible to write them in terms of ours, the first as $d a^2 d^2 m a d^2 m^2 a d m^2 (a^2 d)^2 a m d m^2 a^2 d^2 a m^2$ and the second as the slightly simpler (!) $m^2 d^2 (m a^2 d)^2 a^2 d$. These are also calculated by GAP, but such permutation re-mappings are quite tough to work out and it's possible that there are shorter paths from our madness to Messiaen.

20191110

Harmonic Minor - Seventh Haven

First, Count your Sevenths

By a 'seventh' we just mean a tetrad in the 12-tone 'universe' built from stacked thirds (either major or minor) each third being constructed by skipping exactly alternate scale notes. Further, the whole tetrad is constructively (i.e. with no inversions) contained strictly within the span of one octave. The commonest seventh chords encountered are the minor 7th, the major 7th and - perhaps the most well known of all - the dominant 7th, often known simply as the 7th.

The diatonic scale - with its (major, or Ionian Mode) semitone skip pattern of 2212221 - can carry four such stacks, the aformentioned three, plus the one beginning on the subtonic, the 'half-diminished' or 7♭5 chord. Naturally this capability obtains for all seven modes (Ionian, Dorian, Phrygian, Lydian, Mixolydian, Aeolian, Locrian).

The Melodic Minor scale - with its semitone skip pattern of 2122221 - can carry five such stacks. Although it can no longer support a 'standard' major 7th, this loss is amply replaced by two others, the more unusual major augmented seventh +M7 rooted on the scale's tonic, and the 'psycho chord', the minor major seventh mM7 - rooted on the scale's submediant. Again, naturally, this capability obtains for all seven of this scale's modes - more usually regarded as scales in their own right (e.g. Locrian Super, Altered, Melodic Minor, Javanese, Lydian Augmented, Overtone, Hindi, Locrian Natural, etc.).

But there are two more 7ths. All seven may be counted systematically. Starting from a root note labelled 0 you add either 3 or 4 semitones (i.e. the minor or major third), then those two 'waypoints' each offer two further choices by adding 3 or 4 semitone skips, finalising to 8 choices with the concluding 3 or 4 semitone skip to finish the tetrad. The 8th choice is excluded, however, as 4+4+4 tops it off with the root (albeit an octave above) and is not a seventh chord.

In order of 'thirds-stacking' then,we have:

  • 333 - diminished
  • 334 - half-diminished (or minor 7th flat 5)
  • 343 - minor 7th
  • 344 - minor major 7th
  • 433 - 7th
  • 434 - major 7th
  • 443 - augmented major 7th (or major 7th sharp 5)

As 4-gons embedded within the chromatic 12-gon, they may be represented thus (tonic, or root, note at the top, scale ascent clockwise):

Seven Sevenths

Note that the tetrads are generally 'closed' with interval skips of less than 3 - this is simply a fourth skip necessary to complete the tetragonal embedding within the 12-tone dodecagon and should not be seen as part of the seventh's construction. Also, blue indicates the chords represented are their own inversions whereas pink pairs are mutual inverses (e.g. half-diminished is an inversion of 7th, and vice versa).

In the key of F (chosen mainly to confine the tetrads behind a treble clef fence) these chords are:

Effy Sevenths

No heptatonic scale constructable from just half steps or whole steps (interval strings comprising only 1s and 2s) is capable of supporting all of these sevenths. It's necessary to include a 3 step, and - once included - it must be flanked on each side by 1 steps otherwise a two note jump in either direction would exceed 4 semitones and break the minor/major third requirement. This leaves four skips of 1s and 2s - needless to say, consecutive 1 skips are also prohibited since they'd lead to two note jumps incapable of providing any kind of a third (naturally we regard a diminished third as out of bounds).

And the scale known commonly known as the Harmonic Minor, with its interval string of 2122131, is the 'only' heptatonic scale able to accommodate all seven tetrads. The word 'only' is in scare quotes because, as with all heptatonic scales, it has seven modes and these, too, have acquired their own names (often several) as scales, e.g. Locrian Ultra, Harmonic Minor, Mohammedan, Locrian Natural 6, Major Augmented, Harmonic Major, Lydian Diminished, Romanian, Phrygian Dominant, Spanish, Jewish, Aeolian Harmonic etc..

Harmonic minor scale, interval string 2122131, as 7-gon in 12-gon

Tonic at top, scale-note skipping clockwise.

In fact, as the interval string is reversible (say, to the Ethiopian scale, interval-strung as 2212131) in a way that the diatonic and melodic minor 'modes' are not (both of which are their own inverses), a further seven scales or modes are available to support the seven sevenths. There are thus up to fourteen in all.

As an illustration, here's a descent through the scale degrees of an Indian scale (also known as Makam Huzzam, Maqam Saba Zamzam, Phrygian flat 4, according to this catalogue of scale names - thanks to Paul Erlich for pointing me there) showing each of the seven sevenths:

An Indian Descent

An Odd Connection to Block Designs

We have seven 'shapes' (see the above tetragons) embeddable within a seven-sided polygon. Perhaps the simplest example found in every introduction to the subject matter of block designs is one generated by quadratic residues in a field of integers modulo a prime number, itself congruent to the number 3 modulo 4, the first 'interesting' such prime being 7 (3 itself being too trivial). More often than not, the Fano Plane turns up as a diagram:

5 6 3 4 0 1 2

There are seven 'lines' in this figure (if one allows the inscribed circle as being a line), each going through three points. Each such line is a distinct block of the design shown below as a set of seven blocks of three integers each.

The quadratic residues used to construct this simple block design are the squares of the integers modulo 7. Thus 12 = 1, 22 = 4, 32 = 2 (9/7 leaves remainder 2), etc.. We can say etc. here because the next square, i.e. 42 = 16 also leaves remainder 2 after division by 7, and no results other than 1, 2 and 4 will ever turn up.

This set, { 1, 4, 2 }, constitutes the first block (it is, in fact, a representation of the multiplicative group ℤ*7) of the design and subsequent blocks are generated simply by adding 1 (modulo 7, as always) to each of its elements. Thus the second block is { 2, 5, 3 }, the third is { 3, 6, 4 }, the fourth { 4, 0, 5 }, the fifth, sixth and seventh { 5, 1, 6 }, { 6, 2, 0 } and { 0, 3, 1 } - after which further generations would repeat from the first block.

1234560
4560123
2345601

The (symmetric) block design (v=7, k=3, λ=1) displayed as b=7 vertically oriented blocks, in which each variety (integers 0 … 6) turns up r=3 times each and in which each of the 7×6/2=21 pairs of varieties (e.g. {0,1}, {2,5}, {3,4} …) turns up once (λ=1).

Such designs are symmetric in that the number, v, of varieties being distributed is the same as the number, b, of blocks where each block holds k distinct varieties. The varieties are to have equal representation - r of each - throughout the whole design. Seen as a rectangular arrangement of b blocks it's easy to see that vr = bk.

A less obviously visualised property of the block design - in this case a 2-design - is that each pair (hence the 2) of varieties is also equally represented. There are v(v-1)/2 possible pairs and if appearing λ times amongst the b blocks (of k(k-1)/2 pairs in each block), we must have that λv(v-1)=bk(k-1) or, using the earlier equation, λ(v-1)=r(k-1).

It's important to remember that block designs are a way to disperse varieties of objects in a way that - on the face of it - looks somewhat random or unpredictable but which is in fact engineered to give each variety equal exposure in several positions (blocks, the location or sequence of which is unimportant). In the case of 2-designs, each possible pair of varieties will also turn up the same number of times. In the more general t-design case, each t-sized subset of the v varieties (of which there are v(v-1)(v-2)…(v-t+1) distinct possibilities) have equal representation.

Although the designs themselves may be conveniently be built from integers - using the heavy lifting machinery of addition, multiplication, exponentiation etc. - once the design has been generated the numbers may be replaced by something more abstract (the integers’ responsibilities then being delegated, relegated even, to mere labelhood). These objects or varieties can be anything (well, anything distinguishable) and need not be integers. They may be breeds of plant, species of bacteria,

colours: … and even music:
Fano Triads

where, in the above sequence of triads based on the seven blocks, we have mapped the integers 0 … 6 to the pitches B, C, D, E, F, G# and A.

It may seem perverse to sharpen the G in what would normally look like a perfectly ordinary chord sequence in the C major scale, but there's another, seveny, musical reason for it - and it's not the (implied) 7/4 time signature, but that the fact that each triad might be seen as a tetrad missing its fifth. Respectively those missing fifths would be A, B, C, D, E, F and G#. We shall put them in the bass (labelled with the integers 6, 0, 1, 2, 3, 4 and 5) and bung in an extra root note below. Notice that we would then have the complete sequence of all seven sevenths:

Plesio-Fano Tetrads

I want to show you something. It may mean something to you, it may not. I don't know. I don't know anymore.

Ricky Roma

G# A E F B C D

20190726

All Interval Sets revisited

Recently, I spotted a five year old comment by David Feldman, which reminded me of my earlier post on All Interval Sets.

The brute force method, in brief, is to look for 6 term polynomials of the form

s(x) = 1 + x + xp + xq + xr + xs, (2 < p < q < r < s < 31)

such that

s(x) · s(x-1)
= 6 + x + x2 + x3 + x4 + … + x-3 + x-2 + x-1
= 6 + x + x2 + x3 + x4 + … + x28 + x29 + x30 modulo (x31-1)

since that product, fully written out, will look like the 36 term polynomial

1 + x + xp + xq + xr + xs +
x-1 + 1 + xp-1 + xq-1 + xr-1 + xs-1 +
x-p + x1-p + 1 + xq-p + xr-p + xs-p +
x-q + x1-q + xp-q + 1 + xr-q + xs-q +
x-r + x1-r + xp-r + xq-r + 1 + xs-r +
x-s + x1-s + xp-s + xq-s + xr-s + 1

where 6 of the 36 terms are unavoidably collapsed into units (from, e.g. xr · x-r ≡ 1) and the remaining 30 terms - products of 6 × 5 = 30 terms with unequal exponents - are present exactly once. The four 'unknowns' p, q, r and s must be chosen so that the nonzero differences { 0-1, 0-p, 0-q, 0-r, 0-s, 1-0, 1-p, 1-q, 1-r, 1-s, p-0, p-1, p-q, p-r, p-s, q-0, q-1, q-p, q-r, q-s, r-0, r-1, r-p, r-q, r-s, s-0, s-1, s-p, s-q, s-r } must equate to {±1, ±2, ±3, ±4, ±5, ±6, ±7, ±8, ±9, ±10, ±11, ±12, ±13, ±14, ±15}. I.e. where the 28 member set

{ -p, -q, -r, -s, 1-p, 1-q, 1-r, 1-s, p, p-1, p-q, p-r, p-s, q, q-1, q-p, q-r, q-s, r, r-1, r-p, r-q, r-s, s, s-1, s-p, s-q, s-r }
must be the same as the set
{±2, ±3, ±4, ±5, ±6, ±7, ±8, ±9, ±10, ±11, ±12, ±13, ±14, ±15}
- we already know where the ±1s are. Bear in mind that the first, variable, set is by no means presented in any kind of numerical value order. We know things like q-p > 0, and s-p > s-r, and q-r < 0, but not much else.

Whilst the brute force search, finding p, q, r and s - as 10 solution quartets -

pqrs
381218
3101426
461321
4101217
6182229
8111317
11192628
14202429
15192124
15202228

does not take very long for 31 EDO, one can appreciate that for the larger octave division sets where the k(k-1) distinct differences between k distinct pitch classes must all occur exactly once, higher values of k represents a combinatorial explosion in search times (or large systems of Diophantine simultaneous equations).

The Feldman Observation

Prof Feldman finds a rather quicker way to get the all interval sets for 31 EDO, and begins with the fact that the number 3 can generate the complete set of integers 1 … 30 when repeatedly multiplied by itself, 29 times, modulo 31.

This is not as weirdly out of left-field as it sounds. All it takes is a little messing around with multiplicative group theory. Here are the integers we're looking at:

30,31,32,33,34,35, …, 327,328,329
1,3,9,27,19,26,16,17,20,29,25,13,8,24,10,30,28,22,4,12,5,15,14,11,2,6,18,23,7,21

Now this set - which is to say the set of all integers between 1 and 30 inclusive - forms a group, G, with 30 elements. Insofar as

  • the multiplicative identity, 1, is an element
  • any pair, multiplied together modulo 31, is an element (e.g. 25×11 = 275 = (31×8) + 27 ≡ 27)
  • every element has exactly one multiplicative inverse (e.g. 27-1 = 23, since 27×23 = 621 = (31×20) + 1)
  • … and of course integer multiplication in modulo arithmetic is associative

All except the third property is plain to see. You may wish to verify the less obvious one with 28×27 multiplications, or read up on multiplicative groups.

Now this order 30 group has a particular subgroup, H of order 3 (Sylow says there's only one), comprising elements { 3^0, 3^10, 3^20 }, i.e. { 1, 25, 5 }, as the following (rather simple) multiplication table shows:

×311525
11525
55251
252515

Because this subgroup is of order 3, G's elements may be partitioned into 30/3 = 10 cosets of 3 members each. One of them being H itself, and the other 9 being non-groups - since the triples perforce lack the identity.

Here they are with the cosets in columns (with the first column being the actual subgroup H)

H×3kk
0369121518212427
 1271629830415223
 25242812146731917
 511182192620131022

He then combines the first two cosets (columns) to produce the 6-member set H×30H×33 = {1, 5, 11, 24, 25, 27}.

That this set is the 'same' as one found by brute-force is not hard to see. It's basically x24s(x), as the following argument should show.

Differences are completely unaffected by the subtraction of the same constant from each of those six numbers, and it's easy to see that a subtraction of 24 from each will be appropriate since it takes 24 and 25 to 0 and 1 respectively.

{1-24, 5-24, 11-24, 24-24, 25-24, 27-24} = {-23, -19, -13, 0, 1, 3} ≡31 {8, 12, 18, 0, 1, 3} = {0, 1, 3, 8, 12, 18}

since the 24-24, 25-24 gives us a 0, 1 (the 1 + x of our general s(x) 'all interval' polynomial). We can now see that we have recovered the first row of our brutishly forced table, i.e. where p=3, q=8, r=12, s=18.

Were this 'instant solution' not remarkable enough, we may recover the others - again pretty much instantly - by pairing up the remaining 8 cosets:

6∪9161821122829
12∪15914630826
18∪21207315413
24∪2719223221017

The first column entries ab label the rows as being the union of cosets H×3a and H×3b.

All 10 cosets of H (including, as usual, subgroup H itself) have now been accounted for. The group G's 30 elements have thus been partitioned into 5 hexads.

These 5 hexads look like plausible all-interval sets for 31 EDO (we already know the first one is precisely one such) since in each one of them we can see two elements differing by 1 (giving us our 0, 1 exponents for the polynomial s(x)). If we perform the appropriate row subtractions, then, we get

24-23-19-13013x24s0(x)
28-12-10-7-1601x28s1(x)
816-222018x8s2(x)
3174012110x3s3(x)
22-3-2010-12-5x22s4(x)

where the first column shows the value subtracted from each element in that row, and the last column shows what the original row was, written as a pitch class polynomial, where sk(x) is some six term polynomial beginning with 1 + x. We can now present (after modulo 31 normalisation) the p, q, r, s sets in the following table's right hand column (ignoring the 0s and 1s now common to each row).

812180133,8,12,18
192124150115,19,21,24
1629220186,18,22,29
1740121104,10,12,17
281110192611,19,26,28

reproducing five rows (respectively 1st, 9th, 5th, 4th and 7th) of the 'brute' table. Which is basically the full set of all interval patterns since the remaining 5 are simply inversions of the 5 found here (all-interval sets come in pairs of mutually inverted pitch class sets).

It's not clear to me what directed him towards the idea of constructing a set from the union of an order 3 subgroup and its 'first' non-group coset. What is clear is that a more obviously direct approach using an order 6 subgroup would not have worked. For whilst G's subgroup K = {1, 5, 6, 25, 26, 30} has the right number of elements for a 31 EDO all-interval set, it already has two differences of 1 (26-25 and 6-5) in it and so is a complete non-starter.

Is 73 the Best Number?

Some may know that Sheldon Cooper believes it is. But even he may be unaware of a musically interesting property of this particular prime.

First of all, being 9×8+1 it brings us to 73 EDO, just like 6×5+1 brings us to 31 EDO, both of which allow for the possibility of all-interval sets in which all possible (nonzero) differences between pitch classes in pitch class subsets of size 9 and 6 respectively occur exactly once. In polynomial terms we're looking for polynomials such as

s(x) = 1 + x + xp3 + xp4 + xp5 + xp6 + xp7 + xp8 + xp9

where 2 < p3 < p4 < p5 < p6 < p7 < p8 < p9 < 73) such that

s(x) · s(x-1)
= 9 + x + x2 + x3 + x4 + … + x-3 + x-2 + x-1
= 9 + x + x2 + x3 + x4 + … + x70 + x71 + x72 modulo (x73-1)

Of course we've already computed these sets with our brute-force methodology and where, as predicted, the search for the 8 exponent sets found took somewhat longer than it did for 31 EDO - about an hour of computation with a C program. By the time we got to 91 EDO, the computation was taking about a day to complete.

As it happens, life is particularly easy with 73 EDO. First of all, we need a multiplicative group of order 72 to hold our 72 difference counting exponents, and the integer 5 generates it quite nicely, in that the set {50, 51, 52, 53, …, 570, 571} all calculated modulo 73, contains every integer in the range 1 … 72 exactly once. This is a well-known fact about this group, so no work is required here. Although even though you don't need to do it, a computer algebra system such as GAP will take mere seconds to assure you that this is the case.

gap> c:=List([0..71],i->(5^i) mod 73);
[ 1, 5, 25, 52, 41, 59, 3, 15, 2, 10, 50, 31, 9, 45, 6, 30, 4, 20, 27, 62,
18, 17, 12, 60, 8, 40, 54, 51, 36, 34, 24, 47, 16, 7, 35, 29, 72, 68, 48,
21, 32, 14, 70, 58, 71, 63, 23, 42, 64, 28, 67, 43, 69, 53, 46, 11, 55, 56,
61, 13, 65, 33, 19, 22, 37, 39, 49, 26, 57, 66, 38, 44 ]
gap> Sort(c);
gap> c=List([1..72]);
true

And GAP will generate the appropriate group for you, pretty much instantly.

gap> G:=Units(Integers mod 73);
<group of size 72 with 1 generators>
gap> Int(GeneratorsOfGroup(G)[1]);
5

Now we need to find a subgroup H, ideally of order 9, of G. It's certainly possible since 9 divides 72 exactly, and such a subgroup would have an index of 8 = 72 ÷ 9. GAP provides us with a function which gives us subgroups of such an index:

gap> K:=LowIndexSubgroups(G,8);
[ <group of size 72 with 1 generators>, <group of size 36 with 4 generators>,
<group of size 24 with 4 generators>, <group of size 18 with 3 generators>,
<group of size 12 with 3 generators>, <group of size 9 with 2 generators> ]

And we see that the 6th entry is exactly what we're looking for. We can list its elements:

gap> List(K[6]);
[ Z(73)^0, Z(73)^64, Z(73)^48, Z(73)^56, Z(73)^40, Z(73)^24, Z(73)^32, Z(73)^16, Z(73)^8 ]
gap> H:=K[6];
<group of size 9 with 2 generators>
gap> List(H,i->Int(i));
[ 1, 37, 64, 55, 32, 8, 16, 4, 2 ]

And here is H's multiplication table:

×7313764553281642
113764553281642
3737645532816421
6464553281642137
5555328164213764
3232816421376455
881642137645532
1616421376455328
442137645532816
221376455328164

We can see that there's only one element-difference of 1 (from 2 - 1), which is encouraging. We can sort H's elements and subtract 1 from each (remember that subtraction of the same constant from each element has no impact upon their differences)

gap> S:=List(H,i->Int(i));
[ 1, 37, 64, 55, 32, 8, 16, 4, 2 ]
gap> Sort(S);
gap> S-1;
[ 0, 1, 3, 7, 15, 31, 36, 54, 63 ]

Inspection of the n=73 table in that earlier post shows that the set {0, 1, 3, 7, 15, 31, 36, 54, 63} we have here is precisely the first row of that table, under the heading p1 p2 p3 p4 p5 p6 p7 p8 p9.

But of course there's more. Being of index 8, this order 9 subgroup H is associated with another 7 cosets. We already know that 73 EDO provides 4 pairs of mutually inverse all-interval sets. Can it be that the remaining 7 cosets here provide exactly what we need, in what is essentially no time at all (compared to a daysworth of computational searching)?

Since we were careful to make S the sorted list of the group H's operations, rather than overwrite H as a list, the GAP variable H, for H, remains available to us and we can list all 8 cosets in integer form with a one-liner:

gap> C:=List(RightCosets(G,H),i->List(i,j->Int(j)));
[ [ 1, 37, 64, 55, 32, 8, 16, 4, 2 ], [ 22, 11, 21, 42, 47, 30, 60, 15, 44 ],
[ 46, 23, 24, 48, 12, 3, 6, 38, 19 ], [ 72, 36, 9, 18, 41, 65, 57, 69, 71 ],
[ 63, 68, 17, 34, 45, 66, 59, 33, 53 ], [ 51, 62, 52, 31, 26, 43, 13, 58, 29 ],
[ 27, 50, 49, 25, 61, 70, 67, 35, 54 ], [ 10, 5, 56, 39, 28, 7, 14, 40, 20 ] ]

And we know what to do now - although there is likely a better way to do this in GAP if you're going to do it a lot. First we will construct an array of 8 elements to be subtracted, modulo 73, from each of the 8 integer lists (in order to rebase each of them with a 0, 1 pair of elements). Then we will perform that subtraction in a loop, sort each of the 8 lists, and finally re-present:

gap> b:= [1,21,23,71,33,51,49,39];;
gap> for i in [1..8] do; C[i] := (C[i] - b[i]) mod 73; od;
gap> for c in C do; Sort(c); od;
gap> Sort(C);
gap> Display(C);
[[ 0, 1,  3,  7, 15, 31, 36, 54, 63 ],
 [ 0, 1,  5, 12, 18, 21, 49, 51, 59 ],
 [ 0, 1,  7, 11, 35, 48, 51, 53, 65 ],
 [ 0, 1,  9, 21, 23, 26, 39, 63, 67 ],
 [ 0, 1, 11, 20, 38, 43, 59, 67, 71 ],
 [ 0, 1, 12, 20, 26, 30, 33, 35, 57 ],
 [ 0, 1, 15, 23, 25, 53, 56, 62, 69 ],
 [ 0, 1, 17, 39, 41, 44, 48, 54, 62 ]]

And indeed these 8 sets correspond exactly, row for row, to the previously calculated all-interval sets for 73 EDO. And it took only a few minutes rather than an hour or so. The longest part of the process was visually inspecting the cosets in order to construct the 'subtractions array', b.

In any event, for investigations like these, we will find a 'set difference' function useful. We may define it in GAP as:

setdifferences:=function(n, s)
local x, r;
 x := Indeterminate(Integers, "x");
 s := s - Minimum(s);
 r := Sum(List(s, i -> x^i));
 s := Sum(List(s, i -> x^(n-i)));
 return CoefficientsOfUnivariatePolynomial((r*s) mod (x^n-1));
end;

Such a function will essentially perform the calculation of s(x) · s(x-1) and return the coefficients of the polynomial. For example:

gap> setdifferences(73, [22, 11, 21, 42, 47, 30, 60, 15, 44]);
[ 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]

which reveals to a human onlooker that the supplied pitch class set does indeed form an-all interval set within 73 EDO. For a non-human tester, the following function may be more useful:

isalldifferenceset:=function(s)
local x, k, n;
  k := Size(s);
  n := k * (k - 1) + 1;
  s := s - Minimum(s);
  if Maximum(s) < n then
    x := ShallowCopy(setdifferences(n, s));
    if (Size(x) = n) and (x[1] = k) then
      Remove(x, 1);
      return (Minimum(x) = 1) and (Maximum(x) = 1);
    fi;
    return false;
  fi;
  return false;
end;

133 EDO

We already mentioned that it took about a day's worth of computation to find the 12 all-interval sets within 91 EDO (the next suitable microtonality beyond 73 EDO). How long would brute force technique take to search through 111 EDO to find all-interval sets of 11 pitch classes? I don't know because I've not tried it. And the next one up is the sets of size 12 in 133 EDO - how long would that take?

As a teaser, let's try our GAP function out with something daring:

gap> setdifferences(133,[ 0,1,10,58,60,64,82,87,98,101,113,126 ]);
[ 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1 ]

Using group theory it doesn't actually take all that much effort to research 12×11+1 = 133 EDO. Here is a list of the 36 (normal-form) all-interval sets of 12 pitch classes therefrom:

0110586064828798101113126
01253040465396100114122131
0115254552586163808492
018143045475666106109129
0116212449515862688094
0131721586573100105111124
019192431525658697298
015121531333956768598
012633394453616384118130
01521243949617592125127
018213943485473105117131
01233757627583869092102
01622334050596388119131
016183968798298102124126
0173537506689108113122130
0152444717480105112120122
01151820243152608595107
0142751577989100118120125
 
0182133364752707476124
01312203438818894104109
014250547173768289109119
015252868788789104120126
0140546672768385110113118
0110232934616976113117131
01366265767882103110115125
013649587895101103119122129
01416507173819095101108
01794259738595110113129
01317296180869195113126
01324244485159727797111
013154671758494101112128
01810323652556695116128
0141221264568849799127
011214222954606390110129
012739497482103110114116119
01914163445557783107130

Some hints about this - unlike 31 and 73, the number 133 is not prime but has divisors 7 and 19. This means the associated multiplicative group (G) has order (7-1)×(19-1) = 108. Also, 108 is divisible by 36, 12, and 3.