Abelisk sandhög modell

Identitetselementet för sandhöggruppen i ett rektangulärt rutnät. Gula pixlar motsvarar hörn som bär tre partiklar, lila till två partiklar, grön till en och svart till noll.

Den Abeliska sandstapelmodellen (ASM) är det mer populära namnet på den ursprungliga Bak–Tang–Wiesenfeld-modellen ( BTW). BTW-modellen var det första upptäckta exemplet på ett dynamiskt system som visade självorganiserad kritikalitet . Den introducerades av Per Bak , Chao Tang och Kurt Wiesenfeld i en tidning från 1987.

Tre år senare upptäckte Deepak Dhar att BTW-sandhögmodellen verkligen följer den abelska dynamiken och hänvisade därför till denna modell som den abeliska sandhögsmodellen.

Modellen är en cellulär automat . I sin ursprungliga formulering har varje plats på ett ändligt rutnät ett tillhörande värde som motsvarar högens lutning. Denna lutning byggs upp när "sandkorn" (eller "spån") placeras slumpmässigt på högen, tills lutningen överstiger ett specifikt tröskelvärde vid vilken tidpunkt den platsen kollapsar och överför sand till de intilliggande platserna, vilket ökar deras lutning. Bak, Tang och Wiesenfeld övervägde processen med successiv slumpmässig placering av sandkorn på nätet; varje sådan placering av sand på en viss plats kanske inte har någon effekt, eller så kan det orsaka en kaskadreaktion som kommer att påverka många platser.

Dhar har visat att den slutliga stabila sandhögskonfigurationen efter att lavinen har avslutats är oberoende av den exakta sekvensen av störtningar som följs under lavinen. Som en direkt konsekvens av detta faktum visas det att om två sandkorn läggs till den stabila konfigurationen i två olika ordningsföljder, t.ex. först på plats A och sedan på plats B, och först vid B och sedan vid A, slutligen stabil konfiguration av sandkorn visar sig vara exakt densamma. När ett sandkorn läggs till en stabil sandhögskonfiguration resulterar det i en lavin som slutligen slutar leda till en annan stabil konfiguration. Dhar föreslog att tillägget av ett sandkorn kan ses som en operatör, när det verkar på en stabil konfiguration, producerar det en annan stabil konfiguration. Dhar visade att alla sådana additionsoperatorer bildar en abelsk grupp, därav namnet Abelian sandpile-modell. Modellen har sedan dess studerats på det oändliga gittret, på andra (icke-kvadratiska) gitter och på godtyckliga grafer (inklusive riktade multigrafer ). Det är nära besläktat med dollarspelet , en variant av chip-firing-spelet som introducerades av Biggs.

Definition (rektangulära rutnät)

Sandhögmodellen är en cellulär automat som ursprungligen definierades på ett rektangulärt rutnät ( schackbräde ) av standard kvadratiskt gitter . Till varje vertex ( sida , fält ) i rutnätet associerar vi ett värde ( sandkorn , lutning , partiklar ) , med kallas den (initiala) konfigurationen av sandhögen.

Automatens dynamik vid iteration definieras sedan enligt följande:

  1. Välj en slumpmässig vertex enligt någon sannolikhetsfördelning (vanligtvis enhetlig).


  2. Lägg till ett sandkorn till denna vertex samtidigt som korntalen för alla andra hörn är oförändrade, dvs sätt och för alla .
  3. Om alla hörn är stabila , dvs för alla , även konfigurationen sägs vara stabil. Fortsätt i så fall med nästa iteration.



  4. Om minst en vertex är instabil , dvs för vissa , hela konfigurationen sägs vara instabil. I det här fallet, välj valfritt instabilt hörn slumpmässigt. Vänd denna vertex genom att minska dess korntal med fyra och genom att öka korntalet för var och en av dess (högst fyra) direkta grannar med en, dvs. sätt och if . Om en vertex vid gränsen av domänen välter, resulterar detta i en nettoförlust av korn (två korn i hörnet av rutnätet, ett korn annars).
  5. På grund av omfördelningen av korn kan störtningen av en vertex göra andra hörn instabila. Upprepa sålunda tippningsproceduren tills alla hörn av så småningom blir stabila och fortsätt med nästa iteration.

