On the sandpile group of regular trees

OnthesandpilegroupofregulartreesEvelinToumpakari∗March12,2004AbstractThesandpilegroupofaconnectedgraphisthegroupofrecurrentconfigurationsintheabeliansandpilemodelonthisgraph.Westudythestructureofthisgroupforthecaseofregulartrees.Adescriptionofthisgroupisthefollowing:LetT(d,h)bethed-regulartreeofdepthhandletVbethesetofitsvertices.DenotetheadjacencymatrixofT(d,h)byAandconsiderthemodifiedLaplacianmatrixΔ:=dI−A.LettherowsofΔspanthelatticeΛinZV.ThesandpilegroupofT(d,h)isZV/Λ.Wecomputetherank,theexponentandtheorderofthisabeliangroupandfindacyclicHall-subgroupoforder(d−1)h.Wefindthatthebase(d−1)-logarithmoftheexponentandoftheorderareasymptotically3h2/π2andcd(d−1)h,respectively.WeconjectureanexplicitformulafortheranksofallSylowsubgroups.1IntroductionMotivatedbytheconceptof“self-organizedcriticality”instatisticalmechanics[1](cf.[10]),theAbelianSandpileModel(ASM)isagameonaconnectedgraphwithaspecialvertexcalledthe“sink.”Werefertothisgraphasthe“augmentedgraph”andtheterm“thegraph”willbereservedtotheaugmentedgraphwiththesinkdeleted.Verticesotherthanthesinkwillbecalled“ordinary.”Acon-figurationofthegameisanassignmentofanon-negativeintegerwitoeachvertexioftheaugmentedgraph.Theseintegersmaybethoughtofasthenum-bersofsandgrainsatthe“sites.”Aconfigurationisstableifforallordinaryverticesi,0≤wideg(i),wheredeg(i)isthedegreeofiintheaugmentedgraph.Whentheheightatanordinaryvertexireachesdeg(i),a“toppling”oc-curs,i.e.,thisvertexlosesdeg(i)grains,onetoeachofitsneighbors(includingthesink).Startingwithanyunstableconfigurationandtopplingunstableordi-naryverticesrepeatedly,wefinallyarriveatastableconfiguration.Theorderinwhichthetopplingsoccurdoesnotmatter[4],thereforethemodeliscalledabelian.Moreover,theconnectednessoftheaugmentedgraphensuresthata∗DepartmentofMathematics,UniversityofChicago,5734S.Universityave,Chicago,IL60637,Email:[e-mail]1stableconfigurationwillbereachedinafinitenumberofsteps:thesink“col-lects”thegrains“fallingoff”theordinaryvertices.Foreveryordinaryvertexi,wedefineanoperatorαionthespaceofstableconfigurations.Forastableconfigurationw,αi(w)isthestableconfigurationweobtainafteraddingonegrainatvertexiandtopplingifnecessary.Aconfigurationwisrecurrentifforeveryoperatorαithereisapositiveintegerrisuchthatαrii(w)=w(Dhar[7]).Theαirestrictedtothesetofrecurrentconfigurationsformanabeliangroupoforderequaltothenumberofspanningtreesofthegraph[7].Theoperatorsαionthesetofrecurrentconfigurationssatisfytherelationsαdeg(i)i=Qαj,wheretheproductextendsoverallordinaryneighborsjofi[7].Itturnsoutthattheserelationsdefinethegroup.Creutz[6]provedthattherecurrentconfigurationsundertheoperationofpointwiseadditionandtopplinggenerateanabeliangroupisomorphictothegroupgeneratedbytheoperatorsαi.Thisgroupiscalledin[5]thesandpilegroupoftheaugmentedgraph.Ofspecialinterestaresequencesofsandpilegroupsderivedfrominfinited-regulargraphsinthefollowingway:LetT=(V(T),E(T))beaninfinited-regulargraph.WitheveryfinitesubsetP⊂V(T)weassociateagraphˆPasfollows:WeconsiderthesubgraphPinducedonP,adjoinasinktoP=V(P)andjoineachvertexi∈Pbyd−degP(i)edgestothesink.ThiswayallverticesinPhavedegreedinˆP.Nowtakea“well-behaved”sequence{Pn}ofsubsetsofV(T)andconsiderthesandpilegroupsGnassociatedwithˆPn.Aninstanceofthisprocedureisthesequenceoffinitesquarelatticesstudiedin[9].Withsomeabuseofterminology,weshallrefertoGasthesandpilegroupofthegraphPratherthanthesandpilegroupoftheaugmentedgraphˆP.InthispaperwechooseTtobetheinfiniteregulartreeofdegreedandPhtobetheballofradiushaboutavertexdesignatedastheroot.WestudytheassociatedsandpilegroupG(d,h),whichwecallthesandpilegroupofthed-valenttreeofdepthh.Wefindtherank,theexponentandtheorderofG(d,h)andweshowthatG(d,h)hasacyclicHall-subgroupoforder(d−1)h.AslightvariationoftheASMisstudiedin[2]and[3].ProbabilisticaspectsoftheASMonˆT(d,h)andoninfiniteregulartreesarestudiedin[8]and[11]respectively.AcomprehensiveintroductiontotheASMandtosimilarmodelscanbefoundin[10].Acknowledgments:IwouldliketothankmyadvisorStevenLalleyforintro-ducingmetothistopicandforhisconstantencouragement.IwouldliketoexpressmygratitudetoL´aszl´oBabaiformanyhelpfuldiscussionsandforhissupport.2MainresultsInthissectionwestatethemainresultsofthispaper.TheresultsconcernG(d,h),thesandpilegroupofthed-valenttreeofdepthh.Throughoutthis2paperweassumed≥3,h≥1.Theorem2.1TherankofG(d,h)is(d−1)h.Definition2.2LetGbeafinitegroup.TheexponentofGistheleastcommonmultipleoftheordersoftheelementsofG.IfGisabelianthentheexponentisalsothelargestorderofanelement.Notation:(i)WedenotetheexponentofG(d,h)byexp(d,h).(ii)Wedefinethenumbersθ(d,n)asθ(d,n):=[(d−1)n−1]/(d−2).Theorem2.3Theexponentexp(d,h)ofthegroupG(d,h)isequalto(d−1)hlcm{dθ(d,h+1),θ(d,h),θ(d,h−1),...,θ(d,2)}.(1)Thisseemstobethefirsttimeintheliteraturethatsubstantialinformationabouttheexponentofanontrivialclassofsandpilegroupsisfound.Corollary2.4Foreveryfixedd≥3,thefollowingasymptoticequalityholdsash→∞:logd−1exp(d,h)∼3h2π2.Notation:WedenotetheorderofG(d,h)byg(d,h).Theorem2.5Theorderg(d,h)ofthegroupG(d,h)isequaltod(d−1)h[θ(d,h+1)]d−1h−1Yn=1[θ(d,h+1−n)](d−2)d(d−1)n−1.(2)