The eerie symmetry of a perfect ping [or, taking a bunch of cowbells and dropping them down the stairs]

december 01, 2014.

"Add 'm up, account for luck
you never know"

The Score, one of the editions of Samuel Hansen's math podcast Relatively Prime (published in the Fall of 2012), features Scott Rickard - an engineer and mathematician with a keen interest in music - who reflects upon a possible 'objective' and 'formal' interpretaion of highly subjective notions like (musical) 'beauty' and 'ugliness'. Or, formulated in a somewhat more modest manner: of what we find 'pleasing' in music and what not.

It is difficult to disagree that what generally - by 'the populus', to use Scott Rickard's words - is experienced as 'pleasing' in music often will be linked to various sorts of repetitions, to patterns in sounds and tones building up 'expectations' for the listener, which then may or may not be fulfilled. "I would argue that pure random music, although to some people it might sound beautiful," Scott said, "will be difficult to classify as such. That is probably not what the general populus would call beautiful."

He then continued by giving the off-the-top-of-his-head illustration of sonic/musical ugliness, that became a main reason for this article to, eventually, come into being.

Here's the example that was: "taking a bunch of cowbells and dropping them down the stairs".

This, very literally, rung a bell: part of our this summer's adventures with Rébus and Kaspar König in the Swiss alps saw us turn into Trichler, when in our way we re-enacted what only later we learned to be an ancient Swiss folk custom in which the cowbell is the protagonist. It comes mighty close to "taking a bunch of cowbells and dropping them dawn the stairs". But were our sonic experiences in Switzerland experiences of sonic ugliness? Was ours ugly music?


You can probably almost see me smile: these questions are rhetorical; I have no intention whatsoever to answer them. But I found Scott's phrase interesting enough to copy it from Samuel Hansen's podcast, and use it as an audio-sample in a recent unPublic session, on Thursday October 16th, with Ian-John Hutchinson, Yoko Miura and Rébus. I virtually dropped the phrase down the stairs, cowbell-style ;-).

Indeed. It was because of the cowbells that I paid such close attention to Scott Rickard's exposition, in that same podcast, of his ideas on how to capture a notion of 'musical ugliness' formally. It was linked to an earlier appearance of his at the "Between the lines" TEDx event in Miami, on September 13th 2011. There Scott gave a talk that centered on the mathematics behind The Perfect Ping, a short piece for piano that he composed and that - with a provocative wink - was presented as the 'ugliest piece of music in the world'.

Why the 'ugliest music in the world'? Because, as he explained, it was conceived so as to be devoid of pattern; in the 'ugliest music in the world' there is nothing that repeats.

But is it really as 'pattern free' and 'void of repetition' as Scott claims it to be? What follows basically and informally is concerned with that question. It suggests a (negative) answer, but without imposing it. Because I do think that not only musical beauty but also the judgment on a 'yes' or 'no' of musical patterns ultimately is a 'head thing': it resides between the ears (and behind the eyes) of a beholder. On the go, though, we will learn some fascinating things about the math of permutations and its application to all interval twelve tone rows in atonal music theory.

The world's "ugliest" piece of music was derived from a so called Costas array, or Costas permutation, i.e. a bijection ƒn on the set {1, ..., n} with the property (the Costas property) that all pairs (vectors) of the form (i1 - i2, ƒn(i1)-ƒn(i2)), with i1 < i2 ∈ {1, ..., n}, are distinct. To be exact: Scott, who is a Costas specialist, picked (or rather - and this is important - algebraically generated, see below) a Costas permutation of order 88. He took the numbers to designate the 88 successive notes that can be played on the keyboard of a piano, from the low A (la) on the far left to the high C (do) on the far right. In 'The Perfect Ping' each of these notes is played only once, in the order determined by the Costas permutation.

88 88

Scott's permutation is the column of numbers to the right of these lines, running down from 1 (the low A (la) - the first note of the piece) to 30 (the D (re) one octave below middle C - its 88th and final note ( * )). [The colored dotted boxes divide the list of the composition's notes in two equal but rigorously related parts. You may enjoy trying to find how the notes in the two halves are related. We'll come back to that.]

