9
$\begingroup$

Let $W$ be a Coxeter group with set of simple reflections $S$. Suppose that I have chosen a preferred reduced decomposition for every element of $W$. Given an arbitrary word in the alphabet $S$, is there an algorithm for reducing this word to my chosen decomposition using the Coxeter relations? That is to say, an algorithm which at each step replaces a subword of the form $s_i s_k s_i \dots$ by $s_k s_i s_k \dots$, or which removes an occurrence of $s_k^2$.

I would be happy with an answer in the following situation: $W=\Sigma_n$ is the symmetric group on $n$ letters and the preferred decomposition is given by taking the lexicographically smallest (or largest) reduced decomposition.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

Yes, at least if your chosen element is the lexicographically first reduced expression for your permutation. This is how people usually prove that any two reduced expressions for a given permutation are connected by a series of long and short braid moves -- by reducing both to the lexicographically first reduced expression for that permutation.

You can find such an algorithm for the symmetric group e.g. in:

Adriano Garsia, The saga of reduced factorizations of elements of the symmetric group, Publications du Laboratoire de Combinatoire et d' Informatique 29 (2002)

While oddly enough, I don't see this book listed on MathSciNet, I just found a copy available for free by googling: Adriano Garsia saga

This is also discussed (for more general Coxeter groups) in the book:

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

At least the connectedness result is there, and I believe it is again by this type of algorithm -- I don't have the book with me right now to check for sure.

Another potentially relevant reference is:

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ What do you mean by 'greedy'? For example, how does this algorithm deal with $s_1 s_3 s_2 s_1 s_3$? When you reference Garsia, I assume that you are referring to the proof of Theorem 1.1.2. This describes a different algorithm which is probably sufficient for my purposes. $\endgroup$
    – Joe Loubert
    Oct 7, 2012 at 23:17
  • $\begingroup$ Yes, I was referring to Theorem 1.1.2, though I guess I hadn't remembered the details of how it worked correctly. $\endgroup$
    – Patricia Hersh
    Oct 7, 2012 at 23:35
  • $\begingroup$ If you don't yet have the lexicographically earliest reduced expression, then either your expression will agree up to commutation moves with one having $s_{i+1}s_is_{i+1}$, or will have $s_js_i$ for $j>i+1$. My point was to keep eliminating such things until there are none left. But I'd forgotten about perhaps needing commutation moves to enable a long braid move, which means you should prioritize long braid moves. Anyway, if your focus is type A, Garsia is a good source; otherwise I'd see Björner/Brenti. I'm not sure whether Humphreys also discusses this, but that's a good place to look too. $\endgroup$
    – Patricia Hersh
    Oct 8, 2012 at 1:33
11
$\begingroup$

An algorithm for reducing arbitrary words in any Coxeter group to their lexicographically least reduced representatives is described in the paper:

B. Brink and R.B. Howlett, ``A finiteness property and an automatic structure for Coxeter groups'', Math. Ann. 296, (1993), 179-190.

It doesn't do exactly what you asked for, in that it doesn't do the reductions using only the defining Coxeter relations, but it uses longer substitutions, which can of course be derived from the defining relations, and are always length or lexicographically decreasing. It is the reduction algorithm based on the automatic structure of Coxeter groups, and runs in quadratic time in general. It has been implemented (for example) in the Computer Algebra System Magma.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.