Message #499

From: David Smith <djs314djs314@yahoo.com>
Subject: [MC4D] Re: Magic120Cell Realized
Date: Wed, 07 May 2008 05:24:01 -0000

Hi everyone,

I have just finished calculating an upper bound for the number
of permutations of the 120-Cell. To establish it is the exact answer
(which I am virtually certain of), we will have to find a number
of algorithms which I will describe in my explanation.

The calculation was only difficult in one aspect, namely the
possible orientations of the corners. Here is the upper bound:

(600!/2)*(1200!/2)*(720!/2)*((2^720)/2)*((6^1200)/2)*((12^600)/3)

To answer Roice’s question, I did find an arbitrary-precision
calculator (Googol+, trial version) that displays the entire
number in its full glory:

23435018363697222779126210606140343600982219866708667227704291465940007
37743198001537086016413748065359228217622633869330769129523601891497799
90823414733250819032377663096727895392891107724676361939174468537213471
84699260131924584724938945790242680862147295113762851571432130901040238
96149551266842769465158629370618815995041314328829732432057176063611161
23422302770133676753359134856348612503635674252607065815753807941966366
98057536512196715919594180779891338303538085006270891583549467992567391
85180535778985103137974951114346934416286264525322532242698044327455362
45594013789336900464999769975314632465421639791307831594564938014806846
43170816415770010483963217284920963354265992129473309221874222731561178
16542353296798264919536869373254412130565886195935986667368898349834998
21329543130389608025077440970771216857898162084209764122888617411552472
35969553038560987694512525780640891845410615026444483377179855326132898
75234261959552618641928258383934632570287455387991780347467121010722113
61928836844443707162412473785444967682885281547729595860180055748863425
82987146883285105106538113133816701062677558383952546932927579065352378
01699938857635611816907866063280477566711511600651402621287007177419657
47137395706297269591116929204261763967322064643743204180740840609622274
50477533328851963152796037024975768039218238701900252954269938177351575
02677389416404108346187189424180896325665818763923753999882873138580846
77228966566309226326618668840915289587325249776450099751298794240127365
82338830099863762586940626070992713912334648392737597361950653986530252
30327207836333881250393819594360829900032177090494274930448392889865527
16614065052187986459391365691818487107035801789611790557625739664732160
65851938727927023709296602229334790711981400149187774330090686038188693
91261606235286494542181170865114851849953373717543236061723434256780261
70547107650201457180103595669061215322965129698879686174938686442023883
00748340309101390837462739717879861015966407725537701315760595302551716
71986415959726651855198833270638521668923163972072488967633862968020464
59857154591489337994834077319666200102594473324166310981151194815089205
57151182894539191982468293894472660275087710846277134524865818266133054
42334380903271185037626999712118120957184637997454373033536708899691932
67133888402013848180589600375369501541798982850283307728992349369110105
46520467826426004880473115209607600645972315535718172987982451474844986
38207939550826131991321502334364118044702920268720341762396367094618866
13506333873119893045317942691097910138170606688929064386560230196639558
14850013029742851991570001253742052023463664478943640221712458729805575
31060005263175107421358143058444429499655242088655206273565212573195537
60877333581750403698478423610827287681768029874613544014049713469388295
71527311448542611407166314396015388432540041818749117638737494542689341
11177171793223712397899145235623177290619123784817857187575278090251642
14840994381181018155477448811016038175506185165844643664291009318841540
44262379730778251303396955855695117379535034691606466408011495289375314
79718119837237414217144612432890362908806009419290522751980178308626097
82557352902277742867710678069168798437309117460470080742233210420451923
51892222110034306764675636566213792404505572865844730850823909858221035
85434125488705753096939302756128054596976405648147286686571256428614441
70150339281973567744826847917503807378348535977716210565251241466128121
27489744510755607030104354706835298463258585993214964912284096487358233
65511645083418224779444054273548541176504221269485074946310915002488718
06278368621631798236853973136155878954455605260743873955312576387057492
91464434261509507888671511637033790932545587351156241243113539812047803
32568991232059877343852662991568615775896662637181748468409947337080580
40572024450182896514659885925637625707421001762988412973222775700881854
24686720928281296902412091261171945310151555961276870291126372512436270
06952830074271589382737534210078713204605113743280142889267219197170354
89582163680862223974028925034235784987192176322008136686679929878224156
10403264150753927641888742398755843764458442462577801213007109287401551
75841278684502282053918624209180100149726514306210673113609117091246135
65223035254373475279222721857792173328260547996939875237576837159815118
68437995628528234082912911481312451144148067422323644080656449490476178
69974972208660720805312515123592330897469991534040275425615810166559862
90453613626399014292854794414276344511148330328685197189376868495672292
92219730863040706516534661225522594916193135982360752630702024083643694
98309370698498093084824000430278614244379613737044583505562135097992678
05260822568001712636170958894341958120566294218192269192589063843887982
76399691863692115560126140715610109114003149849449412445547918396053785
42102203322863117771608181202015567452798664995683183676667131261081040
30610697346947842941118989099929505001072885907143020380705671971970771
74641197649400613289762440747999594711818677478380093322693390443497615
06790858102509872412149022901579978879595015323736540446504645407248271
24442974862512599608887589752218559193144931596281284315382618742792620
66616881593787942961115669105927538622586908510205223079160329890976613
24318437454227007437361053657522104635365530904941109094426111379946913
71854373062622155659107585797616686931874970164036381491924856162327083
87215983278489287122517383893445550987886905214362677925682743059318092
90715982378923238819174377671246115948128333247228319128499096287090364
06418925007261761200623236257957747401814104819201322380783299932882694
97705069648412898606682892058216414535137703172325349226036435233500060
08811101917211049364489819890827973553466812312700794247970136249599713
68830975248367892523082396738072274831267273049793679458450960225575330
90840325055925127369491405078011569600959829055592354981900265212992888
74537523085955044911868546931655826676111114140917917721449373043059908
24075969774780698659600903247322382509271117981454345778343923721701140
34040387142730946291948768518544291460594918104272439297270660195239204
69851212038726474485921192066725395225842350618752505691550098017532445
29742915483006071654290990776376332377597123229369363319211034520828156
16383626599751692734054125142693424208441259140739967321942103460390485
73512549204538199361441602981588922796564372729802637150967463996220269
92509662606254579651749991204772662937610983604733514590588466763484779
75336521786978901110936704729127455396942554264720541493172351367586278
52118009553781736752460941012653895714556808971968820220233708185524289
26324734529251413367934964381909880343066993726638347012446562279909471
00665871099287936575368913555297252102692185719691751527961183922455231
72371787084227168597930766375481134730976264840880937562376002100356262
35107696623982892463214959186113390887996406714662349935032809366747705
65928739057221107528446966775483155772142995330294320084551917275407602
87830218813852897349462068161826723496382625465167461901840049431850524
89018407136301332421978685188429040584176333209422917640992438642326814
48471988797114061727140678598275664209888253021405519815632168746508451
06268660985414101246860290152701992710734632469139060273152361598118124
26751417487110100479881455904096718779749277515897027333976945734065218
13427043475236100473238801150143720068671986307968791851735260237830993
59283951655340545557118534217560207955199404424096337283839953943573882
77230454238664055061747285720327136114251359554586129278357158728391085
51846977682603655222729137145829356583863818649600000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000

