Grupo Grigorchuk

En el área matemática de la teoría de grupos , el grupo de Grigorchuk o el primer grupo de Grigorchuk es un grupo finitamente generado construido por Rostislav Grigorchuk que proporcionó el primer ejemplo de un grupo finitamente generado de crecimiento intermedio (es decir, más rápido que el polinomial pero más lento que el exponencial) . El grupo fue construido originalmente por Grigorchuk en un artículo de 1980 ^[1] y luego demostró en un artículo de 1984 ^[2] que este grupo tiene un crecimiento intermedio, proporcionando así una respuesta a un importante problema abierto planteado por John Milnor en 1968. El grupo de Grigorchuk sigue siendo un objeto clave de estudio en la teoría geométrica de grupos , particularmente en el estudio de los llamados grupos de ramas y grupos de autómatas, y tiene conexiones importantes con la teoría de grupos de monodromía iterada . ^[3]

Historia y significado

El crecimiento de un grupo finitamente generado mide la asintótica, a partir del tamaño de una n -bola en el gráfico de Cayley del grupo (es decir, el número de elementos de G que pueden expresarse como palabras de longitud como máximo n en el conjunto generador de G ). El estudio de las tasas de crecimiento de grupos finitamente generados se remonta a la década de 1950 y está motivado en parte por la noción de entropía de volumen (es decir, la tasa de crecimiento del volumen de bolas) en el espacio de recubrimiento universal de una variedad compacta de Riemann en geometría diferencial . Es obvio que la tasa de crecimiento de un grupo finitamente generado es como máximo exponencial y también se entendió desde el principio que los grupos nilpotentes finitamente generados tienen crecimiento polinomial. En 1968, John Milnor planteó una pregunta ^[4] sobre la existencia de un grupo finitamente generado de crecimiento intermedio , es decir, más rápido que cualquier función polinomial y más lento que cualquier función exponencial. Un resultado importante en el tema es el teorema de Gromov sobre grupos de crecimiento polinomial , obtenido por Gromov en 1981, que muestra que un grupo finitamente generado tiene crecimiento polinomial si y solo si este grupo tiene un subgrupo nilpotente de índice finito . Antes del trabajo de Grigorchuk, hubo muchos resultados que establecían la dicotomía del crecimiento (es decir, que el crecimiento es siempre polinomial o exponencial) para varias clases de grupos finitamente generados, como grupos lineales , grupos resolubles , ^{[5] [6]} etc. ${\displaystyle n\to \infty }$

El grupo G de Grigorchuk fue construido en un artículo de 1980 de Rostislav Grigorchuk ^[1] , donde demostró que este grupo es infinito, periódico y residualmente finito . En un artículo posterior de 1984 ^[2] Grigorchuk demostró que este grupo tiene un crecimiento intermedio (este resultado fue anunciado por Grigorchuk en 1983). ^[7] Más precisamente, demostró que G tiene un crecimiento b ( n ) que es más rápido que pero más lento que donde . El límite superior fue mejorado posteriormente por Laurent Bartholdi ^[8] a ${\displaystyle \exp({\sqrt {n}})}$ ${\displaystyle \exp(n^{s})}$ ${\displaystyle s=\log _{32}31\approx 0.991}$

${\displaystyle s={\frac {\log 2}{\log 2-\log \eta }}\approx 0.7674,\qquad \eta ^{3}+\eta ^{2}+\eta =2.}$

Yurii Leonov demostró un límite inferior de ^[9] . Se conjeturó que el límite ${\displaystyle \exp(n^{0.504})}$

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

y esto siguió siendo un problema abierto importante hasta que el problema fue resuelto en 2020 por Anna Erschler y Tianyi Zheng ^[10] en el que se demostró que el límite es igual a . ${\displaystyle s}$

El grupo de Grigorchuk también fue el primer ejemplo de un grupo que es dócil pero no elementalmente dócil , respondiendo así a un problema planteado por Mahlon Marsh Day en 1957. ^[11]

Originalmente, el grupo G de Grigorchuk se construyó como un grupo de transformaciones que preservaban la medida de Lebesgue en el intervalo unitario, pero posteriormente se encontraron descripciones más simples de G y ahora se presenta generalmente como un grupo de automorfismos del árbol binario regular infinito con raíz . El estudio del grupo de Grigorchuk informó en gran parte el desarrollo de la teoría de grupos de ramas, grupos de autómatas y grupos autosimilares en los años 1990-2000 y el grupo de Grigorchuk sigue siendo un objeto central en esta teoría. Recientemente, se han descubierto conexiones importantes entre esta teoría y la dinámica compleja, particularmente la noción de grupos de monodromía iterada , en el trabajo de Volodymyr Nekrashevych, ^[12] y otros.

