Mathematics/Length-3 Tesseract
Note: This page is under construction.
The tesseract with side length 3 is probably the most “canonical” more-dimensional combination puzzle. This page deals with some of its mathematical properties.
The shape of the tesseract has these components:
- Cells (colours): 8 cubes {4,3}
- Faces: 24 squares {4}
- Edges: 32
- Vertices: 16
Written by Jakub Štepo. Please note that some of the calculations may be unverified.
Number of positions
If we have a pieces, we can permute them a! ways; this can be easily shown: Suppose we remove all the pieces. If we are placing the first one, there are a ways to do so. For the second piece, there are, however, only a − 1, since one is already occupied by the first piece, and both these pieces have together a × (a − 1) permutations as there are a − 1 positions of the second piece per each of the a positions of the first piece. If we continue this way, it becomes clear that there are a × (a − 1) × (a − 2) × ... × 3 × 2 × 1 (we actually have no choice for the last a-th piece), which is conventionally denoted as a!.
Now, each of the a pieces can be oriented b if it stays in place. This means that there will be ba ways to only orient the pieces if we do not permute them, because there are b orientations of the first piece per b orientations of the second piece etc.
Multiplying these numbers should give us the total number of a puzzle’s positions (there are ba orientations per each of a! permutations), but it often happens that not all of them are reachable by using legal moves, and we have to divide this figure due to constraints.
(If the pieces’ permutations have given parity, the permutation constraint c = 2 because only half of the permutations are attainable. With regard to orientations, we can say that all but last pieces have ba − 1 orientations in total and it may happen that the last piece cannot reach all orientations, so it has only b/d, where d is the orientation constraint.)
Now if we look at our puzzle in particular, we see that our pieces can be classified in several categories based on how many stickers (colours) they have. Here I list them along with how many orientations does one piece of such a category have:
| Pieces | Number | Orientations |
|---|---|---|
| 1-colour | 8 | 1 |
| 2-colour | 24 | 2 |
| 3-colour | 32 | 6 |
| 4-colour | 16 | 12 |
- Total pieces: 72 (80 if we count the immobile 8 as well)
- Total stickers: 216
Now, what the constraints are?
Let us start by analyzing what a move actually does. Each move can be broken down to rotations about a face axis, so it is sufficent to consider these only. This move creates 1 4-cycle of 2-coloured pieces, 3 4-cycles of 3-coloured pieces and 2 4-cycles of 4-coloured pieces. As such, because odd-length cycles are even permutations and vice versa, a move is an even permutation. The 4-coloured’s movement is also even permutation and so the 3-coloured’s and 2-coloured’s permutation as a whole has to be even, even though permutations of both may be odd. Out of all possible permutations, exactly half are even, forcing us to divide by 2 in these cases. This means that the permutation constraint for the 4-coloured is 2 and the 2-coloured and 3-coloured have “joint” permutation constraint of 2.
Now, looking on orientations, as a move is even permutation, the orientation constraint for both 2-coloured is 2 (orientation of the last piece is fully determined by others) and for 3-coloured is 2 (if all but last have even permutation as a whole, the last has to have one of the 3 even-permutation-orientations, and the same applies for odd permutations), but the 4-coloured are more complicated; for them, it is found to be 3 (if you are interested in how is it computed, see David Smith’s Magic120Cell calculations based on Keane and Kamack’s paper, as a similar approach is applicable to the tesseract).
Therefore, this is the number of positions:
(24! × 32!)/2 × 224/2 × 632/2 × 16!/2 × 1216/3 =
= 1 756 772 880 709 135 843 168 526 079 081 025 059 614 484 630 149 557 651 477 156 021 733 236 798 970 168 550 600 274 887 650 082 354 207 129 600 000 000 000 000 ≈
≈ 1.76 × 10120
or one vigintillion seven hundred and fifty-six novendecilliard seven hundred and seventy-two novendecillion eight hundred and eighty octodecilliard seven hundred and nine octodecillion one hundred and thirty-five septendecilliard eight hundred and forty-three septendecillion one hundred and sixty-eight sedecilliard five hundred and twenty-six sedecillion seventy-nine quinquadecilliard eighty-one quinquadecillion twenty-five quattuordecilliard fifty-nine quattuordecillion six hundred and fourteen tredecilliard four hundred and eighty-four tredecillion six hundred and thirty duodecilliard one hundred and forty-nine duodecillion five hundred and fifty-seven undecilliard six hundred and fifty-one undecillion four hundred and seventy-seven decilliard one hundred and fifty-six decillion twenty-one nonilliard seven hundred and thirty-three nonillion two hundred and thirty-six octilliard seven hundred and ninety-eight octillion nine hundred and seventy septilliard one hundred and sixty-eight septillion five hundred and fifty sextilliard six hundred sextillion two hundred and seventy-four quintilliard eight hundred and eighty-seven quintillion six hundred and fifty quadrilliard eighty-two quadrillion three hundred and fifty-four trilliard two hundred and seven trillion one hundred and twenty-nine billiard six hundred billion (long scale)
Symmetry
For our purposes, a permutation is symmetric if and only if it is equal to performing a symmetry operation on the whole tetrahedron, doing the permutation and then recoloring all stickers by substituting a colour with the colour it maps onto after the performation of the symmetry operation.
Here we compute the total number of symmetrically distinct positions, so that positions are considered with positions which they can be mapped onto with symmetry operations. My approach is patterned on Dan Hoey’s calculations. Burnside’s lemma is a useful tool, as it states that this number is equal to the average of fixed points. Therefore, the first step is to evaluate the numbers for each conjugacy class.
A conjugacy class is basically a set of simplest forms of symmetry, which cannot be broken down as combinations of simpler symmetries. The tesseract has 384 such simplest forms of symmetry, but that would be too many to describe (at least for a person as lazy as me). Luckily, we do not have to, as many of them act in similar ways. Hence, they can be grouped in classes based on their properties – conjugacy classes. For example, there are eight ways to rotate a cube around a corner by 120°, but each is in fact the same, since each does one 3-cycle of 3 adjacent face-centre-pairs (pairs consist of opposite centres). This thought will be helpful in a moment.
I describe conjugacy classes of the tesseract here with Greg Egan’s notation; his webpage was a huge help to me. 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 suitable to shorten it with exponents: Class equivalent to two-fold rotation about face axis in 3D can be 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 symmetries in it, which is the number of ways we can choose such cycles times (k − 1)! times 2k − 1 for each k-cycle.
Now that we are able to describe 4D symmetries, we can look what do they do to the puzzle.
If we perform a symmetry operation, it becomes clear that the pieces of the puzzle group in k-cycles; each of the k pieces contained in a cycle will map to another piece within the cycle after a given symmetry operation.
In j k-cycles, the cycles can exchange positions, each one can be in k different permutations and each one can have n orientations if n is the number of possible orientations of a single piece; this gives at most j! × kj × nj symmetric positions for a set of j k-cycles in a conjugacy class, and the total number of positions in it is the product of all such sets.
However, this upper bound is obviously almost never reached. Let us now discuss each of the piece types in detail.
The 2-coloured pieces and the 3-coloured pieces (as a whole) accept only even permutations. Therefore, when we calculate the final number of positions as a product of the computed numbers for 2-, 3- and 4-coloured pieces, we have to divide by 2, as exactly half of the permutations can be shown to be even.
The same applies for the 4-coloured pieces, which accept only even permutations, which means that with their permutations, we will always have to divide by 2.
The 2-coloured pieces have two orientations each, but the total number of flipped pieces has to be even. As we always flip all pieces in a cycle, it is necessary to half the number of calculated orientations if the symmetry operation creates odd-length cycles.
The total permutation of the 3-coloured pieces’ orientations has to be even, so similarly, we have to divide by 2 if there are odd-length cycles contained. Also, the symmetry causes that the 1-cycles in (1,−)(2,−) and (2,−) can have only 2 orientations (but we still have to divide by 2 as one is odd and one is even) and the 1-cycles in (3,+) and (1,−)(3,+) and the 2-cycle in (1,−)(3,−) and (3,−) can be only in 3 orientations (all are even, but with the 1-cycles, there are also 3-cycles, so we still have to half in these cases).
As only one third of the 4-coloured pieces’ orientations is achievable, we expect to have to divide by 3 unless all of the cycles’ lengths are divisible by 3 (this never actually happens), which stays true for proper rotations. For improper rotations, the alternating pieces in cycles are given opposite orientation by the symmetry operation. This means that (at least for even-length cycles), we do not have to divide at all. For the 1-cycles in (2,−), only 2 orientations are possible (the identity and an order-2 orientation), both of which are possible in isolation, meaning we do not have to divide here either. It is also important to notice one fact with the order-3 and order-6 rotations. I will illustrate it on (3,+). Suppose that the plane of rotation goes through the FRUA piece. Then the 4 1-cycles are FRUA, FRUK, BLDK and BLDA pieces. However, if one would switch FRUA with FRUK, they might notice that it can no longer have the (3,+) symmetry, because this action causes that an odd-permutation orientation would be needed in order to preserve it, and these are impossible with the 4-coloured. This problem arises when the switched pieces have odd number of common coordinates (this, however, applies only for even-dimensional spaces), so pairs FRUA-BLDK and FRUK-BLDA can be exchanged. This means that in our case, the pieces act more as if they were in two separate sets of 2 1-cycles rather than one set of 4 1-cycles. Equivalent problems arise for (3,−) and (1,−)(3,+), where we can only swap the 2-cycles between each other (and the cycles’ permutation is fully determined), but not for (1,−)(3,−), because the 2-cycles there consist of the exchangeable pairs. As for other constraints, the 1-cycles in (2,−)2 can be only in 2 orientations, the 1-cycles in (3,+) and the 2-cycles in (1,−)(3,+), (3,−) and (1,−)(3,+) can have only 3 orientations (but for proper rotations, this does never remove the necessity of dividing by 3, as for (2,−)2, there are no cycles with length that is multiple of 3, and for (3,+) and (1,−)(3,+), despite all other are, the non-identity orientations out of the 3 possible are not attainable in isolation).
Now we are able to go on to the actual 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×2^11/2 = 669692775628800 (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 = 63700992
The total for each class is ((2-coloured) × (3-coloured))/2 × (4-coloured) × (class size). We have to multiply by class size as we have to consider all symmetries of the tesseract, and although all symmetries in a conjugacy class behave the same way, we have computed this only for one its symmetry.
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,−) 127750642259039685576459100698931731396476296232121139200000 (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 4574929376846707924918036664273502759412720391014473055557864106301875758650990456653060234022928953153029428983365632
So there are 4 574 929 376 846 707 924 918 036 664 273 502 759 412 720 391 014 473 055 557 864 106 301 875 758 650 990 456 653 060 234 022 928 953 153 029 428 983 365 632 ≈ 4.57 × 10117 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).
Antisymmetry
As a curiosity, we can calculate the number of purely antisymmetric (self-inverse) positions of this puzzle. A permutation is defined to be antisymmetric if and only if it has the same effect as its “time reversal” inverse, or, in other words, is of order 2. Logically, only 2-cycles and 1-cycles (relatively to the initial state) can be formed to fulfill this property (note that here, we do not take combined action of symmetry and antisymmetry into account). We will evaluate this number for each piece type, and then make product of all such values. My calculation is based on methods of Godfrey and Kociemba.
But first, we can make a general formula. Suppose we have j pieces of a same type. If C(x,y) = x!/((x − y)!y!) means the binomial coefficient and Πx = a, b (f(x)) stands for the product of f(x) for x from a to b, there are (Πx = 1, n (C((j − 2(x − 1)),2)))/n! ways to choose n 2-cycles of those. This can be simplified to j!/((j − 2n)! × 2n × n!); let us denote that Anti(j,n).
There are 24 2-coloured pieces with two orientations each (we will write those as 1 and 2). They accept only even (odd) permutations with even (odd) permutations of 3-coloured pieces, respectively, so we will have to calculate those separately. Each 1-cycle has 2 orientations (identity or an order-2), but only half of them are attainable, and each 2-cycle has 2 orientations as well (both pieces have the same). Their odd antisymmetric positions’ count is therefore Σx = 0, 5 (Anti(24,(2x + 1)) × 22x + 1 × 224 − 2(2x + 1) − 1) and their even’s (Σx = 0, 5 (Anti(24,2x) × 22x × 224 − 2(2x) − 1)) + Anti(24,12) × 212 (the number for 12 2-cycles has been computed separately since the formula would yield only half of this value because there are no 1-cycles orientations of which we could half); these numbers are found to be equal to 109 391 445 831 696 384 and 110 864 354 430 930 944, respectively.
There are 32 3-coloured pieces with six orientations each (identity, 3 order-2 and 2 order-3). Each 1-cycle has 4 orientations (identity or any of the order-2), but calculating count of the possible ones is more complicated. If one performs one orientation of order 2, they will also have to perform another one. This means that there are C(k,2l) × 32l options for 2l pieces with nonzero orientation out of k free 1-cycles, and so Σx = 0, 16 − n (C((32 − 2n),2x) × 32x) options per n 2-cycles of 3-coloured pieces. Each 2-cycle has 6 orientations (both identity, both order-2 or each a different order-3), so number of their odd permutations is Σx = 0, 7 (Anti(32,(2x + 1)) × 62x + 1 × (Σy = 0, 16 − (2x + 1) (C((32 − 2(2x + 1)),2y) × 32y))) and of their even Σx = 0, 8 (Anti(32,2x) × 62x × (Σy = 0, 16 − 2x (C((32 − 4x),2y) × 32y))), equal to 400 534 291 178 320 764 983 751 396 556 800 and 399 990 391 831 754 132 534 501 965 889 536.
If we multiply the obtained values with corresponding parity, we get 43 815 025 217 170 182 796 090 446 219 216 231 847 240 610 611 200 odd antisymmetric positions of 2-coloured and 3-coloured pieces and 44 344 676 569 002 535 733 255 640 669 067 488 730 377 548 201 984 even ones, giving a subtotal of 88 159 701 786 172 718 529 346 086 888 283 720 577 618 158 813 184.
There are 16 4-coloured pieces with twelve orientations each (identity, 3 order-2, and 8 order-3). Each 1-cycle has 4 orientations (identity or order-2) and each 2-cycle has 12 orientations (both identity, both order-2 or each being inverse of the other order-3). They accept only even number of 2-cycles, giving Σx = 0, 4 (Anti(16,2x) × 122x × 416 − 4x) = 17 183 034 389 364 736 antisymmetric positions.
The product of these values is the final total of 1 514 851 187 547 945 564 174 052 809 349 480 746 221 364 817 706 402 235 357 461 479 424 ≈ 1.51 × 1066 antisymmetric positions of this puzzle, which is about 1 unvigintillion 515 vigintillion (short scale) or 6 undecillion 515 decilliard (long scale).
