Complete simultaneous conjugacy invariants in Artin's braid groups
This provides an effective solution to a fundamental computational problem in group theory, particularly for braid groups used in cryptography and topology, though it is incremental as it builds on existing super summit set concepts.
The authors solved the simultaneous conjugacy problem in Artin's braid groups and Garside groups by developing a complete, finite invariant that generalizes super summit sets to higher dimensions, with complexity polynomial in set cardinalities and input parameters. Computer experiments indicated that for order N independent elements in braid group B_N, the invariant's cardinality is typically close to 1.
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 $B_N$, is generically close to~1.