Article
The root extraction problem for generic braids
Author/s | Cumplido Cabello, María
![]() ![]() ![]() ![]() ![]() ![]() González-Meneses López, Juan ![]() ![]() ![]() ![]() ![]() ![]() ![]() Silvero Casanova, Marithania ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Department | Universidad de Sevilla. Departamento de álgebra |
Date | 2019-10 |
Published in |
|
Abstract | We show that, generically, finding the k-th root of a braid is very fast. More precisely, we provide an algorithm which, given a braid x on n strands and canonical length l, and an integer k > 1, computes a k-th root of ... We show that, generically, finding the k-th root of a braid is very fast. More precisely, we provide an algorithm which, given a braid x on n strands and canonical length l, and an integer k > 1, computes a k-th root of x, if it exists, or guarantees that such a root does not exist. The generic-case complexity of this algorithm is O(l(l + n)n3 log n). The non-generic cases are treated using a previously known algorithm by Sang-Jin Lee. This algorithm uses the fact that the ultra summit set of a braid is, generically, very small and symmetric (through conjugation by the Garside element ∆), consisting of either a single orbit conjugated to itself by ∆ or two orbits conjugated to each other by ∆. |
Project ID. | MTM2016-76453-C2-1-P
![]() EP/S010963/1 ![]() IT974-16 ![]() |
Citation | Cumplido Cabello, M., González-Meneses López, J. y Silvero Casanova, M. (2019). The root extraction problem for generic braids. Symmetry, 11 (11), 1-15. |
Files | Size | Format | View | Description |
---|---|---|---|---|
The root extraction problem for ... | 310.5Kb | ![]() | View/ | |