Algoritmo para el sistema de raíces del grupo de Coxeter generado por permutaciones

Question

Supongamos que nos dan un grupo $G$ en términos de generadores $t_1, ..., t_n$ que son de orden 2 en $S_m$ (sin embargo no suponemos nada más que estos elementos generan $G$ y tienen orden 2). Cuál es la forma más eficiente de determinar:

1. Si $G$ es abstractamente isomorfo a un grupo Coxeter
2. Suponiendo que sí, un sistema Coxeter para $G$
3. Suponiendo que no, una presentación de $G$ como cociente de un grupo Coxeter

Answer 1

Hay una respuesta teórica (en contraposición a una respuesta algorítmica) en "Combinatorics of Coxeter groups" de Björner y Brenti, sección 1.5. (Parece que dan crédito a Matsumoto por su teorema 1.5.1). (Su teorema 1.5.1 es el siguiente:

Supongamos que $W$ es un grupo generado por un subconjunto $S$ formado por elementos de orden $2$ . Entonces TFAE:

1. $(W,S)$ es un sistema Coxeter (es decir $S$ genera $W$ como grupo Coxeter)
2. $(W,S)$ tiene la Propiedad de Intercambio.
3. $(W,S)$ tiene la propiedad de borrado.

Se trata de propiedades escritas en términos de palabras reducidas.

Para hablar de un algoritmo real, necesitamos un significado preciso de la suposición de que "se nos da un grupo ". $G$ en términos de generadores $t_1,\ldots,t_n$ ". La única interpretación razonable que le encuentro es que tenemos un oráculo que te dice si dos palabras de los generadores representan el mismo elemento.

En principio, podría diseñar un algoritmo "parcial", comprobando el Intercambio o el Borrado. Pero si tu grupo es infinito, podría ejecutarse eternamente, y nunca sabrías si tu algoritmo está a punto de dar con un contraejemplo al Intercambio o al Borrado.

EDIT: Ahora que me he dado cuenta de que la pregunta especifica que todo esto tiene lugar dentro de algún grupo simétrico $S_m$ : El grupo $G$ es finito, por lo que hay finitamente muchas palabras reducidas, y la Propiedad de Intercambio se puede comprobar en tiempo finito.

Answer 2

No creo que esto sea lo que el autor de la pregunta quiere decir, así que esto no es realmente una respuesta. Pero vale la pena mencionarlo y es demasiado largo para un comentario.

Si sabemos que $t_1,\ldots,t_n$ son transposiciones, entonces $G$ es un "subgrupo de reflexión" de $S_m$ (un subgrupo generado por reflexiones). Entonces un teorema de Deodhar ("A note on subgroups generated by reflections in Coxeter groups") y Dyer ("Reflection subgroups of Coxeter systems") nos dice que $G$ es un grupo Coxeter. También dan una receta para encontrar un sistema simple: Encontrar todas las transposiciones en $G$ y hallar las raíces positivas correspondientes. De todas estas raíces positivas, hallar el único subconjunto mínimo tal que todas las raíces positivas estén en el tramo no negativo del subconjunto. Las transposiciones para ese subconjunto son el sistema simple.

En este caso, $G$ será un producto de grupos simétricos.