Problema verbal para grupos

En matemáticas, especialmente en el área del álgebra abstracta conocida como teoría de grupos combinatoria, el problema de palabras para un grupo finitamente generado G es el problema algorítmico de decidir si dos las palabras en los generadores representan el mismo elemento. Más precisamente, si A es un conjunto finito de generadores para G entonces el problema de palabras es el problema de membresía para el lenguaje formal de todas las palabras en A y un conjunto formal de inversos que mapean a la identidad bajo el mapa natural del monoide libre con involución en A al grupo G. Si B es otro conjunto generador finito para G, entonces el problema verbal sobre el conjunto generador B es equivalente al problema verbal sobre el conjunto generador A. Por lo tanto, se puede hablar sin ambigüedades de la decidibilidad del problema verbal para el grupo G generado finitamente.

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

Historia

A lo largo de la historia del tema, los cálculos en grupos se han llevado a cabo utilizando varias formas normales. Estos generalmente resuelven implícitamente el problema verbal para los grupos en cuestión. En 1911, Max Dehn propuso que el problema verbal era un área de estudio importante por derecho propio, junto con el problema de la conjugación y el problema del isomorfismo de grupos. En 1912 dio un algoritmo que resuelve tanto el problema de la palabra como el de la conjugación para los grupos fundamentales de variedades bidimensionales orientables cerradas de género mayor o igual a 2. Los autores posteriores ampliaron en gran medida el algoritmo de Dehn y lo aplicaron a un amplia gama de problemas de decisión de la teoría de grupos.

Pyotr Novikov demostró en 1955 que existe un grupo G finitamente presentado tal que el problema verbal para G es indecidible. De ello se deduce inmediatamente que el problema verbal uniforme también es indecidible. William Boone obtuvo una prueba diferente en 1958.

El problema verbal 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 los algoritmos, sino en una de las ramas centrales de las matemáticas clásicas, el álgebra. Como resultado de su falta de solución, se ha demostrado que varios otros problemas en la teoría de grupos combinatoria también son irresolubles.

Es importante darse cuenta de que el problema verbal es, de hecho, solucionable para muchos grupos G. Por ejemplo, los grupos policíclicos tienen problemas de palabras 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, consulte el algoritmo de Todd-Coxeter y el algoritmo de finalización de Knuth-Bendix. Por otro lado, el hecho de que un algoritmo en particular no resuelva el problema de palabras para un grupo en particular no muestra que el grupo tenga un problema de palabras 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, por lo que tiene un problema verbal solucionable.

Una descripción más concreta

En términos más concretos, el problema verbal uniforme se puede expresar como una pregunta de reescritura, para cadenas literales. Para una presentación P de un grupo G, P especificará un cierto número de generadores

x, Sí., z,...

para G. Tenemos que presentar una carta para x y otro (para comodidad) para el elemento del grupo representado por x⁻¹. Llame a estas letras (twice como los generadores) el alfabeto .. {displaystyle Sigma } para nuestro problema. Luego cada elemento en G está representado en de alguna manera por un producto

abc... pqr

de símbolos de .. {displaystyle Sigma }, de cierta longitud, multiplicado en G. La cadena de longitud 0 (la cadena nula) representa el elemento de identidad e de G. El problema es poder reconocer Todos los caminos e puede ser representado, dadas algunas relaciones.

El efecto de las relaciones en G es hacer que varias cadenas de este tipo representen el mismo elemento de G. De hecho, las relaciones proporcionan una lista de cadenas que se pueden introducir donde queramos o cancelar cuando las veamos, sin cambiar el 'valor', es decir, el elemento del grupo que es el resultado de la multiplicación.