What a number!

Here is an outline of how I derived this upper bound:

First of all, we can count that the 120-Cell has 120
1-colored immobile center pieces, 720 2-colored pieces
(120*12/2), 1200 3-colored pieces (120*30/3), and 600
4-colored pieces (120*20/4). When a dodecahedral face
rotates, there are 2 5-cycles of the 2-colored pieces,
6 5-cycles of the 3-colored pieces, and 4 5-cycles of
the 4-colored pieces. Since 5-cycles are even permutations,
all permutations of each type of piece (including facelets),
will be even.

Therefore, the 720 2-coloreds can be permuted
720!/2 ways, dividing by 2 because of the even parity.
Similarly, the 3-coloreds and 4-coloreds can be permuted
1200!/2 and 600!/2 ways, respectively. Multiplying
these three terms together, we obtain an upper bound
for the number of ways the pieces can be permuted without
regards to orientation:

(600!/2)*(1200!/2)*(720!/2)

To show this number is exact, we will have to find 3 algorithms:
one that performs a 3-cycle of any three 2-coloreds without
affecting any other 2-coloreds, a 3-cycle of any three 3-coloreds
without affecting any other 3-coloreds, and a 3-cycle of any
three 4-coloreds without affecting any other 4-coloreds. These
three algorithms, when combined with each other and conjugates
(setup moves), can produce any possible permutation of the
pieces.

