My colleague Pablo Soberon just showed me an unusually problematic result to cite, and I wanted to share this weird story. If you have other weird citation stories, do tell!

Yes, this is a second silly post in a row. Lately I’m not finding the time to write more serious ones. And the silly stories need to be documented somewhere…

This story begins with a Japanese anime show called The Melancholy of Haruhi Suzumiya. I don’t know much about this show, but apparently there are several different orders in which one can watch the episodes. This led a fan of the show to ask for the minimum number of episodes one needs to watch, so that you saw all the episodes in every possible order. In other words, the minimum sequence of the numbers from that contains every possible permutation of the numbers. (if I understand correctly, each order has to appear consecutively, with no additional numbers in between). This was on 4chan in 2011. A solution was then offered by an anonymous user, and this disappeared among the other weird anime discussions around the web.

It turns out that some people have been studying the above question as a serious math problem, prior to the show and not aware of it. The sequence containing all of the possible permutations is referred to as a

*superpermutation*. See for example here and here. One paper about this was even published in the journal “Discrete Mathematics” in 2013. Now the people coming from the mathematical angle discovered the original 4chan discussion, and in it the solution to the problem. So can they cite this result? It is by an anonymous person and appeared on an anime fans website. If this is not complicated enough, the relevant website no longer exists. Instead, the original discussion was discovered on a site that archives old online discussions. And it’s unclear how stable this archive site is. Luckily, this is not my problem!

Advertisements

At the english wikipedia, one finds the following citation in the article https://en.wikipedia.org/wiki/Superpermutation

Anomymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince (October 25, 2018). “A lower bound on the length of the shortest superpattern”. OEIS. Retrieved 27 October 2018. URL: https://oeis.org/A180632/a180632.pdf

The title of that oeis note is awkward, since “Superpattern” is already used for a different related concept (a sequence that contains every permutation as the relative ordering of a not-necessarily-contiguous subsequence). Determining the length of the minimal superpattern for all permutations is also an open problem, though here the bounds are that it’s between (n/e)^2 and n^2/2 (see https://en.wikipedia.org/wiki/Superpattern for details and references).

Oh. I definitely agree. But I think they’ll need to stick with that title by now – otherwise they would cause still more confusion 😀

See also De Bruijn sequences

De Bruijn sequences ask for every possible sub-sequence and not just permutations, no?