# Related fundamental mathematical conjectures by [L.Babai](https://en.wikipedia.org/wiki/L%C3%A1szl%C3%B3_Babai), [P.Diaconis](https://en.wikipedia.org/wiki/Persi_Diaconis)

Although that particular challenge is narrowly focused on a particular puzzle group, it is provides an illustration for deep mathematical problems, some which are easy to state, but they seems out of reach of the present mathematics. 

Babai-like conjecture for symmetric (permutation) group of n-letters: whatever generators (moves) you choose the God's number (diameter of the Cayley graph) is not more than n^2. I.e. any two permutations can be transformed to each other by not more than n^2 moves (whatever moves you select -- with the only condition all permutations are achievable by them). 
Babai's conjecture is actually more general, T.Tao and others made huge progress on it recent years (see [blog](https://seaneberhard.com/2020/05/21/babais-conjecture-for-at-least-three-random-generators/), [survey13](https://arxiv.org/abs/1303.0239), [survey19](https://arxiv.org/abs/1902.06308) ), but it is still open as well as n^2 conjecture above. The particular conjecture for permutation group goes back at least to V.Rubtsov who raised the question  and supported it by computational experiments in 1975(!). ([Link1](https://doi.org/10.1007/BF01071362), [Link2](https://www.kaggle.com/datasets/alexandervc/cayleypy-development-3-growth-computations/data?select=Rubtsov1976_MaxDiamSearch.pdf)). 