Ställningen av flera hörn under en iteration kallas en lavin . Varje lavin kommer garanterat att sluta sluta, dvs efter ett ändligt antal störtningar nås en stabil konfiguration så att automaten är väldefinierad. Dessutom, även om det ofta kommer att finnas många möjliga val för den ordning i vilken hörn ska störtas, beror den slutliga stabila konfigurationen inte på den valda ordningen; detta är en mening där sandhögen är abelisk . På liknande sätt är antalet gånger varje vertex välter under varje iteration också oberoende av valet av vältningsordning.

Definition (oriktade finita multigrafer)

För att generalisera sandhögsmodellen från det rektangulära rutnätet av standardkvadratgittret till en godtycklig oriktad finit multigraf en speciell vertex kallas diskbänken anges som inte får välta. En konfiguration (tillstånd) av modellen är då en funktion räknar icke- negativt antal korn på varje icke-sjunkande vertex. En icke-sjunkande vertex med

är instabil; den kan vältas, vilket skickar ett av sina korn till var och en av sina (icke-sänka) grannar:

för alla , .

Den cellulära automaten fortskrider sedan som tidigare, dvs genom att lägga till, i varje iteration, en partikel till en slumpmässigt vald icke-sjunkande vertex och välta tills alla hörn är stabila.

Definitionen av sandhögsmodellen som ges ovan för ändliga rektangulära rutnät av standardkvadratgittret kan då ses som ett specialfall av denna definition: betrakta grafen som erhålls från genom att lägga till en ytterligare vertex, sänkan, och genom att rita ytterligare kanter från sänkan till varje gränspunkt för så att graden av varje icke-sjunkande vertex av är fyra. På detta sätt kan även sandhögsmodeller på icke-rektangulära rutnät av standardkvadratgittret (eller något annat gitter) definieras: Skär någon avgränsad delmängd av med . Dra ihop varje kant av vars två ändpunkter inte är i . Den enda återstående vertexen utanför utgör sedan sänkan för den resulterande sandhögsgrafen.

Övergående och återkommande konfigurationer

I dynamiken för sandstapelautomaten definierad ovan, vissa stabila konfigurationer ( för alla ) dyker upp oändligt ofta, medan andra bara kan dyka upp ett ändligt antal gånger (om alls). De förra kallas för återkommande konfigurationer , medan de senare kallas transienta konfigurationer . De återkommande konfigurationerna består därigenom av alla stabila icke-negativa konfigurationer som kan nås från vilken annan stabil konfiguration som helst genom att upprepade gånger lägga till sandkorn till hörn och välta. Det är lätt att se att den minimalt stabila konfigurationen , där varje vertex bär sandkorn, kan nås från vilken annan stabil konfiguration som helst (lägg till korn till varje vertex). Följaktligen är de återkommande konfigurationerna exakt de konfigurationer som kan nås från den minimalt stabila konfigurationen genom att endast lägga till sandkorn och stabilisera.

Inte alla icke-negativa stabila konfigurationer är återkommande. Till exempel, i varje sandhögsmodell på en graf som består av minst två sammankopplade hörn utan sjunker, är varje stabil konfiguration där båda hörnen bär noll korn av sand återkommande. För att bevisa detta, observera först att tillsatsen av sandkorn bara kan öka det totala antalet korn som bärs av de två hörnen tillsammans. För att nå en konfiguration där båda hörnen bär noll partiklar från en konfiguration där detta inte är fallet innebär det alltså nödvändigtvis steg där åtminstone en av de två hörnen välter. Överväg det sista av dessa steg. I detta steg måste en av de två hörnen falla sist. Eftersom vältning överför ett sandkorn till varje närliggande vertex, innebär detta att det totala antalet korn som bärs av båda hörnen tillsammans inte kan vara lägre än ett, vilket avslutar beviset.

Sandstapel grupp

Givet en konfiguration , för alla , omkullkastning av instabila icke-sänkande hörn på en ändlig ansluten graf tills ingen instabil icke-sänkande vertex återstår leder till en unik stabil konfiguration , vilket är kallas stabiliseringen av . Givet två stabila konfigurationer och , kan vi definiera operationen , motsvarande vertexvis tillsats av korn följt av stabiliseringen av den resulterande sandhögen.

