Throughout this section, for denotes an adjacent transposition in , and is the word length with respect to . Since , words in the are just words in the .
12.2.1 Permutation Diagrams
Definition 12.2.1 (Permutation diagram). The diagram of consists of points on a top line, points on a bottom line, and for each a strand joining the top point to the bottom point . The strands may be drawn as straight segments, or as any curves that move steadily downward; only which point is joined to which matters.
The diagram of a product is obtained by placing the diagram of above the diagram of : the strand starting at reaches in the middle and at the bottom. This matches our convention that applies first. The diagram of is a single crossing:
So writing amounts to drawing a diagram of in layers, each containing a single crossing, with at the top and at the bottom. For example, here is the permutation with one-line notation (so ,,,; in cycle notation ), drawn with straight strands and in layers:
The layered diagram shows that . The straight diagram has three crossings, one for each pair of strands whose order is reversed.
12.2.2 Word Length Equals the Number of Inversions
Recall from Definition 3.4.10 that an inversion of is a pair with and , that is the number of inversions, and that . In the straight diagram of , the strands starting at cross exactly when , so is the number of crossings.
Lemma 12.2.2 (Multiplying by ). Let and . Then
Proof. The permutation takes the same values as , except that the values in positions and are swapped: . Let be positions with . Since only exchanges the adjacent positions and , we still have , and is an inversion of if and only if is an inversion of . The map is a bijection of the set of pairs other than , so and have the same number of inversions among these pairs. Finally, is an inversion of if and only if , that is, if and only if it is not an inversion of .∎
Theorem 12.2.3 (Word length in ). For every , the word length of with respect to is .
Proof. First, whenever : by Lemma 12.2.2, each additional factor changes the number of inversions by , and .
Next we show by induction on that is a product of generators. If , then , so , the empty product. If , then for some , since otherwise would be increasing. By Lemma 12.2.2, , so by induction is a product of generators, and is a product of of them. ∎
In the language of diagrams: every layered diagram of has a crossing for each pair of strands whose order is reversed, and if the strands starting at adjacent points and cross, we can draw that crossing first, as the top layer , and continue with a diagram of .
Corollary 12.2.4 (The longest element). The permutation with , has word length , and every other element of has smaller word length.
Proof. Every pair is an inversion of , so . Any is not decreasing, so it has a pair with , and .∎
Proposition 12.2.5 (Shortest words ending in ). Let and . The following are equivalent:
some shortest word for ends with ;
;
.
The set of such is the ending set of .
Proof. (a)(b): if with a word of length , then has length at most . (b)(a): by Lemma 12.2.2 and Theorem 12.2.3, ; a shortest word for followed by is a word for of length ending with . (b)(c) is Lemma 12.2.2, since .∎
Similarly, some shortest word for begins with if and only if is in the ending set of (reverse the word); these form the starting set of .
12.2.3 Diagrams and the Presentation of
By Theorem 3.6.18, the map induces an isomorphism In terms of diagrams, the three kinds of relations are three local moves:
two consecutive crossings of the same two strands cancel; crossings of strands far apart slide past each other; and a strand can be moved across the crossing of two others. The presentation says that every identity between words in the that holds in follows from these three moves.
12.2.4 A Normal Form for
Definition 12.2.6 (Normal form). A normal form for a group is a set of words in the letters ,, such that every element of is represented by exactly one of these words.
If we have a normal form and an algorithm that rewrites any word as the normal-form word representing the same element, the word problem is solved: two words represent the same element if and only if they have the same normal form.
Proposition 12.2.5 lets us list all the shortest words for a permutation : for each in the ending set of , find the shortest words for and append . Making the same choice every time singles out one of them.
Definition 12.2.7 (Normal form for ). For , define a word in recursively: is the empty word, and for ,
Since at each step, the recursion stops after steps, and is a word of length representing : a shortest word for . As runs over , the words form a normal form for , with respect to the presentation of Theorem 3.6.18.
Example 12.2.8 (A normal form). Let as above. Its ending set is , since and . Following the smallest index each time: where each arrow multiplies on the right by , that is, swaps the entries in positions and . So , the word read off the layered diagram above. Following index first instead, gives the other shortest word, ; since , and each have a single index in their ending sets, these two are the only shortest words for .
For , whose elements we can compute with directly, the word problem is easy anyway. The point is that the same method, describing an element by a preferred word built greedily from the end, also works in groups we cannot compute with so directly, such as the braid groups.