cube files
Indexed Cube Lovers Archive
{4,3,3} 3 symmetry
Submitted by Jakub Stepo on Sun, 02/24/2019 - 06:09.
Hello, I am new to this forum and this is my first post. I know that maybe its content will seem trivial to some of you, but I am afraid that I am not so well versed in mathematics and programming, so I try to do at least something within my limited capabilities (I am 15.34 at the moment).
Based on Dan Hoey’s calculations, I was able to calculate the number of essentially different positions up to symmetry of the four-dimensional analogue of the Rubik’s cube. However, it is quite probable that I have made some mistakes, as I have done it only by hand. Nevertheless, from the patterns observed I was able to make some interesting generalizations, presented later in this post.
I describe the conjugacy classes here with Greg Egan’s notation; his webpage was a huge help to me. To briefly introduce it, it characterizes them by listing which cycles do the 3-cube-centre-pairs (the pairs consist of centres with opposite coordinates) form and whether do they swap also or not, which is denoted using signs. However, even-length cycles are assigned the opposite sign. For example, consider the rotation analogous to two-fold rotation about diagonal in 3D – one 3-cube-centre-pair swaps and two other are exchanged without swapping, so we write it as (1,−)(2,−). When more cycles of the same type occur, it is shortened with exponents: class equivalent to two-fold rotation about face axis in 3D can is written as (1,−)^2 The determinant can be determined easily, so that it is 1 (proper rotation) for even number of minus signs and −1 (improper rotation) for odd number of minus signs. Order of the class is equal to lowest common multiple of the cycles, doubled if it is even permutation of the centre-pairs and improper rotation or odd permutation of them and proper rotation. Size of the class is the number of ways we can choose such cycles times (k−1)! times 2^(k−1) for each k-cycle.
Now on to the calculation: Here is a table listing which cycles emerge within the pieces of the puzzle along with class’ order and size; for the sake of brevity, “cycle(s)” shall be abbreviated to “c”:
Having calculated this, I will now attempt to create a general guide to calculate the number of positions reduced in symmetry for any sequential move puzzle:
Sadly, I do not understand antisymmetry well enough (yet) to do corresponding calculations including antisymmetry also. I have only calculated that the number of self-inverse positions of the 4D-analogue-of-the-Rubik’s-cube should be 1 514 851 187 547 945 564 174 052 809 349 480 746 221 364 817 706 402 235 357 461 479 424.
Anyways, I hope that at least some of you found this interesting.
Yours faithfully,
Jakub
Based on Dan Hoey’s calculations, I was able to calculate the number of essentially different positions up to symmetry of the four-dimensional analogue of the Rubik’s cube. However, it is quite probable that I have made some mistakes, as I have done it only by hand. Nevertheless, from the patterns observed I was able to make some interesting generalizations, presented later in this post.
I describe the conjugacy classes here with Greg Egan’s notation; his webpage was a huge help to me. To briefly introduce it, it characterizes them by listing which cycles do the 3-cube-centre-pairs (the pairs consist of centres with opposite coordinates) form and whether do they swap also or not, which is denoted using signs. However, even-length cycles are assigned the opposite sign. For example, consider the rotation analogous to two-fold rotation about diagonal in 3D – one 3-cube-centre-pair swaps and two other are exchanged without swapping, so we write it as (1,−)(2,−). When more cycles of the same type occur, it is shortened with exponents: class equivalent to two-fold rotation about face axis in 3D can is written as (1,−)^2 The determinant can be determined easily, so that it is 1 (proper rotation) for even number of minus signs and −1 (improper rotation) for odd number of minus signs. Order of the class is equal to lowest common multiple of the cycles, doubled if it is even permutation of the centre-pairs and improper rotation or odd permutation of them and proper rotation. Size of the class is the number of ways we can choose such cycles times (k−1)! times 2^(k−1) for each k-cycle.
Now on to the calculation: Here is a table listing which cycles emerge within the pieces of the puzzle along with class’ order and size; for the sake of brevity, “cycle(s)” shall be abbreviated to “c”:
Conjugacy
class Order Size 2-coloured 3-coloured 4-coloured
========= ===== ==== ========== ========== ==========
e 1 1 24 1-c 32 1-c 16 1-c
(1,−)^4 2 1 12 2-c 16 2-c 8 2-c
(1,−)^2 2 6 4 1-c 16 2-c 8 2-c
10 2-c
(2,+) 4 12 4 1-c 8 4-c 4 4-c
5 4-c
(1,−)^2 4 12 2 2-c 8 4-c 4 4-c
(2,+) 5 4-c
(2,+)^2 4 12 6 4-c 8 4-c 4 4-c
(2,−)^2 2 12 4 1-c 16 2-c 4 1-c
10 2-c 6 2-c
(1,−) 2 24 2 1-c 4 1-c 8 2-c
(2,−) 11 2-c 14 2-c
(3,+) 3 32 8 3-c 2 1-c 2 1-c
10 3-c 2 1-c
4 3-c
(1,−) 6 32 4 6-c 1 2-c 2 2-c
(3,−) 5 6-c 2 6-c
(4,+) 8 48 3 8-c 4 8-c 2 8-c
(1,−) 2 4 12 1-c 8 1-c 8 2-c
6 2-c 12 2-c
(1,−)^3 2 4 12 2-c 16 2-c 8 2-c
(2,−) 2 12 6 1-c 8 1-c 8 1-c
9 2-c 12 2-c 4 2-c
(1,−)^2 2 12 2 1-c 16 2-c 8 2-c
(2,−) 11 2-c
(1,−) 4 24 2 2-c 8 4-c 4 4-c
(2,+) 5 4-c
(2,−) 4 24 2 1-c 8 4-c 4 4-c
(2,+) 1 2-c
5 4-c
(3,−) 6 32 4 6-c 1 2-c 2 2-c
5 6-c 2 6-c
(1,−) 6 32 4 3-c 2 1-c 2 2-c
(3,+) 2 6-c 2 3-c 2 6-c
4 6-c
(4,−) 4 48 6 4-c 8 4-c 4 4-c
Here are the deducted numbers:
2-COLOURED Conjugacy class Permutations Orientations Positions ============ ============ ============ =============================== e 24! × 2^24/2 = 5204698426366666226930810880000 (1,−)^4 12!×2^12 × 2^12 = 8036313307545600 (1,−)^2 4!×10!×2^10 × 2^4×2^10/2 = 730573937049600 (2,+) 4!×5!×4^5 × 2^4×2^5/2 = 754974720 (1,−)^2(2,+) 2×2^2×5!×4^5 × 2^2×2^5 = 125829120 (2,+)^2 6!×4^6 × 2^6 = 188743680 (2,−)^2 4!×10!×2^10 × 2^4×2^10/2 = 730573937049600 (1,−)(2,−) 2×11!×2^11 × 2×2^11/2 = 334846387814400 (3,+) 8!×3^8 × 2^8/2 = 33861058560 (1,−)(3,−) 4!×6^4 × 2^4 = 497664 (4,+) 3!×8^3 × 2^3 = 24576 (1,−) 12!×6!×2^6 × 2^12×2^6/2 = 2893072790716416000 (1,−)^3 12!×2^12 × 2^12 = 8036313307545600 (2,−) 6!×9!×2^9 × 2^6×2^9/2 = 2191721811148800 (1,−)^2(2,−) 2×11!×2^11 × 2^2×2^11/2 = 669692775628800 (1,−)(2,+) 2×2^2×5!×4^5 × 2^2×2^5 = 125829120 (2,−)(2,+) 2×2×5!×4^5 × 2^2×2×2^5/2 = 62914560 (3,−) 4!×6^4 × 2^4 = 497664 (1,−)(3,+) 4!×3^4×2×6^2 × 2^4×2^2/2 = 4478976 (4,−) 6!×4^6 × 2^6 = 188743680
3-COLOURED Conjugacy class Permutations Orientations Positions ============ ============== ============= ============================================================= e 32! × 6^32/2 = 1047084579365917383525797057070930493704282754126970880000000 (1,−)^4 16!×2^16 × 6^16 = 3868294502459441978076561408000 (1,−)^2 16!×2^16 × 6^16 = 3868294502459441978076561408000 (2,+) 8!×4^8 × 6^8 = 4438236667576320 (1,−)^2(2,+) 8!×4^8 × 6^8 = 4438236667576320 (2,+)^2 8!×4^8 × 6^8 = 4438236667576320 (2,−)^2 16!×2^16 × 6^16 = 3868294502459441978076561408000 (1,−)(2,−) 4!×14!×2^14 × 2^4×6^14/2 = 21490525013663566544869785600 (3,+) 2×10!×3^10 × 3^4×6^10/2 = 1049477429229826867200 (1,−)(3,−) 2×5!×6^5 × 3×6^5 = 43535646720 (4,+) 4!×8^4 × 6^4 = 127401984 (1,−) 8!×12!×2^12 × 6^8×6^12/2 = 144614702168868369334246834176000 (1,−)^3 16!×2^16 × 6^16 = 3868294502459441978076561408000 (2,−) 8!×12!×2^12 × 2^8×6^12/2 = 22041564116578016969097216000 (1,−)^2(2,−) 16!×2^16 × 6^16 = 3868294502459441978076561408000 (1,−)(2,+) 8!×4^8 × 6^8 = 4438236667576320 (2,−)(2,+) 8!×4^8 × 6^8 = 4438236667576320 (3,−) 2×5!×6^5 × 3×6^5 = 43535646720 (1,−)(3,+) 2×2×3^2×4!×6^4 × 3^2×6^2×6^4/2 = 235092492288 (4,−) 8!×4^8 × 6^8 = 4438236667576320
4-COLOURED Conjugacy class Permutations Orientations Positions ============ ============== ============ ============================== e 16!/2 × 12^16/3 = 644715750409906996346093568000 (1,−)^4 8!×2^8/2 × 12^8/3 = 739706111262720 (1,−)^2 8!×2^8/2 × 12^8/3 = 739706111262720 (2,+) 4!×4^4/2 × 12^4/3 = 21233664 (1,−)^2(2,+) 4!×4^4/2 × 12^4/3 = 21233664 (2,+)^2 4!×4^4/2 × 12^4/3 = 21233664 (2,−)^2 4!×6!×2^6/2 × 2^4×12^6/3 = 8806025134080 (1,−)(2,−) 8!×2^8/2 × 12^8/3 = 739706111262720 (3,+) (2×2)×4!×3^4/2 × 3^4×12^4/3 = 2176782336 (1,−)(3,−) 2×2^2×2×6^2/2 × 3^2×12^2/3 = 124416 (4,+) 2×8^2/2 × 12^2/3 = 3072 (1,−) 8!×2^8/2 × 12^8 = 2219118333788160 (1,−)^3 8!×2^8/2 × 12^8 = 2219118333788160 (2,−) 8!×4!×2^4/2 × 2^8×12^4 = 41094783959040 (1,−)^2(2,−) 8!×2^8/2 × 12^8 = 2219118333788160 (1,−)(2,+) 4!×4^4/2 × 12^4 = 63700992 (2,−)(2,+) 4!×4^4/2 × 12^4 = 63700992 (3,−) 2×2×6^2/2 × 3^2×12^2 = 93312 (1,−)(3,+) 2×2×6^2/2 × 3^2×12^2 = 93312 (4,−) 4!×4^4/2 × 12^4 = 63700992The total for each class is (2-coloured)×(3-coloured)/2 ×(4-coloured)×(class size).
TOTAL Conjugacy class Total ============ ========================================================================================================================= e 1756772880709135843168526079081025059614484630149557651477156021733236798970168550600274887650082354207129600000000000000 (1,−)^4 11497557803313571701881319062903855825682866660890902528000000 (1,−)^2 6271395165443766382844355852493012268554290905940492288000000 (2,+) 426893024140465883454209890713600 (1,−)^2(2,+) 71148837356744313909034981785600 (2,+)^2 106723256035116470863552472678400 (2,−)^2 149318932510565866258198948868881244489387878712868864000000 (1,−)(2,−) 63875321129519842788229550349465865698238148116060569600000 (3,+) 1237680706117919967859807513199071199232000 (1,−)(3,−) 43129799915034095124480 (4,+) 230844665274826752 (1,−) 1856873273785608466117989769149838721779822477836435975045120000000 (1,−)^3 137970693639762860422575828754846269908194399930690830336000000 (2,−) 11911481795714655997805044354212748848156298016980992000000 (1,−)^2(2,−) 34492673409940715105643957188711567477048599982672707584000000 (1,−)(2,+) 426893024140465883454209890713600 (2,−)(2,+) 213446512070232941727104945356800 (3,−) 32347349936275571343360 (1,−)(3,+) 1572081206902992767287296 (4,−) 1280679072421397650362629672140800 Total/384 4574929376846707924918036664273502759412720391014473055557863939959893650526399862305272865622237030657852043408965632So there are 4 574 929 376 846 707 924 918 036 664 273 502 759 412 720 391 014 473 055 557 863 939 959 893 650 526 399 862 305 272 865 622 237 030 657 852 043 408 965 632 ≈ 4.57×10^117 essentially different positions of this puzzle up to symmetry, which is about 4 octotrigintillion 575 septentrigintillion (short scale) or 4 novendecilliard 575 novendecillion (long scale).
Having calculated this, I will now attempt to create a general guide to calculate the number of positions reduced in symmetry for any sequential move puzzle:
- Find the types of the pieces (presumably by number of their stickers). Find the subtypes of the types of the pieces, based on their orbits. Find number of orientations of a single piece and permutation parities attainable by actual turns of the puzzle for each subtype (parity may be shared among more piece subtypes).
- Find all conjugacy classes of the symmetry of the shape and their sizes.
- For each conjugacy-class-subtype pair, determine how many how long cycles of pieces are formed. Dissect each such cycle set into smaller based on how are stickers within them mapped. Dissect each such cycle set into smaller within which the pieces can be permuted on the puzzle with moves and retain symmetry.
- For each such “final” cycle set, determine which cycles do the stickers form within the cycle and dissect them into subsets in a similar manner as we did with pieces in 1). Now take one piece within it and examine cycles of its stickers. You can calculate number of its possible orientations easily: if there are n k-cycles of stickers and the k-cycles span among j pieces, there will be n!×(k/j)^n possibilities. Then take the product for all such counts of stickers of the piece and determine which fraction of the orientations are attainable, giving the orientation count.
- For each conjugacy-class-subtype pair, calculate the number of positions by taking the product of all n!*k^n*o^n for all “final” cycle sets which comprise n k-cycles and can attain o orientations (which we have calculated in 4)). If the cycles in a set can achieve 1/m of their permutations because the stickers would no longer be mapped properly, use n!/m*k^n*o^n instead. If normally in this subtype 1/f of orientations of a single piece (or, in fact, of any number of pieces) would be achievable if all other were in solved state and there are cycles whose length does not divide f and in those, some of the o orientations would not be solvable in isolation, divide the product by f furthermore.
- For each conjugacy class, calculate the total number of positions by taking the product of the size of the class and the numbers of positions calculated in 5) divided adequately based on the parities of the subtypes.
- Sum all of the results in 6) for all conjugacy classes and divide the sum by size of the symmetry group of the puzzle’s shape. The result, by Polya-Burnside’s lemma, is the number of symmetrically distinct positions of the puzzles.
Sadly, I do not understand antisymmetry well enough (yet) to do corresponding calculations including antisymmetry also. I have only calculated that the number of self-inverse positions of the 4D-analogue-of-the-Rubik’s-cube should be 1 514 851 187 547 945 564 174 052 809 349 480 746 221 364 817 706 402 235 357 461 479 424.
Anyways, I hope that at least some of you found this interesting.
Yours faithfully,
Jakub
