On the centralizer of generic braids
Juan González-Meneses and Dolores Valladares∗

arXiv:1802.04897v1 [] 13 Feb 2018

February, 2018

Abstract
We study the centralizer of a braid from the point of view of Garside theory, showing that
generically a minimal set of generators can be computed very efficiently, as the ultra summit
set of a generic braid has a very particular structure. We present an algorithm to compute the
centralizer of a braid whose generic-case complexity is quadratic on the length of the input,
and which outputs a minimal set of generators in the generic case.

1

Introduction

Braid groups, introduced by Artin [1, 2], and more generally Artin-Tits groups of spherical type [7,
8], have a very particular algebraic structure, called Garside structure, which can be used to
deduce many porperties, make computations and solve decision problems in these groups. Groups
admitting such a Garside structure are called Garside groups [13, 12].
Among the basic results concerning braid groups that are obtained using its Garside structure, one
can find the solutions to the word problem [18, 15, 5] and the conjugacy problem [18, 14, 5, 16,
19, 3, 20, 21]. Closely related to the latter is the problem of determining the centralizer of a given
braid [26, 17, 23, 24]. In 1971, Makanin [26] gave an algorithm to compute a generating set of the
centralizer Z(x) of any given braid x. This method can be easily generalized to all Garside groups,
but it has a huge complexity and highly redundant generating sets. A much better algorithm
was given in [17], although the actual complexity of the algorithm and the number of generators
given as output is not clear. A different approach uses the geometric properties of braids [23],
since the geometric classification of a braid as periodic, reducible or pseudo-Anosov determines
the structure of its centralizer. For instance, if x is pseudo-Anosov, one can use the well-known
result by McCarthy [27, 22] applied to braids [23], to see that Z(x) is isomorphic to Z × Z. One
generator is pseudo-Anosov, usually a root of x, and the other generator is periodic, and can be
chosen to be a root of the Garside element ∆2 . But in order to compute the generators of Z(x),
the procedure in [17] is usually applied.
The main idea of the algorithm in [17] is to compute, given a braid x, a finite set of elements
called its ultra summit set (U SS(x)), which is an invariant subset of the conjugacy class of x. The
elements of this set are computed along with conjugating elements connecting them, so the ultra
summit set is stored as a directed graph, Γx . A generating set of the fundamental group of Γx
yields a generating set of the centralizer of x, in a natural way.
The algorithm in [17] is very efficient in practice. So the question arises whether, generically, this
algorithm will produce a small number of generators in a short time. One can see from computations
that, in most cases, the graph Γx is quite small and satisfies a very particular property: conjugating
elements correspond to factors of the normal form of x. In this case we will say that U SS(x) is
minimal (cf. Definition 4.1). We will show in this paper that, indeed, this case is generic.
Before stating the result, we need to clarify what do we understand by generic. We will consider
the braid group Bn with some natural generating set (the set of simple elements). In the Cayley
∗ Both authors partially supported by Spanish Projects MTM2013-44233-P and FEDER. First author partially
supported by MTM2016-76453-C2-1-P and FEDER.

1

graph of Bn with respect to this set of generators, we will consider the ball B(l) of radius l centered
at the neutral element. We will say that a property P is generic in Bn , or that the braids satisfying
P are generic, if the proportion of braids which satisfy P in B(l) tends to 1 as l tends to infinity.
For instance, Wiest and Caruso [10] showed that braids which admit a ‘short’ conjugation to a rigid
pseudo-Anosov braid are generic (rigidity is a Garside theoretical property that will be explained
later). In particular, pseudo-Anosov braids are generic. In [10] it is also proved that braids which
admit a given factor in its normal form are generic. Studying with more detail the properties of
these generic braids, we show the following:
Theorem 4.8. The proportion of braids in B(l) whose ultra summit set is minimal tends to 1
exponentially fast, as l tends to infinity.
In this generic case in which the ultra summit set of a braid x is minimal, we will be able to describe
an explicit minimal set of generators for its centralizer, as follows. In general U SS(x) consist of
a set of orbits under a special kind of conjugation called cycling. The conjugating elements for
iterated cycling, starting from x, will be denoted a1 , a2 , . . . As this orbit is finite, there is some
k > 0 such that cycling k times x one gets back to x. In other words, if we define P C(x) = a1 · · · ak ,
then P C(x) commutes with x. We will show that if U SS(x) is minimal, then it has at most two
orbits, and we can describe all possible cases as follows:
Theorem 5.3. Let x be a rigid braid such that U SS(x) is minimal and has two orbits under
cycling. Then Z(x) = P C(x), ∆2 .
Theorem 5.5. Let x be a rigid braid such that U SS(x) is minimal and has only one orbit under
cycling of length k. One has:
E
D
i) If ∆−1 x∆ 6= x, then Z(x) = a1 · · · a k ∆−1 , ∆2 .
2

−1

ii) If ∆

x∆ = x, then Z(x) = hP C(x), ∆i.

From Theorem 4.8 it follows that Theorem 5.3 and Theorem 5.5 are describing the centralizers of
generic braids. This yields an algorithm to compute a minimal set of generators for the centralizer
of a braid, which runs generically in polynomial time.
Corollary 6.2. There exists an algorithm to compute a generating set for the centralizer of a braid
y ∈ Bn , whose generic-case complexity is O(l2 n4 log n), where l = ℓ(y).
The plan of the paper is as follows: in Section 2.1 we describe basic facts about Garside groups.
In Section 2.2 and 2.3 we give the basic definitions and results concerning the left normal form
and the conjugacy problem, respectively. In Section 2.4 we describe the structure of ultra summit
sets, defining the minimal simple elements introduced in [17] and two special kind of conjugations
from [4]. We finish this section with basic notions about the transport map, which will be used
several times in this paper. In Section 3, thanks to the work by Caruso and Wiest [10] about
genericity of rigid pseudo-Anosov braids, we prove some needed results about generic braids. In
Section 4, we define minimal ultra summit sets and we show that the ultra summit set of a generic
braid is minimal. Section 5 is devoted to determine the centralizer of generic braids. Finally, in
Section 6 we present our algorithm and study its complexity.

2
2.1

Background
Garside groups

A Garside group is a group G which admits a submonoid P and a special element ∆ ∈ P satisfying
some suitable properties [13]. We will apply Garside properties to the particular case of the braid
group Bn , so we will just enumerate the needed results in this setting, starting with the classical
presentation of Bn :


σi σj = σj σi
if |j − i| > 1
.
Bn = σ1 , . . . , σn−1
σi σj σi = σj σi σj if |j − i| = 1
2

The elements of Bn which can be written as a product positive powers of generators are called
positive elements, and they form the monoid P , usually denoted Bn+ . The special element ∆, called
Garside elment, is:
∆ = (σ1 σ2 · · · σn−1 )(σ1 σ2 · · · σn−2 ) · · · (σ1 σ2 )σ1 .
Given two braids a, b ∈ Bn , we say that a is a prefix of b, and we write a 4 b, if a−1 b ∈ Bn+ . This
determines a partial order in Bn which is invariant under left-multiplication, and is a lattice order.
We denote a ∧ b (resp. a ∨ b) the meet (resp. the join) of the braids a and b with respect to 4.
We will also say that a ∧ b is the greatest common prefix of a and b, and that a ∨ b is their least
common multiple.
The set [1, ∆] = {s ∈ Bn |1 4 s 4 ∆} ⊂ Bn+ , called the set of simple elements of Bn , is a very
particular finite set of generators of Bn , which are the building blocks of the normal forms that we
will see later.
The generators σ1 , . . . , σn are called atoms. Conjugation by the Garside element ∆ determines an
inner automorphism of Bn that we denote τ (that is, τ (x) = ∆−1 x∆). It is easy to check that
τ (σi ) = σn−i for every i = 1, . . . , n − 1, so τ has order 2 and ∆2 is central. Actually, the center of
Bn is cyclic, generated by ∆2 .
Throughout this paper we will focus on the braid group Bn , although some results could be
extended or adapted to other Garside groups, as their proofs basically involve techniques from
Garside theory.

2.2

Left normal form

