---
abstract: 'We develop a new approach to the linear ordering of the braid group $B_{n}$, based on investigating its restriction to the set¨${{\mathrm{Div}}({\Delta}_{{n}}^{{d}})}$ of all divisors of ${{\Delta}_{{n}}^{{d}}}$ in the monoid¨$B_\infty^+$, [[*i.e.*]{}]{}, to positive $n$-braids whose normal form has length at most¨${d}$. In the general case, we compute several numerical parameters attached with the finite orders ${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$. In the case of $3$ strands, we moreover give a complete description of the increasing enumeration of ${({\mathrm{Div}}({\Delta}_{3}^{{d}}),\nobreak{<}\nobreak)}$. We deduce a new and specially direct construction of the ordering on $B_3$, and a new proof of the result that its restriction to $B_3^+$ is a well-ordering of ordinal type $\omega^\omega$.'
address: |
    Laboratoire de Mathématiques Nicolas Oresme UMR 6139\
    Université de Caen, 14032 Caen, France
author:
- Patrick DEHORNOY
title: Still another approach to the braid ordering
---

The general aim of this paper is to investigate the connection between the Garside structure of Artin’s braid groups and their distinguished linear ordering (sometimes called the Dehornoy ordering). This leads to a new, alternative construction of the ordering.

Artin’s braid groups¨$B_{n}$ are endowed with several interesting combinatorial structures. One of them stems from Garside’s analysis [@Gar] and is nowadays known as a Garside structure¨[@Dgk; @McC]. It describes $B_{n}$ as the group of fractions of a monoid¨$B_{n}^+$ with a rich divisibility theory. One of the outcomes of this theory is a unique normal decomposition for every braid in¨$B_{n}$ in terms of simple braids, which are the divisors of Garside’s fundamental braid ${\Delta}_{n}$, a finite family of¨$B_{n}^+$ in one-to-one correspondence with the permutations of ${n}$ objects. One obtains a natural graduation of the monoid¨$B_{n}^+$ by considering the family ${{\mathrm{Div}}({\Delta}_{{n}}^{{d}})}$ of all divisors of ${{\Delta}_{{n}}^{{d}}}$, which also are the elements of $B_n^+$ whose normal form has length at most ${d}$.

On the other hand, the braid groups are equipped with a distinguished linear ordering, which is compatible with multiplication on the left, and admits a simple combinatorial characterization¨[@Dfb]: a braid¨${x}$ is smaller than another braid¨${y}$ if, among all expressions of the quotient¨${x}{^{-1}}{y}$ in terms of the standard generators¨${\sigma_{i}}$, there exists at least one expression in which the generator¨${\sigma_{{m}}}$ with maximal (or minimal) index¨${m}$ appears only positively, [[*i.e.*]{}]{}, ${\sigma_{{m}}}$ occurs, but ${\sigma_{{m}}}{^{-1}}$ does not. Several deep results about that ordering are known, in particular the fact that its restriction to¨$B_\infty^+$ is a well-ordering, and a number of equivalent constructions are known¨[@Dgr].

Although both combinatorial in nature, the previous structures remain mostly unconnected—and connecting them may appear as one of the most natural questions of braid combinatorics. For degree¨$1$, [[*i.e.*]{}]{}, for simple braids, the linear ordering corresponds to a lexicographical ordering of the associated permutations¨[@Dgb]. But this connection does not extend to higher degrees, and almost nothing is known about the restriction of the linear ordering to positive braids of a given degree. In particular, no connection is known between the above mentioned Garside normal form and the alternative normal form constructed by S.Burckel in¨[@Bus; @But; @Buu], one that makes comparison with respect to the linear ordering easy: to give an example, the Garside normal form of¨${{\Delta}_{3}^{2{d}}}$ is¨$({\sigma_{1}}{\sigma_{2}}{\sigma_{1}})^{2{d}}$, while its Burckel normal form is $({\sigma_{2}}{\sigma_{1}}^2{\sigma_{2}})^{d}{\sigma_{1}}^{2{d}}$.

