arXiv:1403.4622v5 [] 15 Feb 2018

COMPLETE SIMULTANEOUS CONJUGACY INVARIANTS IN ARTIN’S
BRAID GROUPS
ARKADIUS KALKA, BOAZ TSABAN, AND GARY VINOKUR
Abstract. We solve the simultaneous conjugacy problem in Artin’s braid groups and,
more generally, in Garside groups, by means of a complete, effectively computable, finite
invariant. This invariant generalizes the one-dimensional notion of super summit set to
arbitrary dimensions. One key ingredient in our solution is the introduction of a provable
high-dimensional version of the Birman–Ko–Lee cycling theorem. The complexity of this
solution is a small degree polynomial in the cardinalities of our generalized super summit
sets and the input parameters. Computer experiments suggest that the cardinality of this
invariant, for a list of order N independent elements of Artin’s braid group BN , is generically
close to 1.

1. Introduction
In 1911, Dehn formulated three fundamental algorithmic problems concerning groups: the
Word Problem, the Conjugacy Problem, and the Group Isomorphism Problem. The Word
Problem is that of deciding whether two words in given symmetric generators of a group
represent the same element or, equivalently, whether a word in these generators represents
the identity element. The Conjugacy Problem is that of deciding whether two group elements
are conjugate. The Conjugacy Search Problem version of this problem is to find, given two
conjugate group elements, a witness conjugator.
Throughout, for group elements g and x in G, we use the notation g x := x−1 gx. The Simultaneous Conjugacy Problem (SCP) generalizes the Conjugacy Problem: r-tuples (g1 , . . . , gr )
and (h1 , . . . , hr ) of elements of a group G are conjugate if there is an element x ∈ G such
that
(g1 , . . . , gr )x := (g1x , . . . , grx ) = (h1 , . . . , hr ).
The (r-dimensional) SCP is that of deciding whether two r-tuples of group elements are
conjugate. The definition of the Search SCP is analogous.
An external motivation for studying the SCP comes from cryptography. The security of
a number of cryptographic protocols reduces to the Search SCP in Artin’s braid groups. In
Section 2, we provide such reductions for prominent examples. In the case where G is a braid
group, there are by now polynomial-time, ad-hoc solutions of the problems that characterize
the security of these protocols [5, 33, 2]. These solutions do not address the (formally harder)
2010 Mathematics Subject Classification. 20F36, 20F65, 20C40.
Key words and phrases. Conjugacy problem, simultaneous conjugacy, Braid group, Gaside group, minimal
simple element, Birman-Ko-Lee presentation, summit set, super summit set.
1

2

KALKA, TSABAN, AND VINOKUR

SCP. Moreover, for the lack of a general, polynomial-dimension representation theory for
Garside groups, the known solutions do not generalize to arbitrary Garside groups. From
a heuristic point of view, practically all braid-based cryptographic protocols proposed thus
far, including ones hitherto not cryptoanalyzed, are based on the difficulty of the SCP. In
order to understand the potential of braid groups in cryptography, we must address the
full-fledged SCP.
A number of computational problems in braid groups reduce to the SCP. For example, Dehornoy’s Shifted Conjugacy Problem [8] reduces to the SCP via a reduction to the Subgroup
Conjugacy Problem for the braid group BN −1 in BN [22]. More generally, the Subgroup Conjugacy Problem for BM in BN (M < N) is reducible to the SCP [17]. In a sequel paper [24],
we show that the Double Coset Problem for parabolic subgroups of braid groups reduces to
the SCP. In particular, the present paper leads to the first solution of the Double Coset
Problem.
Our main result is a deterministic, effective solution to the decision and search version of
the SCP, in arbitrary Garside groups. Earlier, Lee and Lee provided a solution in Artin’s
braid groups [27], that extends to Garside groups with weighted presentations. In contrast
to the Lee–Lee solution, our solution provides a finite invariant of the conjugacy class of an
r-tuple. Experimental results, in braid groups, show a considerable improvement over the
earlier solution. We conclude this paper with open problems and indications for additional
applications.
2. Reductions of some computational problems to the SCP
In the original instantiations of the problems below, the group G was Artin’s braid group.
The protocols, problems and reductions in this section apply in arbitrary finitely generated
groups. We assume, for simplicity, that each mentioned group is provided in terms of a
generating set of cardinality r.
The security of the Braid Diffie–Hellman protocol [26], is based on the difficulty of the
following problem.
Problem 2.1. Let A and B be subgroups of a group G with [A, B] = 1, and let g ∈ G be
given. Given a pair (g a , g b), for a ∈ A and b ∈ B, find g ab .
Problem 2.1 reduces to the Search SCP. Indeed, let b1 , . . . , br be generators of the subgroup
B. Find an element ã ∈ G such that
(g, b1 , . . . , br )ã = (g a , b1 , . . . , br ).

Then [ã, B] = 1, and
g ab = (g a )b = (g ã )b = g ãb = g bã = (g b)ã ,
which we can compute, having g b and ã.
The Double Coset protocol [6] is a generalization of the Braid Diffie–Hellman protocol.
Its security is based on the difficulty of the following problem.

SIMULTANEOUS CONJUGACY IN BRAID GROUPS

3

Problem 2.2. Let A1 , A2 , B1 and B2 be subgroups of a group G with [A1 , B1 ] = [A2 , B2 ] = 1,
and let g ∈ G be given. Given a pair (a1 ga2 , b1 gb2 ), for ai ∈ Ai and bi ∈ Bi for i = 1, 2, find
a1 b1 ga2b2 .
To see that Problem 2.2 reduces to the Search SCP, let bi1 , . . . , bir be generators of the
subgroup Bi for i = 1, 2. For elements b ∈ B1 of our choice, since [a1 , B1 ] = 1, we know the
element bga2 = ba1 ga2 . Find an element ã2 ∈ G such that
ga2
2
(bg11 , . . . , bg1r , b21 , . . . , b2r )ã2 = (bga
11 , . . . , b1r , b21 , . . . , b2r ).

Then [ã2 , B2 ] = 1, and [(ga2 )(gã2 )−1 , B1 ] = 1. Compute ã1 = (a1 ga2 )(gã2 )−1 = a1 (ga2 )(gã2 )−1 .
Then [ã1 , b1 ] = 1, and thus
ã1 (b1 gb2 )ã2 = b1 ã1 gã2 b2 = b1 a1 ga2b2 = a1 b1 ga2 b2 ,
which we can compute from b1 gb2 , ã1 and ã2 .
The security of the Commutator protocol [1] is based on the difficulty of the following
problem.
Problem 2.3. Let A and B be subgroups of a group G. Given Ab and B a , for a ∈ A and
b ∈ B, find the commutator [a, b].
The reducibility of Problem 2.3 to the SCP remains open. Generically, the centralizer
of subgroups of the braid group is equal to the center of the entire group, which is known.
Problem 2.3 reduces to the conjunction of the Search SCP and computing the centralizer
of a finite set of elements: Let a1 , . . . , ar , b1 , . . . , br , c1 , . . . , cr and d1 , . . . , dr be generators
of the subgroup A, B and their centralizers C(A) and C(B), respectively. Find elements
ã, b̃ ∈ G such that
(a1 , . . . , ar , d1 , . . . , dr )b̃ = (ab1 , . . . , abr , d1 , . . . , dr ).
and
(b1 , . . . , br , c1 , . . . , cr )ã = (ba1 , . . . , bar , c1 , . . . , cr ).
Then ab̃ = ab . Also, ãa−1 ∈ C(B) and [b̃, C(B)] = 1. In particular, [b̃, ãa−1 ] = 1. Compute
ã−1 b̃−1 ãb̃ = ã−1 b̃−1 (ãa−1 )ab̃ = ã−1 (ãa−1 )b̃−1 ab̃ = a−1 ab̃ = a−1 ab = [a, b].
Finally, the security of the Centralizer protocol [31] is based on the following problem.
Problem 2.4. Let g, a1 , b2 ∈ G, C ≤ C(a1 ), D ≤ C(b2 ), a2 ∈ D and b1 ∈ C. Given g, C,
D, a1 ga2 and b1 gb2 , compute a1 b1 ga2 b2 .
Problem 2.4 reduces to the conjunction of the Search SCP and computing the centralizer
of a finite set of elements: Let c1 , . . . , cr and e1 , . . . , er be generators of the subgroup C and
C(D), respectively. For each c ∈ C, we can compute ca1 ga2 = cga2 . Find ã2 ∈ G such that
ga2
2
(cg1 , . . . , cgr , e1 , . . . , er )ã2 = (cga
1 , . . . , cr , e1 , . . . , er ).

