Monte-Carlo and Polyhedronbased Simulations I Extremal States of the Logarithmic N-Body Pro

1

Website:http://AIMsciences.org

pp.313–341

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI:

EXTREMALSTATESOFTHELOGARITHMICN-BODY

PROBLEMONASPHERE

CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

DedicatedtoProfessorLawrenceSirovichontheoccasionofhis70thbirthday.

(CommunicatedbyKa-KitTung)

Abstract.TheproblemofNbodiesonthesurfaceofthesphereinteract-ingbyalogarithmicpotentialisexaminedforselectedNrangingfrom4to40,962,comparingtheenergiesfoundbyplacingpointsattheverticesofcer-tainpolyhedronstothelowestenergiesfoundbyaMonteCarloalgorithm.Thepolyhedronfamiliesaregeneratedfromsimplepolyhedronsthroughtwotriangularfacesplittingoperationswhichareusediterativelytoincreasethenumberofvertices.Theclosestenergyofthesepolyhedronvertexconfigura-tionstotheMonteCarlo-generatedminimumenergyisidentifiedandthetwoenergiesarefoundtoagreewell.Finallytheenergyperparticlepairisfound

1toasymptoticallyapproachameanfieldtheorylimitof−2(log(2)−1),ap-proximately0.153426,forboththepolyhedronandtheMonteCarlo-generatedenergies.Thedeterministicalgorithmofgeneratingpolyhedronsisshowntobeamethodabletogenerateconsistentlygoodapproximationstotheextremalenergyconfigurationforawiderangeofnumbersofpoints.

1.Introduction.ConsiderNpointvortices,allofuniformstrength,onthesur-x2,...󰀟xNfaceoftheunitsphere.Ifthepositionsofthesevorticesaregivenby󰀟x1,󰀟

thentheenergyofthissystemis[7][10][12][13]

󰀁

E=−log|1−󰀟xj·󰀟xk|(1)

1≤j(withpossiblyaconstantmultiplyingthesum).Extremalconfigurationsofthese

pointsareofgreatinterest.Ithasbeenseen[11]thataMonteCarlo-basedalgo-rithmisabletofindnumericallyconfigurationswhicharelocalminimumsofthepotentialenergyfunction[2].Onemayalsoapproachenergyminimumsbyalgorith-micapproacheswhichtrytouniformlyplacepointsoverthesurfaceofthesphere[3][13].Thisproblemisequivalenttothatofmaximizingtheproductofdistancesbetweenpoints,butrelatedproblemsincludethatofsphericalcodeswhichtrytomaximizetheminimumdistancebetweenpoints,ortheThompsonproblemofequalelectricalchargesonthesphere[1][4].Theserelatedproblemsyieldsimilarbutnotidenticalresults.

Inthispaperanapproachbasedonsolidgeometriesisconsidered.Asetofpointsonthesurfaceofthesphereappearsnaturallytocorrespondtotheverticesofcertainpolyhedrons(forexample,fourvorticesofuniformstrengthwillonthe

author:limc@rpi.edu.MathematicsDepartment,RensselaerPolytechnicIn-stitute,Troy,NY12180USA.

1Corresponding

313

314CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

spherereachanenergyminimumattheverticesofatetrahedron).Thisleadstotheapproachofconstructingpolyhedronsandusingthelocationsoftheverticesofthoseaspointsonwhichtoplacevorticesonthesphere.Onebeginswithabasepolyhedron,inthispaperonewithexclusivelytriangularfaces,andconstructsmorecomplexpolyhedronsfromthatshape.WiththesegeneratedpolyhedronsthenoneplacesvorticesofuniformstrengthateachvertexandstudiestheHamiltonianofthatconfiguration.

Obviouslynotallpolyhedronsmaybeusedinthisapproach.Onlypolyhedronswhichcanhaveallverticesfitonthesurfaceofthesphereareapplicable.Thesetofbasepolyhedronsusedforthispaper(section4)beginswithseveralwhichdofitthesurfaceofthesphere(andwhoseverticesfurthermorecorrespondtoanenergyminimumforvortices).Toconstructamorecomplexpolyhedrononeappliesoneofthe‘facesplitting’operations.

Eitherofthefacesplittingoperationsusedinthispaper(sections4.1and4.2)takesanexistingtriangularfaceandaddsoneormoreverticestotheportionofthesphere’ssurfaceradiallyoutwardfromthatface.Newedgesarethendrawnfromtheoriginalface’sverticestothenewverticesaddedbytheoperation,andnewfacesaredrawnamongtheoriginalandaddedpoints.Thisconstructionsplitstheoriginaltriangularfaceintomultiplenewtriangularfaces,andincreasesthenumberofverticesinthepolyhedron,butstillcreatesapolyhedronwithitsverticesonthesurfaceofthesphereandwhichmaythenbesplitagain.

Onlytwofacesplittingoperationsareconsideredastheyyieldedalargeenoughsetofshapestobeinteresting,butthereisnoreasontosupposetherearenotmoreoperationswhichcouldbeemployedbysimilartechniques.SaafandKuiljaars,studyingsphericalcoding,outlinea‘spiralplacing’ofpointswhichappearsfittabletothefaceshere[13].ThelatticesexploredbyBowick,Cacciuto,Nelson,andTravesset[4]andthetriangulationsusedbyAltschuler,Williams,Ratner,Tipton,Stong,Dowla,andWooten[1]andthoseusedbyBaumgardnerandFrederickson[3]alsosuggestfacesplittingoperationswhichcouldbeproductiveforthissortofpolyhedron-basedinvestigation.

Alsointhispaperonlyasinglefacesplittingoperationwasdoneateachiteration,withthesamesplitperformedforeveryfaceoftheoldpolyhedron.Extensionstothisroutinetosplitdifferentfacesbydifferentrulescanbeimagined,butarenotasobviouslyorganizedforconvenientstudy.

Theoriginalshapesenjoyanearlyuniformvertexdegreecount,withmostver-ticesbeingasconnectedasanyothervertexis.Itisfoundapplyingthesefacesplittingoperationsmaydisrupttheuniformityofthevertexdegrees,butarguedthatthevertexdegreesarenotofinterestinthisproblem–theedgesareanartifactofthepolyhedronsusedtoplacepointsandarenotofphysicalmeaning(section4.4).Theedgesmayberedrawnforconvenience.

Asaresultbyrepeatedlyapplyingachoiceofthefacesplittingoperationsonecancreateabinarytree-likestructureofpolyhedronsofincreasingdegree(section4.3).Asthetwofacesplittingoperationsconsideredheredonotcommutetheplacementofpoints,butdogeneratethesamenumberofpointswhicheverordertheyareappliedin(section4.5),thebinarytree-likestructureismorecompelling(section4.6).Onecancreateseveraldistinctpolyhedronswithequalnumbersofverticesandstilldifferentenergies(section5).

TheverticesofcertaingeneratedpolyhedronsarefoundtohaveenergiesclosetotheextremalstateenergyasgeneratedbyaMonteCarloalgorithm(sections2,

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI315

5).Thepolyhedronsgeneratedfromthetetrahedron(section6),fromtheoctahe-dron(section7),andtheicosahedron(section8)areexamined,tolocateminimumenergiesgeneratedbytheMonteCarlomethodforanequalnumberofvortices.TheenergyperparticlepairiscomparedforthevorticesplacedatthepolyhedronconfigurationsaswellasfortheMonteCarlo-generatedextremalstates,anditisfoundbothpairwiseenergiesagreewithoneanother(section9.1)andtend,inthelimitasthenumberofparticlesgrowsinfinitelylarge,asymptoticallytowardsameanfieldlimit[2](section9.2)(cfLim[9])whichisfoundtobeapairwiseparticleenergyofapproximately0.153426.2.NumericalTools.