The Costas property means the following: if you glide along the list of numbers sequentially (that is: take the order of the numbers as your 'timeline', running from the left to the right, or, in the image: from the top to the bottom; you may also choose to go from the right to the left, but you have to stick to one direction) and consider the successive differences between pairs of numbers that are a chosen fixed distance apart, then you will never find the same difference twice. An example: [2,6,3,8,1,7,9,4,5] is a Costas sequence of order 9. If you glide along the sequence from the left to the right 'in pairs with distance 1', you first get (2,6), then (6,3), (3,8), (8,1), (1,7), (7,9), (9,4) and finally (4,5) with differences 4, -3, 5, -7, 6, 2, -5, 1. If you glide along the sequence 'in pairs with distance 2', you get (2,3), then (6,8), (3,1), (8,7), (1,9), (7,4) and finally (9,5) with differences 1, 2, -2, -1, 8, -3, -4. Et cetera, up until the single 'pair with distance 8': (2,5), with difference 3.

The result is called the sequence's triangle of differences (TD) ( ** ). Here is the TD of the above example:


The column of numbers colored in blue and red to the left of these lines is the first row of the TD of the notes of the 'ugliest piece of music in the world' (the column of numbers to their right): they are the second minus first differences for all the pairs of successive numbers in the list. In the musical interpretation: these are the number of keys on the piano that one has to go to the left (−) or to the right (+) of the key corresponding to the current note, in order to play the next one. Otherwise said: it is the number of semitones that separate two successive notes in the piece, with direction. Music theorists would call them ordered or directed pitch intervals. They would say: "in a Costas tone row all pitches and all directed intervals between equidistant pairs of pitches are distinct". [Also here the colors divide the list of numbers in two parts; this time with a pivot (29), as the number of intervals is odd. And also here you are invited to find out how the two halves are related, which in this case almost literally jumps out. Again, we will come back to this a bit later.]

Costas sequences bear the name of John Costas who introduced them in 1965 during his search for ideal sonar waveforms ('pings'). And as such things often go: that very same year the same objects appeared in a combinatorics paper (entitled Latin squares which contain no repeated digrams) by the American mathematician Edgar Gilbert.

What I find particularly interesting, historically, and from a musician's point of view, is that it was also in 1965 that Stefan Bauer-Mengelberg and Melvin Ferentz published what seems the first description of an algorithm that enumerates all the possible twelve tone rows with the property that not only the twelve tones are distinct, but also the eleven intervals between them [ 2 ]. These rows (which of course are basically permutations of order 12) were very much sought after as kind of 'compositional seed' in the years that very strict forms of serialism were in vogue, the practitioners of which - implicitly or explicitly - tried (like Scott Rickard in his quest for 'ugliness') to push limits in avoiding the use of repetition and repeated patterns in their music.

I do not know whether already back then (in the 1960s, 1970s) there were music theorists and composers that knew about Costas permutations and their properties. Even though, as we will see below, there have been some composers that at the time used (a special kind of) Costas 12 tone row in their work, I doubt that they knew it by that name. The worlds of atonal music theory and that of sonar ping technology half a century ago probably were too wide apart for such a quick 'cross over'.

There is, of course, a big difference in focus. Atonal music theorists in most of their papers on the enumeration and classification of tone rows concentrate on permutations of order 12. Because our Western tonal system has 12 pitch classes (a pitch class identifies all tones that are some whole number of octaves apart), few composers will be interested in facts and theorems about rows of a length different from 12; except for the mathematicians among them, and those who use microtonal series and deviant tonalities. Also, in atonal music theory the eleven distinct intervals in an 'all interval 12 tone row' are not the 'directed pitch intervals' of a Costas permutation. They are what atonal music theorists call 'directed pitch class intervals', which means, mathematically, that all arithmetic is done modulo 12. For example: the difference between pitches 7 and 9 is -2. But between pitch classes that difference is 9 − 7 mod 12 ≡ 10.

