# Cube Permutation Result from a New Member



## David314 (Aug 29, 2009)

Hello, fellow speedsolvers! My name is David Smith, and I posted an introduction earlier today. It's a pleasure to meet you!

I have discovered a result for counting the permutations of the Rubik's Cube which I hope might be of some interest to the community. It is based on the work of Chris Hardwick, who I previously collaborated with regarding the n x n x n cube formulas he found, as well as T. R. Keane and H. J. Kamack, who wrote a paper called "The Rubik Tesseract". I hope that posting this here is relevant and of value to the speedsolving community; if not I apologize in advance.

Basically, I have discovered a general formula which counts the number of visually distinguishable reachable positions of a Rubik's Cube of any size and any dimension. It turns out that Rubik's Cubes can be defined in four dimensions and higher. Many of you may be aware of a computer program called Magic Cube 4D, which is a fully functional representation of a 4-dimensional Rubik's Cube. There is also a program called MagicCube5d, which is the analogous simulation of a 5-dimensional Rubik's Cube. In fact, some have even solved these 5D cubes! The largest one to be solved so far is the 6^5, and its solution is over 1 million moves long.

Theoretically, a Rubik's Cube of any dimension can exist, and these higher dimensional cubes can be of different sizes just like the 3D cube, so one could have for example a 4^6 cube (a 6-dimensional cube with 4 pieces per edge, like the Rubik's Revenge). Just as Chris Hardwick thought to generalize the well-known permutation counts of the 3x3x3, 4x4x4, and 5x5x5 to cubes of arbitrary size, I thought that perhaps I could do the same with cubes of higher dimensions.

I started with the problem of finding the number of permutations of a 3x3x3x3 Rubik's Cube, and then generalized this to an n^4 Rubik's Cube. This formula can be seen here:

http://www.gravitation3d.com/david/n^4_Cube.pdf

As you can see, I liked Chris's use of the (n mod 2) term in his formulas, which equals zero when n is even, and one when n is odd, as a way of accounting for different cases in one formula. Thanks, Chris! 

I then later found a formula for n^5 cubes:

http://www.gravitation3d.com/david/n^5_Cube.pdf

and n^6 cubes:

http://www.gravitation3d.com/david/n^6_Cube.pdf

After much work, I finally found a general formula for counting the number of permutations of an n^d cube, with n >= 2 and d >= 3.

http://www.gravitation3d.com/david/n^d_Cube.pdf

I should definitely mention that my results are only upper bounds, as the only way to prove them exact would be to somehow find general algorithms for cubes of any size which would demonstrate that the possible positions implied by my formulas are all reachable, or possibly by making heavy use of group theory, in which I am much a novice. In the past these algorithms have always been found, once the impossible positions have been removed, for many different types of 3D and 4D puzzles, including the n^3 cube, the Megaminx, and Magic120Cell, a 4D version of the Megaminx.

I apologize for the lack of a proof for any of these formulas (although I have proved them for myself), they would certainly be long and detailed. Actually, I do have a paper on the derivation of the n^4 cube formula, which can be found here. All of these results and others can be found on my website, www.mathproofs.bravehost.com. By the way, some of you may find some of the puzzles on the puzzles page interesting. Many of them seem completely impossible to solve, especially the last one. 

Describing how each formula works would be a bit complicated (and very lengthy!), but I would be more than happy to answer any questions you may have. Also, feel free to raise any concerns or doubts you may have about my formulas, I completely welcome constructive criticism!

Thanks for reading this long post, I hope my work is a positive contribution to the community, albeit an abstract one. I would also like to thank Chris in particular for his help all those years ago; without finding his formulas I may never have had the idea to come up with my own.


----------



## Lucas Garron (Aug 29, 2009)

Nice post!

I once found "the" n^3 formula independently, but I don't think I can verify yours. But results like this are always cool.

Some comments:

Is there any way to simplify the formulas consistently? It would be really nice if they don't look like one big mess. Would a product help at all?

Are you anywhere near something lie a formula for n^m?

Is there a particular reason you used the term "families" instead of "orbits"? Is it to avoid confusion between slightly similar terms?

Could you make a unified PDF of the formulas (simpler download)?


