Supongamos que tenemos matrices enteras$A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Defina$\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ por$x_i\mapsto A_i$. ¿Existe un algoritmo para decidir si$\varphi$ es inyectable o no?
Respuestas
¿Demasiados anuncios?
Para $n=1, 2$ la respuesta es "sí" dado que el grupo es prácticamente libre, para $n\ge 3$ no se conoce la respuesta (un problema abierto).
Edit. De hecho, incluso para dos $n\times n$-matrices el problema está abierta. Además, la solución de los siguientes `más fácil" el problema es que no se conoce: para que algebraicas de los números enteros $\lambda$ las matrices $\left(\begin{array}{ll} 1 & 2\\\ 0 & 1 \end{array}\right)$ e $\left(\begin{array}{ll} 1 & 0\\\ \lambda & 1 \end{array}\right)$ generar un grupo libre (ver este papel, por ejemplo). El hecho de que este problema es más fácil de lo que sigue de la observación trivial de que el grupo generado por estas dos matrices es isomorfo a algunos efectivamente computable grupo de $n\times n$-entero matrices para algunos $n\ge 2$ (dependiendo del grado de la algebraicas número $\lambda$).
Guy
Puntos
16718
Aquí están algunos hechos generales que pueden ser relevantes.
Dado un finitely presentó el grupo de $G$ y una representación $\rho:G\to GL_n(\mathbb{Z})$, no existe ningún algoritmo que es uniforme en $n$ que decide si o no $\rho$ es inyectiva.
Sin embargo, esto deja abierta la posibilidad de que existe un algoritmo para el particular $n$. (Es fácil para $n=2$, cuando el grupo es prácticamente libre. Creo que nada es conocido por $n>2$.) También, los ejemplos que construimos no son libres de grupos, por lo que es posible decir algo en ese caso.
En otra dirección, un número finito de presentación para un grupo de $G$ y una solución al problema de palabras en $G$, uno mediante algoritmos puede determinar si es o no $G$ es un grupo libre.
Neil
Puntos
6
Algunos comentarios sobre la pregunta '¿Es decidable si es o no un colección de enteros matrices genera un grupo libre?'
Dado un conjunto finito de matrices S sobre un campo, el problema de probando si el grupo H generado por S contiene un libre no abelian subgrupo es decidable. Un algoritmo de resolución de la problema así como su aplicación (en Magma) disponible. Aviso que los algoritmos no la construcción de un aparcamiento no abelian subgrupo en H, pero se justifica su existencia. En cuanto a las pruebas, libertad de finitely generado lineal de grupos, entonces el problema tiene una muy larga historia. Me puede recomendar como un punto de inicio en el papel de John Dixon Puede.J Matemáticas, v. 37, n. 2, 1985, 238-259 (ver pág. 240 allí, y luego siga las referencias).