Our aim in this paper is to investigate the finite linearly ordered sets ${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$. A nice way of thinking of this structure is to consider the increasing enumeration of¨${{\mathrm{Div}}({\Delta}_{{n}}^{{d}})}$, and to view it as a distinguished path from¨$1$ to¨${{\Delta}_{{n}}^{{d}}}$ in the Cayley graph of¨$B_{n}$. A complete description of this path would arguably be an optimal solution to the rather vague question of connecting the Garside and the ordered structures of braid groups. Such a description seems to be extremely intricate from a combinatorial point of view, and it remains out of reach for the moment, but we prove partial results in this direction, namely

- $(i)$ in the general case, a determination of some numerical parameters attached with ${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$ that in some sense measure its size, with explicit values for small values of¨${n}$ and¨${d}$, and

- $(ii)$ in the special case ${n}= 3$, a complete description of the increasing enumeration of¨${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$.

More specifically, the parameters we investigate are the complexity and the heights. The complexity¨${{c}({{\Delta}_{{n}}^{{d}}})}$ is defined as the maximal number of occurrences of¨${\sigma_{{n}-1}}$ in an expresion of¨${{\Delta}_{{n}}^{{d}}}$ containing no¨${\sigma_{{n}-1}}$. It is connected with the termination of the handle reduction algorithm of¨[@Dfo], and its determination was left as an open question in the latter paper. The ${r}$-height¨${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ is defined to be the number of¨${r}$-jumps in the increasing enumeration of ${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$ (augmented by¨$1$), where the term ${r}$-jump refers to some natural filtration of the linear ordering¨${<}$ by a sequence of partial orderings¨${<}_{r}$. When ${r}$ increases, ${r}$-jumps are higher and higher, so ${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ counts how many big jumps exist in ${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$. We prove that the complexity ${{c}({{\Delta}_{{n}}^{{d}}})}$ equals the height ${{h_{{n}-1}}({{\Delta}_{{n}}^{{d}}})}$ (Proposition¨\[P:MainHeight\]), and that, for each¨${r}$, the ${r}$-height ${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ is the number of divisors of¨${{\Delta}_{{n}}^{{d}}}$ whose ${d}$th factor of the normal form is right divisible by¨${\Delta}_{r}$ (Proposition¨\[P:Main\]). Together with the combinatorial results of¨[@Dhi], this allows for computing the explicit values listed in Table¨\[T:Values\], and for establishing various inductive formulas (Propositions¨\[P:Values\] and¨\[P:Values34\], among others).

Besides the enumerative results, we also prove a general structural result that connects the ordered set ${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$ with (subsets of) ${({\mathrm{Div}}({\Delta}_{{n}-1}^{{d}}),\nobreak{<}\nobreak)}$ (Corollary¨\[C:Structure\]). This result suggests an inductive method for directly constructing the increasing enumeration of ${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$ starting from those of ${({\mathrm{Div}}({\Delta}_{{n}-1}^{{d}}),\nobreak{<}\nobreak)}$ and ${({\mathrm{Div}}({\Delta}_{{n}}^{{d}-1}),\nobreak{<}\nobreak)}$. This approach is completed here for ${n}= 3$ (Proposition¨\[P:Enum3\]). In some sense, $3$ strand braids are simple objects, and the result may appear as of modest interest; however, the order on $B_3^+$ is a well-ordering of ordinal type $\omega^\omega$, hence not a so simple object. The interesting point is that this approach leads to a new, alternative construction of the braid ordering, with in particular a new and simple proof for the so-called Comparison Property which is the hard core in the construction, namely the part that guarantees the linearity of the ordering. In this way, one obtains not only one more construction of an ordering that already has many constructions [@Dgr], but arguably the optimal one, as it makes all proofs simple once the initial inductive definition is correctly stated, and as the connection with the Garside structure is then explicit.

The paper is organized as follows. After a first introductory section recalling basic properties and setting the notation, we introduce the parameters ${{c}({{\Delta}_{{n}}^{{d}}})}$ and ${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ in Section¨\[S:Meas\], and we establish their connection. In Section¨\[S:Deter\], we connect in turn ${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ with the number of ${n}$-braids whose ${d}$th factor in the normal form satisfy certain constraints, and deduce explicit values. Finally, in Section¨\[S:N3\], we study the specific case of¨${({\mathrm{Div}}({\Delta}_{3}^{{d}}),\nobreak{<}\nobreak)}$ and describe its increasing enumeration, resulting in the new construction of the braid ordering in this case.

Background and preliminary results
==================================

Our notation is standard, and we refer to textbooks like¨[@Bir] or¨[@Eps] for basic results about braid groups. We recall that the ${n}$¨strand braid group¨$B_{n}$ is defined for ${n}\ge 1$ by the presentation $$\label{E:Present}
B_{n}= \left<{\sigma_{1}}, \dots, {\sigma_{{n}-1}} \,;\,
\begin{array}{cl}
{\sigma_{i}} {\sigma_{j}} = {\sigma_{j}} {\sigma_{i}} 
&\text{\quad for $\vert
i - j\vert \ge 2$}\\
\   {\sigma_{i}} {\sigma_{j}} {\sigma_{i}}  = {\sigma_{j}} {\sigma_{i}} {\sigma_{j}}
&\text{\quad for $\vert i - j\vert = 1$}
\end{array} \right>.$$ So, $B_1$ is the trivial one-element group, while $B_2$ is the free group generated by¨${\sigma_{1}}$. The elements of¨$B_{n}$ are called ${n}$¨strand braids, or simply [*${n}$-braids*]{}. We use $B_\infty$ for the group generated by an infinite sequence of¨${\sigma_{i}}$’s subject to the relations of¨, [[*i.e.*]{}]{}, the direct limit of all¨$B_{n}$’s with respect to the inclusion of¨$B_{n}$ into¨$B_{n+1}$.

By definition, every ${n}$-braid¨${x}$ admits (infinitely many) expressions in terms of the generators¨${\sigma_{i}}$, $1
\le i < n$. Such an expression is called an ${n}$¨strand [*braid word*]{}. Two braid words¨${w},
{w}'$ representing the same braid are said to be [*equivalent*]{}; the braid represented by a braid word¨${w}$ is denoted¨${[{w}]}$.

Positive braids and the element ${\Delta}_{n}$
----------------------------------------------

We denote by¨$B_{n}^+$ the monoid admitting the presentation¨, and by¨$B_\infty^+$ the union (direct limit) of all¨$B_{n}^+$’s. The elements of¨$B_{n}^+$ are called [*positive*]{} ${n}$-braids. In¨$B_\infty^+$, no element except¨$1$ is invertible, and we have a natural notion of divisibility:

For ${x}, {y}$ in¨$B_{n}^+$, we say that ${x}$ is a [*left divisor*]{} of¨${y}$, denoted ${x}{\preccurlyeq}{y}$, or, equivalently, that ${y}$ is a [*right multiple*]{} of¨${x}$, if ${y}= {x}{z}$ holds for some¨${z}$ in¨$B_{n}^+$. We denote by¨${\mathrm{Div}}({y})$ the (finite) set of all left divisors of¨${y}$ in¨$B_{n}^+$.

The monoid $B_{n}^+$ is not commutative for ${n}\ge
3$, and therefore there are distinct symmetric notions of a right divisor and a left multiple—but we shall mostly use left divisors here. Note that ${x}$ is a (left) divisor of¨${y}$ in the sense of¨$B_{n}^+$ if and only if it is a (left) divisor in the sense of¨$B_\infty^+$, so there is no need to specify the index¨${n}$.

According to Garside’s theory [@Gar], $B_{n}^+$ equipped with the left divisibility relation is a lattice: any two positive ${n}$-braids¨${x},
{y}$ admit a greatest common left divisor, denoted ${\mathrm{gcd}}({x}, {y})$, and a least common right multiple, denoted¨${\mathrm{lcm}}({x}, {y})$. A special role is played by the lcm¨${\Delta}_{n}$ of¨${\sigma_{1}}$, …, ${\sigma_{{n}-1}}$, which can be inductively defined by $$\label{E:Delta}
{\Delta}_1 = 1, \qquad
{\Delta}_{n}= {\sigma_{1}} {\sigma_{2}} \dots {\sigma_{n-1}} \, {\Delta}_{{n}-1}.$$ It is well known that ${\Delta}_{n}^2$ belongs to the centre of¨$B_{n}$ (and even generates it for ${n}\ge 3$), and that the flip automorphism¨${\phi_{n}}$ of¨$B_{n}$ corresponding to conjugation by¨${\Delta}_{n}$ exchanges¨${\sigma_{i}}$ and¨${\sigma_{n-i}}$ for $1 \le i \le {n}-1$. It follows that ${\phi_{n}}$ also exchanges¨${\sigma_{n, 1}}$ and¨${\sigma_{1, n}}$.

In¨$B_{n}^+$, the left and the right divisors of¨${\Delta}_{n}$ coincide, and they make a finite sublattice of¨$(B_{n}^+,
{\preccurlyeq})$ with ${n}!$¨elements. These braids will be called [*simple*]{} in the sequel. When braid words are represented by diagrams as mentioned in Figure \[F:Diagram\], simple braids are those positive braids that can be represented by a diagram in which any two strands cross at most once.

(83,21)(0,0) (10,0)[![One associates with every ${n}$¨strand braid word¨${w}$ an ${n}$¨strand braid diagram by stacking elementary diagrams as above; then two braid words are equivalent if and only if the associated diagrams are the projections of ambient isotopic figures in¨${\mathbb{R}}^3$, [[*i.e.*]{}]{}, one can deform one diagram into the other without allowing the strands to cross or moving the endpoints.[]{data-label="F:Diagram"}](Sigma.eps "fig:")]{} (0,13)[${\sigma_{i}}$ :]{} (0,3)[${\sigma_{i}}{^{-1}}$ :]{} (9.5,19)[$1$]{} (19.5,19)[$2$]{} (50,19)[$i$]{} (58,19)[$i{+}1$]{} (27,3)[…]{} (77,3)[…]{} (27,13)[…]{} (77,13)[…]{}

By mapping¨${\sigma_{i}}$ to the transposition¨$(i, i+1)$, one defines a surjective homomorphism¨$\pi$ of¨$B_{n}$ onto the symmetric group¨${\mathfrak{S}_{{n}}}$. The restriction of¨$\pi$ to simple braids is a bijection: for every permutation¨$f$ of¨$\{1, \dots, {n}\}$, there exists exactly one simple braid¨${x}$ satisfying $\pi({x}) = f$. It follows that the number of simple ${n}$-braids is¨${n}!$.

\[X:Degree\] The set¨${{\mathrm{Div}}({\Delta}_{3}^{})}$ consists of six elements, namely $1$, ${\sigma_{1}}$, ${\sigma_{2}}$, ${\sigma_{2}}{\sigma_{1}}$, ${\sigma_{1}}{\sigma_{2}}$, and¨${\Delta}_3$. In examples, we shall often use the shorter notation¨$\tt a$ for¨${\sigma_{1}}$, $\tt b$ for¨${\sigma_{2}}$, [[*etc.*]{}]{} Thus, the six simple $3$-braids are $1$, $\tt a$, $\tt b$, $\tt ba$, $\tt ab$, $\tt aba$.

The normal form
---------------

For each positive ${n}$-braid¨${x}$ distinct of¨$1$, the simple braid ${\mathrm{gcd}}({x}, {\Delta}_{n})$ is the maximal simple left divisor of¨${x}$, and we obtain a distinguished expression ${x}= {x}_1 {x}'$ with¨${x}_1$ simple. By decomposing¨${x}'$ in the same way and iterating, we obtains the so-called normal expression¨[@ElM; @Eps].

A sequence $({x}_1, \dots, {x}_{d})$ of simple ${n}$-braids is said to be [*normal*]{} if, for each¨${k}$, one has ${x}_{k}=
{\mathrm{gcd}}({\Delta}_{n}, {x}_{k}\dots {x}_{d})$.

Clearly, each positive braid admits a unique normal expression. It will be convenient here to consider the normal expression as unbounded on the right by completing it with as many trivial factors¨$1$ as needed. In this way, we can speak of the [*${d}$th factor*]{} (in the normal form) of¨${x}$ for each positive braid¨${x}$. We say that a positive braid has [*degree¨${d}$*]{} if ${d}$ is the largest integer such that the ${d}$th factor of¨${x}$ is not¨$1$. We shall use the following two properties of the normal form:

[@ElM] \[L:Normal\] A sequence of simple ${n}$-braids $({x}_1, \dots,
{x}_{d})$ is normal if and only if, for each¨${k}<
{d}$, each¨${\sigma_{i}}$ that divides¨${x}_{{k}+1}$ on the left divides¨${x}_{k}$ on the right.

[@ElM] \[L:Degree\] For ${x}$ a positive braid in¨$B_{n}^+$, the following are equivalent:

$(i)$ The braid¨${x}$ belongs to¨${{\mathrm{Div}}({\Delta}_{{n}}^{{d}})}$, [[*i.e.*]{}]{}, is a (left or right) divisor of¨${{\Delta}_{{n}}^{{d}}}$;

$(ii)$ The degree of¨${x}$ is at most¨${d}$.

\[X:Enum\] There are 19 divisors of ${{\Delta}_{3}^{2}}$, which also are the $3$-braids of degree at most $2$. Their enumeration in normal form—in an ordering that may seem strange now, but should become familiar soon—is: $1$, ${\mathtt{a}}$, ${\mathtt{a}}{\mathord{\cdot}}{\mathtt{a}}$, ${\mathtt{b}}$, ${\mathtt{b}}{\mathtt{a}}$, ${\mathtt{b}}{\mathtt{a}}{\mathord{\cdot}}{\mathtt{a}}$, ${\mathtt{b}}{\mathord{\cdot}}{\mathtt{b}}$, ${\mathtt{b}}{\mathord{\cdot}}{\mathtt{b}}{\mathtt{a}}$, ${\mathtt{a}}{\mathtt{b}}$, ${\mathtt{a}}{\mathtt{b}}{\mathtt{a}}$, ${\mathtt{a}}{\mathtt{b}}{\mathtt{a}}{\mathord{\cdot}}{\mathtt{a}}$, ${\mathtt{a}}{\mathtt{b}}{\mathord{\cdot}}{\mathtt{b}}$, ${\mathtt{a}}{\mathtt{b}}{\mathord{\cdot}}{\mathtt{b}}{\mathtt{a}}$, ${\mathtt{a}}{\mathord{\cdot}}{\mathtt{a}}{\mathtt{b}}$, ${\mathtt{a}}{\mathtt{b}}{\mathtt{a}}{\mathord{\cdot}}{\mathtt{b}}$, ${\mathtt{a}}{\mathtt{b}}{\mathtt{a}}{\mathord{\cdot}}{\mathtt{b}}{\mathtt{a}}$, ${\mathtt{b}}{\mathtt{a}}{\mathord{\cdot}}{\mathtt{a}}{\mathtt{b}}$, ${\mathtt{a}}{\mathtt{b}}{\mathtt{a}}{\mathord{\cdot}}{\mathtt{a}}{\mathtt{b}}$, ${\mathtt{a}}{\mathtt{b}}{\mathtt{a}}{\mathord{\cdot}}{\mathtt{a}}{\mathtt{b}}{\mathtt{a}}$.

By Lemma \[L:Degree\], every divisor of¨${{\Delta}_{{n}}^{{d}}}$ can be expressed as the product of at most¨${d}$ divisors of¨${\Delta}_{n}$, so we certainly have ${\mathtt{\#}}{{\mathrm{Div}}({\Delta}_{{n}}^{{d}})} \le ({n}!)^{d}$ for all¨${n},
{d}$.

The braid ordering
------------------

The basic notion is the following one:

Let ${w}$ be a nonempty braid word. We say that ${\sigma_{{m}}}$ is the [*main*]{} generator in¨${w}$ if ${\sigma_{{m}}}$ or ${\sigma_{{m}}}{^{-1}}$ occurs in ${w}$, but no ${\sigma_{i}}^{\pm1}$ with $i > {m}$ does. We say that ${w}$ is [*$\s$-positive*]{} ([[*resp.[ ]{}*]{}]{}[*$\s$-negative*]{}) if the main generator occurs only positively ([[*resp.[ ]{}*]{}]{}negatively) in¨${w}$.

A positive nonempty braid word, [[*i.e.*]{}]{}, one that contains no¨${\sigma_{i}}{^{-1}}$ at all, is $\s$-positive, but the inclusion is strict: for instance, ${\sigma_{1}}{^{-1}}{\sigma_{2}}$ is not positive, but it is $\s$-positive, as its main generator, namely¨${\sigma_{2}}$, occurs positively (one¨${\sigma_{2}}$) but not negatively (no¨${\sigma_{2}}{^{-1}}$).

Then we have the following two properties, which have received a number of independent proofs¨[@Dgr]:

[*A $\s$-positive braid word does not represent¨$1$.*]{}

[*Every braid except¨$1$ can be represented by a $\s$-positive word or by a $\s$-negative word.*]{}

It is then straightforward to order the braids:

If ${x}, {y}$ are braids, we say that ${x}{<}{y}$ holds if the braid¨${x}{^{-1}}{y}$ admits at least one $\s$-positive representative.

It is clear that the relation¨${<}$ is transitive and compatible with multiplication on the left; Property¨A implies that ${<}$ has no cycle, hence is a strict partial order, and Property¨C then implies that it is actually a linear order.

As every nonempty positive braid word is $\s$-positive, ${x}{\preccurlyeq}{y}$ implies ${x}{\le}{y}$ for all positive braids¨${x}, {y}$, but the converse is not true: ${\sigma_{1}}$ is not a left divisor of¨${\sigma_{2}}$, but ${\sigma_{1}}
{<}{\sigma_{2}}$ holds, since ${\sigma_{1}}{^{-1}}{\sigma_{2}}$ is a $\s$-positive word.

\[X:List\] The increasing enumeration of the set¨${{\mathrm{Div}}({\Delta}_{3}^{})}$ is $$\tt 1 {<}a {<}b {<}ba {<}ab {<}aba.$$ For instance, we have $\tt ba {<}ab$, [[*i.e.*]{}]{}, ${\sigma_{2}}{\sigma_{1}}
{<}{\sigma_{1}}{\sigma_{2}}$, as the quotient, namely ${\sigma_{1}}{^{-1}}{\sigma_{2}}{^{-1}}{\sigma_{1}} {\sigma_{2}}$ (or $\tt ABab$), also admits the expression ${\sigma_{2}} {\sigma_{1}}{^{-1}}$, a $\s$-positive word. Similarly, the reader can check that the increasing enumeration of¨${{\mathrm{Div}}({\Delta}_{3}^{2})}$ is the one given in Example \[X:Enum\].

\[L:Extend\] The linear ordering¨${<}$ extends the left divisibility ordering¨${\prec}$.

By definition, $1 {<}{\sigma_{i}}$ holds for every¨$i$. As the ordering¨${<}$ is compatible with multiplication on the left, it follows that ${x}{<}{x}{\sigma_{i}}$ holds for all¨$i, {x}$, and, therefore, ${x}{<}{x}{y}$ holds whenever ${y}$ is a non-trivial positive braid.

Lemma¨\[L:Extend\] implies that $1$ is always the first element of¨${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$, and ${{\Delta}_{{n}}^{{d}}}$ is always its last element. It may be noted that a deep result by Laver¨[@Lve] shows that, although ${<}$ is not compatible with right multiplication in general, nevertheless ${x}{<}{\sigma_{i}}
{x}$ always holds, [[*i.e.*]{}]{}, ${<}$ also extends the right divisibility ordering.

By Property C, every nontrivial braid admits at least one $\s$-positive or $\s$-negative expression. In general, such a $\s$-positive or $\s$-negative expression is not unique, but the main generator in such expressions is uniquely defined:

\[L:Index\] If a braid¨${x}$ admits a $\s$-positive expression, then the main generators in any two $\s$-positive expressions of¨${x}$ coincide.

Assume that ${w}$, ${w}'$ are $\s$-positive expressions of¨${x}$, and let ${\sigma_{{m}}}$, ${\sigma_{{m}'}}$ be their main generators. Assume for instance ${m}<
{m}'$. Then ${w}{^{-1}}{w}'$ is a $\s$-positive word, and it represents the trivial braid¨$1$: this contradicts Property¨A.

So, there will be no ambiguity in referring to [*the*]{} main generator of some non-trivial braid¨${x}$: this means the main generator in any $\s$-positive (or $\s$-negative) expression of¨${x}$.

Our current definition corresponds to the order¨$<^\phi$ of¨[@Dgr]. It differs from the one most usually considered in literature in that we refer to the maximal index rather than to the minimal one in the definition of a $\s$-positive word. Switching from one definition to the other amounts to conjugating by¨${\Delta}_{n}$, [[*i.e.*]{}]{}, to applying the flip automorphism. Results are entirely similar for both versions. However, it is much more convenient to consider the “max” choice here, because it guarantees that $B_{n}^+$ is an initial segment of¨$B_{n+1}^+$. Using the “min” convention would make the statements of the forthcoming sections less natural.

Measuring the ordered sets¨${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$ {#S:Meas}
=========================================================================================

As was said above, our aim is to investigate the finite ordered sets¨${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$, and, more generally, $({\mathrm{Div}}({z}), {<})$ for¨${z}$ a positive braid. We shall do it by defining numerical parameters that somehow measure their size. The first parameter involves the length of the $\s$-positive words that are, in some natural sense defined below, drawn in the Cayley graph of¨${{\Delta}_{{n}}^{{d}}}$. It will be called the [*complexity*]{} of¨${{\Delta}_{{n}}^{{d}}}$, because it is directly connected with the complexity analysis of the handle reduction algorithm of¨[@Dfo]. The other parameters involve a filtration of the linear ordering by the¨${\sigma_{i}}$’s, and they will be called the [*heights*]{} of¨${{\Delta}_{{n}}^{{d}}}$ because they count the jumps of a given height in¨${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$.

Sigma-positive paths in the Cayley graph
----------------------------------------

The first parameter we attach to $({\mathrm{Div}}({z}),
{<})$ involves the $\s$-positive paths in the Cayley graph of¨${z}$.

We recall that the Cayley graph of the group¨$B_{n}$ with respect to the standard generators ${\sigma_{i}}$ is the labeled graph with vertex set¨$B_{n}$ and such that there exists a ${\sigma_{i}}$-labeled edge from¨${x}$ to¨${y}$ if and only if ${y}= {x}{\sigma_{i}}$ holds. The Cayley graph of the monoid¨$B_{n}^+$ is obtained by restricting the vertices to¨$B_{n}^+$. Note that the Cayley graph of¨$B_{n}$ (and a fortiori of¨$B_{n}^+$) can be seen as a subgraph of the Cayley graph of¨$B_\infty$.

(Figure¨\[F:Cayley\]) For ${z}$ a positive braid, we denoted by¨${\Gamma}({z})$ the subgraph of the Cayley graph of¨$B_\infty$ obtained by restricting the vertices to¨${\mathrm{Div}}({z})$, and only keeping those edges that connect two vertices in¨${\mathrm{Div}}({z})$.

As every element of¨$B_{n}^+$ is a left divisor of¨${{\Delta}_{{n}}^{{d}}}$ for¨${d}$ large enough, the Cayley graph of¨$B_{n}^+$ is the union of all graphs¨${{\Gamma}({{\Delta}_{n}^{k}})}$ when ${d}$¨varies.

\[htb\]

(110,51)(0, -3) (5,8)[![The graphs of¨${{\Gamma}({{\Delta}_{3}^{}})}$ and ${{\Gamma}({{\Delta}_{3}^{2}})}$; the dotted edges represent¨${\sigma_{1}}$, the plain ones¨${\sigma_{2}}$; observe that the graph of¨${{\Delta}_{3}^{2}}$ is not planar; in grey: two $\s$-positive words traced in the graphs, namely $\tt aAbab$ and $\tt bbabAbab$ ([*cf.*]{} Lemma¨\[L:Path\])[]{data-label="F:Cayley"}](Path31.eps "fig:")]{} (50,0)[![The graphs of¨${{\Gamma}({{\Delta}_{3}^{}})}$ and ${{\Gamma}({{\Delta}_{3}^{2}})}$; the dotted edges represent¨${\sigma_{1}}$, the plain ones¨${\sigma_{2}}$; observe that the graph of¨${{\Delta}_{3}^{2}}$ is not planar; in grey: two $\s$-positive words traced in the graphs, namely $\tt aAbab$ and $\tt bbabAbab$ ([*cf.*]{} Lemma¨\[L:Path\])[]{data-label="F:Cayley"}](Path32.eps "fig:")]{} (2,20)[$1$]{} (10,34)[${\sigma_{2}}$]{} (27,34)[${\sigma_{2}}{\sigma_{1}}$]{} (10,7)[${\sigma_{1}}$]{} (27,7)[${\sigma_{1}}{\sigma_{2}}$]{} (36,20)[${\Delta}_3$]{} (47,20)[$1$]{} (55,33)[${\sigma_{2}}$]{} (60,44)[${\sigma_{2}}^2$]{} (70,44)[${\sigma_{2}}^2{\sigma_{1}}$]{} (80,44)[${\sigma_{2}}{\sigma_{1}}^2$]{} (90,44)[${\sigma_{2}}{\sigma_{1}}^2{\sigma_{2}}$]{} (65,33)[${\sigma_{2}}{\sigma_{1}}$]{} (65,33)[${\sigma_{2}}{\sigma_{1}}$]{} (86,33)[${\Delta}_3{\sigma_{1}}$]{} (99,33)[${\Delta}_3{\sigma_{1}}{\sigma_{2}}$]{} (55,8)[${\sigma_{1}}$]{} (65,8)[${\sigma_{1}}{\sigma_{2}}$]{} (86,8)[${\Delta}_3{\sigma_{2}}$]{} (99,8)[${\Delta}_3{\sigma_{2}}{\sigma_{1}}$]{} (82,20)[${\Delta}_3$]{} (108,20)[${\Delta}_3^2$]{} (60,-3)[${\sigma_{1}}^2$]{} (70,-3)[${\sigma_{1}}^2{\sigma_{2}}$]{} (80,-3)[${\sigma_{1}}{\sigma_{2}}^2$]{} (90,-3)[${\sigma_{1}}{\sigma_{2}}^2{\sigma_{1}}$]{}

A path in the Cayley graph can be specified by its initial vertex and the list of the labels of its successive edges, [[*i.e.*]{}]{}, by a braid word. For each¨$i <
n$ and each¨${x}$ in¨$B_{n}$, there is exactly one ${\sigma_{i}}$-labeled edge with target¨${x}$, and one ${\sigma_{i}}$-labeled edge with source¨${x}$ in the Cayley graph of¨$B_{n}$. Hence, in the complete Cayley graph of¨$B_{n}$, for each initial vertex¨${x}$ and each ${n}$-braid word¨${w}$, there is always one path labeled¨${w}$ starting from¨${x}$. When we restrict to some fragment¨${\Gamma}$, this need not be the case, but we have an unambiguous notion of¨${w}$ being drawn in¨${\Gamma}$ from¨${x}$. Formally, this corresponds to

For ${\Gamma}$ a subgraph of the Cayley graph of¨$B_\infty$, and ${x}$ a vertex in¨${\Gamma}$, we say that a braid word¨${w}$ is [*drawn*]{} from¨${x}$ in¨${\Gamma}$ if, for every prefix¨${v}{\sigma_{i}}$ ([[*resp.[ ]{}*]{}]{}${v}{\sigma_{i}}{^{-1}}$) of¨${w}$, there exists a ${\sigma_{i}}$-labeled edge starting from ([[*resp.[ ]{}*]{}]{}finishing at)¨${x}\, {[{v}]}$ in¨${\Gamma}$.

For instance, we can check on Figure¨\[F:Cayley\] that the word¨${\sigma_{1}}^2$ is drawn from¨${\sigma_{2}}$ in¨${{\Gamma}({{\Delta}_{3}^{2}})}$, but not in¨${{\Gamma}({{\Delta}_{3}^{}})}$. In algebraic terms, we have the following characterization:

\[L:Path\] Assume that ${z}$ is a positive braid, and ${w}$ is a braid word. Then ${w}$ is drawn from¨${x}$ in¨${\Gamma}({z})$ if and only if ${x}{[{v}]} {\preccurlyeq}{z}$ holds for each prefix¨${v}$ of¨${w}$.

The condition is sufficient. Indeed, assume it is satisfied by¨${w}$, and ${v}{\sigma_{i}}$ is a prefix of¨${w}$. Then, by hypothesis, ${x}{[{v}]}$ and ${x}{[{v}]}{\sigma_{i}}$ are left divisors of¨${z}$, hence are vertices in¨${\Gamma}({z})$, and, therefore, there is a ${\sigma_{i}}$-labeled edge between¨${x}{[{v}]}$ and ${x}{[{v}]} {\sigma_{i}}$ in¨${\Gamma}({z})$. The argument is similar for a prefix of the form ${v}{\sigma_{i}}{^{-1}}$. Using induction on the length of¨${w}$, we deduce that ${w}$ is drawn from¨${x}$ in¨${\Gamma}({z})$.

Conversely, if there exists a ${w}$-labeled path from¨${x}$ in¨${\Gamma}({z})$, then, for each prefix¨${v}$ of¨${w}$, the braid¨${x}{[{v}]}$ has to represent some vertex in¨${\Gamma}({z})$, hence it is a left divisor of¨${z}$.

For¨${z}$ a positive braid, we shall investigate the $\s$-positive words drawn in the graph¨${\Gamma}({z})$. It is clear that, even if ${\mathrm{Div}}({z})$ is a finite set, arbitrary long words are drawn in¨${\Gamma}({z})$ whenever the latter contains at least 2¨vertices, [[*i.e.*]{}]{}, ${z}$ is not¨$1$. The example of Figure¨\[F:Cayley\] shows that restricting to $\s$-positive words does not change the result: for instance, for each¨${k}$, the word $({\sigma_{1}}{\sigma_{1}}{^{-1}})^{k}{\sigma_{2}}{\sigma_{1}}{\sigma_{2}}$ is a $\s$-positive expression of¨${\Delta}_3$, and it is drawn in¨${{\Gamma}({{\Delta}_{3}^{}})}$. So we cannot hope for any finite upper bound on the length of the $\s$-positive words drawn in¨${\Gamma}({z})$ in general. Now, the situation changes if we concentrate on the main generators, [[*i.e.*]{}]{}, we forget about the generators with non-maximal index.

\[L:Finite\] Assume that ${\Gamma}$ is subgraph of the Cayley graph of¨$B_\infty$, and ${w}$ is a $\s$-positive word drawn in¨${\Gamma}({z})$. Then the number of occurrences of the main generator in¨${w}$ is at most the number of non-terminal vertices in¨${\Gamma}$.

Assume that ${w}$ is drawn from¨${x}$ in¨${\Gamma}$. Let ${\sigma_{{m}}}$ be the main generator in¨${w}$. As there is at most one ${\sigma_{{m}}}$-labeled edge starting from each vertex of¨${\Gamma}$, it suffices to show that the number of¨${\sigma_{{m}}}$’s in¨${w}$ is bounded above by the number of ${\sigma_{{m}}}$-edges in¨${\Gamma}$. Hence, it suffices to show that the path¨$\gamma$ associated with¨${w}$ cannot cross the same ${\sigma_{{m}}}$-edge twice. Now assume that some ${\sigma_{{m}}}$-edge starts from the vertex¨${y}$, and that ${\gamma}$ crosses this edge twice. This means that ${\gamma}$ contains a loop from¨${y}$ to¨${y}$. Let ${v}$ be the subword of¨${w}$ labeling that loop. By construction, ${v}$ begins with¨${\sigma_{{m}}}$, it contains no¨${\sigma_{{m}}}{^{-1}}$ and no ${\sigma_{i}}^{\pm1}$ with $i > m$ as it is a subword of¨${w}$, and it represents the braid¨$1$ as it labels a loop in the Cayley graph of¨$B_\infty$: this means that ${v}$ is a $\s$-positive word representing¨$1$, which contradicts Property¨A.

Lemma¨\[L:Finite\] applies in particular to every graph¨${\Gamma}({z})$ with¨${z}$ a positive braid. So we can introduce our first parameter measuring the size of the ordered set¨${({\mathrm{Div}}({z}),\nobreak{<}\nobreak)}$:

(Figure \[F:Cayley\]) For¨${z}$ a positive braid with main generator¨${\sigma_{{m}}}$, the [*complexity*]{}¨${c}({z})$ of¨${z}$ is defined to be the maximal number of¨${\sigma_{{m}}}$’s in a $\s$-positive word drawn in¨${\Gamma}({z})$.

The word¨${\sigma_{2}} {\sigma_{1}} {\sigma_{2}}$ is a $\s$-positive word drawn from¨$1$ in¨${{\Gamma}({{\Delta}_{3}^{}})}$, and it contains two¨${\sigma_{2}}$’s, hence we have ${{c}({{\Delta}_{3}^{}})}
\ge 2$. Actually, it is not hard to obtain the exact value ${{c}({{\Delta}_{3}^{}})} = 2$. Indeed, if a $\s$-positive path¨${\gamma}$ contains the two ${\sigma_{2}}$-edges starting from¨$1$ and¨${\sigma_{1}}{\sigma_{2}}$, it cannot come back to¨${\sigma_{2}}$ for possibly crossing the third ${\sigma_{2}}$-edge; and if ${\gamma}$ contains the ${\sigma_{2}}$-edge that starts from¨${\sigma_{1}}$, it can never come back to¨$1$ or to¨${\sigma_{2}}{\sigma_{1}}$ and therefore contains at most one ${\sigma_{2}}$-edge. As we have ${{\Delta}_{3}^{{d}}} = ({\sigma_{2}} {\sigma_{1}} {\sigma_{2}})^{d}$, we deduce ${{c}({{\Delta}_{3}^{{d}}})} \ge 2{d}$ for every¨${d}$; this value is certainly not optimal, since the example displayed in Figure¨\[F:Cayley\] contains five¨${\sigma_{2}}$’s, proving ${{c}({{\Delta}_{3}^{2}})} \ge 5$—the exact value is¨$6$, and, more generally, we have ${{c}({{\Delta}_{{n}}^{{d}}})}
= 2^{{d}+1} - 2$, as will be seen in Section¨\[S:Deter\].

Restricting to $\s$-positive words drawn in¨${\Gamma}({z})$ is essential: for instance, for each¨${k}$, we have $$\label{E:Unbounded}
{\Delta}_3 = {\sigma_{2}}^{{k}+1} {\sigma_{1}}{\sigma_{2}}{\sigma_{1}}^{-{k}},$$ a $\s$-positive word containing ${k}+ 2$ letters¨${\sigma_{2}}$. Now, for¨${k}\ge 1$, the word involved in¨ is not drawn in¨${{\Gamma}({{\Delta}_{3}^{1}})}$, as its prefix¨${\sigma_{2}}^2$ is not. Thus the parameter¨${c}({z})$ really involves the left divisors of¨${z}$.

A direct application of Lemma¨\[L:Finite\] gives:

Every positive braid has a finite complexity; more precisely, for¨${z}$ of length¨$\ell$ in¨$B_{n}^+$ with ${n}\ge 3$, we have ${c}({z}) \le ({n}-1)^\ell$.

The number of non-terminal vertices in¨${\Gamma}({z})$, [[*i.e.*]{}]{}, the number of proper left divisors of¨${z}$, is at most $1 + ({n}-1) + ({n}-1)^2 + \cdots + ({n}-1)^{\ell-1}$.

As the length of any positive expression of¨${\Delta}_{n}$ is ${n}({n}-1)/2$, we obtain in particular for all¨${n}, {d}$ $$\label{E:Coarse}
{{c}({{\Delta}_{{n}}^{{d}}})} \le
({n}-1)^{{d}{n}({n}-1)/2}.$$

Before going further, let us observe that, in the definition of the complexity of¨${z}$, we can restrict to decompositions of¨${z}$, [[*i.e.*]{}]{}, instead of considering paths starting from and finishing at arbitrary vertices, we can restrict to paths starting from¨$1$ and finish at¨${z}$:

\[L:Decomp\] Assume that ${z}$ is a positive braid with main generator¨${\sigma_{{m}}}$. Then ${c}({z})$ is the maximal number of¨${\sigma_{{m}}}$’s in any $\s$-positive decomposition of¨${z}$ drawn in¨${\Gamma}({z})$.

Let ${c}'({z})$ be the number involved in the above statement. Clearly we have ${c}'({z}) \le {c}({z})$. Conversely, assume that ${w}$ is drawn in¨${\Gamma}({z})$ from¨${x}$, and that the ${w}$-labeled path starting from¨${x}$ finishes at¨${y}$. Let ${u}$ be a positive expression of¨${x}$, and ${v}$ be a positive expression of¨${y}{^{-1}}{z}$. The latter exists as, by hypothesis, ${y}$ is a left divisor of¨${z}$. Then ${u}{w}{v}$ is a $\s$-positive decomposition of¨${z}$ drawn in¨${\Gamma}({z})$. Hence we have ${c}'({z}) \ge {c}({z})$.

Let us call Property A$^*$ the fact that all numbers¨${{c}({{\Delta}_{{n}}^{{d}}})}$ are finite. Above we derived Property A$^*$ from Property¨A. Actually, the implication is an equivalence, [[*i.e.*]{}]{}, we can also deduce Property¨A from Property A$^*$. Indeed, assume that some $\s$-positive braid word¨${w}$ represents¨$1$. The word¨${w}$ may involve negative letters and the problem is to find a vertex¨${x}$ such that there exists a path labeled¨${w}$ from¨${x}$ in some¨${{\Gamma}({{\Delta}_{{n}}^{{d}}})}$. Let ${\sigma_{m}}$ be the main generator in¨${w}$. The word¨${w}$ has finitely many prefixes, say ${w}_0$, …, ${w}_\ell$. By Garside’s theory, each word¨${w}_i$ is equivalent to a word of the form¨$u_i{^{-1}}{v}_i$ with ${u}_i, {v}_i$ positive. Let ${x}$ be the least common left multiple of the positive braids¨${[{u}_0]}$, …, ${[{u}_\ell]}$. Then, for each¨$i$, the braid¨${x}{[{w}_i]}$ is positive. Moreover, there exist¨${n}$ and¨${d}$ such that ${x}{[{w}_0]}$, …, ${x}{[{w}_\ell]}$ all are divisors of¨${{\Delta}_{{n}}^{{d}}}$. This means that the word¨${w}$ is drawn from¨${x}$ in¨${{\Gamma}({{\Delta}_{{n}}^{{d}}})}$, and the associated path is a loop around¨${x}$. It follows that ${w}^{k}$ is drawn in¨${{\Gamma}({{\Delta}_{{n}}^{{d}}})}$ from¨${x}$ for each¨${k}$. By construction, ${w}^{k}$ contains at least ${k}$¨generators¨${\sigma_{m}}$, hence ${{c}({{\Delta}_{{n}}^{{d}}})}$ cannot be finite.

Connection with handle reduction
--------------------------------

Handle reduction¨[@Dfo] is an algorithmic solution to the word problem of braids that relies on the braid ordering—actually the most efficient method available to-date in practice. It is proved to be convergent, but the complexity upper bound resulting from the argument of¨[@Dfo] is exponential with respect to the length of the input word, seemingly very far from sharp.

Each step of handle reduction involves a specific generator¨${\sigma_{i}}$, and, for an induction, the point is to obtain an upper bound on the number of reduction steps involving the main generator. The latter will naturally be called the [*main*]{} reduction steps. The connection between handle reduction and the complexity as defined above relies on the following technical result:

[@Dfo] Assume that ${z}$ is a positive braid with main generator¨${\sigma_{{m}}}$, and ${w}$ is drawn in¨${\Gamma}({z})$. Then, for each sequence of handle reductions from¨${w}$, [[*i.e.*]{}]{}, each sequence¨$\vec{w}$ with ${w}_0= {w}$ such that ${w}_{k}$ is obtained by reducing one handle from¨${w}_{{k}-1}$ for each¨${k}$, there exists a witness-word¨${u}$ that is $\s$-positive, drawn in¨${\mathrm{Div}}({z})$, and such that the number of¨${\sigma_{{m}}}$’s in¨${u}$ is the number of main reductions in¨$\vec{w}$.

It follows that the number of main reduction steps in any sequence of handle reductions starting with a word drawn in¨${\Gamma}({z})$ is bounded above by¨${c}({z})$. In particular, if we start with an $n$¨strand braid word¨${w}$ of length¨$\ell$, then it is easy to show that ${w}$ is drawn in¨${{\Gamma}({{\Delta}_{{n}}^{\ell}})}$, and, applying the upper bound of¨, we deduce an upper bound for the number of possible main reductions from¨${w}$, one that is exponential with respect to¨$\ell$.

A natural way of improving this coarse upper bound would be to determine the value of¨${{c}({{\Delta}_{{n}}^{{d}}})}$ more precisely. This will be done in Section¨\[S:Deter\] below. However, the explicit formulas show that, for ${n}\ge
3$, the growth rate with respect to¨${d}$ is exponential, thus discarding any hope of proving the expected polynomial upper bound for the number of reduction steps by this approach.

A filtration of the braid ordering
----------------------------------

We now introduce new numerical parameters for the ordered sets¨${({\mathrm{Div}}({z}),\nobreak{<}\nobreak)}$. These numbers appear in connection with a natural filtration of the ordering¨${<}$, using an increasing sequence of partial orderings that we introduce now.

By Lemma¨\[L:Index\], the index of the main generator of a non-trivial braid is well defined. We can use this index to measure the height of the jump between two braids¨${x}, {y}$ satisfying ${x}{<}{y}$:

For ${x}, {y}$ in $B_\infty$ and ${r}\ge 1$, we say that ${x}{<}_{r}{y}$ holds or, equivalently, that $({x}, {y})$ is a [*${r}$-jump*]{}, if ${x}{^{-1}}{y}$ admits a $\s$-positive expression in which the main generator is ${\sigma_{{m}}}$ with ${m}\ge {r}$.

For each ${r}\ge 1$, the relation ${<}_{r}$ is a strict partial order that refines ${<}$; the relation ${<}_1$ coincides with ${<}$, and ${r}\le {q}$ implies that ${<}_{q}$ refines ${<}_{r}$.

That ${<}_{r}$ is transitive follows from the fact that the concatenation of a $\s$-positive word with main generator ${\sigma_{{m}}}$ and a $\s$-positive word with main generator ${\sigma_{{m}'}}$ is a $\s$-positive word with main generator ${\sigma_{\max({m}, {m}')}}$.

In the sequel, we consider the ${<}_{r}$-chains included in ${\mathrm{Div}}({z})$, and their length:

For ${z}$ a positive braid and ${r}\ge 1$, we define the [*${r}$-height*]{}¨${h_{{r}}}({z})$ of¨${z}$ to be the maximal length of a ${<}_{r}$-chain included in ${\mathrm{Div}}({z})$.

Before giving examples, we observe the connection between¨${h_{{r}}}({z})$ and the increasing enumeration of the set ${\mathrm{Div}}({z})$:

\[L:Enum\] Let ${z}$ be a positive braid and ${r}\ge
1$. Then ${h_{{r}}}({z})-1$ is the number of ${r}$-jumps in the increasing enumeration of ${({\mathrm{Div}}({z}),\nobreak{<}\nobreak)}$.

If the number of ${r}$-jumps in the increasing enumeration of ${\mathrm{Div}}({z})$ is ${N}_{r}-1$, we can extract from ${\mathrm{Div}}({z})$ a ${<}_{r}$-chain of length ${N}_{r}$. Conversely, assume that $({y}_0, \dots {y}_{{N}_{r}})$ is a ${<}_{r}$-chain in ${\mathrm{Div}}({z})$. Let ${z}_0 {<}\ldots {<}{z}_{N}$ be the increasing enumeration of ${\mathrm{Div}}({z})$. As ${<}_{r}$ refines ${<}$, there exists an increasing function $f$ of $\{0, \ldots,
{N}_{r}\}$ into $\{0, \ldots, {N}\}$ such that ${y}_i = {z}_{f(i)}$ holds for every $i$. Now the hypothesis ${z}_{f(i)} {<}_{r}{z}_{f(i+1)}$ implies that there exists at least one ${r}$-jump between ${z}_{f(i)}$ and ${z}_{f(i+1)}$. Indeed, by Lemma \[L:Index\], it is impossible that a concatenation of ${m}$-jumps with ${m}< {r}$ results in a ${r}$-jump. So the number of ${r}$-jumps in $({z}_0, \dots, {z}_{N})$ is at least ${N}_{r}$.

In other words, in order to determine¨${h_{{r}}}({z})$, there is no need to consider arbitrary chains: it is enough to consider the maximal chain obtained by enumerating ${\mathrm{Div}}({z})$ exhaustively.

\[X:Height\] Refining the increasing enumeration of¨${{\mathrm{Div}}({\Delta}_{3}^{})}$ given in Example¨\[X:List\] by indicating for each step the height of the corresponding jump, we obtain: $$\label{E:List31}
\tt 1 {<}_1 a {<}_2 b
{<}_1 ba
{<}_2 ab {<}_1 {\Delta}_3,$$ where we recall $\tt a, b, \dots$ stand for ${\sigma_{1}}, {\sigma_{2}}, \dots$. For instance, $\tt (ba, ab)$ is a $2$-jump, as we have $\tt
(ba){^{-1}}(ab) = ABab = AabA = bA$, a $\s$-positive decomposition with main generator ${\sigma_{2}}$. The number of $1$-jumps in , [[*i.e.*]{}]{}, the number of symbols ${<}_{r}$ with ${r}\ge 1$, is $5$, while the number of $2$-jumps is $2$, so, by Lemma¨\[L:Enum\], we deduce ${{h_{1}}({{\Delta}_{3}^{}})} = 6$ and ${{h_{2}}({{\Delta}_{3}^{}})} = 3$. Similarly, we obtain for¨${{\Delta}_{3}^{2}}$ $$\begin{gathered}
\tt 1 {<}_1 a {<}_1 aa {<}_2 b {<}_1 ba 
{<}_1 baa {<}_2 bb {<}_1 bba 
{<}_2 ab {<}_1
aba  {<}_1 abaa {<}_2 abb 
\\ \tt 
{<}_1 abba {<}_2
aab
{<}_1  aaba {<}_1 aabaa {<}_2 baab {<}_1 baaba
{<}_1 baabaa,\end{gathered}$$ leading to ${{h_{1}}({{\Delta}_{3}^{2}})} = 19$ and ${{h_{2}}({{\Delta}_{3}^{2}})} = 7$.

\[P:Decreasing\] $(i)$ For every braid ${z}$ in $B_{n}^+$, we have $${h_{1}}({z}) = {\mathtt{\#}}{\mathrm{Div}}({z})  \ge
{h_{2}}({z})
\ge \dots \ge {h_{{n}}}({z}) = 1.$$

$(ii)$ For all positive braids ${z}, {z}'$ and ${r}\ge 1$, we have $$\label{E:Addition}
{h_{{r}}}({z}{z}') \ge {h_{{r}}}({z}) + {h_{{r}}}({z}').$$

$(i)$ A ${<}_1$-chain is simply a ${<}$-chain, hence every subset of ${\mathrm{Div}}({z})$ gives such a chain. So the maximal ${<}_1$-chain in ${\mathrm{Div}}({z})$ is ${\mathrm{Div}}({z})$ itself, and ${h_{1}}({z})$ is the cardinality of ${\mathrm{Div}}({z})$.

On the other hand, no ${<}_{n}$-chain in $B_{n}^+$ has length more than $1$, as the main generator of a $\s$-positive ${n}$ strand braid word cannot be ${\sigma_{{n}}}$ or above. So ${h_{{n}}}({z})$ is $1$.

Then, for ${q}\le {r}$, every ${<}_{r}$-chain is a ${<}_{q}$-chain, which implies ${h_{{r}}}({z}) \ge {h_{{q}}}({z})$.

Point $(ii)$ is obvious, as the concatenation of two ${<}_{r}$-chains is a ${<}_{r}$-chain.

From  we deduce ${h_{{r}}}({z}^{d}) \ge {d}\cdot {h_{{r}}}({z})$ for all ${r}, {z}$. By Lemma¨\[L:Degree\], every divisor of ${{\Delta}_{{n}}^{{d}}}$ can be decomposed as the product of at most ${d}$ divisors of ${\Delta}_{n}$, and the latter are ${n}!$ in number, so we obtain the (coarse) bounds $${d}\cdot {{h_{{r}}}({{\Delta}_{{n}}^{}})} \le {{h_{{r}}}({{\Delta}_{{n}}^{{d}}})} \le
({n}!)^{d}$$ for all ${r}, {n}, {d}$. Better estimates will be given below.

Instead of restricting to subsets of $B_\infty$ of the form ${\mathrm{Div}}({z})$, we can define the complexity and the ${r}$-height for every (finite) set of braids ${X}$. Most general results extend, but, when ${X}$ is not closed under left division, nothing can be said about the number of ${\sigma_{{r}}}$’s involved in a ${r}$-jump. Considering such an extension is not useful here.

Connection with the complexity
------------------------------

We shall now connect the complexity¨${c}({z})$ with the numbers¨${h_{{r}}}({z})$ just defined. The result is simple:

\[P:MainHeight\] For ${z}$ a positive braid with main generator¨${\sigma_{{m}}}$, we have $${c}({z}) = {h_{{m}}}({z}) - 1.$$ In particular, for ${n}\ge 2$ and ${d}\ge 0$, we have $$\label{E:Complexity}
{{c}({{\Delta}_{{n}}^{{d}}})} = {{h_{{n}-1}}({{\Delta}_{{n}}^{{d}}})} - 1.$$

One inequality is easy:

\[L:MainHeight\] For ${z}$ a positive braid with main generator¨${\sigma_{{m}}}$, we have ${c}({z}) \le
{h_{{m}}}({z}) - 1$.

The argument is reminiscent of that used for Lemma \[L:Enum\], but requires a little more care. Assume that ${w}$ is a $\s$-positive word drawn in¨${\Gamma}({z})$ from¨${x}$ containing ${N}_{m}$¨occurrences of¨${\sigma_{{m}}}$. By Lemma¨\[L:Decomp\], we can assume ${x}= 1$ without loss of generality. Let ${z}_0
{<}{z}_1 {<}\dots {<}{z}_{N}$ be the increasing enumeration of¨${\mathrm{Div}}({z})$. By definition, all prefixes of¨${w}$ represent divisors of¨${z}$, so, letting¨$\ell$ be the length of¨${w}$, there exists a mapping $f : \{0,
\dots, \ell\} \to  \{0,
\dots, {N}\}$ such that, for each¨${k}$, the length¨${k}$ prefix of¨${w}$ represents¨${z}_{f({k})}$. By construction, we have $f(0) = 0$ and $f(\ell) = {N}$.

The difference with Lemma \[L:Enum\] is that $f$ need not be increasing. Now, let $p_1$, …, $p_{{N}_{m}}$ be the ${N}_{m}$ positions in¨${w}$ where the generator ${\sigma_{m}}$ occurs, completed with $p_0 = 0$. Then, in the prefix of¨${w}$ of length¨$p_1$, [[*i.e.*]{}]{}, in the subword of¨${w}$ corresponding to positions from¨$p_0+1$ to¨$p_1$, there is one¨${\sigma_{m}}$, plus letters¨${\sigma_{i}}^{\pm1}$ with $i <
m$ (Figure¨\[F:Jump\]). This subword is therefore $\s$-positive, hence we must have ${z}_{f(p_0)} {<}{z}_{f(p_1)}$, which requires $f(p_0) < f(p_1)$. Moreover, the quotient ${z}_{f(p_0)}{^{-1}}{z}_{f(p_1)}$ is a braid that admits at least one $\s$-positive expression containing¨${\sigma_{m}}$, hence ${z}_{f(p_0)}
{<}_{m}{z}_{f(p_1)}$ holds. Now the same is true between¨$f(p_1)$ and¨$f(p_2)$, [[*etc.*]{}]{} Hence the number of ${m}$-jumps in the increasing enumeration of ${\mathrm{Div}}({z})$ is at least ${N}_{m}$, [[*i.e.*]{}]{}, we have ${h_{{m}}}({z}) \ge
{N}_{m}+ 1$.

\[htb\]

(120,27)(0, -0) (0,2)[![Proof of Lemma \[L:MainHeight\]: the main generator ${\sigma_{{m}}}$ corresponds to the bold arrow: the function¨$f$ need not be increasing, but the projection of a bold arrow upstairs must include at least one bold arrow downstairs, [[*i.e.*]{}]{}, at least one ${m}$-jump.[]{data-label="F:Jump"}](Jump.eps "fig:")]{} (87,23)[almost-positive]{} (87,19)[expression]{} (102,15)[of¨${z}$]{} (87,5)[increasing ]{} (87,1)[enumeration of ${\mathrm{Div}}({z})$]{} (0,0)[${z}_0$]{} (10,0)[${z}_1$]{} (20,0)[${z}_2$]{} (24,0)[${<}_{m}$]{} (30,0)[${z}_3$]{} (40,0)[${z}_4$]{} (50,0)[${z}_5$]{} (54,0)[${<}_{m}$]{} (60,0)[${z}_6$]{} (70,0)[${z}_7$]{} (80,0)[${z}_8$]{} (2,9)[$\scriptstyle f(0)$]{} (12,9)[$\scriptstyle f(2)$]{} (22,9)[$\scriptstyle f(1)$]{} (32,9)[$\scriptstyle f(4)$]{} (42,9)[$\scriptstyle f(3)$]{} (62,9)[$\scriptstyle f(5)$]{} (62,12)[$\scriptstyle f(7)$]{} (72,9)[$\scriptstyle f(6)$]{}

It remains to prove the second inequality in Proposition \[P:MainHeight\], [[*i.e.*]{}]{}, to prove that, if ${z}$ is a positive ${n}$-braid satisfying ${h_{{m}}}({z}) = {N}+1$, then ${z}$ admits an almost-positive expression containing ${N}$ generators ${\sigma_{{m}}}$. The problem is as follows: if ${z}$ is a positive braid and ${x}, {y}$ are left divisors of ${z}$ satisfying ${x}{<}{y}$, then, by definition, the quotient ${x}{^{-1}}{y}$ admits some $\s$-positive expression ${w}$, but nothing [*a priori* ]{} guarantees that ${w}$ be drawn in ${\Gamma}({z})$. In other words, we might have ${x}{<}{y}$ but no $\s$-positive witness for this inequality inside ${\mathrm{Div}}({z})$. This however cannot happen, but the proof requires a rather delicate argument.

\[P:Handle\] Let ${z}$ be a positive braid. Then, for all ${x}, {y}$ in¨${\mathrm{Div}}({z})$, the following are equivalent:

$(i)$ The relation ${x}{<}{y}$ holds, [[*i.e.*]{}]{}, there exists a $\s$-positive path from ${x}$ to ${y}$ in the Cayley graph of $B_\infty$;

$(ii)$ There exists a $\s$-positive path from¨${x}$ to¨${y}$ in the Cayley graph of $B_{n}$;

$(iii)$ There exists a $\s$-positive path from¨${x}$ to¨${y}$ in¨${\Gamma}({z})$.

Clearly $(iii)$ implies¨$(ii)$, which implies¨$(i)$. We shall prove that $(i)$ implies $(iii)$—and thus reprove that $(i)$ implies $(ii)$, which was first proved in¨[@Lrb]—by using the handle reduction method of¨[@Dfo; @Dgr]. The problem is to prove that, among all $\s$-positive paths connecting¨${x}$ to¨${y}$ in the Cayley graph of¨$B_\infty$, at least one is drawn in ${\Gamma}({z})$.

Now, let ${u}, {v}$ be positive words representing ${x}$ and¨${y}$. Then the word¨${u}{^{-1}}{v}$ represents¨${x}{^{-1}}{y}$, and, by hypothesis, it is drawn in ${\Gamma}({z})$ from¨${x}$. Handle reduction is an operation that transforms a braid word into equivalent words and eventually produces a $\s$-positive word if it exists. It is proved in¨[@Dfo] that, for every ${n}$¨strand braid word¨${w}$, there exists a finite fragment¨${\Gamma}_{w}$ of the Cayley graph of $B_{n}^+$ and a vertex¨${x}_{w}$ of¨${\Gamma}_{w}$ such that ${w}$ and all words obtained from¨${w}$ by handle reduction are drawn from¨${x}_{w}$ in¨${\Gamma}_{w}$. Moreover, when ${w}$ has the form¨${u}{^{-1}}{v}$ with ${u}, {v}$ positive, then all vertices in¨${\Gamma}_{w}$ are the left divisors of the least common right multiple of the braids represented by¨${u}$ and¨${v}$, here ¨${x}$ and¨${y}$, while ${x}_{w}$ is the braid represented by¨${u}$, [[*i.e.*]{}]{},¨${x}$. As ${x}$ and¨${y}$ are divisors of¨${z}$, so is their least common right multiple, and the graph¨${\Gamma}_{w}$ is included in ¨${\Gamma}({z})$. It follows that every word obtained from¨${u}{^{-1}}{v}$ using handle reduction is drawn from¨${x}$ in¨${\Gamma}({z})$. The termination of handle reduction guarantees that, among these words, at least one is $\s$-positive, so $(iii)$ follows.

A direct application of Proposition \[P:Handle\] is the existence of $\s$-positive quotient-sequences drawn in the Cayley graph. The definition is as follows:

\[D:Witness\] Assume that ${z}$ is a positive braid and ${X}$ is a subset of ${\mathrm{Div}}({z})$. Let ${x}_0 {<}\dots {<}{x}_{N}$ be the increasing enumeration of ${X}$. We say that a sequence of words $\vec{w}= ({w}_1, \dots,
{w}_{N})$ is a [*quotient-sequence*]{} for ${X}$ if, for each ${k}$, the word ${w}_{k}$ is an expression of ${x}_{{k}-1}{^{-1}}{x}_{k}$ for each¨${k}$. We say that $\vec{w}$ is [*$\s$-positive*]{} if every entry in¨$\vec{w}$ is $\s$-positive, and that $\vec{w}$ is [*drawn in¨${\Gamma}({z})$*]{} (from¨${x}_0$) if ${w}_{k}$ is drawn from ${x}_{{k}-1}$ in ${\Gamma}({z})$ for each¨${k}$.

\[C:Witness\] Assume that ${z}$ is a positive braid. Then every subset of ${\mathrm{Div}}({z})$ admits a $\s$-positive quotient-sequence drawn in¨${\Gamma}({z})$.

\[X:Jump\] (Figure¨\[F:MaxPath\]) By computing the successive quotients in the increasing enumeration of¨${{\mathrm{Div}}({\Delta}_{3}^{2})}$ given in Example¨\[X:List\], we easily find that $$\tt (a, a, AAb, a, a, AAb, a, AAb, a, a, bAA, a,
bAA, a, a, bAA, a, a)$$ is a $\s$-positive quotient-sequence for ${\mathrm{Div}}({{\Delta}_{3}^{2}})$ drawn in¨${{\Gamma}({{\Delta}_{3}^{2}})}$. This sequence turns out to be the unique sequence with the above properties, but this uniqueness is specific to the case of $3$-braids ([*cf.*]{} Figure \[F:Decomp41\] below).

\[htb\]

(60,45)(0, -0) (0,0)[![The increasing enumeration of the divisors of¨${{\Delta}_{3}^{2}}$, and a $\s$-positive quotient-sequence drawn in¨${{\Gamma}({{\Delta}_{3}^{2}})}$: the associated path visits every vertex, and is labeled $\tt aaAAbaaAAbabAAaaAAbabAAaabAAaa$; it crosses $6$ ${\sigma_{2}}$-edges (and no ${\sigma_{2}}{^{-1}}$)[]{data-label="F:MaxPath"}](MaxPath32.eps "fig:")]{} (1,26)[$1$]{} (57,18)[${\Delta}_3^2$]{}

We can now easily complete the proof of Proposition \[P:MainHeight\]:

Let $({z}_0, \dots, {z}_{N})$ be the ${<}$-increasing enumerationof ${\mathrm{Div}}({z})$. By Corollary¨\[C:Witness\], there exists a $\s$-positive quotient-sequence¨$\vec{w}$ for¨${\mathrm{Div}}({z})$ that is drawn in¨${\Gamma}({z})$. Let ${w}=
{w}_1 \ldots {w}_{N}$. By construction, ${w}$ is a $\s$-positive word drawn in¨${\Gamma}({z})$, and the number of occurrences of the main generator¨${\sigma_{{m}}}$ in¨${w}$ is (at least) the number of ${m}$-jumps in¨$({z}_0, \dots,
{z}_{N})$. So we have ${c}({z}) \ge {h_{{m}}}({z})
-1$. Owing to Lemma¨\[L:MainHeight\], this completes the proof.

Assume that $\vec{w}$ is a $\s$-positive quotient-sequence for ${\mathrm{Div}}({z})$, and ${\sigma_{{m}}}$ is the main generator occurring in $\vec{w}$. Then each word ${w}_i$ contains zero or one letter ${\sigma_{{m}}}$. Indeed, if ${w}_i$ contained two ${\sigma_{{m}}}$’s or more, then the vertex reached after the first ${\sigma_{{m}}}$ ought to lie in the open ${<}$-interval determined by two successive entries of $\vec{z}$, and the latter is empty by construction since all elements of ${\mathrm{Div}}({z})$ occur in $\vec{z}$.

A decomposition result for ${({\mathrm{Div}}({z}),\nobreak{<}\nobreak)}$ {#S:Deter}
========================================================================

In this section, we establish a structural result describing $({{\mathrm{Div}}({\Delta}_{{n}}^{{d}})}, <)$ as the concatenation of ${{c}({{\Delta}_{{n}}^{{d}}})}+1$ intervals isomorphic to subsets of¨$({{\mathrm{Div}}({\Delta}_{{n}-1}^{{d}})}, <)$. We deduce an explicit formula connecting¨${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ with the number of braids in¨${{\mathrm{Div}}({\Delta}_{{n}}^{{d}})}$ whose ${d}$th factor is right divisible by¨${\Delta}_{r}$, which in turn enables us to complete the computation of¨${{c}({{\Delta}_{{n}}^{{d}}})}$ and¨${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ for small values of¨${r}$, ${n}$ and¨${d}$.

$B_{r}$-classes
---------------

In order to analyse the linearly ordered sets¨${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$, and, more generally, $({\mathrm{Div}}({z}), {<}\nobreak)$ for¨${z}$ a positive braid, we introduce convenient partitions. As $B_{r}$ is a group for each ${r}$, it is clear that the relation ${x}{^{-1}}{y}\in B_{r}$ defines an equivalence relation on (positive) braids, so we may put:

For ${r}\ge 1$ and ${x}, {y}$ in¨$B_\infty^+$, we say that ${x}$ and ${y}$ are [*$B_{r}$-equivalent*]{} if ${x}{^{-1}}{y}$ belongs to¨$B_{r}$.

By construction, $B_{r}$-equivalence is compatible with multiplication on the left. In the sequel, we consider the restriction of $B_{r}$-equivalence to finite subsets of $B_\infty^+$ of the form ${\mathrm{Div}}({z})$, [[*i.e.*]{}]{}, we use $B_{r}$-equivalence to partition ${\mathrm{Div}}({z})$ into subsets, naturally called $B_{r}$-classes.

As $B_1$ is trivial, $B_1$-equivalence is equality, and, therefore, the $B_1$-classes are singletons. On the other hand, any two elements of¨$B_{n}$ are $B_{r}$-equivalent for each¨${r}\ge n$, so, for ${z}$ in¨$B_{n}^+$, there is only one $B_{r}$-class for ${r}\ge
n$, and the only interesting relations arise for $1 < {r}< n$. For instance, ${{\mathrm{Div}}({\Delta}_{3}^{})}$ contains three $B_2$-classes, while ${{\mathrm{Div}}({\Delta}_{3}^{2})}$ contains seven of them (Figure¨\[F:Classes\]).

\[htb\]

(100,43)(0, -0) (0,0)[![The $B_2$-classes in¨${{\mathrm{Div}}({\Delta}_{3}^{})}$ and¨${{\mathrm{Div}}({\Delta}_{3}^{2})}$[]{data-label="F:Classes"}](Classes.eps "fig:")]{}

Saying that there is an ${r}$-jump between two braids¨${x}$ and¨${y}$ means that ${x}{^{-1}}{y}$ is $\s$-positive and does not belong to¨$B_{r}$, so, for ${x}{<}{y}$, we have the equivalence $$\label{E:Jump}
\big(\mbox{${x}, {y}$ are not
$B_{r}$-equivalent}\big)
\Longleftrightarrow
\left(
\begin{matrix}
\mbox{there is a ${r}$-jump between} \\
\mbox{between¨${x}$ and¨${y}$}
\end{matrix}
\right).$$

\[L:Interval\] Assume that ${z}$ is a positive braid. Then, each $B_{r}$-class in¨${\mathrm{Div}}({z})$ is an interval for¨${<}$ and there is an ${r}$-jump between each $B_{r}$-class and the next one.

Assume ${x}{<}{y}\in {\mathrm{Div}}({z})$. By , if ${x}$ and ${y}$ are not $B_{r}$-equivalent, there is an ${r}$-jump between¨${x}$ and¨${y}$, hence between¨${x}$ and any element of¨${\mathrm{Div}}({z})$ above¨${y}$, so no such element may be $B_{r}$-equivalent to¨${x}$. This implies that each $B_{r}$-class is an ${<}$-interval.

\[C:NbClasses\] For each ${r}\ge 1$, the number of $B_{r}$-classes in¨${\mathrm{Div}}({z})$ is¨${h_{{r}}}({z})$.

By¨, there is no ${r}$-jump between two elements of the same $B_{r}$-class, and there is one between two elements not in the same $B_{r}$-class. Thus the number of $B_{r}$-classes is the number of ${r}$-jumps in the ${<}$-increasing enumeration of¨${\mathrm{Div}}({z})$ augmented by¨$1$, hence, by Lemma \[L:Enum\], it is¨${h_{{r}}}({z})$.

$B_{r}$-equivalence provides a partition of¨$({\mathrm{Div}}({z}), {<})$ into finitely many subintervals. The interest of this partition is that we can describe $B_{r}$-classes rather precisely and, typically, connect them with subsets of¨$B_{r}$. In particular, this will allow for connecting the ordered sets¨${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$ with the sets¨$({{\mathrm{Div}}({\Delta}_{{n}-1}^{{d}})}, {<})$.

\[P:Lattice\] (Figure¨\[F:Decomp\]) Assume ${z}\in B_\infty^+$ and ${r}\ge 1$. Let ${C}$ be a $B_{r}$-class in¨${\mathrm{Div}}({z})$, and let ${a}, {b}$ be its ${<}$-extremal elements. Then ${a}$ divides every element of¨${C}$ on the left, and the left translation by¨${a}$ defines an isomorphism of $({\mathrm{Div}}({a}{^{-1}}{b}), {\preccurlyeq}, {<})$ onto¨$({C}, {\preccurlyeq},
{<})$. In particular, $({C}, {\preccurlyeq})$ is a lattice.

By Lemma¨\[L:Interval\], ${C}$ is the ${<}$-interval determined by¨${a}$ and¨${b}$, [[*i.e.*]{}]{}, we have $${C}= \{{x}\in {\mathrm{Div}}({z}) ; {a}{<}{x}{<}{b}\}.$$

We know that ${\mathrm{Div}}({z})$ is a lattice with respect to left divisibility: any two elements¨${x}, {y}$ of¨${\mathrm{Div}}({z})$ admit a greatest left common divisor, here denoted ${\mathrm{gcd}}({x}, {y})$, and a least common right multiple, denoted¨${\mathrm{lcm}}({x}, {y})$. Firstly, we claim that ${C}$ is a lattice with respect to left divisibility, [[*i.e.*]{}]{}, the left gcd and the right lcm of two elements of¨${C}$ lie in¨${C}$. So assume ${x}, {y}\in {C}$. Let ${x}_0,
{y}_0$ be defined by ${x}= {\mathrm{gcd}}({x}, {y})
{x}_0$ and ${y}= {\mathrm{gcd}}({x},
{y}) {y}_0$. The hypothesis that ${x}{^{-1}}{y}$ belongs to¨$B_{r}$ implies that there exist ${x}_1, {y}_1$ in¨$B_{r}^+$ satisfying ${x}{^{-1}}{y}= {x}_1{^{-1}}{y}_1$. By definition of the gcd, there must exist a positive braid¨${z}_1$ satisfying ${x}_1 = {z}_1 {x}_0$ and ${y}_1 = {z}_1 {y}_0$. Because ${z}_1$ is positive, ${x}_1 \in B_{r}^+$ implies ${x}_0 \in B_{r}^+$, hence ${\mathrm{gcd}}({x}, {y}) \in {C}$. As for the lcm, the conjunction of ${x}= {\mathrm{gcd}}({x},
{y})
{x}_0$ and ${y}= {\mathrm{gcd}}({x}, {y}) {y}_0$ implies $${\mathrm{lcm}}({x}, {y}) = {\mathrm{gcd}}({x},
{y}){\mathrm{lcm}}({x}_0, {y}_0).$$ As ${x}_0, {y}_0
\in B_{r}^+$ implies ${\mathrm{lcm}}({x}_0, {y}_0) \in
B_{r}^+$, we deduce ${\mathrm{lcm}}({x}, {y}) \in {C}$.

As ${C}$ is finite, it follows that ${C}$ admits a global gcd. Because the linear ordering¨${\le}$ extends the partial divisibility ordering¨${\preccurlyeq}$, this global gcd must be the ${<}$-minimum¨${a}$ of¨${C}$. Symmetrically, ${C}$ admits a global lcm, which must be the ${<}$-maximum¨${b}$. So, at this point, we know that ${a}$ is a left divisor of every element in¨${C}$, and ${b}$ is a right multiple of each such element, [[*i.e.*]{}]{}, we have $$\label{E:Inclusion}
{C}\ince \{{x}\in B_\infty^+ ; {a}{\preccurlyeq}{x}{\preccurlyeq}{b}\}.$$ Moreover, ${a}{\preccurlyeq}{x}{\preccurlyeq}{b}$ implies ${a}{\le}{x}{\le}{b}$, hence ${x}\in {C}$, so the inclusion in¨ is an equality.

Now, put $F({x}) = {a}{x}$ for¨${x}$ in¨${\mathrm{Div}}({a}{^{-1}}{b})$. As $B_\infty^+$ is left cancellative, $F$ is injective. Moreover, for ${x}$ a positive braid, ${x}{\preccurlyeq}{a}{^{-1}}{b}$ is equivalent to ${a}{x}{\preccurlyeq}{b}$, so the image of¨$F$ is $\{{x}\in B_\infty^+ ;
{a}{\preccurlyeq}{x}{\preccurlyeq}{b}\}$, hence is¨${C}$. Finally, by construction, $F$ preserves both¨${\preccurlyeq}$ and¨${<}$.

\[htb\]

(86,44)(0, 0) (2,0)[![Decomposition of $({\mathrm{Div}}({z}),
{<})$ into $B_{r}$-classes: each class¨$C$ is a lattice with respect to divisibility; the increasing enumeration of¨${\mathrm{Div}}({z})$ exhausts the first class, then jumps to the next one by an ${r}$-jump, [[*etc.*]{}]{} The number of classes is¨${h_{{r}}}({z})$.[]{data-label="F:Decomp"}](Decomp.eps "fig:")]{} (25,32)[$C$]{} (25,7)[$a$]{} (39,29)[$b$]{} (0,0)[$1$]{} (21,19)[${\sigma_{{r}}}$]{} (41,23)[${\sigma_{{r}}}$]{} (62,27)[${\sigma_{{r}}}$]{} (86,40)[${z}$]{}

For¨${r}= 1$, each $B_{r}$-class is a singleton, and Proposition¨\[P:Lattice\] says nothing; similarly, if the main generator of¨${z}$ is¨${\sigma_{{m}}}$, there is only one $B_{r}$-class for ${r}>
{m}$, and we gain no information. But, for $1 < {r}\le {m}$, and specially for ${r}=
{m}$, Proposition¨\[P:Lattice\] states that the chain¨${\mathrm{Div}}({z})$ is obtained by concatenating ${h_{{r}}}({z})$ copies of sets of the form¨${\mathrm{Div}}({z}')$ with¨${z}'$ of index at most¨${r}$. In particular, for ${z}= {{\Delta}_{n}^{{d}}}$, we have

\[C:Structure\] For each¨${n}$ and each¨${r}$ with ${r}< {n}$, the chain ${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$ is obtained by concatenating ${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ intervals, each of which, when equipped with¨${\preccurlyeq}$, is a translated copy of some initial sublattice of¨$({{\mathrm{Div}}({\Delta}_{{r}}^{{d}})}, {\preccurlyeq})$.

The case of¨${{\Delta}_{3}^{2}}$ and¨${{\Delta}_{4}^{}}$ are illustrated in Figures¨\[F:Decomp32\] and¨\[F:Decomp41\].

\[htb\]

(64,43)(0, 0) (2,0)[![Decomposition of ${({\mathrm{Div}}({\Delta}_{3}^{2}),\nobreak{<}\nobreak)}$ into $B_2$-classes: the increasing enumeration of¨${({\mathrm{Div}}({\Delta}_{3}^{2}),\nobreak{<}\nobreak)}$ is the concatenation of the increasing enumeration of the successive classes, separated by $2$-jumps (compare with Figure¨\[F:MaxPath\]); in this case, $B_2$-classes are simply chains with respect to divisibility[]{data-label="F:Decomp32"}](Decomp32.eps "fig:")]{} (1,25)[$1$]{} (63,20)[${{\Delta}_{3}^{2}}$]{}

\[htb\]

(104,48)(0, 0) (2,0)[![Decomposition of ${({\mathrm{Div}}({\Delta}_{4}^{}),\nobreak{<}\nobreak)}$ into $B_3$-classes; note that the ${\sigma_{3}}$-arrows (thick) corresponding to 3-jumps are not unique; in this case, all $B_3$-classes are isomorphic to the lattice $({{\mathrm{Div}}({\Delta}_{3}^{})}, {<}, {\preccurlyeq})$, [[*i.e.*]{}]{}, to the Cayley graph of¨${\Delta}_3$[]{data-label="F:Decomp41"}](Decomp41.eps "fig:")]{} (7,0)[$1$]{} (97,46)[${{\Delta}_{4}^{}}$]{}

Extremal elements
-----------------

The next step is to observe that extremal points in $B_{r}$-classes admit a simple characterization in terms of divisibility.

\[P:Extremal\] Assume that ${z}$ is a positive braid.

$(i)$ An element¨${x}$ of¨${\mathrm{Div}}({z})$ is the maximum of its $B_{r}$-class if and only if the relation ${x}{\sigma_{i}}
{\preccurlyeq}{z}$ fails for $1 \le i < {r}$.

$(ii)$ An element¨${x}$ of¨${\mathrm{Div}}({z})$ is the minimum of its $B_{r}$-class if and only if no¨${\sigma_{i}}$ with $1 \le i <
{r}$ divides¨${x}$ on the right.

$(i)$ The condition is necessary: if ${x}{\sigma_{i}}$ lies in¨${\mathrm{Div}}({z})$ for some¨$i$ with $i < {r}$, then ${x}{\sigma_{i}}$ lies in the same $B_{r}$-class as¨${x}$, and it is larger both for¨${\preccurlyeq}$ and¨${<}$, so ${x}$ cannot be maximal in its $B_{r}$-class. Conversely, assume that ${x}$ is not maximal in its $B_{r}$-class. Then there exists¨${y}$ satisfying ${x}{<}{y}$ and ${y}$ is $B_{r}$-equivalent to¨${x}$. Now, by Proposition¨\[P:Lattice\], the lcm of¨${x}$ and¨${y}$ is also $B_{r}$-equivalent to¨${x}$, which means that there exists¨${y}_1$ in¨$B_{r}^+$ satisfying ${\mathrm{lcm}}({x}, {y}) = {x}{y}_1$. Now ${x}{<}{y}$ implies ${y}_1 \not= 1$, so there must exist¨$i < m$ such that ${\sigma_{i}}$ is a left divisor of¨${y}_1$. Then we have ${x}{\sigma_{i}} {\preccurlyeq}{x}{y}_1 {\preccurlyeq}{z}$, hence ${x}{\sigma_{i}} {\preccurlyeq}{z}$.

$(ii)$ The argument is symmetric. If we have ${x}= 
{y}{\sigma_{i}}$ for some positive braid¨${y}$ and $i < {r}$, then ${y}$ belongs to the $B_{r}$-class of¨${x}$, and ${x}$ cannot be minimal in its $B_{r}$-class. Conversely, assume that ${x}$ is not minimal in its $B_{r}$-class. Then there exists¨${y}$ satisfying ${y}{<}{x}$ and ${y}$ is $B_{r}$-equivalent to¨${x}$. By Proposition¨\[P:Lattice\] again, the gcd of¨${x}$ and¨${y}$ is also $B_{r}$-equivalent to¨${x}$, which means that there exists¨${y}_0$ in¨$B_{r}^+$ satisfying ${\mathrm{gcd}}({x}, {y}) {y}_0 = {x}$. As ${y}{<}{x}$ implies ${y}_0 \not= 1$, there must exist¨$i < m$ such that ${\sigma_{i}}$ is a right divisor of¨${y}_0$, hence of¨${x}$.

When we apply the previous criterion to the braids¨${{\Delta}_{{n}}^{{d}}}$, we obtain:

\[P:MaxClass\] For ${x}$ in¨${{\mathrm{Div}}({\Delta}_{{n}}^{{d}})}$ and $1 \le
{r}\le {n}$, the following are equivalent:

$(i)$ The element¨${x}$ is ${<}$-maximal in its $B_{r}$-class;

$(ii)$ The element¨${x}{\sigma_{i}}$ belongs to¨${\mathrm{Div}}({{\Delta}_{{n}}^{{d}}})$ for no¨$i < {r}$;

$(iii)$ The ${d}$th factor of¨${x}$ is right divisible by¨${\Delta}_{r}$.

$(iv)$ The ${d}+1$st factor of¨${x}{\Delta}_{r}$ is¨${\Delta}_{r}$.

The equivalence of¨$(i)$ and¨$(ii)$ is given by Proposition¨\[P:Extremal\]$(i)$. It remains to establish the equivalence of¨$(ii)$–$(iv)$. For ${r}= 1$, $(ii)$ is vacuously true, while $(iii)$ and $(iv)$ always hold. So the expected equivalences are true. We henceforth assume ${r}\ge 2$.

Let ${x}$ belong to¨${{\mathrm{Div}}({\Delta}_{{n}}^{{d}})}$, and let ${x}_{d}$ be the ${d}$th factor in the normal form of¨${x}$. For $i < n$, saying that ${x}{\sigma_{i}}$ does not belong to¨${\mathrm{Div}}({{\Delta}_{{n}}^{{d}}})$ means that the normal form of¨${x}{\sigma_{i}}$ has length ${d}+1$, hence, equivalently, that the normal form of¨${x}_{d}{\sigma_{i}}$ has length¨$2$. This occurs if and only if ${\sigma_{i}}$ is a right divisor of¨${x}_{d}$. So, for ${r}\le n$, $(ii)$ is equivalent to ${x}_{d}$ being right divisible by all¨${\sigma_{i}}$’s with $1 \le i < {r}$, hence to ${x}_{d}$ being right divisible by the (left) lcm of these elements, which is¨${\Delta}_{r}$.

Finally, $(iii)$ and $(iv)$ are equivalent. Indeed, if the ${d}$th factor¨${x}_{d}$ in the normal form of¨${x}$ is divisible by¨${\Delta}_{r}$ on the right, then $({x}_{d}, {\Delta}_{r})$ is a normal sequence as no ${\sigma_{i}}$ with $i < {r}$ from¨${\Delta}_{r}$ may pass to¨${x}_{d}$. Hence $({x}_1, \ldots, {x}_{d}, {\Delta}_{r})$ is a normal sequence, necessarily the normal form of¨${x}{\Delta}_{r}$. Conversely, assume that the normal form of¨${x}{\Delta}_{r}$ is $({x}_1, \ldots, {x}_{d}, {\Delta}_{r})$. The hypothesis that $({x}_{d}, {\Delta}_{r})$ is normal implies that ${x}_{d}$ is divisible on the right by each¨${\sigma_{i}}$ with $i < {r}$, hence is divisible on the right by¨${\Delta}_{r}$. Now $({x}_1, \ldots,
{x}_{d})$ is the normal form of¨${x}$.

Observe that, for ${r}\ge 2$, an element of¨${{\mathrm{Div}}({\Delta}_{{n}}^{{d}})}$ that is ${<}$-maximal in its $B_{r}$-class cannot belong to¨${{\mathrm{Div}}({\Delta}_{{n}}^{{d}-1})}$, [[*i.e.*]{}]{}, cannot have degree ${d}-1$ or less, since the ${d}$th factor of its normal form cannot be¨$1$.

Similar conditions characterize the minimal elements of the $B_{r}$-classes. Because the normal form has a priviledged orientation, the results are not entirely symmetric of those of Proposition¨\[P:MaxClass\]

\[P:MinClass\] For ${x}$ in¨${{\mathrm{Div}}({\Delta}_{{n}}^{{d}})}$ and $1 \le
{r}\le {n}$, the following are equivalent:

$(i)$ The element¨${x}$ is ${<}$-minimal of its $B_{r}$-class;

$(ii)$ No¨${\sigma_{i}}$ with $i < {r}$ is a right divisor of¨${x}$;

$(iii)$ The degrees of¨${x}$ and¨${x}{\Delta}_{r}$ are equal.

The equivalence of¨$(i)$ and¨$(ii)$ is given by Proposition¨\[P:Extremal\]$(ii)$. On the other hand, everything is obvious for¨${r}= 1$. So it remains to establish the equivalence of¨$(ii)$ and¨$(iii)$ in the case ${r}\ge 2$. Now, assume that¨$(ii)$ holds an ${x}$ has degree¨${d}$. The hypothesis that ${\sigma_{i}}$ is not a right divisor of¨${x}$ implies that ${x}{\sigma_{i}}$ is a divisor of¨${{\Delta}_{{n}}^{{d}}}$. As this holds for each $i <
{r}$, the lcm of ${x}{\sigma_{1}}$, …, ${x}{\sigma_{{r}-1}}$, which is ${x}{\Delta}_{r}$, also divides¨${{\Delta}_{{n}}^{{d}}}$, which means that ${x}{\Delta}_{r}$ has degree (at most)¨${d}$. So $(ii)$ implies¨$¨(iii)$.

Conversely, assume that ${\sigma_{i}}$ divides¨${x}$ on the right. Then the degree of¨${x}{\sigma_{i}}$ is strictly larger than that of¨${x}$, and, [*a fortiori*]{}, the same is true for¨${x}{\Delta}_{r}$.

Determination of¨${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$
------------------------------------------------------

A direct application of the previous results is a formula connecting the number of $B_{r}$-classes in¨${\mathrm{Div}}({{\Delta}_{{n}}^{{d}}})$, [[*i.e.*]{}]{}, the numbers¨${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$, with the number of braids whose normal form ends with some specific factor.

For ${n}, {d}\ge 1$ and for¨${s}$ a simple ${n}$-braid, we denote by¨${b_{{n},{d}}({s})}$ the number of positive braids of degree at most¨${d}$, [[*i.e.*]{}]{}, of divisors of¨${{\Delta}_{{n}}^{{d}}}$, whose ${d}$th factor is¨${s}$.

\[P:Main\] For $1 \le {r}\le {n}$, we have $$\label{E:Main}
{{h_{{r}}}({{\Delta}_{{n}}^{{d}}})} = \sum_{\mbox{\Small $s$ right divisible by
${\Delta}_{r}$}} {b_{{n},{d}}(s)}  = {b_{{n},{d}+1}({\Delta}_{r})} .$$

In words: The number of ${r}$-jumps in ${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$ is the number of ${n}$-braids of degree at most¨${d}$ whose ${d}$th factor is right divisible by¨${\Delta}_{r}$.

By Corollary¨\[C:NbClasses\], ${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ is the number of $B_{r}$-classes in¨${\mathrm{Div}}({{\Delta}_{{n}}^{{d}}})$. Each class contains exactly one maximum element, and, by Proposition¨\[P:MaxClass\], the latter are characterized by the property that their ${d}$th factor is right divisible by¨${\Delta}_{r}$. The first equality in¨ follows. The second one follows from the equivalence of¨$(iii)$ and¨$(iv)$ in Proposition¨\[P:MaxClass\].

For ${r}= 1$, as every simple braid is divisible by¨$1$ on the right, Relation¨ reduces to $$\label{E:MainOne}
{{h_{1}}({{\Delta}_{{n}}^{{d}}})} = \sum_{{s}} {b_{{n},{d}}({s})} = {b_{{n},{d}+1}(1)},$$ a special case of the relation ${h_{1}}({z}) =
{\mathtt{\#}}{\mathrm{Div}}({z})$ of Proposition¨\[P:Decreasing\]. For ${r}= {n}$, as the only normal sequence of length¨${d}$ that finishes with¨${\Delta}_{n}$ is $({\Delta}_{n},
\dots, {\Delta}_{n})$, Relation¨ reduces to $$\label{E:Mainn}
{{h_{{n}}}({{\Delta}_{{n}}^{{d}}})} = 1,$$ also noted in Proposition¨\[P:Decreasing\]. Finally, for ${r}= {n}-1$, we obtain using Proposition¨\[P:MainHeight\]:

\[C:Main\] For ${n}\ge 2$, we have $$\label{E:MainNO}
{{c}({{\Delta}_{{n}}^{{d}}})} = {{h_{{n}- 1}}({{\Delta}_{{n}}^{{d}}})} -1 = \sum_{i =
2}^{{n}}
{b_{{n},{d}}({\sigma_{i}} {\sigma_{i+1}} \dots {\sigma_{{n}-1}}{\Delta}_{{n}- 1})} =
{b_{{n},{d}+1}({\Delta}_{{n}- 1})} - 1.$$

The simple ${n}$-braids that are right divisible by¨${\Delta}_{{n}-1}$ are the braids of the form ${\sigma_{i}} {\sigma_{i+1}} \dots {\sigma_{{n}-1}}$ with $1 \le i\le
{n}$. Indeed, it is clear that every such braid is simple and right divisible by¨${\Delta}_{{n}-1}$. Conversely, the only possibility for ${z}{\Delta}_{{n}-1}$ to be simple is that ${z}$ moves the ${n}$th strand to some position between¨$1$ and¨${n}$, but introduces no crossing between the remaining strands. Finally, ${\sigma_{1}} {\sigma_{2}} \dots {\sigma_{{n}-1}}{\Delta}_{{n}-1}$ is¨${\Delta}_{n}$, and we already observed that ${b_{{n},{d}}({\Delta}_{n})}$ is¨$1$, so we obtain the first equality in¨.

Computation of¨${b_{{n},{d}}({s})}$
-----------------------------------

By Lemma¨\[L:Normal\], normal sequences are characterized by a local condition involving only pairs of consecutive elements. It follows that the set of all normal sequences is a rational set, [[*i.e.*]{}]{}, it can be recognized by a finite state automaton. Standard arguments then show that the numbers¨${b_{{n},{d}}({s})}$ obey a linear recurrence. Building on this observation, seemingly first used in the case of braids in¨[@Chb], we can obtain explicit formulas for the parameters¨${{c}({{\Delta}_{{n}}^{{d}}})}$ and¨${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ for small values of¨${r}$, ${n}$, and/or¨${d}$. We shall not go into details in the current paper, and refer to¨[@Dhi] where all formulas are established—and where, more generally, the rich combinatorics underlying the normal form of braids is investigated.

In the sequel, we write $(M)_{{x}, {y}}$ for the $({x},
{y})$-entry of a matrix¨$M$. The general principle for computing the numbers¨${b_{{n},{d}}({s})}$ for some fixed¨${n}$ is as follows:

\[L:Comput\] For ${n}\ge 1$, let $M_{n}$ be the square matrix with entries indexed by simple ${n}$-braids defined by $$(M_{n})_{{s}, {t}} = 
\begin{cases}
1 & \mbox{if $({s}, {t})$ is normal,}\\
0 & \mbox{otherwise.}
\end{cases}$$ Then, for every simple¨${t}$ and every ${d}\ge 1$, we have ${b_{{n},{d}}({t})} = ((1, 1, \dots, 1)
\, M_{n}\!\!\!{}^{{d}-1})_{t}$.

The proof is an easy induction on¨${d}$.

The matrix¨$M_1$ is $(1)$, corresponding to ${b_{1,{d}}(1)} = 1$. For ${n}=2$, using the enumeration $(1,
{\sigma_{1}})$ of simple $2$-braids, we find $M_2 = 
\left(\begin{matrix}1&0\\1&1\end{matrix}\right)$, leading to ${b_{2,{d}}(1)} = {d}$, ${b_{2,{d}}({\sigma_{1}})} = 1$, as could be expected: there are ${d}+1$ braids of degree at most¨${d}$, namely the braids¨${\sigma_{1}}^{e}$ with ${e}< {d}$, whose ${d}$th factor is¨$1$, and ${\sigma_{1}}^{d}$, whose ${d}$th factor is¨${\Delta}_2$, [[*i.e.*]{}]{}, ¨${\sigma_{1}}$. For ${n}= 3$, using the enumeration $(1, {\sigma_{1}},
{\sigma_{2}},{\sigma_{2}}{\sigma_{1}}, {\sigma_{1}}{\sigma_{2}}, {\Delta}_3)$ of simple $3$-braids, we obtain $$M_3 = \left(
\begin{matrix}
1&0&0&0&0&0\\
1&1&0&0&1&0\\
1&0&1&1&0&0\\
1&1&0&0&1&0\\
1&0&1&1&0&0\\
1&1&1&1&1&1
\end{matrix}
\right),$$ from which we can deduce for instance ${b_{3,3}(1)}= 19$ or ${b_{3,4}({\sigma_{1}})} = 15$ using Lemma¨\[L:Comput\].

Using Proposition¨\[P:Main\], we deduce

\[P:Values\] With $M_{n}$ as in Lemma¨\[L:Comput\], we have for ${n}\ge {r}\ge 1$ and ${d}\ge 1$ $$\begin{gathered}
{{c}({{\Delta}_{{n}}^{{d}}})} = ((1, 1, \dots, 1) \, M_{n}^{d})_{{\Delta}_{{n}-1}}
- 1,\\
{{h_{{r}}}({{\Delta}_{{n}}^{{d}}})} = ((1, 1, \dots, 1) \,
M_{n}^{d})_{{\Delta}_{{r}}}.\end{gathered}$$

$(i)$ For fixed¨${n}, {r}$, the generating functions for the sequences ${{c}({{\Delta}_{{n}}^{{d}}})}$ and ${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ are rational.

$(ii)$ For fixed¨${n}, {r}$, the numbers ${{c}({{\Delta}_{{n}}^{{d}}})}$ and ${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ admit expressions of the form $$\label{E:General}
P_1({d}) {\rho}_1^{d}+ \cdots +
P_{k}({d}) {\rho}_{k}^{d}.$$ where ${\rho}_1$, …, ${\rho}_{k}$ are the non-zero eigenvalues of¨$M_{n}$ and $P_1, \dots,
P_{k}$ are polynomials with $\deg(P_{i})$ at most the multiplicity of¨${\rho}_{i}$ for¨$M_{n}$.

As the matrix¨$M_{n}$ is an ${n}! \times {n}!$ matrix, completing the computation is not so easy, even for small values of¨${n}$. Actually, it is shown in¨[@Dhi] how to replace¨$M_{n}$ with a smaller matrix¨$\overline
M_{n}$ of size $p({n}) \times p({n})$, where $p({n})$ is the number of partitions of¨${n}$. The property is connected with classical results by Solomon about the descents of permutations¨[@Sol]. With such methods, one easily obtains the values listed in Table¨\[T:Values\].

$$

                               ${d}$                                 0     1       2         3           4             5               6
  ---------------------------------------------------------------- --- ----- ------- --------- ----------- ------------- ---------------
   width0pt height12pt depth6pt ${{h_{1}}({{\Delta}_{2}^{{d}}})}$    1     2       3         4           5             6               7
       width0pt height12pt ${{h_{1}}({{\Delta}_{3}^{{d}}})}$         1     6      19        48         109           234             487
        width0pt depth6pt ${{h_{2}}({{\Delta}_{3}^{{d}}})}$          1     3       7        15          31            63             127
       width0pt height12pt ${{h_{1}}({{\Delta}_{4}^{{d}}})}$         1    24     211      1380        8077         45252          249223
                 ${{h_{2}}({{\Delta}_{4}^{{d}}})}$                   1    12      83       492        2765         15240           83399
        width0pt depth6pt ${{h_{3}}({{\Delta}_{4}^{{d}}})}$          1     4      15        64         309          1600            8547
       width0pt height12pt ${{h_{1}}({{\Delta}_{5}^{{d}}})}$         1   120    3651     79140     1548701      29375460       551997751
                 ${{h_{2}}({{\Delta}_{5}^{{d}}})}$                   1    60    1501     30540      585811      11044080       207154921
                 ${{h_{3}}({{\Delta}_{5}^{{d}}})}$                   1    20     311      5260       94881       1755360        32741851
        width0pt depth6pt ${{h_{4}}({{\Delta}_{5}^{{d}}})}$          1     5      31       325        4931         86565         1590231
       width0pt height12pt ${{h_{1}}({{\Delta}_{6}^{{d}}})}$         1   720   90921   7952040   634472921   49477263360   3836712177121
                 ${{h_{2}}({{\Delta}_{6}^{{d}}})}$                   1   360   38559   3228300   254718389   19808530620   1535016069499
                 ${{h_{3}}({{\Delta}_{6}^{{d}}})}$                   1   120    8727    649260    49654757    3831626580    296361570667
                 ${{h_{4}}({{\Delta}_{6}^{{d}}})}$                   1    30    1075     61620     4387195     332578230     25612893355
                 ${{h_{5}}({{\Delta}_{6}^{{d}}})}$                   1     6      63      1956      116423       8448606       643888543

  : First values of ${{h_{{r}}}({{\Delta}_{{n}}^{{d}}})}$ for $1 \le {r}< {n}$—the value is¨$1$ for ${r}\ge {n}$. For instance, we read that the number of $3$-strand braids of degree at most¨$2$, [[*i.e.*]{}]{}, ${{h_{1}}({{\Delta}_{3}^{2}})}$, is¨$19$—as was seen in Example¨\[X:Height\]—while the maximal number of¨${\sigma_{3}}$’s in a $\s$-positive word drawn in¨${{\Gamma}({{\Delta}_{4}^{4}})}$, [[*i.e.*]{}]{}, ${{c}({{\Delta}_{4}^{4}})}$, which is ${{h_{3}}({{\Delta}_{4}^{4}})}-1$ according to Proposition¨\[P:MainHeight\], is¨$308$.[]{data-label="T:Values"}

$$

Using the reduced matrices $\overline M_3 = \left(\begin{matrix}1&0&0\\4&2&0\\1&1&1
\end{matrix}\right)$ and $\overline M_4 =
\left(\begin{matrix}1&0&0&0&0\\11&4&1&0&0\\5&3&2&1&0\\
6&4&2&2&0\\1&1&1&1&1
\end{matrix}\right)$, we obtain the following explicit form for¨ involving the non-zero eigenvalues of¨$M_3$, namely $1$ (double), $2$ and of¨$M_4$, namely $1$ (double), $2$, and $3 \pm
\sqrt6$:

\[P:Values34\] Let ${\rho}_1 = 3 + \sqrt{6}$ and ${\rho}_2 = 3 - \sqrt{6}$. Then, for ${d}\ge 1$, we have $$\begin{aligned}
{{h_{1}}({{\Delta}_{3}^{{d}}})} &= 8\cdot 2^{d}- 3 {d}- 7,\\
{{h_{2}}({{\Delta}_{3}^{{d}}})} &= {{c}({{\Delta}_{3}^{{d}}})}+1 = 2 \cdot 2^{d}- 1,\\
{{h_{1}}({{\Delta}_{4}^{{d}}})} &= 
\frac3{20}(32 + 13\sqrt6) {\rho}_1^{d}+ \frac3{20}(32 - 13\sqrt6) {\rho}_2^{d}- \frac{128}5 \cdot\, 2^{d}+  6{d}+ 17,\\
{{h_{2}}({{\Delta}_{4}^{{d}}})} &= 
\frac1{20}(32 + 13\sqrt6) {\rho}_1^{d}+ \frac1{20}(32 - 13\sqrt6) {\rho}_2^{d}- \frac{16}5 \cdot\, 2^{d}+ 1,\\
{{h_{3}}({{\Delta}_{4}^{{d}}})} &= {{c}({{\Delta}_{3}^{4}})} +1 = 
\frac1{20}(4 + \sqrt6) {\rho}_1^{d}+ \frac1{20}(4 - \sqrt6) {\rho}_2^{d}+ \frac85 \cdot\, 2^{d}- 1.\end{aligned}$$

The main interest of the above formulas are to show that each of the involved parameters has an exponential growth with respect to¨${d}$, in $O(2^{d})$ for ${n}= 3$, and in $O((3+\sqrt{6})^{d})$ for ${n}= 4$. For practical purposes, it may be more convenient to resort to inductive formulas, for instance $$\begin{gathered}
\label{E:Recur3}
{{h_{1}}({{\Delta}_{3}^{{d}}})} = 2 {{h_{1}}({{\Delta}_{3}^{{d}-1}})} + 3 {d}+ 1,\\
\label{E:Recur4}
{{h_{1}}({{\Delta}_{4}^{{d}}})} = 6{{h_{1}}({{\Delta}_{4}^{{d}-1}})} - 3{{h_{1}}({{\Delta}_{4}^{{d}-2}})}
+ 32 \cdot 2^{d}- 12 {d}- 34,\end{gathered}$$ together with initial values ${{h_{1}}({{\Delta}_{3}^{0}})} = {{h_{1}}({{\Delta}_{4}^{0}})} = 1$, ${{h_{1}}({{\Delta}_{4}^{1}})} = 24$ (or ${{h_{1}}({{\Delta}_{4}^{-1}})}= 0$).

Small values of¨${d}$
---------------------

Another approach is to keep¨${d}$ fixed and let¨${n}$ vary. Once again, we only mention a few results, and refer the reader to¨[@Dhi] for the proofs and additional comments. For ${d}= 1$, it is easy to determine all values:

\[[@Dhi]\] For ${n}\ge {r}\ge 1$, we have $$\label{E:K1}
{{h_{{r}}}({{\Delta}_{{n}}^{}})} = \frac{{n}!}{{r}!}.$$

For ${d}= 2$, it is easier to complete the computation for ${n}- {r}$ rather than¨${r}$ fixed.

\[[@Dhi]\] \[P:K2\] For ${n}\ge {r}\ge 1$, we have $$\begin{aligned}
{{h_{{n}-{r}}}({{\Delta}_{{n}}^{2}})} 
&= {r}!\,({r}+1)^{n}+ \sum_{i = 1}^{r}P_i({n}) \,
i^{{n}-{r}+i-1},\\
\intertext{for some polynomial $P_i$ of degree at
most¨${r}- i + 1$. The values for ${r}=
1, 2$ are}
{{h_{{n}-1}}({{\Delta}_{{n}}^{2}})} &= 2^{n}- 1, \\
{{h_{{n}-2}}({{\Delta}_{{n}}^{2}})} &= 2 \cdot 3^{n}- ({n}+ 6) \cdot
2^{{n}-1} + 1.\end{aligned}$$

For ${r}$ fixed, no general formula is known. Let us mention the case of¨${{h_{1}}({{\Delta}_{{n}}^{2}})}$, which follows from results of¨[@CSV]:

\[[@Dhi]\] The numbers¨${{h_{1}}({{\Delta}_{{n}}^{2}})}$ are determined by the induction $${{h_{1}}({{\Delta}_{0}^{2}})}=1, \qquad 
{{h_{1}}({{\Delta}_{{n}}^{2}})} = \sum_{{i}=0}^{{n}-1} (-1)^{{n}+ {i}+1} {{n}\choose {i}}^2 
{{h_{1}}({{\Delta}_{{i}}^{2}})}.$$ Their double exponential generating function is, with $J_0({x})$ is the Bessel function, $$\sum_{{n}= 0}^\infty {{h_{1}}({{\Delta}_{{n}}^{2}})}
\frac{z^{n}}{{n}!^2} = 
\bigg( \sum_{{n}= 0}^\infty (-1)^{n}\frac{z^{n}}{{n}!^2}
\bigg){^{-1}}= \frac1{J_0(\sqrt{z})}.$$

Finally, for ${d}= 3$, the computation can be completed at least in the case ${n}- {r}= 1$:

\[[@Dhi]\] For¨${n}\ge 1$, we have, with $e = \exp(1)$, $$\label{E:KKK3}
{{h_{{n}-1}}({{\Delta}_{{n}}^{3}})} = \sum_{{i}=0}^{{n}-1}
\frac{{n}!}{{i}!} = \lfloor{n}! e\rfloor - 1.$$

Using Proposition¨\[P:MainHeight\], we deduce the following explicit values for ${{c}({{\Delta}_{{n}}^{{d}}})}$, [[*i.e.*]{}]{}, for the maximal number of occurrences of¨${\sigma_{{n}-1}}$ is a $\s$-positive word drawn in the Cayley graph of¨${{\Delta}_{{n}}^{{d}}}$: $${{c}({{\Delta}_{{n}}^{}})} = {n}- 1, \qquad
{{c}({{\Delta}_{{n}}^{2}})} = 2^{n}- 2, \qquad
{{c}({{\Delta}_{{n}}^{3}})} = \sum_{{i}=0}^{{n}-1}
\frac{{n}!}{{i}!} - 1 = \lfloor{n}! e\rfloor - 2.$$ The formulas listed above show that a number of different induction schemes appear, suggesting that the combinatorics of normal sequences of braids is very rich.

A complete description of ${({\mathrm{Div}}({\Delta}_{3}^{{d}}),\nobreak{<}\nobreak)}$ {#S:N3}
======================================================================================

Our ultimate goal would be a complete description of each chain ${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$, this typically meaning that we are able to explicitly specify the increasing enumeration of its elements. This goal remains out of reach in the general case, but we shall show now how the process can be completed in the case ${n}= 3$. The counting formulas of Section¨\[S:Deter\] play a key role in the construction, and, in particular, the Pascal triangle of Table¨\[T:Triangle\] below is directly connected with the $2^{d}$¨factor in the inductive formulas of Proposition¨\[P:Values34\]. As an application, we deduce a new proof of Property¨C and of the well-ordering property, hence a complete re-construction of the braid ordering in the case ${n}= 3$.

The general principle is to make the decomposition of Corollary¨\[C:Structure\] explicit. The latter shows that, for all¨${n}$ and¨${d}$, the chain ${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$ can be decomposed into ${{c}({{\Delta}_{{n}}^{{d}}})}$¨subintervals each of which is a copy of some fragment of¨${({\mathrm{Div}}({\Delta}_{{n}-1}^{{d}}),\nobreak{<}\nobreak)}$. Moreover, the approach of Section¨\[S:Deter\] suggests an induction on¨${d}$ as well, so, finally, we are led to looking for a description of¨${({\mathrm{Div}}({\Delta}_{{n}}^{{d}}),\nobreak{<}\nobreak)}$ in terms of¨${({\mathrm{Div}}({\Delta}_{{n}-1}^{{d}}),\nobreak{<}\nobreak)}$ and¨${({\mathrm{Div}}({\Delta}_{{n}}^{{d}-1}),\nobreak{<}\nobreak)}$—[[*i.e.*]{}]{}, in the current case, a description of ${({\mathrm{Div}}({\Delta}_{3}^{{d}}),\nobreak{<}\nobreak)}$ in terms of ${({\mathrm{Div}}({\Delta}_{2}^{{d}}),\nobreak{<}\nobreak)}$ and ${({\mathrm{Div}}({\Delta}_{3}^{{d}-1}),\nobreak{<}\nobreak)}$.

The braids¨${\delta_{{n},{p}}}$
-------------------------------

The subsequent construction will appeal to a double series of braid called¨${\delta_{{n},{p}}}$, and we begin with a few preliminary properties of these braids.

For ${n}\ge 2$, let ${\sigma_{{n}, 1}}$ and ${\sigma_{1, {n}}}$ respectively denote the braid words ${\sigma_{{n}-1}} {\sigma_{{n}-2}} \dots {\sigma_{1}}$ and ${\sigma_{1}} {\sigma_{2}}
\dots {\sigma_{{n}-1}}$. For ${p}\ge 0$, we define ${\widetilde\delta_{{n},{p}}}$ to be (the braid represented by) the length¨${p}$ prefix of the right infinite word¨$({\sigma_{{n}, 1}}{\sigma_{1, {n}}})^\infty$, and ${\delta_{{n},{p}}}$ to be (the braid represented by) the length¨${p}$ suffix of the left infinite word¨$^\infty({\sigma_{{n}, 1}}{\sigma_{1, {n}}})$.

For instance, we find ${\delta_{3,0}} = 1$, ${\delta_{3,1}} = {\mathtt{b}}$, ${\delta_{3,2}} = {\mathtt{a}}{\mathtt{b}}$, …, ${\delta_{3,4}} = {\mathtt{b}}{\mathtt{a}}{\mathtt{a}}{\mathtt{b}}$, …, ${\delta_{3,7}} = {\mathtt{a}}{\mathtt{a}}{\mathtt{b}}{\mathtt{b}}{\mathtt{a}}{\mathtt{a}}{\mathtt{b}}$, [[*etc.*]{}]{}Similarly, we have ${\delta_{4,6}} = {\mathtt{c}}{\mathtt{b}}{\mathtt{a}}{\mathtt{a}}{\mathtt{b}}{\mathtt{c}}$, and, more generally, ${\delta_{{n},2{n}-2}} = {\widetilde\delta_{{n},2{n}-2}}= {\sigma_{{n},
1}}{\sigma_{1, {n}}}$. Note that, as a word, ${\delta_{{n},{p}}}$ is obtained by reversing the order of the letters in¨${\widetilde\delta_{{n},{p}}}$.

For ${n}\ge 2$ and ${p}, {q}\ge 0$ satisfying ${p}+ {q}= {d}({n}-1)$, we have $$\label{E:Deltadelta}
{\delta_{{n},{p}}} \, {{\Delta}_{{n}-1}^{{d}}} \, {\widetilde\delta_{{n},{q}}} = {{\Delta}_{{n}}^{{d}}}.$$

We first prove using induction on¨${d}$ the relation $$\label{E:Deltak0}
{\delta_{{n},{d}({n}-1)}} \, {{\Delta}_{{n}-1}^{{d}}} = {{\Delta}_{{n}}^{{d}}},$$ [[*i.e.*]{}]{}, with ${q}=
0$. For ${d}= 0$, reduces to $1 =
1$. Assume ${d}\ge 1$. By definition, ${\delta_{{n},{d}({n}-1)}}$ is ${\sigma_{{n},1}} \, 
{\delta_{{n},({d}-1)({n}-1)}}$ for ${d}$¨odd, and is ${\sigma_{1, {n}}} \,
{\delta_{{n},({d}-1)({n}-1)}}$ for ${d}$¨even, so, in any case, we can write $${\delta_{{n},{d}({n}-1)}} = {\phi_{{n}}}^{{d}-1}({\sigma_{1, {n}}}) \,
{\delta_{{n},({d}-1)({n}-1)}},$$ where we recall ${\phi_{{n}}}$ denotes the flip automorphism of¨$B_{n}$ that exchanges¨${\sigma_{i}}$ and ${\sigma_{{n}- i}}$. Using the induction hypothesis and¨, we find $$\begin{aligned}
{\delta_{{n},{d}({n}-1)}} \, {{\Delta}_{{n}-1}^{{d}}} 
&= {\phi_{{n}}}^{{d}-1}({\sigma_{1, {n}}}) \, {\delta_{{n},({d}-1)({n}-1)}} \,
{{\Delta}_{{n}-1}^{{d}-1}} \, {\Delta}_{{n}-1}\\
&= {\phi_{{n}}}^{{d}-1}({\sigma_{1, {n}}}) \, {{\Delta}_{n}^{{d}-1}} \, {\Delta}_{{n}-1}
= {{\Delta}_{n}^{{d}-1}} \, {\sigma_{1, {n}}} \, {\Delta}_{{n}-1}
= {{\Delta}_{n}^{{d}-1}} \, {\Delta}_{n}= {{\Delta}_{{n}}^{{d}}}.\end{aligned}$$

We return to the general case of¨. For ${d}$ even, we have ${\delta_{{n},{d}({n}-1)}} = {\widetilde\delta_{n,{d}({n}-1)}}$, hence ${\widetilde\delta_{{n},{q}}} \, {\delta_{{n},{p}}} = {\delta_{{n},{d}({n}-1)}}$. If ${d}$ is odd, we have ${\delta_{{n},{d}({n}-1)}} =
{\phi_{{n}}}({\widetilde\delta_{n,{d}({n}-1)}})$, which implies ${\phi_{{n}}}({\widetilde\delta_{{n},{q}}}) \, {\delta_{{n},{p}}} = {\delta_{{n},{d}({n}-1)}}$. So ${\phi_{{n}}}^{d}({\widetilde\delta_{{n},{q}}}) \, {\delta_{{n},{p}}} = {\delta_{{n},{d}({n}-1)}}$ holds in both cases. Now, using¨, we find $$\begin{aligned}
{\phi_{{n}}}({\widetilde\delta_{{n},{q}}}) \, {\delta_{{n},{p}}} \, {{\Delta}_{{n}-1}^{{d}}} \, {\widetilde\delta_{{n},{q}}}
&= {\delta_{{n},{d}({n}-1)}} \, {{\Delta}_{{n}-1}^{{d}}} \, {\widetilde\delta_{{n},{q}}}
= {{\Delta}_{{n}}^{{d}}} \, {\widetilde\delta_{{n},{q}}}
= {\phi_{{n}}}({\widetilde\delta_{{n},{q}}}) \, {{\Delta}_{{n}}^{{d}}},\end{aligned}$$ from which we deduce¨ by cancelling ${\phi_{{n}}}({\widetilde\delta_{{n},{q}}})$ on the left.

For $1 \le i \le {n}-2$ we have $$\label{E:Commut}
{\delta_{{n},{d}({n}-1)}} \, {\sigma_{i}} = {\sigma_{i+e}} \,
{\delta_{{n},{d}({n}-1)}}$$ with $e = 0$ if ${d}$ is even, and $e = 1$ if ${d}$ is odd.

For $1 \le i \le {n}-2$, we have $${\sigma_{1,n}} \, {\sigma_{i}} = {\sigma_{i+1}} \, {\sigma_{1,n}},
\mbox{\quad and \quad}
{\sigma_{{n}, 1}} \, {\sigma_{i+1}} = {\sigma_{i}} \, {\sigma_{{n}, 1}},$$ as an easy induction shows. This implies ${\sigma_{{n},1}} \, {\sigma_{1,n}} \, {\sigma_{i}} = {\sigma_{i}} \,
{\sigma_{{n},1}} \, {\sigma_{1,n}}$, and therefore $({\sigma_{{n},1}}
\, {\sigma_{1,n}})^{d}\, {\sigma_{i}} = {\sigma_{i}} \,
({\sigma_{{n},1}} \, {\sigma_{1,n}})^{d}$, [[*i.e.*]{}]{}, ${\delta_{{n},2{d}({n}-1)}} \, {\sigma_{i}} = {\sigma_{i}} \,
{\delta_{{n},2{d}({n}-1)}}$, for every¨${d}$. On the other hand, we have ${\delta_{{n},(2{d}+1)({n}-1)}} = {\sigma_{1,n}} \, {\delta_{{n},2{d}({n}-1)}}$, hence $${\delta_{{n},(2{d}+1)({n}-1)}} \, {\sigma_{i}} 
= {\sigma_{1,n}} \, {\sigma_{i}} \, {\delta_{{n},2{d}({n}-1)}} 
= {\sigma_{i+1}} \, {\sigma_{1,n}} \, {\delta_{{n},2{d}({n}-1)}} =
{\sigma_{i+1}} \, {\delta_{{n},(2{d}+1)({n}-1)}},$$ as was expected.

A Pascal triangle
-----------------

We shall now construct for every¨${d}$ a sequence of positive braids¨${S_{3}^{{d}}}$ that will turn out to be the increasing enumeration of¨${({\mathrm{Div}}({\Delta}_{3}^{{d}}),\nobreak{<}\nobreak)}$. The construction relies on an induction similar to a Pascal triangle. In order to make it easily understandable, it is convenient to start with a construction in the (trivial) cases¨${n}=
1$ and¨${n}= 2$.

As $B_1$ is the trivial group, then for every¨${d}$ there is exactly one element of degree at most¨${d}$, namely¨$1$, and we can state:

Let ${S_{1}^{{d}}}$ be defined for ${d}\ge 0$ by $$\label{E:Def1}
{S_{1}^{{d}}} = (1).$$ Then ${S_{1}^{{d}}}$ is the increasing enumeration of¨${{\mathrm{Div}}({\Delta}_{1}^{{d}})}$.

The group¨$B_2$ is the rank¨$1$ free group generated by¨${\sigma_{1}}$. The fundamental braid¨${\Delta}_2$ is just¨${\sigma_{1}}$, and the braids of degree at most¨${d}$, [[*i.e.*]{}]{}, the divisors of¨${{\Delta}_{2}^{{d}}}$, consist of the ${d}+1$ braids¨$1, {\sigma_{1}}, \ldots, {\sigma_1^{{d}}}$. On the other hand, we have ${\sigma_{1, 2}} = {\sigma_{2, 1}} =
{\sigma_{1}}$, and ${\delta_{1,i}} = {\sigma_1^{i}}$ for every¨$i$.

If $S_1, S_2$ are sequences (of braids), we denote by $S_1 + S_2$ the concatenation of¨$S_1$ and¨$S_2$, [[*i.e.*]{}]{}, the sequence obtained by appending¨$S_2$ after¨$S_1$. If $S$ is a sequence of braids, and ${x}$ is a braid, we denote by¨${x}S$ the translated sequence obtained by multiplying each entry in¨$S$ by¨${x}$ on the left.

With these conventions, the sequence $(1, {\sigma_{1}},
\dots, {\sigma_{1}}^{d})$ can be expressed as ${\delta_{2,0}}(1)
+ {\delta_{2,1}}(1) + \cdots + {\delta_{2,{d}}}(1)$, and we can state:

\[P:Enum3\] Let ${S_{2}^{{d}}}$ be defined for ${d}\ge 0$ by $$\label{E:Def2}
{S_{2}^{{d}}} = {\delta_{2,0}}{S_{1}^{{d}}} + {\delta_{2,1}}{S_{1}^{{d}}} + \cdots + {\delta_{2,{d}}}{S_{1}^{{d}}}.$$ Then ${S_{2}^{{d}}}$ is the increasing enumeration of¨${{\mathrm{Div}}({\Delta}_{2}^{{d}})}$.

We repeat the process for¨${n}= 3$, introducing a sequence¨${S_{3}^{{d}}}$ by a definition similar to¨ that involves ${S_{2}^{{d}}}$ and¨${S_{3}^{{d}-1}}$. The result we shall prove is:

\[P:Main3\] Let ${S_{3}^{{d}}}$ be defined for ${d}\ge 0$ by $$\begin{aligned}
 \label{E:Def3}
{S_{3}^{{d}}} =  {\delta_{3,0}}{S_{2}^{{d}}} + {S_{3}^{{d}, 1}}
+ {\delta_{3,1}}{S_{2}^{{d}}} + \cdots 
+ {\delta_{3,2{d}-1}}{S_{2}^{{d}}} + {S_{3}^{{d}, 2{d}}} + {\delta_{3,2{d}}} {S_{2}^{{d}}},\end{aligned}$$ where ${S_{3}^{{d}, 1}}, \cdots, {S_{3}^{{d}, 2{d}}}$ are defined by ${S_{3}^{{d}, 1}} =
{S_{3}^{{d}, 2{d}}} =
\emptyset$ and, for $2 \le {p}\le 2{d}-1$, $${S_{3}^{{d}, {p}}} = 
\begin{cases}
\phantom{{\sigma_{2}}}{\sigma_{1}}({S_{3}^{{d}-1, {p}-1}} +
{\delta_{3,{p}-1}}{S_{2}^{{d}-1}} +
{S_{3}^{{d}-1, {p}}}) & \mbox{for ${p}= 0 \pmod 4$,}\\
{\sigma_{2}}{\sigma_{1}}({S_{3}^{{d}-1, {p}-2}} + {\delta_{3,{p}-1}}{S_{2}^{{d}-1}} +
{S_{3}^{{d}-1, {p}-1}}) & \mbox{for ${p}= 1 \pmod 4$,}\\
\phantom{{\sigma_{2}}}{\sigma_{2}}({S_{3}^{{d}-1, {p}-1}} +
{\delta_{3,{p}-1}}{S_{2}^{{d}-1}} +
{S_{3}^{{d}-1, {p}}}) & \mbox{for ${p}= 2 \pmod 4$,}\\
{\sigma_{1}}{\sigma_{2}}({S_{3}^{{d}-1, {p}-2}} + {\delta_{3,{p}-1}}{S_{2}^{{d}-1}} +
{S_{3}^{{d}-1, {p}-1}}) & \mbox{for ${p}= 3 \pmod 4$.}
\end{cases}$$ Then ${S_{3}^{{d}}}$ is the increasing enumeration of¨${{\mathrm{Div}}({\Delta}_{3}^{{d}})}$.

The general scheme is illustrated in Table¨\[T:Triangle\]: the sequence¨${S_{3}^{{d}}}$ is constructed by starting with $2{d}+1$¨copies of¨${S_{2}^{{d}}}$ translated by¨${\delta_{3,0}}$, …, ${\delta_{3,2{d}}}$ and inserting (translated copies of) fragments of the previous sequence¨${S_{3}^{{d}-1}}$.

(130,47)(1, 0) (0,10)[${\delta_{3,0}} {S_{2}^{3}}$]{} (10,10)[$({S_{3}^{3,1}})$]{} (20,10)[${\delta_{3,1}} {S_{2}^{3}}$]{} (32,10)[${S_{3}^{3,2}}$]{} (40,10)[${\delta_{3,2}} {S_{2}^{3}}$]{} (52,10)[${S_{3}^{3,3}}$]{} (60,10)[${\delta_{3,3}} {S_{2}^{3}}$]{} (72,10)[${S_{3}^{3,4}}$]{} (80,10)[${\delta_{3,4}} {S_{2}^{3}}$]{} (92,10)[${S_{3}^{3,5}}$]{} (100,10)[${\delta_{3,4}} {S_{2}^{3}}$]{} (110,10)[$({S_{3}^{3,6}})$]{} (120,10)[${\delta_{3,6}} {S_{2}^{3}}$]{} (10,9)[$\underbrace{\hbox to 28mm{\hfill}}$]{} (14,4)[${\sigma_{2}}\cdot$]{} (29,4)[${\sigma_{1}}{\sigma_{2}}\cdot$]{} (17.5,3)[$\swarrow$]{} (26.5,3)[$\searrow$]{} (52,9)[$\underbrace{\hbox to 26mm{\hfill}}$]{} (56,4)[${\sigma_{1}}\cdot$]{} (70,4)[${\sigma_{2}}{\sigma_{1}}\cdot$]{} (59,3)[$\swarrow$]{} (68,3)[$\searrow$]{} (92,9)[$\underbrace{\hbox to 27mm{\hfill}}$]{} (96,4)[${\sigma_{2}}\cdot$]{} (111,4)[${\sigma_{1}}{\sigma_{2}}\cdot$]{} (99,3)[$\swarrow$]{} (108,3)[$\searrow$]{} (14,0)[$\cdots$]{} (31,0)[$\cdots$]{} (54,0)[$\cdots$]{} (71,0)[$\cdots$]{} (95,0)[$\cdots$]{} (112,0)[$\cdots$]{}

(20,22)[${\delta_{3,0}} {S_{2}^{2}}$]{} (30,22)[$({S_{3}^{2,1}})$]{} (40,22)[${\delta_{3,1}} {S_{2}^{2}}$]{} (52,22)[${S_{3}^{2,2}}$]{} (60,22)[${\delta_{3,2}} {S_{2}^{2}}$]{} (72,22)[${S_{3}^{2,3}}$]{} (80,22)[${\delta_{3,3}} {S_{2}^{2}}$]{} (90,22)[$({S_{3}^{2,4}})$]{} (100,22)[${\delta_{3,4}} {S_{2}^{2}}$]{} (30,21)[$\underbrace{\hbox to
28mm{\hfill}}$]{} (36,16)[${\sigma_{2}}\cdot$]{} (50,16)[${\sigma_{1}}{\sigma_{2}}\cdot$]{} (38,14.5)[$\swarrow$]{} (47,14.5)[$\searrow$]{} (72,21)[$\underbrace{\hbox to
27mm{\hfill}}$]{} (77,16)[${\sigma_{1}}\cdot$]{} (91,16)[${\sigma_{2}}{\sigma_{1}}\cdot$]{} (79,14.5)[$\swarrow$]{} (88,14.5)[$\searrow$]{}

(40,34)[${\delta_{3,0}} {S_{2}^{1}}$]{} (50,34)[$({S_{3}^{1,1}})$]{} (60,34)[${\delta_{3,1}} {S_{2}^{1}}$]{} (70,34)[$({S_{3}^{1,2}})$]{} (80,34)[${\delta_{3,2}} {S_{2}^{1}}$]{} (50,33)[$\underbrace{\hbox to
28mm{\hfill}}$]{} (56,28)[${\sigma_{2}}\cdot$]{} (70,28)[${\sigma_{1}}{\sigma_{2}}\cdot$]{} (58,26.5)[$\swarrow$]{} (67,26.5)[$\searrow$]{}

(60,44)[${\delta_{3,0}} {S_{2}^{0}}$]{}

\[X:SS3\] The difference between the definition of¨${S_{3}^{{d}}}$ in¨ and that of¨${S_{2}^{{d}}}$ in¨ is the insertion of the additional factors $ {S_{3}^{{d},{p}}}$ between the consecutive terms¨${\delta_{3,{q}}}{S_{2}^{{d}}}$. Because ${S_{3}^{{d}, 1}}$ and ${S_{3}^{{d}, 2{d}}}$ are empty, the difference occurs for ${d}\ge 2$ only. The first values are:

${S_{3}^{0}} = {\delta_{3,0}} {S_{2}^{0}} = (1)$,

${S_{3}^{1}} = {\delta_{3,0}} {S_{2}^{1}} + {S_{3}^{1,1}} + {\delta_{3,1}} {S_{2}^{1}} +
{S_{3}^{1,2}} + {\delta_{3,2}} {S_{2}^{1}}$

$= (1, {\mathtt{a}}) + \emptyset
+ {\mathtt{b}}(1, {\mathtt{a}}) + \emptyset 
+ {\mathtt{a}}{\mathtt{b}}(1, {\mathtt{a}})$

$= (1, {\mathtt{a}}, {\mathtt{b}}, {\mathtt{b}}{\mathtt{a}}, {\mathtt{a}}{\mathtt{b}}, {\mathtt{a}}{\mathtt{b}}{\mathtt{a}})$,

${S_{3}^{2}}  = {\delta_{3,0}} {S_{2}^{2}} + {S_{3}^{2,1}} +
{\delta_{3,1}} {S_{2}^{2}} + {S_{3}^{2,2}} +
{\delta_{3,2}} {S_{2}^{2}} + {S_{3}^{2,3}} +
{\delta_{3,3}} {S_{2}^{2}} + {S_{3}^{2,4}} +
{\delta_{3,4}} {S_{2}^{2}}$

$ = (1, {\mathtt{a}}, {\mathtt{a}}{\mathtt{a}}) + \emptyset
+ {\mathtt{b}}(1, {\mathtt{a}}, {\mathtt{a}}{\mathtt{a}}) + {\mathtt{b}}({\mathtt{b}}, {\mathtt{b}}{\mathtt{a}})
+ {\mathtt{a}}{\mathtt{b}}(1, {\mathtt{a}}, {\mathtt{a}}{\mathtt{a}})$

$ + {\mathtt{a}}{\mathtt{b}}({\mathtt{b}}, {\mathtt{b}}{\mathtt{a}})
+ {\mathtt{a}}{\mathtt{a}}{\mathtt{b}}(1, {\mathtt{a}}, {\mathtt{a}}{\mathtt{a}}) + \emptyset 
+ {\mathtt{b}}{\mathtt{a}}{\mathtt{a}}{\mathtt{b}}(1, {\mathtt{a}}, {\mathtt{a}}{\mathtt{a}})$

$ = (1, {\mathtt{a}}, {\mathtt{a}}{\mathtt{a}}, {\mathtt{b}}, {\mathtt{b}}{\mathtt{a}}, {\mathtt{b}}{\mathtt{a}}{\mathtt{a}},
{\mathtt{b}}{\mathtt{b}}, {\mathtt{b}}{\mathtt{b}}{\mathtt{a}},
{\mathtt{a}}{\mathtt{b}}, {\mathtt{a}}{\mathtt{b}}{\mathtt{a}}, {\mathtt{a}}{\mathtt{b}}{\mathtt{a}}{\mathtt{a}},
{\mathtt{a}}{\mathtt{b}}{\mathtt{b}}, {\mathtt{a}}{\mathtt{b}}{\mathtt{b}}{\mathtt{a}}, {\mathtt{a}}{\mathtt{a}}{\mathtt{b}}$,

${\mathtt{a}}{\mathtt{a}}{\mathtt{b}}{\mathtt{a}}, {\mathtt{a}}{\mathtt{a}}{\mathtt{b}}{\mathtt{a}}{\mathtt{a}}, {\mathtt{b}}{\mathtt{a}}{\mathtt{a}}{\mathtt{b}},
{\mathtt{b}}{\mathtt{a}}{\mathtt{a}}{\mathtt{b}}{\mathtt{a}}, {\mathtt{b}}{\mathtt{a}}{\mathtt{a}}{\mathtt{b}}{\mathtt{a}}{\mathtt{a}})$.\
It is easy to check directly that the sequence ${S_{3}^{{d}}}$ provides the increasing enumeration of¨${{\mathrm{Div}}({\Delta}_{3}^{{d}})}$ for ${d}= 0, 1, 2$.

The proof of Proposition¨\[P:Main3\] will be split into several pieces, each of which is established using an induction on the degree¨${d}$.

\[L:Inclusion3\] All entries in¨${S_{3}^{{d}}}$ are divisors of¨${{\Delta}_{3}^{{d}}}$.

The result is true for ${d}= 0$. Assume ${d}\ge 1$. By construction, each entry in¨${S_{3}^{{d}}}$ either is of the form ${\delta_{3,{q}}} {\sigma_{1}}^{e}$ with $0 \le {q}\le 2{d}$ and $0 \le
{e}\le {d}$, or belongs to some subsequence¨${S_{3}^{{d},{p}}}$ with $2 \le {p}\le 2{d}-
1$. In the first case, ${\delta_{3,{q}}}{\sigma_{1}}^{e}$ is a right divisor of ${\delta_{3,2{d}}}
{\sigma_{1}}^{e}$, which itself is a left divisor of ${\delta_{3,2{d}}} {\sigma_{1}}^{d}$. By¨, the latter is¨${{\Delta}_{3}^{{d}}}$. Hence each ${\delta_{3,{q}}}
{\sigma_{1}}^{e}$ is a divisor of¨${{\Delta}_{3}^{{d}}}$. As for the entries coming from some subsequence¨${S_{3}^{{d},{p}}}$, by definition they are of the form¨${x}{y}$ with ${x}$ one of ${\sigma_{2}}, {\sigma_{1}}{\sigma_{2}}, {\sigma_{1}},
{\sigma_{2}}{\sigma_{1}}$ and ${y}$ an entry in¨${S_{3}^{{d}-1}}$. Then ${x}$ is a divisor of¨${\Delta}_3$, while, by induction hypothesis, ${y}$ is a divisor of¨${{\Delta}_{3}^{{d}-1}}$, so ${x}{y}$ is a divisor of¨${{\Delta}_{3}^{{d}}}$.

\[L:Card3\] The length of the sequence¨${S_{3}^{{d}}}$ equals the cardinality of¨${{\mathrm{Div}}({\Delta}_{3}^{{d}})}$.

Let $\ell_{d}$ denote the length of¨${S_{3}^{{d}}}$. Computing¨$\ell_{d}$ is not very difficult. However, there is need to do it, which amounts to solve a recursive formula unnecessarily. Indeed, we saw in Section¨\[S:Deter\] that the cardinality¨${{h_{1}}({{\Delta}_{3}^{{d}}})}$ of¨${{\mathrm{Div}}({\Delta}_{3}^{{d}})}$ obeys the inductive rule¨. So it will be enough to check that $\ell_{d}$ satisfies the relation $$\label{E:Double}
\ell_{d}= 2 \ell_{{d}-1} + 3{d}+ 1,$$ and starts from the initial¨$\ell_1 = 6$ (or $\ell_0 =
1$). The latter point was checked in Example¨\[X:SS3\].

Now Table¨\[T:Triangle\] shows that most entries in¨${S_{3}^{{d}-1}}$ give rise to two entries in¨${S_{3}^{{d}}}$. More precisely, each entry of¨${S_{3}^{{d}-1}}$ not belonging to a factor of the form¨${\delta_{3,2{q}}}
{S_{2}^{{d}-1}}$ gives rise to two entries in¨${S_{3}^{{d}}}$, and, conversely, each entry in¨${S_{3}^{{d}}}$ not belonging to a factor¨${\delta_{3,{q}}}
{S_{2}^{{d}}}$ comes from such an entry in¨${S_{3}^{{d}-1}}$. There are ${d}$¨factors¨${\delta_{3,2{q}}} {S_{2}^{{d}-1}}$ in¨${S_{3}^{{d}-1}}$, each of length¨${d}$, and $2{d}+1$¨factors¨${\delta_{3,2{q}}} {S_{2}^{{d}}}$ in¨${S_{3}^{{d}}}$, each of length¨${d}+1$. So we obtain $$\ell_{d}- (2{d}+1)({d}+1) = 2(\ell_{{d}-1} - {d}^2),$$ which gives¨.

At this point, we cannot (yet) conclude that each divisor of¨${{\Delta}_{3}^{{d}}}$ occurs exactly once in¨${S_{3}^{{d}}}$, as there could be some repetitions.

A quotient-sequence for¨${S_{3}^{{d}}}$
---------------------------------------

Our next aim is to show that ${S_{3}^{{d}}}$ is ${<}$-increasing. To this end, we shall explicitly determine the quotient of adjacent entries in¨${S_{3}^{{d}}}$, [[*i.e.*]{}]{}, we shall specify a quotient-sequence for¨${S_{3}^{{d}}}$ in the sense of Definition¨\[D:Witness\].

A preliminary step consists in determining the first and the last entries of the sequence¨$ {S_{3}^{{d},{p}}}$. For¨$S$ a nonempty sequence, we denote by ${(S)_{\!_1}}$ ([[*resp.[ ]{}*]{}]{}${(S)_{\!_\infty}}$) the first ([[*resp.[ ]{}*]{}]{}last) entry in¨$S$.

\[L:FirstLast\] For $1 < i < 2{d}$, we have $${( {S_{3}^{{d},{p}}})_{\!_1}} = {\delta_{3,{p}-1}} \, {\sigma_{2}}, 
\mbox{\quad and \quad}
{( {S_{3}^{{d},{p}}})_{\!_\infty}} \, {\sigma_{2}} = {\delta_{3,{p}}} \, {\sigma_1^{{d}}}.$$

The result is vacuously true for ${d}= 0, 1$. Assume ${d}\ge
2$ with ${p}= 0 \pmod 4$. Using the definition, the induction hypothesis, and¨, we find $$\begin{gathered}
{( {S_{3}^{{d},{p}}})_{\!_1}} 
= {\sigma_{1}} \, {( {S_{3}^{{d}-1,{p}-1}})_{\!_1}} = 
{\sigma_{1}} \, {\delta_{3,{p}-2}} \, {\sigma_{2}}
= {\delta_{3,{p}-1}} \, {\sigma_{2}}, \\
{( {S_{3}^{{d},{p}}})_{\!_\infty}} \, {\sigma_{2}} 
= {\sigma_{1}} \, {( {S_{3}^{{d}-1,{p}}})_{\!_\infty}} \, {\sigma_{2}} 
=  {\sigma_{1}} \, {\delta_{3,{p}}} \, {\sigma_1^{{d}-1}} 
= {\delta_{3,{p}}} \, {\sigma_1^{{d}}}.\end{gathered}$$ Similarly, for ${p}= 1 \pmod 4$, we have $$\begin{gathered}
{( {S_{3}^{{d},{p}}})_{\!_1}} 
= {\sigma_{2}}{\sigma_{1}} \, {( {S_{3}^{{d}-1,{p}-2}})_{\!_1}} = 
{\sigma_{2}}{\sigma_{1}} \, {\delta_{3,{p}-3}} \, {\sigma_{2}}
= {\delta_{3,{p}-1}} \, {\sigma_{2}}, \\
{( {S_{3}^{{d},{p}}})_{\!_\infty}} \, {\sigma_{2}} 
= {\sigma_{2}}{\sigma_{1}} \, {( {S_{3}^{{d}-1,{p}-1}})_{\!_\infty}} \, {\sigma_{2}} 
=  {\sigma_{2}}{\sigma_{1}} \, {\delta_{3,{p}-1}} \, {\sigma_1^{{d}-1}} 
= {\sigma_{2}}\, {\delta_{3,{p}-1}} \, {\sigma_1^{{d}}}
= {\delta_{3,{p}}} \, {\sigma_1^{{d}}}.\end{gathered}$$ Then, for ${p}= 2 \pmod 4$, we have $$\begin{gathered}
{( {S_{3}^{{d},{p}}})_{\!_1}} 
= {\sigma_{2}} \, {( {S_{3}^{{d}-1,{p}-1}})_{\!_1}} = 
{\sigma_{2}} \, {\delta_{3,{p}-2}} \, {\sigma_{2}}
= {\delta_{3,{p}-1}} \, {\sigma_{2}}, \\
{( {S_{3}^{{d},{p}}})_{\!_\infty}} \, {\sigma_{2}} 
= {\sigma_{2}} \, {( {S_{3}^{{d}-1,{p}}})_{\!_\infty}} \, {\sigma_{2}} 
=  {\sigma_{2}} \, {\delta_{3,{p}}} \, {\sigma_1^{{d}-1}} 
= {\delta_{3,{p}}} \, {\sigma_1^{{d}}}.\end{gathered}$$ Finally, for ${p}= 3 \pmod 4$, we find $$\begin{gathered}
{( {S_{3}^{{d},{p}}})_{\!_1}} 
= {\sigma_{1}}{\sigma_{2}} \, {( {S_{3}^{{d}-1,{p}-2}})_{\!_1}} = 
{\sigma_{1}}{\sigma_{2}} \, {\delta_{3,{p}-3}} \, {\sigma_{2}}
= {\delta_{3,{p}-1}} \, {\sigma_{2}}, \\
{( {S_{3}^{{d},{p}}})_{\!_\infty}} \, {\sigma_{2}} 
= {\sigma_{1}}{\sigma_{2}} \, {( {S_{3}^{{d}-1,{p}-1}})_{\!_\infty}} \, {\sigma_{2}} 
=  {\sigma_{1}}{\sigma_{2}} \, {\delta_{3,{p}-1}} \, {\sigma_1^{{d}-1}} 
=  {\sigma_{1}}{\sigma_{2}}{\sigma_{1}}{\sigma_{2}} \, {\delta_{3,{p}-3}} \, {\sigma_1^{{d}-1}}\\
\hspace{4cm}
=  {\sigma_{1}}{\sigma_{1}}{\sigma_{2}}{\sigma_{1}} \, {\delta_{3,{p}-3}} \, {\sigma_1^{{d}-1}} 
=  {\sigma_{1}}{\sigma_{1}}{\sigma_{2}} \, {\delta_{3,{p}-3}} \, {\sigma_1^{{d}}}
= {\delta_{3,{p}}} \, {\sigma_1^{{d}}}.\end{gathered}$$ This completes the argument.

We shall now construct an explicit quotient-sequence for¨${S_{3}^{{d}}}$, [[*i.e.*]{}]{}, a sequence of braid words representing the quotients of the consecutive entries of¨${S_{3}^{{d}}}$. Before doing it for¨${S_{3}^{{d}}}$, let us consider the (trivial) cases of¨${S_{1}^{{d}}}$ and¨${S_{2}^{{d}}}$. As ${S_{1}^{{d}}}$ consists of one single entry, it vacuously admits the empty sequence as a quotient-sequence. As for¨${S_{2}^{{d}}}$, we can state:

For ${d}\ge 0$, let ${\vec w_{1}^{{d}}}$ be the empty sequence, and let¨${\vec w_{2}^{{d}}}$ be defined by $$\label{E:DDef2}
{\vec w_{2}^{{d}}} = {\vec w_{1}^{{d}}} + ({\sigma_{1}}) + {\vec w_{1}^{{d}}} + \cdots + {\vec w_{1}^{{d}}}
+ ({\sigma_{1}}) + {\vec w_{1}^{{d}}},$$ ${d}$¨times¨$({\sigma_{1}})$. Then ${\vec w_{2}^{{d}}}$ is a quotient-sequence for¨${S_{2}^{{d}}}$.

On a similar way, we shall prove:

\[P:Quotient3\] Let ${\vec w_{3}^{{d}}}$ be the sequence defined by ${\vec w_{3}^{0}} = \emptyset$ and $$\begin{aligned}
 \label{E:DDef3}
{\vec w_{3}^{{d}}} =  {\vec w_{2}^{{d}}} 
\!+\! ({\sigma_{1}}^{-{d}}{\sigma_{2}}) 
&+ {\vec w_{2}^{{d}}} 
\!+\! ({\sigma_{1}}^{-{d}}{\sigma_{2}}) 
\!+\! {\vec w_{3}^{{d}, 2}} \!+\!
({\sigma_{2}}{\sigma_{1}}^{-{d}}) \\ 
\notag &+ {\vec w_{2}^{{d}}} 
\!+\! ({\sigma_{1}}^{-{d}}{\sigma_{2}}) 
\!+\! {\vec w_{3}^{{d}, 3}} 
\!+\!
({\sigma_{2}}{\sigma_{1}}^{-{d}}) 
\!+\! \cdots \\  
\notag &+ {\vec w_{2}^{{d}}} 
\!+\! ({\sigma_{1}}^{-{d}}{\sigma_{2}}) 
\!+\! {\vec w_{3}^{{d}, 2{d}-1}} \!+\!
({\sigma_{2}}{\sigma_{1}}^{-{d}}) 
\!+\! {\vec w_{2}^{{d}}} 
\!+\! ({\sigma_{2}}{\sigma_{1}}^{-{d}})
\!+\! {\vec w_{2}^{{d}}},\end{aligned}$$

with = ${\vec w_{3}^{{d}, 2}} = {\vec w_{3}^{{d}, 3}} 
= {\vec w_{2}^{{d}-1}} 
\!+\! ({\sigma_{2}}{\sigma_1^{-{d}+1}}) 
\!+\! {\vec w_{3}^{{d}-1, 2}},$\
width0pt height15pt ${\vec w_{3}^{{d}, 2{d}-2}} ={\vec w_{3}^{{d}, 2{d}-1}}
= {\vec w_{3}^{{d}-1, 2{d}-3}} 
\!+\! ({\sigma_1^{-{d}+1}}{\sigma_{2}}) 
\!+\! {\vec w_{2}^{{d}-1}}$,\
and width0pt height15pt ${\vec w_{3}^{{d}, 2{p}}}  = {\vec w_{3}^{{d}, 2{p}+1}} 
= {\vec w_{3}^{{d}-1,2{p}-1}} 
\!+\! ({\sigma_1^{-{d}+1}}{\sigma_{2}}) 
\!+\! {\vec w_{2}^{{d}-1}} 
\!+\! ({\sigma_{2}}{\sigma_1^{-{d}+1}}) 
\!+\! {\vec w_{3}^{{d}-1, 2{p}}}$

for $4 \le 2{p}\le 2{d}-4$. Then ${\vec w_{3}^{{d}}}$ is a quotient-sequence for¨${S_{3}^{{d}}}$.

\[X:Quotient\] We find ${\vec w_{3}^{1}} 
 = {\vec w_{2}^{1}} + ({\mathtt{A}}{\mathtt{b}}) + {\vec w_{2}^{1}} + ({\mathtt{b}}{\mathtt{A}}) + {\vec w_{2}^{1}}
 = ({\mathtt{a}}, {\mathtt{A}}{\mathtt{b}}, {\mathtt{a}}, {\mathtt{b}}{\mathtt{A}}, {\mathtt{a}})$, and $$\begin{aligned}
{\vec w_{3}^{2}} 
= {\vec w_{2}^{2}} + ({\mathtt{A}}{\mathtt{A}}{\mathtt{b}}) 
&+ {\vec w_{2}^{2}} + ({\mathtt{A}}{\mathtt{A}}{\mathtt{b}}) 
+ {\vec w_{3}^{2, 2}} + ({\mathtt{b}}{\mathtt{A}}{\mathtt{A}})\\
&+ {\vec w_{2}^{2}} +
({\mathtt{A}}{\mathtt{A}}{\mathtt{b}}) + {\vec w_{3}^{2, 3}} + ({\mathtt{b}}{\mathtt{A}}{\mathtt{A}}) + {\vec w_{2}^{2}} +
({\mathtt{b}}{\mathtt{A}}{\mathtt{A}}) + {\vec w_{2}^{2}}\end{aligned}$$ with ${\vec w_{3}^{2, 2}} = {\vec w_{3}^{2, 3}} = {\vec w_{2}^{1}} = ({\mathtt{a}})$, whence $${\vec w_{3}^{2}} 
 = ({\mathtt{a}}, {\mathtt{a}}, {\mathtt{A}}{\mathtt{A}}{\mathtt{b}}, {\mathtt{a}}, {\mathtt{a}}, {\mathtt{A}}{\mathtt{A}}{\mathtt{b}}, {\mathtt{a}}, {\mathtt{b}}{\mathtt{A}}{\mathtt{A}}, {\mathtt{a}}, {\mathtt{a}},
{\mathtt{A}}{\mathtt{A}}{\mathtt{b}}, {\mathtt{a}}, {\mathtt{b}}{\mathtt{A}}{\mathtt{A}}, {\mathtt{a}}, {\mathtt{a}}, {\mathtt{b}}{\mathtt{A}}{\mathtt{A}}, {\mathtt{a}}, {\mathtt{a}}).$$

\[Proof of Proposition¨\[P:Quotient3\]\] We prove using induction on¨${d}$ that ${\vec w_{3}^{{d}}}$ is a quotient-sequence for¨${S_{3}^{{d}}}$ with the $4{d}-2$¨terms in¨ corresponding to the $4{d}-1$¨nonempty terms in¨—so, in particular, for $2
\le {p}\le 2{d}-1$, the subsequence¨${\vec w_{3}^{{d},{p}}}$ is a quotient-sequence for ¨$ {S_{3}^{{d},{p}}}$. The result is vacuously true for ${d}=0$. Assume ${d}\ge 1$. By definition, the sequence¨${S_{3}^{{d}}}$ consists of the concatenation of the $2{d}+1$ sequences ${\delta_{3,0}} {S_{2}^{{d}}}, \cdots, {\delta_{3,2{d}}} {S_{2}^{{d}}}$, in which the $2{d}-2$ sequences ${S_{3}^{{d}, 2}}, \dots, {S_{3}^{{d}, 2{d}-1}}$ are inserted. We shall consider these subsequences separately, and then consider the transitions between consecutive subsequences.

First, ${\vec w_{2}^{{d}}}$ is a quotient-sequence for¨${S_{2}^{{d}}}$, hence it is a quotient-sequence for every sequence ${\delta_{3,{q}}}
{S_{2}^{{d}}}$ as well, since, by definition, the quotients we consider are invariant under left translation. Then, by construction, each subsequence ${S_{3}^{{d}, 2{p}}}$ or ${S_{3}^{{d}, 2{p}+1}}$ appearing in¨${S_{3}^{{d}}}$ is obtained by translating some subsequence¨$S$ of¨${S_{3}^{{d}-1}}$, namely $$S =  {S_{3}^{{d}-1, 2{p}-1}} + {\delta_{3,{q}-1}} {S_{2}^{{d}-1}} +
{S_{3}^{{d}-1, 2{p}}}.$$ By induction hypothesis, the sequence $${\vec w_{3}^{{d}-1, 2{p}-1}} +
({\sigma_1^{-{d}+1}}{\sigma_{2}}) + {\vec w_{2}^{{d}-1}} +
({\sigma_{2}}{\sigma_1^{-{d}+1}}) +
{\vec w_{3}^{{d}-1, 2{p}}},$$ which is precisely ${\vec w_{3}^{{d}, 2{p}}}$ and ${\vec w_{3}^{{d}, 2{p}+1}}$ by definition, is a quotient-sequence for¨$S$. The property remains true in the special cases ${p}= 1$ and ${p}= {d}$, which correspond to removing the initial term¨${S_{3}^{{d}-1,2{p}-1}}$, and/or the final term¨${S_{3}^{{d}-1, 2{p}}}$, respectively. Then ${\vec w_{3}^{{d}, 2{p}}}$ and ${\vec w_{3}^{{d}, 2{p}+1}}$ are also quotient-sequences for any sequence obtained from¨$S$ by a left translation, in particular for¨${S_{3}^{{d},
2{p}}}$ and¨${S_{3}^{{d}, 2{p}+1}}$.

So it only remains to study the transitions between the consecutive terms in the expression¨ of¨${S_{3}^{{d}}}$, [[*i.e.*]{}]{}, to compare the last entry in each term with the first entry in the next term. Four cases are to be considered, namely the special case of the first two terms and of the final two terms, and the generic cases of the transitions from¨${\delta_{3,{q}}} {S_{2}^{{d}}}$ to¨${S_{3}^{{d},{p}+1}}$ and from¨${S_{3}^{{d},{p}}}$ to¨${\delta_{3,{q}}} {S_{2}^{{d}}}$.

As for the first two terms, namely ${\delta_{3,0}} {S_{2}^{{d}}}$ and ${\delta_{3,1}} {S_{2}^{{d}}}$, [[*i.e.*]{}]{}, ${S_{2}^{{d}}}$ and ${\sigma_{2}}{S_{2}^{{d}}}$, the last entry in¨${S_{2}^{{d}}}$ is¨${\sigma_1^{{d}}}$, while the first entry in¨${\sigma_{2}}{S_{2}^{{d}}}$ is¨${\sigma_{2}}$, so ${\sigma_1^{-{d}}}{\sigma_{2}}$ is a quotient. As for the last two terms, namely ${\delta_{3,2{d}-1}} {S_{2}^{{d}}}$ and ${\delta_{3,2{d}}} {S_{2}^{{d}}}$, the last entry in¨${\delta_{3,2{d}-1}}{S_{2}^{{d}}}$ is¨${\delta_{3,2{d}-1}}\,{\sigma_1^{{d}}}$, while the first entry in¨${\delta_{3,2{d}}}{S_{2}^{{d}}}$ is¨${\delta_{3,2{d}}}$. Now, by¨, we have ${\delta_{3,2{d}-1}}\,{\sigma_1^{{d}}}{\sigma_{2}} =
{\delta_{3,2{d}}}
\,{\sigma_1^{{d}}}$, so ${\sigma_{2}}{\sigma_1^{-{d}}}$ is an expression of the quotient.

Consider now the transition from¨${\delta_{3,{q}}} {S_{2}^{{d}}}$ to¨${S_{3}^{{d},{q}+1}}$. The last entry in¨${\delta_{3,{q}}} {S_{2}^{{d}}}$ is¨${\delta_{3,{q}}}\, {\sigma_1^{{d}}}$, while, by Lemma¨\[L:FirstLast\], the first entry in¨${S_{3}^{{d},{q}+1}}$ is¨${\delta_{3,{q}}} \,{\sigma_{2}}$. Hence ${\sigma_1^{-{d}}}{\sigma_{2}}$ represents the quotient. Finally, consider the transition from¨${S_{3}^{{d},{p}}}$ to¨${\delta_{3,{q}}}
{S_{2}^{{d}}}$. By Lemma¨\[L:FirstLast\] again, the last entry¨${x}$ in¨${\delta_{3,{q}}} {S_{2}^{{d}}}$ satisfies¨${x}\, {\sigma_{2}}
= {\delta_{3,{q}}} \, {\sigma_1^{{d}}}$, while the first entry in¨${\delta_{3,{q}}}
{S_{2}^{{d}}}$ is¨${\delta_{3,{q}}}$. Hence ${\sigma_{2}}{\sigma_1^{-{d}}}$ represents the quotient.

\[C:Distinct3\] For each¨${d}$ the sequence¨${S_{3}^{{d}}}$ is ${<}$-increasing; so, in particular, it consists of pairwise distinct braids.

By definition, every word in¨${\vec w_{3}^{{d}}}$ is $\s$-positive, hence, by Property¨A, it does not represent¨$1$.

As ${S_{3}^{{d}}}$ consists of pairwise distinct divisors of¨${{\Delta}_{3}^{{d}}}$, Lemma¨\[L:Card3\] implies that every divisor of¨${{\Delta}_{3}^{{d}}}$ occurs exactly once in¨${S_{3}^{{d}}}$. Then, as ${S_{3}^{{d}}}$ is ${<}$-increasing, it must be the increasing enumeration of¨${{\mathrm{Div}}({\Delta}_{3}^{{d}})}$, and the proof of Proposition¨\[P:Main3\] is complete.

Once we know that ${S_{3}^{{d}}}$ is the increasing enumeration of¨${{\mathrm{Div}}({\Delta}_{3}^{{d}})}$ and that ${\vec w_{3}^{{d}}}$ is a $\s$-positive quotient-sequence for¨${S_{3}^{{d}}}$, we can count the $2$-jumps in¨${S_{3}^{{d}}}$ and obtain the value of¨${{h_{2}}({{\Delta}_{3}^{{d}}})}$ directly: this amounts to forgetting about all¨${\sigma_{1}}^{\pm1}$ in the construction of¨${\vec w_{3}^{{d}}}$, and it is then fairly obvious that there only remains $2^{d}-2$ times¨${\sigma_{2}}$.

Larger values of¨${n}$
----------------------

The same construction can be developped for¨${n}= 4$ and further. The general scheme is clear, namely to define¨${S_{4}^{{d}}}$ using an inductive rule $$\begin{aligned}
 \label{E:Def4}
{S_{4}^{{d}}} =  {\delta_{4,0}} {S_{3}^{{d}}} + {S_{4}^{{d}, 1}}
+ {\delta_{4,1}} {S_{3}^{{d}}} + \cdots 
+ {\delta_{4,3{d}-1}} {S_{3}^{{d}}} + {S_{4}^{{d}, 3{d}}} + {\delta_{4,3{d}}}
{S_{3}^{{d}}},\end{aligned}$$ where the intermediate factor¨${S_{4}^{{d},{p}}}$ is constructed by concatenating and translating convenient fragments of¨${S_{4}^{{d}-1}}$. Owing to the inductive rule¨ satisfied by the number of elements¨${{h_{1}}({{\Delta}_{4}^{{d}}})}$ of¨${{\mathrm{Div}}({\Delta}_{4}^{{d}})}$, we can expect that the generic entry of¨${S_{4}^{{d}-1}}$ has to be repeated 6¨times in¨${S_{4}^{{d}}}$, but with some entries from¨${S_{4}^{{d}-2}}$ repeated 3¨times only. Once the inductive definition of¨${S_{4}^{{d}}}$ is made complete, showing that the sequence is ${<}$-increasing and counting its entries should be easy. As we have no complete description so far, we leave the question open here.

A new construction for the linear ordering of¨$B_3$
---------------------------------------------------

The main interest of the approach described above is not only to connect the Garside structure of¨$B_{n}$ with its linear ordering, but also to provide a new independent construction of the braid ordering, at least in the case of¨$B_3$ as the latter is the only one for which the construction was completed so far.

As was recalled in the introduction, the existence of the linear ordering of braids relies on two properties of braids, namely Property¨A and Property¨C. These properties have received a number of independent proofs¨[@Dgr]. In particular, Property¨A has now a very short proof based on Dynnikov’s coordinization for triangulations of a punctured disk ([@Dgr], Chapter¨9). As for Property¨C, no really simple proof exists so far: not to mention the initial argument involving self-distributive algebra, the combinatorial proofs based on handle reduction or on Burckel’s uniform tree approach, as well as the geometric proofs based on standardization of curve diagrams require some care. So, at the moment, one can estimate that the optimal proof of Property¨C is still missing.

A direct application of our construction of the sequence¨${S_{3}^{{d}}}$ is

Property¨C holds for¨$B_3$, [[*i.e.*]{}]{}, every non-trivial $3$-braid admits a $\s$-positive or a $\s$-negative expression.

We take as an hypothesis that Property¨A is true, so that the relation¨${<}$ is a partial ordering, but we do not assume that ${<}$ is linear. As every braid in¨$B_3$ is the quotient of two positive braids in¨$B_3^+$, proving Property¨C for¨$B_3$ amounts to proving that, if ${x}, {y}$ are arbitrary elements of¨$B_3^+$, then the quotient ${x}{^{-1}}{y}$ admits a $\s$-positive or a $\s$-negative expression.

Now the construction of¨${S_{3}^{{d}}}$ is self-contained, and so is that of¨${\vec w_{3}^{{d}}}$. Then, by construction, every word in¨${\vec w_{3}^{{d}}}$ is $\s$-positive. As any concatenation of $\s$-positive words is $\s$-positive, it follows that, if ${x}, {y}$ are any braids occurring in¨$\bigcup_{d}{S_{3}^{{d}}}$, then the quotient¨${x}{^{-1}}{y}$ admits a $\s$-positive or a $\s$-negative expression, according to whether ${x}$ occurs before or after¨${y}$ in¨${S_{3}^{{d}}}$. So, in order to conclude that Property¨C is true, it just remains to check that each positive $3$-braid occurs in¨$\bigcup_{d}{S_{3}^{{d}}}$. As every entry of¨${S_{3}^{{d}}}$ belongs to¨${{\mathrm{Div}}({\Delta}_{3}^{{d}})}$, this is equivalent to proving that each divisor of¨${{\Delta}_{3}^{{d}}}$ occurs in¨${S_{3}^{{d}}}$. Property¨A guarantees that the entries of¨${S_{3}^{{d}}}$ are pairwise distinct (Corollary¨\[C:Distinct3\]), so it suffices to compare the length of¨${S_{3}^{{d}}}$ with the cardinality of¨${{\mathrm{Div}}({\Delta}_{3}^{{d}})}$, and this is what we made in Lemma¨\[L:Card3\].

Actually the construction of¨${S_{3}^{{d}}}$ gives more. The approach developped by S.Burckel in¨[@Bus] consists in introducing a convenient notion of normal braid words such that every positive braid admits exactly one normal expression. In the case of $3$¨ strand braids, the definition is as follows. Every positive $3$¨strand braid word¨${w}$ can be written as an alternated product of blocks¨${\sigma_{1}}^{{e}}$ and¨${\sigma_{2}}^{{e}}$. Then we define the [*code*]{} of¨${w}$ to be the sequence made by the sizes of these blocks. To avoid ambiguity, we decide that the last block is considered to be a block of¨${\sigma_{1}}$’s, [[*i.e.*]{}]{}, we decide that the code of¨${\sigma_{1}}$ is¨$(1)$, while the code of¨${\sigma_{2}}$ is¨$(1, 0)$. For instance, the code of¨${\sigma_{2}}^2
{\sigma_{1}}^3{\sigma_{2}}^5$ is $(2, 3, 5, 0)$.

A positive $3$¨strand braid word¨${w}$ is said to be [*normal in the sense of Burckel*]{} if its code has the form $(e_1, \dots, e_\ell)$ with $e_{k}\ge 2$ for $2
\le {k}\le \ell-2$.

Burckel shows in¨[@Bus] that every positive $3$-braid admits a unique normal expression and, moreover, that ${x}{<}{y}$ holds if and only if the normal form of¨${x}$ is $\mathtt{ShortLex}$-smaller than the normal form of¨${y}$, where $\mathtt{ShortLex}$ refers to the variant of the lexicographic ordering of sequences in which the length is given priority: $(e_1,
\dots, e_\ell) <_{\mathtt{ShortLex}} (e'_1, \dots,
e'_{\ell'})$ holds for $\ell < \ell'$, and for $\ell =
\ell'$ and $(e_1, \dots, e_\ell)$ lexicographically smaller than¨$(e'_1, \dots, e'_{\ell'})$. Burckel’s method consists in defining an iterative reduction process on non-normal braid words. Our current approach allows for an alternative, simpler method. First, a direct inspection shows:

Let ${\underline{S}_{3}^{{d}}}$ be the sequence of braid words defined by the inductive rule¨. Then ${\underline{S}_{3}^{{d}}}$ consists of words that are normal in the sense of Burckel.

Then, by construction, every braid in¨${S_{3}^{{d}}}$ is represented by a word of¨${\underline{S}_{3}^{{d}}}$, so, as every positive $3$-braid occurs in¨$\bigcup{S_{3}^{{d}}}$, we immediately deduce:

Every positive $3$-braid admits an expression that is normal in the sense of Burckel.

This in turn enables us to obtain a simple proof for the following deep, and so far not very well understood result originally due to Laver¨[@Lve] (and to Burckel [@Bus] for the ordinal type):

The restriction of¨${<}$ to¨$B_3^+$ is a well-ordering of ordinal type¨$\omega^\omega$.

The $\mathtt{ShortLex}$ ordering of sequences of nonnegative integers is a well-ordering of ordinal type¨$\omega^\omega$, so its restriction to codes of normal words in the sense of Burckel is a well-ordering as well. The type of the latter cannot be less than¨$\omega^\omega$ as one can easily exhibit an increasing sequence of length¨$\omega^\omega$.

Burckel’s approach extends to all braid monoids¨$B_{n}^+$, at the expense of introducing a convenient notion of normal word and defining an associated reduction process which is very intricate. Completing the construction of the sequences¨${S_{4}^{{d}}}$ and, more generally, ${S_{{n}}^{{d}}}$ along the lines described above would hopefully allow for an alternative much simpler approach. In particular, once the correct definition is given, all subsequent proofs should reduce to easy inductive verifications.

[99]{}

Bir; J.Birman; Braids, links, and mapping class groups; Annals of Math. Studies 82, Princeton Univ. Press (1975).

Bus; S.Burckel; The wellordering on positive braids; J. Pure Appl. Algebra; 120-1; 1997; 1–17.

But; S.Burckel; Computation of the ordinal of braids; Order; 16; 1999; 291–304.

Buu; S.Burckel; Syntactical methods for braids of three strands; J. Symb. Comp.; 31; 2001; 557–564.

CSV; L.Carlitz, R.Scoville & T.Vaughan; Enumeration of pairs of permutations; Discrete Math.; 14; 1976; 215–239.

Chb; R. Charney; Geodesic automation and growth functions for Artin groups of finite type; Math. Ann.; 301-2; 1995; 307–324.

Dfb; P. Dehornoy; Braid groups and left distributive operations; Trans. Amer. Math. Soc.; 345-1; 1994; 115–151.

Dfo; P.Dehornoy; A fast method for comparing braids; Advances in Math.; 125; 1997; 200–235.

Dgb; P.Dehornoy; Strange questions about braids; J. Knot Th. and its Ramifications; 8-5; 1999; 589–620.

Dgk; P.Dehornoy; Groupes de Garside; Ann. Scient. Ec. Norm. Sup.; 35; 2002; 267–306.

Dgr; P.Dehornoy, I. Dynnikov, D. Rolfsen, B. Wiest; Why are braids orderable?; Panoramas & Synthèses vol. 14, Soc. Math. France (2002).

Dhi; P.Dehornoy; Combinatorics of normal sequences of braids; Preprint.

ElM; E.A.Elrifai & H.R.Morton; Algorithms for positive braids; Quart. J. Math. Oxford; 45-2; 1994; 479–497.

Eps; D.Epstein, J.Cannon, D.Holt, S.Levy, M.Paterson & W.Thurston; Word Processing in Groups; Jones & Bartlett Publ. (1992).

Gar; F.A.Garside; The braid group and other groups; Quart. J. Math. Oxford; 20-78; 1969; 235–254.

Lrb; D.Larue; Left-distributive and left-distributive idempotent algebras; Ph D Thesis, University of Colorado, Boulder (1994).

Lve; R.Laver; Braid group actions on left distributive structures and well-orderings in the braid group; J. Pure Appl. Algebra; 108-1; 1996; 81–98.

McC; J.Mc Cammond; An introduction to Garside structures; Preprint (2005).

Sol; L.Solomon; A Mackey formula in the group ring of a Coxeter group; J. Algebra; 41; 1976; 255-268.