Let us see how the Garside structure of Bn allows to define a particular unique decomposition of
each braid, called its left normal form.
Definition 2.1. Given a simple element s ∈ [1, ∆], the right complement of s is defined by
∂(s) = s−1 ∆, and the left complement of s is ∂ −1 (s) = ∆s−1 .
Notice that the map ∂ is a bijection of [1, ∆] and that ∂ 2 = τ [3].
Definition 2.2. [15] Let s, t be two simple elements in Bn . We say that the decomposition st is
left-weighted if ∂(s) ∧ t = 1 or, equivalently, ∆ ∧ st = s.
Definition 2.3. [15] Given x ∈ Bn , we say that a decomposition x = ∆p x1 . . . xl , where p ∈ Z and
l ≥ 0, is the left normal form of x if xi ∈ [1, ∆] \ {1, ∆} for i = 1, . . . , l and xi xi+1 is a left-weighted
decomposition for i = 1, . . . , l − 1.
Definition 2.4. [15] Given x ∈ Bn whose left normal form is ∆p x1 . . . xl , we define the infimum,
supremum and canonical length of x, respectively, by inf(x) = p, sup(x) = p + l and ℓ(x) = l.
It is well known that left normal forms of elements in Bn exist and are unique [15, 14]. The right
complement plays an important role when comparing the left normal forms of x and x−1 .
Theorem 2.5. [3] If x = ∆p x1 . . . xl is in left normal form, then the left normal form of x−1 is
equal to x−1 = ∆−p−l x′l . . . x′1 ,, where x′i = τ −p−i (∂(xi )), for i = 1, . . . , l.
As we saw in Definition 2.2, the decomposition st is left-weighted if ∂(s) and t have no prefixes in
common, except the trivial one. As ∂(s) is the simple element such that s∂(s) = ∆, the prefixes
of ∂(s) are precisely those simple elements s′ for which ss′ is simple. Hence, the decomposition st
is left-weighted if and only if the only prefix s′ of t such that ss′ is simple is the trivial one.
Given two simple elements s and t, it is easy to find the left-weighted decomposition of the product
st using the description above. If the decomposition st is not left-weighted, this means that there
is a nontrivial prefix s′ 4 t such that ss′ is simple. Since 4 is a lattice order, there is a maximal
element satisfying this property, namely s′ = ∂(s) ∧ t. Hence, transforming the decomposition st
into a left-weighted one means to slide the prefix s′ from the second factor to the first one. That
3

is, write t = s′ t′ and then consider the decomposition st =(ss′ )t′ , with ss′ as the first factor and
t′ as the second one. Since s′ is maximal, the decomposition (ss′ )t′ is left-weighted.
The action of obtaining the left-weighted decomposition of the product of two simple elements s
and t, by sliding the simple element s′ from the second factor to the first factor, is known as a
local sliding applied to the decomposition st. Using local slidings one can compute the left normal
form of any element of a Garside group.

2.3

The conjugacy problem

The known algorithms to solve the conjugacy problem in braid groups share a common strategy.
Given an element x ∈ Bn , the idea is to compute a finite subset of the conjugacy class xBn of x,
which consists of those conjugates satisfying some suitable conditions, and which only depends on
xBn , not on x itself. There are two special types of conjugations ever since the work of ElRifai and
Morton in [14]:
Definition 2.6. Given x = ∆p x1 · · · xl written in left normal form, where l > 0,
the cycling of x is:
c(x) = ∆p x2 · · · xl τ −p (x1 ),
and the decycling of x is:
d(x) = xl ∆p x1 · · · xl−1 .
The conjugating elements involved in a cycling or a decycling will play a crucial role later, so to
avoid repeated references to the automorphism τ we introduce the following definition.
Definition 2.7. [3] Let x be a braid with left normal form x = ∆p x1 · · · xl (l > 0). We define the
initial factor of x as ι(x) = τ −p (x1 ), and the final factor of x as ϕ(x) = xl . If l = 0 we define
ι(∆p ) = 1 and ϕ(∆p ) = ∆.
Notice that, up to conjugation by ∆p , the simple element ι(x) (resp. ϕ(x)) corresponds to the first
(resp. last) non-∆ factor in the left normal form of x. From Theorem 2.5, the initial and final
factors of x and x−1 are closely related.
Lemma 2.8. [3] For every x ∈ Bn one has ι(x−1 ) = ∂(ϕ(x)) and ϕ(x−1 ) = ∂ −1 (ι(x)).
Lemma 2.9. [4] Given x ∈ Bn with ℓ(x) > 0, one has:
xι(x) = c(x),

xϕ(x)

−1

= d(x),

xι(x

−1

)

= x∂(ϕ(x)) = τ (d(x)).

We define the twisted decycling of x as τ (d(x)).
Going back to the conjugacy problem, the finite invariant subset of xBn defined in [14] is called the
super summit set of x, denoted SSS(x). It consists of the conjugates of x having minimal canonical
length. This minimal canonical length among the conjugates of x is called the summit length of x,
and denoted ℓs (x). In [14] it was shown that one obtains an element in SSS(x), starting with x,
by iterated application of cyclings and decyclings.
We will not consider SSS(x) in this paper, but the following invariant subset of SSS(x) introduced
by Gebhardt:
Definition 2.10. [19] The ultra summit set U SS(x) of x ∈ Bn is the set of elements y ∈ SSS(x)
such that cm (y) = y, for some m > 0.
We remark that one obtains an element in U SS(x) by iterated application of cycling to an element
in SSS(x). Thus, the ultra summit set U SS(x) consists of a finite set of disjoint, closed orbits
under cycling. Once one obtains an element in U SS(x), it is explained in [19] how to compute all
elements in U SS(x), together with conjugating elements connecting them.
This was improved in [20] by introducing a new kind of conjugation, called cyclic sliding, to
replace cycling and decycling. Cyclic sliding simplifies the algorithms concerning conjugacy in
Garside groups, and in particular in braid groups.
4

Definition 2.11. [20] Given x ∈ Bn , its preferred prefix is p(x) = ι(x) ∧ ι(x−1 ) = ι(x) ∧ ∂(ϕ(x)).
Definition 2.12. [20] For x ∈ Bn , the cyclic sliding of x is s(x) = xp(x) = p(x)−1 x p(x).
Using cyclic sliding one can define a new subset of the conjugacy class of a braid x, which is
contained in U SS(x). If one applies iterated cyclic sliding to an element x ∈ Bn , one eventually
obtains a repeated element, say y. The orbit of y under cyclic sliding will be called a sliding circuit.
The set of all (disjoint) sliding circuits in the conjugacy class of x is the mentioned invariant subset:
Definition 2.13. [20] The set of sliding circuits SC(x) of x ∈ Bn is the set of conjugates y ∈ xBn
such that sm (y) = y, for some m > 0.
In this paper we will study the centralizer of a special kind of braids, called rigid braids. The idea
of studying rigidity came from the study of elements whose left normal form changes only in the
obvious way under cyclings, decyclings and powers, so their ultra summit sets are easier to study.
Rigid elements in Garside groups were studied in [3].
Definition 2.14. [3] Let x = ∆p x1 . . . xl be in left normal form, with l > 0. Then x is rigid if
ϕ(x)ι(x) is left-weighted as written, that is, if p(x) = 1.

2.4

Minimal simple elements

Let us focus on the ultra summit set U SS(x) of a braid x ∈ Bn . As we said earlier, the elements
of U SS(x) are computed along with conjugating elements connecting them. We will describe in
detail those conjugating elements. We shall use the notation y s = s−1 ys.
Definition 2.15. [19] Given x ∈ Bn and y ∈ U SS(x), we say that a simple element 1 6= s ∈ [1, ∆]
is a minimal simple element for y (with respect to U SS(x)) if y s ∈ U SS(x), and y t ∈
/ U SS(x) for
every 1  t  s.
Definition 2.16. Given x ∈ Bn , the directed graph Γx is defined as follows:
• The vertices are the elements of U SS(x).
• There is an arrow with label s going from y to y s , for every minimal simple element s for y.
In [19] Gebhardt described how to compute the minimal simple elements for a given y ∈ U SS(x).
Moreover, he shows the following:
Theorem 2.17. ([19, Theorem 1.18 and Corollary 1.19]) Let x ∈ Bn and y ∈ U SS(x).
i) If s, t ∈ Bn are such that y s ∈ U SS(x) and y t ∈ U SS(x), then y s∧t ∈ U SS(x).
ii) For every u ∈ Bn+ there is a unique element cy (u) which is minimal with respect to 4 among
the elements υ satisfying u 4 υ and y υ ∈ U SS(x).
iii) The graph Γx described in Definition 2.16 is finite and connected. Its transitive closure is a
complete graph, i.e., every vertex is reachable from every other vertex by an oriented path.
By the above result, given one element x
e ∈ U SS(x), one can obtain any other element in U SS(x)
just through conjugations by minimal simple elements. In this way one can compute the whole
graph Γx , starting with a single element x
e ∈ U SS(x).
From now on, to simplify the notation, we will assume that x belongs to its own ultra summit set.
That is, x ∈ U SS(x). It is known that conjugations by minimal simple elements are quite special:

Corollary 2.18. [4, Theorem 2.5] Let x ∈ U SS(x) with ℓ(x) > 0 and let s be a minimal simple
element for x. Then s is a prefix of either ι(x) or ι(x−1 ), or both.
Definition 2.19. Let x ∈ Bn . A partial cycling of x is a conjugation of x by a prefix of ι(x). A
partial twisted decycling of x is a conjugation of x by a prefix of ι(x−1 ) = ∂(ϕ(x)).
5

Consequently, by Theorem 2.17 and Corollary 2.18, given x, y ∈ U SS(x), there exists a sequence
of partial cyclings and partial twisted decyclings joining x to y.
Due to Corollary 2.18, there are two kinds of minimal simple elements, hence there are two kinds
of arrows in Γx . Following [4], we say that an arrow s starting at a vertex y ∈ U SS(x) is black if s
is a prefix of ι(y), and it is grey if s is a prefix of ι(y −1 ). In other words, an arrow starting at y is
black if it corresponds to a partial cycling of y, and it is grey if it corresponds to a partial twisted
decycling of y. Notice that an arrow can, a priori, be black and grey at the same time. In that
case, we say it is a bi-colored arrow.
Definition 2.20. A path in Γx is a (possibly empty) sequence (se11 , . . . , sekk ), where si is an arrow
ei+1
for every
in Γx and ei = ±1, such that the endpoint of sei i is equal to the starting point of si+1
ek
e1
i = 1, . . . , k − 1. We say that a path (s1 , . . . , sk ) is oriented if ei = 1 for i = 1, . . . , k.
Remark. Every path (se11 , . . . , sekk ) determines an element α = se11 . . . sekk . Distinct paths may
determine the same element. Since the labels of arrows are simple elements, it follows that if the
path is oriented then α ∈ Bn+ .
We end this subsection with the case of rigid braids, since the structure of Γx we described above
will be simpler in this case. Concerning the arrows of Γx , the main difference between the case of
a rigid braid and the general case is the following:
Lemma 2.21. [4] Let x ∈ U SS(x) and ℓ(x) > 0. Then x is rigid if and only if there are no
bi-colored arrows starting at x.
Refer to [4, §2.1] to see several examples illustrating the notions we have seen in this subsection.

2.5

The transport map

We finish this introductory section explaining a tool that will be used several times in this paper:
The transport map. Given two conjugate braids x and xα = α−1 xα, the images of x and xα under
cycling are also conjugate, and we can relate α to a conjugating element for the images c(x) and
c(xα ).
Definition 2.22. [19] Given x, α ∈ Bn , we define the transport of α at x under cycling as
α(1) = ι(x)−1 αι(xα ).
That is, α(1) is the conjugating element that makes the following diagram commutative, in the
sense that the conjugating element along any closed path is trivial:
ι(x)

x −−−−→ c(x)


 (1)

αy
yα
ι(xα )

xα −−−−→ c(xα )

Note that the horizontal rows in this diagram correspond to applications of cycling. For an integer
i > 1 we define recursively α(i) = (α(i−1) )(1) , which is the transport of α(i−1) at ci−1 (x). We also
define α(0) = α.
Under certain conditions, the transport under cycling respects many aspects of the Garside structure. In particular, if x and xα as above are super summit elements, that is, x and xα have minimal
canonical length in their conjugacy class, the transport map preserves products, left divisibility,
greatest common prefixes, and powers of ∆. For more details, refer to [19].
Suppose that a given braid x is rigid. Then x belongs to its ultra summit set (it trivially belongs to
SC(x), which is contained in U SS(x)), and the minimal simple elements for x have some particular
properties that we will show to end this section. These properties can be deduced from the results
in [4], but we will provide proofs.
6

Lemma 2.23. Let x be a rigid braid with normal form ∆p x1 · · · xl (l > 0), and let a = ι(x). Then
a(kl+r) = τ −(k+1)p (xr+1 ), for all k ≥ 0 and all r = 0, . . . , l − 1.
Proof. For every i > 0, we have the following diagram:
ι(x)

ι(c(x))

ι(c(x))

ι(c2 (x))

ι(ci−1 (x))

x −−−−→ c(x) −−−−→ c2 (x) −−−−→ · · · −−−−→ ci−1 (x) −−−−−−→




 (i−1)
 (2)
a=ι(x)
 (1)
ya
ya
y
ya

c(x) −−−−→ c2 (x) −−−−−→ c3 (x) −−−−→ · · · −−−−→

ci (x)

ι(ci (x))

ci (x)

 (i)
ya

−−−−−−−−−→ ci+1 (x)

By definition of the transport of a at x,
a(i)

=
=

ι(ci−1 (x))−1 · · · ι(c(x))−1 ι(x)−1 ι(x) ι(c(x)) · · · ι(ci−1 (x)) ι(ci (x))
ι(ci (x))

By hypothesis, a = ι(x) = τ −p (x1 ), so the result is true for k, r = 0. Since x is rigid, c(x) =
∆p x2 · · · xl a is in left normal form as written. Then c(x) is also rigid. Applying the same argument
to each cycling of x, it follows that ci (x) is rigid for every i > 0, and that cycling just corresponds
to cyclic permutation of the factors of x (up to conjugation by some power of ∆). More precisely,
every l cyclings, the factors of the normal form of x go back to their original position, but each
one is conjugated by ∆−p . Therefore a(kp+r) = ι(ckp+r (x)) = τ −(k+1)p (xr+1 ), as we wanted to
show.
We will use several times the following important property, which shows that, in U SS(x), iterated
transport of an element always comes back to the original element.
Lemma 2.24. [19, Lemma 2.6] Let x belong to Garside group, and let u be a positive element.
Assume that x, xu ∈ U SS(x). Let m be a positive integer such that cm (x) = x and cm (xu ) = xu .
Then u(km) = u for some k > 0.
We can deduce the following property for minimal simple elements.
Lemma 2.25. Let x ∈ U SS(x) and let u be a minimal simple element for x with respect to
U SS(x). Then, u(i) is a minimal simple element for ci (x), for all i ≥ 1.
Proof. Suppose that u(i) is not a minimal simple element for some i. So there exist nontrivial
positive elements a, b such that u(i) = ab and (ci (x))a ∈ U SS(x). By Lemma 2.24, iterated
transport of a comes back to a, hence a(j) 6= 1 for every j > 0 (as if a trivial element is obtained,
all the forthcoming transports would be trivial). In the same way, b(j) 6= 1 for every j > 0. But
we know, by Lemma 2.24 again, that u(i+t) = u for some t > 0. As transport preserves products,
we have u = u(i+t) = (u(i) )(t) = (ab)(t) = a(t) b(t) , where a(t) 6= 1, b(t) 6= 1 and, by construction,
(t)
x(a ) ∈ U SS(x). This contradicts the minimality of u.
Definition 2.26. Let x be a rigid braid (so x ∈ U SS(x)) with left normal form ∆p x1 · · · xl . We
say that a simple factor of the normal form of x, say xr , is minimal if τ −p (xr ) is a minimal simple
element for cr−1 (x) with respect to U SS(x).
As a direct consequence of Lemma 2.25 and Lemma 2.23, we have the following.
Corollary 2.27. Let x be a rigid braid whose left normal form is ∆p x1 · · · xl . If a simple factor
of its normal form is minimal, then all factors are minimal.
Proof. Suppose xr is minimal for some r = 1, . . . , l. This means that τ −p (xr ) is a minimal simple
element for cr−1 (x) with respect to U SS(x). Since x is rigid, cr−1 (x) is also rigid. Hence, by
Lemma 2.25, (τ −p (xr ))(i) is a minimal simple element for every i > 0.
On the other hand, by Lemma 2.23, every simple factor of the normal form of x will eventually
appear as a transport of τ −p (xr ), up to conjugation by some power of ∆. Since conjugation by ∆
preserves minimal simple elements, the result follows.
7

3

Generic braids

