superpermutation

File:Superpermutation distribution.png

In combinatorial mathematics, a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. While trivial superpermutations can simply be made up of every permutation concatenated together, superpermutations can also be shorter (except for the trivial case of n = 1) because overlap is allowed. For instance, in the case of n = 2, the superpermutation 1221 contains all possible permutations (12 and 21), but the shorter string 121 also contains both permutations.

It has been shown that for 1 ≤ n ≤ 5, the smallest superpermutation on n symbols has length 1! + 2! + … + n! {{OEIS|A180632}}. The first four smallest superpermutations have respective lengths 1, 3, 9, and 33, forming the strings 1, 121, 123121321, and 123412314231243121342132413214321. However, for n = 5, there are several smallest superpermutations having the length 153. One such superpermutation is shown below, while another of the same length can be obtained by switching all of the fours and fives in the second half of the string (after the bold 2):{{cite journal |first=Nathaniel |last=Johnston |date=July 28, 2013 |arxiv=1303.4150 |title=Non-uniqueness of minimal superpermutations |journal=Discrete Mathematics |volume=313 |issue=14 |pages=1553–1557 |doi=10.1016/j.disc.2013.03.024 |bibcode=2013arXiv1303.4150J |url=http://www.njohnston.ca/publications/non-uniqueness-of-minimal-superpermutations/ |accessdate=March 16, 2014 | zbl=1368.05004|s2cid=12018639 }}

123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321

For the cases of n > 5, a smallest superpermutation has not yet been proved nor a pattern to find them, but lower and upper bounds for them have been found.

Finding superpermutations

file:superpermutations.jpg

One of the most common algorithms for creating a superpermutation of order $n$ is a recursive algorithm. First, the superpermutation of order $n-1$ is split into its individual permutations in the order of how they appeared in the superpermutation. Each of those permutations are then placed next to a copy of themselves with an nth symbol added in between the two copies. Finally, each resulting structure is placed next to each other and all adjacent identical symbols are merged.{{cite web|url=http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html|title=Superpermutations|last=Egan|first=Greg|date=20 October 2018|website=gregegan.net|access-date=15 January 2020}}

For example, a superpermutation of order 3 can be created from one with 2 symbols; starting with the superpermutation 121 and splitting it up into the permutations 12 and 21, the permutations are copied and placed as 12312 and 21321. They are placed together to create 1231221321, and the identical adjacent 2s in the middle are merged to create 123121321, which is indeed a superpermutation of order 3. This algorithm results in the shortest possible superpermutation for all n less than or equal to 5, but becomes increasingly longer than the shortest possible as n increase beyond that.

Another way of finding superpermutations lies in creating a graph where each permutation is a vertex and every permutation is connected by an edge. Each edge has a weight associated with it; the weight is calculated by seeing how many characters can be added to the end of one permutation (dropping the same number of characters from the start) to result in the other permutation. For instance, the edge from 123 to 312 has weight 2 because 123 + 12 = 12312 = 312. Any Hamiltonian path through the created graph is a superpermutation, and the problem of finding the path with the smallest weight becomes a form of the traveling salesman problem. The first instance of a superpermutation smaller than length $1! + 2! + \ldots + n!$ was found using a computer search on this method by Robin Houston.

= Lower bounds, or the Haruhi problem =

In September 2011, an anonymous poster on the Science & Math ("/sci/") board of 4chan proved that the smallest superpermutation on n symbols (n ≥ 2) has at least length n! + (n−1)! + (n−2)! + n − 3. In reference to the Japanese anime series The Melancholy of Haruhi Suzumiya, particularly the fact that it was originally broadcast as a nonlinear narrative, the problem was presented on the imageboard as "The Haruhi Problem":{{Cite web |last=Anon |first=- San |date=September 17, 2011 |title=Permutations Thread III ニア愛 |url=https://warosu.org/sci/thread/S3751105#p3751197 |website=Warosu}} if you wanted to watch the 14 episodes of the first season of the series in every possible order, what would be the shortest string of episodes you would need to watch?{{Cite web|last=Klarreich|first=Erica|date=November 5, 2018|title=Sci-Fi Writer Greg Egan and Anonymous Math Whiz Advance Permutation Problem|url=https://www.quantamagazine.org/sci-fi-writer-greg-egan-and-anonymous-math-whiz-advance-permutation-problem-20181105/|archive-url=|archive-date=|access-date=June 21, 2020|website=Quanta Magazine|language=en}} The proof for this lower bound came to the general public interest in October 2018, after mathematician and computer scientist Robin Houston tweeted about it.{{cite web |last1=Griggs |first1=Mary Beth |title=An anonymous 4chan post could help solve a 25-year-old math mystery |url=https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery |website=The Verge}} On 25 October 2018, Robin Houston, Jay Pantone, and Vince Vatter posted a refined version of this proof in the On-Line Encyclopedia of Integer Sequences (OEIS).{{cite web |author1=((Anonymous 4chan poster)) |last2=Houston |first2=Robin |last3=Pantone |first3=Jay |last4=Vatter |first4=Vince |date=October 25, 2018 |title=A lower bound on the length of the shortest superpattern |url=https://oeis.org/A180632/a180632.pdf |accessdate=27 October 2018 |website=OEIS}} A published version of this proof, credited to "Anonymous 4chan poster", appears in {{harvs|last1=Engen|last2=Vatter|year=2021|txt}}.{{citation

| last1 = Engen | first1 = Michael

| last2 = Vatter | first2 = Vincent

| title = Containing all permutations

| doi = 10.1080/00029890.2021.1835384

| doi-access = free

| journal = American Mathematical Monthly

| year = 2021

| volume = 128

| issue = 1

| pages = 4–24

| arxiv = 1810.08252

}}

For "The Haruhi Problem" specifically (the case for 14 symbols), the current lower and upper bound are 93,884,313,611 and 93,924,230,411, respectively. This means that watching the series in every possible order would require about 4.3 million years.{{Cite web |last=Spalding |first=Katie |date=2018-10-30 |title=4chan Just Solved A Decades-Old Mathematical Mystery |url=https://www.iflscience.com/an-anonymous-online-anime-fan-just-solved-a-problem-thats-been-eluding-mathematicians-for-decades-50364 |access-date=2023-10-05 |website=IFLScience |language=en}}

= Upper bounds =

On 20 October 2018, by adapting a construction by Aaron Williams for constructing Hamiltonian paths through the Cayley graph of the symmetric group,{{Cite arXiv|eprint=1307.2549v3|first=Williams|last=Aaron|title=Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)|year=2013|class=math.CO}} science fiction author and mathematician Greg Egan devised an algorithm to produce superpermutations of length n! + (n−1)! + (n−2)! + (n−3)! + n − 3. Up to 2018, these were the smallest superpermutations known for n ≥ 7. However, on 1 February 2019, Bogdan Coanda announced that he had found a superpermutation for n=7 of length 5907, or (n! + (n−1)! + (n−2)! + (n−3)! + n − 3) − 1, which was a new record. On 27 February 2019, using ideas developed by Robin Houston, Egan produced a superpermutation for n = 7 of length 5906. Whether similar shorter superpermutations also exist for values of n > 7 remains an open question. The current best lower bound (see section above) for n = 7 is still 5884.

References

External links

[http://www.njohnston.ca/2013/04/the-minimal-superpermutation-problem/ The Minimal Superpermutation Problem - Nathaniel Johnston's blog]
{{cite web|last1=Grime|first1=James|title=Superpermutations - Numberphile|url=https://www.youtube.com/watch?v=wJGE4aEWc28|website=YouTube|publisher=Brady Haran|accessdate=1 February 2018|format=video}}
[https://warosu.org/sci/thread/S3751105#p3751197 The original 4chan post on /sci/], archived on warosu.org
[https://twitter.com/robinhouston/status/1054637891085918209 Tweet] by Robin Houston, which brought attention to the 4chan post
[https://www.quantamagazine.org/sci-fi-writer-greg-egan-and-anonymous-math-whiz-advance-permutation-problem-20181105/ Article] about the problem of finding short superpermutations in Quanta Magazine

Category:Combinatorics on words

Category:Enumerative combinatorics

Category:Permutations