Grupa Grigorczuka

W matematycznym obszarze teorii grup grupa Grigorczuka lub pierwsza grupa Grigorczuka to skończenie generowana grupa skonstruowana przez Rostisława Grigorczuka , która dostarczyła pierwszego przykładu skończenie wygenerowanej grupy o pośrednim (to znaczy szybszym niż wielomian, ale wolniejszym niż wykładniczy) wzrost . Grupa została pierwotnie skonstruowana przez Grigorczuka w artykule z 1980 roku, a następnie udowodnił on w artykule z 1984 roku, że ta grupa ma średni wzrost, dostarczając w ten sposób odpowiedzi na ważny otwarty problem postawiony przez Johna Milnora w 1968 roku. Grupa Grigorczuka pozostaje kluczowym przedmiotem badań. zajmuje się geometryczną teorią grup , w szczególności badaniem tzw. grup gałęzi i grup automatów, i ma ważne powiązania z teorią iterowanych grup monodromicznych .

Historia i znaczenie

Wzrost skończenie wygenerowanej grupy mierzy asymptotyki, ponieważ wielkości $n$ -kuli na wykresie Cayleya liczby elementów G które można wyrazić jako słowa o długości co najwyżej n w zbiorze generującym G ). Badanie tempa wzrostu skończenie generowanych grup sięga lat pięćdziesiątych XX wieku i jest częściowo motywowane pojęciem entropii objętości ( czyli tempo wzrostu objętości kulek) w uniwersalnej przestrzeni pokrywającej zwartej rozmaitości riemannowskiej w geometrii różniczkowej . Jest oczywiste, że tempo wzrostu skończenie generowanej grupy jest co najwyżej wykładnicze i wcześnie zrozumiano również, że skończenie generowane grupy nilpotentne mają wzrost wielomianowy. W 1968 roku John Milnor postawił pytanie o istnienie skończenie generowanej grupy o pośrednim wzroście , to znaczy szybciej niż jakakolwiek funkcja wielomianowa i wolniej niż jakakolwiek funkcja wykładnicza. Ważnym wynikiem w tej dziedzinie jest twierdzenie Gromowa o grupach wzrostu wielomianowego , otrzymane przez Gromowa w 1981 roku, które pokazuje, że skończenie generowana grupa ma wzrost wielomianowy wtedy i tylko wtedy, gdy ta grupa ma nilpotentną podgrupę o skończonym indeksie . Przed pracą Grigorczuka było wiele wyników ustalających dychotomię wzrostu (to znaczy, że wzrost jest zawsze wielomianowy lub wykładniczy) dla różnych klas skończenie generowanych grup, takich jak grupy liniowe , grupy rozwiązywalne itp.

G Grigorczuka została skonstruowana w artykule Rostisława Grigorczuka z 1980 roku , w którym udowodnił, że ta grupa jest nieskończona, okresowa i szczątkowo skończona . W kolejnym artykule z 1984 r. Grigorczuk udowodnił, że ta grupa ma średni wzrost (wynik ten ogłosił Grigorczuk w 1983 r.). Dokładniej, udowodnił, że G ma wzrost b ( n ), który jest szybszy niż ${\ Displaystyle \ exp ({\ sqrt {n}})}$${\ Displaystyle \ exp (n ^ {s})}$ gdzie ${\ Displaystyle s = \ log _ {32} 31 \ około 0,991}$ . Górna granica została później poprawiona przez Laurenta Bartholdiego do

${\ Displaystyle s = {\ Frac {\ log 2} {\ log 2- \ log \ eta}} \ około 0,7675,\qquad \eta ^{3}+\eta ^{2}+\eta =2.}$

Dolna granica ${\ Displaystyle \ exp (n ^ {0,504})}$ została udowodniona przez Jurija Leonowa. Dokładna asymptotyka wzrostu G jest nadal nieznana. Przypuszcza się, że granica

${\ Displaystyle \ lim _ {n \ do \ infty} \ log _ {n} \ log b (n)}$

istnieje, ale nawet to pozostaje głównym otwartym problemem. Ten problem został rozwiązany w 2020 roku przez Erschlera i Zhenga. Pokazują, że granica jest równa ${\ displaystyle s}$ .

Grupa Grigorczuka była również pierwszym przykładem grupy, która jest uległa , ale nie elementarna , odpowiadając w ten sposób na problem postawiony przez Mahlona Marsha Daya w 1957 roku.

G Grigorczuka została skonstruowana jako grupa przekształceń zachowujących miarę Lebesgue'a na przedziale jednostkowym, ale później znaleziono prostsze opisy G i obecnie jest zwykle przedstawiana jako grupa automorfizmów nieskończonego regularnego drzewa o korzeniach binarnych . Badanie grupy Grigorczuka w dużej mierze wpłynęło na rozwój teorii grup rozgałęzionych, grup automatów i grup samopodobnych w latach 90. – 2000, a grupa Grigorczuka pozostaje centralnym obiektem tej teorii. Ostatnio ważne powiązania między tą teorią a dynamiką złożoną, zwłaszcza pojęciem iterowanych grup monodromicznych , zostały odkryte w pracy Wołodymyra Niekraszewicza. i inni.

