# What would happen if the world's best mathematicians devoted their research to cube theory?



## goodatthis (May 21, 2017)

I would assume that breakthroughs would occur, but then again, I don't know how much academic research is done on rubik's cubes and cube theory already. Either way, I think it's interesting to think about.

When I say "world's best mathematicians," I mean those who are the best in the areas most relevant to cube theory, such as abstract algebra and group theory, combinatorics, other discrete math, etc.


----------



## stannic (May 24, 2017)

Well, some mathematicians actually spend some of their time studying puzzles, including the Rubik's Cube. But perhaps you mean doing long-term systematic academic research on cube theory as a high priority.

*Disclaimer*

An answer to any "what would happen if" is likely to be speculative to some extent.

For what it's worth, below are loosely connected amateurish speculations in no particular order. I may not be the right person to ask about things I'm going to write about; people who actually deal with those things clearly know much more on the specific details. Some parts of the following may be obvious to everyone. Other parts may be abstract nonsense.

So basically take all of this with some scepticism.

*Puzzle theory*

I would replace "cube theory" with "sequential-movement-puzzles theory", to cover (at least) twisty puzzles, circle puzzles, bandaged puzzles and sliding puzzles. (I'll just write "puzzle" instead of "sequential movement puzzle" from now on.) This already leads to a huge variation (in particular, almost everything on Jaap's website would be covered), but still seems to be manageable.

The "core" of puzzle theory would include a common glossary and conventions (perhaps massively borrowing, combining and extending existing conventions and terminology from areas you mentioned, but some new conventions would still be helpful if not necessary). Different branches of puzzle theory would extend that further to deal with specific topics.

Perhaps establishing "core" terminology and conventions and using that to explicitly show important connections between puzzle theory and other areas (including those you mentioned) would be one of first "breakthroughs" to occur. You want a common flexible language which "works" for seemingly unrelated puzzles in different contexts, making it easy to discuss basic problems on concrete puzzles without thinking _too much_ about troubles like how to present a bandaged puzzle with generators and relations or how to handle multiple solved configurations. Once such language exists, it will be easier to ask more advanced questions about families of puzzles.

What is a puzzle? The common idea is that there are moving parts and a system of rules which specifies exactly how and when these parts can be moved. There are still decisions to be made (e.g. do you allow puzzles with non-reversible moves? Do you allow any real number as an angle of rotation in a twisty/circle puzzle, or only a discrete subset like (360/n) degrees where n is a positive integer? Do you require a puzzle to have finitely many moving parts? Do you require the current state of the puzzle to be completely observable, or there may be a "hidden" part? Do you require a puzzle to be physically realizable in the three-dimensional Euclidean world?) Perhaps answers to some of these questions would become parts of the terminology and conventions.

*Long-term systematic research*

I do not expect _many_ "fundamental breakthroughs" or "ground-breaking discoveries". It seems more likely that there would be many seemingly small improvements in various subbranches of puzzle theory, which would eventually have significant cumulative effect. (Maybe this accumulated effect would tend to be relatively unnoticeable unless you are closely watching or actually doing long-term systematic research.)

Instead of just answering a specific question about a given puzzle, a mathematician would (attempt to) formulate and prove a general statement about a family of puzzles. Even when a "concrete" puzzle is under study (such as 3x3x3), all the results (perhaps including some intermediate results which do not rely on too many arbitrary decisions/implementation details) would go into a kind of a library or a queryable database, in the hope of discovering connections with other results later.

*Archaeology*

There are already publications and books on various puzzle-related topics (some of which might be at some point termed "the classics of puzzle theory"). That probably may be augmented by archives of relevant online forums, newsgroups and mailing lists. However, a large part of the knowledge seems to be fragmented (so that you may accidentally find something relevant on an unrelated website or in an unrelated book). I would expect that one of first "breakthroughs" to occur (or maybe a never-ending challenge) is bringing the existing knowledge into system. That would probably involve mining it, archiving it, creating various indexes and "entry points" and so on.

So you might as well invite "world's best librarians" and "world's best puzzle historians" to the party.

*Computers*

Answering many questions for specific puzzles will still rely on massive computations, unless there is a nice mathematical trick applicable to a "small" family of puzzles (think Tower of Hanoi or Lights Out). Even if it turns out there exists a simple formula which can be proven to answer some question, actually proving the formula to be correct may well require computations to be performed. So a major factor will be writing code which correctly implements a given algorithm and runs fast on a given hardware.

Further, the algorithms will become more and more involved and hybrid, combining lots of fundamental algorithms and ideas into a single system, so that issues with big software projects (think GAP or Wolfram Alpha) will come into play.

Considering the above, you might want to invite "world's best programmers" and "world's best software architects" as well.

*Obtaining (some) answers early*

Even if answering most questions will still require huge computations to be performed, researchers might be able to make "earlier-than-expected" answers more likely by determining which technical choices are more likely to lead to good performance. (By "technical choices" I mean here activities like choosing pruning tables for an optimal solver, or choosing a particular sequence of subgoals to prove an upper bound.)

To give a concrete example, someone might find a way to automatically discard most multistage chains for the 4x4x4 without any human intervention or lengthy calculations, just by proving in some way that there must be a better chain. In this case, choosing a particular multistage chain (a sequence of subgoals to prove an upper bound fo the 4x4x4) would be a "technical choice".

It seems to me (as an outside observer) that current approaches involve a significant amount of "hand-tuning" to make them faster and/or less memory-intensive. Even when all the basic algorithms are already chosen and the exact way to combine them is chosen, there are still many decisions to be made. Although these decisions do not affect the correctness of the algorithm, making the right decisions all the way along may lead to a significant improvement in terms of computing resources. A systematic research might help in understanding what choices are likely to be "good" and what choices are likely to be "bad", thus reducing the efforts needed to make all the relevant decisions.

So the researchers might work out a theory for applying a given combination of general-purpose algorithms to the domain of sequential movement puzzles (or a subfamily of them). Such a theory might allow making relevant decisions automatically and maybe even "changing your mind" somewhere in the middle of a computation.

Eventually, most such "hand-tuning" activities would be augmented or replaced by algorithms tuning themselves in some well-defined ways to become more efficient.

Researchers might be able to redefine a hard problem, so that instead of waiting decades to obtain one integer number as the final answer, you'll (relatively) frequently obtain multiple "partial" answers which already tell something about the problem, and in the end all those "partial" answers will combine into the final answer. The big question is of course whether and how it is actually possible to redefine a problem such as finding God's number of a puzzle in a sensible way, so that it will have many "partial" answers each of which is simpler to compute and tells something relevant.

Alternatively, you could just wait for the technological singularity when computers will become smart enough to figure out all of that stuff and prove God's numbers for 4x4x4 and Megaminx in a few real hours without any human intervention at all.

*Further links*

The above is in part inspired by links below.

Someone on this forum asked about "classifying cubes according to invariants like how some knots can be expressed as polynomials". This gives one idea to think about, although I do not know whether it can result in something interesting.

Some other threads on this forum which seem to be relevant to the general idea of developing a theory of sequential movement puzzles:

Any books about puzzle theory?
Mathematics in cubing 
Need Help Simulating Cuboids
3 dimensional equivalent of 3x3x3x3 hypercube
Higher dimensional Rubik's cube

Other links:

(Jaap's website) Group Theory for puzzles
(Jaap's website) On the PSPACE-completeness of Bandaged Puzzles
(arXiv) Algorithms for Solving Rubik's Cubes
(Cube Forum) About 490 million positions are at distance 20
(Cube Forum) Lower Bounds for n x n x n Rubik's Cubes (through n=20) in Six Metrics


----------

