Grigorchuk grupp

Inom det matematiska området av gruppteorin är Grigorchuk -gruppen eller den första Grigorchuk-gruppen en ändligt genererad grupp konstruerad av Rostislav Grigorchuk som gav det första exemplet på en ändligt genererad grupp av intermediär (det vill säga snabbare än polynom men långsammare än exponentiell) tillväxt . Gruppen konstruerades ursprungligen av Grigorchuk i en tidning från 1980 och han bevisade sedan i en tidning från 1984 att denna grupp har en medeltillväxt, vilket ger ett svar på ett viktigt öppet problem som ställdes av John Milnor 1968. Grigorchuk-gruppen förblir ett nyckelobjekt för studie i geometrisk gruppteori , särskilt i studiet av de så kallade grengrupperna och automatgrupperna, och det har viktiga samband med teorin om itererade monodromigrupper .

Historia och betydelse

Tillväxten av en ändligt genererad grupp mäter asymptotiken, eftersom $n\to \infty$ av storleken på en n -kula i gruppens Cayley-graf ( det vill säga antalet element i G som kan uttryckas som ord med längd som högst n i genereringsmängden G ). Studiet av tillväxthastigheter för ändligt genererade grupper går tillbaka till 1950-talet och motiveras delvis av föreställningen om volymentropi (det vill säga tillväxthastigheten för volymen av bollar) i det universella täckningsutrymmet för ett kompakt Riemann-grenrör i differential geometri . Det är uppenbart att tillväxthastigheten för en ändligt genererad grupp som mest är exponentiell och man förstod också tidigt att ändligt genererade nilpotenta grupper har polynomtillväxt. År 1968 John Milnor en fråga om förekomsten av en ändligt genererad grupp av intermediär tillväxt , det vill säga snabbare än någon polynomfunktion och långsammare än någon exponentiell funktion. Ett viktigt resultat i ämnet är Gromovs teorem om grupper av polynomtillväxt, erhållen av Gromov 1981, som visar att en ändligt genererad grupp har polynomtillväxt om och endast om denna grupp har en nilpotent undergrupp av ändligt index . Före Grigorchuks arbete fanns det många resultat som etablerade tillväxtdikotomi (det vill säga att tillväxten alltid är antingen polynom eller exponentiell) för olika klasser av ändligt genererade grupper, såsom linjära grupper, lösbara grupper , etc.

Grigorchuks grupp G konstruerades i en tidning från 1980 av Rostislav Grigorchuk , där han bevisade att denna grupp är oändlig, periodisk och resterande ändlig . I en efterföljande tidning 1984 bevisade Grigorchuk att denna grupp har medeltillväxt (detta resultat tillkännagavs av Grigorchuk 1983). Mer exakt bevisade han att G har tillväxt b ( n ) som är snabbare än $\exp({\sqrt {n}})$ men långsammare än $\ exp(n^{s})$ där $s=\log _{32}31\approx 0,991$ . Den övre gränsen förbättrades senare av Laurent Bartholdi till

$s={\frac {\log 2}{\log 2-\log \eta }}\ ungefär 0,7675,\qquad \eta ^{3}+\eta ^{2}+\eta =2.$

En nedre gräns för $\exp(n^{0,504})$ bevisades av Yurii Leonov. Den exakta asymptotiken för tillväxten av G är fortfarande okänd. Det förmodas att gränsen

$\lim _{n\to \infty }\log _{n}\log b(n),$

existerar men även detta förblev ett stort öppet problem. Detta problem löstes 2020 av Erschler och Zheng. De visar att gränsen är lika med $s$ .

Grigorchuks grupp var också det första exemplet på en grupp som är mottaglig men inte elementärt mottaglig , och svarade därmed på ett problem som ställdes av Mahlon Marsh Day 1957.

Ursprungligen konstruerades Grigorchuks grupp G som en grupp av Lebesgue-mätbevarande transformationer på enhetsintervallet, men därefter hittades enklare beskrivningar av G och den presenteras nu vanligtvis som en grupp automorfismer av det oändliga regelbundna binära rotade trädet . Studiet av Grigorchuks grupp informerade till stor del om utvecklingen av teorin om grengrupper, automatgrupper och självliknande grupper under 1990-2000-talen och Grigorchuks grupp förblir ett centralt objekt i denna teori. Nyligen har viktiga samband mellan denna teori och komplex dynamik, särskilt föreställningen om itererade monodromigrupper , upptäckts i Volodymyr Nekrashevychs arbete. och andra.

