# 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