Para un ejemplo simple, tome la presentación {a | a³}. Escribiendo A por el inverso de a, tenemos cadenas posibles que combinan cualquier número de los símbolos a y A. Siempre que veamos aaa, o aA o Aa, podemos tacharlos. También debemos recordar tachar AAA; esto dice que dado que el cubo de a es el elemento de identidad de G, también lo es el cubo de la inversa de a. En estas condiciones, el problema verbal se vuelve fácil. Primero, reduzca las cadenas a la cadena vacía, a, aa, A o AA. Luego tenga en cuenta que también podemos multiplicar por aaa, por lo que podemos convertir A a aa y convertir AA a a. El resultado es que el problema verbal, aquí para el grupo cíclico de orden tres, tiene solución.

Este no es, sin embargo, el caso típico. Para el ejemplo, tenemos una forma canónica disponible que reduce cualquier cadena a una de longitud máxima de tres, al disminuir la longitud de forma monótona. En general, no es cierto que se pueda obtener una forma canónica para los elementos, por cancelación escalonada. Uno puede tener que usar relaciones para expandir una cadena varias veces, para finalmente encontrar una cancelación que reduzca la longitud.

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

Ejemplos

Los siguientes grupos tienen un problema verbal que se puede resolver:

• Grupos automáticos, incluyendo:
  • Grupos finitos
  • Grupos curvados negativamente (aka. hiperbólicos)
  • Grupos eucaclidianos
  • Coxeter groups
  • Grupos de apoyo
  • Grupos geométricos finitos
• Grupos libres generados por finitos
• Generados finitos grupos abelianos libres
• Grupos policíclicos
• Generado de forma selectiva en grupos presentados, incluyendo:
  • Finitely presentó grupos simples.
• Finitely presented residually finite groups
• Grupos de vendedores (este es un teorema de Magnus), incluyendo:
  • Grupos fundamentales de manifolds bidimensionales orientados cerrados.
• Grupos vulnerables
• Grupos autoestables

También se conocen ejemplos con problemas verbales irresolubles:

• Dado un conjunto repetidamente enumerable A de números enteros positivos que tiene problemas de membresía insoluble,a,b,c,d Silencio aⁿbaⁿ = cⁿdcⁿ: n ▪ Aне es un grupo finitamente generado con una presentación repetidamente enumerable cuyo problema de palabra es insoluble
• Cada grupo finitamente generado con una presentación repetidamente enumerable y problema de palabra insoluble es un subgrupo de un grupo presentado finitamente con problema de palabra insoluble
• El número de vendedores en un grupo presentado con problemas de palabras insolubles puede ser tan bajo como 14 o incluso 12.
• Un ejemplo explícito de una breve presentación razonable con problemas de palabras insolubles se da en Collins 1986:

.. a,b,c,d,e,p,q,r,t,kSilenciop10a=ap,pacqr=rpcaq,ra=ar,p10b=bp,p2adq2r=rp2daq2,rb=br,p10c=cp,p3bcq3r=rp3cbq3,rc=cr,p10d=dp,p4bdq4r=rp4dbq4,rd=dr,p10e=ep,p5ceq5r=rp5ecaq5,re=er,aq10=qa,p6deq6r=rp6edbq6,pt=tp,bq10=qb,p7cdcq7r=rp7cdceq7,qt=tq,cq10=qc,p8ca3q8r=rp8a3q8,dq10=qd,p9da3q9r=rp9a3q9,eq10=qe,a− − 3ta3k=ka− − 3ta3.. {displaystyle {begin{lllll}langle {d=b} {3} {8} {8}} {}}

Resolución parcial del problema verbal

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

Dada una presentación recurrente P =XSilencioR♫ Para un grupo G, definir:

S={}.. u,v.. :uyvson palabras enXyu=vdentroG}{displaystyle S={langle u,vrangle:u{text{ and }v{text{ are words in }X{text{ and }u=v{ in }G}}}

entonces hay una función recursiva parcial f_P tal que:

fP().. u,v.. )={}0si.. u,v.. ▪ ▪ Sindefinidos/no se detienensi.. u,v.. ∉ ∉ S{displaystyle f_{P}(langle u,vrangle)={begin{cases}0 limit{text{if} langle u,vrangle in S\{text{undefinido/does not halt} ### {text{if}langle u,vrangle notin Send{cases}}

Más informalmente, hay un algoritmo que se detiene si u=v, pero no lo hace de otra manera.

Se sigue que para resolver el problema verbal para P es suficiente construir una función recursiva g tal que:

g().. u,v.. )={}0si.. u,v.. ∉ ∉ Sindefinidos/no se detienensi.. u,v.. ▪ ▪ S{displaystyle g(langle u,vrangle)={begin{cases}0 {text{if} langle u,vrangle notin S{text{undefinido/does not halt} {text{if}\langle u,vrangle in Send{cases}}

Sin embargo, u=v en G si y solo si uv ⁻¹=1 en G. De ello se deduce que para resolver el problema verbal para P es suficiente construir una función recursiva h tal que:

h()x)={}0sixل ل 1dentroGindefinidos/no se detienensix=1dentroG{displaystyle h(x)={begin{cases}0 {text{if} xneq 1 {text{in} G\{text{undefinido/does not halt} {fnMicrosoft Sans Serif}\fnK}\fnK}\fnK}\fnK}\fn}\fn}\fn}\fn}fn}\fn}\\\fnK}\\\\fnMicrosoft}fn}\\\\fn}fn}\\\fn}fn}\\fn}fn}\\\\\\\fn}\\\fn}\\\\\\\\\fn}\\\\\\\\\\\\fn}\fn}fn}\fn}fn}\\\\\\\fn}\\fn Gend{cases}}

Ejemplo

Se probará lo siguiente como ejemplo del uso de esta técnica:

Teorema: Un grupo finito presentado de forma finita tiene un problema de palabras solvable.

Prueba: Supongamos que G = ⟨X|R⟩ es un grupo residualmente finito presentado finitamente.

Sea S el grupo de todas las permutaciones de N, los números naturales, que fija todos menos un número finito de números:

1. S es localmente finito y contiene una copia de cada grupo finito.
2. El problema de la palabra en S es solvable calculando productos de permutaciones.
3. Hay una enumeración recursiva de todas las cartografías del conjunto finito X en S.
4. Desde G es residualmente finito, si w es una palabra en los generadores X de G entonces w ل dentro G si y sólo de alguna cartografía X en S induce un homomorfismo tal que w ل dentro S.

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

Para cada asignación de X en S
 Si cada vendedor en R está satisfecho en S
 Si w ل 1 en S
 retorno 0
 Fin si Fin siFin

define una función recursiva h tal que:

h()x)={}0sixل ل 1dentroGindefinidos/no se detienensix=1dentroG{displaystyle h(x)={begin{cases}0 {text{if} xneq 1 {text{in} G\{text{undefinido/does not halt} {fnMicrosoft Sans Serif}\fnK}\fnK}\fnK}\fnK}\fn}\fn}\fn}\fn}fn}\fn}\\\fnK}\\\\fnMicrosoft}fn}\\\\fn}fn}\\\fn}fn}\\fn}fn}\\\\\\\fn}\\\fn}\\\\\\\\\fn}\\\\\\\\\\\\fn}\fn}fn}\fn}fn}\\\\\\\fn}\\fn Gend{cases}}

Esto muestra que G tiene un problema verbal solucionable.

Insolubilidad del problema verbal uniforme

El criterio dado anteriormente, para la resolución del problema verbal en un solo grupo, se puede ampliar con un argumento sencillo. Esto da el siguiente criterio para la resolución uniforme del problema verbal para una clase de grupos presentados finitamente:

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

