On lexicographic representatives in braid monoids

Abstract

The language of maximal lexicographic representatives of elements in the positive braid monoid $A_n$ with $n$ generators is a regular language. We describe with great detail the smallest Finite State Automaton accepting such language, and study the proportion of elements of length $k$ whose maximal lexicographic representative finishes with the first generator. This proportion tends to some number $P_{n,1}$, as $k$ tends to infinity, and we show that $P_{n,1}\ge \frac{1}{8}$ for every $n\ge 1$. We also provide an explicit formula, based on the Fibonacci numbers, for the number of states of the automaton.

29 pages, lots of figures. Updated reference