2.1.MonteCarloAlgorithm.Givenasystemofnpointvortices,allofuniformstrength(assumedtobe1),thepotentialenergywillbe

z2,...,󰀟zn)=−H(󰀟z1,󰀟

n󰀁1≤jlog|1−󰀟zj·󰀟zk|(2)

forparticlesonthesurfaceofthesphere(with󰀟zj=(xj,yj,zk)thecoordinatesof

vortexj,andtheconstraintthat|󰀟zj|≡1forallj)[7][8][12].

AMetropolis-ruleMonteCarloalgorithmisemployedtofindanequilibriumconfigurationforthissystem.Eachsweepisaseriesofnexperiments,ineachofwhichonevortexis(randomly)selected.Oneachvortexaproposeddisplacementistested:Considermovingthechosenvortexbyarotationaroundarandomlyselectedaxisbyanangleuniformlydistributedon(0,󰀡).Thechangeinenergy∆Hthisrotationwouldcauseiscalculated.Basedonapreselectedinversetemperatureβ,andarandomlychosennumberruniformlydistributedon(0,1),thechangeis

󰀃󰀄acceptedifrThisprocessofconsiderationandacceptanceorrejectionisrepeatedforeachofthenexperimentsinthesweep.Thesweepsarerepeateduntileitherastatisticalequilibriumisachievedorapreselectednumberofsweepshasbeenallowedtoelapse.Inthispaperwaitingforapreselectednumberofsweepstocompleteisused.

Theuseofjustafinitenumberofsweepsbeforeconsideringthesystemtobeatornearlyattheenergyminimumisjustifiedbyfigure1,inwhichtheenergyofthesystem(pernumberofpairsofparticles)iscomparedforavarietyofnumbersofvortices.Ineachcasetheenergy(perpair)declinesrapidlyfromaninitialvalueandsettlestoanearlyuniformlevelwithinseveralhundredsweeps.Forupto642vorticiesjust500sweepssufficestoreachthisextremalconfiguration.

ItisanunavoidableconsequenceoftheMonteCarloalgorithmthatitisunlikelytoproduceexactlytheglobalminimumforanynumberofpoints.Supposethatoneparticleisoutofthis‘exact’positionbyasmallangle.ThelikelihoodthataMonteCarlosweep,whenitdoespickthisvortextomove,willpickjustthecorrectdirectionandjustthecorrectangletofitthevortexexactlyinplaceistiny.However,

316CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

Energy per Particle Pair versus Sweeps Completed0.20.180.16Energy per Particle Pair 20 32 501102586420.140.120.10.080.060100200300400500600Sweeps Completed7008009001000Figure1.Systemenergy(perpairofpoints)versusthenumberofsweepscompletedfor20,32,50,110,258,and642pointsonthesurfaceofthesphere.Convergenceoccurswithinseveralhundredsweeps,asitappearstodofortherangeofNvaluesexaminedinthispaper.

thedifficultyintheseexactmatchesiscausedbythesystemreachingaverygoodconfigurationwithinthesefirstseveralhundredsweeps–themoveswhichproducegreatdecreasesinthesystemenergyaremade,andonlyincrementalimprovementsremainavailable.

ItisalsoaconsequencethatastheMonteCarloalgorithmproducesastatisticalequilibriumitisnotguaranteedthatthepointsgeneratedarenearadynamicequilibrium.Ifeachattemptedmoveofapointmayspreadoverawideenoughregion,andtheinversetemperatureusedtodrivethesystemtowardequilibriumislargeenough,itislikelythatlocalminimumswillbeescaped.

NeverthelesstheseproblemsdopersistwiththeMonteCarloalgorithm,andresultinahandfulofanomaliessuchasthatseeninsections8.3.1and8.3.2,inwhichtheMonteCarloalgorithmdoesnot(inits40,000sweeps)reachanenergyquiteaslowasthatachievedbytheicosahedronsplitbythegeodesicwordCG(section4).

2.2.RadialDistributionFunction.Theradialdistributionfunction–atermwhichisborrowedfromthestatisticalmechanicsofgases–studiesthedensityofparticlesrelativetoauniformdensity,atagivenradiusfromanygivenreferencepoint[6].Inthispapertheuseofsuchafunctionisstraightforward–thevortex

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI317

particlesbehaveinsomewayslikeagas–andsoitservesasatoolbywhichthestructureofthesystemcanbemeasured(cf.alsoLim,Nebus,andAssad[11]).Theradialdistributionfunctionisdefinedforagivenangularseparationθ.(Thisseparationisequivalent,onthesurfaceoftheunitsphere,tothedistanceθ.)Itisconstructedheretobethesetoforderedpairsofangularseparationsθwiththenumberofpairswhichhavethatseparation.

Definition1.Forasetofparticles󰀟xj,j=1...Ndefinetheradialdistributionfunctiontobethesetoforderedpairs

D={(θ,n)|nisthenumberofpairsofpointswithseparationθ}–thatis,θisaradialseparationwithnpairsofpointswiththatseparation.Inthestudiesofgasandcrystalpropertiesfromwhichthenotionofaradialdistributionfunctionisderived,theradialdistributionfunctionistakentobethenumberofpairsseparatedbyagivenrangeofdistances,dividedbythenumberofpairswhichwouldbeexpectedinacompletelyuniformdistribution–typicallymeaningonedividesthenumberofparticlesinashellbyauniformdensitytimesthevolumeofthatshell[6].Forthispaperthatnormalizationisnotused.

Inthispapergraphsoftheradialdistributionfunctionsaresimplifiedbygrouping

πapart,makingtheplotsrepresentthenumberstogetherangleswhichare∆θ=180ofverticesperdegreeapart.

3.TheMeanFieldLimit.Theproblemofpointvorticesonthesphereisbe-lievedtotakeonameanfieldlimitasthenumberofparticlesgrowsinfinitelylarge(cfBergersen’scalculationsin[2]).Onecanestimatetheexpectedenergyperparti-clepairforthiscontinuumlimitbecauseasthenumberofparticlesgrowsinfinitelylargethemostprobablevorticitydistributionbecomesauniformdensityρ.Thenonecalculatestheexpectedtotalenergytobe

󰀂󰀂1

ρ2log|1−󰀟x·󰀟y|dAdA󰀁E=−

2DD󰀁whereDisthesurfaceoftheunitsphere,dAisat󰀟xanddA󰀁isat󰀟y.Thefactor12wasintroducedtopreventdoublecountingofeachparticlepair.Ifonefirstkeep󰀟x

󰀁

atθ=0andperformtheintegrationoverdA,onehas

󰀂󰀂1

E=−ρ2log|1−cos(θ󰀁)|dAdA󰀁

2DD󰀁

󰀂2π󰀂󰀂π

12󰀁

=−ρdAdφdθ󰀁log|1−cosθ󰀁|sinθ󰀁(4)

200D

󰀂12

=−ρdA2π(2log2−2)

2D

NowifoneintegratesoverdA,onewouldget

1

E=−ρ28π2(2log2−2)

2

NForsufficientlylargefinitevaluesofN,bysettingthevortexdensityρ=4πinequation4,oneobtainsthefollowingboundsfortheexpectedtotalenergyEN

(3)

0≤EN≤

1N2

(2log2−2)−22

318CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

withENthemostprobableenergyforthisuniformlyspreadpointparticles.Butmorethanthat,themeanfieldlimit(ifitholds)statesthat

EN

N−>∞N2lim

1

=−(log2−1)∼0.153426

2

Thusasthenumberofvorticesgrows,themeanfieldenergyperparticlepairwillapproachaconstantofapproximately0.153426.Thenumericalresultsexaminedinsection9.2andplottedinfigures9and10stronglysupporttheexistenceofthismeanfieldlimitinthisproblem.

4.PolyhedronShapes.Beginwithaconvexpolyhedronwithfacescomposedentirelyoftriangles.Thoughthefacesneednotberegular,thePlatonicsolidsofthetetrahedron,theoctahedron,andtheicosahedronformausefulbasicsetand(asisseeninsections6.1,7.1,and8.1)allrepresentextremalstatesforthevortexproblemwiththecorrespondingnumberofvortices.

DaudSuttonconsiders[14]manypolyhedronshapeswhichmaybeconstructedbyperformingseveraloperationsonpolyhedraoffewervertices.Suchoperationsincludethetakingofdualstoexistingpolyhedra,truncatingtheverticesofashape,compoundingofseveralpolyhedratogether,twistingofedges,andthelike.Thisopensagreatarrayofshapestoconsider.Forthispaper,aminimalsetofoperations–calledthecentroidsplitandthegeodesicsplit–areusedtoconstructrobustfamiliesofpolyhedra.4.1.CentroidSplitting.

Definition2.TheCentroidsplitofatriangleABCistoaddtoitapointDwheretheraybeginningatthecenterofthesphereandpassingthroughthecentroidofABCintersectsthesphere,andaddingtothepolyhedrontheedgesAD,BD,andCD.

ThisconstructiondoesnotpreservethedegreesoftheoriginalpointsA,B,orC,butitisarguedinsection4.4suchdegreecountsarearbitrarypropertiesanddonotrequireanyattention.

Thissplittingincreasesthenumberofverticesinthepolyhedronbythenumeroffaces,triplesthenumberoffaces,andaddsthreetimesthenumberoffacestothenumberofedges.Fromthisconstructionthecountofvertices,edges,andfacesinthenewpolyhedronis:

v󰀁e󰀁f󰀁

=v+f=e+3f=

3f,

(5)

Anapparentanomalyofthecentroidsplittingisthatcertainconfigurationsmayappeartocreateasquarefacefromwhatwasoriginallyapolyhedronwithonlytriangularfaces–notably,ifonetakesthecentroidsplitofaregulartetrahedrontheresulthasverticesatthecornersofthecube.Ifonedoesnotlosetheedgeinformationasoriginallycreatedthiseffectwillnotpropagate–eitherthegeodesicorthecentroidsplitafterthisshapewillrestorethefiguretowhatareclearlytriangularfaces.

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI319

Figure2.Anexampleofthecentroidsplit.ThecentroidoftheplanartriangleABCisadded,andthenthepointatwhichtherayfromthecenterofthespherepassingthroughthiscentroidisaddedasD.TheedgesAD,BD,andCDareadded.

4.2.GeodesicSplitting.

Definition3.TheGeodesicsplitofatriangleABCistoaddtoitapointEwheretherayfromthecenterofthesphereandpassingthrughthemidpointofABintersectsthesphere,apointFsimilarlybasedonthebisectionofBC,andapointGsimilarlybasedonthebisectionofCA,andaddingtothepolyhedrontheedgesEF,FG,andGE,andfurthermoreaddingedgesAEandEBinplaceofAB,addingedgesBFandFCinplaceofBC,andedgesCGandGAinplaceofCA.Thissplittingpreservesthedegreesoftheoriginalpolyhedron’svertices,andaddsonlyverticesofdegreesix.

Thissplittingincreasesthenumberofverticesinthepolyhedronbythenumberofedges,quadruplesthenumberoffaces,anddoublesandthenaddsthreetimesthenumberoffacestothenumberofedges.Fromthisconstructionthecountofvertices,edges,andfacesinthenewpolyhedronis:

v󰀁e󰀁f󰀁

=v+e=2e+3f=

4f,

(6)

320CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

Figure3.Anexampleofthegeodesicsplit.ThemidpointsofgeodesicsAB,BC,andCAareaddedasthepointsE,F,andGrespectively,andthentheedgesEF,FG,andGEareadded.

4.3.GeodesicWords.Byapplyingthecentroidandgeodesicsplittingsrepeat-edlyfromanoriginalshapeafamilyofrelatedpolyhedronsmaybeconstructed.LettingCstandforacentroidsplitandGstandforageodesicsplitonecancon-structageodesicwordfromabasicpolyhedrontomuchmoercomplexshapes.Definition4.AGeodesicWordisastringofCandGoperationsrepresentingtherepeatedsplittingoffacesofabasicpolyhedron.

AsexamplethewordCCCGrepresentsthreecentroidsplitsandthenageodesicsplitfromoneoftheoriginalpolyhedrons.

4.4.VertexDegreesbyVoronoiMethods.Awell-knownresultinthestudyofpolyhedrons[14]composedprimarilyoftriangleandsquarefacesrelatesthenumberofverticesandtheirdegreestogether,andholds

2v4+v5−v7−2Q=12

(7)

wherev4isthenumberofverticesofdegreefour,v5thenumberofverticesofdegreefive,v7thenumberofverticesofdegreeseven,andQthenumberofsquarefaces.Inapplyingthegeodesicsplittingofafacevorticesofonlydegreesixarecreated,andsothenewpolyhedronsatisfieswithouteffortintotheaboverelationship.In

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI321

thecentroidsplit,however,thedegreesofallexistingverticesaredoubled,andanumber(equaltothenumberoffacesinthepolyhedronbeingsplit)ofnewverticesofdegreethreearecreated,resultinginashapewhichdoesnotimmediatelyfitthisrelationshipatall.

Thereforeifthecountofvertexdegreesisofinterest–thoughformechanicalpropertiessuchasthesystem’spotentialenergyitisnot,sincetheedgeshoweverdrawndonotchangethelocationsofverticesandthereforedonotaffecttheme-chanicsatall–eithertherelationshipofequation7mustbeabandonedoronemustredrawvertexedgesaftereachcentroidsplit.Iftheedgelinesareredrawn,andnewtriangularfacescreated,aregularalgorithmforsuchredrawingisnecessary.OnesatisfactoryalgorithmistouseamethodbasedonVoronoidiagrams.Definition5.Avertexdegree,afterredrawing,isequaltothedegreeofthepolygonwhichsurroundsthatvertexoncetheVoronoidiagrambasedonthesetofallthepolyhedron’sverticeshasbeendrawn.

AVoronoidiagramtakesabasesetofNpointsanddividesthedomainintoNregions,eachofwhichconsistsofthepointsclosesttoexactlyonepointoftheoriginalbaseset.Theboundariesoftheseregionswillbepolygons,inthiscaseonthesurfaceofthesphere.

xjifandonlyiftheregionsurrounding󰀟xiisDrawanedgefrompoint󰀟xito󰀟

adjacenttothatsurrounding󰀟xj.Thisnewsetofedgesbasedonthecentroidalgorithmrestorestheverticeswhichhadoriginallybeendegreefivetothatdegreeagain,restoresthosewhichhadbeendegreesixtothatagain,andsetsthenewverticestodegreesix.Asaresulttherelationship7again.

Thismethodbreaksdown,bycreatingnontriangularfaces,iftwoormoread-jacentfacesofthesplitpolyhedronarecoplanar.EffectivelyifthefigurehasanontriangularfacetheVoronoi-basedredrawingofedgeswillpropagatethatnon-triangularface.

4.5.NoncommutivityofCandGoperations.AcursoryexaminationofthetheresultofwordsCGandofGConanytrianglefacesuggeststheoperationsmaycommute.Ineitherordertheoriginalfaceissplitintotenpoints,anddrawingtheeffectsoftheseoperationsonaplanartrianglereinforcesthissuggestion.

Theorem1.Foratrianglerestingintheplane,thecentroidsplitandthegeodesicsplitofthattrianglearecommutativeoperations.

Proof.LettriangleABCrestintheplane.AcentroidsplitcreatesthepointDandtheedgesAD,BD,andCD.ThegeodesicsplitofthiscreatespointEbisectingAB,pointFbisectingBC,pointGbisectingCA,pointHbisectingAD,pointIbisectingBD,andpointJbisectingCD.

Nowconsiderthegeodesicsplitfollowedbythecentroidsplit.AgainontriangleABC,letpointE󰀁bisectAB,F󰀁bisectBC

D󰀁∼DasthetriangleE󰀁F󰀁G󰀁issimilartoABC,withedgeE󰀁F󰀁paralleltoAB,F󰀁G󰀁paralleltoBC,andG󰀁E󰀁parallelCA.H󰀁∼HbecauseAE󰀁G󰀁issimilartoABC,withthelengthAE󰀁halfthatofAB(andsoon),thereforethedistancefromAtothecentroidH󰀁ishalfthedistancefromAtothecentroidD󰀁.BysimilarargumentsI󰀁∼IandJ󰀁∼J.

Thusontheplanethecentroidandgeodesicsplittingsofatrianglecommuteintheirplacementofpoints.

322CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

Figure4.Anillustrationofhowthecentroidandgeodesicsplitsmaybeexpectedtocommute.AsconstructedontheplanethetriangleAEGmustbesimilartoABC(andsimilarlyEBFandGFCarealsosimilartoABC),makingitpossibletoshowthecentroidandgeodesicoperationsmaybeperformedineitherorder.However,similartrianglesdonotexistonthesurfaceofthesphereandsotheproofbreaksdown.Figure5providesanexampleoftheCGwordresultingindifferentpointsthantheGCworddoes.

Corollary2.Forasphericaltrianglethecentroidandgeodesicsplittingsdonotcommute.

Proof.Commutivityholdfortrianglesonthesurfaceofthesphere,whichformthegeometryusedinthesepolyhedronsplittings.CriticaltotheproofofthecommutivityintheplaneistheuseofsimilartrianglestoshowtheequalpositioningofpointsHandH󰀁,ofIandI󰀁,andofJandJ󰀁.Similartrianglesdonotexistonthesurfaceofthesphereandasaresulttheproofdoesnothold–andinpracticeanexaminationofthedifferencebetweenCGandGCstartingfromasimplepolyhedronshowsthis.Figure5showsanexampleofthesenoncommutingoperations.Whilethegraphsofvertexpositionsmaynotbeobvious,thedifferencesbetweentheirradialdistributionfunctionsdemonstratetheycannotbeequivalentconfigurations:oneisnotarotationorreflectionoftheother.

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI

Octahedron CGOctahedron GC323

110.50.500-0.5-0.5-110.50-0.5-1-10-0.50.51-110.50-0.5-1-10-0.50.51Octahedron–CGRadial Distribution Function,Octahedron CG140140120120Octahedron–GCRadial Distribution Function,Octahedron GC1001008080606040402020020406080100120140160180020406080100120140160180RadialDistributionFunction–CGRadialDistributionFunction–GCFigure5.TheoctahedronsplitfirstbythegeodesicwordGCandthenbythewordCG,showingthefinalpolyhedronstonotbeidentical.

Itisworthnotingthatastheareaofasphericaltriangledecreases–asthetrianglegetsclosertobeingplaner–thecentroidandgeodesicsplitscomeclosertocommuting,inthattheresultsofaCGandofaGCoperationresultinsetsofpointswhichareclosertooneanother.Thisisultimatelyreflectednumericallyintheenergiesofpolyhedronssplitbylonggeodesicwordsbegintovaryonlyslightlywhentheydifferonlyinthelasttwoletters–andthisdoesnotnecessarilytakemanysplits.Wordsasshortasthreeletterscanseetheirlasttwoletterscomenearcommuting.

4.6.PolyhedronTrees.Fromanyreferencebasepolyhedronwhichhasonlytri-angularfacesonecanperformgeodesicwordsplittingsoneachofthefaces.Iftheyareonthesurfaceofthespheretheneverygeodesicwordrepresentsanewpolyhe-dron.Aseachsplitmaybeeitheracentroidorageodesicsplit,thestructureofabinarytreeissuggested,eachgeodesicwordcorrespondingtoonebranch.Definition6.APolyhedronTreeisthebinarytreeconstructedbytakingapoly-hedronbaseandapplyingtoitallgeodesicwords.

Onemaybuildatreeofpolyhedronsbelongingtooneofseveralfamiliesandsocoveringagreatnumberofpossiblenumbersofvertices.Althoughthenumberofgeodesicandcentroidsplitsinaworddefinesthenumberofverticeswhichwillarisefromthatsplittingbeingperformedonabasicshape,thenoncommutivityofthoseoperationsonthesurfaceofthesphereresultsindistinctpolyhedronsforeachcase.

324CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

WordTetrahedronOctahedronBaseShape46C814G1018CC2038CG2650GC2650GG3466CCC56110CCG74146CGC74146CGG98194GCC74146GCG98194GGC98194GGG130258CCCC164326CCCG218434CCGC218434CCGG290578CGCC218434CGCG290578CGGC290578CGGG386770GCCC218434GCCG290578GCGC290578GCGG386770GGCC290578GGCG386770GGGC386770GGGG5141026Icosahedron12324292122122162272362362482362482482642812108210821442108214421442192210821442144219221442192219222562

Figure6.Vertexcountsforgeodesicwordsplittingsfromseveralpolyhedronbases.Thenumberofvertices,aswellasthenumbersoffacesandedges,maybederivedfromformulas5and6.

Forthefirstgenerationsofpolyhedronssplitoffthebasepolyhedraofthetetra-hedron,octahedron,andicosahedrononehasthistableofvertexcountsforthewordsoflengthuptofour:

Thetablecanclearlybeextendedindefinitely,withthewordsoflengthngener-ating2nuniquevertexconfigurations,butonlyn+1distinctnumbersofvertices.AlthoughinthefirstfewbranchesofthistreeitisnotobservedthatanynumberNmaybegeneratedbytwogeodesicwordswhichhavedifferentnumbersofcentroidandgeodesicsplits(whetherworkingfromthesameordifferentbasepolyhedra),itisnotassertedthatanygivennumbermaybegeneratedfromatmostonebasepolyhedronandnumberofcentroidandgeodesicsplits.

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI325

Severalpolyhedraofinterestaregeneratedbythesebranches:thetetrahedronsplitbyC,forexample,isthecube,andtheicosahedronsplitbyCisthetrun-catedicosahedron(anditsowndual).Extremelyfewofthesepolyhedraareknown“interesting”configurationssuchasPlatonicorArchimedeansolids.

Symmetryconsiderationsleadonetoexpectthebasicshapesofthetetrahedron,octahedron,andicosahedronwillrepresentequilibriumconfigurationsforthevortexproblem–vorticesplacedattheverticesofthesepolyhedraontheunitspherewillremaininplace.Similarlyoneexpectsanynumberofpurelygeodesicsplits,orachainofgeodesicsplitsfollowedbyonecentroidsplit,toproduceanotherequilibrium.

5.NumericalResults.ExaminedinthissectionistheagreementbetweentheresultsoftheMonteCarloalgorithmandtheconfigurationofseveralknownpoly-hedronvertices.Initialsuccessesinmatchingtheconfigurationsofpointsforshapessuchasthetetrahedronandtheoctahedronsuggestregularpolyhedronsmayrepre-sentextremalstatesfortheproblemofvorticesonthesurfaceofthesphere.Thisishowevernotthecase,asexaminationoftheproblemwith8vorticesdemonstrates–therectangularantiprismisashapewithalowerenergythanthecubehas.Thenumericalresultsderivedherewererunfor40,000sweepsoftheparticles,withaninversetemperatureβof100,000,000.Themaximumanglebywhichanyvortexwasallowedtomovewas0.05radians.Therandomnumberseedusedwasthetimeofday,andthecalculationsperformedbycomputersrunningMatlab(andreliantuponitsbuilt-inrandomnumbersequencegenerator).Thesourcecodesareavailableuponrequest.

ThefirstsubsectionsofeachoftheseconfigurationsistheresultnotofaMonteCarlosimulation,butrathertheresultofusingtheprecisecoordinatesofthever-ticesofapolyhedronasderivedbyperformingthespecifiedsplitsonthefacesofthetetrahedron,octahedron,oricosahedron.Theuseoftheseshapesforreferencevalidatestheroutineswhichcalculatesystemenergy,radialdistributionfunction,andwhichplotthepositionsofthesepoints.Themapsoftheplotsareanunpro-jectedlatitude-longitudesystem,unfortunatelydistortingtoanextenttheanglesbetweenvortexpairsandoccasionallymakingaconfigurationdifficulttoidentify,asinsections6.1.1and6.1.2inwhichbothgraphsdisplayingthesamestateisnotimmediatelyobvious.

EachfinalsubsectionistheresultofaMonteCarlosimulationonthecorre-spondingnumberofvorticesalongwiththeenergyofthatstate.ThisisexpectedtobeatorneartheextremalstateenergyforthecorrespondingnumberofvorticesduetotheabilityoftheMonteCarloalgorithmtoescapelocalenergyminimumsandfindeventuallytheglobalminimum.

6.TheTetrahedronTree.6.1.FourPoints.

6.1.1.Tetrahedron.ThetetrahedronisoneofthePlatonicsolids[5]andisacom-monlyrecognizedshape.Inthevortexproblemitisadynamicequilibrium.

326CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

StateEnergy:-1.72609243Latitude-Longitude Plot,Tetrahedron1.56Radial Distribution Function,Tetrahedron150.5403-0.52-11-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure6.1.1aRadialDistributionFunction

Figure6.1.1b

6.1.2.FreeParticles.Fourparticlesfindthetetrahedron.AstheMonteCarloalgo-rithmhasnomeansofdetectinglatitudetheconfigurationis‘pointed’inarandomlychosendirection.Becauseofthis,andthedistortionofanglesandareasforcedbyprojectingthesurfaceofthesphereontothelatitude-longituderectangleplotted,thetetrahedronisnotobviousasplotted(asseveralothershapeswillnotbeobviousfromtheirplots,asinsections7.1.2and6.2.2).Theenergyandradialdistributionfunctionindicatethetetrahedronhasbeenfound.

StateEnergy:-1.72609239Latitude-Longitude Plot,Monte Carlo, 4 points1.56Radial Distribution Function,Monte Carlo, 4 points150.5403-0.52-11-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure6.1.2aRadialDistributionFunction

Figure6.1.2b

6.2.EightPoints:Single-LetterWords.6.2.1.CSplit.

StateEnergy:-1.35919229Latitude-Longitude Plot,Tetrahedron C1.512Radial Distribution Function,Tetrahedron C1100.5806-0.54-12-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMapFigure6.2.1aRadialDistributionFunctionFigure6.2.1b

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI327

6.2.2.FreeParticles.

StateEnergy:-1.44791144Latitude-Longitude Plot,Monte Carlo, 8 points1.58Radial Distribution Function,Monte Carlo, 8 points7160.55043-0.52-11-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure6.2.2a

6.3.26Points:Two-LetterWords.6.3.1.CGSplit.

RadialDistributionFunction

Figure6.2.2b

StateEnergy:52.04024268Latitude-Longitude Plot,Tetrahedron CG1.590Radial Distribution Function,Tetrahedron CG180700.56005040-0.530-12010-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure6.3.1a

6.3.2.FreeParticles.

RadialDistributionFunction

Figure6.3.1b

StateEnergy:51.26225521Latitude-Longitude Plot,Monte Carlo, 26 points1.512Radial Distribution Function,Monte Carlo, 26 points1100.5806-0.54-12-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMapFigure6.3.2a

6.4.98Points:Three-LetterWords.

RadialDistributionFunctionFigure6.3.2b

328CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

6.4.1.CGGSplit.

StateEnergy:1218.58714521Latitude-Longitude Plot,Tetrahedron CGG1.5Radial Distribution Function,Tetrahedron CGG25012000.50150-0.5100-150-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure6.4.1a

6.4.2.FreeParticles.

RadialDistributionFunction

Figure6.4.1b

StateEnergy:1210.13160347Latitude-Longitude Plot,Monte Carlo, 98 points1.590Radial Distribution Function,Monte Carlo, 98 points801700.56050040-0.53020-110-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure6.4.2a

7.TheOctahedronTree.7.1.SixPoints.

RadialDistributionFunction

Figure6.4.2b

7.1.1.Octahedron.TheoctahedronisanotherPlatonicsolid.Itisclearlyanequi-libriumandtheevidenceofMonteCarloexperiments(section7.1.2)indicatesitisalsoanenergyminimum.

StateEnergy:-2.079441541679841.5121100.5806-0.54-12-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMapFigure7.1.2aRadialDistributionFunctionFigure7.1.2b

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI329

7.1.2.FreeParticles.Sixfreeparticlesmovetowardstheextremalstate,whichistheoctahedronconfigurationseeninsection7.1.2.

StateEnergy:-2.07944143162953Latitude-Longitude Plot,Monte Carlo, 6 points1.512Radial Distribution Function,Monte Carlo, 6 points1100.5806-0.54-12-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure7.1.2a

7.2.14Points:Single-LetterWords.7.2.1.CSplit.

RadialDistributionFunction

Figure7.1.2b

StateEnergy:6.29252876Latitude-Longitude Plot,Octahedron C1.5Radial Distribution Function,Octahedron C1200.515010-0.5-15-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure7.2.1a

7.2.2.FreeParticles.

RadialDistributionFunction

Figure7.2.1b

StateEnergy:6.26082162Latitude-Longitude Plot,Monte Carlo, 14 points1.518Radial Distribution Function,Monte Carlo, 14 points161140.5121008-0.564-12-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMapFigure7.2.2a

7.3.50Points:Two-LetterWords.

RadialDistributionFunctionFigure7.2.2b

330CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

7.3.1.CGSplit.

StateEnergy:266.54209732Latitude-Longitude Plot,Octahedron CG1.5140Radial Distribution Function,Octahedron CG11201000.580060-0.540-120-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure7.3.1a

7.3.2.FreeParticles.

RadialDistributionFunction

Figure7.3.1b

StateEnergy:266.05829961Latitude-Longitude Plot,Monte Carlo, 50 points1.535130Radial Distribution Function,Monte Carlo, 50 points0.52502015-0.510-15-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure7.3.2a

7.4.194Points:Three-LetterWords.7.4.1.CGGSplit.

RadialDistributionFunction

Figure7.3.2b

StateEnergy:5192.17477404Latitude-Longitude Plot,Octahedron CGG1.550045014003500.53000250200-0.515010050-1.5-3-2-101230Radial Distribution Function,Octahedron CGG-120406080100120140160180Latitude-LongitudeMapFigure7.4.1a

7.4.2.FreeParticles.

RadialDistributionFunctionFigure7.4.1b

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI331

StateEnergy:5186.55694273Latitude-Longitude Plot,Monte Carlo, 194 points1.5Radial Distribution Function,Monte Carlo, 194 points20010.51500100-0.550-1-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure7.4.2aRadialDistributionFunction

Figure7.4.2b

8.TheIcosahedronTree.

8.1.12Points.

8.1.1.Icosahedron.WithtwelvevorticesonehastwopolyhedronconfigurationsasprovidedbyCoxeter’sarrayofPlatonicsolidsandtheirduals[5].Thefirstoftheseistheicosahedron.Theicosahedronisnottheonlyconfigurationoftwelvevorticeswithanalyticallyknownpoints;anotherconfigurationisthecuboctahedron.ThecuboctahedronisnotfoundbyaMonteCarloexperimentwithfreeparticles.

StateEnergy:2.53542345606662Latitude-Longitude Plot,Icosahedron1.530Radial Distribution Function,Icosahedron1250.520015-0.510-15-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure8.1.1aRadialDistributionFunction

Figure8.1.1b

8.1.2.FreeParticles.Twelvefreeparticlesmovetowardstheicosahedronshape.Thoughthelatitude-longitudeplotsarenotobviouslyidentical,theirradialdistri-butionfunctionsmatchpreciselyandtheirenergiesareverynearlyequal.

332CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

StateEnergy:2.53542467Latitude-Longitude Plot,Monte Carlo, 12 points1.530Radial Distribution Function,Monte Carlo, 12 points1250.520015-0.510-15-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure8.1.2a

8.2.32Points:Single-LetterWords.8.2.1.CSplit.

RadialDistributionFunction

Figure8.1.2b

StateEnergy:89.04326633Latitude-Longitude Plot,Icosahedron C1.560Radial Distribution Function,Icosahedron C1500.540030-0.520-110-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure8.2.1a

8.2.2.FreeParticles.

RadialDistributionFunction

Figure8.2.1b

StateEnergy:89.04373997Latitude-Longitude Plot,Monte Carlo, 32 points1.545Radial Distribution Function,Monte Carlo, 32 points401350.53025020-0.51510-15-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure8.2.2a

8.3.122Points:Two-LetterWords.8.3.1.CGSplit.

RadialDistributionFunction

Figure8.2.2b

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI333

StateEnergy:1942.05613972Latitude-Longitude Plot,Icosahedron CG1.5400Radial Distribution Function,Icosahedron CG13503000.52500200-0.5150100-150-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure8.3.1a

8.3.2.FreeParticles.

RadialDistributionFunction

Figure8.3.1b

StateEnergy:1942.36355642Latitude-Longitude Plot,Monte Carlo, 122 points1.5120Radial Distribution Function,Monte Carlo, 122 points11000.580060-0.540-120-1.5-3-2-10123020406080100120140160180Latitude-LongitudeMap

Figure8.3.2a

8.4.482Points:Three-LetterWords.8.4.1.CGGSplit.

RadialDistributionFunction

Figure8.3.2b

StateEnergy:33965.73014674Latitude-Longitude Plot,Icosahedron CGG1.518001160014000.512001000800-0.5600400200-1.5-3-2-101230Radial Distribution Function,Icosahedron CGG0-120406080100120140160180Latitude-LongitudeMap

Figure8.4.1a

8.4.2.FreeParticles.

RadialDistributionFunction

Figure8.4.1b

334CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

StateEnergy:33965.34803522Latitude-Longitude Plot,Monte Carlo, 482 points1.510009008000.57006000500400-0.5300-1200100-1.5-3-2-101230Radial Distribution Function,Monte Carlo, 482 points120406080100120140160180Latitude-LongitudeMap

Figure8.4.2a

9.PolyhedronResults.

RadialDistributionFunction

Figure8.4.2b

9.1.SplitPolyhedronsandExtremalStates.Thevortexinteractionenergy,asoneexpectsfromconsiderationsofthemeanfieldtheory–orsimplyfromob-servingthatthenumberofparticlesisincreasingandthereforethenumberofpairsincreasingasthesquareofthenumberofpoints[2]–growsquadraticallyintermsofthenumberofvortices.ThisgrowthisindependentofwhetherthevorticesarearrangedattheverticesofapolyhedronorwhethertheyareallowedtofindaextremalstatebytheMonteCarloalgorithm,asindicatedbyfigures7and8.Thetablesinthissectionpresenttheminimumstatesforthefirstfewlengthsofgeodesicwordsbasedonthepolyhedronsofthetetrahedron,theoctahedron,andtheicosahedron.Thesefigures,eachPlatonicsolidswithfacescomposedoftriangles(withverticesuniformlyofdegreethree,four,andfive,respectively)andsoenjoyconsiderablerotationalsymmetry.Theyarealsoknowntobeextremalstatesfortheircorrespondingvortexproblemandaredynamicequilibriums.IneachtablethestartingpolyhedronandthegeodesicwordusedtogenerateaconfigurationofNpointsisgiven,andtheenergyofthepolyhedronasgeneratedbythatgeodesicwordisprovidedandcomparedtotheenergyoftheextremalstateasfoundbytheMonteCarlomethod(section2.1).

Thepolyhedron-basedenergiesandtheMonteCarloextremalstateenergiesdisagreeinalmosteverycasebesidesthebasicpolyhedrons.SeveralpolyhedronconfigurationsapproachtheMonteCarloenergyclosely,andinonecase–theIcosahedronsplitbyCG–thepolyhedronenergyisbelowthatoftheMonteCarloenergy.ThisreflectsthattheMonteCarloalgorithmdoesquicklyreachapointneartheenergyminimum,butisslowtothenreachexactlytheenergyminimum.Thereisarelativelysmallregionofphasespacewhichneedstobereached,andafiniterunmayneverthelessnotbelongenoughtoreachit.InsupportofthatargumentonenotestheMonteCarloextremalstateenergyforthetetrahedron,octahedron,andicosahedronareveryslightlyhigherthanthepolyhedronideals,thoughtheMonteCarloextremalstatesareextremelynearthegeodescword-generatedpositions.Inthepolyhedronsgrownfromtheoctahedrontheagreementbetweenpolyhe-dronenergiesoflongerwordsasthefinalgeodesiclettersarereversedgrowsslightlybetter.IntheshapesgrownfromtheicosahedroneventheCGwordhasanagree-mentinenergiesaboutatenthofapercenttotheMonteCarlo-generatedextremalstateenergy.TheCGGstatedoesnotagreeastightlywiththeextremalstateenergy,butitisstillinexcellentagreement.

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI

Energy from Polyhedron Configurations versus Number of Particles335

10710610510Energy104310210110110010210Number of Points3104PolyhedronConfigurationsFigure7.Thesystemenergyasafunctionofthenumberofpar-ticlesfortheexaminedpolyhedrons.

TheradialdistributionfunctionasgeneratedbytheMonteCarloroutineisclosertoauniformdistribution–notethatthedistributionisclosetoasinusoidalcurve–whereastheradialdistributionfunctionsforpolyhedronsgeneratedbygeodesicwordshavefewerandrarerpeaks,amuchmorecrystallineconfiguration.9.2.PairwiseInterationEnergies.Fromobservingthattheenergyofthesys-temgrowsasthesquareofthenumberofparticles(asderivedbyBergersenetal[2])–thatis,thenumberofpairsofparticlesinthesystem–thequestionofwhattheaverageenergyofinteractionofapairmightbeisraised.Figures9and10andthetablesinthissubsectionrepresenttheenergiesofthesystemdividedbyN(N−1),bothforthepolyhedronsasgeneratedbythegeodesictreesgrownfromthetetrahedron,octahedron,andicosahedron,andfortheMonteCarloextremalstateenergyfoundforthecorrespondingnumberofpoints.

Asmaybeexpectedfromthequadraticgrowthofenergyterms,oncethenum-berofpointsgrowsmoderatelylarge,thepairwiseenergyappearstoapproachaconstantapproximately0.15.Asmaybeexpectedfromtherelativelylowvariationinsystemenergiesdespitethenoncommutivityofcentroidandgeodesicsplitsthepairwiseenergydependsonlyslightlyonthegeodesicword.

ThepairwiseMonteCarloenergytendstohaveaslightlylowervaluethanthatofthepolyhedron-basedconfiguration.

Itisclearthatforanyfinitenumberofvorticesthesystemenergy–andthusthepairwiseenergy–maybemadearbitarilylarge,bytheexpedientofmovingat

336CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

Energy from Monte Carlo Run versus Number of Particles107106105104Energy10310210110010-110-210110210Number of Points3104MonteCarloextremalstateFigure8.Thesystemenergyasafunctionofthenumberofpar-ticlesfortheextremalstateasfoundbyaMonteCarloalgorithm.NTetrahedron4C8CG26CGG98NOctahedron8C14CG50CGG194

N123212248210823242

PolyhedronEnergyMonteCarloEnergy-1.72609243-1.72609239-1.35919229-1.4479114452.0402426851.262255211218.587145211210.13160347PolyhedronEnergyMonteCarloEnergy-2.07944154-2.079441436.292528766.26082162266.54209732266.058299615192.174774045186.55694273PolyhedronEnergyMonteCarloEnergy2.535423462.5354246789.0432663389.043739971942.056139721942.3635564233965.7301467433965.34803522176215.65351546175409.183189031602250.211728941598209.70411300

IcosahedronCCGCGGCCGCCCCGC

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI

Energy per Particle Pair from Polyhedron Configurations versus Number of Particles337

100Energy per Particle Pair10-110-210110210Number of Points3104PolyhedronConfigurationsFigure9.Thesystemenergypernumberofpairsasafunctionofthenumberofparticlesfortheexaminedpolyhedrons.

leastonepairofvorticessufficientlyclosetogether.Thisindicatesthatthoughbothpolyhedrons(ofmanydifferentshapes)andMonteCarlobasedextremalstatestendtowardsaveryuniformfinitepairwiseenergy,thispairwiseenergydoesneverthelessdependinsomewayonthedistributionofpoints.Itisnotsimplythecasethatasthenumberofpointsgrowsarbitrarilylargethepairwiseenergywillapproachapproximately0.15.

Asshowninsection3,theenergyperpairofparticlesapproachesameanfieldvalueof−12(log(2)−1)asthenumberofparticlesgrowswithoutbound,andthisappearstobethelimitreachedbyboththeMonteCarlo-derivedextremalstateandbythepolyhedronconfigurationsdevelopedbythegeodesicwordsfromthebasicshapes.

9.3.EnergyOverage.Inthissubsection,figure11,andthecorrespondingtablesrepresenttheenergy‘overage,’theamountbywhichtheenergyofthepolyhedronconfigurationexceedstheMonteCarloextremalstateenergy.Withtheexceptionsofthebasestatesofthetetrahedron,octahedron,andicosahedron–andtheexcep-tionalcasementionedinsection9.1oftheicosahedronsplitbythegeodesicwordCG–theseoveragesareallpositive.ThepolyhedronenergiesaregreaterthantheMonteCarloextremalstateenergies.

Severalofthevaluesforlownumbersofvorticesreturnnegativenumbers,re-flectingonlythattheMonteCarloextremalstateenergieswerenegative,andsothefractionofthepolyhedronenergyminusMonteCarloenergyovertheMonte

338CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

Pairwise Energy from Monte Carlo Run versus Number of Particles10010-1Energy per Particle Pairs10-210-310-410110210Number of Points3104MonteCarloextremalstateFigure10.ThesystemenergypernumberofpairsasafunctionofthenumberofparticlesfortheextremalstateasfoundbyaMonteCarloalgorithm.TetrahedronCCGCGG

N482698

PairwisePolyhedronPairwiseMonteCarlo-0.14384103583-0.1438410325-0.02427129089-0.025855561430.080061911820.078865008020.128191368110.12730187287PairwisePolyhedronPairwiseMonteCarlo-0.06931471133-0.069314714330.034574333850.034400118790.108792672380.108595224330.138672474070.13852243317PairwisePolyhedronPairwiseMonteCarlo0.019207753480.019207762650.089761357190.089761834650.131557792960.131578617830.146503783380.146502135230.150657768370.149968266520.152488922650.15210438056

NOctahedron6C14CG50CGG194

N123212248210823242

IcosahedronCCGCGGCCGCCCCGC

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI339

TetrahedronCCGCGG

NEnergyOverage40.000000023178-0.06127387874260.01517661419980.00698729106N123212248210823242

EnergyOverage-0.00000047724-0.00000531918-0.000158269390.000011250040.004597651680.00252814609

NOctahedron6C14CG50CGG194EnergyOverage-0.000000043280.005064373640.001818201920.00108315234

IcosahedronCCGCGGCCGCCCCGC

0Excess Energy in Polyhedron over Monte Carlo configurations versus Number of Points1010-110-2Energy Overage10-310-410-510-610-7101102103Number of VerticesFigure11.ThepercentagebywhichpolyhedronenergiesexceedtheMonteCarlo-generatedextremalstateenergiesasafunctionofthenumberofparticles.

Carloenergyisnegative.Similarly–astheMonteCarloextremalstateenergyisnegativeforthetetrahedronextremalstate–the‘overage’isrecordedaspositiveeventhoughtheMonteCarloextremalstateismarginallyhigherthantheana-lyticallydeterminedtetrahedroncoordinates.TheexceptionallyhighoveragefromthetetrahedronsplitbyGisreflectiveoftheMonteCarloenergybeingasmallnumber,magnifyingthesizeofadifferencewhichisnotmuchgreaterthanthatofthetetrahedronsplitbyC.

340CHJANC.LIM,JOSEPHNEBUS,ANDSYEDM.ASSAD

Asafunctionofwordlengththeenergyoverageappearstodeclineaseitherthenumberofpointsgrowsgreaterorthewordlengthincreases–sincethetraitsarecorrelatedtheavailabledatadoesnotdistinguishbetweenthetwo.TheavailablenumericalexperimentsdonotformaclearbodyofevidenceindicatingthedifferencebetweenpolyhedronenergiesandMonteCarloextremalstateenergieswillbecomearbitrarilysmallasthenumberofpointsincreases.Theobservationsofsections9.1and9.2indicatingthesteadygrowthofenergywiththenumberofpointssuggestssuggestsonlythattheenergiesofpolyhedronsandoftheextremalstatesshouldgrowatthesamerateswiththenumberofpoints.

10.Conclusions.ThetraditionaluseofaMonteCarloalgorithmtofindstatis-ticalequilibriumsextendseasilytofindingtheenergyminimumforanN-bodyproblem.SuchMonteCarloapproachesprovideacomputationallyrapidmethodofreachingaconfigurationofpointswhichisclosetotheextremalstatefor,inthiscase,thelogarithmicpotential.Ithasweaknessesinlocatingtheprecisecoordi-natesofaextremalstate,buttheeaseofimplementationandspeedofproducingapproximateresultsleavesitstillapotenttool.

Theradialdistributionfunctionisaconvenienttooltodeterminequicklythattwoconfigurationsofpointsonthespherearenotequivalent,aswasdoneinshow-ingthatthecentroidandgeodesicsplitsonthespheredonotcommute.Itisnotassertedthattheradialdistributionfunctioncanbeusedtoprovetwoconfigura-tionsareequivalent,buttheabilitytoruleoutapparentequivalencesisitselfofinterest,andtheextensionoftheradialdistributionfunctiontodetermininganypairwise-definedfunction,suchaspotentialenergy,suggeststhefunctionmayhaveconsiderableutility.

Polyhedronsmaybeconstructedasthe‘splittings’ofsimplerpolyhedrons,andtheconstructionofcomplexshapesfromsimplepolyhedronsknowntobeofinter-estresultsinshapeswhichmayhaveconsiderablestructure–withmanypointsnearoneanotherorconfinedtoarelativelysmallportionofthesphere,configura-tionsfarfromhomogenous–yetwithouttheenergygrowingmorethanmarginallygreaterthanwhattheMonteCarloalgorithmsuggestsistheglobalenergymini-mum.Howothersplittingoperationsmayfitintothissortofalgorithm,bothtogeneratepolyhedronsandhowwelltheirenergiesfitthoseoftheMonteCarloandthecentroidandgeodesicsplits,isaninterestingquestiondeservingofexploration.Theplotsofenergyperparticlepairinfigures9and10agreewiththecalculationofBergersenetal[2]thatameanfieldlimitfortheenergyofthislogarithmicinteractioncanbeexpectedtohold,eventhoughasBergersenetalcalculatethestandardthermodynamiclimitisfoundnottobevalid.

TheabilityofMonteCarloalgorithmstogeneratestatesnearanequilibrium,eitherforthecaseoffreeparticlesorforconstrainedparticles,offersavenuesforfurtherresearchinpairwiseinteractionsandwillbeexaminedinacomingpaper[11].Similarlytheuseofgeodesicwordsthatbeginfrombasicshapestobuildcon-figurationswithmanymorepointssuggestsanotheravenueforstudyingequilibriumconfigurationsbothforthepointsonthesurfaceofthesphereandforpointsontheplane,arelatedproblemalsotobeexaminedinanotherpaper[11].

Acknowledgement

ThisresearchwaspartiallysupportedbygrantR-151-000-015-112attheNa-tionalUniversityofSingapore.Wewouldliketothankthefacultyandstaffof

MONTE-CARLOANDPOLYHEDRON-BASEDSIMULATIONSI341

ComputationalScienceattheNUSandtheDeanofScienceoftheNUSfortheirhospitalityandsupportofthiswork.

REFERENCES

[1]EricLewinAltschuler,TimothyJ.Williams,EdwardR.Ratner,RobertTipton,Richard

Stong,FaridDowla,andFrederickWooten.PossibleMinimumLatticeConfigurationsforThompson’sProblemofChargesonaSphere.PhysicalReviewLettersVolume78Number14,(7April1997),2681-2685

[2]B.Bergersen,D.Boal,andP.Palffy-Muhoray,Equilibriumconfigurationsofparticlesona

sphere:thecaseoflogarithmicinteractions.J.Phys.A:Math.Gen.27(1994)2579-2586.[3]JohnR.Baumgardner,PaulO.Frederickson,IcosahedronDiscretizationoftheTwo-Sphere.

SIAMJournalonNumericalAnalysis22(December1985),1107-1115.

[4]M.Bowick,A.Cacciuto,D.R.Nelson,andA.Traesset.CrystallineOrderonaSphere

andtheGeneralizedThompsonProblem.http://arxiv.org/PScache/cond-mat/pdf/0206/0206144.pdf

[5]H.S.M.Coxeter,LL.D,FRS,RegularPolytopes2ndEdition.MacMillanCompany,New

York,1963.

[6]J.P.HansenandI.R.McDonald,Theoryofsimpleliquids,2nded.,AcademicPress,London,

1986.

[7]Y.KimuraandH.Okamoto,Vortexmotiononasphere.J.Phys.Soc.Japan561987,4203-4206.

[8]ChjanC.Lim,Relativeequilibriaofsymmetricn-bodyproblemsonthesphere:Inverseand

Directresults.Comm.PureandAppliedMathLI1998,341-371.

[9]ChjanC.Lim,ExactSolutionsofanenergy-enstrophytheoryforthebarotropicvorticity

equationonarotatingsphere.PhysicaA,February2001,131-158.

[10]ChjanLim,JamesMontaldi,MarkRoberts,RelativeEquilibriaofPointVorticesonthe

Sphere.PhysicaD148(2001),97-135.

[11]ChjanC.Lim,JosephNebus,SyedM.Assad.AMonteCarloAlgorithmforFreeandCoaxial

RingExtremalStatesoftheVortexN-BodyProblemonaSphere.Submittedforpublication.[12]PaulK.Newton,TheN-VortexProblem:AnalyticalTechniques.Springer,NewYork,2001.[13]E.B.Saff,A.B.J.Kuijlars.DistributingManyPointsontheSphere.MathematicalIntelli-gencer,v19,(1997),p5-11

[14]DaudSutton,PlatonicandArchimedeanSolids,WalkerandCompany,NewYork,2002.

ReceivedNovember2002;revisedFebruary2003.

DepartmentofMathematicalSciences,RensselaerPolytechnicInstituteE-mailaddress:limc@rpi.edu

DepartmentofMathematicalSciences,RensselaerPolytechnicInstitute,Depart-mentofComputationalScience,NationalUniveristyofSingaporeNationalUniversityofSingapore.E-mailaddress:nebusj@rpi.edu