Po artykule Grigorczuka z 1984 roku było wiele późniejszych rozszerzeń i uogólnień.

Definicja

Nieskończone drzewo binarne T ₂ . Jego węzły są oznaczone ciągami zer i jedynek.

Chociaż początkowo grupę Grigorczuka definiowano jako grupę przekształceń zachowujących miarę Lebesgue'a przedziału jednostkowego, obecnie grupa ta jest zwykle dana przez jej realizację jako grupa automorfizmów nieskończonego drzewa regularnego o korzeniach binarnych T ₂ . Drzewo T ₂ $Sigma = \ {0,1 \}$ realizowane jako zbiór wszystkich skończonych ciągów w alfabecie $1$ plus pusty ciąg $który$ jest głównym wierzchołkiem T ₂ . Dla wierzchołka x T ₂ łańcuch x 0 jest lewym dzieckiem x , a łańcuch x 1 jest prawym dzieckiem x w T ₂ . Grupę wszystkich automorfizmów Aut( T ₂ ) można zatem traktować jako grupę wszystkich permutacji zachowujących długość σ Σ ${\ Displaystyle \ Sigma ^ {*}}$ , które również szanują początkową relację segmentów , to znaczy taką, że ilekroć ciąg jest początkowym segmentem ciągu y , to σ ( x ) jest początkowym segmentem σ ( y ).

Grupa Grigorczuka G jest wtedy definiowana jako podgrupa Aut( T ₂ ) wygenerowana przez cztery określone elementy Aut( T ₂ ):

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

gdzie automorfizmy a , b , c , d są zdefiniowane w następujący sposób (zwróć uwagę, że wszystkie automorfizmy drzewa są ustalane ): ${\ displaystyle \ varnothing}$

${\ Displaystyle {\ rozpocząć {wyrównane} a (0) = 1, \ qquad a (1) = 0, \ qquad \ forall x \ in \ Sigma ^ {*} \ quad & {\ rozpocząć {przypadki} a (0x )=1x\\a(1x)=0x\end{przypadki}}\\[6pt]{\begin{wyrównane}&b(0)=c(0)=d(0)=0\\&b(1) =c(1)=d(1)=1\end{wyrównane}}\qquad \forall x\in \Sigma ^{*}\quad &{\begin{wyrównane}&{\begin{przypadki}b(0x )=0a(x)\\b(1x)=1c(x)\end{przypadki}}\\&{\begin{przypadki}c(0x)=0a(x)\\c(1x)=1d( x)\end{przypadki}}\\&{\begin{przypadki}d(0x)=0x\\d(1x)=1b(x)\end{przypadki}}\end{wyrównane}}\end{wyrównane }}}$

Działanie standardowego zespołu prądotwórczego grupy Grigorczuk na drzewie T ₂ . Trójkąty oznaczają nieskończone poddrzewa, które pozostają niezmienione.

Widzimy, że tylko element a jest zdefiniowany jawnie, a elementy b , c , d są definiowane rekurencyjnie. Aby uzyskać lepszy obraz tej akcji, zauważamy, że ma naturalną gradację na poziomy określone przez długość strun: ${\ displaystyle T_ {2}}$

${\ Displaystyle {\ rozpocząć {wyrównane} i \ ell = 0 \ qquad \ varnothing \\& \ ell = 1 \ qquad 0,1 \ \&\ell =2\qquad 00,01,10,11\\&\qquad \cdots \end{aligned}}}$

Niech teraz oznaczymy sumę wszystkich wierzchołków z poziomem ${\ Displaystyle \ leqslant n.}$${\ displaystyle T [n]}$ Oznacza to:

$\ Displaystyle {\ rozpocząć {wyrównane} T [0 ]&=\{\varnic \}\\T[1]&=\{\varnic ,0,1\}\\T[2]&=\{\varnic ,0,1,00,01,10, 11\}\\&\quad \cdots \end{aligned}}}$

Ponieważ automorfizmy drzewa zachowują długość, jako zbiór jest ustalany przez $\$$} (T_ {2})}$ dla wszystkich ${\ Displaystyle n \ geqslant 0.}$ Mając to na uwadze, piszemy:

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

