Problema de palabras para grupos

Problema en la teoría de grupos finitos

En matemáticas , especialmente en el área del álgebra abstracta conocida como teoría de grupos combinatorios , el problema verbal para un grupo finitamente generado es el problema algorítmico de decidir si dos palabras en los generadores representan el mismo elemento de . El problema verbal es un ejemplo bien conocido de un problema indecidible . ${\displaystyle G}$ ${\displaystyle G}$

Si es un conjunto finito de generadores para , entonces el problema verbal es el problema de pertenencia para el lenguaje formal de todas las palabras en y un conjunto formal de inversas que se asignan a la identidad bajo el mapa natural del monoide libre con involución en el grupo . Si es otro conjunto generador finito para , entonces el problema verbal sobre el conjunto generador es equivalente al problema verbal sobre el conjunto generador . Por lo tanto, se puede hablar inequívocamente de la decidibilidad del problema verbal para el grupo finitamente generado . ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle B}$ ${\displaystyle G}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle G}$

El problema de palabras uniforme relacionado pero diferente para una clase de grupos presentados recursivamente es el problema algorítmico de decidir, dada como entrada una presentación para un grupo en la clase y dos palabras en los generadores de , si las palabras representan el mismo elemento de . Algunos autores requieren que la clase sea definible por un conjunto de presentaciones recursivamente enumerables . ${\displaystyle K}$ ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle K}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle K}$

Historia

A lo largo de la historia de la materia, los cálculos en grupos se han llevado a cabo utilizando varias formas normales . Estas suelen resolver implícitamente el problema de palabras para los grupos en cuestión. En 1911, Max Dehn propuso que el problema de palabras era un área de estudio importante por derecho propio, ^[1] junto con el problema de conjugación y el problema de isomorfismo de grupos . En 1912, presentó un algoritmo que resuelve tanto el problema de palabras como el de conjugación para los grupos fundamentales de variedades bidimensionales orientables cerradas de género mayor o igual a 2. ^[2] Los autores posteriores han ampliado en gran medida el algoritmo de Dehn y lo han aplicado a una amplia gama de problemas de decisión teóricos de grupos . ^{[3] [4] [5]}

Pyotr Novikov demostró en 1955 que existe un grupo finito tal que el problema verbal para es indecidible . ^{[6] De ello se deduce inmediatamente que el problema verbal uniforme también es indecidible.} William Boone obtuvo una prueba diferente en 1958. ^[7] ${\displaystyle G}$ ${\displaystyle G}$

El problema de las palabras fue uno de los primeros ejemplos de un problema irresoluble que no se encuentra en la lógica matemática ni en la teoría de algoritmos , sino en una de las ramas centrales de las matemáticas clásicas, el álgebra . Como resultado de su imposibilidad de solución, se ha demostrado que varios otros problemas de la teoría combinatoria de grupos también son irresolubles.

El problema verbal es, de hecho, solucionable para muchos grupos . Por ejemplo, los grupos policíclicos tienen problemas verbales solucionables, ya que la forma normal de una palabra arbitraria en una presentación policíclica es fácilmente computable; otros algoritmos para grupos pueden, en circunstancias adecuadas, también resolver el problema verbal, véase el algoritmo de Todd-Coxeter ^[8] y el algoritmo de compleción de Knuth-Bendix . ^[9] Por otro lado, el hecho de que un algoritmo particular no resuelva el problema verbal para un grupo particular no muestra que el grupo tenga un problema verbal irresoluble. Por ejemplo, el algoritmo de Dehn no resuelve el problema verbal para el grupo fundamental del toro . Sin embargo, este grupo es el producto directo de dos grupos cíclicos infinitos y, por lo tanto, tiene un problema verbal solucionable. ${\displaystyle G}$

Una descripción más concreta

En términos más concretos, el problema de palabras uniforme puede expresarse como una pregunta de reescritura , para cadenas literales . ^[10] Para una presentación de un grupo , se especificará un cierto número de generadores. ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle P}$