4

KALKA, TSABAN, AND VINOKUR

Let ã1 = (a1 ga2 )(gã2 )−1 . Then ã1 = a1 ((ga2 )(gã2 )−1 ) ∈ C(C), and thus [ã1 , b1 ] = 1. Also,
[ã2 , C(D)] = 1 and b2 ∈ C(D). Thus, [ã2 , b2 ] = 1. It follows that
ã1 (b1 gb2 )ã2 = b1 ã1 gã2 b2 = b1 a1 ga2b2 = a1 b1 ga2 b2 .
3. Background on Garside groups
Garside groups [11, 29] form a generalization of braid groups where Garside’s solution
to the conjugacy problem in braid groups applies. Many examples of Garside groups are
known [10]. These include, in addition to Artin’s braid groups, all Artin groups of finite
type and torus link groups [30].
Let M be a monoid. An element a ∈ M is a left divisor of an element b ∈ M (a  b) if
b ∈ aM. An element a is right divisor of an element b (b  a) if b ∈ Ma. It is a divisor of
b if it is a left or a right divisor of b. Div(b) is the set of divisors of b. An element b ∈ M is
balanced if the left and right divisors of b coincide.
A monoid M is Noetherian if for each element a ∈ M there is a natural number n such
that a cannot be expressed as the product of more than n nonidentity elements. An element
a 6= 1 in M is an atom if a = bc implies b = 1 or c = 1. A set generates a Noetherian monoid
M if and only if it includes all atoms of M.
Let M be a finitely generated, cancellative Noetherian monoid. The relations  and  are
partial orders, and every element of M admits only finitely many left and right divisors [11].
An element m ∈ M is a right lcm of a and b if a, b  m, and whenever a  c and b  c, we
have m  c. The definition of left lcm is symmetric, using the relation . Right and left
˜ b, respectively. If a ∨ b exists,
lcms of pairs a and b are unique, and are denoted a ∨ b and a ∨
then there is a unique element c such that a ∨ b = ac. This element c is the right complement
(or residue) of a in b, denoted by a\b. We define the left complement symmetrically. In
˜ b = (b/a)a = (a/b)b.
particular, we have a ∨ b = a(a\b) = b(b\a), and a ∨
A monoid M is Gaussian if it is Noetherian, cancellative, and every pair of elements
a, b ∈ M admits a right and a left lcm. Let M be a Gaussian monoid. For every pair of
elements a and b, the set of common left divisors of a and b is finite and admits a right
lcm, which is therefore the greatest common left divisor of a and b, denoted by a ∧ b. The
˜ b is symmetric. A Gaussian monoid M is a lattice with respect
definition of right gcd a ∧
to the relations  and . The groups of right fractions and left fractions of the monoid M
coincide, and form the group of fractions of M. The monoid M embeds in this group.
Definition 3.1. A Garside group is a group G equipped with a finite subset S and an
element ∆ such that the monoid G+ generated by S is Gaussian with G is its group of
fractions, ∆ ∈ G+ is a balanced element, and S = Div(∆).
In this case, we say that G+ is a Garside monoid, ∆ the Garside element, and the elements
of S are the simple elements of G.
Let G be a Garside group. There may be several choices of S and ∆ witnessing that, and
we always assume, tacitly, that S and ∆ are fixed in the background. The set S is closed
˜ , ∧ and ∧
˜ . Indeed, S is the closure of the atoms of G+ under
under the operators \, /, ∨, ∨

SIMULTANEOUS CONJUGACY IN BRAID GROUPS

5

the operators \ and ∨. The functions ∂ : a 7→ a\∆ and ∂˜ : a 7→ ∆/a map G+ onto S, and
˜ S are bijections of S satisfying ∂|
˜ S = (∂|S )−1 . In particular, we have
the restrictions ∂|S , ∂|
∂ 2 (a) = τ (a) and ∂˜2 = τ −1 (a) for all a ∈ S, where τ denotes the inner automorphism of G
defined by a 7→ ∆−1 a∆.
The partial orders  and  on G+ extend naturally to partial orders on the whole Garside
group G. Define a partial order on G by a ≤ b if there are c, c′ ∈ G+ such that b = cac′ . For
elements a, b ∈ G and k ∈ Z, we have a  ∆k  b if and only if b  ∆k  a if and only if
a ≤ ∆k ≤ b. For m, n ∈ Z, define the interval
[m, n] := { a ∈ G : ∆m ≤ a ≤ ∆n }.

The infimum and the supremum of an element a ∈ G, denoted inf a and sup a, respectively,
are the maximal m ∈ Z and the minimal n ∈ Z such that a ∈ [m, n]. The canonical length
of a, denoted cl(a), is the difference sup a − inf a.
Let G be a Garside group. The (left) normal form of an element a ∈ G+ is a unique
decomposition a = s1 · · · sl such that si = ∆ ∧ (si · · · sl ) ∈ S for all i, and sl 6= 1. The
length l of this decomposition equals sup a. The (left) normal form of a general element a is
obtained by expressing a = ∆inf a a+ for the unique element a+ ∈ G+ , and decomposing a+
to its (left) normal form.
4. The basic solution
Picantin’s solution for the Conjugacy Problem in Garside groups [29] extends to the SCP
by choosing the appropriate coordinate-wise generalization of the involved notions. For
a natural number r, the standard partial order ≤ of Z extends to a partial order of Zr
coordinate-wise: for elements p = (p1 , . . . , pr ) and q = (q1 , . . . , qr ) in Zr , we define p ≤ q if
pi ≤ qi for all i = 1, . . . , r. For an r-tuple a = (a1 , . . . , ar ) of elements of a Garside group G,
let
aG := { ag : g ∈ G } = { (ag1 , . . . , agr ) : g ∈ G },
the (simultaneous) conjugacy class of a. Define
inf a := (inf a1 , . . . , inf ar );
sup a := (sup a1 , . . . , sup ar ).
For p, q ∈ Zr with p ≤ q, define the following interval :
[p, q] = { a ∈ Gr : p ≤ inf a and sup a ≤ q }

= { (a1 , . . . , ar ) ∈ Gr : pi ≤ inf ai and sup ai ≤ qi for all i = 1, . . . , r }.

Lemma 4.1. Let G be a Garside group, and r be a natural number. For all tuples p, q ∈ Zr ,
the interval [p, q] is finite.
Proof. The one-dimensional case (r = 1) is due to Picantin [29]. In the case r > 1, the
interval
[p, q] = [p1 , q1 ] × · · · × [pr , qr ]

6

KALKA, TSABAN, AND VINOKUR

is finite, as a product of finitely many one-dimensional intervals.



Lemma 4.2 ([29, Lemma 2.3]). Let G be a Garside group. Then ∆ ≤ αβ implies ∆ ≤
α(β ∧ ∆), for all α, β ∈ G+ .
Since the set of simple elements S in a Garside group is finite and the automorphism
τ : S → S a bijection, there is a natural number k such that τ k is the identity map. Then
the element ∆k is in the center of G. Assume that elements a, c ∈ G are conjugate by an
element x ∈ G. Then, for a large enough natural number m, the elements a and c are
also conjugate by the element x+ := ∆mk x ∈ G+ . It follows that the same holds for tuples
a, c ∈ Gr , for an arbitrary dimension r.
Theorem 4.3 (Simultaneous Convexity). Let G be a Garside group, p, q ∈ Zr , and a, c ∈
−1
˜ ∆,
[p, q]. Assume that c = ax = ax̃ for elements x, x̃ ∈ G+ . Let x1 := ∆ ∧ x and x̃1 := x ∧
−1
the leftmost and rightmost simple factors of x, respectively. Then ax1 , ax̃1 ∈ [p, q].
Proof. The case r = 1 is due to Picantin [29, Propositions 3.2]. It follows that, for each
x̃−1

i = 1, . . . , r, we have axi 1 , ai 1 ∈ [pi , qi ], and thus ax1 , ax̃1 ∈ [p, q].
−1