Después del artículo de Grigorchuk de 1984, hubo muchas ampliaciones y generalizaciones posteriores. ^{[13] [14] [15] [16]}

Definición

El árbol binario infinito T ₂ . Sus nodos están etiquetados por cadenas de 0 y 1.

Aunque inicialmente el grupo de Grigorchuk se definió como un grupo de transformaciones que preservan la medida de Lebesgue del intervalo unidad, en la actualidad este grupo suele darse por su realización como un grupo de automorfismos del árbol binario regular infinito con raíz T ₂ . El árbol T ₂ es el conjunto Σ ^* de todas las cadenas finitas en el alfabeto  Σ = {0,1} , incluyendo la cadena vacía ∅ , que tiene como raíz T ₂ . Para un vértice  x de T ₂ la cadena x 0 es el hijo izquierdo de x y la cadena x 1 es el hijo derecho de x en T ₂ . El grupo de todos los automorfismos  Aut( T ₂ ) puede así considerarse como el grupo de todas las permutaciones que preservan la longitud σ de Σ ^* que también respetan la relación de segmento inicial : siempre que una cadena  x es un segmento inicial de una cadena  y entonces σ( x ) es un segmento inicial de σ( y ) .    

El grupo de Grigorchuk  G es el subgrupo de Aut( T ₂ ) generado por cuatro elementos específicos de Aut( T ₂ ) definidos de la siguiente manera (nótese que ∅ está fijado por cualquier automorfismo de árbol): donde y $${\displaystyle G=\langle a,b,c,d\rangle \leq {\text{Aut}}(T_{2}){\text{,}}}$$ $${\displaystyle a(0)=1{\text{,}}\qquad a(1)=0{\text{,}}\qquad \forall x\in \Sigma ^{*}\quad {\begin{cases}a(0x)=1x\\a(1x)=0x\end{cases}}}$$ $${\displaystyle {\begin{aligned}&b(0)=c(0)=d(0)=0\\&b(1)=c(1)=d(1)=1{\text{,}}\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){\text{.}}\end{cases}}\end{aligned}}}$$

Acción del conjunto generador estándar del grupo de Grigorchuk sobre el árbol T ₂ . Los triángulos denotan subárboles infinitos que permanecen inalterados.

Sólo el elemento a se define explícitamente; intercambia los árboles hijos de ∅ . Los elementos b , c y d se definen mediante una recursión mutua .

Para entender el efecto de las últimas operaciones, considere la rama  B más a la derecha de T ₂ , que comienza {∅, 1, 11, 111, ...} . Como rama, B es isomorfo en orden a El árbol original T ₂ se puede obtener enraizando un árbol isomorfo a T ₂ en cada elemento de B ; a la inversa, se puede descomponer T ₂ en subárboles isomorfos indexados por elementos de . ${\displaystyle \mathbb {N} .}$ ${\displaystyle B\cong \mathbb {N} }$

Las operaciones b , c y d respetan esta descomposición: fijan cada elemento de B y actúan como automorfismos en cada subárbol indexado. Cuando b actúa, fija cada subárbol con índice ≡ 2 (mod 3) , pero actúa como a en el resto. Del mismo modo, cuando c actúa, fija solo los subárboles de índice ≡ 1 (mod 3) ; y d fija los de índice ≡ 0 (mod 3) .

Una notación compacta para estas operaciones es la siguiente: sea la rama izquierda (resp. derecha) de T ₂ T _L = 0Σ ^* (resp. T _R = 1Σ ^* ), de modo que Escribimos f = ( g , h ) para significar que f actúa como g en T _L y como h en T _R . Por lo tanto De manera similar donde id es la función identidad . $${\displaystyle a(T_{L})\subseteq T_{R},\quad a(T_{R})\subseteq T_{L}{\text{.}}}$$ $${\displaystyle {\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}{\text{.}}\end{cases}}\end{aligned}}}$$ $${\displaystyle aba=(c,a),\quad aca=(d,a),\quad ada=(b,{\text{id}}){\text{,}}}$$

Propiedades