f()P,w)={}0siwل ل 1dentroGindefinidos/no se detienensiw=1dentroG{displaystyle f(P,w)={begin{cases}0 recur{if} ¿Por qué? G\{text{undefinido/does not halt} {fnK} w=1 {text{in} Gend{cases}}

Boone-Rogers Theorem: No hay un algoritmo parcial uniforme que solucione el problema de la palabra en todos los grupos finitos presentado con problema de palabras solvable.

En otras palabras, el problema verbal uniforme para la clase de todos los grupos presentados finitamente con problemas verbales solucionables 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 isomórfica de cada grupo presentado finitamente con un problema verbal solucionable. Parece natural preguntar si este grupo puede tener un problema verbal solucionable. Pero es una consecuencia del resultado de Boone-Rogers que:

Corollario: No hay un grupo universal de problemas de palabras. Eso es, si G es un grupo presentado finitamente que contiene una copia isomorfa de cada grupo presentado finitamente con problema de palabras solvable, entonces G debe tener un problema de palabra insolvable.

Observación: Supongamos que G = ⟨X|R⟩ es un grupo de presentación finita con un problema verbal soluble y H es un subconjunto finito de G. Sea H^* = ⟨H⟩, el grupo generado por H. Entonces el problema verbal en H^* tiene solución: dadas dos palabras h, k en los generadores H de H^*, escríbalas como palabras en X y compárelas usando la solución al problema verbal en G. Es fácil pensar que esto demuestra una solución uniforme del problema verbal para la clase K (digamos) de grupos generados de forma finita que pueden integrarse en G. Si este fuera el caso, la inexistencia de un grupo de problemas verbales solucionables universales se derivaría fácilmente de Boone-Rogers. Sin embargo, la solución que se acaba de mostrar para el problema de palabras para grupos en K no es uniforme. Para ver esto, considere un grupo J = ⟨Y|T⟩ ∈ K; para usar el argumento anterior para resolver el problema verbal en J, primero es necesario exhibir un mapeo e: Y → G que se extiende a un incrustado e^*: J → G. Si hubiera una función recursiva que mapeara (generada finitamente) presentaciones de grupos en K a incrustaciones en G, entonces una solución uniforme del problema verbal en K de hecho podría construirse. Pero no hay razón, en general, para suponer que existe tal función recursiva. Sin embargo, resulta que, usando un argumento más sofisticado, el problema verbal en J se puede resolver sin usar una incrustación e: J → G. En su lugar, se utiliza una enumeración de homomorfismos y, dado que dicha enumeración se puede construir de manera uniforme, da como resultado una solución uniforme al problema verbal en K.

Prueba de que no existe un grupo universal de problemas verbales con solución

Supongamos que G fuera un grupo de problemas verbales con solución universal. Dada una presentación finita P = ⟨X|R⟩ de un grupo H, uno puede enumerar recursivamente todos los homomorfismos h: H → G enumerando primero todas las asignaciones h^†: X → G. No todas estas asignaciones se extienden a los homomorfismos, pero, dado que h^†(R) es finito, es posible distinguir entre homomorfismos y no -homomorfismos, utilizando la solución del problema verbal en G. "Eliminar" no homomorfismos da la enumeración recursiva requerida: h₁, h₂,..., h_n,....

Si H tiene un problema verbal solucionable, entonces al menos uno de estos homomorfismos debe ser una incrustación. Entonces, dada una palabra w en los generadores de H:

Siwل ل 1dentroH,hn()w)ل ل 1dentroGpara algunoshn{displaystyle {text{ If}neq 1 {text{in} ¿Qué? G ' {text{for some} H_{n}

Siw=1dentroH,hn()w)=1dentroGpara todoshn{displaystyle {text {fn}fn}fn}fnh}\fnh}\fn}\fn}\fn}\fn}\fnK}fnfn}\\\fnK}}\\fnKfnKfnK}}}\\\\\\\fnK}}}\\\fnK\\\fnK}}}\\\fnK}}\\\\\\\\\\fnK}\\\\\\\\fn}}}}}}\\\\\fn}}}\\\\\\fn}fn}}}}}}}\\\\\\\fn ¿Qué? G ' {text{for all} H_{n}

Considere el algoritmo descrito por el pseudocódigo:

Vamos n = 0
 Vamos repetible = TRUE
 mientras ()repetible)