The one-dimensional version of the following corollary is due to Picantin [29, Propositions 3.3].
Corollary 4.4. Let G be a Garside group, and p, q ∈ Zr . For all conjugate tuples a, c ∈ [p, q],
there are a natural number l, tuples v0 , v1 , . . . , vl ∈ [p, q], and simple elements s1 , . . . , sl ∈ G
si
such that v0 = a, vl = c, and vi−1
= vi for i = 1, . . . , l; schematically:
s

s

s

sl−1

s

1
2
3
l
a −→
v1 −→
v2 −→
· · · −→ vl−1 −→
c.

Proof. There is an element x ∈ G+ such that ax = c. The assertion follows by applying the
Simultaneous Convexity Theorem 4.3 sup x times.

We obtain an extension of Picantin’s result [29, Corollary 3.4] to the simultaneous setting.
Theorem 4.5. The SCP in Garside groups is solvable.
Proof. Given tuples a, c ∈ Gr , fix tuples p, q ∈ Zr with p ≤ inf a, inf c and sup a, sup c ≤ q.
Then a, c ∈ [p, q], and the elements a and c are conjugate if and only if c ∈ aG ∩ [p, q].
By Lemma 4.1, the set aG ∩ [p, q] is finite. By Corollary 4.4, this set can be generated by
starting with a and iteratively conjugating with simple elements, keeping only the conjugates
that remain in [p, q], until we obtain no new elements of [p, q] (Algorithm 1).
We solve the Search SCP by keeping track of the conjugating elements during the computation of the set aG ∩ [p, q].

For braid groups, a variation of the solution presented here was provided by Lee and
Lee [27]. Their solution uses, instead of intervals [p, q], intervals of the form
[p, ∞] = { a ∈ Gr : p ≤ inf a }.

SIMULTANEOUS CONJUGACY IN BRAID GROUPS

7

Algorithm 1 Compute the set aG ∩ [p, q], for p, q ∈ Zr and a ∈ [p, q].
W := ∅; V := {a}
repeat
Take v ∈ V
for all s ∈ S do
u := (v1s , . . . , vrs )
if u ∈ [p, q] and u ∈
/ V then
V := V ∪ {u}
end if
end for
W := W ∪ {v}; V := V \ {v}
until V = ∅
return W

While these intervals are finite for braid groups, and more generally for so-called Garside
groups with weighted presentation, they may potentially be infinite in some Garside groups,
in which case the Lee–Lee solution to the SCP may not terminate in finite time.
The solution presented in this section is infeasible in practice, for two reasons: The intervals used are typically too large, and each step in the algorithm consists of conjugating
by all simple elements. In the braid group BN , there are exponentially (in N) many simple
elements. We address these issues in the coming sections.

5. Simultaneous Cyclic Sliding
While cycling only affects the infimum of a braid, cyclic sliding [18] affects infimum and
supremum. We identify and establish a high-dimensional generalization of the latter. This
plays a crucial role in our moving to minimal intervals in the next section.
Let a ∈ Gr . For each index i = 1, . . . , r, represent the group element ai in normal form:
(i)

(i)

ai = ∆pi Pi = ∆pi s1 · · · sli .
Assume that the interval [p, q] is not minimal with respect to aG , that is, there exists an
element b ∈ aG such that [p, q] % [inf b, sup b]. Consider target intervals [p̃, q̃] which are
proper subintervals of [p, q] such that qi − q̃i ≤ 1 and p̃i − pi ≤ 1 for all i = 1, . . . , r. By
definition, there are exactly 2r target intervals that are maximal with respect to ≤, namely
those where the tuples p and p̃—(exclusive) or q and q̃—differ in exactly one coordinate.
According to our assumption, there exists (among these 2r maximal target intervals) at
least one such that [p̃, q̃] ∩ aG 6= ∅. We define simultaneous cyclic sliding with respect to a
target interval [p̃, q̃].

8

KALKA, TSABAN, AND VINOKUR

5.1. Simultaneous cycling and decycling. Let b ∈ [p̃, q̃] ∩ aG . Fix an element X ∈ G+
such that XaX −1 = b. For i = 1, . . . , r, write
(1)

bi = ∆p̃i b̄i = X∆pi Pi X −1 ,

with b̄i  1. The normal form of bi need not be ∆p̃i b̄i ; in general, we have inf(bi ) ≥ p̃i .
Multiplying Equation (1) on the left by ∆−(p̃i −1) , we have
∆b̄i = ∆−(p̃i −1) X∆pi Pi X −1 = τ p̃i −1 (X)∆pi −p̃i +1 Pi X −1  ∆.

Since X  1, we have τ p̃i −1 (X)∆pi −p̃i +1 Pi  ∆. For the index i with p̃i = pi + 1, we have
τ p̃i −1 (X)Pi  ∆ which by Lemma 4.2 implies that
(i)

τ p̃i −1 (X)(Pi ∧ ∆) = τ p̃i −1 (X)s1  ∆.

(i)

By the invariance of the relation  under right multiplication, we have τ p̃i −1 (X)  ∆(s1 )−1 =
(i)
(i)
∂ −1 (s1 ). By invariance of  under τ -automorphism, we have X  τ −p̃i +1 (∂ −1 (s1 )). Taking
the left lcm for all i with p̃i = pi + 1, we obtain
(2)

X

∼
_

(i)

τ −p̃i +1 (∂ −1 (s1 )).

i: p̃i =pi +1

Definition 5.1. In the above notation, the simultaneous cycling operation is the left conjugation of the tuple a ∈ Gr by the element in the right hand side of Equation (2).
We define simultaneous decycling analogously: Recall that qi = sup ai = − inf a−1
i . Let
−1
−qi ′
the normal form of the element ai be ∆ Pi . Since sup bi ≤ q̃i ≤ qi and inf bi = − sup bi ,
we have inf b−1
i ≥ −q̃i . Thus, for each index i = 1, . . . , r, we can write
(3)

−1
−q̃i ′
b̄i = Xa−1
= X∆−qi Pi′ X −1
b−1
i X
i = ∆

−q̃i ′
b̄i need not be the
for some element b̄′i  1. In general, we have inf(b−1
i ) ≥ −q̃i and ∆
−1
q̃i +1
normal form of bi . Multiplying Equation (3) on the left by ∆
, we have

∆b̄′i = ∆q̃i +1 X∆−qi Pi′ X −1 = τ −q̃i −1 (X)∆−qi+q̃i +1 Pi′ X −1  ∆.

Since X  1, we have τ −q̃i −1 (X)∆−qi+q̃i +1 Pi′  ∆. For i with q̃i = qi − 1, we have
τ −q̃i −1 (X)Pi′ = τ −qi (X)Pi′  ∆. By Lemma 4.2, we have τ −qi (X)(Pi′ ∧ ∆)  ∆. The
normal form of the element a−1
is related to that of ai . In particular, we have
i
(i)

Pi′ ∧ ∆ = τ −qi (∂(sli )).
Thus,
(i)

(i)

τ −qi (X∂(sli )) = τ −qi (X(sli )−1 )∆  ∆.

(i)

By invariance of the relation  under right multiplication, we have τ −qi (X)  τ −qi (sli ).
(i)
Invariance of the relation  under the automorphism τ implies that X  sli for all i with

SIMULTANEOUS CONJUGACY IN BRAID GROUPS

9

q̃i = qi − 1. Finally, we can take the left lcm and obtain
∼
_
(i)
(4)
X
sli .
i: q̃i =qi −1

Definition 5.2. In the above notation, the simultaneous decycling operation is the left
conjugation of the tuple a ∈ Gr by the element on the right hand side of Equation (4).
5.2. Simultaneous cyclic sliding.
Definition 5.3. In the above notation, Equations (2) and (4) imply that
∼
∼
 _
  _

(i)
−p̃i +1 −1 (i)
˜
(5)
X
τ
(∂ (s1 )) ∨
sli =: x(0).
i: p̃i =pi +1

i: q̃i =qi −1

The simultaneous cyclic sliding operation (with respect to the target interval [p̃, q̃]) is the
left conjugation of the tuple a ∈ Gr by the element x(0). Let sl(a) := x(0)ax(0)−1 .
It is easy to verify that
p̃i − 1 ≤ inf(sl(ai )) ≤ sup(sl(ai )) ≤ q̃i + 1