Efter Grigorchuks artikel från 1984 fanns det många efterföljande förlängningar och generaliseringar.

Definition

Det oändliga binära trädet T ₂ . Dess noder är märkta med strängar med 0:or och 1:or.

Även om Grigorchuk-gruppen initialt definierades som en grupp av Lebesgue-måttbevarande transformationer av enhetsintervallet, ges denna grupp för närvarande vanligtvis genom dess förverkligande som en grupp av automorfismer av det oändliga regelbundna binära rotade trädet T ₂ . Trädet T ₂ realiseras som mängden $\Sigma ^{*}$ av alla finita strängar i alfabetet $\Sigma =\{0,1\}$ plus tom sträng $\varnothing$ som är rotpunkten till T ₂ . För en vertex x av T ₂ är strängen x 0 det vänstra barnet till x och strängen x 1 är det högra barnet till x i T ₂ . Gruppen av alla automorfismer Aut( T ₂ ) kan alltså ses som gruppen av alla längdbevarande permutationer σ av $\Sigma ^{*}$ som också respekterar den initiala segmentrelationen, dvs. närhelst en sträng x är ett initialt segment av en sträng y så är σ ( x ) ett initialt segment av σ ( y ).

Grigorchuk -gruppen G definieras sedan som undergruppen av Aut( T ₂ ) genererad av fyra specifika element av Aut( T ₂ ):

$G=\langle a,b,c,d\rangle \leqslant {\text{Aut}}(T_{2}),$

där automorfismerna a , b , c , d definieras enligt följande (observera att $\varnothing$ är fixerad av alla automorfismer i trädet):

${\begin{aligned}a(0)=1,\qquad a(1)=0, \qquad \forall x\in \Sigma ^{*}\quad &{\begin{cases}a(0x)=1x\\a(1x)=0x\end{cases}}\\[6pt]{\begin {aligned}&b(0)=c(0)=d(0)=0\\&b(1)=c(1)=d(1)=1\end{aligned}}\qquad \forall x\in \Sigma ^{*}\quad &{\begin{aligned}&{\begin{cases}b(0x)=0a(x)\\b(1x)=1c(x)\end{cases}}\\ &{\begin{cases}c(0x)=0a(x)\\c(1x)=1d(x)\end{cases}}\\&{\begin{cases}d(0x)=0x\\ d(1x)=1b(x)\end{cases}}\end{aligned}}\end{aligned}}$

_Handlingen av standardgenereringsuppsättningen för Grigorchuk-gruppen på trädet T2 . Trianglarna betecknar de oändliga underträden som förblir oförändrade.

Vi ser att endast elementet a definieras explicit och elementen b , c , d definieras rekursivt. För att få en bättre bild av denna handling noterar vi att $T_{2}$ har en naturlig gradering till nivåer som ges av strängarnas längd:

${\begin{aligned}&\ell =0\qquad \varnothing \\&\ell =1\qquad 0,1\ \&\ell =2\qquad 00,01,10,11\\&\qquad \cdots \end{aligned}}$

Låt nu $T[n]$ beteckna föreningen av alla hörn med nivå $\leqslant n.$ Detta betyder:

${\begin{aligned}T[0 ]&=\{\varnothing \}\\T[1]&=\{\varnothing ,0,1\}\\T[2]&=\{\varnothing ,0,1,00,01,10, 11\}\\&\quad \cdots \end{aligned}}$

Eftersom automorfismer hos trädet är längdbevarande, fixeras $T[n]$ som en uppsättning av ${\text{Aut}}(T_{2})$ för alla $n\geqslant 0.$ Med detta i åtanke skriver vi:

$T_{2}=0\Sigma ^{*}\sqcup T[1]\sqcup 1\Sigma ^{*}.$

Vi kallar $0\Sigma ^{*}$ (resp. $1\Sigma ^{*}$ ) den vänstra (resp. högra) grenen och betecknar den med $T_{L}$ (resp. $T_{R}$ ). Med denna notation ser vi att:

$a(T_{L})\subseteq T_{R},\quad a(T_{R})\subseteq T_{L}.$

Nu kan vi också skriva verkan av elementen b , c och d i termer av den disjunkta föreningen enligt följande:

${\begin{aligned}b :=(a,c)\quad &\Longleftrightarrow \quad b(x)={\begin{cases}a(x)&x\in T_{L}\\c(x)&x\in T_{R}\ end{cases}}\\c:=(a,d)\quad &\Longleftrightarrow \quad c(x)={\begin{cases}a(x)&x\in T_{L}\\d(x) &x\in T_{R}\end{cases}}\\d:=({\text{id}},b)\quad &\Longleftrightarrow \quad d(x)={\begin{cases}x&x\in T_{L}\\b(x)&x\in T_{R}\end{cases}}\end{aligned}}$