We will now present some results by Caruso and Wiest [9, 10] on generic braids, and adapt them
to our purposes.
Let B(l) be the ball of radius l centered at 1 in the Cayley graph of the braid group Bn , with
generators the simple braids. We are interested in the proportion of braids in B(l) which have a
very particular ultra summit set, when l tends to infinity. In order to find this proportion, we will
follow the arguments in [10].
Let Bnp,l = {x ∈ Bn | inf (x) = p, ℓ(x) = l}. The sets Bnp,l are disjoint as left normal forms are
unique. Since left normal forms are closely related to the so-called mixed normal forms [11], and
the latter are geodesics in the mentioned Cayley graph of Bn , is follows that
B(l) =

l
l−k
G
G

Bnη,k .

(1)

k=0 η=−l

So B(l) is the disjoint union of a finite number of sets of the form Bnη,k . Also, it is shown in [9]
k
|B η,k |
that Bnη,k = Θ(λk ) for some λ > 1, meaning that the sequences λnk and Bλη,k stay bounded
| n |
as k tends to infinity.
Definition 3.1. [10] Let x be a braid with left normal form x = ∆p x1 · · · xl . Let us denote
P (x) = x2·⌈ l ⌉+1 · · · xl−2·⌈ l ⌉ (the middle fifth of the left normal form). A conjugation of x is
5
5
non-intrusive if the normal form of the conjugated braid contains P (x) as a subword.
Proposition 3.2. [10] There exists a constant 0 < µR < 1 (which depends only on n) such that,
among the braids in Bnp,l , the proportion of those that can be non-intrusively conjugated to a rigid
pseudo-Anosov braid is at least 1 − µlR , for sufficiently large l.
Lemma 3.3. [9] Let w be a fixed braid of infimum 0. Then there exists a constant 0 < µM < 1
such that the proportion of braids x ∈ Bnp,l for which w appears as a set of consecutive factors of
the normal form of P (x) is at least 1 − µlM , for sufficiently large l.
We are interested in the following kind of braids:
Definition 3.4. Let x be a braid with left normal form x = ∆p x1 · · · xl . We say that x is a
σ1 -non-intrusive braid if x admits a non-intrusive conjugation to a rigid pseudo-Anosov braid and
σ1 and ∂(σ1 ) are simple factors of P (x).
Corollary 3.5. There exists a positive constant 0 < µ < 1 such that the proportion of σ1 -nonintrusive braids in Bnp,l is at least 1 − µl , for sufficiently large l.
Proof. We just need to take µ > max(µR , µM1 , µM2 ), where µR is the constant appearing in Proposition 3.2,
µM1 is the constant appearing in Lemma 3.3 for w = σ1 , and µM1 is the constant appearing
in Lemma 3.3 for w = ∂(σ1 ).
Corollary 3.6. The proportion of σ1 -non-intrusive braids in B(l) tends to 1 as l tends to infinity.
Moreover, this convergence happens exponentially fast.
Proof. This is similar to the proof of Theorem 5.1 in [10]. The ball B(l) can be decomposed as
in (1), where the size of each Bnη,k is Θ(λk ) for some λ > 1. In each Bnη,k , the proportion of
σ1 -non-intrusive braids is at least 1 − µk for sufficiently large k. Let k0 be the biggest value of k
such that the mentioned proportion is smaller than 1 − µk . Then, for l > k0 , we can decompose

 

k0 l−k
l
l−k
G
G
G
G
G
B(l) = 
Bnη,k  
Bnη,k  .
k=k0 +1 η=−l

k=0 η=−l

8

The size of the set on the left is O((k0 + 1)(2l + 1)λk0 ), that is, O(2l + 1). In the set on the right,
the number of braids which are not σ1 -non-intrusive is

O (2l − k0 )(λµ)k0 +1 + (2l − k0 − 1)(λµ)k0 +2 + · · · (l + 2)(λµ)l−1 + (l + 1)(λµ)l .

Now notice that the number of elements in B(l) is at least |Bn0,l | = Θ(λl ). Therefore, the proportion
of braids which are not σ1 -non-intrusive in B(l) is


(2l − k0 − 1)µk0 +2
(l + 2)µl−1
2l + 1 (2l − k0 )µk0 +1
l
+
+
+
·
·
·
+
+
(l
+
1)µ
O
λl
λl−k0 −1
λl−k0 −2
λ

l 
≤ O (2l + 1)(l + 1) max(λ−1 , µ)
.
This tends exponentially fast to 0, hence the proportion of σ1 -non-intrusive braids in B(l) tends
exponentially fast to 1, as l tends to infinity.

4

Minimal ultra summit set

Once we showed that σ1 -non-intrusive braids are generic, we will see that their ultra summit sets are
particularly simple. Recall the directed graph Γx related to the ultra summit set U SS(x) of a braid
x, and recall also that the arrows in Γx can be black or grey (or both). Since U SS(x) ⊂ SSS(x),
the canonical length of all elements in U SS(x) is the same, namely ℓs (x).
Definition 4.1. Let x ∈ Bn . We say that U SS(x) is minimal if ℓs (x) > 1 and, for every vertex y
in Γx there is only one black arrow starting at y, corresponding to ι(y), and only one grey arrow
starting at y, corresponding to ι(y −1 ) = ∂(ϕ(y)).
Lemma 4.2. Let x ∈ Bn . If U SS(x) is minimal, then all elements in U SS(x) are rigid.
Proof. Recall that y is rigid if and only if p(y) = ι(y) ∧ ι(y −1 ) = 1. Suppose that U SS(x) is
minimal, that is, for every y ∈ U SS(x), ι(y) and ι(y −1 ) are minimal simple elements for y. This
−1
means that y ι(y) and y ι(y ) belong to U SS(x) and no proper positive prefix of either conjugating
element conjugates y to U SS(x). Let s = ι(y) ∧ ι(y −1 ). By Theorem 2.17, y s ∈ U SS(x). Since
s is a prefix of both ι(y) and ι(y −1 ), which are minimal, there are just two possible cases: Either
s = ι(y) = ι(y −1 ) or s = ι(y) ∧ ι(y −1 ) = 1.
Suppose that s = ι(y) = ι(y −1 ). That is, ι(y) = ∂(ϕ(y)). We would then have ϕ(y)ι(y) =
ϕ(y)∂(ϕ(y)) = ∆. But then, if ∆p y1 · · · yl is the left normal form of y, we would have c(y) =
∆p y2 · · · yl−1 ϕ(y)ι(y) = ∆p y2 · · · yl−1 ∆, hence the canonical length of c(y) would be smaller than
the canonical length of y, contradicting the fact that y ∈ U SS(x). Hence, ι(y) ∧ ι(y −1 ) = 1,
meaning that y is rigid for every y ∈ U SS(x).
Suppose that U SS(x) is minimal, so by Lemma 4.2 it consists of rigid elements. By definition,
at every vertex y of Γx there are two outgoing arrows, a black one corresponding to ι(y), and a
grey one corresponding to ι(y −1 ) = ∂(ϕ(y)). But once the conjugation by ι(y) is performed, as y
is rigid, the last factor of the obtained element is precisely ι(y). This means that every vertex of
Γx has exactly one incoming black arrow, which corresponds to its final factor. In the same way,
as y −1 is rigid (rigidity is preserved by taking inverses), the same argument applies to the grey
arrows: Every vertex of Γx has exactly one incoming grey arrow, which corresponds to the final
factor of its inverse.
Therefore, the graph Γx , locally at y, is as sketched in Figure 1, where the grey arrows are represented by dashed lines.

9

u

v
b2

b1

y
g1

g2

w

z

Figure 1: Black and grey arrows in Γx , locally at a vertex y in a minimal ultra summit set.
Lemma 4.3. Let U SS(x) be minimal and let y ∈ U SS(x). Using the notations in Figure 1, the
following conditions hold:
i) b1 b2 is left-weighted.
ii) g1 g2 is left-weighted.
iii) b1 g2 = ∆.
iv) g1 b2 = ∆.
Proof. By Lemma 4.2, we know that y is rigid, and then y −1 is also rigid. We recall that each
black arrow is the initial factor of its source, and the final factor of its target. Also, each grey
arrow is the initial factor of the inverse of its source, and the final factor of the inverse of its target.
Hence:
i) b1 = ϕ(y) and b2 = ι(y). Since y is rigid, b1 b2 is left-weighted.
ii) g1 = ϕ(y −1 ) and g2 = ι(y −1 ). Since y −1 is rigid, g1 g2 is left-weighted.
iii) b1 = ϕ(y) and g2 = ι(y −1 ) = ∂(ϕ(y)) by Lemma 2.8. Hence b1 g2 = ∆.
iv) b2 = ι(y) and g1 = ϕ(y −1 ) = ∂ −1 (ι(y)) by Lemma 2.8. Hence g1 b2 = ∆.