aumento n por 1
 si (solución al problema de palabras en G revelaciones hn()w) G)
 Vamos repetible = FALSE
Producto 0.

Esto describe una función recursiva:

f()w)={}0siwل ل 1dentroHindefinidos/no se detienensiw=1dentroH.{displaystyle f(w)={begin{cases}0 limit{text{if} ¿Por qué? H\{text{undefinido/does not halt} {fnK} w=1 {text{in} H.end{cases}}

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

f()P,w)={}0siwل ل 1dentroHindefinidos/no se detienensiw=1dentroH.{displaystyle f(P,w)={begin{cases}0 recur{if} ¿Por qué? H\{text{undefinido/does not halt} {fnK} w=1 {text{in} H.end{cases}}

Pero esto resuelve uniformemente el problema verbal para la clase de todos los grupos presentados de forma finita con problema verbal solucionable, lo que contradice a Boone-Rogers. Esta contradicción prueba que G no puede existir.

Estructura algebraica y problema verbal

Hay una serie de resultados que relacionan la resolución del problema verbal y la estructura algebraica. El más significativo de ellos es el teorema de Boone-Higman:

Un grupo presentado finitamente tiene un problema de palabras solvable si y sólo si puede ser incrustado en un grupo simple que puede ser incrustado en un grupo presentado finitamente.

La creencia generalizada es que debería ser posible hacer la construcción de modo que el grupo simple en sí mismo se presente finitamente. Si es así, se esperaría que fuera difícil de probar, ya que la asignación de presentaciones a grupos simples tendría que ser no recursiva.

Bernhard Neumann y Angus Macintyre han demostrado lo siguiente:

Un grupo presentado finitamente tiene problema de palabra solvable si y sólo si puede ser incrustado 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 solución del problema verbal es el teorema de Kuznetsov:

Un grupo simple presentado recursivamente S tiene problemas de palabras.

Para probar esto, sea ⟨X|R⟩ una presentación recursiva para S. Elige a ∈ S tal que a ≠ 1 en S.

Si w es una palabra sobre los generadores X de S, entonces sea:

Sw=.. XSilencioR∪ ∪ {}w}.. .{displaystyle S_{w}=langle XtenciónRcup {w}rangle.}

Hay una función recursiva f.. XSilencioR∪ ∪ {}w}.. {displaystyle f_{langle X sometidaRcup {w}rangle } tal que:

f.. XSilencioR∪ ∪ {}w}.. ()x)={}0six=1dentroSwindefinidos/no se detienensixل ل 1dentroSw.{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} S_{w}\{text{undefinido/does not halt} ### {text{if} xneq 1\text{in} S_{w}.

Escribe:

g()w,x)=f.. XSilencioR∪ ∪ {}w}.. ()x).{displaystyle g(w,x)=f_{langle X sometidaRcup {w}rangle }(x).}

Entonces, debido a que la construcción de f fue uniforme, esta es una función recursiva de dos variables.

De ahí que: h()w)=g()w,a){displaystyle h(w)=g(w,a)} es recursivo. Por construcción:

h()w)={}0sia=1dentroSwindefinidos/no se detienensiaل ل 1dentroSw.{displaystyle h(w)={begin{cases}0 {text{if} a=1 {text{in} S_{w}\{text{undefinido/does not halt} ¿Qué? S_{w}.

Como S es un grupo simple, sus únicos grupos cocientes son él mismo y el grupo trivial. Como a ≠ 1 en S, vemos a = 1 en S_w si y solo si S_w es trivial si y solo si w ≠ 1 en S. Por lo tanto:

h()w)={}0siwل ل 1dentroSindefinidos/no se detienensiw=1dentroS.{displaystyle h(w)={begin{cases}0 {text{if} ¿Por qué? S\{text{undefinido/does not halt} {fnK} w=1 {text{in} S.end{cases}}

La existencia de tal función es suficiente para probar que el problema verbal se puede resolver para S.

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

El problema de la palabra es uniformemente solvable para la clase de grupos simples finitos.