Las siguientes son propiedades algebraicas básicas del grupo de Grigorchuk (ver ^[17] para pruebas):

• El grupo G es infinito. ^[2]
• El grupo G es residualmente finito . ^[2] Sea el homomorfismo de restricción que envía cada elemento de G a su restricción a los primeros n niveles de T ₂ . Los grupos Aut( T [ n ]) son finitos y para cada g no trivial en G existe n tal que ${\displaystyle \rho _{n}:G\to {\text{Aut}}(T[n])}$ ${\displaystyle \rho _{n}(g)\neq 1.}$
• El grupo G está formado por a y dos cualesquiera de los tres elementos b,c,d . Por ejemplo, podemos escribir ${\displaystyle G=\langle a,b,c\rangle .}$
• Los elementos a , b , c , d son involuciones .
• Los elementos b , c , d conmutan por pares y bc = cb = d , bd = db = c , dc = cd = b , de modo que es un grupo abeliano de orden 4 isomorfo al producto directo de dos grupos cíclicos de orden 2. ${\displaystyle \langle b,c,d\rangle \leqslant G}$
• Combinando las dos propiedades anteriores, vemos que cada elemento de G puede escribirse como una palabra (positiva) en a , b , c , d tal que esta palabra no contenga ninguna subpalabra de la forma aa , bb , cc , dd , cd , dc , bc , cb , bd , db . Tales palabras se denominan palabras reducidas .
• El grupo G es un 2-grupo , es decir, cada elemento de G tiene un orden finito que es una potencia de 2. ^[1]
• El grupo G es periódico (como un grupo de 2) y no localmente finito (ya que se genera de manera finita). Como tal, es un contraejemplo del problema de Burnside .
• El grupo G tiene un crecimiento intermedio. ^[2]
• El grupo G es dócil pero no elementalmente dócil . ^[2]
• El grupo G es simplemente infinito , es decir G es infinito pero todo grupo cociente propio de G es finito.
• El grupo G tiene la propiedad de subgrupo de congruencia : un subgrupo H tiene índice finito en G si y solo si hay un entero positivo n tal que ${\displaystyle \ker(\rho _{n})\leqslant H.}$
• El grupo G tiene un problema de pertenencia a un subgrupo solucionable, es decir, hay un algoritmo que, dadas palabras arbitrarias w , u ₁ , ..., u _{n ,} decide si w representa o no un elemento del subgrupo generado por u ₁ , ..., u _n . ^[18]
• El grupo G es subgrupo separable , es decir, cada subgrupo finitamente generado es cerrado en la topología pro-finita en G. ^[18]
• Cada subgrupo maximo de G tiene un índice finito en G. ^[19 ]
• El grupo G es finitamente generado pero no finitamente presentable . ^{[2] [20]}
• El estabilizador de los vértices de nivel uno en G ( el subgrupo de elementos que actúan como identidad en las cadenas 0 y 1), está generado por los siguientes elementos: ${\displaystyle T_{2}}$

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

${\displaystyle G_{\{0,1\}}}$es un subgrupo normal de índice 2 en G y

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

• Una palabra reducida representa un elemento de si y sólo si esta palabra implica un número par de ocurrencias de a . ${\displaystyle G_{\{0,1\}}}$
• Si w es una palabra reducida en G con un número par positivo de ocurrencias de a , entonces existen palabras u , v (no necesariamente reducidas) tales que:

${\displaystyle w=(u,v)\quad {\text{and}}\quad {\begin{cases}|u|,|v|\leqslant {\tfrac {1}{2}}|w|&|w|{\text{ odd}}\\|u|,|v|\leqslant {\tfrac {1}{2}}(|w|+1)&|w|{\text{ even}}\end{cases}}}$

A esto a veces se le llama propiedad de contracción . Desempeña un papel clave en muchas demostraciones sobre G, ya que permite utilizar argumentos inductivos sobre la longitud de una palabra.

• El grupo G tiene un problema de palabras solucionable y un problema de conjugación solucionable (consecuencia de la propiedad de contracción).

Véase también

• Teoría de grupos geométricos
• Crecimiento de grupos finitamente generados
• Grupos afines
• Grupo de monodromía iterada
• Criptografía no conmutativa

Referencias