${\displaystyle x,y,z,\ldots }$

para . Necesitamos introducir una letra para y otra (por conveniencia) para el elemento del grupo representado por . Llamemos a estas letras (el doble de las que hay en los generadores) el alfabeto de nuestro problema. Luego, cada elemento en se representa de alguna manera mediante un producto ${\displaystyle G}$ ${\displaystyle x}$ ${\displaystyle x^{-1}}$ ${\displaystyle \Sigma }$ ${\displaystyle G}$

${\displaystyle abc...pqr}$

de símbolos de , de cierta longitud, multiplicados por . La cadena de longitud 0 ( cadena nula ) representa el elemento identidad de . El quid de todo el problema es poder reconocer todas las formas en que se pueden representar, dadas algunas relaciones. ${\displaystyle \Sigma }$ ${\displaystyle G}$ ${\displaystyle e}$ ${\displaystyle G}$ ${\displaystyle e}$

El efecto de las relaciones en es hacer que varias de estas cadenas representen el mismo elemento de . De hecho, las relaciones proporcionan una lista de cadenas que pueden introducirse donde queramos o cancelarse cuando las veamos, sin cambiar el "valor", es decir, el elemento del grupo que es el resultado de la multiplicación. ${\displaystyle G}$ ${\displaystyle G}$

Para un ejemplo simple, considere el grupo dado por la presentación . Escribiendo para la inversa de , tenemos posibles cadenas que combinan cualquier número de los símbolos y . Siempre que veamos , o o podemos eliminarlos. También debemos recordar eliminar ; esto dice que como el cubo de es el elemento identidad de , también lo es el cubo de la inversa de . Bajo estas condiciones, el problema verbal se vuelve fácil. Primero reduzca las cadenas a la cadena vacía, , o . Luego observe que también podemos multiplicar por , por lo que podemos convertir a y convertir a . El resultado es que el problema verbal, aquí para el grupo cíclico de orden tres, es solucionable. ${\displaystyle \langle a\,|\,a^{3}=e\rangle }$ ${\displaystyle A}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle A}$ ${\displaystyle aaa}$ ${\displaystyle aA}$ ${\displaystyle Aa}$ ${\displaystyle AAA}$ ${\displaystyle a}$ ${\displaystyle G}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle aa}$ ${\displaystyle A}$ ${\displaystyle AA}$ ${\displaystyle aaa}$ ${\displaystyle A}$ ${\displaystyle aa}$ ${\displaystyle AA}$ ${\displaystyle a}$

Sin embargo, este no es el caso típico. Para el ejemplo, tenemos una forma canónica disponible que reduce cualquier cadena a una de longitud de tres como máximo, disminuyendo la longitud de manera monótona. En general, no es cierto que se pueda obtener una forma canónica para los elementos mediante la cancelación gradual. Es posible que haya que usar relaciones para expandir una cadena muchas veces, con el fin de encontrar finalmente una cancelación que reduzca la longitud.

El resultado es que, en el peor de los casos, la relación entre cadenas que dice que son iguales es un problema indecidible . ${\displaystyle G}$

Ejemplos

Los siguientes grupos tienen un problema de palabras solucionable:

• Grupos automáticos , incluidos:
  • Grupos finitos
  • Grupos de curvatura negativa (también conocidos como hiperbólicos)
  • Grupos euclidianos
  • Grupos de Coxeter
  • Grupos de trenzas
  • Grupos geométricamente finitos
• Grupos libres generados de forma finita
• Grupos abelianos libres finitamente generados
• Grupos policíclicos
• Grupos presentados de forma recursiva y absolutamente generada de forma finita , ^[11] incluyendo:
  • Grupos simples finitamente presentados.
• Grupos finitos residuales presentados de forma finita
• Un grupo de relatores ^[12] (este es un teorema de Magnus), incluye:
  • Grupos fundamentales de variedades bidimensionales cerradas orientables.
