The Infimum, Supremum, and Geodesic Length of a Braid Conjugacy Class
The Infimum, Supremum, and Geodesic Length of a Braid Conjugacy Class
复制标题
辫子共轭类的下确界、上界和测地线长度
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Sang Jin Lee
中科院分区：
文献类型：
--
作者：
J. Birman;K. Ko;Sang Jin Lee
摘要 早期工作中给出了辫子群 Bn,n =2, 3, 4, ... 中共轭问题的算法解决方案。本注释涉及两个整数类不变量的计算，称为“inf”和“sup”。两种算法的一个关键问题是必须“循环”（或“去循环”）的 m 次，以便增加 inf（或减少 su）或确保它对于该类来说已经是最大值（或最小值）。我们的主要结果是证明，在 E. A. Elrifai 和 H. R. Morton (1994, Quart. J. Math. Oxford45, 479–497) 所陈述的情况下，m 受 ((n2−n)/2)−1 限制，而在作者 (1998, Adv. Math.139, 322–353) 所陈述的情况下，m 受 n−2 限制。紧接着，在两种算法中，inf 和sup 的计算在字长和编织索引上都是多项式。整数 inf 和 su 确定（但不是由其确定）共轭类中元素的最短测地线长度，因此我们还获得了用于计算该长度的多项式时间算法。
Abstract Algorithmic solutions to the conjugacy problem in the braid groups Bn,n =2, 3, 4, … were given in earlier work. This note concerns the computation of two integer class invariants, known as “inf” and “sup.” A key issue in both algorithms is the number m of times one must “cycle” (resp. “decycle”) in order to either increase inf (resp. decrease sup) or to be sure that it is already maximal (resp. minimal) for the class. Our main result is to prove that m is bounded above by ((n2−n)/2)−1 in the situation stated by E. A. Elrifai and H. R. Morton (1994, Quart. J. Math. Oxford45, 479–497) and by n−2 in the situation stated by authors (1998, Adv. Math.139, 322–353). It follows immediately that the computation of inf and sup is polynomial in both word length and braid index, in both algorithms. The integers inf and sup determine (but are not determined by) the shortest geodesic length for elements in a conjugacy class, and so we also obtain a polynomial-time algorithm for computing this length.