Corollary 4.4. If U SS(x) is minimal, then one of the following conditions holds:
i) U SS(x) has two orbits under cycling, conjugate to each other by ∆
ii) U SS(x) has one orbit under cycling, conjugate to itself by ∆.
Proof. By Lemma 4.2, U SS(x) consists of rigid elements. As every rigid element belongs to
U SS(x) (cycling is roughly a cyclic permutation of its factors), it follows that U SS(x) is the
set of rigid conjugates of x. (This was already shown in [20, Theorem 1], anyway).
Let y ∈ U SS(x). As U SS(x) is minimal, every black arrow in Γx corresponds to a cycling.
Hence, iteratively conjugating y by black arrows, we obtain the whole orbit of y under cycling.
Now consider the grey arrow g2 starting at y, and denote by b1 the black arrow ending at y as
in Figure 1. Denote by u the source of b1 and by z the target of g2 . By Lemma 4.3 b1 g2 = ∆,
hence u∆ = z. Since u belongs to the orbit of y under cycling, say Oy , it follows that z belongs
τ (Oy ). This happens for all elements in U SS(x): Every grey arrow in Γx sends an element in an
orbit O, to an element in τ (O).
Therefore, if we start at an orbit O, conjugating by a black arrow we stay in O, and conjugating
by a grey arrow we pass to the orbit τ (O). As all elements in U SS(x) are connected by black and
grey arrows, and ∆2 is a central element, it follows that in U SS(x) there are at most two orbits:
If the orbit O is conjugate to itself by ∆, there will be just one orbit; otherwise, there will be two
orbits conjugate to each other by ∆.

10

Suppose that U SS(x) is minimal and has one orbit which is conjugate to itself by ∆. For simplicity,
we will assume that x ∈ U SS(x). We will distinguish two cases, depending on whether or not ∆
commutes with x. If ∆ ∈ Z(x) (the centralizer of x) then, as conjugation by ∆ sends normal forms
to normal forms, every factor in the left normal form of x commutes with ∆, hence every element
in the orbit of x is conjugate to itself by ∆. That is, τ (y) = y for every element y ∈ U SS(x). If
∆ 6∈ Z(x), then x is not conjugate to itself by ∆ and this implies that the length of its orbit is an
even number, as shown in the following result.
Proposition 4.5. Let x ∈ U SS(x) be a braid such that U SS(x) is minimal and has one orbit
which is conjugate to itself by ∆. Let x = X1 , X2 , . . . , Xk be the elements in this orbit, where
c(Xj ) = Xj+1 (indices are considered modulo k). If ∆ ∈
/ Z(x), then k is even and τ (Xj ) = Xj+ k
2
for j = 1, . . . , k.
Proof. Let ∆p x1 · · · xl be the left normal form of x, and suppose that p is even. Then τ (x) =
∆p τ (x1 ) · · · τ (xl ) ∈ U SS(x) and τ (x) 6= x as ∆ 6∈ Z(x). Since U SS(x) has a single orbit, one can
go from x to τ (x) by iterated cycling, and since x is rigid and p is even, each cycling corresponds to
a cyclic permutation of the factors in the left normal form of x. Hence, there is some r, 0 < r < k
such that τ (x) = cr (x). That is, τ (xj ) = xj+r for all j = 1, . . . , l, where indices are taken modulo
l. This implies that xj = τ 2 (xj ) = xj+2r , and hence c2r (x) = x. Since the orbit of x under cycling
has length k, it follows that k|2r. But since k > r, we finally obtain k = 2r.
Therefore, the length of the orbit is an even number and τ (Xj ) = Xj+ k for every Xj ∈ U SS(x).
2
Notice that x = ∆p (x1 · · · xr )(τ (x1 ) · · · τ (xr )) · · · (x1 · · · xr )(τ (x1 ) · · · τ (xr )).
Now suppose that p is odd. In this case, since x is rigid, the left normal form of x2 is
x2 = ∆2p τ (x1 ) . . . τ (xl )x1 . . . xl ,
and x2 is also rigid. Hence, cycling x2 corresponds to a cyclic permutation of the factors in its left
normal form and, for every i ≥ 0, the normal form of ci (x2 ) has 2l non-∆ factors, the last l being
the factors of ci (x) and the first l being their conjugates by ∆. Therefore, the lengths of the orbits
of x and x2 coincide, and the orbit of x2 is precisely x2 = (X1 )2 , (X2 )2 , . . . , (Xk )2 .
Since the infimum of x2 is even, we can apply the previous case to x2 and we obtain that k is even,
and that τ ((Xj )2 ) = (Xj+ k )2 , which is equivalent to τ (Xj ) = Xj+ k for j = 1, . . . , k (as the braids
2
2
involved are rigid).
Now that we know some properties of the structure of minimal ultra summit sets, we proceed to
show that this case is generic. Let us first show that the minimality of the ultra summit set is a
local property:
Theorem 4.6. Let x be a rigid braid with ℓ(x) > 1. Then U SS(x) is minimal if and only if ι(x)
and ι(x−1 ) are minimal simple elements for x.
Proof. The condition is clearly necessary. To show that it is sufficient, suppose that ι(x) and ι(x−1 )
ex be the orbit
are minimal simple elements for x. Let Ox be the orbit of x under cycling, and let O
of x under twisted decycling.
It is shown in [3] that if x is rigid and ℓ(x) > 1, then U SS(x) is the set of rigid conjugates of
x. Then U SS(x−1 ) is the set of rigid conjugates of x−1 , so U SS(x−1 ) = U SS(x)−1 . Also, as
all elements are rigid, decycling is just the inverse of cycling, hence twisted decycling sends any
ex ∪ τ (O
ex ).
element in Ox to an element in τ (Ox ), and viceversa. It follows that Ox ∪ τ (Ox ) = O
Call this set U.
By Corollary 2.27, as ι(x) is a minimal simple element for x, all elements in the normal form of x
are minimal, so ι(y) is a minimal simple element for y, for every y ∈ Ox . Conjugating the whole
picture by ∆, it follows that ι(z) is a minimal simple element for z, for every z in τ (Ox ). So we
cannot escape from U = Ox ∪ τ (Ox ) conjugating by black arrows, as all black arrows correspond
to cyclings.

11

Now notice that one can obtain Γx−1 from Γx just by replacing each vertex y with y −1 . The arrows
will have the same labels, but their colors will be exchanged. Since ι(x−1 ) is a minimal simple
element for x, it is also a minimal simple element for x−1 . Applying Corollary 2.27 to x−1 , we
have that all black arrows in Ox−1 ∪ τ (Ox−1 ) correspond to cyclings. Notice that applying twisted
decycling to a braid y is equivalent to applying cycling to its inverse (the conjugating element is
ex . Therefore, all grey arrows in O
ex ∪ τ (O
ex ) correspond
ι(y −1 ) in both cases). Hence (Ox−1 )−1 = O
e
e
to twisted decyclings. So we cannot escape from U = Ox ∪ τ (Ox ) conjugating by grey arrows.
We have then shown that for every element y ∈ U, ι(y) and ι(y −1 ) are minimal simple elements
for y. Hence y only admits these two minimal simple elements (as every minimal simple element
must be a prefix of one of these, by Corollary 2.18), and conjugating y by any of these will take
us again into U. As we can obtain the whole U SS(x) starting with any element and conjugating
by minimal simple elements, it follows that U = U SS(x). Therefore, U SS(x) is minimal.
Theorem 4.7. Let x be a σ1 -non-intrusive braid. Then, U SS(x) is minimal.
Proof. By hypothesis, x admits a non-intrusive conjugation to a rigid pseudo-Anosov braid y,
where σ1 and ∂(σ1 ) are simple factors of the normal form of y. σ1 is clearly minimal as it cannot
be decomposed, hence by Corollary 2.27 all simple factors in the normal form of y are minimal.
Therefore, ι(y) is a minimal simple element for y.
Now ∂(σ1 ) is also a simple factor of the normal form of y. This implies, using the relation between
the normal forms of y and y −1 , that some factor in the normal form of y −1 equals either σ1 or σn−1 .
Then, all simple factors in the normal form of y −1 are minimal. Therefore ι(y −1 ) is a minimal
simple element for y −1 , so it is a minimal simple element for y (recall that y is rigid).
Therefore, both ι(y) and ι(y −1 ) are minimal simple elements for y. Also, ℓ(y) > 1 as its left normal
form contains both σ1 and ∂(σ1 ). By Theorem 4.6 U SS(y), that is U SS(x), is minimal.
The next result follows immediately from Theorem 4.7 and Corollary 3.6.
Theorem 4.8. The proportion of braids in B(l) whose ultra summit set is minimal tends to 1
exponentially fast, as l tends to infinity.

