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 (*i*_{1} - *i*_{2}, ƒ_{n}(*i*_{1})-ƒ_{n}(*i*_{2})), with *i*_{1} < *i*_{2} ∈ {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.

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.

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.

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

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 (*i*_{1} - *i*_{2}, ƒ_{n}(1)-ƒ_{n}(2) mod *n*), with *i*_{1} < *i*_{2} ∈ {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):

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

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 **Z**_{q−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).

A permutation σ of order *n* is *singly periodic* iff the mapping σ((*i*−*k*) 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 **A**^{T}. 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.

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 × 10^{134}) 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 3^{87} 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 } ≡ ρ^{i}(ρ^{q − 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 *i*_{j} and *i*_{j+ (q-1)/2} between consecutive notes, separated by half the order: *i*_{j+ (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}) = − *i*_{j}.

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)):

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 ]: T_{1} for the upper left one (red, pointing down), T_{2} for the upper right one (blue, pointing down), T_{3} for the upper middle one (green, pointing up) and T_{4} 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: T_{1} = − T_{2}; 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 2*m* this middle row will contain the *m* numbers 2*m* + 1 − 2σ(*j*), with *j* running from 1 to *m*; in our example 2*m* + 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:

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 eerie symmetry of a perfect ping » |

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:

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.

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 ρ^{(i−k) modq−1} : **Z**_{q−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*)^{×} → **Z**_{q−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.

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 2*m* - 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 2*m* 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 2*m*, that is: either 0, 2*m* or −2*m*. 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 2*m*, this sum will always be equal to 2*m*; like in this classy TD of 'my very first Costas array' (a transposition of the classy 12 tone row generated by primitive root 7):

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:

log_{2} ☞ [12,1,4,2,9,5,11,3,8,10,7,6]

log_{6} ☞ [12,5,8,10,9,1,7,3,4,2,11,6] (≡ 5 × log_{2})

log_{7} ☞ [12,11,8,10,3,7,1,9,4,2,5,6] (≡ 11 × log_{2})

log_{11} ☞ [12,7,4,2,3,11,5,9,8,10,1,6] (≡ 7 × log_{2})

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 log_{2} row by multiplication with a factor 5, or 7, or 11 (because, modulo 13, 2 ≡ 6^{5} ≡ 7^{11} ≡ 11^{7}).

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 n ^{th} 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

...

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 3^{rd} '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? ;-)

« 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, ..., *n* − *i*. 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 2*m* + 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 Z_{n} 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 >>>...

**|** **»**