RT Journal Article
T1 The Root Extraction Problem for Generic Braids
A1 Cumplido, María
A1 González Meneses, Juan
A1 Silvero, Marithania
AB We show that, generically, finding the k-th root of a braid is very fast. More precisely, we providean algorithm which, given a braid x on n strands and canonical length l, and an integer k > 1, computesa k-th root of x, if it exists, or guarantees that such a root does not exist. The generic-case complexityof this algorithm is O(l(l + n)n3 log n). The non-generic cases are treated using a previously knownalgorithm 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 D), consisting of either a singleorbit conjugated to itself by D or two orbits conjugated to each other by D.
PB MDPI
SN 2073-8994
YR 2019
FD 2019-11
LK http://hdl.handle.net/10272/17584
UL http://hdl.handle.net/10272/17584
LA eng
NO Cumplido, M., González Meneses, J.,  Silvero, M. (2019). The Root Extraction Problem for Generic Braids. Symmetry, 11(11), 1327. DOI: https://doi.org/10.3390/sym11111327
NO Authors partially supported by the Spanish research project MTM2016-76453-C2-1-P and FEDER. Firstauthor was also supported by EPSRC New Investigator Award EP/S010963/1. Third author was also supported bythe Basque Government grant IT974-16 and Centro de Estudios Avanzados en Física, Matemáticas y Computación dela Universidad de Huelva.
DS Repositorio Institucional de la Universidad de Huelva
RD 30 may 2026