Sea $F_n$ sea el grupo libre sobre las letras $x_1,...,x_n$ . Dado un conjunto de elementos $\{ w_1,...,w_m \} \subset F_n$ ¿cómo puedo saber si generan $F_n$ ? ¿Existen buenas condiciones necesarias/suficientes?
Del mismo modo, me gustaría poder saber si un conjunto finito de elementos en $F_n \times F_n$ generar todo el grupo? ¿Hay alguna forma algorítmica de hacerlo?
Aquí tiene una respuesta a su pregunta sobre $F_n$ .
El artículo de Nielsen de 1921 "On Calculation with non-commutative factors and its applications to group theory" da una respuesta algorítmica a un caso especial de su pregunta, a saber, cuando $w_1,...,w_m$ es una base libre de $F_n$ . El enfoque moderno del algoritmo de Nielsen utiliza secuencias de pliegues de Stallings, y además ese enfoque genera fácilmente a un algoritmo para decidir cuándo $w_1,...,w_m$ genera $F_n$ . El éxito de este algoritmo es quizá la mejor condición necesaria y suficiente que conozco.
El algoritmo es de naturaleza topológica y esa es la forma más fácil de describirlo, aunque al tratarse enteramente de grafos finitos es fácilmente programable.
Sea $R_n$ sea el grafo de la rosa con aristas etiquetadas $x_1,...,x_m$ Por lo tanto $\pi_1(R_n)$ se identifica con $F_n$ .
Del mismo modo $R_m$ sea el grafo rosa con aristas etiquetadas por símbolos abstractos $W_1,...,W_m$ Por lo tanto $\pi_1(R_m)$ se identifica con $F_m$ . Aquí estoy pensando en $W_i$ como símbolo abstracto que representa la palabra $w_i \in F_n$ .
Sea $f : R_m \to R_n$ el mapa que lleva vértice a vértice y toma la arista de $R_m$ etiquetado $W_i$ a la ruta de borde en $R_n$ etiquetados por letras de la palabra $w_i$ .
Su pregunta es equivalente a la siguiente ¿Cómo puedo saber que el mapa inducido $f_* : \pi_1(R_m) \to \pi_1(R_n)$ es suryectiva?
La respuesta es:
A continuación describiré el Paso 1, cómo construir la factorización plegada de Stallings de $f$ .
La palabra $w_i$ es una palabra reducida en los generadores $x_1,..,x_m$ y sus inversos. Sea $L_i$ sea la longitud de $w_i$ . Subdividir el borde de $R_m$ etiquetado $W_i$ en $L_i$ edgelets orientados y etiquetados, donde un edgelet está etiquetado $x_i$ si y sólo si la letra correspondiente de $w_i$ es $x_i$ o $x_i^{-1}$ la orientación apunta hacia delante si esa letra es $x_i$ y al revés si esa letra es $x_i^{-1}$ .
La secuencia de pliegues de Stallings se construye inductivamente, partiendo de $$R_m = G_0 \xrightarrow{f = h_0} R_n $$ En el paso inductivo, dado $$R_m = G_0 \xrightarrow{f_1} \cdots \xrightarrow{f_k} G_k \xrightarrow{h_k} R_n $$ uno se pregunta si $h_k$ es una inyección local. Si es así, la inducción está completa. Si no, entonces hay dos bordes orientados $e,e' \subset G_k$ con la misma etiqueta y con el mismo vértice inicial o el mismo vértice terminal. Entonces se puede factorizar $h_k : G_k \to R_n$ como $$G_k \xrightarrow{f_{k+1}} G_{k+1} \xrightarrow{h_{k+1}} R_n $$ donde $f_{k+1}$ identifica $e$ y $e'$ . Desde $G_{k+1}$ tiene un borde menos que $G_k$ la inducción debe parar. Es fácil ver que $(f_k)_*$ y $(f_{k+1})_*$ tienen la misma imagen, por lo tanto cuando la inducción se detiene los mapas $f_*$ y $h_*$ tienen la misma imagen.
Por último, permítanme justificar el paso 2. Dado que $h : G_K \to R_n$ es localmente inyectiva, se deduce de simples argumentos topológicos que existe un mapa de cobertura conexo $\tilde h : \tilde G \to R_n$ y una incrustación $i : G_K \hookrightarrow \tilde G$ tal que $h = \tilde h \circ i$ . Esto implica que $h_*$ no es suryectiva si y sólo si se cumple una de las siguientes condiciones: el mapa de cobertura $\tilde h$ tiene grado $d \ge 2$ o $\tilde h$ tiene grado $d=1$ y $\tilde G$ es un subgrafo propio de $G_K$ ; equivalentemente, $h$ no es un homeomorfismo.
Para cada generador $y_i$ de $F$ ejecutar dos algoritmos en paralelo:
A. Enumerar todas las palabras $w=w(x_1,...,x_k)$ en los elementos $x_1,...,x_k$ reescrito como palabras reducidas en $y_1,...y_n$ y para cada palabra comprobar si $w$ es igual a $y_i$ . Si para algunos $w$ lo es, pase al siguiente generador $y_{i+1}$ . Si para todos $y_i$ 's concluyes que tal $w=w_i$ existe, entonces $x_1,...,x_k$ generar $F$ . (Esta es la semidecidabilidad a la que se refiere Derek: Funciona siempre que el grupo ambiente tenga un problema de palabras resoluble, no es necesario suponer que el grupo es libre. Por ejemplo, $F_n\times F_n$ tiene un problema de palabras solucionable, por una razón obvia).
B. Para cada grupo de permutación $S_N$ enumerar todos los homomorfismos $\phi: F\to S_N$ y para cada $\phi$ comprobar si $\phi(y_i)$ pertenece al subgrupo generado por $\phi(x_1),...,\phi(y_k)$ . Si para algunos $\phi$ no lo hace, entonces has terminado: Los elementos $x_1,...,x_k$ no generan $F$ .
La cuestión es que cada grupo libre $F$ es LERF: Para cada subgrupo finitamente generado $H<F$ y $y\in F \setminus H$ existe un homomorfismo $\phi: F\to S_N$ tal que $\phi(y)\notin \phi(H)$ . Por lo tanto, si $H=<x_1,...,x_k>$ es un subgrupo propio de $F$ luego algún generador gratuito $y_i$ no está en $H$ . Por lo tanto, el algoritmo anterior acabará por demostrarlo.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
1 votos
No soy un experto, pero esto me parece pedir tanto que puede ser indecidible... Por ejemplo, en general, el problema de isomorfismo de grupo (con grupos presentados por los generadores y las relaciones) es indecidible ... probablemente google-able.
3 votos
Esto es decidible para $F_n$ e indecidible para $F_n\times F_n$ . El primero porque todo subgrupo finitamente generado de $F_n$ es cuasiconvexa, esto último se debe a la construcción de Mikhailova.
0 votos
Aunque el problema es indecidible en general para $F_n \times F_n$ es semidecidible en el sentido de que si los elementos dados generan todo el grupo, se puede demostrar que sí. El procedimiento de enumeración de cosets de Todd-Coxeter es probablemente la forma más eficaz de hacerlo en la práctica.
1 votos
En resumen, la solución negativa para $F_2\times F_2$ para $F_2=\langle x,y\rangle$ una presentación $\langle x,y\mid r_1,\dots,r_n\rangle$ define el grupo trivial si $\{(x,x),(y,y),(1,r_1),\dots,(1,r_n)\}$ genera $F_2\times F_2$ (verificación directa). Por lo tanto, un algoritmo para saber si un subconjunto finito genera $F_2\times F_2$ daría lugar a un algoritmo para resolver el problema de la trivialidad, que se sabe que no existe.