### Superpermutations

Posted:

**Tue Jan 29, 2019 5:10 pm UTC**https://www.youtube.com/watch?v=OZzIvl1tbPo

In this video, Matt Parker talks about superpermutations; that is, a string of symbols from an alphabet, containing as substrings every permutation of the alphabet. That is, given A, B, and C, the smallest superpermutation is ABCABACBA - you can find all six permutations of A, B, and C as substrings in it, and there is no smaller string with this property.

There's a ton we don't know about superpermutations. We have an algorithm that can generate them quickly, and it finds the shortest string for 3 (length 9), 4 (length 33), and 5 (length 153) letters. (Interestingly, while the 2, 3, and 4-letter alphabets have unique shortest superpermutations, 5 letters has *8* equally-shortest superperms. One is a letter-swap of the one the algorithm finds, but the other six appear to have no relation to the algo-generated one; they were found by exhaustive computer search instead.)

At 6 letters, tho, the algorithm generates a length 873 superpermutation, but it turns out there's an unrelated length 872 one, found by computer search. (The guy interviewed in the video, Robin Houston, was the first to discover it.)

The even more interesting part, tho, is that recently we've gotten novel upper and lower bounds for the length of shortest superpermutation for a given alphabet: the lower bound was proven in 2011 by an anonymous 4-chan poster in a thread about anime, and just "discovered" by the wider mathematical world in the last few months (Houston ended up writing up the anon's result in an official paper; anon has first credit in the author bylines. It was generally accepted as a valid proof just last week or so.); the new upper bound was also proven just a few weeks ago by Greg Egan (famed sci-fi author, and amateur mathematician). Egan actually discovered a new, more efficient algorithm for constructing superpermutations, and it happens that the length it generates is lower than the previously-believed upper bound. We know this still isn't optimal, because it finds a length 873 superpermutation for 6 letters, but as previously stated Houston found a length 872 one. Houston believes they can improve Egan's algorithm by 1, so it will generate the 872 and be the current best at all lengths.

This was just real cool and I thought I should share. ^_^

In this video, Matt Parker talks about superpermutations; that is, a string of symbols from an alphabet, containing as substrings every permutation of the alphabet. That is, given A, B, and C, the smallest superpermutation is ABCABACBA - you can find all six permutations of A, B, and C as substrings in it, and there is no smaller string with this property.

There's a ton we don't know about superpermutations. We have an algorithm that can generate them quickly, and it finds the shortest string for 3 (length 9), 4 (length 33), and 5 (length 153) letters. (Interestingly, while the 2, 3, and 4-letter alphabets have unique shortest superpermutations, 5 letters has *8* equally-shortest superperms. One is a letter-swap of the one the algorithm finds, but the other six appear to have no relation to the algo-generated one; they were found by exhaustive computer search instead.)

At 6 letters, tho, the algorithm generates a length 873 superpermutation, but it turns out there's an unrelated length 872 one, found by computer search. (The guy interviewed in the video, Robin Houston, was the first to discover it.)

The even more interesting part, tho, is that recently we've gotten novel upper and lower bounds for the length of shortest superpermutation for a given alphabet: the lower bound was proven in 2011 by an anonymous 4-chan poster in a thread about anime, and just "discovered" by the wider mathematical world in the last few months (Houston ended up writing up the anon's result in an official paper; anon has first credit in the author bylines. It was generally accepted as a valid proof just last week or so.); the new upper bound was also proven just a few weeks ago by Greg Egan (famed sci-fi author, and amateur mathematician). Egan actually discovered a new, more efficient algorithm for constructing superpermutations, and it happens that the length it generates is lower than the previously-believed upper bound. We know this still isn't optimal, because it finds a length 873 superpermutation for 6 letters, but as previously stated Houston found a length 872 one. Houston believes they can improve Egan's algorithm by 1, so it will generate the 872 and be the current best at all lengths.

This was just real cool and I thought I should share. ^_^