1. RI Grigorchuk. Sobre el problema de Burnside sobre grupos periódicos. (Ruso) Funktsionalyi Analiz i ego Prilozheniya, vol. 14 (1980), núm. 1, págs. 53–54.
2. RI Grigorchuk, Grados de crecimiento de grupos finitamente generados y la teoría de medias invariantes. Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya. vol. 48 (1984), núm. 5, págs. 939–985.
3. Volodymyr Nekrashevych. Grupos autosimilares. Encuestas y monografías matemáticas, 117. American Mathematical Society, Providence, RI, 2005. ISBN  0-8218-3831-8 .
4. John Milnor, Problema No. 5603, American Mathematical Monthly , vol. 75 (1968), págs. 685–686.
5. John Milnor . Crecimiento de grupos resolubles finitamente generados. Archivado el 23 de mayo de 2011 en la Wayback Machine . Journal of Differential Geometry . vol. 2 (1968), págs. 447–449.
6. Joseph Rosenblatt. Medidas invariantes y condiciones de crecimiento , Transactions of the American Mathematical Society , vol. 193 (1974), págs. 33–53.
7. Grigorchuk, R. I. (1983). К проблеме Милнора о групповом росте[Sobre el problema de Milnor del crecimiento del grupo]. Doklady Akademii Nauk SSSR (en ruso). 271 (1): 30–33.
8. Laurent Bartholdi. Límites inferiores del crecimiento de un grupo que actúa sobre el árbol binario enraizado. International Journal of Algebra and Computation, vol. 11 (2001), núm. 1, págs. 73–88.
9. Yu. G. Leonov, Sobre un límite inferior para el crecimiento de un grupo de 2 con 3 generadores. Matematicheskii Sbornik, vol. 192 (2001), núm. 11, págs. 77–92; traducción en: Sbornik Mathematics. vol. 192 (2001), núm. 11–12, págs. 1661–1676.
10. Anna Erschler , Tianyi Zheng "Crecimiento de los grupos periódicos de Grigorchuk". Inventiones Mathematicae , vol. 219 (2020), n.º 3, págs. 1069-1155.
11. Mahlon M. Day. Semigrupos susceptibles. Illinois Journal of Mathematics, vol. 1 (1957), págs. 509–544.
12. Volodymyr Nekrashevych, Grupos autosimilares. Encuestas y monografías matemáticas, 117. American Mathematical Society, Providence, RI, 2005. ISBN 0-8218-3831-8 . 
13. Roman Muchnik e Igor Pak . Sobre el crecimiento de los grupos de Grigorchuk. Revista internacional de álgebra y computación, vol. 11 (2001), núm. 1, págs. 1–17.
14. Laurent Bartholdi. El crecimiento del grupo de torsión de Grigorchuk. International Mathematics Research Notices, 1998, núm. 20, págs. 1049–1054.
15. Anna Erschler . Constantes críticas para la recurrencia de paseos aleatorios en G-espacios. Archivado el 25 de julio de 2011 en Wayback Machine. Université de Grenoble. Annales de l'Institut Fourier, vol. 55 (2005), núm. 2, pp. 493–509.
16. Jeremie Brieussel, Crecimiento de ciertos grupos Archivado el 2 de octubre de 2011 en Wayback Machine , Tesis doctoral, Universidad de París, 2008.
17. Pierre de la Harpe. Temas de teoría geométrica de grupos. Chicago Lectures in Mathematics. University of Chicago Press, Chicago. ISBN 0-226-31719-6 ; Cap. VIII, El primer grupo de Grigorchuk, págs. 211–264. 
18. RIGrigorchuk y JS Wilson. Una propiedad estructural relativa a la conmensurabilidad abstracta de subgrupos. Journal of the London Mathematical Society (2), vol. 68 (2003), núm. 3, págs. 671–682.
19. EL Pervova, Subgrupos densos en todas partes de un grupo de automorfismos de árboles. (en ruso). Trudy Matematicheskogo Instituta Imeni VA Steklova. vol. 231 (2000), Din. Hermana, Avtom. Yo Beskon. Gruppy, págs. 356–367; traducción en: Actas del Instituto Steklov de Matemáticas, vol 231 (2000), no. 4, págs. 339–350.
20. IG Lysënok, Un conjunto de relaciones definitorias para el grupo Grigorchuk. Matematicheskie Zametki, vol. 38 (1985), núm. 4, págs. 503–516.

Enlaces externos

• Rostislav Grigorchuk e Igor Pak, Grupos de crecimiento intermedio: una introducción para principiantes, preimpresión, 2006, arXiv