tamaño del menor grupo generador de un grupo

Question

Supongamos que tengo un grupo bonito (por ejemplo, ¿hiperbólico de palabras? ¿bi-automático? ¿automático?) y quiero saber cuánto mide el conjunto generador más pequeño. ¿Es esto factible (o, por decirlo de un modo más optimista, cuál es la clase de grupos más grande para la que es factible)? En realidad, lo que más me interesa es saber si existe un conjunto generador de cardinalidad $2,$ pero sospecho que es tan difícil como la pregunta general.

EDITAR Lo que yo realmente quiere saber es la respuesta para retículos (por ejemplo, $SL(n, \mathbb{Z}),$ ), pero probablemente no pertenezca a ninguna clase manejable.

ACTUALIZACIÓN De hecho, se sabe que $SL(n, \mathbb{Z})$ se genera mediante $2$ elementos (Hua+Reiner escribieron un grupo electrógeno con tres elementos en 1949, al igual que M. Conder et al en 1992, para $SL(3, \mathbb{Z})$ pero Stanton M. Trott lo hizo con dos generadores en 1962). Los generadores son: $\begin{pmatrix} 1 & 0 & 0 & \dots & 0 \\ 1 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ . & . & . & \dots & .\\ 0 & 0 & 0 & \dots & 1 \end{pmatrix}$ y $\begin{pmatrix} 0 & 1 & 0 & \dots & 0\\ 0 & 0 & 1 & \dots & 0\\ . & . & . & \dots & .\\ 0 & 0 & 0 & \dots & 1\\ (-1)^n & 0 & 0 & \dots & 0 \end{pmatrix}$

Answer 1

Recuerdo haber estudiado este tipo de cuestiones para grupos finitos y desde el punto de vista de la complejidad. Recuerdo que se cree (pero todavía está abierto) que $d(G)=2$ es un problema NP-completo incluso para un grupo de permutaciones (dado un conjunto generador es fácil verificar que genera todo el grupo, por lo que el problema está en NP). No estoy seguro de si esta conjetura está formalmente enunciada en alguna parte (véase aquí para una declaración informal).

Por otra parte, permítanme explicar por qué es obvio que el $d(G)=?\ 2$ problema es difícil. Esto ya lo entendió Hall en este documento clásico . Por ejemplo $G=H^m$ donde $H=A_n$ y $n!/8< m < n!/4.$ Para $m=n!/8$ y $n$ lo suficientemente grande, $d(G)=2$ mientras que para $m=n!/4$ , $d(G)=3$ . Calcular dónde se produce exactamente la transición implica calcular la inversión de Möbius de toda la red de subgrupos de $H$ . Esto es, claramente, un Tarea hercúlea en la práctica si no en teoría . Obsérvese que la probabilidad de que O(1) elementos aleatorios generen $G$ llega a cero. La misma historia para $H=SL(2,p)$ . Ver más aquí .

Answer 2

@Igor: Si no recuerdo mal, para celosías en $\mathrm{SL}_n(\mathbb R)$ , $n\ge 2$ la respuesta es 2 (quizás alguien pueda corregirme).

Actualización 1. $\mathrm{SL}_n(\mathbb R)$ la pregunta es interesante.

Actualización 3. Le puede interesar este documento Demuestran que los principales subgrupos de congruencia de $\mathrm{SL}_n(\mathbb Z)$ tienen un número acotado de generadores, pero no es cierto para todos los subgrupos aritméricos de $\mathrm{SL}_n(\mathbb R)$ .

Para los grupos hiperbólicos existe un resultado de Arzhantseva-Olshanskii (Arzhantseva, G. N.; Olʹshanskiĭ, A. Yu. Generalidad de la clase de grupos en los que los subgrupos con un menor número de generadores son libres. Mat. Zametki 59 (1996), no. 4, 489--496) que genéricamente los grupos hiperbólicos dados por $n$ generadores y una serie de relaciones son $n$ -generado. Por lo tanto, si tiene una presentación aleatoria con $n$ generadores, da un grupo que no puede ser generado por menos elementos. No creo que exista un algoritmo conocido que dé como resultado el menor número de generadores dada una presentación más la información adicional de que el grupo es hiperbólico (CAT(0), etc.).

Actualización 2. Como HW observó a continuación, si sabemos que el grupo es hiperbólico, podemos encontrar su $\delta$ .

Pero si además de la hiperbolicidad se conoce la $\delta$ (constante de hiperbolicidad), entonces el algoritmo debería existir simplemente porque no hay que buscar demasiado los generadores: todo conjunto generador debería consistir (hasta la conjugación) en elementos relativamente cortos. La prueba puede derivarse de un artículo de Arzhantseva (o Kapovich-Weidmann) Arzhantseva, Goulnara N., Una dicotomía para subgrupos finitamente generados de grupos hiperbólicos de palabras. Aspectos topológicos y asintóticos de la teoría de grupos, 1-10, Contemp. Math., 394, Amer. Math. Soc., Providence, RI, 2006 (resp. Kapovich, Ilya; Weidmann, Richard Nielsen methods and groups acting on hyperbolic spaces. Geom. Dedicata 98 (2003), 95-121. )

Answer 3

La respuesta a esta pregunta no se conoce ni siquiera en los grupos prácticamente abelain $G$ . Es bien sabido que $d(\hat G) \leq d(G) \leq d(\hat G) +1$ donde $d(G)$ es el número mínimo de generadores de $G$ y $d(\hat G)$ es el número mínimo de generadores para la terminación del perfil. En este caso $d(\hat G)$ es relativamente fácil de calcular.

Hay algunos ejemplos en los que $d(G) = d(\hat G) +1$ pero demostrando que $d(G) > d(\hat G)$ es no trivial y utiliza que ciertos elementos en el grupo de clase ideal si algunos anillo de enteros es no trivial. Es plassible que los únicos obstáculos para $d(G) = d(\hat G)$ (para virtualmente abeliano $G$ ) son de esta forma, pero aún no se ha precisado.

Por supuesto, si $d(G)=d(\hat G)$ se puede escribir un algoritmo estúpido y lento para verrificarlo, pero no estoy awere de cualquier alg que puede demostrar que $d(G) > d(\hat G)$ .

Answer 4

No existe un límite superior para los subgrupos de índice finito de $SL_n({\mathbb Z})$ . Es decir, dado cualquier número entero $k$ existe un subgrupo de índice finito de $SL_n({\mathbb Z})$ que necesita al menos $k$ generadores. No sé a quién se debe esto originalmente, pero es una observación de Rapinchuk que si se tira del centro de, digamos $SL_{2n}({\mathbb Z}/m {\mathbb Z})$ donde $m$ es el producto de $k$ primos distintos hasta $SL_{2n}({\mathbb Z}) $ se obtiene un subgrupo de índice finito de $SL_{2n}({\mathbb Z})$ cuya abelianización tiene $({\mathbb Z}/2{\mathbb Z})^k$ como cociente y, por tanto, es al menos $k$ generados.

Por otra parte, un subgrupo de índice finito de $SL_n({\mathbb Z})$ contiene un subgrupo de índice finito más pequeño generado por 3 elementos; este resultado es válido para cualquier grupo aritmético no uniforme de rango superior en un grupo lineal semisimple (y se debe a Ritumoni Sarma y Venkataramana).