• Grupos combinables
• Grupos autoapilables

También se conocen ejemplos con problemas de palabras irresolubles:

• Dado un conjunto recursivamente enumerable de números enteros positivos que tiene un problema de pertenencia insoluble, es un grupo finitamente generado con una presentación recursivamente enumerable cuyo problema de palabras es insoluble ^[13] ${\displaystyle A}$ ${\displaystyle \langle a,b,c,d\,|\,a^{n}ba^{n}=c^{n}dc^{n}:n\in A\rangle }$
• Todo grupo finitamente generado con una presentación recursivamente enumerable y un problema verbal insoluble es un subgrupo de un grupo finitamente presentado con un problema verbal insoluble ^[14]
• El número de relatores en un grupo finitamente presentado con un problema de palabras insoluble puede ser tan bajo como 14 ^[15] o incluso 12. ^{[16] [17]}
• En Collins 1986 se da un ejemplo explícito de una presentación breve y razonable con un problema de palabras insoluble: ^{[18] [19]}

${\displaystyle {\begin{array}{lllll}\langle &a,b,c,d,e,p,q,r,t,k&|&&\\&p^{10}a=ap,&pacqr=rpcaq,&ra=ar,&\\&p^{10}b=bp,&p^{2}adq^{2}r=rp^{2}daq^{2},&rb=br,&\\&p^{10}c=cp,&p^{3}bcq^{3}r=rp^{3}cbq^{3},&rc=cr,&\\&p^{10}d=dp,&p^{4}bdq^{4}r=rp^{4}dbq^{4},&rd=dr,&\\&p^{10}e=ep,&p^{5}ceq^{5}r=rp^{5}ecaq^{5},&re=er,&\\&aq^{10}=qa,&p^{6}deq^{6}r=rp^{6}edbq^{6},&pt=tp,&\\&bq^{10}=qb,&p^{7}cdcq^{7}r=rp^{7}cdceq^{7},&qt=tq,&\\&cq^{10}=qc,&p^{8}ca^{3}q^{8}r=rp^{8}a^{3}q^{8},&&\\&dq^{10}=qd,&p^{9}da^{3}q^{9}r=rp^{9}a^{3}q^{9},&&\\&eq^{10}=qe,&a^{-3}ta^{3}k=ka^{-3}ta^{3}&&\rangle \end{array}}}$

Solución parcial del problema de palabras

El problema de palabras para un grupo presentado recursivamente se puede resolver parcialmente en el siguiente sentido:

Dada una presentación recursiva para un grupo , defina: ${\displaystyle P=\langle X\,|\,R\rangle }$ ${\displaystyle G}$

${\displaystyle S=\{\langle u,v\rangle :u{\text{ and }}v{\text{ are words in }}X{\text{ and }}u=v{\text{ in }}G\ \}}$

entonces existe una función recursiva parcial tal que: ${\displaystyle f_{P}}$

${\displaystyle f_{P}(\langle u,v\rangle )={\begin{cases}0&{\text{if}}\ \langle u,v\rangle \in S\\{\text{undefined/does not halt}}\ &{\text{if}}\ \langle u,v\rangle \notin S\end{cases}}}$

De manera más informal, existe un algoritmo que se detiene si , pero no lo hace en caso contrario. ${\displaystyle u=v}$

De ello se deduce que para resolver el problema de palabras es suficiente construir una función recursiva tal que: ${\displaystyle P}$ ${\displaystyle g}$

${\displaystyle g(\langle u,v\rangle )={\begin{cases}0&{\text{if}}\ \langle u,v\rangle \notin S\\{\text{undefined/does not halt}}\ &{\text{if}}\ \langle u,v\rangle \in S\end{cases}}}$

