Algoritmo para reducir palabras en un grupo Coxeter

Question

Dejemos que $W$ sea un grupo Coxeter con un conjunto de reflexiones simples $S$ . Supongamos que he elegido una descomposición reducida preferida para cada elemento de $W$ . Dada una palabra arbitraria del alfabeto $S$ ¿existe un algoritmo para reducir esta palabra a la descomposición que he elegido utilizando las relaciones de Coxeter? Es decir, un algoritmo que en cada paso sustituya una subpalabra de la forma $s_i s_k s_i \dots$ por $s_k s_i s_k \dots$ o que elimine una ocurrencia de $s_k^2$ .

Me gustaría recibir una respuesta en la siguiente situación: $W=\Sigma_n$ es el grupo simétrico en $n$ letras y la descomposición preferida viene dada por tomar la descomposición reducida lexicográficamente más pequeña (o más grande).

Answer 1

En el artículo se describe un algoritmo para reducir palabras arbitrarias de cualquier grupo Coxeter a sus representantes lexicográficamente menos reducidos:

B. Brink y R.B. Howlett, ``Una propiedad de finitud y una estructura automática para grupos Coxeter'', Math. Ann. 296, (1993), 179-190.

No hace exactamente lo que pedías, en el sentido de que no hace las reducciones utilizando sólo las relaciones de Coxeter definitorias, sino que utiliza sustituciones más largas, que por supuesto pueden derivarse de las relaciones definitorias, y son siempre de longitud o lexicográficamente decrecientes. Es el algoritmo de reducción basado en la estructura automática de los grupos Coxeter, y se ejecuta en tiempo cuadrático en general. Se ha implementado (por ejemplo) en el sistema de álgebra computacional Magma.

Answer 2

Sí, al menos si el elemento elegido es la primera expresión reducida lexicográficamente para su permutación. Así es como la gente suele demostrar que dos expresiones reducidas cualesquiera para una permutación dada están conectadas por una serie de movimientos de trenzas largas y cortas -- reduciendo ambas a la primera expresión reducida lexicográficamente para esa permutación.

Puedes encontrar un algoritmo de este tipo para el grupo simétrico, por ejemplo, en:

Adriano Garsia, La saga de las factorizaciones reducidas de elementos del grupo simétrico, Publications du Laboratoire de Combinatoire et d' Informatique 29 (2002)

Aunque curiosamente no veo este libro en MathSciNet, acabo de encontrar una copia disponible de forma gratuita buscando en Google: La saga de Adriano Garsia

Esto también se discute (para grupos Coxeter más generales) en el libro:

Anders Björner y Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, 231, Springer, Nueva York, 2005, xiv + 363 pp.

Al menos el resultado de conectividad está ahí, y creo que es de nuevo por este tipo de algoritmo -- no tengo el libro conmigo ahora mismo para comprobarlo.

Otra referencia potencialmente relevante es:

Paul Edelman, Lexicographically first reduced words, Discrete Math, 147 (1995), no. 1-3, 95--106.