På samma sätt har vi:

$aba=(c,a),\quad aca=(d,a),\quad ada=(b,{\text{id}}).$

Egenskaper

Följande är grundläggande algebraiska egenskaper för Grigorchuk-gruppen (se för bevis):

• Gruppen G är oändlig.
• Gruppen G är resterande ändlig . Låt $\rho _{n}:G\to {\text{Aut}}(T[n])$ vara restriktionshomomorfismen som skickar varje element i G till dess begränsning till det finita trädet T [ n ]. Grupperna Aut( T [ n ]) är ändliga och för varje icke-trivialt g i G finns det n så att $\rho _{n}(g)\neq 1.$
• Gruppen G genereras av a och två av de tre elementen b,c,d . Till exempel kan vi skriva $G=\langle a,b,c\rangle .$
• Elementen a , b , c , d är involutioner .
• Elementen b , c , d pendlar parvis och bc = cb = d , bd = db = c , dc = cd = b , så att $\langle b,c,d\ rangle \leqslant G$ är en abelsk grupp av ordning 4 som är isomorf till den direkta produkten av två cykliska grupper av ordning 2.
• Genom att kombinera de två föregående egenskaperna ser vi att varje element i G kan skrivas som ett (positivt) ord i a , b , c , d så att detta ord inte innehåller några underord av formen aa , bb , cc , dd , cd , dc , bc , cb , bd , db . Sådana ord kallas reducerade .
• Gruppen G är en 2-grupp , det vill säga varje element i G har en ändlig ordning som är en potens av 2.
• Grupp G har medeltillväxt.
• Gruppen G är mottaglig men inte elementär mottaglig .
• Gruppen G är bara oändlig , det vill säga G är oändlig men varje riktig kvotgrupp av G är ändlig.
• Gruppen G har undergruppsegenskapen kongruens : en undergrupp H har ändligt index i G om och endast om det finns ett positivt heltal n så att $\ker(\rho _{n})\leqslant H.$
• Gruppen G har ett lösbart undergruppsmedlemskapsproblem, det vill säga det finns en algoritm som, givet godtyckliga ord w , u ₁ , ..., u _n avgör huruvida w representerar ett element i undergruppen som genereras av u ₁ , .. ., u _n .
• Gruppen G är undergrupp separerbar , det vill säga varje ändligt genererad undergrupp är stängd i den profinita topologin på G .
• Varje maximal undergrupp av G har ändligt index i G .
• Gruppen G är ändligt genererad men inte ändligt presentabel .
• Stabilisatorn för nivå ett hörn i $T_{2}$ i G (undergruppen av element som fungerar som identitet på strängarna 0 och 1), genereras av följande element :

$G_{\{0,1\}}=\langle b,c,d,aba,aca,ada\rangle .$

$G_{\{0,1\}}$ är en normal undergrupp av index 2 i G och

$G=G_{\{0,1\}}\sqcup aG_{\{0,1\}}.$

• Ett reducerat ord representerar ett element av $\displaystyle G_{\{0,1\}}}$ om och endast om detta ord innefattar ett jämnt antal förekomster av en .
• Om w är ett reducerat ord i G med ett positivt jämnt antal förekomster av a , så finns det ord u , v (inte nödvändigtvis reducerat) så att:

$w=(u,v)\quad {\text{and}}\quad {\begin{cases}|u|,|v|\leqslant {\tfrac {1}{2}}|w| &|w|{\text{ udda}}\\|u|,|v|\leqslant {\tfrac {1}{2}}(|w|+1)&|w|{\text{ jämn}} \end{cases}}$

Detta kallas ibland för kontraktionsegenskapen . Det spelar en nyckelroll i många bevis angående G eftersom det gör det möjligt att använda induktiva argument om längden på ett ord.

• Gruppen G har lösbart ordproblem och lösbart konjugationsproblem (konsekvens av kontraktionsegenskapen).

Se även

• Geometrisk gruppteori
• Tillväxt av ändligt genererade grupper
• Mottagliga grupper
• Itererad monodromigrupp
• Icke-kommutativ kryptografi

externa länkar

• Rostislav Grigorchuk och Igor Pak, Groups of Intermediate Growth: an Introduction for Beginners , preprint, 2006, arXiv