[ Main page | Part I. Geometry and combinatorics | Part III. Multiplication | Part IV. Closures ]

Coxeter groups
Part II. Word processing

by Bill Casselman
In working with Coxeter groups on a computer, the most basic questions to be answered are
  • How to represent elements of the group?
  • How to multiply two elements of a group?
  • How to list elements of a group?
There is probably no one best way to deal with these questions in all circumstances, but it will become apparent that I have a personal favorite, partly because it is theoretically the most interesting. In this Chapter we shall examine the first and second questions. Multiplication will be considered in Chapter III.
In any Cartan realization, the elements of $W@ are linear transformations, and one natural idea is to represent them by the corresponding matrices. In some circumstances, for example in low-dimensional graphics or investigating the geometry of regions of the Tits cone, this is a reasonable choice, but usually it is a very poor one. To avoid round-off errors (a potentially serious problem), it is a good idea to use a Cartan matrix with integral coordinates if it exists (as it does for the crystallographic groups), or the standard realization, in which case you are faced with arithmetic in cyclotomic fields. Storage (proportional to $|S|^{2}@) is one problem, and the low speed involved in cyclotomic arithmetic is another. Also, testing inequalities involving cyclotomic numbers can be tricky.

Why are round-off problems potentially serious? For finite and affine groups they probably aren't, but for groups where the Tits cone is acute it may well be - as a chamber $wC@ appproaches its boundary in projective space, it becomes more and more difficult to separate two distinct chambers. This problem is not avoided with crystallographic groups, either, where integer overflow may occur. In practice, I have seen graphics programs have trouble with single precision calculations (about $7@ decimal accuracy), producing images of chambers that were visibly awry near the Tits cone boundary.

A method that is subject to some of the criticisms in the previous section, but is nonethless sometimes convenient, is one which represents each element of $W@ by a vector in $|S|@ dimensions. First fix a vector $u@ in the interior of the fundamental chamber $C@. Then an element $w@ is characterized by either of its transforms $wu@ or $w^{-1}u@ - in effect by the chamber $wC@ itself, since no $w@ will fix $u@. The vector is probably best expressed in terms of the coordinates $w_{a} = < a, w^{-1}u >@ where $a@ varies over the basic roots. The amount of storage involved is minimal, certainly. Then we have a very simple and efficient formula for reflection (where $a = a_{s}@):

$(ws)_{b}@$= < b, (ws)^{-1}u >@
$= < b, s w^{-1}u >@
$= < b, w^{-1}u > - < a, w^{-1}u > < b, a^{v} >@
$= w_{b} - < b, a^{v} > w_{a}@

This is especially efficient because the number $< b, a^{v} >@ (an entry in the Cartan matrix) will in practice be $0@ most of the time and can then be ignored. This formula can be used to multiply two elements $x@ and $y@ if we know an expression $y = s_{1} ... s_{n}@ for $y@.

One nice feature of this representation of elements is that we can use it to find the reduced expressions to use in multiplication. We know that $ws < w@ if and only if $C@ and $w^{-1}C@ lie on opposite sides of the hyperplane $a = 0@ ($a = a_{s}@), that is to say if $< a, Cw > = < w^{-1}a, C > < 0@, or in other words if $w_{a} < 0@. So to find a reduced expression for $w@ we let $s@ be such that $w_{a}@ is negative and calculate $ws@. Repeat until there are no negative coordinates, when $w = 1@. (Research problem) Suppose the realization to be the standard one. Take $u@ to be such that $u_{a} = 1@ for all $a@. The coordinates of $w^{-1}u@ are cyclotomic. Is there a good way to tell whether $(wu)_{a} < 0@ without using real approximation? To estimate carefully how good approximations have to be if you do use them? (This can certainly done for finite dihedral groups.)

One natural way to express elements of $W@ is in terms of one of its expressions as a product of generators. At first this seems a daunting idea, but in time it looks better and better. Its principal advantage is that there are certainly no problems with accuracy. Apparent disadvantages are the complexity of calculations - it is not at all clear where to begin - and possibly having to deal with words of arbitrarily large length. In particular, neither the problem of multiplication nor that of generation have immediately apparent solutions. These, at least, turn out not to be real difficulties, and for interesting mathematical reasons. As for the length of words, in practice it does not seem to be a problem except for elements where calculations are impractical for other, more serious, reasons.

The first difficulty faced in this approach is to decide which of many, many possible reduced expressions by which to represent an element. There are two natural choices. The first is to single out what is called the ShortLex expression, which is lexicographically least (i.e. least in dictionary order) among all reduced expressions. This requires first ordering elements of $S@ or, equivalently, indexing them. Consider the dihedral group of order $8@ with generators $s < t@, for example. Every element except the longest one has a unique reduced expression, and the longest can be expressed as $stst@ or $tsts@ (according to the braid relation). The expression for it is $stst@, since it comes before $tsts@ in the dictionary.