Sin embargo, en si y solo si en . De ello se deduce que para resolver el problema de palabras es suficiente construir una función recursiva tal que: ${\displaystyle u=v}$ ${\displaystyle G}$ ${\displaystyle uv^{-1}=1}$ ${\displaystyle G}$ ${\displaystyle P}$ ${\displaystyle h}$

${\displaystyle h(x)={\begin{cases}0&{\text{if}}\ x\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ x=1\ {\text{in}}\ G\end{cases}}}$

Ejemplo

A continuación se demostrará como ejemplo del uso de esta técnica:

Teorema: Un grupo finito de residuos presentado finitamente tiene un problema verbal solucionable.

Prueba: Supongamos que es un grupo residualmente finito y finitamente presentado. ${\displaystyle G=\langle X\,|\,R\rangle }$

Sea el grupo de todas las permutaciones de los números naturales que fija todos los números excepto un número finito. Entonces: ${\displaystyle S}$ ${\displaystyle \mathbb {N} }$

1. ${\displaystyle S}$es localmente finito y contiene una copia de cada grupo finito.
2. El problema de palabras se puede resolver calculando productos de permutaciones. ${\displaystyle S}$
3. Hay una enumeración recursiva de todas las asignaciones del conjunto finito en . ${\displaystyle X}$ ${\displaystyle S}$
4. Dado que es residualmente finito, si es una palabra en los generadores de entonces en si y sólo si alguna aplicación de en induce un homomorfismo tal que en . ${\displaystyle G}$ ${\displaystyle w}$ ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle w\neq 1}$ ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle S}$ ${\displaystyle w\neq 1}$ ${\displaystyle S}$

Dados estos hechos, el algoritmo queda definido por el siguiente pseudocódigo:

Para cada mapeo de X en S Si cada relator en R se satisface en S Si w ≠ 1 en S retorna 0 Fin si  Fin si Fin para

define una función recursiva tal que: ${\displaystyle h}$

${\displaystyle h(x)={\begin{cases}0&{\text{if}}\ x\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ x=1\ {\text{in}}\ G\end{cases}}}$

Esto demuestra que el problema tiene solución. ${\displaystyle G}$

Insolubilidad del problema de palabras uniformes

El criterio dado anteriormente para la resolubilidad del problema verbal en un solo grupo se puede extender mediante un argumento sencillo. Esto da el siguiente criterio para la resolubilidad uniforme del problema verbal para una clase de grupos finitos:

Para resolver el problema de palabras uniforme para una clase de grupos, es suficiente encontrar una función recursiva ⁠ ⁠ que tome una presentación finita para un grupo y una palabra ⁠ ⁠ en los generadores de , tal que siempre que : ${\displaystyle K}$ ${\displaystyle f(P,w)}$ ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle w}$ ${\displaystyle G}$ ${\displaystyle G\in K}$

${\displaystyle f(P,w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ G\end{cases}}}$

Teorema de Boone-Rogers: No existe un algoritmo parcial uniforme que resuelva el problema verbal en todos los grupos finitamente presentados con problemas verbales solucionables.

En otras palabras, el problema verbal uniforme para la clase de todos los grupos finitamente presentados con problemas verbales resolubles es irresoluble. Esto tiene algunas consecuencias interesantes. Por ejemplo, el teorema de incrustación de Higman se puede utilizar para construir un grupo que contenga una copia isomorfa de cada grupo finitamente presentado con problemas verbales resolubles. Parece natural preguntarse si este grupo puede tener problemas verbales resolubles. Pero es una consecuencia del resultado de Boone-Rogers que:

Corolario: No existe un grupo universal de problemas verbales que se puedan resolver. Es decir, si es un grupo finitamente presentado que contiene una copia isomorfa de cada grupo finitamente presentado con problemas verbales que se puedan resolver, entonces él mismo debe tener problemas verbales que no se puedan resolver. ${\displaystyle G}$ ${\displaystyle G}$

