On lexicographic representatives in braid monoids
- PDF / 1,097,884 Bytes
- 37 Pages / 439.37 x 666.142 pts Page_size
- 87 Downloads / 173 Views
On lexicographic representatives in braid monoids Ramón Flores1
· Juan González-Meneses2
Received: 13 August 2018 / Accepted: 3 October 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract The language of maximal lexicographic representatives of elements in the positive braid monoid An 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 Pn,1 , as k tends to infinity, and 3 = 0.1875 for every n ≥ 1. We also provide an explicit we show that Pn,1 ≥ 16 formula, based on the Fibonacci numbers, for the number of states of the automaton. Finally, we present the pseudocode of an algorithm which computes the adjacency matrix of the finite-state automaton. Keywords Braid monoid · Automaton · Regular language · Fibonacci number
1 Introduction The positive braid monoid with n generators, An , also known as the spherical type Artin–Tits monoid of type An , or as the positive braid monoid on n + 1 strands Bn+1 , is the monoid with the following presentation: An = a1 , . . . , an
ai a j = a j ai ai a j ai = a j ai a j
if | j − i| > 1 if | j − i| = 1
+
.
Both authors partially supported by Spanish Project MTM2016-76453-C2-1-P and FEDER.
B
Ramón Flores [email protected] Juan González-Meneses [email protected]
1
Departamento de Geometría y Topología, Universidad de Sevilla-IMUS, c/Tarfia s/n, 41012 Sevilla, Spain
2
Departamento de Álgebra, Universidad de Sevilla-IMUS, c/Tarfia s/n, 41012 Sevilla, Spain
123
Journal of Algebraic Combinatorics
Since the appearance of the seminal survey included in [1], which in turn reunited different notions that have circulated some years around the group-theoretic community, there has been a growing interest in the role of finite-state automata in group theory. In particular, in the context of Artin groups and monoids, different automata have been proposed, see, for example, [2] or [7]. In the present paper, we deeply analyze a finite-state automaton proposed by the second author and Gebhardt in [5]. In that paper, a polynomial algorithm is given to select a random element of An , among all elements of given length, with uniform probability. The difficulty of this task comes from the fact that a given positive braid β may admit many different words in the generators a1 , . . . , an representing it (although all representatives have the same length, as the relations in An are homogeneous). In order to be able to count the elements in An of length k, one can choose a unique representative for each element. For instance, one can order lexicographically the (finite set of) words representing β, setting a1 < a2 < · · · < an , and choose the smallest element. With this ordering, it is shown in [5] that the language L n of smallest lexicographic representatives of elements of An is a regular language (a fact that
Data Loading...