Givet en godtycklig men fast ordning av de icke-sänkande hörnen, kan multipla vältningsoperationer, som t.ex. kan inträffa under stabiliseringen av en instabil konfiguration, kodas effektivt genom att använda grafen Laplacian , där är gradmatrisen och är grafens närliggande matris . Att ta bort raden och kolumnen för som motsvarar sänkan ger den reducerade grafen Laplacian . Sedan, när man börjar med en konfiguration och fäller varje vertex totalt gånger ger konfigurationen , där är sammandragningsprodukten. Dessutom, om motsvarar antalet gånger varje vertex fälls under stabiliseringen av en given konfiguration , då

I det här fallet hänvisas till tippnings- eller vägmätarfunktionen (av stabiliseringen av ).

Under operationen bildar uppsättningen av återkommande konfigurationer en abelsk grupp som är isomorf till cokärnan i den reducerade grafen Laplacian , dvs till n anger antalet hörn (inklusive sänkan). Mer generellt bildar uppsättningen av stabila konfigurationer (övergående och återkommande) en kommutativ monoid under operationen . Det minimala idealet för denna monoid är då isomorft för gruppen av återkommande konfigurationer.

Gruppen som bildas av de återkommande konfigurationerna, såväl som gruppen till vilken den förra är isomorf, hänvisas oftast till som sandhöggruppen . Andra vanliga namn för samma grupp är kritisk grupp , Jacobian-grupp eller (mindre ofta) Picard-grupp . Observera dock att vissa författare endast betecknar gruppen som bildas av de återkommande konfigurationerna som sandhöggruppen, samtidigt som namnet Jacobian grupp eller kritisk grupp reserveras för den (isomorfa) gruppen som definieras av eller för relaterade isomorfa definitioner). Slutligen använder vissa författare namnet Picard-gruppen för att hänvisa till den direkta produkten av sandstapelgruppen och som naturligt förekommer i en cellulär automat som är nära besläktad med sandstapelmodellen, kallad chipet eldning eller dollarspel.

Med tanke på de isomorfismer som anges ovan är ordningen på sandhöggruppen determinanten för som enligt matristrädets sats är antalet spännande träd i grafen.

Självorganiserad kritik

Det ursprungliga intresset bakom modellen härrörde från det faktum att den i simuleringar på gitter attraheras till dess kritiska tillstånd , vid vilken tidpunkt systemets korrelationslängd och systemets korrelationstid går till oändlighet, utan någon finjustering av en systemparameter. Detta står i kontrast till tidigare exempel på kritiska fenomen, såsom fasövergångarna mellan fast och vätska, eller vätska och gas, där den kritiska punkten endast kan nås genom exakt inställning (t.ex. temperatur). Därför kan vi i sandhögsmodellen säga att kritikaliteten är självorganiserad .

När sandhögsmodellen väl når sitt kritiska tillstånd finns det ingen korrelation mellan systemets svar på en störning och detaljerna i en störning. Generellt betyder detta att om du tappar ytterligare ett sandkorn på högen kan det inte hända något, eller så kan det få hela högen att kollapsa i en massiv ras. Modellen visar också 1/ ƒ brus , en egenskap som är gemensam för många komplexa system i naturen.

Denna modell visar bara kritiskt beteende i två eller flera dimensioner. Sandhögsmodellen kan uttryckas i 1D; men istället för att utvecklas till sitt kritiska tillstånd, når 1D-sandhögsmodellen istället ett minimalt stabilt tillstånd där varje gitterplats går mot den kritiska lutningen.

För två dimensioner har det antagits att den associerade konforma fältteorin består av symplektiska fermioner med en central laddning c = −2.

Egenskaper

Minst handlingsprincip