for all i = 1, . . . , r. In other words, the infimum and supremum of the element sl(ai ) are
at most in distance one outside the target interval. Indeed, we have implicitly treated the
difficult cases (where p̃i = pi + 1 or q̃i = qi − 1) in the derivation above. The cases where
p̃i = pi or q̃i = qi are clear, since conjugation by any simple element (in particular, by x(0))
can decrease (respectively, increase) the infimum (respectively, supremum) by at most 1.
For an element a ∈ G+ in a Garside group G, let kak be the maximum number of atoms in
an expression of a as a product of atoms. The following theorem generalizes the Birman–Ko–
Lee Cycling Theorem [4] to dimension r > 1. It asserts that if moving to a proper subinterval
is possible, then this can be done in at most k∆k − 1 steps. As usual, for i ∈ {1, . . . , r} let
ei ∈ Zr be the tuple with all coordinates 0 but the i-th, which is 1.
Theorem 5.4 (Simultaneous Cyclic Sliding). Let a ∈ Gr ∩ [p, q]. For each index i = 1, . . . , r
and each pair (p̃, q̃) ∈ {(p + ei , q), (p, q − ei )} with aG ∩ [p̃, q̃] 6= ∅, we have
slk∆k−1 (a) := sl(sl(· · · sl(a))) ∈ [p̃, q̃].
|
{z
}
k∆k−1 times

Proof. Let a(0) := a. For t = 0, 1, . . . , k∆k − 2, let a(t + 1) = sl(a(t)). Let pi (t) := inf(ai (t)),
qi (t) := sup(ai (t)), and li (t) := qi (t) − pi (t). Express the element ai (t) in normal form:
(i)

(i)

ai (t) = ∆pi (t) s1 (t) · · · sli (t) (t).

Explicitly, a(t + 1) = x(t)a(t)x(t)−1 , where
∼
 _
 
(i)
˜
x(t) :=
τ −p̃i +1 (∂ −1 (s1 (t))) ∨
i: p̃i =pi (t)+1

∼
_

i: q̃i =qi (t)−1


(i)
sli (t) (t) .

10

KALKA, TSABAN, AND VINOKUR

Setting X(t) := x(t)x(t − 1) · · · x(1)x(0), we have ai (t) = X(t)ai X(t)−1 .
Let m and X = X(m)  1 be minimal (with respect to ) such that XaX −1 = a(m+1) ∈
[p̃, q̃]. Let X̄(t) := x(m)x(m − 1) · · · x(t), that is, decompose X = X(m) = X̄(t)X(t − 1) for
all t = 1, 2, . . . , m. For t = 0, we obtain X̄(0) = X(m) = X. Define
H(t) := ∆ ∧ X̄(t)

for t = 0, 1, . . . , m. Then H(t + 1)  H(t) for all t = 0, 1, . . . , m − 1.
By the minimality of the number m, we have H(m) = x(m) ≻ 1. By the minimality of
the element X = X(m), we have inf X = 0, and hence H(0) = ∆ ∧ X̄(0) = ∆ ∧ X  ∆. In
order to prove that
(6)

1 ≺ H(m) ≺ · · · ≺ H(1) ≺ H(0) ≺ ∆

it suffices to show that H(t) 6= H(t + 1) for all t. Then Equation (6) implies that
0 < kH(m)k < · · · < kH(1)k < kH(0)k < k∆k,

and thus m + 1, is bounded below k∆k − 1, which completes the proof.
We prove the inequality H(1) 6= H(0); the proof of the inequality H(t + 1) 6= H(t) for
t = 1, . . . , m − 1 is similar. Let L := cl(X) = sup(X) ≤ m + 1. Express in normal form
X = BL · · · B2 B1 . Then H(0) = X̄(0) ∧ ∆ = X ∧ ∆ = BL . Assume, towards a contradiction,
that H(1) = H(0) = BL , that is, X̄(1) ∧ ∆ = BL . Write X̄(1) = x(m) · · · x(1) = BL R1 for
some R1 ∈ G+ . Then X = BL R1 x(0) and BL−1 · · · B1 = R1 x(0). We prove that
(7)

(8)

(BL−1 · · · B1 )ai  ∆p̃i , and

−q̃i
(BL−1 · · · B1 )a−1
i  ∆

For all i = 1, . . . , r.
Proof of Equation (7). First, let i be an index with p̃i = pi + 1. According to Equation (2),
(i)
(i)
we have x(0)  τ −pi (∂ −1 (s1 )). Write x(0) = ri τ −pi (∂ −1 (s1 )). Then
(i)

(BL−1 · · · B1 )ai = R1 x(0)∆pi Pi = R1 ri τ −pi (∂ −1 (s1 ))∆pi Pi
(i)

(i)

(i)

(i)

= R1 ri ∆pi ∂ −1 (s1 )s1 s2 · · · sli  ∆pi +1 = ∆p̃i .
|
{z
}
∆

The case where p̃i = pi is simpler:

(BL−1 · · · B1 )ai = R1 x(0)∆pi Pi  ∆pi = ∆p̃i .

Proof of Equation (8): Let i be an index such that q̃i = qi − 1. According to Equation (4),
(i)
(i)
(i)
−qi
we have x(0)  sli . Write x(0) = ri′ sli . Since a−1
P̄i and P̄i ∧ ∆ = τ −qi (∂(sli ))), we
i = ∆
(i)
can write P̄i = τ −qi (∂(sli ))P̄i′. Thus,
(i)

−qi
(BL−1 · · · B1 )a−1
P̄i = R1 ri′ sli ∆−qi P̄i
i = R1 x(0)∆
(i)

(i)

= R1 ri′ ∆−qi τ −qi (sli )τ −qi (∂(sli )) P̄i′  ∆−qi +1 = ∆−q̃i .
|
{z
}
∆

SIMULTANEOUS CONJUGACY IN BRAID GROUPS

11

The case where q̃i = qi is simpler:
−qi
(BL−1 · · · B1 )a−1
P̄i  ∆−qi = ∆−q̃i .
i = R1 x(0)∆

Next, we prove that:
(9)
(10)

inf((BL−1 · · · B1 )ai (BL−1 · · · B1 )−1 ) ≥ p̃i and

sup((BL−1 · · · B1 )ai (BL−1 · · · B1 )−1 ) ≤ q̃i

For all i = 1, . . . , r.
Proof of Equation (9): Define, for k = 0, 1, . . . , L and i = 1, . . . , r,
αi (k) := inf[(BL−1 · · · B1 )ai ∂(B1 )τ (∂(B2 )) · · · τ k−1 (∂(Bk ))].

Note that ∂(B1 )τ (∂(B2 )) · · · τ k−1 (∂(Bk )) is the normal form of (Bk · · · B1 )−1 ∆k . By definition, for i = 1, . . . , r we have
αi (0) = inf[(BL−1 · · · B1 )ai ] ≥ p̃i ,

αi (L) = inf[(BL−1 · · · B1 ) ai ∂(B1 ) · · · τ L−1 (∂(BL ))]
|
{z
} |
{z
}
X −1 ∆L

−1
BL
X

= inf[BL−1 (Xai X −1 )∆L ] ≥ −1 + p̃i + L,

and

αi (k) ≤ αi (k + 1)

for all k = 0, 1, . . . L − 1. By the lemma, we have αi (k + 1) ≤ αi (k) + 1 for all k and i. Since
∂(B1 )τ (∂(B2 )) · · · τ k−1 (∂(Bk )) is in normal form, we have
αi (k) = αi (k + 1)

⇒

αi (k) = · · · = αi (L − 1) = αi (L).

Assume that there is an index i such that αi (L − 1) ≤ p̃i + L − 2. Since αi (0) ≥ p̃i , there is
a natural number k such that αi (k) = αi (k + 1). Hence αi (k) = · · · = αi (L − 1) = αi (L) ≤
p̃i + L − 2, in contradiction to the inequality αi (L) ≥ p̃i + L − 1. Thus, αi (L − 1) ≥ p̃i + L − 1
for all i = 1, . . . , r, that is,
inf[(BL−1 · · · B1 )ai ∂(B1 ) · · · τ L−2 (∂(BL−1 ))] ≥ p̃i + L − 1,
|
{z
}
(BL−1 ···B1 )−1 ∆L−1

