On the superpermutations of the family of multisets [1, 1, n]

Inspection of the preliminary results for this family which we discovered last time reveals that some of the minimal-length superpermutations of the multisets [1, 1, 2] and [1, 1, 5] are palindromic.

Conveniently, a brute-force search of the space of possible palindromic superpermutations is considerably faster than a brute-force search of the entire superpermutation space. This is because it is only necessary to find a string which contains half of the full set of permutations (eliminating mirrored pairs of permutations), which can then be mirrored to produce to the second half of a palindromic superpermutation. This requires checking (n/2)! orders in which to combine 2^(n/2) possible subsets of the full set of n permutations, but since the exponential function grows much slower than the factorial function, this turns out to be a net win.

It turns out that all members of this family have palindromic optimal superpermutations of a common form (some have multiple palindromic superpermutations). For n=1 through 9, the relevant results are as follows:

(Note that these examples have all undergone rewriting to ensure that digits have their initial appearances in increasing order, and the palindromic suffix is marked out with brackets.)

[1,1,1]: 12312[1321]
[1,1,2]: 112311213[12113211]
[1,1,3]: 11123111213112[1131211132111]
[1,1,4]: 11112311112131112113[1121113121111321111]
[1,1,5]: 111112311111213111121131112[11131121111312111113211111]
[1,1,6]: 11111123111111213111112113111121113[1112111131121111131211111132111111]
[1,1,7]: 11111112311111112131111112113111112111311112[1111311121111131121111113121111111321111111]
[1,1,8]: 111111112311111111213111111121131111112111311111211113[11112111113111211111131121111111312111111113211111111]
[1,1,9]: 11111111123111111111213111111112113111111121113111111211113111112[1111131111211111131112111111131121111111131211111111132111111111]

Each of these starts with n ones, followed by repetitions of the following pattern:

'2' '1'{0} '3' '1'{n-0} '2' '1'{1} '3' '1'{n-1} '2' '1'{2} '3' '1'{n-2}...

I.e., alternating '2's followed by x '1's, and '3's followed by n-x '1's, with x increasing by one in each chunk of symbols, up to n-1 chunks of ones.

This leads to a straightforward O(n^2) algorithm (because the final length is of order n^2, so it takes at least that much time to output the entire string) for generating minimal superpermutations of any multiset in the family [1, 1, n], with O(1) complexity for generating each subsequent symbol incrementally, with the lengths tightly following the previously determined lower bound for this family:

k = 2n + (n+1)(n+2) + 1

An initial exploration of superpermutations of multisets

 A superpermutation of a set is a sequence of n distinct symbols which contains all n! permutations of those n symbols as substrings. A trivial superpermutation just lists all possible permutations one after another, for a total length of n*n!. However, considerably smaller superpermutations can be achieved by overlapping permutations with common prefixes and suffixes.

Without loss of generality, we can label all of the elements of a finite set with integers, and work exclusively with sets of consecutive integers. Each set, and its corresponding set of superpermutations, can then be parameterized with a single number--its size, or cardinality.

The unique superpermutation of the set of size 1 is "1".

The superpermutations of the set of size 2 are "121" and "212" (which are equivalent up to relabelling).

And minimal-length superpermutations are known for sets of up to size 5.

But what if, instead of working with proper sets, in which each symbol must occur exactly once, we decided to look at permutations of multisets instead?

Multisets allow each element to occur any number of times, known as the multiplicity of the element. The (equivalence classes of) multisets are no longer characterized by a single number; instead, we can talk about the support cardinality (the number of different kinds of elements it has), the multiplicities of each of those elements, and the multiset cardinality, which is the sum of the multiplicities. All of that information can be encoded as an ordered list of multiplicities (which, for the sake of consistency and without loss of generality, we can assert must be non-decreasing). Thus, the multiset { 1, 1, 1 } can be represented by the list [3], and the multiset { 1, 2, 2 } can be represented by the list [1, 2].

This provides several different dimensions along which to extend the size of a multiset, with different implications for their effect on the superpermutation.

Multisets with all multiplicities equal to 1 are equivalent to sets of the same cardinality, and have the same superpermutations. Due to the repeated elements, however, multisets with multiplicities greater than one have fewer distinct permutations than sets of the same cardinality, and thus have shorter minimal superpermutations. In the trivial case of multisets with support cardinality 1, they have a single permutation (a list of their single element repeated as many times as its multiplicity), which is also the unique superpermutation--just like sets of cardinality 1.