The other fundamental conjecture is due to famous "mathematician and magician" [Persi Diaconis](https://en.wikipedia.org/wiki/Persi_Diaconis). 
It states that whatever moves you choose the mixing time would not be more than n^3 log(n) ([Question 2 page 9](https://arxiv.org/abs/1309.7754)). That roughly speaking predicts that whatever way you shuffle n cards, then n^3 log(n) random shuffles suffices to get random configuration.

# Optimal solution - typically NP-complete (and harder) problems 

It has been proved already in 80-ies that finding the optimal solutions (and diameters) for general permutation groups is hard.
NP-hardness for both optimal decomposition and diameter estimation: [The minimum-length generator sequence problem is NP-hard](https://doi.org/10.1016/0196-6774(81)90029-8), 1981, S Even, O Goldreich
Strengthening to [P-space competeness](https://en.wikipedia.org/wiki/PSPACE-complete) (conjecturally outside NP) for optimal decomposition even for two generators : [The complexity of finding minimum-length generator sequences](https://doi.org/10.1016/0304-3975(85)90047-7), 1986, Mark R. Jerrum

In 2010-ies, results were found for concrete generators, even for Rubik's cube:
[Solving the Rubik's Cube Optimally is NP-complete](https://arxiv.org/abs/1706.06708), 2017, Erik D. Demaine et.al.
[Pancake Flipping is Hard](https://arxiv.org/abs/1111.0434), 2011, L. Bulteau, et.al.
And many others

# God's number for most of the groups/puzzles unknown - open research problems 

Determining God's number (diameter) for the standard Rubik's cube was a long searched result  [remarkably resolved only in 2010](https://www.cube20.org/) in HTM metric, and in 2014 for [QTM metric](https://www.cube20.org/qtm/). It is not yet known for [STM](https://www.speedsolving.com/wiki/index.php?title=Metric#STM) and other metrics for 333 cube. Neither it is known for majority of other puzzles. Known estimates are collected at [speedsolving site](https://www.speedsolving.com/wiki/index.php?title=God%27s_Algorithm#Table_of_God.27s_Numbers).  

Recent papers propose precise conjecture for 444,555 cubes [Hirata1](https://arxiv.org/abs/2404.07337), [Hirata2](https://arxiv.org/abs/2407.12961). But they are not proved. 

Developing methods to estimate diameters (God's numbers) would be noteworthy achievement. 

# More math: [Poincare conjecture](https://en.wikipedia.org/wiki/Poincar%C3%A9_conjecture), [Markoff triples](https://en.wikipedia.org/wiki/Markov_number), automatic theorem proving

From Poincare conjecture to Cayley graph pathfinding with Reinforcement Learning.
[Poincare conjecture in 3d](https://en.wikipedia.org/wiki/Poincar%C3%A9_conjecture) was selected as one of 7 "[Millenium Prize Problems](https://en.wikipedia.org/wiki/Millennium_Prize_Problems)" -  hardest and most important problems in mathematics in 20-th century. It was ingeniously resolved by G. Perelman. However its twin brother - smooth Poincare conjecture in four dimensions  "remains open and is thought to be very difficult"([link](https://en.wikipedia.org/wiki/Poincar%C3%A9_conjecture#Dimensions)). Moreover there is no consensus in community should it be true or not. Prominent mathematicians [Selman Akbulut](https://en.wikipedia.org/wiki/Selman_Akbulut) and [Robion Kirby](https://en.wikipedia.org/wiki/Robion_Kirby) proposed conjectural counterexamples to it and several other conjectures in 1985: “A potential smooth counterexample in dimension 4 to the Poincare conjecture, the Schoenflies conjecture, and the Andrews–Curtis conjecture”([link](https://doi.org/10.1016/0040-9383(85)90010-2)).  Some of these potential counterexamples  were only [refuted in 2024](https://arxiv.org/abs/2408.15332)  with the help of the reinforcement learning. Essentially the problem is almost the same as described in that challenge - find a path between two elements of a space where a group acts. However the structure of the group is more complicated - infinite group of the Andrews–Curtis transformations. 

[Markoff triples](https://en.wikipedia.org/wiki/Markov_number) are solutions of certain  Markov Diophantine equation, the subject going back to 19-th century and attracted attention of many prominent mathematicians. 
[J.Ellenberg](https://en.wikipedia.org/wiki/Jordan_Ellenberg) in a beautiful [blog post](https://quomodocumque.wordpress.com/2016/05/11/bourgain-sarnak-gamburd-on-markoff-triples/): "[Bourgain](https://en.wikipedia.org/wiki/Jean_Bourgain), [Gamburd](https://en.wikipedia.org/wiki/Alexander_Gamburd), [Sarnak](https://en.wikipedia.org/wiki/Peter_Sarnak) on [Markoff triples](https://en.wikipedia.org/wiki/Markov_number)"  emphasises  that: "Again, I emphasize that this is on its face a question of pure combinatorial group theory.  You want to know if you can get from any pair of elements in SL_2(F_p) with negative-unipotent commutator to any other via the two moves above.  You can set this up on your computer and check that it holds for lots and lots of p (they did.)" That is reiterated in recent ML Cayley graph pathfinding [paper](https://arxiv.org/abs/2503.05558) by [M.Douglas](https://en.wikipedia.org/wiki/Michael_R._Douglas) and K.Fraser-Taliente. Who emphasised that such problems can be approached with AI-helped pathfinding and can be considered as "warm-up" for previously discussed Andrews–Curtis conjecture work. 

So in a nutshell both problems ask about existence of a path for some elements in the space where group acts. Potential counterexamples suggesting that path does not exist - might be sometimes resolved by explicit pathfinding. 

Automatic theorem proving.
In a sense, doing mathematics - is actually a pathfinding - to prove a theorem one needs to find a sequence  of arguments which lead from it to axioms or known statements. That can be formalised with the help of e.g. [Lean](https://en.wikipedia.org/wiki/Lean_(proof_assistant)) the language to give "formal proofs". So formally speaking it is the same pathfinding problem, however difficulty lies in enormously larger space of possible moves and states. Although systems like AlphaGeometry were quite successful on solving geometric problems with more or less similar approach as one can use for puzzles/Cayley graphs, the gap between elementary geometry problems and real math research problems is still large. 

# Analogies with games and AlphaGo/Zero approach

Games like Go, chess represent the same class of problems - one needs to find a path on a huge graph - nodes are positions, edges are moves. One searches the path from initial position to any position marked "win". The difference is in two-players scenario which means that after move is done by one player, then position changes independently on his will (second player makes a move). So it is a path-finding on a graph in somewhat changing environment. Nevertheless, conceptually, it is the same class of pathfinding problems.  Group/Puzzle solving represents in that respect a more simple scenario - when environment is not changing. Success of AlphaGo handling the Go game with 10^170 positions suggests the groups/puzzles of similar size should be tractable. The difficulty of the group/puzzle case lies in the different direction - there are many different groups and ideal system should effectively work on all them (it is not obvious that same method can work e.g. for  nilpotent and simple groups - which are quire different). And, moreover, ideally, to be very fast - to enable users (mathematicians) to conduct effectively computational experiments. 

# Fractals and puzzles - beautiful fractal images from groups

Discover  beautiful fractal images from groups: "Investigation of these groups reveals a new family of fractals, as well as a rich structure that is intriguing both mathematically and artistically." [2023](https://arxiv.org/abs/2302.12950), even more [videos](https://www.twodisks.org/play/?r1=1.555&r2=1.48&n1=17&n2=4&zoom=1.382636655948553) (thanks to Tomas Rokicki).