Stabiliseringen av chipkonfigurationer följer en form av minsta verkansprincip : varje vertex faller inte mer än nödvändigt under stabiliseringens gång. Detta kan formaliseras enligt följande. Kalla en sekvens av störtningar legal om den bara störtar instabila hörn, och stabilisering om det resulterar i en stabil konfiguration. Standardsättet för att stabilisera sandhögen är att hitta en maximal laglig sekvens; dvs genom att välta så länge det är möjligt. En sådan sekvens är uppenbarligen stabiliserande, och sandhögens Abeliska egenskap är att alla sådana sekvenser är likvärdiga upp till permutation av störtningsordningen; det vill säga för varje vertex antalet gånger välter detsamma i alla legala stabiliserande sekvenser. Enligt minsta åtgärdsprincipen är en minimal stabiliserande sekvens också likvärdig upp till permutation av störtningsordern till en laglig (och fortfarande stabiliserande) sekvens. Speciellt är den konfiguration som resulterar från en minimal stabiliserande sekvens densamma som resultatet av en maximal laglig sekvens.

Mer formellt, om är en vektor så att är antalet gånger som vertex välter under stabiliseringen (via omkullkastning av instabila hörn) av en chipkonfiguration , och är en integralvektor (inte nödvändigtvis icke-negativ) så att är stabil, då är för alla hörn .

Skalningsgränser

Animation av sandhögens identitet på kvadratiska rutnät av ökande storlek. Svart färg betecknar hörn med 0 korn, grönt är för 1, lila är för 2 och guld är för 3.

Animationen visar den återkommande konfigurationen som motsvarar identiteten för sandhöggruppen på olika kvadratiska rutnät med ökande storlekar , varvid konfigurationerna skalas om till alltid ha samma fysiska dimension. Visuellt tycks identiteterna på större rutnät bli mer och mer detaljerade och "konvergera till en kontinuerlig bild". Matematiskt antyder detta existensen av skalningsgränser för sandhögsidentiteten på kvadratiska rutnät baserat på begreppet svag-* konvergens (eller någon annan, generaliserad föreställning om konvergens). Faktum är att förekomsten av skalningsgränser för återkommande sandhögskonfigurationer har bevisats av Wesley Pegden och Charles Smart. I ytterligare samarbete med Lionel Levine använder de skalningsgränsen för att förklara den fraktala strukturen av sandhögen på kvadratiska rutnät.

Generaliseringar och relaterade modeller

Sandstapelmodeller på oändliga rutnät

30 miljoner korn föll till en plats för det oändliga kvadratiska rutnätet och störtades sedan enligt reglerna för sandhögsmodellen. Vit färg anger platser med 0 korn, grönt är för 1, lila är för 2, guld är för 3. Begränsningsrutan är 3967×3967.

Det finns flera generaliseringar av sandhögsmodellen till oändliga rutnät. En utmaning i sådana generaliseringar är att det i allmänhet inte längre är garanterat att varje lavin så småningom kommer att sluta. Flera av generaliseringarna tar alltså endast hänsyn till stabiliseringen av konfigurationer för vilka detta kan garanteras.

En ganska populär modell på det (oändliga) kvadratiska gittret med platser definieras enligt följande:

Börja med någon icke-negativ konfiguration av värdena som är finit, vilket betyder

Vilken webbplats som helst med

är instabil och kan välta (eller skjuta ), skicka en av sina marker till var och en av sina fyra grannar:

Eftersom den initiala konfigurationen är ändlig kommer processen garanterat att avslutas, med kornen som sprids utåt.

Ett populärt specialfall av denna modell ges när den initiala konfigurationen är noll för alla hörn utom origo. Om ursprunget bär ett stort antal sandkorn, bildar konfigurationen efter avkoppling fraktala mönster (se figur). När man lät det initiala antalet korn vid ursprunget gå till oändlighet, visades de omskalade stabiliserade konfigurationerna konvergera till en unik gräns.

Sandstapelmodeller på riktade grafer

Sandhögsmodellen kan generaliseras till godtyckligt riktade multigrafer. Reglerna är att alla vertex med

är instabil; vältning igen skickar marker till var och en av sina grannar, en längs varje utgående kant:

och för varje :

där är antalet kanter från till .

I detta fall är den Laplacian matrisen inte symmetrisk. Om vi ​​specificerar en sänka så att det finns en väg från varannan vertex till , då är stabiliseringsoperationen på finita grafer väldefinierad och sandstapelgruppen kan skrivas

som förut.