or, equivalently, inf[(BL−1 · · · B1 )ai (BL−1 · · · B1 )−1 ] ≥ p̃i for all i.
Proof of Equation (10): Analogously, define
k−1
αi− (k) := inf[(BL−1 · · · B1 )a−1
(∂(Bk ))].
i ∂(B1 )τ (∂(B2 )) · · · τ

The element αi− (k) has the same properties as αi (k), expect that we have to replace p̃i by
−q̃i . In particular, we have αi− (0) ≥ −q̃i and αi− (L) ≥ −1 − q̃i + L. The proof proceeds as
in the previous case, and we obtain
−1
−1
inf[(BL−1 · · · B1 )a−1
i (BL−1 · · · B1 ) ] = − sup[(BL−1 · · · B1 )ai (BL−1 · · · B1 ) ] ≥ −q̃i .

12

KALKA, TSABAN, AND VINOKUR

Equations (9) and (10) assert that the tuple (BL−1 · · · B1 )a(BL−1 · · · B1 )−1 lies in the target
interval [p̃, q̃], in contradiction to the minimality of the element X = BL BL−1 · · · B1 . We
conclude that the assumption H(0) = H(1) is false.

6. Moving to minimal intervals
Let G be a Garside group and a, c ∈ Gr . The solution to the SCP for a and c, described
in section 4, is by choosing some interval [p, q] containing a and c and computing the set
aG ∩ [p, q]. Increasing p or decreasing q—lexicographically—may reduce the cardinality of
this set considerably.
Algorithm 2 conjugates an r-tuple into a prescribed interval, assuming that this is possible.
For braid groups, with [inf c, ∞] (where c is conjugate to a) instead of [p, q] (and M = ∞), this
algorithm is similar to that of Lee and Lee [27]. Here, for example, we can take the smaller
interval [inf c, sup c]. We note that a simultaneous cycling theorem was not established for
˜ -join of all cyclings for
the operation used by Lee and Lee; they did not conjugate by the ∨
components with infimum outside the target interval.
Algorithm 2 Given tuples a ∈ Gr and p, q ∈ Zr , find an element y ∈ G+ such that
−1
ay ∈ [p, q]. Uses input parameter M ∈ N ∪ {∞}.

function ConjugateToInterval(a, p, q, M)
y := 1; c := a; i := 0
while c ∈
/ [p, q] and i < M do
h := 1
for k := 1 to r do
if inf ck < pk then
˜ ∆τ − inf ck (∆ ∧ (∆− inf ck ck ))−1
h := h ∨
end if
if qk < sup ck then
Bring ck in normal form ∆inf ck s1 · · · scl(ck )
˜ scl(ck )
h := h ∨
end if
end for
−1
y := hy, c := ch
i := i + 1
end while
−1
return y
⊲ Successful if and only if ay ∈ [p, q].
end function

By the Simultaneous Cyclic Sliding Theorem (Theorem 5.4), we have the following performance guarantee.

SIMULTANEOUS CONJUGACY IN BRAID GROUPS

13

Corollary 6.1. Assume that a ∈ Gr ∩[p, q], i ∈ {1, . . . , r}, and (p̃, q̃) ∈ {(p+ei , q), (p, q−ei )}
is a pair with aG ∩ [p̃, q̃] 6= ∅. Let y := ConjugateToInterval(a, p′ , q ′ , k∆k − 1). Then
−1
ay ∈ [p̃, q̃].
Definition 6.2. Let G be a Garside group, r a natural number, a ∈ Gr , and p, q ∈ Zr be
tuples with p ≤ q. The interval [p, q] is minimal for the conjugacy class aG if [p, q] intersects
aG , but no proper subinterval of [p, q] intersects aG .

Consider the one-dimensional case. For a Garside group G and an element a ∈ G,
the summit infimum and summit supremum of a are the maximal infimum and minimal
supremum, respectively, of an element of aG . In this one-dimensional case, the interval
[suminf(a), sumsup(a)] is the only minimal interval with respect to a. Garside’s Summit
Set [16] and Elrifai–Morton’s Super Summit Set [13] of a are the sets
SS(a) = aG ∩ [suminf a, ∞];

SSS(a) = aG ∩ [suminf a, sumsup a],

respectively. These sets are complete conjugacy invariants. In higher dimensions, there
are in general more than one minimal interval for a conjugacy class. Any canonical choice
among them would provide a complete conjugacy invariant. We provide two variations of a
complete invariant for simultaneous conjugacy classes. Since we use minimal intervals, these
invariants generalize the classic Super Summit Sets to general dimension.
Definition 6.3. Let G be a Garside group and a ∈ Gr . The lexicographically minimal
interval for the conjugacy class aG is the unique interval [p, q] with the following properties:
(1) p1 and q1 are the summit infimum and summit supremum of a1 , respectively.
(2) For i = 2, 3, . . . , r, in this order : pi is maximal and qi is minimal (given pi ) with
(a1 , . . . , ai )G ∩ [(p1 , . . . , pi ), (q1 , . . . , qi )] 6= ∅.
The Lexicographic Super Summit Set of a, LSSS(a), is the intersection of aG with its lexicographically minimal interval.
The lexicographically′ minimal interval for the conjugacy class aG is the unique interval
[p, q] with the following properties:
(1) For i = 1, . . . , r: pi is maximal with (a1 , . . . , ai )G ∩ [(p1 , . . . , pi ), ∞] 6= ∅.
(2) For i = 1, . . . , r: qi is minimal with (a1 , . . . , ai )G ∩ [(p1 , . . . , pi ), (q1 , . . . , qi )] 6= ∅.
The Lexicographic′ Super Summit Set of a, LSSS′ (a), is the intersection of aG with its
lexicographically′ minimal interval.
If [p, q] is the lexicographically′ minimal interval for a conjugacy class aG , then the set
LSS(a) := aG ∩ [p, ∞] is also a complete invariant for aG , but it is, in general, larger than
LSSS′ (a).
Given a lexicographically minimal interval [p, q] for an element a ∈ Gr , we can conjugate the element a into LSSS(a) using ConjugateToInterval(a, p, q, k∆k − 1), and then
compute the entire LSSS(a) using Algorithm 1. Algorithm 3 computes the lexicographically
minimal interval for an element a. Analogous assertions hold for LSSS′ (a).

14

KALKA, TSABAN, AND VINOKUR

Algorithm 3 Compute the lexicographically minimal interval [p, q] for an element a ∈ Gr

for i = 1, . . . , r do
pi := inf ai .
repeat
y := ConjugateToInterval((a1 , . . . , ai ), (p1 , . . . , pi + 1), (q1 , . . . , qi−1 , ∞), k∆k −
1)
−1
if (a1 , . . . , ai )y ∈ [(p1 , . . . , pi + 1), (q1 , . . . , qi−1 , ∞)] then
pi := pi + 1
−1
a := ay
flag := true
else
flag := false
end if
until flag = false
qi := sup ai .
repeat
y := ConjugateToInterval((a1 , . . . , ai ), (p1 , . . . , pi ), (q1 , . . . , qi − 1), k∆k − 1)
−1
if (a1 , . . . , ai )y ∈ [(p1 , . . . , pi + 1), (q1 , . . . , qi − 1)] then
qi := qi − 1
−1
a := ay
flag := true
else
flag := false
end if
until flag = false
end for
return p, q
The following proposition summarizes the relations among the introduced invariants.

Proposition 6.4. Let G be a Garside group and i ∈ {1, . . . , r}. Let proji denote the projection on the first i coordinates. For each tuple a ∈ Gr , the following relations hold:
LSS((a1 , . . . , ai )) = proji (LSS(a)),
LSSS((a1 , . . . , ai )) = proji (LSSS(a)),
LSSS′ ((a1 , . . . , ai )) ⊆ proji (LSSS′ (a)),
LSSS′ (a) ⊆ LSS(a).

In particular, we have SS(a1 ) = proj1 (LSS(a)) and
SSS(a1 ) = proj1 (LSSS(a)) ⊆ proj1 (LSSS′ (a)).



SIMULTANEOUS CONJUGACY IN BRAID GROUPS

15