Nazywamy $oznaczamy$ odpowiednio $prawą$ ) gałąź i $T_ {L}}$${$ (odp. ${\ Displaystyle T_ {R}}$ ). Dzięki tej notacji widzimy, że:

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

Teraz możemy również zapisać działanie elementów b , c i d w kategoriach związku rozłącznego w następujący sposób:

${\ Displaystyle {\ rozpocząć {wyrównane} b: = (a, c) \ quad & \ Longleftrightarrow \ quad b (x) = {\ rozpocząć {przypadki} a (x) i x \ w T_ {L} \\ c ( x)&x\in T_{R}\end{przypadki}}\\c:=(a,d)\quad &\Longleftrightarrow \quad c(x)={\begin{przypadki}a(x)&x\in T_{L}\\d(x)&x\in T_{R}\end{cases}}\\d:=({\text{id}},b)\quad &\Longleftrightarrow \quad d(x) ={\begin{przypadki}x&x\in T_{L}\\b(x)&x\in T_{R}\end{przypadki}}\end{wyrównane}}}$

Podobnie mamy:

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

Nieruchomości

Poniżej przedstawiono podstawowe właściwości algebraiczne grupy Grigorczuka (patrz dowody):

• Grupa G jest nieskończona.
• Grupa G jest rezydualnie skończona . Niech ${\ Displaystyle \ rho _ {n}: G \ do {\ tekst {Aut}} (T [n])}$ będzie homomorfizmem restrykcyjnym, który wysyła każdy element G do jego ograniczenia do skończonego drzewa T [ n ]. Grupy Aut( T [ n ]) są skończone i dla każdego nietrywialnego g w G istnieje n ${\ Displaystyle \ rho _ {n} (g) \ neq 1.$ ≠
• Grupa G jest generowana przez a i dowolne dwa z trzech elementów b,c,d . Na przykład możemy napisać ${\ Displaystyle G = \ langle a, b, c \ rangle.}$
• Elementy a , b , c , d są inwolucjami .
• Elementy b , c , d dojeżdżają parami i bc = cb = re , bd = db = do , dc = cd = b , tak że ${\ Displaystyle \ langle b, c, d \ rangle \leqslant G}$ jest grupą abelową rzędu 4 izomorficzną z iloczyn bezpośredni dwóch grup cyklicznych rzędu 2.
• Łącząc dwie poprzednie własności widzimy, że każdy element G można zapisać jako (dodatnie) słowo w a , b , c , d takie, że to słowo nie zawiera żadnych podsłów postaci aa , bb , cc , dd , cd , dc , pne , cb , bd , db . Takie słowa nazywane są zredukowanymi .
• Grupa G jest grupą 2-grupową , to znaczy każdy element w G ma skończony porządek , który jest potęgą 2.
• Grupa G ma średni wzrost.
• Grupa G jest podatna , ale nie elementarna .
• Grupa G jest po prostu nieskończona , to znaczy G jest nieskończona, ale każda właściwa grupa ilorazowa G jest skończona.
• Grupa G ma właściwość podgrupy kongruencji : podgrupa H ma skończony indeks w G wtedy i tylko wtedy, gdy istnieje dodatnia liczba całkowita n taka, że ${\ Displaystyle \ ker (\ rho _ {n}) \ leqslant H.}$
• Grupa G ma rozwiązywalny problem przynależności do podgrup, to znaczy istnieje algorytm, który dla danych dowolnych słów w , u ₁ , ..., u _n decyduje, czy w reprezentuje element podgrupy wygenerowanej przez u ₁ , .. ., u _n .
• Grupa G jest podgrupą separowalną , to znaczy każda skończenie generowana podgrupa jest domknięta w topologii pro-skończonej na G .
• Każda maksymalna podgrupa G ma skończony indeks w G .
• Grupa G jest generowana skończenie, ale nie daje się skończenie przedstawiać .
• Stabilizator wierzchołków poziomu pierwszego w $}$ (podgrupa elementów, które działają jako tożsamość na łańcuchach 0 i 1), jest generowany przez następujące elementy: T 2 {\ displaystyle T_

${\ Displaystyle G _ {\ {0,1 \}} = \ langle b, c, d, aba, aca, ada \ rangle.} sol { , 1 } {\ Displaystyle G _ {\$

$}$ jest normalną podgrupą o indeksie 2 w G i

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

• Zredukowane słowo reprezentuje element wtedy i tylko $.$ parzystą liczbę wystąpień a
• Jeśli w jest słowem zredukowanym w G z dodatnią parzystą liczbą wystąpień a , to istnieją słowa u , v (niekoniecznie zredukowane) takie, że:

${\ Displaystyle w = (u, v) \ quad {\ tekst {i}} \ quad {\ rozpocząć {przypadki} | u |, | v | \ leqslant {\ tfrac {1} {2}} | w | & |w|{\text{nieparzyste}}\\|u|,|v|\leqslant {\tfrac {1}{2}}(|w|+1)&|w|{\text{parzyste}}\ end{cases}}}$

Nazywa się to czasem właściwością kontrakcji . Odgrywa kluczową rolę w wielu dowodach dotyczących G , ponieważ pozwala na użycie argumentów indukcyjnych na długości słowa.

• Grupa G ma rozwiązywalny problem słowny i rozwiązywalny problem koniugacji (konsekwencja własności kontrakcji).

Zobacz też

• Geometryczna teoria grup
• Wzrost skończenie generowanych grup
• Przyzwoite grupy
• Iterowana grupa monodromiczna
• Kryptografia nieprzemienna

Linki zewnętrzne

• Rostislav Grigorchuk i Igor Pak, Grupy o średnim wzroście: wprowadzenie dla początkujących , przedruk, 2006, arXiv