When I moved to studying maths at university, I was stunned by the great variety of concepts, structures and objects that university-level maths finds completely normal, but that you barely even think about at school level. These topics underlie much of other maths, and even though many have been well understood for a very long time, mathematicians are still making new discoveries about them even now. One of my favourite topics was the idea of permutations – ways to rearrange a list of objects, or shuffle things – like a deck of cards.

While I definitely spent time at school rearranging objects (I just like it when things are in the right order, ok?), and often idly wondered about how many different ways there might be to do this, I never realised, until I learnt about it in a first-year maths lecture, that there is a whole mathematical structure around such rearrangements.

You can find the number of ways there are to rearrange N objects by multiplying together all the numbers from 1 up to N: this is called ‘N factorial’, written as ‘N!’. So for 3 objects there are 3! = 3 × 2 × 1 = 6, and with 3 objects there are six possible rearrangements: 123, 132, 213, 231, 312 and 321. For four things there are 4! = 24 arrangements, and so on. Mathematicians study ways to combine permutations, thinking of them as a function that takes a list of objects and rearranges them, but you can also just think of them as all the different ways to order a list of a given size.

As well as being a nifty presentation of an idea, and having lots of lovely properties, permutations also crop up in many other areas of maths – they are mainly studied in combinatorics, but anyone working in group theory or algebra will come across them all the time. I also found them popping up in my PhD research in topology, and they are incredibly useful in many contexts.

Permutations of steel?

Imagine my excitement when I learned that as well as my beloved permutations, there’s also the concept in mathematics of superpermutations. These are sequences of numbers which contain every permutation of the numbers 1 to N, at least once somewhere within the sequence.

For example, if I wanted a superpermutation on the numbers 1 and 2, I could write 121. This contains 12, and 21. To go up to three, and have a sequence that includes all six of the three-item permutations listed above, I’d need 123121321.

The thing mathematicians have been interested in is: what’s the shortest this sequence of digits could be, for a given number N? It’s obvious that if you were to just write the six permutations on three objects out in order: 123132213231312321, you’d have a superpermutation – but it’s not the shortest one. Starting from this simple upper bound of N! × N (the number of possible permutations multiplied by the length of each one), mathematicians have been working to try to get a better bound on the length of the minimal superpermutation. For values of N from 1 to 5, we know the answer – 1 (just 1), 3 (our example of 121), 9 (123121321, as seen above), for four things it’s 33 symbols long, and for five things the shortest string is 153 symbols long (eight different such strings exist, proved to be all of them in 2014). There’s a nice pattern in these values:

1 = 1!
3 = 1! + 2!
9 = 1! + 2! + 3!
33 = 1! + 2! + 3! + 4!
153 = 1! + 2! + 3! + 4! + 5!

But in mathematics, sadly not every pattern carries on forever. Beyond N = 5, the pattern breaks down, and for large values of N the number of possibilities becomes so huge, we don’t have much of an idea of what’s going on at all. For example, the minimal length for six objects, which following the pattern you might expect to be 1! + 2! + 3! + 4! + 5! + 6! = 873, turns out to be something else. In 2014, mathematician Robin Houston discovered a superpermutation for N = 6 of length 872. Others have since found hundreds more of this same length.

Many assumptions that had been made about this problem were suddenly thrown on their head. It’s possible to construct minimal superpermutations for N=1 to 5 using a known algorithm, building it at each stage using a superpermutation for one fewer objects, combined with the new symbol – but this method doesn’t give a minimal superpermutation beyond N = 5. But is 872 the shortest, or could a shorter one be out there?

Credit: Numberphile: Superpermutations, on YouTubeAll of this is covered in James Grime’s wonderful Numberphile video, which he made back in January to explain the problem. But there’s been a recent development in the story which has again taken quite a few people by surprise – and in the video, when James says ‘we don’t know if this is the shortest’ – he may now wish to revise that statement.

Back in 2011, an interesting post appeared on an internet message board called 4Chan, in a discussion about the anime TV series ‘The Melancholy of Haruhi Suzumiya’ – a show which originally aired its episodes in non-chronological order. They posed a problem: if you want to watch all the episodes of a show in all possible orders, what’s the fewest episodes you need to watch?

This is exactly the minimal superpermutation question again, but phrased in terms of TV show episodes. If your show had only 3 episodes, and you watched them in the order 123121312, you’d have seen all 3! = 6 possible orderings during your marathon binge-watch.

Apparently one anonymous user took the problem seriously, and earlier this month it was discovered that they’d in fact found a way to prove a lower bound on such numbers – a minimum length. Since internet forums aren’t the usual location for serious mathematical discourse, nobody thought to take it seriously – until now. Their proof does appear to hold up, and shows that the minimum length of a superpermutation on N objects has to be at least N! + (N−1)! +(N-2)! + N − 3.

This means for 6 objects, it is 6! + 5! + 4! + 6 – 3 = 867. In the wake of this discovery, algorithms have been constructed that can generate superpermutations with this length – and just in case this wasn’t a strange enough story already, the person who found the algorithms is Australian sci-fi author Greg Egan.

Robin Houston, along with some colleagues, has now written up the 4Chan proof as a formal paper, and they are working to integrate it with other proofs about the upper bound for the length of a minimal superpermutation to try to get a complete picture – having both an upper and lower bound brings us much closer to finding the exact value.

The proof method involves visualising all the permutations as part of a network, or graph, and considering how easy it is to move from one permutation to another by adding symbols to the end – for example, 123 can be followed by 231 just by adding one symbol to get 1231, but for 123 to be followed by 312 we’d need to add two extra symbols. Then, the ‘easiest’ path through the graph is determined, using known algorithms from graph theory to solve what’s called the ‘Travelling Salesman Problem’ – how to visit every point with the least possible effort.

This simple problem has now found at least a partial solution – and one which could have been known years ago, if only people had thought to look in the dark corners of the internet for it. At least you know that if you wanted to watch all 14 episodes of the Haruhi TV series in all the possible orders, you’d only need to watch at least 14! + 13! + 12! + 14 – 4 = 93,884,313,611 episodes, which at half an hour per episode would only take you 4.4 million years. Better get started, then!