Our invariants are computable in finite time: detecting the lexicographically minimal
interval [p, q] of an element of this set, and then computing aG ∩ [p, q]. Also, note that
finite invariants of conjugacy classes imply canonical representatives: The lexicographically
minimal element of the invariant. However, the computational complexity of computing such
a canonical representative remains proportional to the cardinality of the initial invariant.
This completes our treatment of interval minimization. We next address the second and
last problem: Removing the need to conjugate by all simple elements in each step of our
algorithms. This will be done by extending the method of minimal simple elements to our
situation.
7. Minimal simple elements
We apply the technique of minimal simple elements, introduced by González–Meneses
and Franco [14], in order to make the computation of the sets aG ∩ [p, q] more efficient.
The propositions and algorithms in this section are natural generalizations of earlier algorithms [14, 20, 23].
Proposition 7.1. Let G be a Garside group. Let v ∈ Gr be a tuple with v ∈ [p, q], for
p, q ∈ Zr . For i = 1, . . . , r, express vi = ∆pi wi = zi ∆pi with wi , zi ∈ G+ and (wi−1 ∆qi −pi ),
(∆qi −pi zi−1 ) ∈ G+ . Let s ∈ S. Then:
(1) v s ∈ [p, q] if and only if
τ pi (s)  wi s and τ −qi (s)  (∆qi −pi zi−1 )s

for all i = 1, . . . , r.
−1
(2) v s ∈ [p, q] if and only if

szi  τ −pi (s) and s(wi−1 ∆qi −pi )  τ qi (s)

for all i = 1, . . . , r.

Proof. (1) For i = 1, . . . , r, we have ∆pi ≤ vis ≤ ∆qi if and only if ∆pi  vis  ∆qi . Since 
is invariant under left multiplication, we have ∆pi  s−1 ∆pi wi s if and only if τ pi (s)  wi s,
and s−1 zi ∆pi s  ∆qi is equivalent to s  ∆−pi zi−1 s∆qi = τ qi (∆qi −pi zi−1 s). By invariance of
 under the automorphism τ , we have τ −qi (s)  (∆qi −pi zi−1 )s.
−1
−1
(2) Here, for i = 1, . . . , r, we use that ∆pi ≤ vis ≤ ∆qi if and only if ∆qi  vis  ∆pi .
Since  is invariant under right multiplication, we conclude that szi ∆pi s−1  ∆pi if and only
if szi  τ −pi (s), and ∆qi  s∆pi wi s−1 is equivalent to ∆qi swi−1 ∆−pi = τ −qi (swi−1∆qi −pi )  s.

By invariance of  under τ , we have s(wi−1∆qi −pi )  τ qi (s).