----------



## David314 (Aug 29, 2009)

Hi, Lucas! Thanks for your positive comments and suggestions, and for taking a look at my results. It's very nice to be corresponding with others about my work!

In response to your comments:



> Is there any way to simplify the formulas consistently? It would be really nice if they don't look like one big mess. Would a product help at all?




I agree, they are somewhat messy! A product form might be possible, but I don't think it would end up making the formulas appear much simpler then they are now, as multiple products would be needed. The way to do this would be to plug in the correct value of the dimension into my general n^d formula (see below), but it appears that this will complicate things further. The problem is that the bases in each individual formula vary too much and cannot all be expressed as a simple product. In choosing between such a product form and the expanded form I am currently using, I would want to choose the latter, as it seems simpler to me. Thanks very much for the suggestion though, I had not previously looked into it. It's too bad your idea didn't simplify things!



> Are you anywhere near something lie a formula for n^m?




If you mean a general formula for a cube of any size and dimension, I have indeed finished that, and included it in my previous post. I apologize if I am either misinterpreting your question, or if my previous post was not clear.



> Is there a particular reason you used the term "families" instead of "orbits"? Is it to avoid confusion between slightly similar terms?




Feel free to correct me if I am wrong, but I was under the impression that the term "orbit" refers to the different cube "universes" that can occur when one disassembles the cube and reconfigures it; at least this is what Wikipedia would have me believe! I defined a family to be a complete group of pieces that occupy the same positions and orientations in all possible configurations of the cube. If this is what is commonly meant by "orbit", I would be happy to change the terminology in my paper! I am very grateful that you took the time to actually look at my paper, not many have done so.



> Could you make a unified PDF of the formulas (simpler download)?




That's a great idea, I never thought of that! Here is such a pdf, it includes the general n^d formula I mentioned above. Thanks!

I checked out your website, congratulations on being accepted to Stanford! I found some of the links on your site very intriguing, especially the probability page and he concept of speed blindfold cubing. My site is here, as a math fan you really might like to take a look at the puzzles page, as the puzzles within are very unique and fun to read even if one is not going to try to solve them! They are also highly counterintuitive, especially the last one which seems like it has a typo! 

Thanks again for your support and suggestions, and feel free to correct me on anything I may have misunderstood.


----------



## Lucas Garron (Aug 30, 2009)

David314 said:


> If you mean a general formula for a cube of any size and dimension, I have indeed finished that, and included it in my previous post. I apologize if I am either misinterpreting your question, or if my previous post was not clear.


Oh. Sorry, the d just looked like it was part of the URL encoding, and it didn't stand out enough. Do you have text versions of the formulas, like a LaTeX source?
I want to import them into Mathematica. 



David314 said:


> Feel free to correct me if I am wrong, but I was under the impression that the term "orbit" refers to the different cube "universes" that can occur when one disassembles the cube and reconfigures it; at least this is what Wikipedia would have me believe! I defined a family to be a complete group of pieces that occupy the same positions and orientations in all possible configurations of the cube.


Yeah, like "algorithm" and "parity," "orbit" slightly gets misused in cubing compared to group theory. I think your use is fine, though; you actually understand what's going on.


----------



## David314 (Aug 31, 2009)

Sorry for taking so long to get back to you, it's been busy around here. I don't have text versions of my formulas, but I might be able to get you LaTeX source for them soon. A friend of mine recently pointed me to the website www.codecogs.com, which has a visual editor that directly converts mathematical input into LaTeX source. However, I don't know how I would do the n^d formula, as the final term is a nested series of products, the number of which depends upon the dimension. There is no way to express this as a single product, and there is no standard notation for such a concept. I'm sure it would be possible to do it with LaTeX code, I just don't know how, and have to rely on the visual editor. I'll get LaTeX code for the other three formulas to you as soon as possible.


----------



## David314 (Sep 2, 2009)

Hi Lucas. I got around to completing the 4D cube formula in Latex, and have attached it. I don't know much about Latex, so please let me know if it is okay, and if you want the other formulas. I am thinking now that I could type up the general n^d formula in Latex, and will do so if the 4D formula meets your expectations.


----------