Observación: Supongamos que es un grupo finitamente presentado con un problema verbal solucionable y es un subconjunto finito de . Sea , el grupo generado por . Entonces el problema verbal en es solucionable: dadas dos palabras en los generadores de , escríbalas como palabras en y compárelas usando la solución al problema verbal en . Es fácil pensar que esto demuestra una solución uniforme del problema verbal para la clase (digamos) de grupos finitamente generados que pueden incrustarse en . Si este fuera el caso, la no existencia de un grupo universal solucionable de problema verbal se seguiría fácilmente de Boone-Rogers. Sin embargo, la solución que se acaba de exhibir para el problema verbal para los grupos en no es uniforme. Para ver esto, considere un grupo ; para usar el argumento anterior para resolver el problema verbal en , primero es necesario exhibir una aplicación que se extienda a una incrustación . Si hubiera una función recursiva que mapeara representaciones (finitamente generadas) de grupos en a incrustaciones en , entonces podría construirse una solución uniforme del problema verbal en . Pero no hay razón, en general, para suponer que exista tal función recursiva. Sin embargo, resulta que, usando un argumento más sofisticado, el problema verbal en puede resolverse sin usar una incrustación . En cambio, se usa una enumeración de homomorfismos y, dado que tal enumeración puede construirse de manera uniforme, da como resultado una solución uniforme al problema verbal en . ${\displaystyle G=\langle X\,|\,R\rangle }$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H^{*}=\langle H\rangle }$ ${\displaystyle H}$ ${\displaystyle H^{*}}$ ${\displaystyle h,k}$ ${\displaystyle H}$ ${\displaystyle H^{*}}$ ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle K}$ ${\displaystyle G}$ ${\displaystyle K}$ ${\displaystyle J=\langle Y\,|\,T\rangle \in K}$ ${\displaystyle J}$ ${\displaystyle e:Y\to G}$ ${\displaystyle e^{*}:J\to G}$ ${\displaystyle K}$ ${\displaystyle G}$ ${\displaystyle K}$ ${\displaystyle J}$ ${\displaystyle e:J\to G}$ ${\displaystyle K}$

Prueba de que no existe un grupo de problemas de palabras que se puedan resolver de manera universal

Supongamos que se trata de un grupo de problemas verbales universalmente solucionables. Dada una presentación finita de un grupo , se pueden enumerar recursivamente todos los homomorfismos enumerando primero todas las aplicaciones . No todas estas aplicaciones se extienden a homomorfismos, pero, dado que es finito, es posible distinguir entre homomorfismos y no homomorfismos, utilizando la solución del problema verbal en . "Eliminar" los no homomorfismos da la enumeración recursiva requerida: . ${\displaystyle G}$ ${\displaystyle P=\langle X\,|\,R\rangle }$ ${\displaystyle H}$ ${\displaystyle h:H\to G}$ ${\displaystyle h^{\dagger }:X\to G}$ ${\displaystyle h^{\dagger }(R)}$ ${\displaystyle G}$ ${\displaystyle h_{1},h_{2},\ldots ,h_{n},\ldots }$

Si tiene un problema de palabras solucionable, entonces al menos uno de estos homomorfismos debe ser una incrustación. Por lo tanto, dada una palabra en los generadores de : ${\displaystyle H}$ ${\displaystyle w}$ ${\displaystyle H}$

${\displaystyle {\text{If}}\ w\neq 1\ {\text{in}}\ H,\ h_{n}(w)\neq 1\ {\text{in}}\ G\ {\text{for some}}\ h_{n}}$

${\displaystyle {\text{If}}\ w=1\ {\text{in}}\ H,\ h_{n}(w)=1\ {\text{in}}\ G\ {\text{for all}}\ h_{n}}$

Consideremos el algoritmo descrito por el pseudocódigo:

Sea  n = 0 Sea  repetible = VERDADERO mientras ( repetible ) aumenta n en 1 si (la solución al problema verbal en G revela que h n ( w ) ≠ 1 en G ) Sea  repetible = FALSOsalida 0.