Researchers of Costas permutations, on the other hand, are far from concentrating on one single order. Even though one knows that there is no limit to the size of possible Costas permutations (that is because there are infinitely many prime numbers, we'll come back to that), it is, after all those years, still unclear whether there are Costas permutations of all possible orders. So that is sort of a stubborn open problem.

Costas permutations also differ essentially from 'all interval tone rows' in the sense that the all interval condition in atonal music theory is asked only to hold for pairs of tones with distance 1. In 'Costas terminology' this means that only the entries in the first row of the triangle of differences are asked to be all distinct (modulo 12).

A musician, having learned about Costas, might wonder whether one can extend atonal music theory's 'all interval condition' on a 12 tone row to the row's full triangle of differences. And yes, one can. It leads us to what I would have liked to call classy Costas permutations, in reference to the 'pitch classes' in 12 tone rows. But then in the literature I found them referred to as range- or R-periodic Costas permutation modulo n [ 3 ]; in this article, though, I will stick to classy.

For those who come to the subject with a musical eye, classiness is one of two obvious variations on the definition of a Costas permutation. Both of them involve a condition on the differences between equidistant pairs of numbers in permutations that is stronger than the original Costas property, in the sense that each of them, if it holds, will imply that also the original condition is fulfilled.

All graceful Costas permutations are trivial,

The first one is the extension to all rows of the triangle of differences of what is called gracefulness of a permutation. A permutation is said to be graceful if the absolute values of all the differences between successive numbers are distinct. From the point of view of a search for musical 'pattern freeness' this is a logical constraint, as to the (or least my) musical ear, the occurrence of mirrored intervals - e.g., one semitone up and somewhat later one semitone down - certainly is a form of 'repetition'; and 'mirror pairs' (the occurrence of a number n and its additive inverse −n in the same row of the triangle of differences) pretty much always occur in a Costas sequence. Gracefulness would forbid the occurrence of such mirror pairs everywhere in the TD.

Here is a simple example of a 'graceful 12 tone row', together with its triangle of absolute differences.

Graceful 12 tone row + triangle of absolute differences

As you see, 'gracefulness' holds for all the odd rows of the triangle, but not for the even ones. So this 12 tone row is not a graceful Costas permutation. It is also not a Costas permutation tout court. There is a reason for that: there are no graceful 12 tone rows that are also Costas sequences; so there are definitely no graceful Costas sequences of order 12. In fact, strengthening the Costas property to gracefulness is asking too much. Interesting ones simply do not exist: it is not difficult to show that the only graceful Costas permutations are trivial, i.e. they have order 2 or 3. Which implies that every non-trivial Costas permutation must have at least one mirror pair ( *** ). So here's the kind of pattern that no Costas will be able to avoid...

but there are some pretty interesting classy permutations...

In a classy permutation - an R-periodic permutation mod n - we strengthen the Costas property to the 'all pitch class intervals' property from atonal music theory. Hence we forbid the occurrence of the same pitch class intervals in an 'all interval row' also in all the other rows of its triangle of (mod n) differences: a classy permutation of order n is a bijection ƒn on the set {1, ..., n} with the property (classiness) that all pairs (vectors) of the form (i1 - i2, ƒn(1)-ƒn(2) mod n), with i1 < i2 ∈ {1, ..., n}, are distinct. Any classy permutation of course is a Costas permutation. But only a very few Costas permutations are also classy.

We start by observing that for such classy 'all interval' permutations to exist the order has to be even. That is because 'classiness' of a permutation σ of odd order n implies that the sum of the n − 1 entries of the first row of the triangle of classy differences is equal to 0 mod n. But this contradicts the fact that this same sum is also equal to σ(n) − σ(1) which is not equal to 0 mod n. (If it were, σ would not be a permutation.)

OK, so we need to have even order. But then do classy permutations exist for all even orders? Or only for some of them? With the indispensable help of the lists of all known Costas permutations that are made available online by James K. Beard, I started looking for them. In the simplest imaginable way, using Microsoft's Excel. And yes! I found that non-trivial classy permutations do exist. But no! They do not exist for all even orders.

The first un-successful search was the one that had me looking for them among the 444 Costas permutations of order 8: none of these is classy. Then there is also not a single classy one among the 17252 Costas sequences of order 14. And also no classy Costas of size 20. On the other hand: one does find classy Costas permutations of orders 4, 6, 10, 12, 16, 18. And here is one of order 22, together with its triangle of classy (mod 22) differences (TcD):

Classy order 22 permutation + triangle of mod 22 differences

You should feel the pattern that's emerging here... And yes, your guess that there will be no classy permutations of order 24, nor of order 26, was also mine. Indeed: there are not. The pattern being, that apparently one only finds classy permutations if the order is one less than a prime. I am not sure yet whether these are the only possible even orders for classy permutations (this, as a matter of fact, seems to be a pretty hard question). But I do know that for every order that is q − 1, with q a prime number, there will be classy permutations. I can even tell - without looking - how many of these you are going to find. Or to stay on the safe side: how many of them you are going to find at least. Classiness indeed proves to be pretty seldom. For example: the order 22 sequence above is one among precisely 220 classy permutations of order 22, with 10 distinct TcD's. So, modulo an evident equivalence, there are only 10 classy permutations of order 22. There are, essentially, no more than 4 classy 12 tone rows. For order 6, that number is 2 (for a total of 12 classy permutations of order 6). And so on...

... courtesy of some relatively simple algebra... (1. finite field exponentials)

The explanation takes two - closely related - steps that are intimately linked to one of the few known algebraic recipes that generate Costas sequences, discovered independently by Lloyd Welch (in 1982) and Edgar Gilbert (in 1965).
It is easy to apply: given any prime number q, take a primitive root ρ of the finite field GF(q); then the sequence of powers ρ1, ρ2, ... , ρq − 1 [mod q] will determine a Costas permutation of {1, ... , q − 1}. For suppose that two entries in row k of the TD are equal. This means that ρi + k − ρi ≡ ρj + k − ρj for some i, j. From this it follows that (ρi − ρj)(ρk − 1) ≡ 0. But ρ is a primitive root and k < q − 1, so ρk ≢ 1. This then forces the equality of i and j. (We view ρ as a bijection between the additive group Zq−1 and the multiplicative subgroup GF(q)× of the finite field.)

As an example: in GF(7), 3 and 5 are the primitive roots. Now take one of these, e.g. 5, and calculate the successive powers mod 7. They are 5,4,6,2,3,1. And indeed: [5,4,6,2,3,1] is a Costas permutation of order 6. Moreover, also each of its cyclic variations is a Costas permutation: [4,6,2,3,1,5] and [6,2,3,1,5,4] and [2,3,1,5,4,6] and [3,1,5,4,6,2] and [1,5,4,6,2,3]. This construction is known as the exponential Welch construction and one calls the resulting permutations exponential Welch-Costas permutations.

The 'cyclicity' of the thus generated permutations is called 'single periodicity' in the literature. It is illustrated in the following animated image which (horizontally) 'cycles' the matrix representation of the permutation [5,4,6,2,3,]. Think of the matrix (or the list of numbers) being wrapped around a cylinder held vertically; and then you rotate the cylinder (along a North-South axis).

Exponential Welch-Costas sequences are 'singly periodic'

A permutation σ of order n is singly periodic iff the mapping σ((ik) mod n) is a Costas permutation for every integer k. It is easy to see that the exponential Welch-Costas permutations have this property. These actually remain the only known singly periodic Costas permutations. For example: [6,2,1,4,5,3] is a Costas permutation but not an exponential Welch-Costas sequence. And indeed, its cyclic variation [3,6,2,1,4,5] is not Costas. It is a long-standing and still open conjecture that only the exponential Welch-Costas arrays are singly periodic. We will soon see that this actually is equivalent to the 'hard question' about classiness mentioned above.

For we can also wrap the matrix around a cylinder held horizontally and again rotate the cylinder. Is it possible that all the permutations thus obtained (turning the matrix along an East-West axis) are Costas permutations? From a musician's point of view this vertical cycling is like transposing a row of pitch classes. So let us call a permutation that conserves the Costas property under all such possible transpositions, a transpositional permutation: " a permutation σ of order n is transpositional iff (σ + k) mod n is a Costas permutation for all integers k ". One maybe should be careful not to confuse this notion of 'transpositionality' of a permutation matrix A with that of its transpose AT. But we will only need the word in this short paragraph, because, as a matter of fact, one easily shows that this 'transpositionality' is the same as 'classiness': a permutation is classy if and only if it is transpositional.

Below is an animated image of a transpositional permutation. It is not the same permutation as in the previous animation. Exponential Welch-Costas permutations are not classy, i.e. not transpositional. For example: [5,4,6,2,3,1] + 3 mod 6 = [2,1,3,5,6,4], is not a Costas permutation. The animated permutation actually is [6,4,5,2,1,3], which - and this is sort of an intended pun :) - is the (matrix) transpose of [5,4,6,2,3,1]. I.e., it is the inverse of the exponential Welch-Costas permutation [5,4,6,2,3,1]. It is easy to see that the inverse of a Costas permation again is a Costas permutation. The transpositionality is the property this inverse 'inherits' from the expontial construction, where it manifests itself as 'single periodicity': a permutation σ is singly periodic iff its inverse σ−1 is transpositional. It is thus that classiness becomes a property of permutations that are the inverses of permutations generated by the exponential Welch-Costas construction.

