Surjunktiv grupp
är en surjunktiv grupp en grupp så att varje injektiv cellulär automat med gruppelementen som sina celler också är surjektiv . Surjunktiva grupper introducerades av Gottschalk (1973) . Det är okänt om varje grupp är surjunktiv.
Definition
En cellulär automat består av ett vanligt system av celler, som var och en innehåller en symbol från ett ändligt alfabet , tillsammans med en enhetlig regel som kallas en övergångsfunktion för uppdatering av alla celler samtidigt baserat på värdena för angränsande celler. Vanligtvis är cellerna arrangerade i form av en linje eller ett högredimensionellt heltalsrutnät , men andra arrangemang av celler är också möjliga. Det som krävs av cellerna är att de bildar en struktur där varje cell "ser likadan ut som" alla andra celler: det finns en symmetri av både arrangemanget av celler och regeluppsättningen som tar vilken cell som helst till vilken annan cell som helst. Matematiskt kan detta formaliseras genom begreppet en grupp , en uppsättning element tillsammans med en associativ och inverterbar binär operation. Elementen i gruppen kan användas som celler i en automat, med symmetrier som genereras av gruppoperationen. Till exempel kan en endimensionell linje av celler beskrivas på detta sätt som den additiva gruppen av heltal , och de högre dimensionella heltalsnäten kan beskrivas som de fria abelska grupperna .
Samlingen av alla möjliga tillstånd för en cellulär automat över en grupp kan beskrivas som de funktioner som mappar varje gruppelement till en av symbolerna i alfabetet. Som en finit uppsättning har alfabetet en diskret topologi , och samlingen av tillstånd kan ges produkttopologin ( kallas en prodiskret topologi eftersom den är produkten av diskreta topologier). För att vara övergångsfunktionen för en cellulär automat måste en funktion från tillstånd till tillstånd vara en kontinuerlig funktion för denna topologi, och måste också vara ekvivariant med gruppåtgärden, vilket innebär att skiftning av cellerna innan övergångsfunktionen tillämpas ger samma resultat som att tillämpa funktionen och sedan flytta cellerna. För sådana funktioner Curtis-Hedlund-Lyndon-satsen att värdet av övergångsfunktionen vid varje gruppelement beror på det tidigare tillståndet för endast en ändlig uppsättning av angränsande element.
En tillståndsövergångsfunktion är en surjektiv funktion när varje stat har en föregångare (det kan inte finnas någon Edens lustgård) . Det är en injektiv funktion när inga två tillstånd har samma efterföljare. En surjunktiv grupp är en grupp med egenskapen att, när dess element används som celler i cellulära automater, är varje injektiv övergångsfunktion hos en cellulär automat också surjektiv. Sammanfattningsvis, för att sammanfatta definitionerna ovan, är en grupp surjunktiv om, för varje finit uppsättning , varje kontinuerlig ekvivariant injektiv funktion är också surjektiv. Implikationen från injektivitet till surjektivitet är en form av Edens lustgårds sats , och de cellulära automaterna som definieras från injektiva och surjektiva övergångsfunktioner är reversibla .
Exempel
Exempel på surjunktiva grupper inkluderar alla lokalt resterande ändliga grupper , alla fria grupper , alla undergrupper av surjunktiva grupper, alla abelska grupper, alla sofiska grupper och varje lokalt surjunktiv grupp.
När han introducerade surjunktiva grupper 1973, observerade Gottschalk att det inte fanns några kända exempel på icke-surjunktiva grupper. Från och med 2014 är det fortfarande okänt om varje grupp är surjunktiv.
Se även
- Axe–Grothendiecks sats , ett analogt resultat för polynom
Anteckningar
- Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010), "Surjunctive groups", Cellular Automata and Groups , Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag , doi : 10.1007/978-3-642-14034-1_3 , ISBN 978-3- 642-14033-4 , MR 2683112 , Zbl 1218.37004
- Gottschalk, Walter (1973), "Some general dynamical notions", Recent Advances in Topological Dynamics (Proc. Conf. Topological Dynamics, Yale Univ., New Haven, Connecticut, 1972; in honor of Gustav Arnold Hedlund) , Lecture Notes in Math., vol. 318, Berlin, New York: Springer-Verlag , s. 120–125, doi : 10.1007/BFb0061728 , ISBN 978-3-540-06187-8 , MR 0407821 , Zbl 40255 .
- Šunić, Zoran (2014), "Cellulära automater och grupper, av Tullio Ceccherini-Silberstein och Michel Coornaert (bokrecension)", Bulletin of the American Mathematical Society , 51 ( 2): 361–366, doi : 10.1090/S0273-0979 -2013-01425-3 .