; TeX output 2001.05.11:0637VEV]N cmbx12FINITEٚDYNAMICALSYSTEMSGK`y cmr10REINHARDUULAUBENBACHERANDBODOP*AREIGIS6 $- cmcsc10Abstract.\`This޳papGerismotivqatedbythetheoryofsequentialdynamical $systems,AdevelopGed[ cmmi10;1g^ 0ercmmi7n Atoyitself.3W*eintroGduceseveralequivqalencerelationsonsystems$and studytheresultingequivqalenceclasses.Thecaseoftwo-dimensional$systemsUUisstudiedindetail.=t- cmcsc10Introduction*XQ cmr12ThetopicofthispapSeristhestudyoffunctions+pg cmmi12fQ:URkg 2cmmi8n d !", cmsy10!kg nm;andtheiriterates,-wherek=f0;1g,andkg2n isthen-foldCartesianproSductofukg.DGWVeviewsucrhfunctionsas,@ cmti12 nite6dynamicffalsystemsuonthesetofbinarystringsofagivrenlength,*andcallthemsystems.ҽOurmotivXationcomesfromaninrterestintheirroleincomputersimulations. ane orttoestablisharigorousmathematicalfoundationforcomputersimrulation,lhasbSeenunderwayV,UNf I{(1)$׹:URkg n d!kg nm:WVewcallthefunctionfG(Y;n9)theseffquential.dynamicalsystemw(SDS)/determinedbrygYp,ݧtheloScalfunctionsfG2i@andthepermrutationË2URSnP.3uThegraphYv׹isthedepffendency35graph,andthepSermrutationXistheupffdateschedule.MTheeassumptionthattheloScalupdatefunctionsfG2i H>aresymmetricintheirinputsismotivXatedbrythedesireforagoSodtheoryofSDSandfacilitatestheproSofJhofsomekreyresults.vFVromthepoinrtofviewofapplicationstosimulationittisquiterestrictivre.$FVorinstance,itpreventsparallelcellularautomatafrombSeingmodeledasanSDS.*OneaofthegoalsofthispapSeristoclarifytherelationshipbetrweenalocalfunctionsonkg2n ^andthegraphYp.ʻFVorthispurpSosewredisregardtheaddedstructureprorvidedbytheupSdateschedule,andstudyn-tuplesoffunctions(fG 1;:::ʜ;fG nO);whereafG2i+:URkg2n d!kg2n q4crhangesonlythevXalueofthei-thcoSordinate. @WVealsodonotrequiretheloScalfunctionstobesymmetric.MoregenerallyV,wrewillstudysets,Bofsucrhfunctions.ThemainresultweobtainisaGaloiscorrespSondencebSetrweensetsofsucrhn-tuplesoffunctionsandsubgraphsofthecompletegraphon˶nvrertices.:Oneconsequenceisthat,givenasetoffunctions,thereisagraphG,sothatthefunctionsare1-loScalwithrespecttoG.*This1resultsuggestsapSossibleapproacrhtothestudyoflocalfunctionswithoutexplicitreferencetoagraph. Givrenthatinapplicationsthegraphde ningthe57inrteractionofvXariablesoftenchanges,GthismightbSesigni cantbSoththe-oreticallyandpracticallyV.Then}ZwreconsiderthestablebSehaviorofsystems.ThesetoflimitcyclesLfinAthestatespaceSf `isasubSdigraphofthestatespace,)witheacrhconnectedcompSonenrtWVedenotebryFMҹthepSowersetofthissetwithouttheemptryset, 6thatis,itselemenrtsarenon-emptysetsofn-tuplesoffunctionsfromkg2n "toitself,wherethejӹ-thfunctionappliedtoxUR2kg2ncrhangesonlythejӹ-thcoSordinateofx.OTheorem2.2. TherffeJtisaGaloiscorrespondencebetweenF{andthesetGofsubffgraphs35ofthecffompletegraphKn ۅonthevertexsetf1;:::ʜ;ng.Prffoof.#RWVe rstde nefunctionsUR:Fc ۼ!G.; :G `!F1;andathenvrerifythattheysatisfytheconditionsforaGaloiscorrespSondence,thatis,thatand areinclusionrevrersing,FUR (Fƹ),andG (G).*LetF2F1.0 De neasubgraph(Fƹ)ofKn asfollorws.Firstconstructthek|setx~F8ofalln-tuplesW~*f=v(aX~tfG1 ҫ;aV~tfG2 ҩ;:::ʜ;Wm|~*fGn);whicrheitherareinFƹ,orarisefromanGelemenrtinF駹byreplacingoneofthecoSordinatesbya0-loScalfunction,that]is,bryafunctionfromL2iRA0 ˹forsomei. >Nowde nethegraph(Fƹ)as7jVE6P.REINHARDTLA9UBENBACHERANDBODOP:AREIGISVÍfollorws.}Anyedgei{j&ofKn ",isin(Fƹ)ifandonlyifiLş~fGiiL؃~ (fGj=iLm~IfGjiLW~ (fGiforyall!W~*f g=UR(fG21;:::ʜ;fG2nO)2xy~F H.*NorwletGURKn MbSeagraph.!WVede neaset (G)ofn-tuplesoffunctionsonkg2n bry9(cA (G)UR=L 1ڍ1(\-z D ӍG D)L 2ڍ1(\-z D ӍG D)UNL nڍ1P(\-z D ӍG);E퍹whereꨟ\-z D ӍGisthecomplemenrtofGinKnP.WVeneedtoshorwthatand areinclusionreversing, thatFUR (Fƹ),andethatoGUR (G).6xTVoshorwthe rstpropSertyV,letFURFƟ20SninF1.6xThenx~Fuxj~FƟ0`.AnE-edgei{jofKn}isin(FƟ20o)ifandonlyfG2iandfG2j6commruteforeveryelementfU=xV(fG2liǹ)2x!}~FƟ20.9Sincex>~FJx!}~FƟ20,_i{jBtisalsoconrtainedin(Fƹ).9IfGxVG20cڹaresubgraphsofKnP,9then\-z  ӍG0'\-z D ӍGb.]A1-loScalfunctiononthesmallergraphiscertainly=also1-loScalonthelargergraph.gThisshorwsthatthecorrespondenceisinclusionrevrersing.*TVo]shorwthatF (Fƹ),zElet(fG21;:::ʜ;fG2nO)2Fƹ.WVeharve]toshorwthatfG2iŻ2f`L2iRA1(`z p(Fƹ)),xi.e. zthat\vfG2iٹ(x)doSesnotdependonthejӹ-thcoordinatexj€ofxifj Iisenotconnectedtoiinthegraph`z p(Fƹ).Letjӹ(6=URi)bSeavrertexin`z p(Fƹ) suchthati{ja۹isnotin`z p(Fƹ).'LetWC~*fG2jbSeafunctioninLOj0.Then(fG21;:::ʜ;W~*fG2j x;:::;fG2nO)UR2xy~F H.Since'i{j]isnotin`z p(Fƹ) t,vitisin(Fƹ)hencefG2i/@W~*gfG2jkɹ=W[~*pfG2jgfG2i cfor'allfour!functionsWyR~*fG2j2URLOj0.8Norw2EWV#~*SfG jakfG iٹ(x)UR=(x1;:::ʜ;f Giڍi(x);:::ʜ;W~*fOGjáj x(x);:::;xnP)and)fG iWW9R~*fG j#Y(x)UR=(x1;:::ʜ;f Giڍiٹ(x1;:::ʜ;7~xj Z;:::;xnP);:::;W~*fOGjáj x(x);:::;xnP);Ⓧwhere~xjSV=W~*URfOGjáj(x),hencef2GiRAiٹ(x)andfG2i(x)donotdepSendonxjf .+NorwweshowthatGUR (G).8Firstobservrethatw9P) msbm10]qǍM (G)lu*=UR (G)=L 1ڍ1(\-z D ӍG D)L 2ڍ1(\-z D ӍG D)UNL nڍ1P(\-z D ӍG); since4L2iRA0RNL2iRA1(\-z D ӍG D).*Leti{jbSeinGandletfM2 (G).*WVeharve4toshorwthatfG2i\]fG2j =axfG2j]fG2iholds,sincetheni{jisanedgein (G).NJNorwfw2 (G)=L21RA1(\-z D ӍG D)L22RA1(\-z D ӍG D)wL2nRA1P(\-z D ӍG)impliesthatf2GiRAiٹ(x)doSesnotdependonxjjsinceUGthezedgei{j'pisnotin\-z D ӍG9and,similarlyV,fOGjáj (x)zdoSesnotdependonxidڹ.Hencewregeto#fG iWfG j (x)UR=fG iٹ(x1;:::ʜ;fOGjáj(x);:::ʜ;xnP)UR=(x1;:::;f Giڍiٹ(x);:::;fOGjáj (x);:::;xnP)and,similarlyV, ffG jXfG iٹ(x)UR=fG j (x1;:::ʜ;f Giڍi(x);:::ʜ;xnP)UR=(x1;:::;f Giڍiٹ(x);:::;fOGjáj (x);:::;xnP):eÍThrus,wehavefG2iWfG2j [=URfG2jXfG2iٹ.& msam10F٠VE~FINITE!D9YNAMICALSYSTEMSzz7VWVeLillustratethiscorrespSondencewithanexample. ^Letn=3,andLletFconsistofthesingletripleoffunctionsfQ=UR(fG21;fG22;fG23)with%ўʍqfG21(x1;x2;x3) =UR(x2;x2;x3);qfG22(x1;x2;x3) =UR(x1;x1;x3);qfG23(x1;x2;x3) =UR(x1;x2;x1j+x3):InspSectionishorwsthattheonlyedgeofK3 vmcontainedin(Fƹ)is2-3.$Hence(Fƹ)consistsofagraphwiththreevrerticesandoneedge.cqHenceitscomple-menrtisthegraphwiththreeverticesandtwoedgesemanatingfromvertex1.Therefore, (Fƹ)whconsistsofthesetofallfunctions(gn921.=;gn922;gn923)whsucrhthatgn921isarbitraryV,gn922doSesnotdependonthethirdvXariable,andgn923doesnotdependonthesecondvXariable.΍Corollary2.3.With35notationasintheabffovetheorem,wehavey(1)9 (G)UR=G;^k%for35allgrffaphsG.(2)T (Fƹ)UR=(F);^k%and,35inpffarticular,ў ( (Fƹ))UR= (F);%for'allsetsF2F1.CThatis,d isaclosurffeoperatoronthesetof%n-tuples35ofloffcal35functionsonkg2nm.0Prffoof.#RThe֮secondclaimisastandardconsequenceofthepropSertiesofaGaloiscorrespSondence.TVoծshorwthe rstclaim,pleti{jbeanedgein (G),pandsuppSosethatitisnotinG.8Theni{j%2UR\-z D ӍG .Recallthatўz) (G)UR=L 1ڍ1(\-z D ӍG D)UNL nڍ1P(\-z D ӍG):Thenp (G)conrtainsthefunctionfc=9d(fG21;:::ʜ;fG2nO),%suchthatfG2p H=9didforallpUR6=i;jӹ,andpSositivreintegersprimetolcm N(Order(fG);Order (gn9)),andanonnegativreintegern,suchthatthediagramK[*nkg2r*lkg2m|32fd&O line10-!7_.psjnkg2rsjlkg2m|{fd&ά-i_.p**6kg2r`32fd&ά-!7}qsjsj6kg2r`{fd&ά-i}qHzǠ*FfeǠ?`,fǟ-:sH}Ǡ*Ffe°Ǡ?QclgI{-:sH4Ǡ*Ffeh,Ǡ?`fǟ-:s獹commrutes,andqpUR=fG2nO,pqË=gn92n. kҠVE~FINITE!D9YNAMICALSYSTEMSzz9VWVepSostponetheproofthatstableequivXalenceisanequivalencerelationunrtilafterthefollorwingtheorem. De nition_U3.6.9Let:f1;f2>bSesystemswithstatespacesSf8:i andsub-digraphsof).limitcyclesLf8:iʹ.bWVecallf12andf2stably_isomorphicifthereexistsadigraphisomorphismbSetrweenLfq1 andLfq2.7QItisclearthatstableisomorphismisanequivXalencerelation.Theorem3.7.Two?systemsfandg arffestablyequivalentifandonlyiftheyarffe35stablyisomorphic.zPrffoof.#RFirstassumethatf عandg4arestablyequivXalenrt,arestablyisomorphic,withadigraphiso-morphism2荒P:URLfq!!Lg:FVromeacrhlimitcycleinLfchoSoseavertexasrepresentative, xeffdpoint0`=(0;0;:::ʜ;0),:together9>with(22nWp 1)=tcyclesoflengtht.xInpffarticular,Ýforeverynthereexistsalinearsystemkg2n d!URkg2n $withalimitcycleof35length22nR1.aQPrffoof.#RThe[Galois eldF2n9Nisann-dimensionalvrectorspaceoverk/=jF2,henceqEisisomorphictokg2n asakg-vrectorspace.̸ThemultiplicativegroupF2RA2nispcyclicoforder22n"ҹ1.ʓFVoreacrhdivisortof22nҹ1thereexistsa(unique) VE12P.REINHARDTLA9UBENBACHERANDBODOP:AREIGISVsubgroup cmmi10 0ercmmi7K`y cmr10O line10