cycle Logarithmic Welch-Costas sequences are 'transpositional' cycle

Before exploring this inverse construction somewhat more directly, let us have a closer look at the structure of the exponentially generated Costas permutations. Because it is thus that Scott Rickard got the Costas tone sequence of length 88 that he needed for his 'every key on the keyboard played precisely once' piano piece. This is a size that is far beyond reach of our current computational powers, would we have to use brute force and let today's computers check the 88! (88 factorial, approximately equal to 1.855 × 10134) possible permutations (or some considerable chunk of them) for Costas-ness. Also, the probability of hitting upon a Costas sequence of that size by chance is pretty much nil. But 89 is a prime number, so we know that Costas sequences of order 88 exist. And as we saw, constructing them is easy. All we need is a primitive root of the corresponding finite field. Scott settled for 3, the smallest among the 40 primitive roots of GF(89), and calculated all of its powers mod 89. Starting with the 0th (or, if you prefer, the 88th) power, thus putting 1 (the lowest note on the piano's keyboard) at the beginning, this is the list of numbers that we saw before: 1, 3, 9, 27, ... and so on, until what should have been the "world's ugliest piece of music's" final note: 30 (which is 387 mod 89).

You may now begin to understand why, despite the claimed lack of repetition and absence of patterns, the simple algebraic algorithm that generates it makes that this sequence of notes under closer scrutiny turns out to be a veritable treasure trove of pattern and structure. If you more than just glanced over Scott's list of notes, you surely noticed that corresponding numbers in the two halves all add up to 89: they are each other's additive inverses modulo 89. In the other list, that of the intervals, you will have observed that not only each of the occurring intervals is part of one (unique) mirror pair, but that the entire intervallic movement of the second half is the precise mirror image of that of the first half... "What goes up must come down. And everything that falls down eventually rises"... These structural properties of course are no accidents. Both are simple consequences of the algebraic construction, and come with all Costas permutations that are obtained in that way.