Ordningen på sandhöggruppen är återigen determinanten för , som enligt den allmänna versionen av matristrädssatsen är antalet orienterade spännträd som är rotade vid sänkan.

Den utökade sandhögmodellen

Sandstapeldynamik inducerad av den harmoniska funktionen H=x*y på ett 255x255 kvadratiskt rutnät.

För att bättre förstå strukturen av sandhöggruppen för olika ändliga konvexa rutnät av standardkvadratgittret , Lang och Shkolnikov introducerade den utökade sandhögsmodellen 2019. Den utökade sandhögsmodellen definieras nästan exakt på samma sätt som den vanliga sandhögmodellen (dvs. den ursprungliga Bak–Tang–Wiesenfeld-modellen ), förutom att hörnpunkter vid gränsen av rutnätet tillåts nu bära ett icke-negativt reellt antal korn. Däremot är hörn i det inre av rutnätet fortfarande bara tillåtna att bära heltal av korn. Ställningsreglerna förblir oförändrade, dvs både inre och gränsspetsar antas bli instabila och falla om korntalet når eller överstiger fyra.

Också de återkommande konfigurationerna av den utökade sandhögsmodellen bildar en abelisk grupp, kallad den utökade sandhögsgruppen , av vilken den vanliga sandhögsgruppen är en diskret undergrupp . Till skillnad från den vanliga sandhöggruppen är dock den utökade sandhöggruppen en kontinuerlig Lie-grupp . Eftersom den genereras genom att endast lägga till sandkorn till gränsen av rutnätet, har den utökade sandhöggruppen dessutom topologin av en torus av dimension och en volym som ges av ordningen för den vanliga sandhöggruppen.

Av specifikt intresse är frågan hur de återkommande konfigurationerna dynamiskt förändras längs den kontinuerliga geodetiken hos denna torus som passerar genom identiteten. Denna fråga leder till definitionen av sandhögdynamiken

förlängd sandhögmodell)

respektive

(vanlig sandhögmodell)

inducerad av den heltalsvärde övertonsfunktionen vid tiden med identiteten av sandhöggruppen och golvfunktionen. För polynomiska harmoniska funktioner av låg ordning kännetecknas sandhögdynamiken av den mjuka transformationen och uppenbara bevarandet av de fläckar som utgör sandhögens identitet. Till exempel liknar den harmoniska dynamiken som induceras av den "släta sträckningen" av identiteten längs huvuddiagonalerna som visualiseras i animationen. Konfigurationerna som uppträder i dynamiken inducerad av samma övertonsfunktion på kvadratiska rutnät av olika storlekar antogs vidare vara svag-* konvergera, vilket betyder att det antas existera skalningsgränser för dem. Detta föreslår en naturlig renormalisering för de utökade och vanliga sandhöggrupperna, vilket innebär en kartläggning av återkommande konfigurationer på ett givet rutnät till återkommande konfigurationer på ett undernät. Informellt mappar denna renormalisering helt enkelt konfigurationer som förekommer vid en given tidpunkt i sandhögdynamiken inducerad av någon harmonisk funktion på det större rutnätet till motsvarande konfigurationer som visas samtidigt i sandhögen dynamik inducerad av begränsningen av till respektive underrutnät.

Den delbara sandhögen

En starkt besläktad modell är den så kallade delbara sandhögsmodellen , introducerad av Levine och Peres 2008, där det, istället för ett diskret antal partiklar på varje plats , finns ett reellt tal representerar mängden massa på webbplatsen. Om en sådan massa är negativ kan man förstå den som ett hål. Omkullkastningen inträffar närhelst en plats har en massa större än 1; den välter överskottet jämnt mellan sina grannar vilket resulterar i situationen att om en webbplats är full vid tidpunkten kommer den att vara full för alla senare tider.

Kulturella referenser

Sandhögen Bak–Tang–Wiesenfeld nämndes i Numb3rs- avsnittet "Rampage", när matematikern Charlie Eppes förklarar för sina kollegor en lösning på en brottsutredning.

Datorspelet Hexplode är baserat kring den abelianska sandhögsmodellen på ett ändligt hexagonalt rutnät där korn placeras av spelare istället för slumpmässig kornplacering .

Vidare läsning

externa länkar