Library Link of the Day: 4chan Just Solved A Decades-Old Mathematical Mystery

Courtesy of IFLScience:

“You may not have heard of The Melancholy of Haruhi Suzumiya, but, among anime fans at least, it’s a pretty big deal. Originally a series of light novels, it follows the adventures of typical high schooler Kyon and the time-travel alien ESP club he is forced to help create by his beautiful if eccentric friend, the titular Haruhi. Since its original run in 2003, it has spawned 10 additional volumes, a film adaptation, several video games, and even its own religion, Haruhiism.

It was first adapted into an anime back in 2006. There were only 14 episodes, but there was a twist: they were aired in nonlinear order. When the DVD was released, they had been reordered again. And, in a show featuring time travel, philosophical paradoxes, and paranormal phenomena, neither were necessarily the definitive order to watch the series.

Which led to a problem: What is the quickest way to watch the series in every possible order?

A few years ago, one anonymous 4chan poster set out to solve this puzzle. The person claimed to have worked out a lower bound for the answer – watch fewer episodes than that, and you’ve no hope of seeing the series in every order.

Crucially, they offered a proof – and, in doing so, they provided the world with an answer to a problem that had eluded mathematicians for a quarter of a century.

In mathematical terms, the Haruhi problem, as it’s become known, asks the following: What is the shortest possible length of a superpermutation of n elements?

Given a set – a collection of things, or elements, like “natural numbers less than 4” or “colors on the US flag” – a permutation basically means some order those things can be listed in. So one permutation of “natural numbers less than 4” is 123. Another is 312.

A superpermutation, however, is a string containing every possible permutation of a set. One superpermutation of natural numbers less than 4 is 123121321, as it contains each of the six possible orderings of the numbers 1, 2, and 3.

That’s fine for small sets, but the lengths of these superpermutations can get really big, really fast. In fact, by the time you have five numbers in your set, the shortest superpermutation possible is already 153 characters long. So instead of finding superpermutations by trial and error, mathematicians wanted to find a general rule: a formula they could use to find the minimum length of a superpermutation of any number of elements.

Back in 1993, a couple of mathematicians thought they’d done just that, but their conjecture was shown to be false for sets with more than five elements in 2014, and the problem was reopened. Then last week, mathematician Robin Houston stumbled upon the anonymous proof on the Haruhi message board – and excited researchers gathered online for an impromptu peer review.

The verdict? The proof checks out, and “Anonymous 4chan Poster” is now a listed co-author on a new combinatorics paper presenting the result.

And thanks to a recent proof showing an upper bound to the problem, it looks like this 25-year-old math problem may be on track to be solved once and for all.

“It might be possible to crack the thing completely open,” Houston told The Verge.

So should we expect the anonymous 4channer to come forward? Possibly not any time soon – according to their proof, they still have nearly 4.3 million years’ worth of Haruhi left to watch before they have time to enjoy their new mathematical fame.”

Stay Curious!

This entry was posted in Math. Bookmark the permalink.