Here's why... : given some prime number q and a primitive root ρ of GF(q),
(i__ The sum of two members of the resulting permutation of order q − 1 that are separated by a distance of half that order is ρi + ρi + (q − 1)/2 ≡ ρiq − 1)/2 + 1) ≡ ρi(−1 + 1) ≡ 0 mod q. As both powers are distinct and less than q, it follows that their sum has to be equal to q, i.e. the order of the Costas permutation plus one.
(ii__ For intervals ij and ij+ (q-1)/2 between consecutive notes, separated by half the order: ij+ (q-1)/2 = ρ1 + j+ (q-1)/2 − ρj + (q-1)/2 ≡ ρj +(q-1)/2(ρ − 1) ≡ ρ(q-1)/2 · ρj(ρ − 1) ≡ − ρj(ρ − 1) ≡ − (ρ1 + j − ρj) = − ij.

The first property is known as G-symmetry (glide-reflection symmetry) of a permutation (of even order). The second property is just a different manifestation of the same thing. It provides the full triangle of differences of even ordered G-symmetric permutations ( **** ) with a crystal clear & pretty structure, with a lot of symmetries. These are best grasped by viewing an example. Let's have a look at the triangle of pitch differences of the following exponential Welch-Costas 12 tone row (a cyclic shift of the one generated by the primitive root 11 of GF(13)):

G-symmetric (exponential Welch-Costas) 12 tone row

You see how this permutation's TD (and, more generally, that of any G-symmetric array) can be divided into four sub-triangles. We will give them the same names as in [ 4 ]: T1 for the upper left one (red, pointing down), T2 for the upper right one (blue, pointing down), T3 for the upper middle one (green, pointing up) and T4 for the lower middle one (green, pointing down). G-symmetry entails that the numbers in the upper right triangle are, row by row, the additive inverses of the numbers in the upper left one: T1 = − T2; and the lower middle triangle is the exact mirror image of the upper middle one, with the TD's middle row acting as the reflector. (If the G-symmetric permutation σ has order 2m this middle row will contain the m numbers 2m + 1 − 2σ(j), with j running from 1 to m; in our example 2m + 1 is the prime number 13.)

Musically, G-symmetry of a sequence of tones means that the second half of the row will be a perfect mirror image of the first half. The row obeys a wonderful scheme, that of "inverted repeat", as illustrated here:

G-symmetric (exponential Welch-Costas) 12 tone row

I think it will be difficult to not agree that this is a fine sample of a possible, and very strict, pattern in music. But it is this very same structure that underlies Scott Rickard's "The Perfect Ping", presumed to be (well, OK, with a 'wink' :) to be "the world's ugliest piece of music" because of its lack of pattern. There's an eerie symmetry governing its structure, I'd say, for something supposedly pattern-free...

Here are the colored triangle of differences and the graph of the melodic symmetry of the sequence of the 88 piano notes making up the 'ugliest music in the world'.

The TD of the Perfect Ping
« The eerie symmetry of a perfect ping »
The melodic symmetry of the Perfect Ping

[ interlude: "but who can hear it?" ]

Even little experienced and untrained listeners will be able to discern the G-symmetry of a 12-tone row when it has been explained to them what they should hear for, i.e. what type of melodic (interval) movement they should pay attention to. This of course is no longer evident if the mirrored pattern is not a 6 note shorty, but a complex phrase that - like in The Perfect Ping - spans 44 distinct pitches and 43 distinct pitch intervals. Already because of its duration this, for almost all of us, will largely exceed the capacity of our (musical) short term memory. Here we enter the domain of musical cognition. Let me leave it at that, at least for the moment. For there is a second structural ingredient to Scott Rickard's exercise, one that I did not mention yet. It profoundly blurs the melodic symmetry of the piece as sketched above, making it very difficult indeed for someone to discern its symmetry on first hearing, by ear alone. (Trained musicians might be able to hit upon it, though, by jotting down the notes while listening to the piece). That second ingredient is the time structure of the piece: the durations of and between the individual notes; what Gottfried Michael Koenig, in his composition-algorithms and -classes, referred to as the sequence of entry points and entry delays. As part of his quest for pattern-freeness, Scott made sure that there would not be any discernible rhythmic structure, and no recurring pattern of durations. To accomplish this he used a so-called Golomb ruler as his piece's timeline. This is sort of a 'one dimensional' version of a Costas permutation. It is a set of marks ('entry points') on an imaginary ruler ('timeline') such that all distances between marks (all 'time-spans') are distinct. I will not say much more about Golomb rulers (the length of this story already got way out of hand), except that one can, for example, easily derive a Golomb ruler from a Costas array. It indeed is easy tout court to make Golomb rulers; though things become computationally a lot more difficult if one wants a ruler to have certain additional properties; like being the shortest possible one with a given number of marks (the order of the Golomb ruler).

To fix both entry points and entry delays of a twelve tone row, we would need a ruler of order thirteen. Modulo trivial variations, the shortest Golomb ruler of that order is 0, 2, 5, 25, 37, 43, 59, 70, 85, 89, 98, 99, 106. Here is the earlier example of an exponential Welch-Costas 12 tone row, now with this Golomb ruler as its timeline and a semiquaver as the shortest duration:

Exponential Welch-Costas 12 tone row with Golomb ruler timeline

It is hardly exaggerated to call this little score a summary, a 'one octave' version, or - sticking to a scientific vocabulary - the abstract of Scott Rickard's "perfect ping". Here is an illustration of the way in which the Golomb ruler 'distorts' the pattern of 'perfect inverted repeat' proper to the exponential Welch-Costas sequence. I do not know the precise Golomb ruler that Scott used, but the effect on the interval symmetry of the 88 sequence given above will be similar.

Exponential Welch-Costas 12 tone row with Golomb ruler timeline

... classy rows are rare (2. finite field logarithms)

Which then brings us back to classy permutations.

We saw that classiness of a permutation σ of order n is the same thing as transpositionality: σ is classy iff (σ + k) mod n is a Costas permutation for every integer k. We also know that the exponential Welch-Costas permutations are singly periodic: for a given GF(q) with primitive root ρ, the mapping ρ(ik) modq−1 : Zq−1 → GF(q)× determines a Costas permutation for every integer k. But then the same holds true for the inverses of these mappings: for every integer k the mapping ( k+logρi ) mod q−1 : GF(q)×Zq−1 (logρ is the discrete logarithm) will determine a Costas permutation. This is just another way of saying that all logarithmic Welch-Costas permutations are classy.

Vice versa, the inverse of whatever classy, and therefore transpositional, permutation will be singly periodic. Therefore, because the exponential Welch-Costas permutations are the only known singly periodic permutations, the logarithmic Welch-Costas permutations are the only classy permutations that we know.

For each of the properties of exponential Welch-Costas permutations that we encountered above there is a corresponding (inverse) property of logarithmic Welch-Costas permutations; or, in other words (of which it still is not clear whether they are actually equivalent words): for each property of singly periodic permutations there is a corresponding (inverse) property of transpositional/classy permutations.

Just after having downloaded James Beard's fine collection of Costas lists, I used it to randomly pick a Costas permutation of order 12 and had Excel show me its TD. Here is that 12 tone row, together with its triangle of differences.

A classy twelve tone row

What struck my eye in the triangle of differences of this very first Costas row that I looked at was the fact that its central column of intervals (what since in my 'private lingo' I have been calling the spine of a permutation) were all sixes: 6, -6, 6, -6, -6, 6. That was kind of curious, I thought. Six semitones. That's a tritone. The twelve tone row that I was looking at had a tritone spine.

It was only much later that I found out that I quite accidentally had picked on one of the very few classy permutations of order 12.
And all classy 12 tone rows have tritone spines...

Having a tritone spine, or more generally - for a permutation of an even order 2m - having an m-spine is the property of the logarithmic Welch-Costas permutations that corresponds to the G-symmetry of the exponential ones: a permutation σ of order 2m is G-symmetric iff its inverse σ−1 has an m-spine. The symmetry of the TD of a G-symmetric permutation becomes what we might call the 'complementarity' of the TD of its inverse. That is (see the TD above), if one adds the first interval in a row to the last one, or the second one to the one before last, et cetera, than the result will always be 0 mod 2m, that is: either 0, 2m or −2m. For example, in the fourth row of the TD above we have 9 + 3 = 12, −4 −8 = −12, −1 + 1 = 0 and 5 −5 = 0. In the classy TD, where the entries range from 1 to 2m, this sum will always be equal to 2m; like in this classy TD of 'my very first Costas array' (a transposition of the classy 12 tone row generated by primitive root 7):

A classy twelve tone row

The logarithmic Welch-Costas permutations thus, obviously, are as tightly structured as are the exponential ones, though the underlying symmetry here, arguably, is of a more devious and less obvious kind. It is interesting to find that precisely - and maybe only - these 'logarithmically generated' sequences are the classy permutations. As 2, 6, 7 and 11 are the four primitive roots of GF(13), in the order 12 case, they are the permutations generated by:
     log2    ☞   [12,1,4,2,9,5,11,3,8,10,7,6]
     log6    ☞   [12,5,8,10,9,1,7,3,4,2,11,6]    (≡ 5 × log2)
     log7    ☞    [12,11,8,10,3,7,1,9,4,2,5,6]    (≡ 11 × log2)
     log11    ☞    [12,7,4,2,3,11,5,9,8,10,1,6]    (≡ 7 × log2)
For each of the 12 possible transpositions of such rows the classy TD is the same, making for a total of 48 classy 12 tone rows. They share 4 distinct triangles of pitch class intervals, that, however, are multiplicatively inter-derivable, e.g. (as indicated) from the log2 row by multiplication with a factor 5, or 7, or 11 (because, modulo 13, 2 ≡ 65 ≡ 711 ≡ 117).

I was thrilled to find that this particular all interval 12 tone row has been known to music theorists and composers at least since the early 1970s. It is referred to in publications on serial and atonal music theory as 'the (famous) Mallalieu row', which was first 'discovered' by Pohlman Mallalieu ( ***** ). It is described as the - unique - all interval twelve tone row with a 'perfect' degree of self-similarity, in the sense that - merely quoting a summary of [ 5 ]; I have not seen the full articles - if every nth pitch class is taken (for n = 1, 2, ..., 11, counting an extra space every time you "go around the end"), the result is always a transposition of the original row. This is equivalent to the transpositionality, i.e. classiness, of the rows generated logarithmically (as logρ((n × i) mod 13) = logρ(n) + logρ(i) mod 12) and therefore indeed makes them the unique 12 tone rows with that property. Theorists and composers like Milton Babbitt, Robert Morris and Tom Johnson have used the Mallalieu row in their compositional work. They actually also were aware that it could be obtained by 'inverting' the list of successive modulo 13 exponentials of 2.


It would be interesting to do 'Another Perfect Ping', by taking the classy inverse of Scott's 88 tone row together with the same Golomb ruler, and compare the sounding results.


Neither the one nor the other though can, as far as I am concerned, be considered a serious candidate for generating a music that is - as much as possible - free of pattern, void of structure.


Specialists use an informal taxonomy that divides Costas sequences in three disjoint categories: generated, emergent and sporadic. The generated arrays are those that arise algorithmically, like the exponential and logarithmic Welch-Costas permutations. Emergent arrays are sequences that result from the manipulation of generated ones. The sporadic Costas arrays are those whose origin remains unexplained (which of course is something that might change with the evolution of our knowledge). Sporadic arrays are found; they are the result of searching for Costas sequences in the haystack of all possible permutations.

The permutation of order 9 shown at the very beginning of this article is an example of a sporadic Costas array. The only discernible symmetry is that of the unavoidable mirror pairs. Look at its spine: -1,6,-2,3 ... It is an example of what I call a spineless Costas permutation, i.e. a Costas permutation whose spine also has the Costas property. In this case it has that property even in an absolute sense: the sporadic Costas permutation [2,6,3,8,1,7,9,4,5] is an absolutely spineless Costas permutation :) ...