Esto describe una función recursiva:

${\displaystyle f(w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ H\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ H.\end{cases}}}$

La función depende claramente de la presentación . Considerando que es una función de las dos variables, se ha construido una función recursiva ⁠ ⁠ que toma una presentación finita para un grupo y una palabra en los generadores de un grupo , tal que siempre que tenga un problema de palabras soluble: ${\displaystyle f}$ ${\displaystyle P}$ ${\displaystyle f(P,w)}$ ${\displaystyle P}$ ${\displaystyle H}$ ${\displaystyle w}$ ${\displaystyle G}$ ${\displaystyle G}$

${\displaystyle f(P,w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ H\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ H.\end{cases}}}$

Pero esto resuelve uniformemente el problema verbal para la clase de todos los grupos finitos presentados con problemas verbales solucionables, contradiciendo a Boone-Rogers. Esta contradicción demuestra que no puede existir. ${\displaystyle G}$

Estructura algebraica y el problema de palabras

Existen varios resultados que relacionan la resolubilidad del problema verbal con la estructura algebraica. El más significativo de ellos es el teorema de Boone-Higman:

Un grupo presentado finitamente tiene un problema verbal solucionable si y sólo si puede incluirse en un grupo simple que puede incluirse en un grupo presentado finitamente.

Se cree ampliamente que debería ser posible realizar la construcción de modo que el grupo simple en sí mismo se presente de manera finita. Si así fuera, cabría esperar que fuera difícil demostrarlo, ya que la aplicación de las presentaciones a los grupos simples tendría que ser no recursiva.

Bernhard Neumann y Angus Macintyre han demostrado lo siguiente :

Un grupo finitamente presentado tiene un problema verbal solucionable si y sólo si puede incluirse en cada grupo algebraicamente cerrado .

Lo notable de esto es que los grupos algebraicamente cerrados son tan salvajes que ninguno de ellos tiene una presentación recursiva.

El resultado más antiguo que relaciona la estructura algebraica con la resolubilidad del problema verbal es el teorema de Kuznetsov:

Un grupo simple presentado de forma recursiva tiene un problema de palabras solucionable. ${\displaystyle S}$

Para demostrar esto, supongamos que se trata de una presentación recursiva para . Elijamos un elemento no identidad , es decir, en . ${\displaystyle \langle X|R\rangle }$ ${\displaystyle S}$ ${\displaystyle a\in S}$ ${\displaystyle a\neq 1}$ ${\displaystyle S}$

Si es una palabra en los generadores de , entonces sea: ${\displaystyle w}$ ${\displaystyle X}$ ${\displaystyle S}$

${\displaystyle S_{w}=\langle X|R\cup \{w\}\rangle .}$

Existe una función recursiva tal que: ${\displaystyle f_{\langle X|R\cup \{w\}\rangle }}$

${\displaystyle f_{\langle X|R\cup \{w\}\rangle }(x)={\begin{cases}0&{\text{if}}\ x=1\ {\text{in}}\ S_{w}\\{\text{undefined/does not halt}}\ &{\text{if}}\ x\neq 1\ {\text{in}}\ S_{w}.\end{cases}}}$

Escribir:

${\displaystyle g(w,x)=f_{\langle X|R\cup \{w\}\rangle }(x).}$

Entonces, como la construcción de fue uniforme, esta es una función recursiva de dos variables. ${\displaystyle f}$

De ello se deduce que: ⁠ ⁠ ${\displaystyle h(w)=g(w,a)}$ es recursiva. Por construcción:

${\displaystyle h(w)={\begin{cases}0&{\text{if}}\ a=1\ {\text{in}}\ S_{w}\\{\text{undefined/does not halt}}\ &{\text{if}}\ a\neq 1\ {\text{in}}\ S_{w}.\end{cases}}}$