More precisely, the expression for an element $w@ has this recursive definition: (1) $1@ corresponds to the empty word; (2) if $s@ is the least generator such that $sw < w@ then the expression for $w@ is $s@ concatenated to that for $sw@.

Sometimes it is convenient to use the InverseShortLex expression instead, which is the lexicographically least expression when read backwards. In this convention, the longest element above would be represented by $tsts@. For example, it is the expression for $w@ that we can find easily from the vector expression $(w_{a})@, by choosing for length reduction the least $a@ with $w_{a} < 0@.

In the rest of this lecture, we shall explore this purely combinatorial approach.

Tits' word reduction
The first interesting combinatorial result was found by Jacques Tits. In principle, in showing that one word in $S@ is equivalent to another, it could be necessary to inflate the sizes of words as well as shrink them. Tits showed around 1968 that no inflation was necessary. Although this result will play no very practical role, the result is useful in hand calculation, and I will present here a slight modification of Tits' proof.

Changing Tit's terminology slightly, I define reduction of a word in $S@ to be the process of iterating these two transformations of words:

  • deleting a pair $s ### s@;
  • replacing one side of a braid relation by the other.
Here I use $###@ to denote concatenation of words. Let $R(w)@ be the set of all words obtained by all reductions of $w@. It is a finite set, although in general quite large. It includes, for example, all reduced expressions for the element represented by the word, which for even small groups can be huge. The longest element of $H_{4}@, for example (a group of $14,400@ elements whose longest element has length $60@) has, Du Cloux tells me, $1,852,659,333,124,308@ reduced expressions! At any rate, the number of such expressions for a long element can be reasonably expected to be huge. There are three properties of reductions that are straightforward:
  • If $y@ lies in $R(x)@ then $R(y)@ is contained in $R(x)@;
  • if $y@ lies in $R(x)@ and $(x) = (y)@ then $R(y) = R(x)@;
  • $R(s ### x)@ contains $s ### R(x)@.
Here, $(x)@ is the length of $x@ as a word, not as an element of $W@. The third property is a special case of the more general fact that reduction is context-free: that $R(x ### y ### z)@ contains $x ### R(y) ### z@.

(Jacques Tits) In order for two words $x@ and $y@ to be equivalent, it is necessary and sufficient that their reduction sets $R(x)@ and $R(y)@ have an element in common.

. If the intersection is non-empty, then certainly the two are equivalent. The non-trivial half of the Theorem is to show that if $x@ and $y@ are equivalent then $R(x)@ and $R(y)@ intersect. We may assume that $(y) (x)@. Now, the points $(i, j)@ with $j i@ look like this in the plane:

In particular, as the illustration shows, there is a natural order in which to count such points, and the proof proceeds by induction on the index of the pair $(x), (y)@. If $(x) = 0@ the assertion is trivial.

Suppose now that $(x) > 0@, that $(y) (x)@. Our induction assumption is that the Theorem is true for all pairs $x_{*}@, $y_{*}@ with $(x_{*}) < (x)@ or $(x_{*}) = (x)@ but $(y_{*}) < (y)@.

Suppose that there exists $z@ with $(z) < (x)@ lying in $R(x)@. Of course $z@ and $y@ are equivalent. If $(y) < (x)@ than $(z, y) < (y, x)@ since $(y) < (x)@. If $(y) = (x)@ then $(z, y) < (y, x)@ since $(y) = (x)@ but $(z) < (y)@. Either way, we deduce by induction that $R(z)@ and $R(x)@ overlap, hence $R(x)@ and $R(y)@ as well. So we may assume from now on that

  • all elements of $R(x)@ have the same length as $x@.

Since $(x) > 0@, $x = s ### x_{*}@ for some $s@. If $R(x_{*})@ contains elements of length less than that of $x_{*}@, then since $R(x)@ contains $s ### R(x_{*})@ so does $R(x)@ contain elements of length less than that of $x@, a contradiction. So we know that

  • all elements of $R(x_{*})@ have the same length as $x_{*}@, which is $(x) - 1@.

Suppose that $y = s ### y_{*}@. Then $x_{*}@, $y_{*}@ satisfy the induction hypothesis, so that $R(x_{*})@ and $R(y_{*})@ have an element in common. But then so do $s ### R(x_{*})@, $s ### R(y_{*})@, hence $R(x)@ and $R(y)@.

So now we may assume that

  • $y = t ### y_{*}@ with $t@ different from $s@.
In these circumstances, $(y)@ must be the same as $(x)@. For suppose that $(y) < (x)@. The elements $s ### y@ and $x_{*}@ are equivalent. Therefore by the induction assumption $R(s ### y)@ and $R(x_{*})@ have a common element. But since all elements in $R(x_{*})@ have the same length, $(s ### y) = (x_{*}) = (x) - 1@. And $R(s ### y) = R(x_{*})@. Therefore $s ### s y@ lies in $R(x)@, and $y@ lies in $R(x)@. This contradicts our current assumptions.

So now we may assume (a) $(y) = (x)@, and (b) $x = s ### x_{*}@, $y = t ### y_{*}@, with $s@ and $t@ distinct. Since $x@ and $y@ are equivalent, as elements in $W@ they satisfy $sx < x@, $tx < x@, $sy < y@, $ty < y@. Therefore they are longest in their common $W_{s, t}@-coset. Hence there exists a distinguished $z@ in $W^{s, t}@ with $x@, $y@ equivalent to $s_{s, t} z@, where $sz > z@, $tz > z@, $s_{s, t}@ the longest element in $W_{s, t}@. Then $y_{*}@ is equivalent to $s ### t ... z@, $x_{*}@ is equivalent to $t ### s ... z@, and by induction $R(y_{*}) = R(s ### t ... z)@, $R(x_{*}) = R(t ### s ... z)@, and $R(x) = R(s ### x_{*}) = R(s ### t s ... z)@, $R(y) = R(t ### y_{*}) = R(t ### s t ... z)@. But the last two are equivalent according to the braid relation, hence $R(x) = R(y)@.

Because of the potentially huge size of $R(x)@, it is definitely not usually practical to calculate it. Nonetheless, Tits' reductions are easy enough to carry out by hand in simple cases, and his Theorem assures that this effort will not be fruitless. Also, in principle Tits' algorithm tells us how to calculate products. For this, choose an ordering of the elements of $S@ (or, equivalently, index $S@). Assign to each element in $W@ its unique word. Calculating the product of two words $x@ and $y@ means finding the ShortLex expression of the concatenation $z@ of the words. We can do this by calculating $R(z)@ and listing in order in order all those words in it of shortest length. There are standard computer algorithms to do all these operations fairly efficiently, given the essential inefficiency of the process itself. (A minor research problem) Turn this proof into an algorithm that starts with a chain of relations allowing either insertions or deletions and winds up with a pair of reductions.

Finite automata and regular expressions
We are going to be interested in recognizing patterns in reduced expressions for elements of $W@. The simplest patterns of importance will turn out to be regular expressions, those which can be recognized in a particularly simple fashion.

Let's look again at the dihedral group of order $8@. Here is a list of all the expressions of its elements:

$1@, $s@, $t@, $st@, $ts@, $sts@, $tst@, $stst@.

This can also be described by a diagram:

in which paths starting at the dotted disc parametrize words in the group, matching labeled edges between nodes and generators in a word. No surprises here; there are exactly as many nodes in the diagram as there are elements in the group. Something slightly more curious is that paths in this smaller diagram also parametrize the same words:

But the real point to be made occurs with the infinite group $A_{1}^{~}@. The words representing elements can be represented by paths in this diagram, where again elements are in bijection with nodes:

but also by paths in this one:

Of course, this is a wonderul compression! It is the first example we have seen of a phenomenon that we shall see much of later on, and one that seems to be ubiquitous in this subject: infinite Coxeter groups are often represented well by finite structures.

Diagrams of the sort we are looking at - roughly speaking, directed labeled graphs together with a designated starting point - are called automata or state machines in the theory of languages. They play an important role in how computers parse input, among other things. The sets of strings that are recognized by such diagrams are called regular expressions. They are called automata because paths tracing through one follow a program with a strictly limited number of options - if they have arrived at a node, then what they can do subsequently depends only on that node, not on the history of how they got to it. The paths have limited memory, like a simple mechanical toy. If $S@ is any set, the set of all words in $S@ is a regular language commonly expressed as $S*@. If $S = {s, t}@, design a finite automaton that recognizes $S*@. (Edges are allowed to go from a node to itself.)

More about regular expressions
I believe, for reasons that will be laid out later on, that regular expressions will prove to be unavoidable in understanding important phenomena associated to Coxeter groups. How important remains to be seen. Nonetheless, for this reason it seems useful to look at them in more detail. There are many points that haven't been touched upon yet, and a few that haven't been made very precise.

I should also point out that by no means all interesting languages are regular. The simplest example is that of balanced left and right parenthetical expressions. The point is that a regular language has only a limited memory, whereas whether or not a parenthesis `)' is balanced somewhere in an expression by a `(' may involve searching back to the beginning of the expression. Deterministic automata The following are examples of how one normally writes positive rational numbers:

$13@, $2/4@, $20/47@, $1/24@.

These are not:

$13/1@, $02/4@, $0/0@ .

Note that we are not restricting ourselves to reduced fractions. We can put together a recipe for expressing a positive rational number: (1) To write a positive integer we write a sequence of non-negative digits, starting with a positive one. (2) To write a positive rational number, write a positive integer, followed optionally by a slash $/@ followed by a positive integer other than $1@. This recipe is not trivial to read, and for most people it is easier to understand if we encode it in a diagram:

This looks like a finite automaton, but there is a new feature - the red nodes. The point is that not all paths in this diagram lead to an acceptable expression for a fraction. The prefix of a valid expression for a fraction may not be itself valid. For example, the empty string is not acceptable. Also, a single $1@ in the denominator is not acceptable. In this diagram, only those paths leading to a yellow node correspond to acceptable expressions. The yellow nodes are said to be the accepting states of the automaton.

So we have a precise definition: a deterministic automaton is a directed graph together with an alphabet (also called the set of imput symbols). The edges in the graph are labeled by symbols from the alphabet, and there is at most one edge with a given label leaving any node. Some of the nodes are designated as accepting states and one of them as the start state. To such a graph is associated a language in the alphabet $S@, namely those words accepted by a path in the automaton. A path is a sequence of node $n_{0}@, $n_{1}@, ... , $n_{m}@ and it accepts the word $s_{1} ... s_{m}@ if (a) $n_{0}@ is the start state; (b) $n_{m}@ is an accepting state; (c) there is an edge from $n_{k-1}@ to $n_{k}@ labeled by $s_{k}@. If the graph is finite, the language is called regular. This is a crucial restriction, since for any language we can make a recognizing automaton from the tree of all words in the language, which I call the tautologous automaton of the language. Design a finite automaton that represents real numbers.

Why can't we expect a finite automaton to recognize reduced fractions? Whether an expression is recognized by a finite automaton depends on its form, not its content - its syntax, not its semantics. Deciding whether a fraction is reduced or not involves thinking about the meaning of fractions, not just their form. We shouldn't expect anything as simple as a finite automaton to handle this sort of thing. Syntactical analysis is often, however, a preliminary to semantic interpretation. Non-deterministic automata There are also non-deterministic automata. Or, more properly, not-necessarily-deterministic automata. I abbreviate the term as NDA. There are three modifications: (1) There may be several starting states; (2) there may be unlabeled edges; (3) there may be several edges with a given label leaving a node. If $s_{1} ... s_{m}@ is a word in the alphabet, a path accepting this string is a sequence of nodes $n_{0}@, $n_{1}@, ... , n_{m}@ in the automaton such that (a) $n_{0}@ is one of the start states; (b) $n_{m}@ is one of the accepting states; (c) from $n_{k-1}@ to $n_{k}@ there is a directed sequence of edges, one labeled by $s_{k}@ and the rest unlabeled. What is new is that the path is not determined by the word; there may be several paths all accepting the same word. Such diagrams are technically very useful, but do not actually enlarge the meaning of the term `regular expression'. Equivalent automata are those that recognize the same words in the same alphabet.

Every finite NDA is equivalent to a finite deterministic one.

Suppose given an automaton $A@. How is an equivalent deterministic one constructed? First of all, nodes in the new automaton are going to be defined as certain subsets of nodes in the original, which I'll call $A@. And there are two simple auxiliary constructions to be applied in the course of the construction. (a) If $X@ is any set of nodes in $A@, define its saturation $S(X)@ to be the union of $X@ and all nodes reachable from $X@ by an unlabeled edge. A set is called saturated if it is its own saturation. (b) If $X@ is a saturated set of nodes in $A@ and $s@ an input symbol, define $X ### s@ to be the saturation of the set of nodes which are the target of an edge labeled by $s@ leading from a node in $X@. It is entirely possible that $X ### s = X ### t@ for distinct $s@ and $t@.

The nodes of the new automaton are the saturated subsets of the nodes of $A@. There is an edge labeled by $s@ from $X@ to $X ### s@. The start state is the saturation of the set of start states of $A@. A node is accepting if it contains an accepting node from $A@. I leave it as an exercise to verify that this equivlent to $A@.

The new automaton may be huge. In practice, most of the new nodes may be thrown away, because they are not attainable from the start state. As an extreme example, if $A@ is itself deterministic then the only attainable nodes are the singletons. The standard algorithm for constructing the new automaton constructs only those new nodes which are attainable.

The potential exponential growth does occasionally happen. Construction of the deterministic automaton Irredundant automata A node in an automaton is called redundant if no path from a start state reaches it. Eliminating these produces an equivalent automaton. Dead states An automaton is called complete if for each node $n@ and each input symbol $s@ there exists an edge from $n@ labeled by $s@. Any automaton $A@ can be converted easily into an equivalent complete one by adding to it a dead state. This new node is not accepting, and all edges from it lead to itself. If $n@ is a node of $A@ without an edge from it labeled by $s@, then in the new automaton there will be an edge labeled by $s@ leading to the dead state. Inversion The usefulness of non-deterministic automata becomes clear when one tries to build an automaton recognizing the same strings as an automaton $A@, but read backwards. We simply define a new automaton to have as its nodes the same nodes of $A@. Its starting states are the accepting states of $A@, the single accepting state of the new automaton is the start state of $A@, and edges in the new automaton are reversed from those of $A@. That is to say, to an edge from $x@ to $y@ in the original corresponds an edge from $y@ to $x@ in the new one, with the same label. This is a very simple construction, but almost always the new automaton will be non-deterministic. Thus:

The inverted words of a regular language also form a regular language.

This accounts for the result that is a regular language if is. Concatenation If $X@ and $Y@ are languages, then the concatenation of the two is the set of all words $x ### y@ constructed by concatenating a word $x@ from $X@ with on from $Y@. It is denoted X ### Y.

The concatenation of two regular languages is again regular.

Let $X@ and $Y@ be the two languages, $A@ and $B@ recognizing automata. We want to construct an automaton recognizing $X # Y@ in simple terms from $A@ and $B@. An example will motivate the construction, which might otherwise seem mysterious. Suppose $X@ is the language containing just the words $a@ and $ab@, while $Y@ is that containing just $b@ and $bc@. Then $X # Y@ is made up of $ab@, $abb@, $abc@, $abbc@. The minimal deterministic automata for these three languages are

$X # Y@:

The problem is that there is no way to see how the automata for $X@ and $Y@ are related to that for $X # Y@. The source of the difficulty is that the b in abb is different from that in abc - one comes from $X@ and the other from $Y@. There is apparently no direct way to build a deterministic automaton directly from the two components, but there is nonetheless a simple solution: instead of trying to build a deterministic automaton recognizing $X # Y@ we shall build a non-deterministic one. The dual source of the letter b will be dealt with (at least implicitly) by allowing two edges from a given source labeled by b. The actual construction for an arbitrary $X@ and $Y@ is this:

Make up a new version of $A@ by adding to a copy of it a new terminal node z, with unlabeled transitions to it from each accepting state in $A@. Now add on to this in turn a copy of $B@, with unlabeled transitions from $z@ to any of the starting states of $B@ (only one, of course, if $B@ happens to be deterministic). The accepting nodes of the new automaton are just the accepting states of $B@. Repetition If $X@ is a languages, then the repetition of $X@ is the language of all words obtained by concatenating $0@ or more words from $X@. It is denoted X*.

The repetition of a regular language is again regular.

Suppose $A@ recognizes $X@. Add two nodes to a copy of $A@, at the beginning and end. From the first add unlabeled edges to all start states of $A@, and from each of the accepting states add an unlabeled edge to the last. From the last back to the first also add an unlabeled edge. Make each of the new nodes accepting, as well as those of $A@. Add the first to the start states. Alternation If $X@ and $Y@ are languages, then the alternation of the two is the set of all words $w@ which lie in either $X@ or $Y@. It is denoted X | Y.

The alternation of two regular languages is again regular.

Suppose $X@, $Y@, $A@, $B@ as above. Make up a new automaton by starting with copies of $A@ and $B@. Add in a single new node, with unlabeled edges leading from it to all start states of either $A@ or $B@. Make it the single start state of the new automaton. Negation If $X@ is a regular language, then the words in the same alphabet which are not in $E@ also make up a regular language. This new language is called the negation of the original language $X@ and is denoted !X. Keep in mind that this negation is with respect to the given alphabet.

The negation of a regular language is regular.

Suppose that $A@ is a complete automaton recognizing $X@. The recognizing automaton for its negation has the same nodes, edges, and start state as $A@, but its accepting states are the complement of the accepting states in $A@. Intersection If $X@ and $Y@ are languages, then the intersection of the two is the set of all words simultaeously in both languages. It is denoted X & Y.

The intersection of two regular languages is again regular.

It is the negation of the alternation of their negations. Minimal automata Any language is recognized by a unique smallest automaton. There is an efficient algorithm to compute the equivalent minimal automaton from any given finite one.

Here's an example we have seen already. The tautologous automaton recognizing reduced words for $A_{1}^{~}@ is

But now some of the nodes are equivalent in the sense that the paths out of these nodes are the same - i.e. the options for continuing a word from that node are the same. In this picture, all the nodes coloured green are equivalent since all paths out of any of them is just a repeated $st ... @, and all those coloured blue are also equivalent:

We can collapse all of the same colour to a single point, to get a new equivalent automaton:

This construction is always valid, but a bit of care is required. It is not the full set of words leaving a node which is important, but just those which lead to acceptable nodes. For example, a few extra edges could always be added to a dead state without changing things substantially. If $A@ is any automaton, define two nodes $n_{1}@ and $n_{2}@ to be equivalent if they have the following property: a word $w@ leads from $n_{1}@ to an accepting state in $A@ if and only if it leads from $n_{2}@ to an accepting state. Define a new automaton whose nodes are the equivalence classes of nodes in $A@. It start state is the class containing the start state of $A@. Its accepting states are those classes containing accepting nodes of $A@. There is an edge labeled $s@ from a class $N_{1}@ to a class $N_{2}@ if there is an edge from $n_{1}@ in $N_{1}@ to $n_{2}@ in $N_{2}@ labeled by $s@. I leave it as an exercise to verify that this is an equivalent deterministic automaton. The minimization algorithm There is an algorithm for producing the minimal automaton equivalent to a given one which is remarkably efficient. To explain it, I begin by putting the problem more constructively. Let $A@ be the given automaton, which for the moment I assume complete. Nodes $n_{1}@ and $n_{2}@ of $A@ are called equivalent if for every word $w@ in the alphabet of $A@ the nodes $n_{1} # w@ and $n_{2} # w@ are either both accepting or both not. Break this down into more a more explicit test. Divide the nodes into two blocks, the accepting nodes and the rest. Call two nodes equivalent of order $0@ if they are both in the same block. Inductively, call node $n_{1}@ and $n_{2}@ equivalent of order $m+1@ if they are equivalent of order $m@ and the nodes $n_{1} # s@ and $n_{2} # s@ are also equivalent of order $m@ for all symbols $s@. Thus they are equivalent if they are equivalent of all orders.

Suppose we have already found the blocks $B@ of elements equivalent of order $m@, and suppose there are $k@ input symbols. Then we partition each block $B@ into smaller blocks $B_{C1, ... , Ck}@, where $B_{C1, ... , Ck}@ is the set of $b@ in $B@ such that $b # s_{i}@ lies in the block $C_{i}@, for each $i = 1@, ... , $k@. If there are $N@ blocks of order $m@ equivalence, then a priori there might be as many as $N^{k+1}@ blocks of order $m+1@, a potentially disastrous super-exponential growth.

In fact there exists an algorithm with time dependence $O(k n log n)@ if $n@ is the number of states in the original automaton. This works because most of the blocks $B_{C1, ... , Ck}@ will be empty, so the idea is to find away of going from one order to the next by somehow automatically excluding the empty ones.

This algorithm solves a slightly more general problem, one which occurs when dealing with Coxeter groups. Suppose we are given a collection of maps $f_{i}@, $i@ varying over a set $S@, and a partition of a set $X@ into blocks $X_{i}@. Two elements $x@ and $y@ are called equivalent if any iteration of the $f@'s applied to them finds them in the same block. We shall call an element dead if all the $f@'s take it to itself. It works like this, in a rough description:
Start with the partition into two blocks, accepting and non-accepting. Maintain a list of pairs $(B, s)@, to be processed in the order in which they are put on the list, and start the list off by putting all $(B, s)@ on the list where $B@ is the block of accepting states and $s@ ranges over all the input symbols.

While this list is not empty: take a pair $(B, s)@ off the list. For each node $y@ in $B@ look at all nodes $x@ with $x # s = y@. Record the block $B_{x}@ in which $x@ appears. After all $y@ have been examined, look at each of the blocks $B_{*}@ that have been met in this way. If the total number of times they have been encountered is not equal to the total number of elements in $B_{*}@, then divide $B_{*}@ into two parts, the $x@ such that $x # s@ lies in $B#@, and the rest. Let $C@ be the smaller of these two subsets of $B_{*}@. Put $(C, s)@ on the process list for all input symbols $s@. Loop.

In implementing this, before beginning make for each $y@ and $s@ a list of all nodes $x@ with $x # s = y@. As we process the elements $y@ of a block $B@ we maintain a list of all $x@ we meet with $x # s@ in $B@ as well as the block to which $x@ belongs. We also maintain a list of those $B_{x}@, but each one listed only once. After we have examinedd all $y@ in $B@, we go through the list of the $B_{*}@ met, comparing it to the set of $x@ in it. If we do create a new block $C@ by removing elements from $B_{*}@ we do one of two things: put $(C, s)@ on the process list if $(B_{*}, s)@ is on that list; or if not then we put the smaller of $(C, s)@ and $(B_{*}, s)@ on the list.

Automata and Coxeter groups
Let's look at the words for a more complicated infinite Coxeter group, that with Coxeter diagram . It is an affine group, and we shall look at it as generated by affine reflections. There are three generators, which I write as 1, <00ff00>2, <9999ff>3. Each element of the group is represented by a word, hence a path of coloured arrows from the chamber $C@ to the chamber $wC@. Because of uniqueness, the paths all together make up a tree with $C@ as its root.

Certain things are not difficult to see in this image. Every non-empty expression starts with one of the three symbols 1, <00ff00>2, or <9999ff>3, so the chambers other than $C@ are partitioned into three corresponding regions of the plane. Because of the ordering of the three, (1) the $w@ starting with 1 are those chambers on the side of the line of reflection $a_{1} = 0@ opposite to $C@; (2) those $w@ starting with <00ff00>2 are those chambers on the side of the line of reflection $a_{2} = 0@ opposite to $C@, but not already in the first region; (3) those starting with <9999ff>3 are those chambers on the side of the line of reflection $a_{3} = 0@ opposite to $C@, but not already in either of the previous two.

It is significant that each of these regions is convex. Indeed, it appears that all of the regions comprised of a single chamber together with its successors in the tree are convex. We shall why this is so in a moment.

The question is whether we can recognize in this tree a repetition of patterns similar to that in the tree for $A_{1}^{~}@. The answer is that we can. For example, there exist some simple cycles 1<9999ff>3<00ff00>2 ...

There are lots of such cycles - in the following picture, each yellow chamber represents the same position in such a cycle:

But there are more interesting repetitions: Start out at $C@ and move by <9999ff>3. You arrive at essentially the same pattern if you follow this by 1<00ff00>21<9999ff>3. What do I mean by `the same pattern'? That the tree of paths leading out of the two chambers are congruent. If you pick up one of these trees, so to speak, and shift it rigidly to the other chamber, you can then lay it down upon the tree leading out of the second. (Of course I am not claiming to prove this, but all evidence is in favour of the assertion.) There are other chambers equivalent to these two, too. All such positions are shown here:

Two chambers will be called ShortLex congruent if the pattern of transitions in the tree out of each of them is the same. If this happens, then there exists an element of the Weyl group transforming one of these patterns onto the other. It turns out for $A_{2}^{~}@ as for $A_{1}^{~}@ (although we have only suggested that it is true, certainly not proven it) that the set of all expressions for this group is a regular language, or in other words that there are a finite number of congruence classes. Here is the corresponding finite automaton:

Note that there are indeed loops 1<9999ff>3<00ff00>2 and 1<00ff00>21<9999ff>3, as well as 1<00ff00>2<9999ff>3.

This is not an isolated case. It is a very beautiful result of Brigitte Brink and Bob Howlett that:

For any Coxeter group, there are finite automata recognizing expressions, expressions, and reduced words in the group.

We shall look at the proof in subsequent sections. That is a regular language follows formally from the regularity of , since it is just the reversed language. It is reasonable to think of both of these as lacking in significance, perhaps to be considered results in applied rather than pure mathematics. But that reduced words should also be recognized by a finite automaton must be a fundamental property of Coxeter groups. For finite and affine groups it is not a very deep result; it is equivalent to other more familiar properties of these groups. But for other groups it is not at all a trivial fact, and that it has taken so long to be discovered is likely just a sign that not much work has been devoted to these groups.

Here is the finite automaton recognizing reduced words for $A_{2}^{~}@:

Its symmetry arises from the symmetry of the Coxeter diagram. Embedded in it are three hexagons, which are the finite automata for the dihedral groups of two generators, each of order $6@. The minimal finite automaton recognizing reduced words for a finite Coxeter group is always the same size as the group itself - this is essentially because all words terminate in the longest element. Prove this last assertion - that any finite automaton recognizing the reduced expressions for a finite Coxeter group have to have size at least that of the group itself.

Minimal roots
The key to the proof of the Theorem of Brink and Howlett is a more fundamental result of theirs about the roots of a Cartan realization of a Coxeter group. One positive root $b@ is said to dominate another positive root $a@ if the two roots are distinct and the intersection of the half-space $a > 0@ with the Tits cone $@ is entirely contained in the half-space $b > 0@. In other words, if whenever $wC@ lies in the region $a > 0@ then it also lies in the region $b > 0@, equivalently if whenever $w^{-1}a > 0@ then $w^{-1}b > 0@ also. I call a root minimal if it does not dominate any roots. (This notion was first applied seriously by Bob Howlett and Brigitte Brink. Their terminology differs from mine - In their joint paper they use the term elementary, and Howlett still prefers this. In a subsequent paper Brink uses the term dominance minimal, to take account of the distinction between the partial ordering on roots determined by dominance and another one to be introduced later on.) For finite groups, the Tits cone is all of $V@, so there is no dominance and all positive roots are minimal. For affine groups the concept is also simple. In this case the positive roots are of the form $a + c@ for all positive roots $a@ of the associated finite root system and non-negative integer constants $c@, as well as $-a + c@ where $a@ is positive and $c@ is a positive integer. Thus whenever one root dominates another the root hyperplanes must be parallel. The basic ones are the basic roots of the finite system together with $-a + 1@, where $a@ is what is common called the dominant root (although there is no relation with the dominance defined here). The minimal roots are those of the form $a@ or $-a + 1@ where $a@ is positive in the finite system. But for other groups the concept is more subtle. Here is what happens for the group with Coxeter diagram :

In this and a few other simple cases the minimal roots all touch the chamber $C@, but that does not always happen.

The fundamental result of Brink and Howlett , upon which all their non-trivial results depend, is that:

For any Coxeter group there are only a finite number of minimal roots.

Bob Howlett remarks somewhere that he thinks this is a fundamental fact about Coxeter groups, even though there seem to be few applications of it to other properties, and I agree with him.

I am not going to prove the theorem of Brink and Howlett here, but I shall explain some more elementary properties of minmal roots.

There are two interesting order relations among positive roots. One is dominance, which we have seen already. The other is more closely related to how the positive roots are generated. Every positive root is equal to the transform of a basic root by and element of $W@. Define the depth of a root $p@ to be the least length of a $w@ such that $w^{-1} p < 0@. This is also $1@ less than the least length of a $w@ such that $w^{-1} p@ is a basic root. Geometrically, it is the length of the least gallery starting at $C@ with terminal chamber in the region $p < 0@. Thus the depth of a basic root is $1@. Define $p q@ if $q = w p@, where the depth of $q@ is equal to the sum of the depth of $p@ and the length of $w@. We thus have a labeled directed graph: there is an edge from $p@ to $q@ labeled by $s@ in $S@ if $d(q) = d(p) + 1@ and $s p = q@, and $p q@ if there exists a sequence of edges in this root graph from $p@ to $q@.

1. The minimal roots are minimal in this order. 2. If $p@ is a minimal root and $s@ in $S@, then exactly one of these holds: (a) $p = a_{s}@, and $s p < 0@; (b) $s p@ is another minimal root; (c) $s p@ dominates $a_{s}@. Thus we get the minimal root reflection table. In cases (a) we write $s p = -@, in case (c) we write $s p = +@, else $s p = q@. The minimal root reflection table is an important tool in algorithms involving Coxeter groups.

The root hyperplanes $p = 0@ and $q = 0@ intersect in if and only if the group generated by $s_{p}@ and $s_{q}@ is contained in the conjugate of some finite dihedral group $W_{s, t}@. The product $st@ will thus be of order dividing $m_{s, t}@.

Lemma. If $p@ dominates $q@ and $wq@ is a positive root then $wp@ is also a positive root and $wp@ dominates $wq@.

If $p q@ and $p@ is minimal then so is $q@. If $p@ dominates $q@ then thedepth of $p@ is greater than or equal to to that of $q@.

Brink's thesis.

Coxeter distance. Different definitions of depth. Structure of the root graph?

Building the automaton

For each $w@ in $W@ let $_{w}@ be the SL continuation, the set of all $x@ in $W@ such that the word for $w@ is a prefix of that for $x@.

Then $w # s@ lies in if and only if $ws@ lies in $_{w}@ and then $_{ws} = _{w} w _{s}@. The region $_{w} = w^{-1}_{w}@ is the ine intersection of minimal root half-spaces. Use the equivalent: $w # s@ is in if and only if $s@ lies in $_{w}@ and then $_{ws} = s S_{w} cap S_{s}@. (consistency: $C@ at least lies in this intersection since $C@ is contained in s _{w}@). Distinguish geometry from elements. Proof: uses that if $r@ is a minimal root then either (1) $s r@ is again a minimal root; or (2) $r = a_{s}@ and $s r < 0@ or (3) $s r@ dominates $a_{s}@. The $_{w}@ determine the minimal automaton recognizing or reduced words. For the second, need to know $_{s} = { a_{s} }@ while for the second ${ a_{s} } s a_{t} (t < s)@

One advantage of knowing the automaton for is that generation of elements is then easy.

Other occurrences of regular expressions in Coxeter groups

The reduced words for those elements of $W@ with a unique reduced expression form a regular language.

The reduced words are a regular language, and those which uniquely represent an element are, by Tits' Theorem, those which do not contain either side of a braid relation. But those words in $S@ which contain any one side of a particular braid relation form a regular language, hence so do those containing any side of a braid relation, since alternation preserves regularity. But the complement of a regular language is regular, and the intersection of two regular languages is regular.

The coloured chambers are those representing elements with unique expressions.
  • James Humphreys, Reflection groups and Coxeter groups, Cambridge Press, 1990.
  • B. Brink, The set of dominance-minimal roots, preprint, University of Sydney, 1994. Available at http://. This is very different from the article with the same name published in the Journal of Algebra. It is in some ways more readable.
  • B. Brink, The set of dominance-minimal roots, Journal of Algebra 206 (1998), pp. 371-412.
  • B. Brink and R. Howlett, A finiteness property and an automatic structure for Coxeter groups, Math. Ann. 296 (1993), pp.179-190.
  • W. Casselman, Automata, informal lecture notes (in PostScript format), 2002.
  • W. Casselman, Automata to perform basic calculations in Coxeter groups, in Representations of groups, CMS Conference Proceedings 16, A.M.S., 1994.
  • W. Casselman, Multiplication in Coxeter groups, to appear in the Electronic Journal of Combinatorics.
  • A. Aho and J. Ullmann, Design and analysis of computer algorithms, Addison-Wesley, 1974.
  • Fokko du Cloux, Un algorithme de forme normale pour les groupes de Coxeter, preprint, Centre de Mathématiques à l'École Polytechnique, 1990.
  • Fokko du Cloux, A transducer approach to Coxeter groups, J. Symb. Computation 27 (1999), pp. 311-324.
  • J. Tits, Le problème des mots dans les groupes de Coxeter, Symposia Math.1 (1968), pp. 175-185.