Monday, July 1, 2013

A Few Notes about Notations

Several days ago I attached a page to this blog tentatively titled "Spiral Set." I say "tentatively" because it's simply a working title referring to the post "The Form" that began this thread on deep connections. The title will likely change to something more accurately descriptive when I consider this set of eight slides is correct and complete (or when someone tells me that this "super-group"/"hyper-group"/? has been named and studied elsewhere, which would save me a lot of work). I decided to publish this nearly complete set now since nomenclature starts to get cumbersome in describing and applying these inter-related permutations in traditionally marginally- or un-related fields. So a word or two here about the eight slides.

Each slide contains four related permutations. Talking through just one of the slides will explain the other seven. I'm using permutations of order 6 (remember the sestina) to illustrate, but the basic set can be of just about any size. I've chosen the "COIL" slide as an example because I'll be moving soon from the "perfect (Faro) shuffle" in cards to its application in computers.

Some readers will already have noticed that at this point I have introduced four parallel notations, i.e., four different ways of describing (or, better, seeing) the same result.

(1) Open continuous paths. At the top of the slide is a diagram [appearing only in the first four slides as of now – I haven't included the other four yet] showing a 2-dimensional continuous path that crosses once through each of the six points on the line (imagine each point labelled consecutively 1 through 6). Begin at one of the "loose ends" of the path, two of which are "outside" ends and two of which are "inside." Thus outL means start following the path at the outside end on the left resulting in the path on the line [142536] ; outR means start at the outside end on the right, [635241]; inR starts the path at the inside right loose end, [415263]; inL begins at the inside left end, [362514].

(2) Comb combinations. All of these permutations (on all eight slides) are based on dividing the basic set in half in one of two ways: Left and Right halves, L={123} R={456}, and Odd and Even halves, O={135} E={246}.[1]  Each of these subsets is then expressed as an ordered set according to whether the integers increase (→: 123, 456, 135, 246) or decrease (←: 321, 654, 531, 642). Finally, the oriented subsets are either INTERLeaved as in this example or CONCATenated (see slide 1, for example) beginning with whichever subset is written first. Thus, INTERL(L→R→) means write 1 2 3 and then, starting after the 1, interleave 4 5 6 yielding the permutation [142536].[2]  CONCAT(L→R→) = [123456] (see slide 6). INTERL(L←R←) = [362514] (slide 2 above). CONCAT(L←R←) = [321654] (slide 6). INTERL(E←O→) = [614325] (slide 7). Etc. for a total of 32 comb combinations. Also note that the four comb combinations on each of the eight slides are related by both a FLIP operation (O↔E or L↔R, the red lines) and a REVerse orientation operation (← ↔ →, the green lines).

The comb notation and all of the operations it suggests might seem at first to be a highly convoluted way of distinguishing this bunch of 32 permutations (technically only 30 because two of them [123456] and [654321] are repeated) out of all possible permutations. But it's helpful to remember that the comb idea generating all these permutations originated with the medieval definition of the sestina form as retrogradatio cruciata. Once you have the acorn, sooner or later the entire oak will appear for you. But there are two more notations left – the more traditional ones from mathematics.

(3) 1-to-1 map (Cauchy two-line notation). This is the simplest way of representing any permutation and is generally used when introducing the concept in elementary math courses.

It means no more than the top row "goes to" the bottom row: 1→1, 2→4, 3→2, etc. This is often abbreviated in "one-line notation" where the consecutive integers in the top row are assumed; all that's needed is to state the outcome, the bottom row (see the double-line enclosed boxes in slide 2 above).

(4) Closed continuous paths (cyclic notation). This is analogous to the open continuous path in that it cycles through the elements in the string being permuted. Whereas the "open path"notation described in (1) leads through the initial string from one end to another (e.g., 1→4→2→5→3→6), occasionally revealing some nice symmetries, cyclic notation creates one or more closed loops. Referring to the previous example in two-line notation, first note that 1 and 6 are "fixed points" in the example – they don't change in the permutation. Next, go to 2 in the top row and follow the path through: 2→4,4→5,5→3,3→2. tracing the closed path 2→4→5→3→(2). In the traditional notation for cyclic notation this would be written: (1)(6)(2453) as it is on slide 2 above. While I have never seen it presented this way, we could present cyclic notation visually in much the same way the open path notation was presented:

Using cyclic notation it becomes easy to determine any permutation's inverse, e.g., having gone from [123456] to [142536], what permutation will immediately take me back to [123456]? The answer is to simply read each cycle backward. So (1) and (6) are unchanged, but (2453) becomes (3542) which, remembering this is cyclic, is the same as (2354) or (4235) or (5423).  But notice that the inverse we are looking for, (1)(6)(3542) is not available on slide 2. It can be found on slide 1. On inspection we find that slides 1 and 2 are inverse-related, as well as the pair of slides 3 and 4. For the rest, however, the inverse of any permutation is found on the same slide.

A summary of the relationships between the eight slides can be found on the page "Spiral Set Stack."


[1] If the order of the basic set is odd, say 7, all of these relationships will still work and create analogous structures. To work with an odd order, begin by extending the open path diagrams in order to get around the difficulty of dividing the basic set exactly in half. It's an interesting exercise which I'll leave to the reader.
[2] Sorry. Typography problem here. Think of the arrows to the right of a letter within the text as being above the letter as in the slide.