˜ ).
Lemma 7.2. Assume that a set A ⊆ S is closed under the operation ∧ (respectively, ∧
Let x ∈ A. If the set { s ∈ A : x  s } (respectively, { s ∈ A : s  x }) is nonempty, then it
has a unique minimal element with respect to the relation  (respectively, ).

Proof. Every interval { x ∈ G+ : a  x  b } in the poset (G+ , ) is closed under the
operations ∧ and ∨. The intersection of sets closed under ∧ and ∨ is also closed under these
operations. Uniqueness follows.


16

KALKA, TSABAN, AND VINOKUR
[p,q]

Definition 7.3. Let G be a Garside group, p, q ∈ Zr , and v ∈ [p, q]. The set Sright (v) consists
[p,q]
of all -minimal elements s ∈ S such that v s ∈ [p, q]. Similarly, the set Sleft (v) consists of
−1
all -minimal elements s ∈ S such that v s ∈ [p, q].
Analogously to the proof of Gonzáles–Meneses [20, Proposition 2.2], we prove the following
result.

Theorem 7.4. Let G be a Garside group, and a, c ∈ [p, q] ⊆ Gr . The following assertions
are equivalent:
(1) The tuples a and c are conjugate.
(2) There exist a natural number l, elements w̃1 , . . . , w̃l−1 ∈ aG ∩ [p, q], and elements
[p,q]
s̃i ∈ Sright (w̃i ), for i = 1, . . . , l, such that
s̃

s̃

s̃l−1

s̃

1
2
l
a ←−
w̃1 ←−
c.
· · · ←− w̃l−1 ←−

(3) There exist a natural number l, elements w1 , . . . , wl−1 ∈ aG ∩ [p, q], and elements
[p,q]
si ∈ Sleft (wi ), for i = 1, . . . , l, such that
s

s

sl−1

s

1
2
l
a −→
w1 −→
c.
· · · −→ wl−1 −→



The set { s ∈ S : v s ∈ [p, q] } is closed under ∧. It follows [14, Corollary 4.3] that for each
[p,q]
s ∈ Sright (v) there is an atom x ∈ S such that s is the unique -minimal element of the set
[p,q]

{ a ∈ S : x  a and v a ∈ [p, q] }. Similarly, each element of Sleft (v) is the unique -minimal
element of the set { a ∈ S : a  x and v a ∈ [p, q] } for some atom x ∈ S. It follows that, in
[p,q]
Algorithm 1, the computation of aG ∩ [p, q] can be done with S replaced by Sright (v), a set
not larger than the number of atoms in S. For example, the Artin groups of type An , Bn ,
and Dn , respectively, have (n + 1)!, n!2n , and n!2n−1 simple elements, but only n atoms.
Algorithms 4, 5 and 6, build on earlier algorithms [14, 20, 23].
Proposition 7.5. Let G be a Garside group, p, q ∈ Zr , v ∈ [p, q] ⊆ Gr , and x ∈ S.
Algorithm 4 terminates and provides the correct output.
Proof. By Proposition 7.1 (1), we need to find the smallest element rx such that for all
i = 1, . . . , r, x  rx , τ pi (s)  wi s and τ −qi (s)  wi′ s with wi′ = ∆qi −pi zi−1 . We take a simple
element s such that x  s  rx , initializing with s := x. Then, for k such that τ pk (s)  wk s
or τ −qk (s)  (∆qk −pk zk−1 )s, we compute s1 , s2 ∈ G such that τ pk (s) ∨ wk s = wk ss1 and
τ −qk (s) ∨ wk′ s = wk′ ss2 . If s′ := s1 ∨ s2 = 1, then s1 = s2 = 1, and we have τ p (s)  ws
and τ −q (s)  w ′ s, in contradiction to the choice of k. Thus, s′ 6= 1. s  rx implies that
τ pk (s)  τ pk (rx )  wk rx , and by left-invariance of , it also implies that wk s  wk rx , that is,
τ pk (s), wk s  wk rx . By the definition of right lcm, we have that τ pk (s)∨wk s = wk ss1  wk rx ,
and therefore ss1  rx .
Furthermore, s  rx implies that τ −qk (s)  τ −qk (rx )  wk′ rx , and by left-invariance of the
relation  it also implies wk′ s  wk′ rx , that is, τ −qk (s), wk′ s  wk′ rx . By the definition of right
lcm, τ −qk (s) ∨ wk′ s = wk′ ss2  wk′ rx , and therefore ss2  rx .

SIMULTANEOUS CONJUGACY IN BRAID GROUPS

17

Algorithm 4 Compute the minimal element in the set { a ∈ S : x  a and v a ∈ [p, q] }, for
an atom x.
Express vi = ∆pi wi = zi ∆pi
s := x
while There is an index k ∈ {1, . . . , r} with τ pk (s)  wk s or τ −qk (s)  (∆qk −pk zk−1 )s do
Choose such an index k
Compute s1 ∈ S such that τ pk (s) ∨ wk s = wk ss1
wk′ := ∆qk −pk zk−1
Compute s2 ∈ S such that τ −qk (s) ∨ wk′ s = wk′ ss2
s′ := s1 ∨ s2
s := ss′
rx := s
end while
return rx
From ss1  rx and ss2  rx we conclude that ss1 ∨ ss2 = s(s1 ∨ s2 ) = ss′  rx .
So, if s is not equal to rx , then Algorithm 4 gives an element s′ 6= 1 such that s  ss′  rx ,
and it starts again checking whether ss′ = rx . Since the number of left divisors of rx is finite,
this process must stop. Therefore, Algorithm 4 finds the requested minimal element in finite
time.

Algorithm 5 Compute the minimal element of the set { a ∈ S : a  x and v a ∈ [p, q] }, for
an atom x ∈ S
Express vi = ∆pi wi = zi ∆pi
s := x
while There is k with szk  τ −pk (s) and s(wk−1 ∆qk −pk )  τ qk (s) do
˜ szk = s1 szk
Compute s1 ∈ S such that τ −pk (s)∨
−1 qk −pk
′
wk := wk ∆
˜ swk′ = s2 swk′
Compute s2 ∈ S such that τ qk (s)∨
′
˜ s2
s := s1 ∨
′
s := s s
end while
rx := s
return rx
[p,q]

[p,q]

The sets of minimal simple elements Sright (v) and Sleft (v) can be computed by comparing
the elements rx , for all atoms x of G+ , and keeping the minimal ones. Since it is faster to
check whether an atom divides an simple element than to compare two simple elements, we
prefer to use [14, Algorithm 3] (see Proposition 5.3 there).
We conclude by pointing out that, since our invariants are preserved by the automorphism
τ , it is natural to consider them modulo τ , that is, to maintain only one representative (for

18

KALKA, TSABAN, AND VINOKUR
[p,q]

[p,q]

Algorithm 6 Compute Sright (v) or Sleft (v), respectively.
Let x1 , . . . , xm be the atoms of G
R := ∅
for i = 1, . . . , m do
Compute rxi using Algorithm 4 (or 5, respectively)
Ji := { j : j ∈ R and xj  rxi (or rxi  xj ) }
Ki := { j : j > i and xj  rxi (or rxi  xj ) }
if Ji = Ki = ∅ then
R := R ∪ {i}
end if
end for
return { rxi : i ∈ R }
example, the lexicographically minimal one) out of each τ -orbit. For example, the order of
τ for two known Garside structures in braid groups BN with N ≥ 4 strands, namely, the
Artin–Garside structure with Garside element ∆ = ∆N and the dual or Birman–Ko–Lee
structure with ∆ = δN , are 2 and N, respectively.
8. Experimental results in Artin’s braid groups
We have conducted extensive experiments checking the cardinalities of the finite sets that
can be used for solving the SCP. The experiments are on Artin’s braid groups BN , with their
two known Garside structures (Artin and BKL). For a tuple a ∈ BrN , the set aBN ∩ [inf a, ∞]
is the one proposed by Lee and Lee [27]. The set aBN ∩ [inf a, sup a] is its natural subset
introduced here. Both of these sets are not invariants of the conjugacy class. The sets LSS(a)
and LSSS(a) are the invariants introduced here, namely the lexicographic summit set and
the lexicographic super summit set.
We did not notice substantial differences between the cardinalities of the two variations
of LSSS introduced here. Thus, we used in the experiments the second variation, so that
LSSS(a) is always a subset of LSS(a). This allows the use of a smaller number of experiments,
while avoiding problems arising from the large variance.
To give the two sets that are not invariants a fair chance, we considered them for solving
the Search SCP: We constructed conjugate a, c ∈ BrN by choosing b ∈ BrN and x, y ∈ BN ,
and setting a = bx and c = by . We then computed, instead of aBN ∩ [inf a, ∞], the typically
smaller set aBN ∩ [inf c, ∞], and similarly for the other set.
Random elements of BN were generated as products of random 2N log N generators, each
inverted in probability 1/2. Such products are, with high probability, fully supported in the
group.
We summarize the results in Table 8, which demonstrates the following typical inequalities:
|LSSS(a)| < |LSS(a)| ≪ aBN ∩ [inf c, sup c] < aBN ∩ [inf c, ∞] .

SIMULTANEOUS CONJUGACY IN BRAID GROUPS

19

The symbol ≪ indicates a dramatic improvement when moving to the invariants. An additional observation is that the BKL presentation provides much smaller sets, often one-element
sets!

Table 1. Cardinalities of sets (modulo τ ) associated to the SCP, for dimension r = 8. Each cell lists the minimum, median, and maximum cardinality
encountered, as well as the percentage of failures, out of 100 experiments. ∞
means > 100,000.
aBN ∩ [inf c, ∞] aBN ∩ [inf c, sup c]
LSS(a)
LSSS(a)
N
Artin
BKL Artin
BKL Artin BKL Artin BKL
4
1
1
1
1
1
1
1
1
116
54
37
17
1
1
1
1
80,438 27,786 14,318
3,441
8
3
5
1
0%
0%
0%
0%
0%
0%
0%
0%
8
∞
∞ 40,630
872
1
1
1
1
∞
∞
∞
∞
63
2
5
1
∞
∞
∞
∞ 3,732 966
160
17
100% 100%
98%
96%
0%
0%
0%
0%
∞
∞
∞
∞ 69,534
2
68
1
16
∞
∞
∞
∞
∞ 740 76,509
6
∞
∞
∞
∞
∞
∞
∞ 28,025
100% 100% 100%
100%
99% 10%
76%
0%

We have tested, for the BKL presentation, the effect of increasing the dimension. Table
2 summarizes the results. We observe that the cardinality of the invariant LSSS tends to 1
with the increase of the dimension, and suggests that when r = O(N) and the elements of
the r-tuple are “generic” and independent, the invariant tends to have cardinality 1.

Table 2. The effect of increasing the dimension r on the cardinality of
the Birman–Ko–Lee Lexicographic SSS invariant (modulo τ ), for braid index N = 32. Each cell lists the minimum, median, and maximum cardinality
encountered, out of 100 experiments. ∞ means > 100,000.
r
4
8 16 32 64
Minimum
∞ 720
3
1
1
Median
∞
∞ 95
2
1
Maximum
∞
∞ ∞ 75
4
Failures
100% 75% 3% 0% 0%

20

KALKA, TSABAN, AND VINOKUR

9. Comparison with Garside families
Some of the conditions in the definition of Garside monoids, like being Noetherian, are
often not needed to establish results about them [9, 10]. In the monograph on foundations of
Garside theory [10], the monoid M is replaced by a left-cancellative category C, and the set
of simple elements S is generalized to a “Garside family”, i.e., a subfamily S of C such that
every element in C admits a normal decomposition with respect to S. A Garside category
is a category C that admits such a subfamily S. This generalizes the classic definition in
several directions [10, Chapter 1]:
-

The family S may be infinite (e.g., for the braid group B∞ ),
the monoid (i.e., the category) may be not Noetherian (e.g., the Klein bottle monoid),
it allows for invertible elements (e.g., wreathed free abelian group Zn ≀ Sn ), and
multiplication may not be defined everywhere (e.g., for Ribbon categories).

There are several reasons for our working with the classic definition of Garside groups. Our
main focus is the braid group, and for some group theorists and cryptologists, the classic
definition is more familiar. We developed formulas for special operations using the left and
right lcm, and established the simultaneous cyclic sliding theorem. This theorem requires
Noetherianity, since it explicitly involves the norm of the Garside element. To work with
Garside categories, we would have to consider cancellative Noetherian Garside categories
where every two elements have a left and right lcm, and the Garside family is bounded [10].
Finally, our algorithms for minimal simple elements require that the number of atoms is
finite; we cannot allow infinitely many atoms in S.
The problem of conjugacy in the context of Garside categories is treated in chapter VIII
of the cited book [10]. Remark 1.16 and Exercise 95 there concern simultaneous conjugacy.
The solution of the mentioned exercise appears in a work of Digne and Michel [12, Proposition 6.2] This establishes the first solution to the simultaneous conjugacy problems for
Garside categories, and thus for Garside monoids and groups. Restricted to Artin’s braid
groups, this solution seems to be considerably less efficient than our solution, since it does
not use minimal intervals or anything similar.
In the context of Garside categories one can also define cycling, decycling and cyclic sliding
operations [10, Chapter VIII, Definitions 2.3, 2.8, and 2.29]. These definitions are made in
the object category of the conjugacy category. Thus, a Garside family in the simultaneous
conjugacy category does not help defining these operations. To this end, our notions of
cycling, decycling and cyclic sliding with respect to a target interval should be generalized
to Garside categories.
10. Open problems and further work
In Section 2 we reduced several problems to the conjunction of the Search SCP and the
computation of the centralizer of a set. At present, there are no efficient algorithms for the
computation of the centralizers of sets with more than one element in the braid groups. The

SIMULTANEOUS CONJUGACY IN BRAID GROUPS

21

computation of the centralizer of an element in braid groups involves methods used to solve
the Conjugacy Problem in these groups [15].
Problem 10.1. Does the computation of the centralizer of a set in a group reduce to the
Search SCP?
The invariants introduced in the present paper depend on the order of entries in the
r-tuple.
Problem 10.2. Is there an invariant, computable in comparable time, that does not depend
on the order of the entries?
Our invariants may be huge. In the one-dimensional case, there are the much better
(essentially, equivalent) invariants of Ultra Summit Sets and Sliding Circuits.
Problem 10.3. Is there a generalization of Ultra Summit Sets or Sliding Circuits to the
high-dimensional setting?
It is tempting to define, for example, decycling as left conjugation by the left lcm of all
tails (or final factors) of all components. However, for large simultaneity r, the left lcm of
all tails is, generically, ∆. Thus, we conjugate (from the left) by the left lcm of all tails of
elements where the supremum can be decreased (i.e., where the element is not in its summit
set). Thus, our decycling is only defined for elements that are outside the (simultaneous)
super summit sets, and they do not define simultaneous USS or sliding circuits in any direct
manner.
It is also natural to consider potential applications of this work to cryptanalysis. As we
can see in Section 2, the reductions to the Search SCP provide highly biased instances. The
dependency among the entries renders the invariants too large to be of any direct use. To
this end, the invariants must be combined with heuristic shortcuts, like ones used earlier [21].
The Search SCP has the following heuristic speedup: We compute LSSS(a) and LSSS(c) in
parallel, until we find an element in the intersection. Heuristically,
this has the potential to
√
reduce the running time from n := |LSSS(a)| to about n. However, in our experiments
we did not observe the expected speedup. An investigation of this phenomenon may help
addressing Problem 10.3.
Acknowledgments. We thank Patrick Dehornoy and Jean Michel for providing us information about representation theory of Garside groups and Garside families and, in particular,
for discussions that are summarized in Section 9. We thank David Garber for useful discussions. The research of the first named author is partially supported by the Minerva
Foundation of Germany.
References
[1] I. Anshel, M. Anshel, D. Goldfeld, An algebraic method for public-key cryptography, Mathematical
Research Letters 6 (1999), 287–291.
[2] A. Ben-Zvi, A. Kalka, B. Tsaban, Cryptanalysis via algebraic spans, IACR eprint IACR eprint 2014/041.

22

KALKA, TSABAN, AND VINOKUR

[3] J. Birman, K. Ko, S. Lee, New approaches to the word and conjugacy problem in the braid groups,
Advances in Mathematics 139 (1998), 322–353.
[4] J. Birman, K. Ko, S. Lee, The infimum, supremum and geodesic length of a braid conjugacy class,
Advances in Mathematics 164 (2001), 41–56.
[5] J. Cheon, B. Jun, A polynomial time algorithm for the braid Diffie–Hellman conjugacy problem,
CRYPTO 2003, Lecture Notes in Computer Science 2729 (2003), 212–224.
[6] J. Cha, K. Ko, S. Lee, J. Han, J. Cheon, An efficient implementation of braid groups, ASIACRYPT
2001, Lecture Notes in Computer Science 2248 (2001), 144–156.
[7] John Crisp, Injective maps between Artin groups, in: Geometric Group Theory Down Under, Walter
deGruyter, 1999, 119–137.
[8] P. Dehornoy, Using shifted conjugacy in braid-based cryptography, Contemporary Mathematics 418
(2006), 65–73.
[9] P. Dehornoy, F. Digne, J. Michel, Garside families and Garside germs, Journal of Algebra 380 (2013),
109–145.
[10] P. Dehornoy, with F. Digne, E. Godelle, J. Michel, Foundations of Garside Theory, EMS Tracts in
Mathematics, volume 22, xviii + 690 pages, European Mathematical Society, 2015.
[11] P. Dehornoy, L. Paris, Gaussian groups and Garside groups, two generalizations of Artin groups, Proceedings of the London Mathematical Society 79 (1999), 569–604.
[12] F. Digne and J. Michel, Garside and locally Garside categories, arXiv eprint /0612652, 2006.
[13] E. Elrifai, H. Morton, Algorithms for positive braids, Quarterly Journal of Mathematics 45 (1994),
479–497.
[14] N. Franco, J. González–Meneses, Conjugacy problem for braid groups and Garside groups, Journal of
Algebra 266 (2003), 112–132.
[15] N. Franco, J. González–Meneses, Computation of Centralizers in Braid groups and Garside Groups,
Rev. Mat. Iberoamericana 19 (2003), 367–384.
[16] F. Garside, The braid group and other groups, Quarterly Journal of Mathematics 20 (1969), 235–254.
[17] D. Garber, A. Kalka, E. Liberman, M. Teicher, Double Centralizers of Parabolic Subgroups of Braid
Groups, arXiv eprint 1310.0936
[18] V. Gebhardt, J. González–Meneses, The cyclic sliding operation in Garside groups, Mathematische
Zeitschrift 265 (2010), 85–114.
[19] E. Godelle, Parabolic subgroups of Garside groups, Journal of Algebra 317 (2007), 1–16.
[20] J. Gonzáles–Meneses, Improving an algorithm to solve Multiple Simultaneous Conjugacy Problem in
braid groups, Contemporary Mathematics 372 (2005), 35–42.
[21] D. Hofheinz, R. Steinwandt, A practical attack on some braid group based cryptographic primitives, PKC
2003, Lecture Notes in Computer Science 2567 (2002), 187–198.
[22] A. Kalka, E. Liberman, M. Teicher, A Note on the Shifted Conjugacy Problem in Braid Groups, Groups
Complexity Cryptology 1 (2009), 227–230.
[23] A. Kalka, E. Liberman, M. Teicher, Solution to the subgroup conjugacy problem for Garside subgroups
of Garside groups, Groups Complexity Cryptology 2 (2010), 157–174.
[24] A. Kalka, M. Teicher, B. Tsaban, On the Double Coset Problem for parabolic subgroups of Artin’s braid
groups, arXiv eprint 1402.5541
[25] C. Kassel, V. Turaev, Braid Groups, Graduate Texts in Mathematics 247, Springer, New York, 2008.
[26] K. Ko, S. Lee, J. Cheon, J. Han, J. Kang, C. Park, New public-key cryptosystem using braid groups,
CRYPTO 2000, Lecture Notes in Computer Science 1880 (2000), 166–183.
[27] S. Lee, E. Lee, Potential weaknesses of the commutator key agreement protocol based on braid groups,
EUROCRYPT 2002, Lecture Notes in Computer Science 2332 (2002), 14–28.
[28] M. Picantin, Petites groupes gaussiens, Thèse de Doctorat de l’Université de Caen, 2000.

SIMULTANEOUS CONJUGACY IN BRAID GROUPS

23

[29] M. Picantin, The conjugacy problem in small Gaussian groups, Communications in Algebra 29 (2001),
1021–1039.
[30] M. Picantin, Automatic structures for torus link groups, Journal of Knot Theory and its Ramifications
12, no. 5 (2003), 1–34.
[31] V. Shpilrain, A. Ushakov, A new key exchange protocol based on the decomposition problem, in: L.
Gerritzen, D. Goldfeld, M. Kreuzer, G. Rosenberger and V. Shpilrain, eds., Algebraic Methods in
Cryptography, Contemporary Mathematics 418 (2006), 161–167.
[32] William Thurston, Braid groups, chapter 9 in: D. Epstein, J. Cannon, D. Holt, S. Levy, M. Paterson,
W. Thurston, Word processing in groups, Jones and Bartlett, 1992.
[33] B. Tsaban, Polynomial-time solutions of computational problems in noncommutative algebraic cryptography, Journal of Cryptology 28 (2015), 601–622.
(Kalka) Department of Mathematics, Bar-Ilan University, Israel
Current address: Department of Computer Science, Dortmund University of Applied Sciences and Arts,
Germany
E-mail address: arkadius.kalka@fh-dortmund.de
(Tsaban) Department of Mathematics, Bar-Ilan University, Israel; and Faculty of Mathematics, Weizmann Institute of Science, Israel
E-mail address: tsaban@math.biu.ac.il
(Vinokur) Department of Mathematics, Bar-Ilan University, Israel
E-mail address: vinokur777@gmail.com

