Anonymous 4chan User Solved Part Of A 25-Year-Old Math Mystery

It started on September 16, 2011, when an anime fan posted a math question to the online bulletin board 4chan.

It was about the cult classic television series The Melancholy of Haruhi Suzumiya. The first season of the show, which involves time travel, was originally aired between April 2 and July 2, 2006 in a nonchronological order, with the prologue and first seven chapters of the first novel intermixed with chapters from some of the later novels.

The "next episode" previews feature two different episode numberings: one number from Haruhi, who numbers the episodes in chronological order, and one number from Kyon, who numbers them in broadcast order.

While the season was then re-broadcast and had a DVD version which further rearranged the episodes to chronological order, fans were arguing online about the best order to watch the episodes.

The question was: if viewers wanted to see the season's 14 episodes in every possible order, what is the shortest list of episodes they have to watch?

In less than an hour later, an anonymous person on 4chan offered an answer.

While it wasn't the complete solution, but it lowered the bound of the number of episodes required. According to the user, people who want to watch Haruhi in every possible order, would have to watch at least 93,884,313,611 episodes to see all possible orderings.

"Please look over [the proof] for any loopholes I might have missed," wrote the anonymous poster.

The answer went relatively unnoticed by the mathematics community for seven years, until an Australian science fiction novelist Greg Egan proved a new upper bound on the number of episodes required.

Egan’s discovery renewed interest in the problem and drew attention to the lower bound posted anonymously in 2011.

After Egan took notice, other mathematicians quickly verified Egan’s upper bound, which, like the lower bound, applies to series of any length.

Robin Houston, a mathematician at the data visualization firm Kiln, and Jay Pantone at the Marquette University in Milwaukee independently verified the work of the anonymous 4chan poster.

The solution to the problem comes from every possible rearrangement (permutation) of, which is also called a "superpermutation."

For example, if a television series has one episodes, the shortest way to do it is just by watching 1 episode (1! superpermutation). For two episodes, the shortest way is to watch episode 1, 2 and 2, 1 (or 121, superpermutation 2! + 1!). For three episodes, there are six orders: 123, 132, 213, 231, 312 and 321. That is a total of 18 episodes that includes every ordering. The more efficient way for doing it, is to watch 123121321 in sequence.

But when it goes to six, n = 6 breaks the pattern down.

Because watching Harumi involves more than that number, Houston’s construction works by translating the superpermutation problem into the Traveling Salesman Problem, which looks for the shortest possible route. However, the algorithms can only solve some cases efficiently, while there are other algorithms that produce good approximate solutions.

So here, Houston only produced an approximate solution, and may not be the very best superpermutation,

To solve the six symbol permutation, mathematicians need a giant computer to search for the shortest superpermutation, Pantone said.

"We know our search will finish in finite time, but don’t know if that’s one week or a million years," he said. "There’s no progress bar."

Egan later found a possible way to construct the superpermutations even shorter than Houston’s. He scoured the literature for papers, and came up with a shorter length upper bound for n symbols: n! + (n – 1)! + (n – 2)! + (n – 3)! + n – 3.

When Egan’s result became public, this reminded other mathematicians about the anonymous poster’s proof, and Houston and Pantone soon showed it was correct. This is because the anonymous 4chan poster’s lower bound, is very close to the new upper bound, as it works with n! + (n – 1)! + (n – 2)! + n – 3.

Egan’s construction gives fans his higher bound possible solution: watching all possible orderings of Haruhi season one in just 93,924,230,411 episodes, a number very close to the lower bound said by the anonymous 4chan poster.

Both the anonymous 4chan poster and Egan's discovery, were being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years.

"It took a lot of work to try to figure out whether or not it was correct," Pantone said. “This proof shows that you don’t need to be a professional mathematician to understand mathematics and advance the frontier of knowledge. The beautiful thing about math, is that anyone can understand the questions.”

Houston and Pantone were joined by Vince Vatter of the University of Florida in Gainesville, to write a formal argument about this math problem. In their paper, they list the first author as "Anonymous 4chan Poster."

"It’s a weird situation that this very elegant proof of something that wasn’t previously known was posted in such an unlikely place," explained Houston.