N=6 Palindromes

[Chris Patuzzo]

Hello,

I posted a while ago about an idea I had to specialise the Distributed Chaffin Search to palindromes. I was hoping people might take another look.

In short, my insight was that if we limit the scope of the search to palindromes and make the assumption that no permutation is repeated, we can massively improve the speed of the search.

This is because we can prune far more strings that we would otherwise. We don't need to visit nodes that add a permutation that already appears in reverse in the string built so far since that would cause it to appear twice.

I implemented a single-threaded version of the Chaffin search in Rust and its exhaustive search reached 662 permutations in about three months on my underpowered laptop, which I think is ahead of the combined efforts of the distributed search?

Of course, the shortest superpermutation might not have this structure, but if it does this should get there much faster. Either way, I think we'd learn something so I hope to get the attention from those who know more.

I wrote an article about this. The key idea is in this section: https://tuzz.tech/blog/palindromic-superpermutations#the-magic and my code is here: https://github.com/tuzz/chaffin-variation-rust-v2/

In a month or two I'm building a powerful home lab so I'm going try and parallelise the depth-first search and run it again for an extended period of time.

Thanks

[Chris Patuzzo]

To clarify, since we're searching for palindromes, we only need to search for half of the permutations (360), which is another reason why this is considerably faster.

[Cole Fritsch]

I think this search could be quite interesting. My hypothesis is that the minimal palindromes are the ones from the recursive algorithm. I am very curious to find out if this is right or wrong.

Although all confirmed minimal superpermutations have been palindromic so far, I believe the minimal length for a palindrome of n=6 is at least 873, putting it above 872 -- the lowest length SP for n=6 so far. The main killer is the 5-edge that is forced into the middle of each palindrome of n=6, which can increase the length by quite a bit. I am using a alteration of my bound that has not been confirmed yet, however, I am confident in it.

As for repeated permutations, it would be reasonable to believe that all minimal SPs do not repeat permutations. I think it may be a while before we can prove or disprove that claim.

Little is known about the nature of SPs -- honestly, it seems I know less the more I study them. If we cannot improve our current searching algorithm dramatically, then there is no chance of checking n>=7. Maybe researching the problem with this restrictions could lead to some insight on how minimal SPs function.

-Cole Fritsch