Things get more interesting for multisets of the form [1, n], with support cardinality 2. These have minimal superpermutations of the form 2{n}12{n}--i.e., the second element repeated as many times as its multiplicity on either side of the first element. E.g., 

super([1, 1]) = 212, equivalent to the superpermutation of the set of cardinality 22
super([1, 2]) = 22122
super([1, 3]) = 2221222

etc.

Each individual permutation consists of inserting the first symbol somewhere in the list of repetitions of the second symbol, and can be obtained by sliding a window of length n+1 across the superpermutation, and the lengths of these superpermutations are trivial characterized by the formula L([1, n]) = 2n + 1.

If we move on to multisets of support cardinality 3, however, things suddenly get considerably more complicated. Adding only a single additional element with multiplicity 1 increases the number of permutations by a factor of n+1 (going from 3 for n=2 to 12=3(n+1) for n=3), as the additional element can be placed in every position in each of the previous permutations. Through exhaustive search, the minimal unique (i.e., with mirrored pairs and pairs which can be turned into each other via relabelling) superpermutations of [1, 1, 2] are

13321331233132313
33123313231332133

with a length of 17.

A conservative lower bound on the possible lengths of minimal superpermutations can be acquired by observing that the number of permutations achievable by sliding a window along the superpermutation must equal or exceed the number of distinct permutations of the multiset. The number of windows of length n over a string of length k, where n<=k, is simply k - n + 1. The permutations of a multiset S are given by the formula C(S)!/P(m! | m in M(S)) where C is the cardinality function, P is the product operator, and M is the multiplicity function; in other words, it is the factorial of the cardinality of S divided the product of the factorials of each of the multiplicities of S. Thus,

k >= C(S) + C(S)!/P(m! | m in M(S)) - 1

For the [1, n] multisets, this formula gives lower-bound lengths of 3, 5, and 7, respectively--so it is in fact a tight bound. For the multiset [1, 1, 2], however, this gives lower bound length of 4 + 4!/(1!*1!*2!) - 1 = 4 + 24/2 - 1 = 4 + 12 - 1 = 15--while the actual minimal length, discovered by exhaustive search, was 17. And in fact, it is easy to see that each of the superpermutations have 2 length-4 substrings which are not permutations of the multiset, accounting for the extra length. This is unsurprising, since it is already well known that this is not a tight lower bound for superpermutations of sets, and multisets are a strict superset of sets.

There are a few ways in which we could try to extend this result--increase the value of n again, to create a parameterized family of [1, 1, n] multisets; extend the number of singleton elements, to create a parameterized family of [1{n}, 2] multisets, with increasing support cardinality; or pivoting entirely to see what happens with [n, n] multisets, with support cardinality 2 and multiset cardinality 2n.

It turns out that increasing the number of unique elements increases the number of permutations much faster than increasing the multiplicity of an individual element. Trying to brute force [1, 1, 1, 2] (with 60 permutations) just causes my software to run out of memory and fall over and die. That could probably be fixed, but it makes it much easier to go in different directions for now.

The Family [1, 1, n]

Doing a complete brute-force search of the superpermutation space for n > 2 takes a very long time; however, some superpermutations closely approaching the lower bound can be found relatively quickly.

The multiset [1 1, 3] has a lower bound superpermutation length of 24. It appears to have optimal superpermutations of length 27 -- 3 more than the lower bound. An example is 332313323313233312333213332.

The multiset [1, 1, 4] has a lower bound superpermutation length of 35. It appears to have optimal superpermutations of length 39 -- 4 more than the lower bound. An example is 323331323333123333213333231333233133233.

The multiset [1, 1, 5] has a lower bound superpermutation length of 48. It appears to have optimal superpermutations of length 53 -- 5 more than the lower bound. An example is 33233313323333132333331233333213333323133332331333233.

Recalling that [1, 1, 2] had a minimal superpermutation length of 17 -- two more than its theoretical lower bound -- then assuming that this empirical pattern holds, this family appears to have optimal superpermutation lengths given by k = C(S) + C(S)!/P(m! | m in M(S)) + n - 1, which can be simplified to

k = 2n + (n+1)(n+2) + 1

The Family [n, n]

