ERROR LOADING HTML FROM SOURCE (http://ncf.sobek.ufl.edu//design/skins/UFDC/html/header_item.html)

One-Dimensional Cellular Automata

Permanent Link: http://ncf.sobek.ufl.edu/NCFE004066/00001

Material Information

Title: One-Dimensional Cellular Automata Pascal's Triangle and an Extension of Rule 90 for a Non-Abelian Group
Physical Description: Book
Language: English
Creator: Craig, Erin
Publisher: New College of Florida
Place of Publication: Sarasota, Fla.
Creation Date: 2009
Publication Date: 2009

Subjects

Subjects / Keywords: Cellular Automata
Dihedral Group
Pascal's Triangle
Genre: bibliography   ( marcgt )
theses   ( marcgt )
government publication (state, provincial, terriorial, dependent)   ( marcgt )
born-digital   ( sobekcm )
Electronic Thesis or Dissertation

Notes

Abstract: This thesis is a study of one-dimensional cellular automata. We begin by developing new properties of binomial coefficients that were discovered from patterns seen in Pascal's triangle modulo a prime. Then, motivated by Wolfram, Martin and Odlyzko's "Algebraic Properties of Cellular Automata", we study an extension of Rule 90 for multiplicative groups and develop the necessary and sufficient conditions for a state in this automaton to have a predecessor. We then apply this method to show the fraction of states reachable through evolution for this extension of Rule 90 over the dihedral group.
Statement of Responsibility: by Erin Craig
Thesis: Thesis (B.A.) -- New College of Florida, 2009
Electronic Access: RESTRICTED TO NCF STUDENTS, STAFF, FACULTY, AND ON-CAMPUS USE
Bibliography: Includes bibliographical references.
Source of Description: This bibliographic record is available under the Creative Commons CC0 public domain dedication. The New College of Florida, as creator of this bibliographic record, has waived all rights to it worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law.
Local: Faculty Sponsor: Poimenidou, Eirini

Record Information

Source Institution: New College of Florida
Holding Location: New College of Florida
Rights Management: Applicable rights reserved.
Classification: local - S.T. 2009 C8
System ID: NCFE004066:00001

Permanent Link: http://ncf.sobek.ufl.edu/NCFE004066/00001

Material Information

Title: One-Dimensional Cellular Automata Pascal's Triangle and an Extension of Rule 90 for a Non-Abelian Group
Physical Description: Book
Language: English
Creator: Craig, Erin
Publisher: New College of Florida
Place of Publication: Sarasota, Fla.
Creation Date: 2009
Publication Date: 2009

Subjects

Subjects / Keywords: Cellular Automata
Dihedral Group
Pascal's Triangle
Genre: bibliography   ( marcgt )
theses   ( marcgt )
government publication (state, provincial, terriorial, dependent)   ( marcgt )
born-digital   ( sobekcm )
Electronic Thesis or Dissertation

Notes

Abstract: This thesis is a study of one-dimensional cellular automata. We begin by developing new properties of binomial coefficients that were discovered from patterns seen in Pascal's triangle modulo a prime. Then, motivated by Wolfram, Martin and Odlyzko's "Algebraic Properties of Cellular Automata", we study an extension of Rule 90 for multiplicative groups and develop the necessary and sufficient conditions for a state in this automaton to have a predecessor. We then apply this method to show the fraction of states reachable through evolution for this extension of Rule 90 over the dihedral group.
Statement of Responsibility: by Erin Craig
Thesis: Thesis (B.A.) -- New College of Florida, 2009
Electronic Access: RESTRICTED TO NCF STUDENTS, STAFF, FACULTY, AND ON-CAMPUS USE
Bibliography: Includes bibliographical references.
Source of Description: This bibliographic record is available under the Creative Commons CC0 public domain dedication. The New College of Florida, as creator of this bibliographic record, has waived all rights to it worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law.
Local: Faculty Sponsor: Poimenidou, Eirini

Record Information

Source Institution: New College of Florida
Holding Location: New College of Florida
Rights Management: Applicable rights reserved.
Classification: local - S.T. 2009 C8
System ID: NCFE004066:00001


This item is only available as the following downloads:


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 = ,andlet S 0 = s;rs;r;r beastateintheautomatondenedsuchthat S 0 = s;rs;r;r r 2 s;r 2 s;s;rs = S: Then S 0 0 = s;r and S 0 = r 2 s;rs .Similarly, S 0 1 = rs;r and S 0 = r 2 s;s 1 Itisimportanttomentionthat S 0 0 evolvesto S 0 undertheupdaterulewhichmaps c 0 ;c 1 ;c 2 c 0 c 1 ;c 1 c 2 ;c 2 c 0 : Hence,thestudyofautomatawithevenlength,W,undertheoriginalupdaterulecorrespondsto studyofautomataoflength W 2 undertheupdaterulewrittenabove.Correspondingresultsare inherentwithinthepaper.Whilewenotethishere,wedonotdiscussitagainexplicitly. 31

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 = .BywritingsolutionsfortheequationsappearinginCorollaries 4.12,4.13and4.14withentriesfrom D 2 n ,wedescribethefractionofstatesthathave atleastonepredecessor. WenoteherethattheequationsfromCorollaries4.12and4.13havethesame structureandsowewillstudyallreducedstatesofoddlengthconcurrently.The equationforareducedstateofevenlengthseeninCorollary4.14willbetreated separately.However,tosimplifyalltheaforementionedequations,wewillusethe followingpropertyabouttheelementsof D 2 n Lemma 5.1 Let D 2 n begeneratedbyarotation, r ,andip, s ,suchthat r n =1= s 2 and srs = r )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 .Thenfor a 2 Z =n Z and b 2 Z = 2 Z s b r a = r a )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 ab mod n s b Proof. Either b =0or b =1.Supposerstthat b =0.Then r a = s 0 r a = r a )]TJ/F34 7.9701 Tf 6.586 0 Td [(2 a s 0 = r a .If b =1,then s 1 r a = r )]TJ/F37 7.9701 Tf 6.586 0 Td [(a mod n s 1 = r a )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 a mod n s 1 asexpected. WeproceednowtosimplifyEquations12and13.Itisimportantrsttodevelop notationthatwillbeusedthroughoutthepaper. Note 5.2 Throughoutthepaper,weusethefollowingtodene i 1 ;i 2 ;j 1 and j 2 Forareducedstateofoddwidth, W r i 1 s j 1 = 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 +4 k mod W 35

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 [( doesnotliein Proof. Let : D 2 n D 2 n = bethenaturalprojectionhomomorphismsothat r =0and s =1.Dene f a i g 2 k +1 i =1 suchthat a i 2 D 2 n )]TJ/F26 11.9552 Tf 12.62 0 Td [( forall i .Then 2 k +1 Y i =1 a i = a 1 + a 2 + + a 2 k +1 =1+1+ +1=1 : Itfollowsthat Q 2 k +1 i =1 a i liesin D 2 n )]TJ/F26 11.9552 Tf 12.62 0 Td [( Lemma 5.6 Let S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 beareducedstate.Then,usingthenotation fromNote5.2, j 1 = j 2 i S hasanevennumberoftermsthatliein D 2 n )]TJ/F26 11.9552 Tf 12.62 0 Td [( 38

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 ,andbyLemma5.5,theproductcanbewrittenonlyas productsofanevennumberoftermsin D 2 n )]TJ/F26 11.9552 Tf 13.75 0 Td [( .Hence, j 1 = j 2 S hasan evennumberoftermsin D 2 n )]TJ/F26 11.9552 Tf 12.619 0 Td [( Conversely,supposethat S hasanevennumberoftermsin D 2 n )]TJ/F26 11.9552 Tf 13.289 0 Td [( .Then anyproductofallofitselementsliesin ;specically,theproduct r i 1 s j 1 r i 2 s j 2 = r i 1 + i 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(2 i 2 j 1 mod n s j 1 + j 2 mod2 liesin .Fromthis,weseeclearlythat j 1 + j 2 0mod2andso j 1 j 2 mod2.Since j 1 and j 2 arein Z = 2 Z j 1 j 2 mod2 j 1 = j 2 Hence,if S hasanevennumberoftermsin D 2 n )]TJ/F26 11.9552 Tf 12.619 0 Td [( ,then j 1 = j 2 .Thiscompletes theproof. So,ifareducedstatedoesnothaveanevennumberoftermsfrom D 2 n )]TJ/F26 11.9552 Tf 12.851 0 Td [( thenitcannothaveacorrespondingpredecessorstate.Thelemmabelowcountsthe numberofstateswhichhaveanevennumberoftermsfrom D 2 n )]TJ/F26 11.9552 Tf 12.619 0 Td [( Lemma 5.7 For W 2 N ,thefractionofthe n W statesinthecellularautomaton denedinChapter5over D 2 n whichhaveanevennumberoftermsin D 2 n )]TJ/F26 11.9552 Tf 13.105 0 Td [( is 1 = 2 Proof. Let W 2 N ,andlet S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 denoteareducedstateinthe automatonwithanevennumberoftermsin D 2 n )]TJ/F26 11.9552 Tf 13.364 0 Td [( .Dene E W asthesetof allstatesoflength W withanevennumberoftermsin D 2 n )]TJ/F26 11.9552 Tf 12.824 0 Td [( and O W asthe setofallstatesoflength W withanoddnumberoftermsin D 2 n )]TJ/F26 11.9552 Tf 12.619 0 Td [( andlet : E W O W S = sd 0 ;d 1 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 : Itiseasytoseethat iswelldened.Weshowthat isabijection.Let 39

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 [( is1 = 2. Hence,exactly1 = 2ofstatesdonotsatisfy j 1 = j 2 ,andsoatleast1 = 2ofstates cannothavepredecessors.Itisimportantnowtoexaminethepreviousstatement inadierentlight.Wecanunderstandthisstatementbyrecallingthat D 2 n isthe semidirectproductof Z = 2 Z and Z =n Z ,andsowecangaininsightfromthestudy oftheautomataover Z = 2 Z .InAlgebraicPropertiesofCellularAutomata"[ 15 ], Wolfram,MartinandOdlyzkoprovethefollowinglemma: Lemma 5.8 [Lemma3.2,Lemma3.1in[ 15 ]]Congurationscontaininganodd numberofsiteswithvalue1canneverbegeneratedintheevolutionofthecellular automatondened[bytheupdaterulegiven],andcanoccuronlyasinitialstates. Tomaketheconnectionbetweentheautomatonover Z = 2 Z andtheautomaton over D 2 n ,wetakeareducedstate S over D 2 n andwriteeachentrymodulo toobtainanewstate, S Z = 2 Z ,whichliesintheautomataover Z = 2 Z .Hence,if S Z = 2 Z doesnothaveapredecessor,neitherdoes S .GivenLemma3.2,itfollowsthat S can onlyhaveapredecessorifithasanevennumberofsiteswithvalue1fromthe Z = 2 Z componentof D 2 n .Thiscorrelatestoastatehavinganevennumberofsiteswith valuefrom D 2 n )]TJ/F26 11.9552 Tf 12.619 0 Td [( .Hence,atmost,1 = 2ofstatesintheautomatondenedhave predecessors. Wenowaddresstheotherrequirementforareducedstate S tohaveapredecessor: thenecessityfortheexistenceofapair x 2 Z =n Z and y 2 Z = 2 Z tosatisfyEquation 18or19.Tosolvetheseequations,wewillcalluponaresultfromnumbertheory. 40

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 [( Example: Let S = s;r;rs;r 2 s;s beastateintheautomatondenedinChapter5over D 10 .Because S hasanevennumberoftermsin D 10 )]TJ/F26 11.9552 Tf 12.619 0 Td [( ,wecompute i 1 ;i 2 ;j 1 and j 2 byapplicationofCorollary4.12forautomataofoddlengthoveramultiplicativegroup G .Thiscorollarystatesthat S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 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 : Inthiscase, S hasapredecessorithereexists c 0 2 D 10 satisfying c 0 d 3 d 2 c 0 = d 1 d 0 d 4 ; thatis, c 0 r 2 s rs c 0 = r s s : Thissimpliesto c 0 rc 0 = r Hence, i 1 = i 2 =1and j 1 = j 2 =0.UsingTable1,weseethat S hasexactlyone predecessor.Thispredecessorisdeterminedby x 2 )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 i 2 )]TJ/F26 11.9552 Tf 12.446 0 Td [(i 1 mod n and y =0. 51

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 [( ,wecompute i 1 ;i 2 ;j 1 and j 2 byapplicationofCorollary4.13forautomataofevenlengthoveramultiplicativegroup G .Thiscorollarystatesthat S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 hasapredecessor S 0 = c 0 ; ;c W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 ithereexist c 0 ;c 1 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 c 1 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 1 = m +1 2 )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 Y k =0 d +4 k mod W Inthiscase, S hasapredecessorithereexists c 0 2 D 8 satisfying c 0 d 3 c 0 = d 1 d 5 ; thatis, c 0 rs c 0 = r s 53

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 [( ,wecompute i 1 ;i 2 ;j 1 and j 2 byapplicationofCorollary4.14forautomataofevenlengthover amultiplicativegroup G .Thiscorollarystatesthatfor W =2 m S = d 0 ; ;d W )]TJ/F34 7.9701 Tf 6.586 0 Td [(1 hasapredecessor S 0 = c 0 ; ;c W )]TJ/F34 7.9701 Tf 6.587 0 Td [(1 ithereexist c 0 ;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 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 and 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 55

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 and c 2 D 2 n )]TJ/F26 11.9552 Tf 12.619 0 Td [( .Dene 1 suchthat A 1 B i A = ; 1 ;r k B undercomponentwisemultiplicationand k 2 Z =n Z .Then 1 isanequivalencerelation. 60

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 [( and c 2 .Dene 2 suchthat A 2 B i A = r k ;r k ; 1 B bycomponentwisemultiplicationand k 2 Z =n Z .Then 2 isanequivalencerelation. Proof. SeetheproofforProposition6.1. Usingtheseequivalencerelations,wegivethefollowingconjecture. Conjecture 6.3 Let A;B 2 D 3 2 n bestatesintheautomatondenedinChapter 5over D 2 n suchthattheirrsttwoentriesarein andtheirlastentryis in D 2 n )]TJ/F26 11.9552 Tf 14.725 0 Td [( .Dene A N and B N tobe A and B atthe N thtimestepinthe evolutionoftheautomatonandlet 1 and 2 beasdenedinPropositions6.1and 6.2.If A 1 B ,then A N 2 B N forall N 2 N .Moreover,if A = ; 1 ;r k B ,then A N = r k ;r k ; 1 B N Conjecture6.3canbeusedtoshowthatif A 1 B for k 6 =0,then A and B evolve tocyclesthathavethesamelengthanddonotintersect.Thatis,ifweknowthe lengthofthecyclethat A evolvesto,thenweknowthelengthofaclassofcycles. Moreover,weknowthesizeoftheseclasses:inthestudyoftheautomatonof3cells over D 2 n ,if A isoftheformdescribedinProposition6.1,then A isequivalentto n cellsunder 1 Wenotethat 1 anditscorrespondingequivalencerelation, 2 ,referonlyto statesintheautomatonover D 2 n thatcorrespondto ; 0 ; 1and ; 1 ; 0over Z = 2 Z 61

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


ERROR LOADING HTML FROM SOURCE (http://ncf.sobek.ufl.edu//design/skins/UFDC/html/footer_item.html)