5

The centralizer of generic braids

We have now all the ingredients to describe the centralizer of a generic braid. We know from Theorem 4.8
that braids with minimal ultra summit sets are generic. Hence, we will consider braids x such that
U SS(x) is minimal, and we will describe an explicit set of generators for Z(x), the centralizer of x.
According to Corollary 4.4, we can have two different situations, depending on whether U SS(x)
has one or two orbits under cycling.
Recall that one can obtain an element y ∈ U SS(x) by applying iterated cyclic slidings (or iterated
cyclings and decyclings) to x. This gives a conjugating element c such that y = c−1 xc, and
then Z(y) = c−1 Z(x)c. Therefore, in order to describe Z(x) it suffices to describe Z(y) where
y ∈ U SS(x). We will then assume, for the rest of this section, that x ∈ U SS(x) and, in particular,
that x is rigid.
Following the ideas in [17], we see that in order to compute a generating set for Z(x), we just
need to know Γx . Suppose that a ∈ Z(x). Then a = ∆−2t b for some t ≥ 0, where b is a positive
braid. Then b can be decomposed as a product of minimal simple elements, which corresponds to
an oriented path in Γx that starts and finishes at x. The positive braid ∆2 can also be decomposed
as a loop in Γx based at x. Hence, every element in Z(x) can be decomposed as a product of loops
in Γx , so a set of generators for Z(x) is obtained from a set of generators of the fundamental group
π1 (Γx , x), replacing each loop by the braid it represents.
Computing a set of generators of π1 (Γx , x) is a well-known procedure [25]: Choose a maximal tree
T in Γx . For every vertex v ∈ Γx , call γv the only simple path in T going from x to v. Let A be

12

the set of arrows in Γx \ T and, for every λ ∈ A, denote s(λ) and t(λ) the source and the target of
−1
λ, respectively. Then π1 (Γx , x) is generated by F = {γs(λ) λγt(λ)
; λ ∈ A}. If we denote by ρ the
homomorphism which maps π1 (Γx , x) onto Z(x), which sends each path to its associated element,
then ρ(F ) is a generating set for Z(x).
Let us then study the graphs Γx with detail. We shall need the following.
Definition 5.1. Given x ∈ Bn , we define the preferred cycling conjugator P C(x) of x as the
product of conjugating elements corresponding to iterated cycling until the first repetition. That
is, if t is the smallest positive integer such that ct (x) = ci (x) for some 0 ≤ i < t, then:
P C(x) = ι(x)ι(c(x)) · · · ι(ct−1 (x)).
Notice that if x ∈ SSS(x) and one conjugates x by P C(x), one obtains an element in U SS(x).
Notice also that if x ∈ U SS(x), then P C(x) is the conjugating element along the whole cycling
orbit of x. In particular, if x ∈ U SS(x) then P C(x) commutes with x. Notice also that if x
is rigid, the above expression of P C(x) is in left normal form as written. That is, the product
ι(ci−1 (x))ι(c i (x)) is left-weighted for every i ≥ 0.
Let us distinguish cases depending on the number of orbits in U SS(x).

5.1

Ultra summit set with two orbits

Let x be a rigid braid such that U SS(x) is minimal and has two orbits under cycling, conjugated
to each other by ∆ (see Corollary 4.4). Let O1 and O2 be these two orbits, and let k be the
length of each one. We can assume that x ∈ O1 and O2 = τ (O1 ). Notice that k = ℓ(P C(x)). We
denote by X1,j and X2,j the elements in orbits O1 and O2 , respectively, where τ (Xi,j ) = X3−i,j
and c(Xi,j ) = Xi,j+1 for every j = 1, . . . , k, where i = 1, 2 and the second subindex is considered
modulo k.
Notation 5.2. Let Γx be the graph associated to U SS(x). We denote aj the black arrow in O1
starting at X1,j , bj the black arrow in O2 starting at X2,j , αj the grey arrow going from O1 to O2
ending at X2,j and βj the grey arrow going from O2 to O1 ending at X1,j , for every j = 1, . . . , k.
See Figure 2, where grey arrows are represented by dashed lines.

Figure 2: U SS(x) with two orbits, for k = 4.
Theorem 5.3. Let x be a rigid braid such that U SS(x) minimal and has two orbits under cycling.
Then Z(x) = hP C(x), ∆2 i.

13

Proof. The inclusion hP C(x), ∆2 i ⊆ Z(x) is clear, as ∆2 is central and P C(x) ∈ Z(x) by construction. Let us show the converse inclusion by obtaining a set of generators for Z(x), coming from a
generating set for π1 (Γx , x).
Let T be the maximal subtree of Γx whose arrows are a1 , . . . , ak−1 , b1 , . . . , bk−1 , α1 . Every arrow
λ ∈ Γx \T will produce a generator Fλ = γs(λ) λγt(λ) (by abuse of notation, we will identify the
path in Γx with the braid it represents).
We need to show that Fλ can be written as a product of P C(x), ∆2 and their inverses, for every
λ ∈ Γx \ T = {ak , bk , α2 , . . . , αk , β1 , . . . , βk }.
First, Fak = a1 · · · ak = P C(x), so the claim holds when λ = ak .
Now Fbk = a1 α1 b1 · · · bk−1 bk (a1 α1 )−1 . By Lemma 4.3, aj αj = ∆ for every j = 1, . . . , k. Then
Fbk = ∆b1 · · · bk ∆−1 . Recall that the two orbits under cycling are conjugate by ∆ and τ (X1,j ) =
X2,j for every j = 1, . . . , k. This implies τ (aj ) = bj , hence Fbk = a1 · · · ak = P C(x).
Next, for j = 2, . . . , k − 1 one has:
−1
−1 −1
−1
= a1 · · · aj−1 ∆b−1
Fαj = a1 · · · aj αj b−1
j−1 · · · b1 (a1 α1 )
j−1 · · · b1 ∆
−1
= a1 · · · aj−1 a−1
j−1 · · · a1 = 1.

Now

−1 −1 −1
−1 −1
−1 −1 −1
Fαk = αk b−1
k−1 · · · b1 α1 a1 = αk bk bk bk−1 · · · b1 α1 a1
−1 −1
−1
−1
= ∆b−1
= a−1
.
k · · · b1 ∆
k · · · a1 = P C(x)

It remains to show that the loops determined by the βj ’s belong to hP C(x), ∆2 i.
−1
For j = k, Fβk = a1 α1 βk a−1
k−1 · · · a1 . Notice that bk βk = ∆ by Lemma 4.3. Hence
−1
−1
−1
−1
2
−1
Fβk = a1 α1 bk−1 ∆ak−1
· · · a−1
.
1 = ∆bk ∆ak−1 · · · a1 = ∆ P C(x)

Finally, for j = 1, . . . , k − 1, we have:
−1
−1
−1
2
· · · a−1
Fβj = a1 α1 b1 · · · bj βj aj−1
1 = ∆b1 · · · bj−1 ∆aj−1 · · · a1 = ∆ .

5.2

Ultra summit set with one orbit

Consider now a rigid braid x such that U SS(x) is minimal and has only one orbit O1 of length k,
conjugated to itself by ∆ (see Corollary 4.4). Recall that k = ℓ(P C(x)). We denote by X1,j the
elements in this orbit, for every j = 1, . . . , k, where x = X1,1 . We will distinguish two different
cases, depending on whether ∆ belongs to Z(x) or not. By Proposition 4.5, if ∆ does not belong
to Z(x), then k is even and τ (X1,j ) = X1,j+ k (where j + k2 is considered modulo k) for every
2
j = 1, . . . , k. Otherwise, τ (X1,j ) = X1,j , for all j = 1 . . . , k. Figure 3 illustrates the two cases.
Notation 5.4. Let Γx be the graph which represents the whole set U SS(x) in any of the above
two cases. We denote aj the black arrow starting at X1,j , and αj the grey arrow starting at X1,j+1 ,
so that aj αj = ∆, for every j = 1, . . . , k.

14

Figure 3: U SS(x) with one orbit such that ∆−1 x∆ 6= x (left) and ∆−1 x∆ = x (right), for k = 8.
Theorem 5.5. Let x be a rigid braid such that USS(x) is minimal and has only one orbit under
cycling of length k. One has:
E
D
i) If ∆−1 x∆ 6= x, then Z(x) = a1 · · · a k ∆−1 , ∆2 .
2