Now for the orientations. Since the facelets also undergo
5-cycles, all orientations will be limited to even permutations
of facelets.

Therefore 719 2-coloreds can be oriented in any of 2 ways each,
but the last will be determined by the others because of the
even parity. This results in

(2^720)/2

or 2^719 ways of orienting the 2-coloreds. To show
this number is exact, we must find an algorithm that
flips two 2-colored pieces without affecting the others.

For the 3-coloreds and 4-coloreds, I followed closely
the methods of Keane and Kamack in their paper,
"The Rubik Tesseract", modifying their arguments as neccesary
to apply them to the 120-Cell.

Any 3-colored piece can be oriented in 6 different ways.
(not three, because in four dimensions we can reflect
3-colored pieces as well as twist them!) Notice that a
twist (a 3-cycle of the facelets on that piece) is an even
permutation, while a reflection (a 2-cycle of two of the
facelets on that piece) is an odd permutation. Since the
total parity of all of the 3-coloreds must be even,
the first 1199 3-coloreds can be oriented in 6 ways each,
while the last can be oriented in only 3. (If the first
1199 3-coloreds total to an even permutation, the last
3-colored must be one of the 3 even twists, while if
they total to an odd permutation, the last 3-colored
must be one of the 3 odd reflections) This gives a total
of

(6^1200)/2

or (6^1199)*3 ways of orienting the 3-colored pieces.
To show this number is exact, we must find an algorithm
that twists one 3-colored piece without affecting the others,
and an algorithm that reflects two 3-colored pieces without
affecting the others.

Finally, the toughest part. The orientation of the 4-coloreds
required me to generalize the group theory based solution for
the corners of the 3^4 cube by Keane and Kamack to the
120-Cell.

In their paper, Keane and Kamack first describe that any
particular 4-colored piece can never be in an odd permutation
of its facelets, because the 4-coloreds split into two
different groups: the even and odd permutations, which
happen to be mirror images of each other. This rule applies
equally well to the 120-Cell.

Hence, each 4-colored piece can only be oriented in 12 ways.
(4!/2) There is an additional constraint. In their paper,
Keane and Kamack show that the orientations of 4-colored
pieces in 4D space, which form the alternating group A4,
can be divided into three sets. They describe orientations
using cycle notation of the four faces, labeled a, b, c,
and d. The subgroup N consists of the identity permutation,
(ab)(cd), (ac)(bd), and (ad)(bc). The subgroup S consists
of (abc), (adb), (acd), and (bdc). The subgroup Z
consists of (acb), abd), (adc), and (bcd).

The authors then show that the group of these three subgroups
is isomorphic to (the same as) the group of residue classes,
mod 3, with N as the identity. This means that we can assign
the number 0 to N, the number 1 to S, and the number -1 to Z,
and adding these numbers mod 3 is the same as taking the product
of elements of these three subgroups.