The multiset [2,2] has a total of 6 permutations, and a lower bound superpermutation length of 9. Its single unique superpermutation is

1122112121

which has a single length-4 substring which is not a permutation of the multiset, and a total length of 10.

As with the [1, 1, n] family, doing a complete brute-force search for n>2 takes a very long time, but we can find probable solutions fairly quickly.

The multiset [3, 3] has a lower bound superpermutation length of 25, and an apparent optimal superpermutation of length 29. An example is 12221112221211221212122112122.

The multiset [4, 4] has a lower bound superpermutation length of 77, and an apparent optimal superpermutation length of 117. And example is 222121112222111122221121222111212221121212211122122111222121121221211221212112221122112211211222121212122112122211211.

The multiset [5, 5] causes my search process to run out of memory and fall over. :(

The multiset [1, 1], equivalent to the set { 1, 2 } has a minimum bound of 3, and an actual minimal superpermutation length of 3.

The differences from the minimum bound formula are 0, 1, 4, and 20 for n = 1, 2, 3, and 4 respectively.

Unfortunately, there is a large number of matches for the sequence 0, 1, 4, 20... in The Online Encyclopedia of Integer Sequences... and none for 3, 10, 29, 117. So, without a more principled method construction for these superpermutations, I am unfortunately at a loss to properly characterize them.

Why the Braid Group of Order 4 is the Best Braid Group

 See also: A New Kind of Algebra

Consider the braid group of order 1. It has a single element, the identity element "1", representing section of a single strand. If you stick them together... well, 1*1 = 1, and one untwisted strand stuck onto another untwisted strand just gets you... an untwisted strand. Completely trivial and uninteresting.

Consider the braid group of order 2. It has two generators (basic members which cannot be created by combining other members, but which can combine to create the rest) in addition to the identity element: a twist, and an untwist. This is already an infinite group, because you can make an unlimited number of new unreducible things just by adding more twists! But, it's still a pretty uninteresting one. The only elements are just powers of a single generator--because any sequence that contains both a twist and an untwist simplifies to one that doesn't.

Consider the braid group of order 3. It has four generators, because you can put twists between either of the two pairs of adjacent strands. And finally, you get some non-trivial structure, because twists on different sets of strands don't cancel each other out!

But now, consider the braid group of order 4. It has six generators, and commutative relations! Now you can actually get some interesting algebra going on. And if you continue on to the braid group of order 5? Nothing new. After 4, you just get more things that commute with each other. No truly new structure ever appears again.

Furthermore, if we select elements of B4 with specific interesting properties, we get an interesting number...

Suppose we take a subset of B4 such that all elements obey the rules of Celtic knotwork: i.e., any given strand must alternate between over-crosses and under-crosses; no single strand can cross over another or under another twice in a row. All six generators follow this rule trivially, because they are all single crossings. However, we can characterize the remaining members of this set rather simply: they are all of the braids which contain only sequences of the following pairs of generators:

1. aa
2. bb
3. cc
4. /a/a
5. /b/b
6. /c/c/
7. a/b
8. b/a
9. /ab
10. /ba
11. b/c
12. c/b
13. /bc
14. /cb
15. ac (=ca)
16. a/c (=/ca)
17. c/a (=/ac)
18. /a/c (=/c/a)

So, the entire set can be reduced down to 24 basic elements.

Now, imagine that we print the graphical representations of these elements out of cards, which we can physically manipulate. In addition to lining them up to concatenate them (equivalent to group multiplication), physical cards permit a new operation which is not part of the normal braid algebra: 180-degree rotation. Rotation has the following effect on each of the basic elements:

• r(a)    = c     r(c)    = a
• r(/a)   = /c    r(/c)   = /a
• r(b)    = b
• r(/b)   = /b
• r(aa)   = cc    r(cc)   = aa
• r(/a/a) = /c/c  r(/c/c) = /a/a
• r(bb)   = bb
• r(/b/b) = /b/b
• r(a/b)  = /bc   r(/bc)  = a/b
• r(b/a)  = /cb   r(/cb)  = b/a
• r(/ab)  = b/c   r(b/c)  = /ab
• r(/ba)  = c/b   r(c/b)  = /ba
• r(ac)   = ac
• r(a/c)  = c/a   r(c/a)  = a/c
• r(/a/c) = /a/c

So, suppose that we wanted to build a deck which could provide any of these 24 elements with the minimum number of cards. For any rotational pair, we only need to print a single card, since we can get either member of the pair depending on which way we lay it down. That eliminates 9 elements, getting us down to 15. (It's on odd number because one pair of inverses rotate into each other: a/c ~ c/a.)

If you remove double twists, because they just aren't as cool, that gets you 11 basic cards--which is few enough to fit into the space of a 13-card suit in a regular deck! Thus, you can do Celtic braid algebra on 4 strands by assigning a simple braid value to each of a set of regular playing cards, with two left over--and you get four copies per deck, so you can actually do interesting things!

Go up to order 5, and the number of basic Celtic sequences is considerably larger, so even by throwing out double-twists, you can't get it to fit into a normal card deck nearly as nicely.

A New Kind of Algebra

Suppose we have two "things": a and b. We don't what they are, but we have labels for them. Like any other algebraic variables, we can multiply them by putting them next to each other: aa, ab, ba, or bb. Since we don't know what these things are, we can't assume that their multiplication is commutative; i.e., ab does not necessarily equal ba. So, aa, ab, ba, and bb are four new unknown-but-labelled "things" that are generated by multiplying our original things.

We can also define multiplicative inverses, /a and /b, so we can do division. I general, multiplicative inverses aren't guaranteed to exist, but in this case, we can just assert that they do. Thus,

a/a = /aa = b/b = /bb =1

So, we can now generate additional new things named a/b, /ba, b/a, /ab, /a/a, and /b/b.

Additionally, since we have defined a thing times its inverse to equal 1, given a string of things like a/bba, we can simplify it to a1a = aa. Or, for something a little more complicated, we can simplify something like ba/bb/ab to aa1/ab = aa/ab = a1b = ab. Note, however, that because multiplication in general is not guaranteed to be commutative, we can't simplify a/bab or baa/b--the a's get in the way between the b and its inverse.

So, we can simplify things, but not very interesting things--we can only insert and remove sequences where items and their inverses are right next to each other. So let's add a third thing: c, and it's inverse /c. And, we'll assert some special properties of c:

ac = ca
a/c = /ca
c/a = /ac
/a/c = /c/a

In other words, c and its inverse multiply commutatively with a and its inverse. All other combinations are non-commutative.

Now, we can simplify things like a/bc/cba to a/b1ba = a1a = aa, as before; but we can also do things like baca/c/a/a. Note that nothing is adjacent to its inverse, but because of the commutativity rules, we can re-arrange things to put them next to their inverses: baca/c/a/a = baca/a/c/a = bcaa/a/a/c = bc/caa/a/a = ... = b.

Now, suppose we have two more complicated expressions that we want to multiply together; e.g., perhaps we want to square acb/a/c. By itself, it can't be simplified, because the b does not multiply commutatively, so it blocks re-arrangements of the a's and c's to allow cancellation. But when we square it, we get acb/a/cacb/a/c = acba/ac/cb/a/c = acbb/a/c.

Now, having introduced these unknown things and their algebraic properties... what's the point? Clearly, these things aren't regular numbers--do they correspond to anything familiar?

Yes!

It turns out that a and b behave exactly like (and thus, mathematically are) the generators of the braid group of order 3. In other words, If you have three parallel pieces of string, a is the name we give to twisting the first and second strings in a particular direction; b is the name we give to twisting the second and third strings in the same direction; /a and /b are the names we give to twisting those same pairs of strings in the opposite direction; and any three-strand braid can be algebraically described by some sequence of a's, b's, and their inverses. 1--the multiplicative identity--represents a section of straight, untwisted string. a/a = 1 because twisting a pair of strings and then untwisting it results in... untwisted, straight string. Same with /aa, b/b, and /bb. A typical braided hair ponytail is just a sequence a/ba/b, repeated over and over... or b/ab/a, to get the chevrons pointed in the other direction. Multiplying a's and b's together is not commutative because a twist in the first and second strands shares a strand with a twist in the second and third strands, so you can't slide them past each other to change their order.

Adding c gives you the three generators of the braid group of order 4--that is, a way to describe braids with 4 strings. So, why does c commute with a? Because a twist in strings one and two doesn't share any strands with a twist in strings three and four! So, you can slide them back and forth along their respective pairs of strings to change their linear order.