ii) If ∆−1 x∆ = x, then Z(x) = hP C(x), ∆i.
Proof. In both cases, the inclusions
immediate.

D

a1 . . . a k ∆−1 , ∆2
2

E

⊆ Z(x) and hP C(x), ∆i ⊆ Z(x) are

We obtain a generating set for Z(x) in a similar way as it is done in the proof of Theorem 5.3. Let
T be the maximal tree in Γx , with base vertex x = X1,1 , containing the edges a1 . . . , ak−1 .
E
D
Suppose first that ∆−1 x∆ 6= x. We need to show that Fα1 , . . . , Fαk , Fak ∈ a1 . . . a k ∆−1 , ∆2 .
2

−1

Denote g = a1 · · · a k ∆
2

. We claim that



−1
−1
−1
−1
a1 · · · aj αj a−1
a−1
a
·
·
·
a
k
k
j · · · a1 = g
j+1
j+ −1 j+ −2
2

2

for every j = 1, . . . , k, where every subindex is considered modulo k. In order to prove this claim,
applying Lemma 4.3 and Proposition 4.5, we recall that aj αj = ∆ and τ (X1,j ) = X1,j+ k . Hence
2
τ (aj ) = aj+ k and then the left hand side of the formula is equal to
2

−1
−1
−1
−1
−1
a1 · · · aj−1 ∆a−1
· · · a−1
,
1 = ∆a1+ k · · · aj−1+ k aj+ k −1 · · · a1 = ∆a k · · · a1 = g
j+ k −1
2

2

2

2

2

proving the claim.
It follows immediately that Fαj = g −1 , for j = 1, . . . , k2 .
For j =

k
2

+ 1, . . . , k − 1, one has:
−1
−1
· · · a−1
Fαj = a1 · · · aj αj a−1
1 = a1 · · · aj−1 ∆aj− k −1 · · · a1
j− k −1
2

2

−1
2
= a1 · · · aj−1 a−1
j−1 · · · a k +1 ∆ = a1 · · · a k ∆ = g∆ .
2

2

For j = k:
−1
−1
−1
−1
−1
−1
Fαk = αk a−1
· · · a−1
.
k
1 = ak (ak αk )a k −1 · · · a1 = ∆a k · · · a1 = g
−1
2

2

15

2

Finally:
Fak = a1 · · · ak = a1 · · · a k a k +1 · · · ak = a1 · · · a k (∆−1 a1 · · · a k −1 ∆) = g 2 ∆2 .
2

2

2

2

This shows the result when ∆−1 x∆ 6= x.
Suppose now that ∆−1 x∆ = x. We have to show that Fα1 , . . . , Fαk , Fak ∈ hP C(x), ∆i.
−1
For j = 1, . . . , k − 1 we have Fαj = a1 · · · aj−1 (aj αj )a−1
j−1 · · · a1 . Recall that aj αj = ∆ and that
τ (X1,j ) = X1,j , so τ (ai ) = ai for every i. Hence Fαj = ∆ for j = 1, . . . , k − 1.
−1
−1
−1
−1
Now Fαk = αk a−1
.
k−1 · · · a1 = (αk ak )ak · · · a1 = ∆(P C(x))

Finally, Fak = a1 · · · ak = P C(x).

6

An algorithm to compute the centralizer of a braid

Our goal in this section is to present an algorithm to compute a generating set for the centralizer
of a braid, based in the results from previous sections, which generically terminates in polynomial
time and yields a minimal set of generators consisting of two elements.
Given y ∈ Bn , the first step will be to find x ∈ U SS(y) and a conjugating element c such that
c−1 yc = x. This is achieved by iterated applications of cyclic sliding to y [20]. Next we check
whether x is rigid. If x is rigid, the algorithm continues by computing the minimal simple elements
for x [16]. If ι(x) and ι(x−1 ) are equal to the minimal simple elements for x, then U SS(y) = U SS(x)
is minimal by Theorem 4.6. At this point, one needs to determine whether U SS(y) has one or
two orbits, and in the latter case whether x commutes with ∆, in order to apply Theorem 5.3
or Theorem 5.5. For that, we will check whether or not τ (x) belongs to the orbit of x, and in
particular whether τ (x) is equal to x. This yields a generating set for Z(x) given by Theorem 5.3
or Theorem 5.5 and one obtains a generating set for Z(y) from the equality Z(y) = cZ(x)c−1 .
We remark that if x is not rigid or if U SS(y) is not minimal (a case which is not generic, as shown
in Theorem 4.8), the centralizer of y can be determined by the algorithm given by Franco and
González-Meneses [17]. The algorithm in [17] refers to SSS(x) instead of U SS(x), but it can be
equally applied to U SS(x), or even to SC(x), considerably improving its efficiency.
The pseudocode of the algorithm described in the previous paragraphs is shown in Algorithm 1.
In order to study the complexity of this algorithm, we naturally measure the input braids by their
canonical length. But we will also see how the number n of strands affects the computation, as
this is important in practice, and because the algorithms in braid groups are usually programmed
allowing inputs with an arbitrary number of strands.
We saw in Theorem 4.8 that σ1 -non-intrusive braids are generic in Bn , so we will study the complexity of computing the centralizer of such a braid.
Proposition 6.1. Let y ∈ Bn be a σ1 -non-intrusive braid such that U SS(y) is minimal. If
l = ℓ(y), the complexity of computing a generating set for Z(y) using Algorithm 1 is O(l2 n4 log n).
Proof. The first step of Algorithm 1 consists of applying iterated cyclic sliding until the first
repeated element x is obtained, computing at the same time the conjugating element c, which is
the product of the conjugating elements for each cyclic sliding. By [21, Algorithm 1], the cost of
computing x and c is O (T ln log n), where T is the number of cyclic slidings applied.
Recall from Lemma 4.2 that, as U SS(y) is minimal, x is rigid. In [20] it is shown that, if a braid
y is conjugate to a rigid braid x, then the product of all conjugating elements corresponding to
iterated cyclic sliding is the shortest positive element conjugating y to a rigid braid. On the other
hand, as y = ∆p y1 · · · yl is σ1 -non-intrusive, there is a positive prefix of τ −p (y1 · · · yl ) conjugating y
to a rigid element. This implies that the number of cyclic slidings needed to conjugate y to a rigid
braid is smaller than the letter length of τ −p (y1 · · · yl ), that is, smaller than lk∆k = ln(n − 1)/2.
Since the obtained element x is rigid, the next cyclic sliding yields s(x) = x and the repeated
16

Algorithm 1 Compute a generating set for the centralizer of a braid.
Input: A braid y ∈ Bn given in left normal form.
Output: A generating set for Z(y)
1: Compute x ∈ U SS(y) and c ∈ Bn such that c−1 yc = x by iterated cyclic sliding [20, 21].
2: if x is rigid then
3:
Applying iterated cycling to x, compute k = length of the orbit of x under cycling.
4:
Compute the minimal simple elements for x [19].
5:
if ι(x) and ι(x−1 ) are the minimal simple elements for x then
6:
Compute τ (x).
7:
if τ (x) = x then
8:
A = P C(x), B = ∆. [Theorem 5.5]
k
9:
else if k is even and τ (x) = c 2 (x) then
10:
A = a1 · · · a k ∆−1 , B = ∆2 . [Theorem 5.5]
2
11:
else
12:
A = P C(x), B = ∆2 . [Theorem 5.3]
13:
end if
14:
return {cAc−1 , cBc−1 }.
15:
else
16:
Compute Z(x) applying the algorithm in [17] (using SC(x)).
17:
end if
18: else
19:
Compute Z(x) applying the algorithm in [17] (using SC(x)).
20: end if
element is immediately obtained. Hence T = O(ln2 ), and the first step of the algorithm takes time
O(l2 n3 log n).
The following step is to check whether x is rigid, which means to determine whether p(x) = 1.
This was already made in the previous step, when s(x) was computed. So this step has no cost.
Let x = ∆q x1 · · · xr in left normal form. Since x ∈ U SS(y) ⊂ SSS(y), we have q ≥ p and r ≤ l.
Since x is rigid, the next step in Algorithm 1 is to apply iterated cycling to x in order to compute
k, the length of its orbit under cycling. As x is rigid, the left normal form of c(x) is precisely
∆p x2 · · · xr τ −p (x1 ). In order to compute this normal form, one just needs to apply τ −p to x1 . If p
is even then τ −p is trivial, and if p is odd τ −p is equal to τ . If the simple factors are stored, as usual,
as a list of n numbers (from 1 to n) representing the permutation they induce, applying τ to x1 is
O(n). Hence, each cycling takes O(n). After each cycling, one need to check whether the obtained
element equals x. Comparing two normal forms is O(ln log n) (we compare two lists of rn ≤ ln
numbers between 1 and n, and each number has length at most log n). We know that c2r (x) = x,
hence k ≤ 2r ≤ 2l, so the number of total comparisons we will perform is O(l). Therefore, in order
to compute k one performs k ≤ 2l cyclings (total cost O(ln)) and O(l) comparisons (total cost
O(l2 n log n)). Hence, the cost of computing k is O(l2 n log n).
The next step consists of computing the minimal simple elements for x. The complexity of this
computation is described in [4, Proposition 4.10] for general elements in a Garside group, but in
our case we are in a simpler situation: We are computing the minimal simple elements for a braid
x ∈ Bn which is rigid. We can proceed as follows: For every generator σi (i = 1, . . . , n − 1),
compute the minimal positive element ρi such that σi 4 ρi and xρi ∈ SSS(x). By [21, Proposition
ρ
3.4], in order to compute this
ρ with
 element we start with ρ = σi , and while ℓ(x ) > r we replace