Como es un grupo simple, sus únicos grupos cocientes son él mismo y el grupo trivial. Como en , vemos que en si y solo si es trivial si y solo si en . Por lo tanto: ${\displaystyle S}$ ${\displaystyle a\neq 1}$ ${\displaystyle S}$ ${\displaystyle a=1}$ ${\displaystyle S_{w}}$ ${\displaystyle S_{w}}$ ${\displaystyle w\neq 1}$ ${\displaystyle S}$

${\displaystyle h(w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ S\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ S.\end{cases}}}$

La existencia de tal función es suficiente para demostrar que el problema verbal se puede resolver para . ${\displaystyle S}$

Esta prueba no prueba la existencia de un algoritmo uniforme para resolver el problema verbal para esta clase de grupos. La falta de uniformidad reside en elegir un elemento no trivial del grupo simple. No hay razón para suponer que exista una función recursiva que asigne una presentación de un grupo simple a un elemento no trivial del grupo. Sin embargo, en el caso de un grupo finitamente presentado, sabemos que no todos los generadores pueden ser triviales (cualquier generador individual podría serlo, por supuesto). Utilizando este hecho, es posible modificar la prueba para mostrar:

El problema de palabras es uniformemente solucionable para la clase de grupos simples finitamente presentados.

Véase también

• Combinatoria sobre palabras
• Grupo universal SQ
• Problema de palabras (matemáticas)
• Problema de accesibilidad
• Autómatas de pila anidada (se han utilizado para resolver el problema de palabras para grupos)

Notas

1. Dehn 1911.
2. Dehn 1912.
3. Greendlinger, Martin (junio de 1959), "Algoritmo de Dehn para el problema de palabras", Communications on Pure and Applied Mathematics , 13 (1): 67–83, doi :10.1002/cpa.3160130108.
4. Lyndon, Roger C. (septiembre de 1966), "Sobre el algoritmo de Dehn", Mathematische Annalen , 166 (3): 208–228, doi :10.1007/BF01361168, hdl : 2027.42/46211 , S2CID  36469569.
5. Schupp, Paul E. (junio de 1968), "Sobre el algoritmo de Dehn y el problema de la conjugación", Mathematische Annalen , 178 (2): 119–130, doi :10.1007/BF01350654, S2CID  120429853.
6. Novikov, PS (1955), "Sobre la insolubilidad algorítmica del problema verbal en la teoría de grupos", Actas del Instituto Steklov de Matemáticas (en ruso), 44 : 1–143, Zbl  0068.01301
7. Boone, William W. (1958), "El problema de las palabras" (PDF) , Actas de la Academia Nacional de Ciencias , 44 (10): 1061–1065, Bibcode :1958PNAS...44.1061B, doi : 10.1073/pnas.44.10.1061 , PMC 528693 , PMID  16590307, ​​Zbl  0086.24701 
8. Todd, J.; Coxeter, HSM (1936). "Un método práctico para enumerar clases laterales de un grupo abstracto finito". Actas de la Sociedad Matemática de Edimburgo . 5 (1): 26–34. doi : 10.1017/S0013091500008221 .
9. Knuth, D.; Bendix, P. (2014) [1970]. "Problemas verbales simples en álgebras universales". En Leech, J. (ed.). Problemas computacionales en álgebra abstracta: actas de una conferencia celebrada en Oxford bajo los auspicios del Consejo de investigación científica Atlas Computer Laboratory, del 29 de agosto al 2 de septiembre de 1967. Springer. págs. 263–297. ISBN 9781483159423.
10. Rotman 1994.
11. Simmons, H. (1973). "El problema de las palabras para presentaciones absolutas". J. London Math. Soc . s2-6 (2): 275–280. doi :10.1112/jlms/s2-6.2.275.
12. Lyndon, Roger C.; Schupp, Paul E (2001). Teoría combinatoria de grupos. Saltador. págs. 1–60. ISBN 9783540411581.
13. Collins y Zieschang 1990, pág. 149.
14. Collins y Zieschang 1993, Cor. 7.2.6. sfn error: no target: CITEREFCollinsZieschang1993 (help)
15. Collins 1969.
16. Borisov 1969.
17. Collins 1972.
18. Collins 1986.
19. Utilizamos la versión corregida del Catálogo de sistemas algebraicos de John Pedersen.

