|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Full Text | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
PAGE 1 ONE-DIMENSIONALCELLULARAUTOMATA: PASCAL'STRIANGLEANDANEXTENSIONOFRULE90FOR ANON-ABELIANGROUP ERINCRAIG AThesis SubmittedtotheDivisionofNaturalSciences NewCollegeofFlorida inpartialfulllmentoftherequirementsforthedegree BachelorofArts UnderthesponsorshipofProfessorEiriniPoimenidou Sarasota,Florida May,2009 PAGE 2 Acknowledgements ManythankstoProfessorEiriniPoimenidouforherencouragementandwarmth. Shehasbeenawonderfulsupportandrolemodel,andherdedicationtomypersonal andacademicgrowthhasbeeninvaluable. ThanksalsotoMichaelRose,UniversityofCalifornia-Berkeley,forsharinghis timeandmathematicalintuitionandfortheconversationswhichinspiredthematerial inChapters4and5. AndthankstoProfessorPatrickMcDonald,whohasbeenanever-presentsupport tomethroughoutmyundergraduateeducation. IalsoacknowledgeandthankProfessorKarstenHenckellforhisaidwiththis projectandhispersonalencouragement. PAGE 3 One-DimensionalCellularAutomata: Pascal'sTriangleandanExtensionofRule90foraNon-AbelianGroup ErinCraig NewCollegeofFlorida,2009 ABSTRACT Thisthesisisastudyofonedimensionalautomata.Webeginbydevelopingnew propertiesofbinomialcoecientsthatwerediscoveredfrompatternsseeninPascal's trianglemoduloaprime.Then,motivatedbyWolfram,MartinandOdlyzko'sAlgebraicPropertiesofCellularAutomata"[ 15 ],westudyanextensionofRule90for multiplicativegroupsanddevelopthenecessaryandsucientconditionsforastate inthisautomatontohaveapredecessor.Wethenapplythismethodtoshowthe fractionofstatesreachablethroughevolutionforthisextensionofRule90overthe dihedralgroup. ProfessorEiriniPoimenidou DivisionofNaturalSciences PAGE 4 Contents Chapter1.Introduction1 Chapter2.Pascal'sTriangleModuloaPrime5 Chapter3.AlgebraicPropertiesofCellularAutomata"18 Chapter4.AutomataOveraMultiplicativeGroup22 1.CellsDeterminedbyTheirSuccessors23 2.StatesDeterminedbyTheirSuccessors29 3.Summary32 Chapter5.AnAutomatonOvertheDihedralGroup35 Chapter6.ExamplesandSuggestionsforFurtherStudy51 1.Examples51 2.SuggestionsforFurtherStudy58 AppendixA.Code63 AppendixB.Data68 Bibliography72 iii PAGE 5 CHAPTER1 Introduction Inthesimplestform,acellularautomatonconsistsofarowofcells,eachcontaining adiscretevariable.Thesecellsupdatesimultaneouslyatdiscretetimestepsaccording toaseriesoflocalruleswhichoftendependonlyonthecellitselfanditsnearest neighbors,thecellsimmediatelytoitsleftanditsright.Morecomplexcellular automataaretwo-orthree-dimensionallatticesofcellswhichupdateagainaccording tolocalrules.Becauseautomatastoredataandtrackitschangeovertime,theyare usefulascrudemodelsofphysicalandbiologicalsystems. TherstdiscussionofautomataiscreditedtoStanislawM.Ulam[ 1 ]intheforties. Hestudiedcellularspaces",twodimensionalspacesdividedintocells.Initially,each cellwaseitheron"oro".Thecellsthenupdatedsimultaneouslyatdiscretetime stepsasfollows:ifacellsharedanedgewithtwoormorecellsthatwereonattime t ,itwouldturnonattime t +1,otherwise,thecellwouldturnoattime t +1.To ensurethateachcellsharesanedgewithfourothercells,wegluetogethertheleft andrightandtopandbottomedgesoftheautomaton.AsUlamexploredhowhis cellularspacesevolvedoverthesediscretetimesteps,henoticedthattheyformed complexpatternsandsometimesself-reproduced. Figure1. ExampleofUlam'sCellularSpaces 1 PAGE 6 WhileUlamworkedonhisdevelopmentofcellularspaces,vonNeumann[ 1 ],[ 3 ] hopedtodevelopaself-reproductivemachine.Hewantedtounderstandhoworganismscouldcreatesomethingmorecomplicatedthanthemselvesthroughevolution[ 2 ] andsohehopedtomodelthispatternwithaself-reproductivemachine.Ulam, knowingthathiscellularspacescouldself-reproduce,toldvonNeumannofhiswork. Shortlyafter,vonNeumanndevelopedhismachinenowcalledthevonNeumann UniversalConstructorandpresentedcellularautomataascrudemodelsofbiologicalsystemsinthepaperGeneralandLogicalTheoryofAutomata"[ 3 ].Hewas neverabletoexplainhowthisevolvabilityoforganismswaspossible,onlythatitwas possible. In1970,theworkofautomataadvancedsharplywithJohnConway'sdevelopment ofanautomatonthathecalledtheGameofLife".Thisautomatonlookslikeatwo dimensionallatticewhereeachcelltakesthevaluealive"ordead".Ifadeadcell sharesanedgeorcornerwiththreealivecells,itbecomesalive.Ifanalivecellshares anedgeorcornerwithtwoorthreealivecells,itremainsalive.Otherwise,acell diesorremainsdead.Weagaingluetheedgesoftheautomatontogether.This canbeinterpretedasamodelofasystemwhereorganismssurviveonlyifthespace aroundthemismoderatelypopulated;aconcentrationthatistoohighortoolow killsorganisms.Figure2illustratesthisautomaton. Figure2. ExampleofConway'sGameofLife"Automaton Cellularautomatacanmodelhowaforestrespreads,orleadtonewresultsin numbertheory.Automatahavealsobeenusedasawaytocomposemusic.Most commonly,automataareusedinthestudyofbiologicalandphysicalsystemsbecause 2 PAGE 7 theytrackchangeovertimeinsystemswherethecomponentsofthesysteminteract witheachotheraccordingtoasetoflocalrules. Asimpleexampleofanupdaterule,andtheonewhichwillbediscussedfurther inthispaper,istheoneentitledRule90.Givenacellanditsnearestneighbors,the updatedcellisencodedinthenumber90writteninbinary,01011010. Figure3. UpdateRule90. InFigure3,wecantakecellscoloredblacktocontaina1andthosecoloredwhite tocontaina0.Thisway,wecanseethatthisruleisoneinwhicheachcellupdates tothesumofitsnearestneighborsthecellimmediatelytoitsleftandthattoits rightmodulo2.Inthecasewheretheautomatonisarowofcellsniteinnumber, wegluetogethertheleftandrightedgesoftheautomatontoensurethateachcell hastwonearestneighbors".ThisautomatonisdiscussedatlengthinAlgebraic PropertiesofCellularAutomata"[ 15 ]andwillbediscussedfurtherinsection3. Figure4. OnetimestepintheautomatondenedinAlgebraicPropertiesofCellularAutomata"[ 15 ]. Theautomatonintheexampleabovehaslengthwhichremainsinvariantthrough itsevolution.Notallautomataareso:itiscommonalsotoconsideronedimensional automataofvariablelengths.Themostwellknownexampleofsuchanautomaton isPascal'sTriangle.Thisautomatonisconstructedasfollows:attime t =0,the automatonconsistsofasingle1.Attime t +1,theautomatonhaslength t +2and iswrittenbeneaththeautomatonattime t .Eachcellintheautomatonisthesum 3 PAGE 8 ofthecelldirectlyaboveitandthecellaboveandtotheleft.Ifeitherofthesecells doesnotexistattime t ,weconsiderinitsplaceacellcontaining0. Figure5. Pascal'sTriangle OnPascal'sTriangle,wecanconstructacoordinatesystem t;c where t isthe timestartingwith t =0and c isthecolumnstartingwith c =0.Everypointon thetrianglecorrespondstoabinomialcoecient;thecellpositionedat t;c willhave value )]TJ/F37 7.9701 Tf 5.784 -4.379 Td [(t c .Asaresult,thestudyofpatternsinPascal'strianglethuslycorrelatestoa studyofbinomialcoecients.ThisautomatonwillbediscussedfurtherinChapter 2. 4 PAGE 9 CHAPTER2 Pascal'sTriangleModuloaPrime StudyofPascal'strianglepredatesstudyofautomatabyhundredsofyears.The trianglecanbedatedbackto1261andisattributedtoYangHui.Sincethen,the trianglehasbeenstudiedindepthbecauseofitsclosetiestocombinatoricsand probabilityaswellasthefractalnatureoftheautomatonthatappearswhenallentries arereducedmoduloaprime.Themostcommonlyknownandstudiedfractalproperty oftheautomatonappearswhenthetriangleisreducedmodulo2asillustratedbelow: Figure1. Pascal'striangle;Pascal'strianglereducedmodulo2 Toseepatternsclearly,itisusefultoassigntoeachintegeracolorandcolor eachcell.WeemploysoftwarecreatedbyDonaldSpickleraspartofthePascGalois project[ 5 ]forthecreationandstudyofPascal'strianglemoduloaprimeasillustrated inFigure2. 5 PAGE 10 Figure2. Pascal'strianglemodulo2 Thispictureisfamiliar:itistheSierpinskiGasket.Thispropertyofthetriangle hasbeenstudiedextensivelyforexamples,seereferences[ 6 ]-[ 10 ].Withthispattern asmotivation,weconsidertheautomatonmodulo p ,aprime.Belowaresomeimages oftherst p 2 rowsofthetrianglemodulo p =7 ; 11 ; and13. Figure3. Therst p 2 rowsofPascal'strianglemodulo p =7 ; 11 ; and13. Likeitsimagemodulo2,Pascal'striangleexhibitspatternswhentakenmoduloa prime.However,thesamepatternsdonotappearinatrianglemoduloacomposite number.Weillustratethispropertyingures4and5. 6 PAGE 11 Figure4. Pascal'strianglemodulo2 ; 3,and6attime t =35. Figure5. Pascal'strianglemodulo2 ; 3 ; 4and12attime t =143. 7 PAGE 12 Giventhepatternsinthetrianglemoduloaprimeandthefactthateachpoint onthetrianglecorrespondstoabinomialcoecient,weareabletoestablishnew binomialidentities.Intheproofsthatfollow,wewillmakerepeateduseofWilson's andLucas'Theorems,givenbelow. Theorem 2.1 Wilson'sTheoremLet p 2 Z p 1 .Then p isprimei p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1! )]TJ/F25 11.9552 Tf 21.918 0 Td [(1mod p Theorem 2.2 Lucas'TheoremLet p 2 Z p prime.Given r m 2 N with r m suchthat m = m k p k + + m 1 p + m 0 r = r k p k + + r 1 p + r 0 ; then, m r m k r k m 1 r 1 m 0 r 0 mod p: Proposition2.3,Theorem2.4andCorollary2.5weredevelopedinconjunction withKatelinChildersatthe2005PascGaloisUndergraduateRetreat[ 5 ]. Proposition 2.3 Let p beprimeandlet a;b;k 2 N suchthat b a p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 Then, p )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y n =1 np k + a p k + b )]TJ/F25 11.9552 Tf 21.918 0 Td [(1mod p: Proof. WebeginbyapplyingLucas'Theoremtoseethat np k + a p k + b n 1 a b mod p: As n varies,thesetgeneratedby )]TJ/F37 7.9701 Tf 5.48 -4.379 Td [(n 1 )]TJ/F37 7.9701 Tf 10.959 -4.379 Td [(a b willformareducedresiduesystemmodulo p Consequently, p )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y n =1 np k + a p k + b p )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y n =1 n 1 a b mod p p )]TJ/F25 11.9552 Tf 11.956 0 Td [(1!mod p )]TJ/F25 11.9552 Tf 21.917 0 Td [(1mod p: 8 PAGE 13 AninterpretationofProposition2.3for p =5canbeseeninFigure6. Figure6. Pascal'strianglemodulo5.Thetophighlightedpointrepresentsthebinomialcoecientwhere n =1, k =1, a =3, b =2, i.e. )]TJ/F34 7.9701 Tf 5.48 -4.379 Td [(8 7 .Theremaininghighlightedpointsrepresentbinomialcoefcientsas n variesfrom2through4.Thepropositionstatesthat )]TJ/F34 7.9701 Tf 5.48 -4.379 Td [(8 7 )]TJ/F34 7.9701 Tf 10.959 -4.379 Td [(13 7 )]TJ/F34 7.9701 Tf 10.959 -4.379 Td [(18 7 )]TJ/F34 7.9701 Tf 10.959 -4.379 Td [(23 7 )]TJ/F25 11.9552 Tf 21.918 0 Td [(1mod5. Theorem 2.4 Let p beanoddprimeandlet k 2 N .Then, p )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y n =2 np k 2 p k )]TJ/F25 11.9552 Tf 21.918 0 Td [(2mod p: Proof. ByLucas'Theorem, p )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y n =2 np k 2 p k p )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y n =2 n 2 mod p: Wenowhave p )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y n =2 n 2 = 2 2 3 2 4 2 5 2 6 2 p )]TJ/F25 11.9552 Tf 11.955 0 Td [(4 2 p )]TJ/F25 11.9552 Tf 11.955 0 Td [(3 2 p )]TJ/F25 11.9552 Tf 11.955 0 Td [(2 2 p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 2 = 2! 2!! 3! 2!! 4! 2!! 5! 2!! 6! 2!! p )]TJ/F25 11.9552 Tf 11.955 0 Td [(3! 2! p )]TJ/F25 11.9552 Tf 11.955 0 Td [(5! p )]TJ/F25 11.9552 Tf 11.955 0 Td [(2! 2! p )]TJ/F25 11.9552 Tf 11.955 0 Td [(4! p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1! 2! p )]TJ/F25 11.9552 Tf 11.956 0 Td [(3! = 1 2! p )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 p )]TJ/F25 11.9552 Tf 11.955 0 Td [(2! p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1! 2! 1 2! p )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1 )]TJ/F25 11.9552 Tf 9.299 0 Td [(1mod p 9 PAGE 14 2 1 1 )]TJ/F25 11.9552 Tf 9.299 0 Td [(1mod p )]TJ/F25 11.9552 Tf 21.918 0 Td [(2mod p: AninterpretationofTheorem2.4for p =5canbeseeninFigure7. Figure7. Pascal'strianglemodulo5.Thetophighlightedpointrepresentsthebinomialcoecientwhere n =2and k =1,i.e. )]TJ/F34 7.9701 Tf 5.48 -4.379 Td [(10 10 .The remaininghighlightedpointsrepresentbinomialcoecientsas n varies from2through4.Thetheoremstatesthat )]TJ/F34 7.9701 Tf 5.479 -4.379 Td [(10 10 )]TJ/F34 7.9701 Tf 10.959 -4.379 Td [(15 10 )]TJ/F34 7.9701 Tf 10.959 -4.379 Td [(20 10 )]TJ/F25 11.9552 Tf 21.918 0 Td [(2mod5. Corollary 2.5 Let p beprimeandlet a;b;k 2 N suchthat b a p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 Then, a b p )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y n =2 np k + a 2 p k + b )]TJ/F25 11.9552 Tf 21.918 0 Td [(2mod p Proof. TheproofisadirectapplicationofLucas'Theoremandtheproofof Theorem2.4above. AninterpretationofCorollary2.5for p =5canbeseeninFigure8. 10 PAGE 15 Figure8. Pascal'strianglemodulo5.Thetophighlightedpointrepresentsthebinomialcoecientwhere n =2, k =1, a =3, b =2, i.e. )]TJ/F34 7.9701 Tf 5.479 -4.379 Td [(13 12 .Theremaininghighlightedcirclesrepresentbinomialcoecientsas n variesfrom2through4.Thecorollarystatesthat )]TJ/F34 7.9701 Tf 5.48 -4.379 Td [(3 2 )]TJ/F34 7.9701 Tf 10.959 -4.379 Td [(13 12 )]TJ/F34 7.9701 Tf 10.959 -4.379 Td [(18 12 )]TJ/F34 7.9701 Tf 10.959 -4.379 Td [(23 12 )]TJ/F25 11.9552 Tf 21.918 0 Td [(2mod5. AnotherwaytostudyPascal'strianglemodulo p istoreadeachrowasthebase p expansionofaninteger.In[ 11 ],thefollowingconjectureappears. Conjecture 2.6 If a n = P n k =0 2 k )]TJ/F37 7.9701 Tf 5.48 -4.379 Td [(n k mod2 ,then a n +1=3 a n Wemayunderstand a n asthenumberwhosebinaryexpansionisthe n throw ofPascal'strianglemodulo2.Inthiscontext,theconjectureclaimsthatthenumber representedbyPascal'strianglemodulo2attime t when2 t isthreetimesthe numberrepresentedbyautomatonattime t )]TJ/F25 11.9552 Tf 10.866 0 Td [(1.In[ 12 ],EmmanuelFerrandsketches aproofforthisconjecture.Wegeneralizeandprovethisconjectureforanarbitrary prime p below. Proposition 2.7 Let p beaprimedivisorof n anddene a n asfollows: a n = n X k =0 p k n k mod p Then, a n +1= p +1 a n : 11 PAGE 16 Proof. ObserverstthatbyLucas'Theorem, p j )]TJ/F37 7.9701 Tf 5.479 -4.379 Td [(n k ifandonlyifatleastone ofthebase p digitsof k isgreaterthanitscorrespondingdigitof n .Webeginby writing a n = p 0 n 0 mod p + p 1 n 1 mod p + + p n )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 n n )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 mod p + p n n n mod p : Considernowabinomialcoecient )]TJ/F37 7.9701 Tf 5.479 -4.379 Td [(n k suchthat p doesnotdivide k .Then, writing n = n m p m + + n 0 and k = k m p m + + k 0 ,weapplyLucas'Theoremto seethat )]TJ/F37 7.9701 Tf 5.479 -4.379 Td [(n k )]TJ/F37 7.9701 Tf 5.479 -4.379 Td [(n m k m )]TJ/F37 7.9701 Tf 5.479 -4.379 Td [(n 0 k 0 mod p .Since p j n n 0 =0,andsince p k k 0 > 0.Itnow followsbyourobservationinthebeginningoftheproofthat p j )]TJ/F37 7.9701 Tf 5.48 -4.379 Td [(n k .Wetherefore havethat )]TJ/F37 7.9701 Tf 5.479 -4.379 Td [(n k 0mod p whenever p k .Thus a n = p 0 + p p n p mod p + p 2 p n 2 p mod p + + p n : Wenowwrite a n +1as a n +1= p 0 n +1 0 mod p + + p n +1 n +1 n +1 mod p : Recallingtheupdaterulethatgeneratestheautomaton,namely n k )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 + n k = n +1 k ; wecanrewriteas a n +1= p 0 + p 1 n 0 + n 1 mod p + p 2 n 1 + n 2 mod p + + p p n p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 + n p mod p + p p +1 n p + n p +1 mod p + + p n )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 n n )]TJ/F25 11.9552 Tf 11.955 0 Td [(2 + n n )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 mod p + p n n n )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 + n n mod p + p n +1 : 12 PAGE 17 Usingourobservationabove,wecandropalltermsinvolving )]TJ/F37 7.9701 Tf 5.479 -4.379 Td [(n k mod p whenever p k andthusobtain a n +1= p 0 + p 1 n 0 mod p + p 2 + + p p n p mod p + p p +1 n p mod p + + p n )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 + p n n n mod p + p n +1 : = p 0 + p 1 + p p n p mod p + p p +1 n p mod p + + p n n n mod p + p n +1 : = p 0 + p p n p mod p + + p n n n mod p + p 1 + p p +1 n p mod p + + p n +1 = a n + pa n = p +1 a n asdesired. Onecanalsostudytherst p rowsofPascal'strianglemodulo p asanequilateral triangleinordertostudyitsbehaviorunderipsandrotations.Intheproofsthat follow,wewillmakerepeateduseofthefollowinglemma. Lemma 2.8 Let p beanoddprimeandlet s 2 N suchthat s p )]TJ/F25 11.9552 Tf 11.956 0 Td [(1 .Then, p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(s )]TJ/F25 11.9552 Tf 9.299 0 Td [(1 s p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1! s mod p: Proof. p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(s != p )]TJ/F25 11.9552 Tf 11.955 0 Td [( s +1! )]TJ/F25 11.9552 Tf 9.299 0 Td [( s +1 )]TJ/F25 11.9552 Tf 9.299 0 Td [( s +2 )]TJ/F25 11.9552 Tf 9.298 0 Td [( p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1mod p )]TJ/F25 11.9552 Tf 9.299 0 Td [(1 s p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1! s Propositions2.9and2.10weresuggestedbyProfessorTylerEvansofHumboldt StateUniversityinapresentationatthe2005PascGaloissummerundergraduate researchretreatatNewCollegeofFlorida[ 5 ]andrecentlyappearedin[ 13 ].To 13 PAGE 18 illustratethesepropositions,itisusefultodrawtheautomatonasanequilateral triangle. Thefollowingpropositiondescribesthebehavioroftherst p rowsofPascal's triangleunderthereection 1 : s t 7! p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(s : Figure9. Reection 1 onPascal'strianglemodulo5 Proposition 2.9 Let p beanoddprimeandlet s;t 2 N suchthat t s .Then, s t )]TJ/F25 11.9552 Tf 9.298 0 Td [(1 s + t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(t p )]TJ/F25 11.9552 Tf 11.956 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(s mod p: Proof. p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(s = p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(s s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t )]TJ/F25 11.9552 Tf 9.298 0 Td [(1 t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1! t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(s s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t mod p )]TJ/F25 11.9552 Tf 9.298 0 Td [(1 s + t s t s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t mod p: 14 PAGE 19 Thefollowingpropositiondescribesthebehavioroftherst p rowsofthePascGaloistriangleunderthereection 2 : s t 7! p )]TJ/F25 11.9552 Tf 11.956 0 Td [(1 )]TJ/F25 11.9552 Tf 11.955 0 Td [( s )]TJ/F26 11.9552 Tf 11.956 0 Td [(t t : Figure10. Reection 2 forPascal'strianglemodulo5 Proposition 2.10 Let p beanoddprimeandlet s;t 2 N suchthat t s .Then, s t )]TJ/F25 11.9552 Tf 9.299 0 Td [(1 t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F25 11.9552 Tf 11.955 0 Td [( s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t t mod p: Proof. p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F25 11.9552 Tf 11.956 0 Td [( s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t t = p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F25 11.9552 Tf 11.956 0 Td [( s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(s )]TJ/F25 11.9552 Tf 9.299 0 Td [(1 s p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F25 11.9552 Tf 11.955 0 Td [( s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t s t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1! mod p )]TJ/F25 11.9552 Tf 9.299 0 Td [(1 2 s )]TJ/F37 7.9701 Tf 6.587 0 Td [(t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1! s t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1! s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t mod p 15 PAGE 20 = )]TJ/F25 11.9552 Tf 9.299 0 Td [(1 t s t mod p: Propositions2.9and2.10statethatreectingtherst p rowsofthePascGalois triangleoverthelinesshowninFigures9and10willmapabinomialcoecientto itselforitsadditiveinversemodulo p .Fortheverticalreection : )]TJ/F37 7.9701 Tf 5.48 -4.379 Td [(s t 7! )]TJ/F37 7.9701 Tf 10.301 -4.379 Td [(s s )]TJ/F37 7.9701 Tf 6.586 0 Td [(t ,we havethewellknownidentity )]TJ/F37 7.9701 Tf 5.48 -4.379 Td [(s t )]TJ/F37 7.9701 Tf 10.302 -4.379 Td [(s s )]TJ/F37 7.9701 Tf 6.586 0 Td [(t mod p Thefollowingcorollarydescribesthebehavioroftherst p rowsofthePascGalois triangleundera 2 3 clockwiserotation 1 aboutitsgeometriccenter.Since 1 = 1 wehave 1 : s t 7! p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F25 11.9552 Tf 11.955 0 Td [( s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.956 0 Td [(s : Corollary 2.11 Let p beanoddprimeand s;t 2 N suchthat t s p )]TJ/F25 11.9552 Tf 11.956 0 Td [(1 Then, s t )]TJ/F25 11.9552 Tf 9.299 0 Td [(1 t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F25 11.9552 Tf 11.955 0 Td [( s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(s mod p: Proof. UsingProposition2.9andtheidentitygivenby ,weseethat p )]TJ/F25 11.9552 Tf 11.956 0 Td [(1 )]TJ/F25 11.9552 Tf 11.955 0 Td [( s )]TJ/F26 11.9552 Tf 11.956 0 Td [(t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(s )]TJ/F25 11.9552 Tf 9.298 0 Td [(1 t s s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t mod p )]TJ/F25 11.9552 Tf 9.299 0 Td [(1 t s t mod p: Asimilarresultcanbeobtainedfora 4 3 clockwiserotation, 2 .Since 2 = 2 2 : s t 7! p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.955 0 Td [(t s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t : 16 PAGE 21 Corollary 2.12 Let p beanoddprimeand s;t 2 N suchthat t s p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 Then, s t )]TJ/F25 11.9552 Tf 9.298 0 Td [(1 s + t p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.956 0 Td [(t s )]TJ/F26 11.9552 Tf 11.956 0 Td [(t mod p Proof. ByProposition2.10andtheidentitygivenby p )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 )]TJ/F26 11.9552 Tf 11.956 0 Td [(t s )]TJ/F26 11.9552 Tf 11.956 0 Td [(t )]TJ/F25 11.9552 Tf 9.298 0 Td [(1 s )]TJ/F37 7.9701 Tf 6.587 0 Td [(t s s )]TJ/F26 11.9552 Tf 11.955 0 Td [(t )]TJ/F25 11.9552 Tf 9.299 0 Td [(1 s + t s t : Withthis,wecompleteourstudyofPascal'strianglemoduloaprime.While therearemanyinterestingpropertiesofthisautomatonover Z =p Z ,itisinteresting alsotoexplorethisautomatonoveragroup G usingthegroupoperationinplaceof addition.Thecasewhere G isabelianhasbeenstudiedrecentlyinthepaperThe EvolutionHomomorphismandPermutationActionsonGroupGeneratedCellular Automata"[ 14 ].ThispaperstudiesnotonlythePascalupdaterule,buttheentire classofadditiveupdaterules.Todoso,BardzellandMillerusethepropertythat, overabeliangroups,additiveupdaterulesarehomomorphisms.Inthepaper,AlgebraicPropertiesofCellularAutomata"[ 15 ],Wolfram,Martin,andOdlyzkostudy, withadierentapproach,thesameclassofupdaterulesforautomataover Z =n Z as illustratedinthefollowingsection. 17 PAGE 22 CHAPTER3 AlgebraicPropertiesofCellularAutomata" Inthepaper,AlgebraicPropertiesofCellularAutomata"[ 15 ],Wolfram,Martin, andOdlyzkostudyniteonedimensionalautomataonalengthNdiscretecircle. Expressingtheentriesintheautomatonattime t as a t 0 a t 1 a t N )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 ,theystudy therulethatmaps a t 0 ;a t 1 ; ;a t N )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 a t N )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 + a t 1 ;a t 0 + a t 2 ; ;a t N )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 + a t 0 ; referredtoasRule90.Thepaperdiscussesindetailthecasewhere a i 2 Z = 2 Z and thengeneralizestothecasefor a i 2 Z =n Z .Thecasediscussedindetailherewillbe thatfor Z = 2 Z Figure1. Rule90over Z = 2 Z Becauseanautomatoniscompletelydescribedbyitsentriesattime t andits updaterule,Wolfram,Martin,andOdlyzkodevelopnotationthatdescribeseach ofthese.Theywritetheonedimensionalautomatonof N cellsattime t asthe 18 PAGE 23 polynomial, A t x = N )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 X i =0 a t i x i ; withallcoecientsinacommutativeringinthiscase, Z = 2 Z andthevalueofthe i thcellisgivenbythecoecientof x i .Intheeorttodescribetheupdateruleusing apolynomial,itisusefultointroduceheretheuseofLaurentpolynomials.Notethat multiplicationof A t x by x j describesastateintheautomatonwherealltheentries havebeenshifted j positionstotherightorleft.Tokeepthelengthoftheautomaton constantandtoaddressthefactthattheleftandrightmostedgesoftheautomaton aregluedtogether,theyreducetheproductof A t x andaLaurentpolynomial modulo x N )]TJ/F25 11.9552 Tf 10.692 0 Td [(1.Notingthatwecanshifttheentriesofastateattime t usingLaurent polynomials,itisclearthatupdaterulescanbeappliedusingmultiplicationofthe statebyaLaurentpolynomial. Becausetheupdateruledescribedcanbeconsideredasasumofthestateshifted onecelltotherightandthestateshiftedonecelltotheleft,itcanbeappliedusing multiplicationbytheLaurentpolynomial x + x )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 .Thispolynomialnotationallows forthestudyofcellularautomataovercommutativeringstobetranslatedtoastudy ofLaurentpolynomialsovercommutativerings. Example 3.1 Weupdate ; 0 ; 0 ; 0 withtheupdateruledescribedbymultiplicationby x + x )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 : x 0 +0 x 1 +0 x 2 +0 x 3 x + x )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 = x + x )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 x + x 3 mod x 4 )]TJ/F25 11.9552 Tf 11.955 0 Td [(1=0 x 0 +1 x 1 +0 x 2 +1 x 3 mod x 4 )]TJ/F25 11.9552 Tf 11.956 0 Td [(1 : Notingthateverystatehasauniquesuccessorintimebutmayhaveanynumber ofpredecessors,Wolfram,Martin,andOdlyzkostudyhowmanystateshaveatleast onepredecessor.Theydoindetailthecasefortheautomatonover Z = 2 Z ,andsothis isthecasepresentedhere.Tostudythefractionofstatesthatarereachablethrough theevolutionoftheautomata,theybeginwithalemma: 19 PAGE 24 Lemma 3.2 [Lemma3.1in[ 15 ]]Congurationscontaininganoddnumberof siteswithvalue1canneverbegeneratedintheevolutionofthecellularautomaton dened[bytheupdaterulegiven],andcanoccuronlyasinitialstates. Proof. sketchLet A beastateintheautomatondened.Thenitssuccessor statecanbewrittenas A x = x + x )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 A x + R x x N )]TJ/F25 11.9552 Tf 11.955 0 Td [(1= x 2 +1 B x + R x x N )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 where B x and R x areLaurentpolynomials.Because x 2 +1 x N )]TJ/F25 11.9552 Tf 11.959 0 Td [(1 0mod2 when x =1, A 0mod2.Itfollowsthat A x ,andhenceanystatewitha predecessor,hasanevennumberofsiteswithvalue1. Usingthislemmatoprovethefollowingtheorem,Wolframetal.givethefraction ofstatesthatarereachableintheevolutionoftheautomatondened. Theorem 3.3 [Theorem3.1in[ 15 ]]Thefractionofthe 2 N possiblecongurationsofasize N cellularautomatondened[bytheupdaterulegivenabove]which canoccuronlyasinitialstates,andcannotbereachedbyevolution,is 1 = 2 for N odd and 3 = 4 for N even. Proof. sketchAstate A x isreachablethroughevolutionoftheautomaton ithereexists A x satisfying A x x + x )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 A x mod x N )]TJ/F25 11.9552 Tf 11.955 0 Td [(1,sothat A x = x 2 +1 B x + R x x N )]TJ/F25 11.9552 Tf 11.955 0 Td [(1 asintheproofofLemma3.2. For N even, x )]TJ/F25 11.9552 Tf 13.204 0 Td [(1 2 j x N )]TJ/F25 11.9552 Tf 13.204 0 Td [(1and x )]TJ/F25 11.9552 Tf 13.204 0 Td [(1 2 x 2 +1mod2.Hence,it isevidentfromEquation8that x )]TJ/F25 11.9552 Tf 13.27 0 Td [(1 2 j A x .Nowitispossibletowrite A x = x )]TJ/F25 11.9552 Tf 13.261 0 Td [(1 2 C x = x + x )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 xC x forsomepolynomial C x ,andsoa predecessorfor A x wouldbegivenby xC x .Becausedeg A x N ,itis clearthatdeg C x N )]TJ/F25 11.9552 Tf 11.167 0 Td [(2.Thereareexactly2 N )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 suchpolynomialsandsothere are2 N )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 reachablecongurations,or1 = 4oftotalcongurations. 20 PAGE 25 When N isodd,Lemma3.2statesthatallreachablestateshaveanevennumber ofcellswithvalue1.Itsucestoshowthatallstatesthathaveanevennumber ofcellswithvalue1arereachableintheevolutionoftheautomaton.Toseethis, supposethat A x hasanevennumberofcoecientsthatare1s.Apolynomial A x over Z = 2 Z withanevennumberoftermscanalwaysbewrittenas x +1 D x Moreover, x +1canbewrittenas x +1= x + x )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 x 2 + x 4 + + x N )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 ; andsoapredecessorfor A x isgivenby x 2 + x 4 + + x N )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 D x .Thiscompletes theproof. Inthechaptersthatfollow,similarresultswillbedevelopedfortheautomaton overanymultiplicativegroupandthenthedihedralgroupwith2 n elements, D 2 n Because D 2 n isnotaringandnotabelian,wecannotusepolynomials.Instead, wewilldevelopanapproachtothestudyofRule90overmultiplicativegroupsand proceedtocompleteananalogofLemma3.2andTheorem3.3forthisautomaton over D 2 n 21 PAGE 26 CHAPTER4 AutomataOveraMultiplicativeGroup Inthestudyofcellularautomata,oneisinterestedinpredictinglongtermbehaviorofanautomatonbasedonitslocalrules.Intheclassicalcaseofadditive cellularautomata,onereliesheavilyonthesuperpositionprinciple"whichgivesthe automatonitsadditiveproperty.Todenethissuperpositionprinciple,wewillconsiderastate S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 with d i inanadditiveabeliangroupaselementsin G W .Ifanautomatonsatisesthesuperpositionprinciple,thenitsupdateruleisa homomorphismfrom G W G W [ 14 ].Forexample,Rule90isgivenasfollows:let S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 beastatein Z = 2 Z W ,anddene : Z = 2 Z W Z = 2 Z W S = d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 + d 1 mod2 ; d 0 + d 2 mod2 ; ; d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 + d 0 mod2 : Because Z = 2 Z W isabelian, isahomomorphism. WewishtoconsidertheRule90overanon-abeliangroup, G .Letting S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 beastatein G W ,westudythefollowingupdaterule: : G W G W S = d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 d 1 ;d 0 d 2 ; ;d W )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 d 0 : Itisclearthat,becausethe d i sdonotcommute, isnotingeneralahomomorphism. Asaresult,wecannotapplythetechniquesthathavebeenusedinthepast.Inour studyofcellularautomata,wedevelopnewtechniquestostudythebehaviorofcellular automataovermultiplicativegroupsandapplythetechniquestomultiplicativenonabeliangroups.Inparticular,westudythefractionofstatesinacellularautomaton 22 PAGE 27 thathavepredecessors;thatis,westudythefractionofstatesthatarereachable throughevolutionoftheautomaton.Ourstrategyistodevelopthenecessaryand sucientconditionsforastatetohaveapredecessor.Wewillshowthat,givenastate S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 andatmosttwoentriesfromitspredecessorstate S 0 ,namely c 0 and c 1 ,for c i and d i inamultiplicativegroup G ,wecanobtainallentriesin S 0 .We willthenshowthattherearerequirementson c 0 and c 1 dependingontheentriesof S .Hence,given S ,wecandeterminewhat c 0 and c 1 mustlooklike;given c 0 and c 1 wecandetermine S 0 initsentirety.Ifnosuch c 0 or c 1 exists,then S cannothavea predecessorstateandsoisunreachablethroughevolution. Weproceedbystudyingaone-dimensionalnitecellularautomatonwithperiodic boundaryconditionsoveramultiplicativegroup, G .Asnecessarythroughoutthe paper,wewillunderstandtheautomatonasbeingonalength W discretecircleor asbeingperiodicontheentirediscretelinewithperiod W .Assuch,givenastate S 0 = c 0 ; ;c W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 anditssuccessor, S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 ,wemaywriteourupdate ruleas c i mod W c i +2mod W = d i +1mod W forall i 2 Z .Thisistherulewhichwillbe studiedthroughoutthepaperunlessotherwisespecied. 1.CellsDeterminedbyTheirSuccessors Thissectionismotivatedbythedesiretowritetheentriesofastateinterms oftheentriesinitssuccessorstate.Thiscanbethoughtofasanattempttomove backwardsonetimestepintheevolutionoftheautomatondened. Let S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 beastateintheautomatonandsupposethatitspredecessor, S 0 = c 0 ; ;c W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 ,exists.Then,givenourchoiceofupdaterule,wecan write c a c a +2 = d a +1 c a +2 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 a d a +1 and c a +2 c a +4 = d a +3 c a +4 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 a +2 d a +3 : 23 PAGE 28 Combiningthetwo,wehave c a +4 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 a +1 c a d a +3 .Inthisway,weareabletowrite c a +2 j mod W intermsof c 1 a andtheentriesin S forany j 2 N .Thisisillustratedin theexamplesthatfollow. Example 4.1 a =0 W =6 c 0 c 2 = d 1 c 2 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d 1 c 2 c 4 = d 3 c 4 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 d 3 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 c 0 d 3 c 4 c 0 = d 5 c 0 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 4 d 5 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 d 5 Example 4.2 a =0 W =7 c 0 c 2 = d 1 c 2 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d 1 c 2 c 4 = d 3 c 4 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 d 3 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 c 0 d 3 c 4 c 6 = d 5 c 6 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 4 d 5 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 d 5 c 6 c 1 = d 0 c 1 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 6 d 0 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 5 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 c 0 d 3 d 0 c 1 c 3 = d 2 c 3 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 d 2 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 d 5 d 2 c 3 c 5 = d 4 c 5 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 3 d 4 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 5 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 c 0 d 3 d 0 d 4 c 5 c 0 = d 6 c 0 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 5 d 6 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 4 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 d 5 d 2 d 6 Example 4.3 a =0 W =8 c 0 c 2 = d 1 c 2 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d 1 c 2 c 4 = d 3 c 4 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 d 3 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1 c 0 d 3 c 4 c 6 = d 5 c 6 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 4 d 5 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d 1 d 5 c 6 c 0 = d 7 c 0 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 6 d 7 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 5 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 c 0 d 3 d 7 24 PAGE 29 InLemmas4.4and4.5,wewillexplicitlydescribethisproperty.Toprovethese lemmas,wewillconsidertheautomatononalength W discretecircleasanautomatonontheentirediscretelinewhichisperiodicwithperiod W Lemma 4.4 Let c i d i 2 G ,amultiplicativegroup,andlet S = ;d j ;d j +1 ; and S 0 = ;c j ;c j +1 ; bestatesdenedontheentirediscretelineintheautomatongivensuchthat S 0 evolvesto S inonetimestepundertheupdateruledened. Then,for a 2 Z and j 2 N suchthat j odd and j 3 P j : c a +2 j = 0 @ j )]TJ/F35 5.9776 Tf 5.756 0 Td [(1 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 a +2 j )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l 1 A c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 a 0 @ j +1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d a +1+4 l 1 A : Proof. Weprovethecasewhen a =0andwenotethatadding a toevery indexshiftseachentry a cellstotherightorleftanddoesnotchangetheproof.Let S 0 and S beasgiveninthestatementofthelemma.Toseethat P istrue,we applytheupdateruleto S 0 : c 0 c 2 = d 1 c 2 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d 1 c 2 c 4 = d 3 c 4 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 d 3 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1 c 0 d 3 c 4 c 6 = d 5 c 6 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 4 d 5 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 d 5 : Andso P istrue.Supposenowthat P k istruefor k odd.Then, c 2 k c 2 k +1 = d 2 k +1 c 2 k +1 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k d 2 k +1 c 2 k +1 c 2 k +2 = d 2 k +3 c 2 k +2 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k +1 d 2 k +3 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k +1 c 2 k d 2 k +3 : 25 PAGE 30 Bytheinductivehypothesis, c 2 k +2 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k +1 0 @ k )]TJ/F35 5.9776 Tf 5.756 0 Td [(1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l 1 A c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 0 @ k +1 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 1+4 l 1 A d 2 k +3 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k +2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 0 @ k +1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l 1 A c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 0 @ k +1 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 1+4 l 1 A d 1+4 k +3 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k +2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 0 @ k +1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =1 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k +2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l 1 A c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 0 @ k +1 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 1+4 l 1 A d 1+4 k +3 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 = 0 @ k +2 )]TJ/F35 5.9776 Tf 5.756 0 Td [(1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l 1 A c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 0 @ k +2+1 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 1+4 l 1 A : Hence, P istrueand P k P k +2so P j istrueforall j 2 N j odd,and j 3. Lemma 4.5 Let c i d i 2 G ,amultiplicativegroup,andlet S = ;d j ;d j +1 ; and S 0 = ;c j ;c j +1 ; bestatesdenedontheentirediscretelineintheautomatongivensuchthat S 0 evolvesto S inonetimestepundertheupdateruledened. Then,for a 2 Z and j 2 N suchthat j even and j 2 P j : c a +2 j = 0 @ j 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 a +2 j )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l 1 A c a 0 @ j 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d a +3+4 l 1 A : Proof. Asbefore,weprovethecasewhen a =0.Let S 0 beasgivenabove.To seethat P istrue,weapplytheupdateruleto S 0 : c 0 c 2 = d 1 c 2 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d 1 c 2 c 4 = d 3 c 4 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 d 3 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 c 0 d 3 : Hence, P istrue.Supposethat P k istruefor k even.Then, c 2 k c 2 k +1 = d 2 k +1 c 2 k +1 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k d 2 k +1 26 PAGE 31 c 2 k +1 c 2 k +2 = d 2 k +3 c 2 k +2 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k +1 d 2 k +3 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k +1 c 2 k d 2 k +3 : Bytheinductivehypothesis, c 2 k +2 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k +1 0 @ k 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l 1 A c 0 0 @ k 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 3+4 l 1 A d 2 k +3 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k +2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 0 @ k +2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 Y l =0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l 1 A c 0 0 @ k +2 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 Y l =0 d 3+4 l 1 A d 3+4 k +2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k +2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 0 @ k +2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =1 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k +2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l 1 A c 0 0 @ k +2 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 Y l =0 d 3+4 l 1 A d 3+4 k +2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 = 0 @ k +2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k +2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l 1 A c 0 0 @ k +2 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d 3+4 l 1 A : So P istrueand P k P k +2so P j istrueforall j 2 N j even,and j 2. WenotethattheproofsofLemmas4.4and4.5areverysimilar.Recallingthat for j 2 N j 2 = 8 > > < > > : j )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 j odd j 2 j even j 2 = 8 > > < > > : j +1 2 j odd j 2 j even, wecombineLemmas4.4and4.5toprovethefollowingtheorem. Theorem 4.6 Let c i d i 2 G ,amultiplicativegroup,andlet S = ;d j ;d j +1 ; and S 0 = ;c j ;c j +1 ; bestatesdenedontheentirediscreteline.Then S 0 evolvesto S inonetimestepiforall a 2 Z and j 2 N j 2 P j : c a +2 j = 0 @ b j 2 c)]TJ/F34 7.9701 Tf 10.35 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 a )]TJ/F34 7.9701 Tf 6.586 0 Td [(3+2 j )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l 1 A c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 j a 0 @ d j 2 e)]TJ/F34 7.9701 Tf 10.35 0 Td [(1 Y l =0 d a +1+2 j +1mod2+4 l 1 A : 27 PAGE 32 Proof. Wecanseethat S 0 evolvesto S inonetimestepusingLemmas4.4and 4.5.Toseetheotherdirection,supposethat P j isalwayssatised.Wewantto showthat c a +2 k c a +2 k +1 = d a +2 k +1 .Withoutlossofgenerality,wewillchoose a =0 andsupposethat k iseven.Then c 2 k = 0 @ k 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l 1 A c 0 0 @ k 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d 3+4 l 1 A and c 2 k +1 = 0 @ k 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k +1 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l 1 A c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 0 @ k +2 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d 1+4 l 1 A : Then c 2 k c 2 k +1 = 0 @ k 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l 1 A c 0 0 @ k 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 3+4 l 1 A 0 @ k 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k +1 )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l 1 A c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 0 @ k +2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 1+4 l 1 A : Wewillshowrstthat 0 @ k 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d 3+4 l 1 A = 0 @ k 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k +1 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l 1 A )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 : Expandingtheseproductsandcomputing,wearriveat d 3 d 7 d 3+4 k 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k +1 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k +1 )]TJ/F34 7.9701 Tf 6.587 0 Td [(7 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k +1 )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 k 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 = d 3 d 7 d 3+2 k )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 )]TJ/F26 11.9552 Tf 5.479 -9.683 Td [(d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 d 2 k )]TJ/F34 7.9701 Tf 6.587 0 Td [(5 d 2 k +2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [( k )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 = d 3 d 7 d 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 )]TJ/F26 11.9552 Tf 5.48 -9.683 Td [(d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(5 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 3 =1 asdesired.Itremainstoshowthat 0 @ k 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l 1 A 0 @ k +2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 1+4 l 1 A = d 2 k +1 : 28 PAGE 33 Weexpandtheproductsandcomputetond 0 @ k 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l 1 A 0 @ k +2 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d 1+4 l 1 A = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(7 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 k 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 d 1 d 5 d 1+4 k +2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 d 1+4 k +2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.587 0 Td [(7 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [( k )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 )]TJ/F26 11.9552 Tf 5.479 -9.684 Td [(d 1 d 5 d 1+ k +4 )]TJ/F34 7.9701 Tf 6.587 0 Td [(8 d 1+ k +4 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 = )]TJ/F26 11.9552 Tf 5.479 -9.684 Td [(d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 k )]TJ/F34 7.9701 Tf 6.586 0 Td [(7 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 d 1 d 5 d 2 k )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 d 2 k +1 = d 2 k +1 asdesired.Thiscompletestheproof. Knowingnowhowtodescribespecicentriesinastateusingentriesfromits successorstate,wehopetomoveforwardtodescribeanentirestateintermsofits successor. 2.StatesDeterminedbyTheirSuccessors Asbefore,let S 0 = c 0 ; ;c W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 evolveto S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 inonetimestep. ThevalueofTheorem4.6liesinthefactthatitallowsustowrite c a +2 j intermsonly of c a andtheentriesinthesuccessorstate, S .Takingtheindicesoftheelementsof S and S 0 modulo W ,wenotethat,when j = W or2 j = W ,wecanwrite c a nontrivially intermsofitselfandtheentriesof S .Assumingtheentriesof S areknownand c a is unknown,thenTheorem4.6givesaformulafor c a .Ifitcanbesolved,then c a and everyentryof S 0 indexedby a +2 k for k 2 N exists.Ifnot,thenthereisnosolution for c a oranyentryof S 0 indexedby a +2 k for k 2 N .Hence,for W odd,theexistence of c a guaranteestheexistenceofeveryelementof S 0 .For W even,theexistenceof c a guaranteesonlytheexistenceoftheelementsof S 0 thathavethesameparityas a Thispropertyisillustratedinthefollowingexamples: 29 PAGE 34 Example 4.7 W=7,a=0 c 0 c 2 = d 1 c 2 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d 1 c 2 c 4 = d 3 c 4 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 d 3 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 c 0 d 3 c 4 c 6 = d 5 c 6 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 4 d 5 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 d 5 c 6 c 1 = d 0 c 1 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 6 d 0 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 5 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 c 0 d 3 d 0 c 1 c 3 = d 2 c 3 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 d 2 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 d 5 d 2 c 3 c 5 = d 4 c 5 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 3 d 4 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 5 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 c 0 d 3 d 0 d 4 c 5 c 0 = d 6 c 0 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 4 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 d 5 d 2 d 6 ReducingtheindicesinTheorem4.6modulo W =7,weseethattheformulas aboveareaspredicted. Example 4.8 W=6,a=0 c 0 c 2 = d 1 c 2 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 c 2 c 4 = d 3 c 4 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 d 3 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1 c 0 d 3 c 4 c 0 = d 5 c 0 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 4 d 5 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d 1 d 5 Asbefore,wetaketheindicesinTheorem4.6modulo W =6.Inthisexample, weseethat c 0 canonlydescribe c 0 c 2 and c 4 ,andtheonlyelementsfrom S necessary todosoare d 1 ;d 3 ; and d 5 .Todescribe c 1 ;c 3 and c 5 ,weproceedasbefore. c 1 c 3 = d 2 c 3 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 d 2 c 3 c 5 = d 4 c 5 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 3 d 4 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 c 1 d 4 c 5 c 1 = d 0 c 1 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 5 d 0 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 4 c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1 d 2 d 0 30 PAGE 35 Similarly, c 1 canonlydescribe c 1 c 3 and c 5 ,andtheonlyelementsfrom S necessary todosoare d 0 ;d 2 ; and d 4 Theexampleabovefor W =6motivatesthedevelopmentofnotationtodiscuss whichelementsfrom S areneededtodescribetheelementsof S 0 .Wenotethat S 0 = c 0 ; ;c 5 canbeunderstoodastwostates, S 0 0 = c 0 ;c 2 ;c 4 and S 0 1 = c 1 ;c 3 ;c 5 andwecandene S 0 = d 1 ;d 3 ;d 5 and S 1 = d 0 ;d 2 ;d 4 tocorrespondaccordingly 1 Wedeneareducedstateasfollows. Definition 4.9 Areducedstate, T a ,isastatesuchthatitspredecessorstate, T 0 a ifitexists,canbecompletelygeneratedbytheelementsof T a andthe a th entryof T 0 a Definition 4.10 Areducedpredecessorstate, T 0 a ,isastatewhosesuccessorstate, T a isareducedstate. Forsimplicity,wewillalwaystake a =0.Forautomataofoddlength,allstatesare reduced:asnoted,theirpredecessorstatescanbegeneratedcompletelybytheentries ofthestateitselfand c 0 .Forautomataofevenlength,astate S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 isa combinationoftworeducedstates, S 0 = d 1 ;d 3 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 withreducedpredecessor S 0 0 = c 0 ;c 2 ; ;c W )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 and S 1 = d 0 ;d 2 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 withreducedpredecessor S 0 1 = c 1 ;c 3 ; ;c W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Example 4.11 Let G = D 6 = PAGE 36 3.Summary ThenotationdevelopedinSections1and2givesusawaytounderstandastate intheautomatondenedintermsonlyofoneofitsentriesandtheentriesofits successor.Corollaries4.12,4.13,and4.14describewhenastatehasapredecessor usingtheworkandnotationdevelopedinsections1and2. Corollary 4.12 Let W 2 N suchthat 2 W .Let S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 beastate intheautomatondenedoveramultiplicativegroup, G .Then S hasapredecessor S 0 = c 0 ; ;c W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 ithereexists c 0 2 G satisfying c 0 0 @ W )]TJ/F35 5.9776 Tf 5.756 0 Td [(1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W 1 A c 0 = W +1 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y k =0 d +4 k mod W : Proof. Forthisproof,wewillunderstand S and S 0 asstatesintheautomaton denedontheentirediscretelinethatareperiodicwithperiod W .Forsimplicity, wewillwritethestatesashavinglength W Supposerstthat S hasapredecessor S 0 = c 0 ; ;c W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 .Then,byapplication ofLemma4.4for j = W ,weseethat c 0 satisesEquation12. Conversely,supposethatthereexists c 0 2 G satisfyingEquation12andlet S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 .Construct S 0 = c 0 ; ;c W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 suchthat c i mod W c i +2mod W = d i +1mod W usingthefollowingmethod: c 0 c 2 = d 1 c 2 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d 1 c 2 c 4 = d 3 c 4 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1 c 0 d 3 c W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 c 1 = d 0 c 1 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 d 0 andsoon.Becausewehavealreadychosen c 0 ,wecanworkthiswayonlyuntil c W )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 c 0 = d W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 c 0 = c W )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 .Allthatremainsistoshowthatthe c 0 chosen 32 PAGE 37 satises c 0 = c W )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 .Todoso,wewillshowthat c W )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 c 0 = d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 .Werewrite Equation12tond c 0 = 0 @ W )]TJ/F35 5.9776 Tf 5.757 0 Td [(1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 W )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 k mod W 1 A c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 0 @ W +1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W 1 A Byconstructionof c W )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 ,wecanuseLemma4.5toseethat c W )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 = c 2 W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1mod W = 0 @ W )]TJ/F35 5.9776 Tf 5.756 0 Td [(1 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y k =0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 k mod W 1 A c 0 0 @ W )]TJ/F35 5.9776 Tf 5.756 0 Td [(1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W 1 A : Hence, c W )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 c 0 = )]TJ/F26 11.9552 Tf 5.48 -9.684 Td [(d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 W )]TJ/F34 7.9701 Tf 6.587 0 Td [(5 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 5 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1 c 0 d 3 d 7 d 2 W )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 )]TJ/F26 11.9552 Tf 12.952 -9.684 Td [(d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 2 W )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 7 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d 1 d 5 d 2 W )]TJ/F34 7.9701 Tf 6.586 0 Td [(5 d 2 W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 = )]TJ/F26 11.9552 Tf 5.48 -9.684 Td [(d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 W )]TJ/F34 7.9701 Tf 6.587 0 Td [(5 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 5 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1 c 0 d 3 d 7 d W )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 )]TJ/F26 11.9552 Tf 12.951 -9.684 Td [(d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 W )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 7 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 d 5 d W )]TJ/F34 7.9701 Tf 6.587 0 Td [(5 d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 = d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 asdesired. Asimilarproofrevealsthefollowingtwocorollaries. Corollary 4.13 Let W 2 N suchthat W =2 m and 2 m .Let S = d 1 ;d 3 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 beareducedstateintheautomatondenedoveramultiplicativegroup, G .Then S hasapredecessor S 0 = c 0 ;c 2 ; ;c W )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 ithereexists c 0 2 G satisfying c 0 0 @ m )]TJ/F35 5.9776 Tf 5.756 0 Td [(1 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y k =0 d +4 k mod W 1 A c 0 = m +1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W Wenoteherethat,forastateoftheformgiveninCorollary4.13tohavea predecessor,theremustalsoexista c 1 2 G satisfying c 1 0 @ m )]TJ/F35 5.9776 Tf 5.756 0 Td [(1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W 1 A c 1 = m +1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W : ThisequationisinaccordancewithTheorem4.6for a =1. 33 PAGE 38 Corollary 4.14 Let W 2 N suchthat W =2 m and 2 j m .Let S = d 1 ;d 3 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 beareducedstateintheautomatondenedoveramultiplicativegroup, G .Then S hasapredecessor S 0 = c 0 ;c 2 ; ;c W )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 ithereexists c 0 2 G satisfying 0 @ m 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W 1 A c 0 = c 0 0 @ m 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W 1 A AsinCorollary4.13,astateoftheformgiveninCorollary4.14hasapredecessor iftherealsoexistsa c 1 2 G satisfying 0 @ m 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W 1 A c 1 = c 1 0 @ m 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W 1 A : Again,thisequationisinaccordancewithTheorem4.6for a =1. 34 PAGE 39 CHAPTER5 AnAutomatonOvertheDihedralGroup Inthischapter,westudytheautomatondenedinChapter4overthedihedral groupoforder2 n generatedbyarotation r andaip s ,namely, D 2 n = PAGE 40 r i 2 s j 2 = W +1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W : Whenthestatehasevenwidth, W =2 m suchthat 2 m ,weuse r i 1 s j 1 = m )]TJ/F35 5.9776 Tf 5.756 0 Td [(1 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y k =0 d +4 k mod W r i 2 s j 2 = m +1 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y k =0 d +4 k mod W : Finally,whenastatehaswidth W =2 m suchthat 2 j m ,weuse r i 1 s j 1 = m 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W r i 2 s j 2 = m 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W UsingnotationfromNote5.2,wesimplifyEquations12and13.Wewillwrite themas r x s y r i 1 s j 1 r x s y = r i 2 s j 2 where c 0 = r x s y .UsingLemma5.1,werewritetheaboveas r x + i 1 )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 i 1 y mod n s j 1 + y mod2 r x s y = r i 2 s j 2 r x + i 1 )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 i 1 y + x )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 x j 1 + y mod2mod n s j 1 +2 y mod2 = r i 2 s j 2 = r x + i 1 )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 i 1 y + x )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 x j 1 + y mod2mod n s j 1 mod2 = r i 2 s j 2 = r i 1 +2 x )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 x j 1 + y mod2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 i 1 y mod n s j 1 mod2 = r i 2 s j 2 : So,forareducedstateofoddlengthtohaveacorrespondingreducedpredecessor, itselementsmustsatisfytherequirement j 1 j 2 mod2 : 36 PAGE 41 Additionally,theremustexistapair x 2 Z =n Z and y 2 Z = 2 Z satisfying 2 x )]TJ/F25 11.9552 Tf 11.955 0 Td [( j 1 + y mod2 )]TJ/F25 11.9552 Tf 11.955 0 Td [(2 i 1 y i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n: Wenowrepeattheaboveforareducedstateofevenlength.WewriteEquation 15as r i 1 s j 1 r x s y = r x s y r i 2 s j 2 : Again, c 0 = r x s y .WeuseLemma5.1toseethat r i 1 + x )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 xj 1 mod n s j 1 + y mod2 = r x + i 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 i 2 y mod n s j 2 + y mod2 r 2 i 2 y )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 xj 1 mod n s j 1 = r i 2 )]TJ/F37 7.9701 Tf 6.587 0 Td [(i 1 mod n s j 2 : Asbefore,forareducedstate S tohaveacorrespondingreducedpredecessor,its elementsmustsatisfy j 1 j 2 mod2Equation17.Theremustalsoexistapair x 2 Z =n Z and y 2 Z = 2 Z satisfying 2 i 2 y )]TJ/F25 11.9552 Tf 11.955 0 Td [(2 xj 1 i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n: Havingaddressedallcases,webegintointerprettheserequirementswiththegoal ofstatingthefractionofstatesthatarereachablethroughevolutionoftheautomaton over D 2 n .Forthereader'sconvenience,werestateandrephraseWolfram,Martinand Odlyzko'stheoremfortheautomatonover Z = 2 Z beforestatingtheanalogoustheorem fortheautomatonover D 2 n Theorem 5.3 [Theorem3.3,Theorem3.1in[ 15 ]]Thefractionofthe 2 N possible congurationsofasize N cellularautomatondened[bytheupdaterulegiven]which canbereachedbyevolutionis 1 = 2 for N oddand 1 = 4 for N even. Theorem 5.4 Thefractionofthe n W possiblestatesofasize W cellular automatondenedinChapter5overthedihedralgroupof 2 n elementswhichcanbe reachedthroughevolutionoftheautomatonisgiveninthetablebelow. 37 PAGE 42 n odd n even W odd 1 2 1 4 W =2 m m odd 1 4 1 16 W =2 m m even n m 4 + n m )]TJ/F35 5.9776 Tf 5.756 0 Td [(1 )]TJ/F34 7.9701 Tf 6.587 0 Td [( n m )]TJ/F35 5.9776 Tf 5.756 0 Td [(2 2 n W n m 8 + n m )]TJ/F35 5.9776 Tf 5.756 0 Td [(1 )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 n m )]TJ/F35 5.9776 Tf 5.756 0 Td [(2 2 n W Theorem5.4wasconjecturedinlargepartduetodataobtainedfromtheprogram seeninAppendixA,developedbytheauthorundertheguidanceofMichaelRose, U.C.Berkeley. Knowingnowwhatrequirementsareducedstatemustsatisfytohaveapredecessor,wecountthefractionofstatesthatsatisfytheserequirements.Becauseboththe W oddand W evencaserequireastate S tosatisfyEquation17,weinterpretthis requirementrst.AnunderstandingofEquation17isgiveninthetheorembelow, precededbyalemmathatwillbeusedinitsproof. Lemma 5.5 Theproductof 2 k +1 elementsin D 2 n )]TJ/F26 11.9552 Tf 12.619 0 Td [( PAGE 43 Proof. Supposerstthat S isareducedstateand j 1 = j 2 .Thenusingthe notationfromNote5.2,weconsidertheproductofallelementsof S as r i 1 s j 1 r i 2 s j 2 UsingLemma5.1,wewritethisproductas r i 1 + i 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 i 2 j 1 mod n s j 1 + j 2 mod2 .Since j 1 = j 2 thisproductliesin PAGE 44 : O W E W S = sd 0 ;d 1 ; ;d W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 : Then S = s d 0 ;d 1 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 = ssd 0 ;d 1 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 = S ,so hasan inverseandhenceisabijection.Itfollowsthatthefractionofthe n W statesin theautomatondenedinChapter5over D 2 n whichhaveanevennumberofterms in D 2 n )]TJ/F26 11.9552 Tf 12.619 0 Td [( PAGE 45 Theorem 5.9 LinearCongruenceLet a;b 2 Z ,let n 2 N ,andlet gcd a;n = d Then ax b mod n hasasolutionfor x i d j b .If d j b and x 0 isasolutionof ax b mod n ,thenthe set n x 0 + k n d j k 2 Z o isthesetofallsolutionsfor x .Thissetwillreduceto d solutionsmodulo n WebeginnowtheproofofTheorem5.4.AgainusingnotationfromNote5.2, weknowthatareducedstatemustsatisfy j 1 = j 2 inordertohaveapredecessor. Additionally,wemustbeabletosolveEquations18and19for x and y Supposingthat j 1 = j 2 issatised,weproceedbysolvingEquation18, 2 x )]TJ/F25 11.9552 Tf 11.955 0 Td [( y + j 1 mod2 )]TJ/F25 11.9552 Tf 11.955 0 Td [(2 yi 1 i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n for x 2 Z =n Z and y 2 Z = 2 Z Tond x and y thatsatisfytheabove,wenotethattherearetwocases: j 1 =0 and j 1 =1.First,let j 1 =0.ThenEquation18becomes 2 x )]TJ/F26 11.9552 Tf 11.955 0 Td [(y )]TJ/F25 11.9552 Tf 11.956 0 Td [(2 yi 1 i 2 )]TJ/F26 11.9552 Tf 11.956 0 Td [(i 1 mod n: Because y 2 Z = 2 Z ,allsolutionsareoftheform x; 0or x; 1.Thisallowsusto solvefor x byletting y =0andthenletting y =1.Suppose y =0.ThenEquation 18becomes 2 x i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n: For n suchthat2 n ,2hasamultiplicativeinversemodulo n ,andsoEquation20 reducestoandhasthesolution x 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 i 2 )]TJ/F26 11.9552 Tf 12.261 0 Td [(i 1 mod n .BytheLinearCongruence Theorem,thisistheuniquesolution.When2 j n ,then2hasnomultiplicative inversemodulo n andEquation20cannotbereducedfurther.ApplyingtheLinear 41 PAGE 46 CongruenceTheorem,Equation20hasasolutioni2 j i 2 )]TJ/F26 11.9552 Tf 12.39 0 Td [(i 1 .If2 j i 2 )]TJ/F26 11.9552 Tf 12.39 0 Td [(i 1 ,then Equation20hastwosolutions,namely x i 2 )]TJ/F37 7.9701 Tf 6.586 0 Td [(i 1 2 mod n and x i 2 )]TJ/F37 7.9701 Tf 6.587 0 Td [(i 1 2 + n 2 mod n When y =1,thenEquation18becomes )]TJ/F25 11.9552 Tf 9.298 0 Td [(2 i 1 i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n 0 i 2 + i 1 mod n: Inthiscase,thereisnodependenceon x .Hence,if0 i 2 + i 1 mod n ,thentheset f x = k j k 2 Z =n Z g isthesetofsolutionsfor x .Thiscompletesthecasefor j 1 =0. Letting j 1 =1,Equation18reducesto 2 x )]TJ/F25 11.9552 Tf 11.955 0 Td [( y +1mod2 )]TJ/F25 11.9552 Tf 11.955 0 Td [(2 yi 1 i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n: Proceedingasbefore,wesupposethat y =0.Thenwecanreducetheaboveto 0 i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n: AsinEquation21,thereisnodependenceon x .Hence,if0 i 2 )]TJ/F26 11.9552 Tf 12.319 0 Td [(i 1 mod n ,then theset f x = k j k 2 Z =n Z g isthesetofsolutionsfor x When y =1,Equation18becomes 2 x )]TJ/F25 11.9552 Tf 11.955 0 Td [(2 i 1 i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n 2 x i 2 + i 1 mod n: For n suchthat2 n ,2hasamultiplicativeinversemodulo n ,andsoEquation23 reducestoandhasthesolution x 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 i 2 + i 1 mod n .BytheLinearCongruence 42 PAGE 47 Theorem,thisistheuniquesolution.When2 j n ,then2hasnomultiplicative inversemodulo n andEquation23cannotbereducedfurther.ApplyingtheLinear CongruenceTheorem,Equation23hasasolutioni2 j i 2 + i 1 .If2 j i 2 + i 1 ,then Equation23hastwosolutions,namely x i 2 + i 1 2 mod n and x i 2 + i 1 2 + n 2 mod n Forthereader'sconvenience,thesesolutionsaresummarizedinTable1. 43 PAGE 48 j 1 =1 2 n i 2 i 1 mod n i 2 i 1 mod2 x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 2 + i 1 mod n y =1 f x = k j k 2 Z =n Z g y =0 i 2 6 i 1 mod2 x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 2 + i 1 mod n y =1 f x = k j k 2 Z =n Z g y =0 i 2 6 i 1 mod n i 2 i 1 mod2 x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 2 + i 1 mod n y =1 i 2 6 i 1 mod2 x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 2 + i 1 mod n y =1 2 j n i 2 i 1 mod n i 2 i 1 mod2 x i 2 + i 1 2 mod n;y =1; x i 2 + i 1 2 + n 2 mod n y =1 f x = k j k 2 Z =n Z g y =0 i 2 6 i 1 mod2 nosolutions i 2 6 i 1 mod n i 2 i 1 mod2 x i 2 + i 1 2 mod n;y =1; x i 2 + i 1 2 + n 2 mod n y =1 f x = k j k 2 Z =n Z g y =0 i 2 6 i 1 mod2 nosolutions j 1 =0 2 n i 2 )]TJ/F26 11.9552 Tf 21.918 0 Td [(i 1 mod n i 2 i 1 mod2 x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 2 )]TJ/F26 11.9552 Tf 11.265 0 Td [(i 1 mod n y =0 f x = k j k 2 Z =n Z g y =1 i 2 6 i 1 mod2 x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 2 )]TJ/F26 11.9552 Tf 11.265 0 Td [(i 1 mod n y =0 f x = k j k 2 Z =n Z g y =1 i 2 6)]TJ/F26 11.9552 Tf 21.918 0 Td [(i 1 mod n i 2 i 1 mod2 x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 2 )]TJ/F26 11.9552 Tf 11.265 0 Td [(i 1 mod n y =0 i 2 6 i 1 mod2 x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 2 )]TJ/F26 11.9552 Tf 11.265 0 Td [(i 1 mod n y =0 2 j n i 2 )]TJ/F26 11.9552 Tf 21.918 0 Td [(i 1 mod n i 2 i 1 mod2 x i 2 )]TJ/F37 7.9701 Tf 6.586 0 Td [(i 1 2 mod n;y =0; x i 2 )]TJ/F37 7.9701 Tf 6.586 0 Td [(i 1 2 + n 2 mod n y =0 f x = k j k 2 Z =n Z g y =1 i 2 6 i 1 mod2 nosolutions i 2 6)]TJ/F26 11.9552 Tf 21.918 0 Td [(i 1 mod n i 2 i 1 mod2 x i 2 )]TJ/F37 7.9701 Tf 6.586 0 Td [(i 1 2 mod n y =0; x i 2 )]TJ/F37 7.9701 Tf 6.586 0 Td [(i 1 2 + n 2 mod n y =0 i 2 6 i 1 mod2 nosolutions Table1. 2 x )]TJ/F25 11.9552 Tf 11.955 0 Td [( y + j 1 mod2 )]TJ/F25 11.9552 Tf 11.955 0 Td [(2 yi 1 i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n 44 PAGE 49 Withthegoalofdescribingthefractionofstatesinthisautomatonthathave predecessors,weuseTable1tocounthowoftenEquation18hasasolution.Having alreadycountedthefractionofstatesthatsatisfy j 1 = j 2 ,wecannowcompletethe studyofstatesoflength W suchthat4 W Beforeproceeding,weprovealemma. Lemma 5.10 For n 2 N suchthat 2 j n ,thefractionofpairs i 1 ;i 2 suchthat i 1 ;i 2 2 Z =n Z and i 1 i 2 mod2 is 1 2 Proof. Let n 2 N suchthat2 j n .Let A bethesetofallpairs a;b such that a;b 2 Z =n Z and a b mod2,andlet B bethesetofpairs c;d suchthat c;d 2 Z =n Z and c 6 d mod2.Dene : A B a;b = a +1mod n;b : Weshowthat isabijection.Dene : B A c;d = c )]TJ/F25 11.9552 Tf 11.955 0 Td [(1mod n;d : Then a;b = a +1mod n;b = a;b so hasaninverseandhenceisa bijection.Itfollowsthatthefractionofpairs i 1 ;i 2 suchthat i 1 ;i 2 2 Z =n Z and i 1 i 2 mod2is 1 2 Supposerstthat W isodd.Thenfor n odd,allstatessatisfying j 1 = j 2 have atleastonepredecessorandso 1 2 ofstateshaveatleastonepredecessor.When n iseven,onlythestateswhichsatisfy j 1 = j 2 and i 1 i 2 mod2haveatleastone predecessor.ByLemma5.10, 1 2 ofstatessatisfy i 1 i 2 mod2.So,when W isodd and n iseven,thefractionofallstatesthathaveatleastonepredecessoris1 = 4. When W isevensuchthat4 W ,werecallthatastate S iscomposedoftwo reducedstatesthatneedtoconcurrentlysatisfythesamerequirementsasthosein 45 PAGE 50 thecasefor W odd.Hence,wesquaretheprobabilitiesabovetoseethatwhen W is even W and n isodd,thefractionofstateswhichhaveatleastonepredecessor is1 = 4.When W iseven W and n iseven,thisfractionis1 = 16. Havingcompletedthecaseforautomataoflength W suchthat4 W ,weproceed tostudythecasewhen4 j W .Todoso,wesupposethat j 1 = j 2 issatisedandwe lookforsolutionsofEquation19, 2 i 2 y )]TJ/F25 11.9552 Tf 11.955 0 Td [(2 xj 1 i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n: Supposerstthat j 1 =0.Then,Equation19becomes 2 i 2 y i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n: Nomatterthechoiceof y ,thereisnodependenceon x inthiscase.When y =0,if 0 i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n ,thesetofsolutionsfor x is f x = k j k 2 Z =n Z g : When y =1,if0 )]TJ/F26 11.9552 Tf 21.918 0 Td [(i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 ,thesetofsolutionsfor x isasbefore, f x = k j k 2 Z =n Z g : Now,let j 1 =1.ThenEquation19becomes 2 i 2 y )]TJ/F25 11.9552 Tf 11.956 0 Td [(2 x i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n: When y =0,thissimpliesto )]TJ/F25 11.9552 Tf 9.298 0 Td [(2 x i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n: For n suchthat2 n ,2hasamultiplicativeinversemodulo n ,andsoEquation24 reducestoandhasthesolution x 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 i 2 + i 1 mod n .BytheLinearCongruence Theorem,thisistheuniquesolution.When2 j n ,then2hasnomultiplicative 46 PAGE 51 inversemodulo n andEquation24cannotbereducedfurther.ApplyingtheLinear CongruenceTheorem,Equation24hasasolutioni2 j i 2 )]TJ/F26 11.9552 Tf 12.39 0 Td [(i 1 .If2 j i 2 )]TJ/F26 11.9552 Tf 12.39 0 Td [(i 1 ,then Equation24hastwosolutions,namely x )]TJ/F37 7.9701 Tf 23.113 4.813 Td [(i 2 )]TJ/F37 7.9701 Tf 6.587 0 Td [(i 1 2 mod n and x )]TJ/F37 7.9701 Tf 23.113 4.813 Td [(i 2 )]TJ/F37 7.9701 Tf 6.587 0 Td [(i 1 2 + n 2 mod n Wenowlet y =1andsimplifyEquation19to 2 i 2 )]TJ/F25 11.9552 Tf 11.955 0 Td [(2 x i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n )]TJ/F25 11.9552 Tf 9.299 0 Td [(2 x )]TJ/F26 11.9552 Tf 21.918 0 Td [(i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n 2 x i 2 + i 1 mod n: For n suchthat2 n ,2hasamultiplicativeinversemodulo n ,andsoEquation25 reducestoandhasthesolution x 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 i 2 + i 1 mod n .BytheLinearCongruence Theorem,thisistheuniquesolution.When2 j n ,then2hasnomultiplicative inversemodulo n andEquation25cannotbereducedfurther.ApplyingtheLinear CongruenceTheorem,Equation25hasasolutioni2 j i 2 + i 1 .If2 j i 2 + i 1 ,then Equation25hastwosolutions,namely x i 2 + i 1 2 mod n and x i 2 + i 1 2 + n 2 mod n ThesesolutionsaresummarizedinTable2. 47 PAGE 52 j 1 =1 2 n i 2 i 1 mod2 x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 2 + i 1 mod n y =1 x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 1 )]TJ/F26 11.9552 Tf 11.956 0 Td [(i 2 mod n y =0 i 2 6 i 1 mod2 x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 2 + i 1 mod n y =1 x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 1 )]TJ/F26 11.9552 Tf 11.956 0 Td [(i 2 mod n y =0 2 j n i 2 i 1 mod2 x i 2 + i 1 2 mod n;y =1; x i 2 + i 1 2 + n 2 mod n y =1 x i 1 )]TJ/F37 7.9701 Tf 6.587 0 Td [(i 2 2 mod n y =0 i 2 6 i 1 mod2 nosolutions j 1 =0 2 n i 2 i 1 mod n f x k j k 2 Z =n Z g y =0 i 2 )]TJ/F26 11.9552 Tf 21.918 0 Td [(i 1 mod n f x = k j k 2 Z =n Z g y =1 i 2 6 i 1 mod n nosolutions 2 j n i 2 i 1 mod n f x k j k 2 Z =n Z g y =0 i 2 )]TJ/F26 11.9552 Tf 21.918 0 Td [(i 1 mod n f x = k j k 2 Z =n Z g y =1 i 2 6 i 1 mod n nosolutions Table2. 2 yi 2 )]TJ/F25 11.9552 Tf 11.955 0 Td [(2 xj 1 i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n UsingTable2,wecounthowoftenEquation19hasatleastonesolution.Having alreadycountedthefractionofstatesthatsatisfy j 1 = j 2 ,wecannowcompletethe studyofstatesoflength W suchthat4 j W .Wewrite W as W =2 m andrecallthat wearestudyingreducedstatesoflength m Thefractionofthestatesoflength m thatsatisfy j 1 = j 2 is1 = 2,and1 = 2ofthese satisfy j 1 = j 2 =1.For n odd,allofthesestateshavepredecessors;thisaccountsfor 1 = 4ofthe n m totalstatesoflength m .For n evenand j 1 = j 2 =1,astatealsohas tosatisfy i 1 i 2 mod2inordertohaveapredecessor;hence,ofthestatessatisfying j 1 = j 2 =1,1 = 2havepredecessors.Thisaccountsfor1 = 8ofthe n m totalstatesof length m Nowweaddressthecasewhen j 1 = j 2 =0.Tohaveapredecessor,astate mustsatisfy i 1 i 2 mod n ;wenowcountthenumberofstateswhichsatisfythis requirement.Webeginbynotingthatthereare n choicesfor i 1 andoncechosen, i 2 isxedas i 1 .Recallthat i 1 comesfromanorderedproductof m= 2elements. 48 PAGE 53 Therstelementofthisproductcanbeoneof2 n choicesandwehavethesame freedominchoiceforalltheotherelementsuntilthenalone.Thenalelementin thisproductisuniquelydeterminedbythechoicesmadebeforeitandthechoicefor i 1 .Hence,thereare n m= 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 productswhichgive r i 1 andsothereare n m= 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 productswhichgive r i 2 = r i 1 .Hence,includingthechoiceof n ,there n n m )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 ways tosatisfy i 2 i 1 mod n .Byasimilarargument,thereare n n m )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 waystosatisfy i 2 )]TJ/F26 11.9552 Tf 23.654 0 Td [(i 1 mod n .Weaddthetwotoseethatthereare2 n n m )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 waystosatisfy i 2 i 1 mod n .However,for n odd,wehavecountedthecase i 1 = i 2 =0twice, sowesubtract n m )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 fromourtotalcount.For n even,wehavecountedboth i 1 = i 2 =0and i 1 = i 2 = n= 2twiceandsowesubtract2 n m )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 fromourcount. Thisgives,for n odd,thenumberofthe n m totalreducedstatesoflength m j m whichhavepredecessorsis n m 4 + n m )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 )]TJ/F25 11.9552 Tf 12.509 0 Td [( n m )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 .For n even,this numberis n m 8 + n m )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 )]TJ/F25 11.9552 Tf 12.609 0 Td [(2 n m )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 .Werecallthatastate S oflength W j W iscomposedoftworeducedstatesthatneedtoconcurrentlysatisfythesame requirements,andsowesquarethesefractionstoarriveatthefollowing:for W even j W and n odd,thenumberofstateswhichisreachableintheevolution oftheautomatais n m 4 + n m )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 )]TJ/F25 11.9552 Tf 12.947 0 Td [( n m )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 2 ,when n iseven,thisnumberis n m 8 + n m )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 )]TJ/F25 11.9552 Tf 11.955 0 Td [(2 n m )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 2 .ThiscompletestheproofofTheorem5.4. TheproofofTheorem5.4yieldsthefollowingcorollaryregardingthein-degreeof agivenstate. Corollary 5.11 Thefollowingtabledescribesthenumberofpredecessorspossibleforastateoflength W intheautomatondenedover D 2 n 2 n 2 j n 2 W 0 1 n +1 0 2 n +2 2 j W; 4 W 0 1 n +1 n +1 2 0 4 2 n +2 n +2 2 4 j W 0 4 2 n 4 n n 2 2 n 2 0 9 3 n 6 n n 2 2 n 2 49 PAGE 54 Proof. TheproofofCorollary5.11isseenbyapplicationofTables1and2.The applicationofTables1and2willbeillustratedhere,thoughwewillnotdoallcases explicitly. Supposerstthat2 W n isodd.Then,supposeastatesatises j 1 = j 2 =1.If thestatealsosatises i 2 i 1 mod n ,thenithas n +1predecessors.Thepredecessors aredeterminedby x 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 i 2 + i 1 mod n y =1and f x = k j k 2 Z =n Z g and y =0. Ifastatedoesnotsatisfy i 2 i 1 mod n ,thenithasonlyonepredecessor,determined by x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 2 + i 1 mod n and y =1. Ifastatesatises j 1 = j 2 =0andadditionally,thestatesatises i 2 )]TJ/F26 11.9552 Tf 21.918 0 Td [(i 1 mod n thenithas n +1predecessors.Theyaredeterminedby x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 i 2 )]TJ/F26 11.9552 Tf 9.874 0 Td [(i 1 mod n and y = 0,and f x = k j k 2 Z =n Z g and y =1.Ifthestatedoesnotsatisfy i 2 )]TJ/F26 11.9552 Tf 22.459 0 Td [(i 1 mod n thenithasonlythepredecessordeterminedby x 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 i 2 )]TJ/F26 11.9552 Tf 11.955 0 Td [(i 1 mod n and y =0. Now,supposethat2 W and n iseven.Then,ifastatesatises j 1 = j 2 =1, i 2 i 1 mod n and i 2 i 1 mod2,ithas n +2predecessors,determinedby x i 2 + i 1 2 mod n and y =1, x i 2 + i 1 2 + n 2 mod n and y =1andtheset f x = k j k 2 Z =n Z and y =0.Ifastateoftheform j 1 = j 2 =1doesnotsatisfy i 2 i 1 mod2,thenithas nopredecessors. Ifastatesatises j 1 = j 2 =0, i 2 )]TJ/F26 11.9552 Tf 23.152 0 Td [(i 1 mod n ,and i 2 i 1 mod2,thenithas n +2predecessors,determinedby x i 2 )]TJ/F37 7.9701 Tf 6.586 0 Td [(i 1 2 mod n and y =0, x i 2 )]TJ/F37 7.9701 Tf 6.586 0 Td [(i 1 2 + n 2 mod n and y =0andtheset f x = k j k 2 Z =n Z and y =1.Ifthestatesatises j 1 = j 2 =0 and i 2 i 1 mod2,ithasonlytwopredecessors,givenby x i 2 )]TJ/F37 7.9701 Tf 6.587 0 Td [(i 1 2 mod n and y =0, x i 2 )]TJ/F37 7.9701 Tf 6.587 0 Td [(i 1 2 + n 2 mod n and y =0.Ifastatedoesnotsatisfy i 2 i 1 mod n ,thenit hasnopredecessors. TherestoftheproofforthiscorollaryliesinTables1and2. 50 PAGE 55 CHAPTER6 ExamplesandSuggestionsforFurtherStudy 1.Examples UsingthemethodsdescribedinChapter5,wewillgiveexamplesofstatesinthe automatondenedover D 2 n todetermineiftheyhavepredecessorsandifso,what thosepredecessorsare. Example: Let S = s;r;rs;r 2 s;s;s beastateintheautomatondenedover D 8 .Then S hasnopredecessorbecauseithasanoddnumberoftermsin D 8 )]TJ/F26 11.9552 Tf 12.619 0 Td [( PAGE 56 Explicitly,weseethatthesolutionfor c 0 is c 0 = r 0 s 0 =1 : Nowthat c 0 isxed,wecomputetheothertermsusingTheorem4.6.BecauseTheorem4.6doesnotoerasolutionfor c 2 intermsof c 0 ,wecomputethistermexplicitly. c 1 = 3 )]TJ/F35 5.9776 Tf 5.756 0 Td [(1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 6 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l mod5 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 j +1 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 1+4 l mod5 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 d 0 = r 2 s )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 r s = r c 0 c 2 = d 1 c 2 = c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d 1 = r c 3 = 4 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 8 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l mod5 c 0 4 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 3+4 l mod5 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1 c 0 d 3 d 2 = s r )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 r 2 s rs = s 52 PAGE 57 c 4 = 2 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 4 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l mod5 c 0 2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 3+4 l mod5 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 c 0 d 3 = r )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 r 2 s = rs Finally,wechecktoseethatthestateobtained, S 0 = ;r;r;s;rs ,updatesto S in onetimestep: ;r;r;s;rs rsr;r;rs;rrs;s = s;r;rs;r 2 s;s ; asdesired. Example: Let S = s;r;r;rs;rs;s beastateintheautomatondenedinChapter5over D 8 .Because S hasanevennumberoftermsin D 8 )]TJ/F26 11.9552 Tf 13.234 0 Td [( PAGE 58 and c 1 2 D 8 satisfying c 1 d 4 c 1 = d 2 d 0 ; thatis, c 1 rs c 1 = r s : Thesesimplifyto c 0 rsc 0 = rs and c 1 rsc 1 = rs Becausetheseequationsareidentical,wesolveonlyfor c 0 .Weseethat i 1 = i 2 =1 and j 1 = j 2 =1.UsingTable1,weknowthatthereare6predecessorsforthis reducedstate.Usingtheformulasgiven,thepredecessorsforthereducedstateare determinedby1, r 3 s rs r 2 s ,and r 3 s Supposethat c 0 =1and c 1 = rs .Wenowcomputetheothertermsinthepredecessor stateusingTheorem4.6asbefore. c 0 c 2 = d 1 c 2 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 = r c 1 c 3 = d 2 c 3 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 d 2 = rs r = s 54 PAGE 59 c 4 = 2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 4 )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l mod6 c 0 2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 3+4 l mod6 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1 c 0 d 3 = r )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 rs = s c 5 = 2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1+4 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l mod6 c 1 2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 1+3+4 l mod6 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 c 1 d 4 = r )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 rs rs = r 3 Finally,wechecktoseethatthestateobtained, S 0 = ;rs;r;s;s;r 3 ,updatesto S inonetimestep: ;rs;r;s;s;r 3 r 3 rs;r;rss;rs;sr 3 ;s = s;r;r;rs;rs;s asdesired. Example: Let S =1 ;r;s;rs;s;s;r;r beastateintheautomatondenedin Chapter5over D 6 .Because S hasanevennumberoftermsin D 6 )]TJ/F26 11.9552 Tf 12.619 0 Td [( PAGE 60 Inthiscase, S hasapredecessorithereexists c 0 2 D 6 satisfying d 1 d 5 c 0 = c 0 d 3 d 7 thatis, r s c 0 = c 0 rs r and c 1 2 D 8 satisfying d 2 d 6 c 1 = c 1 d 4 d 0 thatis, s r c 1 = c 1 s : Thesesimplifyto rsc 0 = c 0 s and r 2 sc 1 = c 1 s: Wesolverstfor c 0 .Inthiscase, i 1 =1, i 2 =0and j 1 = j 2 =1.UsingTable 2,weseethattherearetwosolutionsfor x and y ,determinedby x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 mod3, y =0and x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 mod3, y =1.Wewillchoosethelatter. Tosolvefor c 1 ,weseethat i 1 =2, i 2 =0,and j 1 = j 2 =1.UsingTable2, weseethattherearetwosolutionsfor x and y ,namely, x 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 mod3, y =0 and x 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 mod3, y =1.Again,wechoosethelatter.Wesolvenowforthe remainingentriesin S 0 .When c 0 = r 2 s and c 1 = rs ,wehave 56 PAGE 61 c 0 c 2 = d 1 c 2 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 0 d 1 = r 2 s )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 r = rs c 1 c 3 = d 2 c 3 = c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 d 2 = rs )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 s = r c 4 = 2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 4 )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l mod8 c 0 2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 3+4 l mod8 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1 c 0 d 3 = r )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 r 2 s rs =1 c 5 = 2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1+4 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l mod8 c 1 2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 1+3+4 l mod8 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 2 c 1 d 4 = s )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 rs s = r 2 s c 6 = 2 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 6 )]TJ/F34 7.9701 Tf 6.587 0 Td [(3 )]TJ/F34 7.9701 Tf 6.586 0 Td [(4 l mod8 c 0 4 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 1+4 l mod8 = d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 3 c )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 0 d 1 d 5 = rs )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 r 2 s )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 r s = s 57 PAGE 62 c 7 = 2 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y l =0 d )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 1+6 )]TJ/F34 7.9701 Tf 6.586 0 Td [(3 )]TJ/F34 7.9701 Tf 6.587 0 Td [(4 l mod6 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 4 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 Y l =0 d 1+1+4 l mod6 = d )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 4 c )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 1 d 2 d 6 = s )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 rs )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 s r = rs Finally,wechecktoseethatthestateobtained, S 0 = r 2 s;rs;rs;r; 1 ;r 2 s;s;rs updatesto S inonetimestep: r 2 s;rs;rs;r; 1 ;r 2 s;s;rs rsrs;r 2 srs;rsr;rs;rr 2 s;s;r 2 srs;sr 2 s = ;r;s;rs;s;s;r;r asdesired. 2.SuggestionsforFurtherStudy Inthestudyofcellularautomata,onewishestodrawthestatetransitiondiagram STD;thatis,onewishestodrawthemapofallstatesintheautomatonasnodes mappingtoeachotherundertheupdaterulefortheautomaton.OntheSTD, allnodeswithin-degreezerorepresentstatesthathavenopredecessorsandthese nodesmapintotheremainingstates,transientsandstatesoncycles.Thisdiagram isusefulininterpretingthelongtermbehaviorofautomata.Toseeanexampleof astatetransitiondiagram,wereturntothepaperAlgebraicPropertiesofCellular Automata"[ 15 ],whereinWolframetal.givethefollowingdiagram: 58 PAGE 63 Figure1. Rule90over Z = 2 Z ;eachnoderepresentsastateinthe automatondenedinChapter3. InourstudyoftheautomatondenedinChapter5over D 2 n ,wedidnotfocuson drawingthestatetransitiondiagraminfavorofndingthefractionofstateswhich havepredecessors.WenotethatthisisanimportantpieceofdatafortheSTD;this fractiongivesusthenumberofnodesthathavein-degreeofatleast1. WenowsuggestonewaytoproceedtodrawamorecompleteSTDforthisautomaton.Recallingthateachstateover D 2 n correspondstoastateover Z 2 ,itis naturaltoclassifystatesusingtheircorrespondingstatesover Z 2 .Forexample,we studyallstatesin D 2 n thatcorrespondto ; 0 ; 1in Z 2 .Thissetincludesallstates over D 2 n thatareoftheform r a ;r b ;r c s .Belowisthediagramforthebehavior ofthesestates;everynoderepresentedwithin-degree0correspondstoastatethat 59 PAGE 64 over D 6 or D 8 thatcorrespondsto ; 0 ; 1over Z = 2 Z .Thestateswithin-degree 1 correspondtostatesthatlooklike ; 1 ; 0over Z = 2 Z Figure2. Thisisapartialstatetransitiondiagramfortheautomaton inChapter5over D 6 .Here,thenodeswithin-degreezerocorrespond tostatesover D 6 thatcorrespondto ; 0 ; 1over Z = 2 Z Figure3. Thisisapartialstatetransitiondiagramfortheautomaton inChapter5over D 8 .AsinFigure2,thenodeswithin-degreezero correspondtostatesover D 8 thatcorrespondto ; 0 ; 1over Z = 2 Z Onemajordicultyofstudyingstatetransitiondiagramscomesfromthesheer numberofstates.Forexample,inanautomatonof3cellsover D 6 ,thereare6 3 states andover D 8 ,thereare8 3 states.Below,wesuggestawaytouseequivalenceclasses tomorereadilystudythisautomatonover D 2 n Proposition 6.1 Let A = a;b;c 2 D 3 2 n beastateintheautomatondenedin Chapter5over D 2 n suchthat a;b 2 PAGE 65 Proof. Itisclearthat A 1 A because A = ; 1 ;r 0 A Supposenowthat A 1 B ,thatis, A = ; 1 ;r k B for k 2 Z =n Z .Then B = ; 1 ;r )]TJ/F37 7.9701 Tf 6.587 0 Td [(k A andso B 1 A Finally,supposethat A 1 B and B 1 C ,thatis, A = ; 1 ;r k 1 B and B = ; 1 ;r k 2 C for k 1 ;k 2 2 Z =n Z .Then A = ; 1 ;r k 1 ; 1 ;r k 2 C = ; 1 ;r k 1 + k 2 mod n andso A 1 C Proposition 6.2 Let A = a;b;c 2 D 3 2 n beastateintheautomatondenedin Chapter5over D 2 n suchthat a;b 2 D 2 n )]TJ/F26 11.9552 Tf 12.619 0 Td [( PAGE 66 However,theproofsofPropositions6.1and6.2didnotrelyonthestructureof A and B ,showingthatonecoulddeneequivalencerelationsthatdeneclassesofstatesin D 2 n thatcorrespondtotheremainingstatesover Z = 2 Z 62 PAGE 67 APPENDIXA Code ThefollowingprogramwaswritteninGAP[ 16 ].Giventhelengthoftheautomatonandtheorderofthedihedralgroup,itreturnsthefractionofstatesthatarenot reachableintheevolutionoftheautomatondenedinSection5. Local_Data:=functiondihedral_group,automata_length localhash,fill_hash,row_number, new_state_hash_number,new_state_hash_number_temp, temp_hash_number,fill_automata,Automata, f,g,r,s,order,index,Reverse_Order,reverse_index, Group_Element,update_one_step,temp_automata, int_to_dihedral,temp,update_number_column, store_updated,in_degree_hash,hash_current_state, sum_automata,eden_states,Garden_Of_Eden; Automata:=NullMatdihedral_group^automata_length,2*automata_length; ################################## ##INITIALIZE## ##Here,wedefinethedihedral## ##group,itsordering,andthe## ##hashthatcountsin-degree## ##foreachstate.## ################################## ##DefineDihedralGroup## 63 PAGE 68 f:=FreeGroup"r","s"; g:=f/[f.1^dihedral_group/2,f.2^2,f.2*f.1*f.2*f.1]; r:=g.1;;s:=g.2;; ##DefineOrdering## order:=NullMat,dihedral_group; forindexin[1..dihedral_group/2]do order[1][index]:=r^index-1; order[1][index+dihedral_group/2]:=s*r^index-1; od; Reverse_Order:=functionGroup_Element forreverse_indexin[1..dihedral_group]do ifGroup_Element=order[1][reverse_index]then returnreverse_index; fi; od; end; in_degree_hash:=NullMatdihedral_group^automata_length,1; forfill_hashin[1..dihedral_group^automata_length]do in_degree_hash[fill_hash][1]:=0; od; ############################################# ##FillstatesinAutomata## ##Here,usingintegers,wefillineach## ##startingstate.Aswefillinthestate,## 64 PAGE 69 ##weupdatetheautomataonceusingour## ##updaterule.Afterupdating,weadd## ##onetohashindicatingthatwehave## ##reachedthenewstatebyevolutionof## ##theautomata.Wethenstorethenew## ##stateasintegersinourautomata.## ############################################# forrow_numberin[1..dihedral_group^automata_length]do temp_hash_number:=row_number-1; fill_automata:=0; whiletemp_hash_number>0do Automata[row_number][automata_length-fill_automata]:= RemInttemp_hash_number,dihedral_group; temp_hash_number:=QuoInttemp_hash_number,dihedral_group; fill_automata:=fill_automata+1; od; #################### #Updateonce# #################### temp_automata:=NullMat,automata_length; forint_to_dihedralin[1..automata_length]do temp:=Automata[row_number][int_to_dihedral]; temp_automata[1][int_to_dihedral]:=order[1][temp+1]; od; ##UpdateAtEndpoints## 65 PAGE 70 temp_automata[2][1]:=temp_automata[1][automata_length]*temp_automata[1][2]; temp_automata[2][automata_length]:= temp_automata[1][automata_length-1]*temp_automata[1][1]; ##UpdateInMiddle## forupdate_number_columnin[2..automata_length-1]do temp_automata[2][update_number_column]:= temp_automata[1][update_number_column-1]* temp_automata[1][update_number_column+1]; od; ##Translatetointegerbasedihedral_group,store## forstore_updatedin[1..automata_length]do Automata[row_number][automata_length+store_updated]:= Reverse_Ordertemp_automata[2][store_updated]-1; od; ######################## ##Updatehash## ##Addonetoin-degree## ##ofnewstate.## ######################## hash_current_state:=0; forsum_automatain[1..automata_length]do hash_current_state:=hash_current_state+ Automata[row_number][automata_length+sum_automata]* dihedral_group^automata_length-sum_automata; od; in_degree_hash[hash_current_state+1]:=in_degree_hash[hash_current_state+1]+1; od; 66 PAGE 71 ######################### ##Count## ##Countthenumberof## ##stateswithin-deg## ##zero.## ######################### Garden_Of_Eden:=0; foreden_statesin[1..dihedral_group^automata_length]do ifin_degree_hash[eden_states][1]=0then Garden_Of_Eden:=Garden_Of_Eden+1; fi; od; returnin_degree_hash; end; 67 PAGE 72 APPENDIXB Data ThefollowingisthedataobtainedfromtheprograminAppendixA. Table1. FractionofReachableStatesintheAutomatonDenedin Chapter5OvertheDihedralGroup. GroupOrder Length ReachableStates TotalStates ReachableStates TotalStates 2 2 1 4 1 4 2 3 4 8 1 2 2 4 4 16 1 4 2 5 16 32 1 2 2 6 16 64 1 4 2 7 64 128 1 2 2 8 64 256 1 4 2 9 256 512 1 2 68 PAGE 73 GroupOrder Length ReachableStates TotalStates ReachableStates TotalStates 4 2 1 16 1 16 4 3 16 64 1 4 4 4 16 256 1 16 4 5 256 1,024 1 4 4 6 256 4,096 1 16 4 7 4,096 16,384 1 4 4 8 4,096 65,536 1 16 4 9 65,536 262,144 1 4 GroupOrder Length ReachableStates TotalStates ReachableStates TotalStates 6 2 9 36 1 4 6 3 108 216 1 2 6 4 196 1,296 49 324 6 5 3,888 7,776 1 2 6 6 11,664 46,656 1 4 6 7 139,968 279,936 1 2 6 8 254,016 1,679,616 49 324 GroupOrder Length ReachableStates TotalStates ReachableStates TotalStates 8 2 4 64 1 16 8 3 128 512 1 4 8 4 196 4,096 49 1024 8 5 8,189 32,768 1 4 8 6 16,384 262,144 1 16 8 7 524,288 2,097,152 1 4 69 PAGE 74 GroupOrder Length ReachableStates TotalStates ReachableStates TotalStates 10 2 25 100 1 4 10 3 500 1,000 1 2 10 4 1,156 10,000 289 2500 10 5 50,000 100,000 1 2 10 6 250,000 1,000,000 1 4 GroupOrder Length ReachableStates TotalStates ReachableStates TotalStates 12 2 9 144 1 16 12 3 432 1,728 1 4 12 4 784 20,736 49 1296 12 5 62,204 248,832 1 4 12 6 186,624 2,985,984 1 16 GroupOrder Length ReachableStates TotalStates ReachableStates TotalStates 14 2 49 196 1 4 14 3 1,372 2,744 1 2 14 4 3,844 38,416 961 9604 14 5 268,912 537,824 1 2 GroupOrder Length ReachableStates TotalStates ReachableStates TotalStates 16 2 16 256 1 16 16 3 1,024 4,096 1 4 16 4 2,116 65,536 529 16384 16 5 262,144 1,048,576 1 4 70 PAGE 75 GroupOrder Length ReachableStates TotalStates ReachableStates TotalStates 18 2 81 324 1 4 18 3 2,916 5,832 1 2 18 4 9,604 104,976 2401 26244 18 5 944,784 1,889,568 1 2 71 PAGE 76 Bibliography [1]Rennard,J. Introduction to Cellular Automata.http://www.rennard.org/alife/english/acintrogb01.html. 2006. [2]Neumann,J.von. Re-evaluation of the problems of complicated automata: Problems of hierarchy and evolution.PapersofJohnvonNeumannonComputingandComputerTheory. W.AsprayandA.Burks,eds.,MITPress.1987. [3]Neumann,J.von. General and Logical Theory of Automata.CerebralMechanismsofBehavior. LloydA.Jeress,ed.NewYork:JohnWileyandSons,Inc.1951. [4]Zajicek,G. Health.what-is-cancer.com/papers/ca/ca28.htm.2009. [5] The PascGalois Project: Visualizing Abstract Mathematics.pascgalois.org.2008. [6]Flacche,M. Pascal's Triangle and Sierpinski's Triangle: An Incredible Link.TheAMATYC Review,Volume22,Number1.2000. [7]CrespoCrespo,C.,Ponteville,Ch.andSpinadel,V.W.de. Divisibility and Cellular Automata. Chaos,Solitons,andFractals,Volume6.1995. [8]Wolfram,S. Cellular Automata.LosAlamosScience,9.1983. [9]Kautz,S.M.,Lathrop,JamesI. Self-assembly of the Discrete Sierpinski Carpet and Related Fractals.arXiv:0901.3189v1.2009. [10]Callan,D. Sierpinski's triangle and the Prouhet-Thue-Morse word.arXiv:math/0610932v3. 2006. [11]Stephen,R. 100 Conjectures From the OEIS.arXiv:math/0409509v4. [12]Ferrand,E. Status Page for the Online Encyclopedia of Integer Sequences.http://www.ark.inberlin.de/conj.txt. [13]Evans,T. Discovering Binomial Identities with PascGaloisJE.Primus,Volume18,Issue4.2008. [14]Bardzell,M.andMiller,N. The Evolution Homomorphism and Permutation Actions on Group Generated Cellular Automata.ComplexSystems,Volume15,Issue2.2004. [15]Wolfram,S.,Martin,O.,andOdlyzko,A.M. Algebraic Properties of Cellular Automata.CommunicationsinMathematicalPhysics,93.1984. 72 PAGE 77 [16] GAP Groups, Algorithms, Programming a System for Computational Discrete Algebra. http://www.gap-system.org/.1995. 73 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||