ρ −1 p
ρ −p−r
ρ 1 ∨ (x ) ∆ ∨ x ∆
. The final value of ρ is precisely ρi . The element 1 ∨ (xρ )−1 ∆p is the
leftmost factor in the right normal form of (xρ )−1 ∆p , and 1 ∨ xρ ∆−p−r is the leftmost factor in
the right normal form of xρ ∆−p−r . Hence, the element 1 ∨ (xρ )−1 ∆p ∨ xρ ∆−p−r can be obtained
at the cost of computing two right normal forms and the least common multiple of two simple
elements. The total cost of one iteration is O(l2 n log n).
Once ρi is computed, we can use [20, Theorem 2]: Since xρi ∈ SSS(y) and it is conjugate to a
rigid element, the shortest positive element αi conjugating xρi to a rigid element is precisely the
17

product of all conjugating elements for iterated cyclic sliding of xρi . By construction ρi αi will
be the minimal element which admits σi as a prefix and conjugates x to a rigid element. Since
∆ admits σi as a prefix and conjugates x to a rigid element, it follows that ρi is a prefix of ∆,
so it is simple. Hence, the total number of iterations of the procedure in this paragraph and the
procedure in the previous paragraph is bounded by n(n − 1)/2. Since the cost of a single cyclic
sliding is O(ln log n), it follows that the complexity of computing ρi αi is O(l2 n3 log n). This is
done for i = 1, . . . , n − 1, and the set of minimal simple elements for x is just the set of minimal
elements in {ρ1 α1 , · · · , ρn−1 αn−1 }, hence we can compute this set in O(l2 n4 log n).
k

The next steps, computing τ (x) and comparing it with x or c 2 (x) (which has been computed in
a previous step, when k was obtained), are negligible compared with the previous ones.
Finally, it remains to conjugate the generators A and B by c−1 to obtain Z(y). Since y is σ1 -nonintrusive, ℓ(c) ≤ 52 ℓ(x) = O(l), and on the other hand ℓ(A) is at most k in all possible cases, where
k ≤ 2l. Then, the cost of conjugating A and B by c−1 , is O (l2 n log n) [21].
Therefore, the total time complexity of the whole algorithm, when applied to the σ1 -non-intrusive
braid y, is O(l2 n4 log n).
Corollary 6.2. There exists an algorithm to compute a generating set for the centralizer of a braid
y ∈ Bn , whose generic-case complexity is O(l2 n4 log n), where l = ℓ(y).
Notice that, when Bn is fixed, the generic-case complexity of Algorithm 1 is quadratic on the
canonical length of the input braid. But one can implement the algorithm letting n vary, and the
generic-case complexity still remains polynomial.

References
[1] E. Artin. Theorie der Zöpfe. Abh. Math. Sem. Univ. Hamburg 4 (1925), no. 1, 47-72.
[2] E. Artin. The theory of braids. Annals of Math., 48 (1947),101-126.
[3] J. Birman, V. Gebhardt and J. González-Meneses, Conjugacy in Garside groups I: cycling,
powers and rigidity, Groups Geom. Dyn. 1 (2007), 221-279.
[4] J. Birman, V. Gebhardt and J. González-Meneses, Conjugacy in Garside groups II: structure
of the ultra summit set, Groups Geom. Dyn. 1 (2008), 13-61.
[5] J. S. Birman, K. H. Ko. and S. J. Lee. A new approach to the word and conjugacy problems
in the braid groups, Adv. Math., 139 (2) (1998), 322-353.
[6] J. S. Birman, K. H. Ko. and S. J. Lee. The infimum, supremum and geodesic length of a
braid conjugacy class, Adv. Math., 164 (1) (2001), 41-46.
[7] N. Bourbaki, Groupes et algèbres de Lie, Chapitres IV-VI, Hermann, Paris, 1968.
[8] E. Brieskorn and K. Saito, Artin-Gruppen und Coxeter-Gruppen, Invent. Math. 17 (1972),
245-271.
[9] S. Caruso, On the genericity of pseudo-Anosov braids I: rigid braids, (2013) arXiv:1306.3757.
[10] S. Caruso and B. Wiest, On the genericity of pseudo-Anosov braids II: conjugations to rigid
braids, Groups Geom. Dyn. 11, 2 (2017), 549565.
[11] R. Charney and J. Meier, The language of geodesics for Garside groups, Math. Z. 248 (2004),
no. 3, 495-509.
[12] P. Dehornoy, Groupes de Garside, Ann. Sci. Ec. Norm. Sup. 35, (2002), 267-306.
[13] P. Dehornoy and L. Paris, Gaussian groups and Garside groups, two generalisations of Artin
groups, Proc. London Math. Soc. 79, 3 (1999), 569-604.
18

[14] E. ElRifai and H. Morton, Algorithms for positive braids, Q. J. Math. Oxf. Ser. II 45 (1994),
479-497.
[15] D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Patterson and W. P.
Thurston, Word Processing in Groups, Jones and Bartlett, Boston (1992).
[16] N. Franco and J. González-Meneses, Conjugacy problem for braid groups and Garside groups,
J. Algebra. 266 (1), (2003), 112-132.
[17] N. Franco and J. González-Meneses, Computation of Centralizers in Braid Groups and Garside Groups, Rev. Mat. Iberoamericana. 19 (2003), 367-384.
[18] F. A. Garside, The braid group and other groups, Quart. J. Math. Oxford Ser. 20 (1969)
235-254.
[19] V. Gebhardt, A new approach to the conjugacy problem in Garside groups, J. Algebra. 292
(2005), 282-302.
[20] V. Gebhardt and J. González-Meneses, The cyclic sliding operation in Garside groups, Math.
Z. 265 (1), 2010, 85-114.
[21] V. Gebhardt and J. González-Meneses, Solving the conjugacy problem in Garside groups by
cyclic sliding, J. Symb. Comp. 45 (6), 2010, 629-656.
[22] N. V. Ivanov. Subgroups of Teichmüller modular groups. Translations of Mathematical Monographs, 115. American Mathematical Society, Providence, RI, 1992.
[23] J. González-Meneses and B. Wiest, On the structure of the centralizer of a braid, Ann. Sci.
École Norm. Sup. 37 (4), 2004, no. 5, 729-757.
[24] E-K. Lee and S-J. Lee, Periodic elements in Garside groups, J. Pure Appl. Algebra. 215
(2011), no. 10, 2295-2314.
[25] R. C. Lyndon and P. E. Schupp, Combinatorial group theory, Reprint of the 1977 edition.
Classics in Mathematics, Springer-Verlag, Berlin, 2001.
[26] G. S. Makanin, On normalizers in the braid group, Mat. Sb. 86 (128), 1971, 171-179.
[27] J. D. McCarthy. Normalizers and cetralizers of pseudo-Anosov mapping classes. Unpublished.
1992. http://users.math.msu.edu/users/mccarthy/publications/normcent.pdf
Juan González-Meneses (meneses@us.es), Dolores Valladares (valladaresg@us.es).
Depto. de Álgebra. Instituto de Matemáticas (IMUS).
Universidad de Sevilla. Av. Reina Mercedes s/n, 41012 Sevilla (Spain).

19