Referencias

• Boone, WW; Cannonito, FB; Lyndon, Roger C. (1973). Problemas de palabras: problemas de decisión y el problema de Burnside en la teoría de grupos. Estudios de lógica y fundamentos de las matemáticas. Vol. 71. North-Holland. ISBN 9780720422719.
• Boone, WW; Higman, G. (1974). "Una caracterización algebraica de la resolubilidad del problema verbal". J. Austral. Math. Soc . 18 : 41–53. doi : 10.1017/s1446788700019108 .
• Boone, WW; Rogers Jr, H. (1966). "Sobre un problema de JHC Whitehead y un problema de Alonzo Church". Math. Scand . 19 : 185–192. doi : 10.7146/math.scand.a-10808 .
• Borisov, VV (1969), "Ejemplos simples de grupos con problemas verbales sin solución", Akademiya Nauk SSSR. Matematicheskie Zametki , 6 : 521–532, ISSN  0025-567X, SEÑOR  0260851
• Collins, Donald J. (1969), "Problemas de palabras y conjugación en grupos con sólo unas pocas relaciones definitorias", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 15 (20–22): 305–324, doi :10.1002/malq. 19690152001, señor  0263903
• Collins, Donald J. (1972), "Sobre el teorema de incrustación de grupos de V. V. Borisov", Boletín de la Sociedad Matemática de Londres , 4 (2): 145–147, doi :10.1112/blms/4.2.145, ISSN  0024-6093, MR  0314998
• Collins, Donald J. (1986), "Una presentación simple de un grupo con un problema verbal irresoluble", Illinois Journal of Mathematics , 30 (2): 230–234, doi : 10.1215/ijm/1256044631 , ISSN  0019-2082, MR  0840121
• Collins, Donald J.; Zieschang, H. (1990), Teoría de grupos combinatorios y grupos fundamentales , Springer-Verlag , pág. 166, MR  1099152
• Dehn, Max (1911), "Über unendliche diskontinuierliche Gruppen", Mathematische Annalen , 71 (1): 116–144, doi :10.1007/BF01456932, ISSN  0025-5831, MR  1511645, S2CID  123478582
• Dehn, Max (1912), "Transformation der Kurven auf zweiseitigen Flächen", Mathematische Annalen , 72 (3): 413–421, doi :10.1007/BF01456725, ISSN  0025-5831, MR  1511705, S2CID  122988176
• Kuznetsov, AV (1958). "Algoritmos como operaciones en sistemas algebraicos". Izvestia Akád. Nauk SSSR Ser Mat . 13 (3): 81.
• Miller, CF (1991). "Problemas de decisión para grupos: estudio y reflexiones". Algoritmos y clasificación en teoría combinatoria de grupos . Publicaciones del Instituto de Investigación en Ciencias Matemáticas. Vol. 23. Springer. págs. 1–60. doi :10.1007/978-1-4613-9730-4_1. ISBN 978-1-4613-9730-4.
• Nyberg-Brodda, Carl-Fredrik (2021), "El problema de las palabras para los monoides de una relación: una encuesta", Semigroup Forum , 103 (2): 297–355, arXiv : 2105.02853 , doi : 10.1007/s00233-021-10216-8
• Rotman, Joseph (1994), Introducción a la teoría de grupos , Springer-Verlag , ISBN 978-0-387-94285-8
• Stillwell, J. (1982). "El problema de las palabras y el problema del isomorfismo para grupos". Boletín de la AMS . 6 : 33–56. doi : 10.1090/s0273-0979-1982-14963-1 .