Notice that this entire argument applies equally well to
the 120-Cell as to the tesseract. Now the only thing left
to show is that the sum of the orientations of the 4-coloreds
(counting 0 for an orientation in N, etc.) mod 3 is always the
same, whether to the tesseract or the 120-Cell.

The orientations can be defined by assigning, to each 4-colored
piece, a letter to each facelet and each position of each
facelet. Then each orientation can be described by a 4-letter
string (e.g. ABCD) relative to the position it is occupying.

When pieces or cubies rotate in a cycle, their facelets undergo
n seperate cycles if they have n facelets. The important thing
is that there are always n disjoint cycles. In the tesseract,
every corner rotation boils down to four 4-cycles of facelets
for each cycle of four cubies. In the 120-Cell, it is the same
except it is four 5-cycles. If we can show that in
cycles of any length, the sum of the orientations of the pieces
does not change, we will have proved this for both the tesseract
and the 120-Cell.

Consider four 2-cycles:

ABCD 1
ABCD 2

Each row represents a 4-colored piece. The actual 4-cycles
are vertical in direction. For example:

ABCD 1
CDAB 2

This means that facelet A goes where facelet C was, etc.
In this example, piece 1 performed an N-twist. Now notice
that since we are dealing with 4-cycles, the facelets of
piece 2 must return to the original positions of the facelets
of piece 1. Therefore, piece 2 also performed an N-twist.
It can be checked that if piece 1 performs a Z-twist, piece
2 performs an S-twist, and if piece 1 performs an S-twist,
piece 2 performs a Z-twist. Therefore, the sum of the values
does not change. (N=0, Z=-1, S=1)

Now we can do a proof by induction to show that any four
cycles has this property. Assume that 4 k-cycles always sum
to the same amount:

ABCD
.
.
.
ABCD (not neccesarily this orientation)

Adding another piece, we are in the same position as before.
If the next-to-last piece is an N-twist when moving to the
position of the last piece, then the last piece must also
be an N-twist when moving to the position of the first piece
(since the ends of the cycles must return to their original
locations) Also, a Z-twist implies an S-twist and
an S-twist implies a Z-twist.

Therefore, no matter what the length of the cycles, the
sum of the values of the orientations never change. This
means it is true for both the tesseract and the 120-Cell.

So now we know the sums of the orientations, mod 3, never
change in the 120-Cell. Since an N-twist is 0, we can have
an isolated N-twist without affecting any other pieces.
The value S - Z must therefore be congruent to 0, mod 3.

This means that the first 599 4-colored pieces can
each be in any of 12 orientations. If the value of orientations
up to that point is 0, the remaining value must be an N-twist.
If it is 1, the remaining value must be a Z-twist, and if
it is -1, the remaing value must be an S-twist. In each case
there are four possible orientations left for the last
4-colored piece. Therefore, the upper bound for the orientations
of the 4-colored pieces is

(12^600)/3

or (12^599)*4. To prove this is exact, we must find algorithms
that show that any N-twist can be performed without affecting
the rest of the pieces, and algorithms showing that any Z-twist
can be performed along with any S-twist without affecting any
other pieces.

When we multiply these figures with the ones for permutations,
we arrive at the final answer. I sincerely hope that I did not
bother anyone by writing this very long post. I just wanted to
share my results with those that are interested.

I am not worried about finding all of the algorithms to make
this figure exact. They will probably arise naturally as we
play with Roice’s program.

I want to once again thank the members of this group for
helping me, and for putting up with my long posts!

Best Regards,

David

— In 4D_Cubing@yahoogroups.com, "Roice Nelson" <roice3@…> wrote:
>
> Awesome, I didn’t want to ask directly, but I’m excited to hear of
your
> interest in looking into the problem of the number of permutations!
I
> wonder if this particular calculation has ever been done before.
Also, I’ve
> seen and used big number calculators on the web before, so I also
had to
> wonder how easy it would be to find one that would be able to show
all the
> digits in the final answer to this problem. I hope one is out there.
>
> cya,
> Roice