Now it would have been great had it been possible to use an absolutely spineless Costas permutation of order 88 to generate a 3rd 'Perfect Piano Ping'. But the only known Costas of length 88 are generated ones. It is still a wide open question whether or not, as of some order, generated Costas sequences become the only possible ones.

There are plenty of sporadic Costas permutations for smaller orders though. As a matter of fact, most of the 12 tone Costas rows are sporadic. A lot of them will be spineless, many of them will be absolutely spineless. These may be interesting candidates to use as pattern free seeds for a pattern free music. For how much closer can one get, virtually, to taking a bunch of cow bells and dropping them down the stairs? ;-)

Absolutely spineless twelve tone Costas row
« An absolutely spineless 12 tone Costas row: like, taking a bunch of cowbells and dropping them down the stairs »

notes __ ::
(*) If you listen to the performance of the piece in the TEDx video, or to the recording that is part of Samuel Hansen's podcast, you may notice that the ultimate note is far lower than the penultimate one: the interval between the final and the one before final note is a 'negative' one, i.e. it goes down. But the Costas sequence ends with the numbers 10 and 30. So the final interval is 30 - 10 = +20: the final note is 20 semitones higher than the penultimate one. It should go up. The final interval should be positive. I pointed this out to prof. Rickard (actually thinking that there was an additional final note) who then, in an email dated October 29th 2014, told me that I was right that the end of his Perfect Ping' was wrong. Not because of an additional note, though, but because of a forgotten one: due to an error in the transcription the final note of the piece had gone missing, and in the performance and recording the piece ends with "33 10" instead of "33 10 30" ... [ ^ ]
(**) The TD, which of course is a well-defined derived object for whatever sequence of numbers, is completely determined by its first row. One gets the subsequent rows by taking successive partial sums of the entries of the first row: of length 2 for the second row, of length 3 for the third one, et cetera. However, it is not the case that whenever the first row's entries are all distinct, the same will hold for all the other rows. To check the Costas property we will need to make the TD more explicit, though it is not necessary to check all of it; see e.g. [ 4 ]. In case the initial sequence is a permutation, we can recover it from the first row of its TD by solving the system of n equations with n unknowns given by the n - 1 equations determined by the first row's entries together with the equation expressing the fact that the sum of the n numbers is equal to n·(n + 1)/2.[ ^ ]
(***) The notion 'mirror pair' appears in Jane Wodlinger's master thesis [ 4 ]. Jane also proves the theorem that all non-trivial Costas permutations contain at least one mirror pair, but that proof is different from the argument that it is a corollary to the fact that there are no non-trivial graceful Costas permutations. So let me quickly sketch a proof of that fact. Gracefulness of a Costas permutation ℊ of order n would imply that each of the n − 1 rows of ℊ is itself a permutation: row 1 is a permutation of 1, ..., n − 1, row 2 is a permutation of 1, ..., n − 2, et cetera: row i is a permutation of 1, ..., ni. This in turn implies that the outermost distance ℊ(n) − ℊ(1) is equal to 1 or -1. Now, if these properties are satisfied and ℊ's order is at least 4, one shows that the distance between the second and one before last element of the permutation has to be 4, contradicting the fact that the three distances in the triangle's second before last row should be 1, 2 and 3. ⊠ [ ^ ]
(****) Similar observations can be made for G-symmetric permutations σ of odd order 2m + 1 ; they are just a tiny bit more involved to formulate, due to the 'single numbered center' σ(m + 1). [ ^ ]
(*****) At the moment of writing I have not been able to find any other information besides the name, and I do not know in what context Pohlman Mallalieu came up with 'his row'... [ ^ ]

references __ ::
[1] Drakakis, Konstantinos (2006). “A review of Costas arrays”, Journal of Applied Mathematics, vol. 2006: Article ID 26385, 32 p. [ ^ ]
[2] Bauer-Mendelberg, Stefan, and Ferentz, Melvin (1965). "On Eleven-Interval Twelve-Tone Rows", Perspectives of New Music 3/2: 93–103. [ ^ ]
[3] Konstantinos Drakakis, Rod Gowb, Gary McGuire (2009). "APN permutations on Zn and Costas arrays", Discrete Applied Mathematics 157 (2009) 3320–3326 [ ^ ]
[4] Jane Wodlinger (2009). "Costas arrays, Golomb rulers and wavelength isolation sequence pairs", MSc thesis, Simon Fraser University, Burnaby, Canada [ ^ ]
[4] Serial Forum: "On Maximally Scrambled Twelve-tone Sets." In Theory Only, vol. 2, no. 5 (1976): 35 and vol. 2, no.7 (1976): 8-20. ("A series of brief letters and articles by Milton Babbitt, Richmond Browne, David Lewin and Robert Morris discussing various aspects of the row [0,1,4,2,9,5,11,3,8,10,7,6 (dubbed the Mallalieu row after its discoverer, Pohlman Mallalieu).") [ ^ ]

tags: Costas arrays, permutations, Milton Babbitt, Tom Johnson, Robert Morris, Mallalieu row

# .456.

comments __ :: __ to comment on this entry, follow this link >>>...

| »