Braids and Knots

这一建议的主要焦点是辫子群中的共轭问题，最终在Garside和Artin群中以及在曲面映射类群中也是如此。首先，我们建议研究辫子群中共轭问题的两种已知方法之间的界面：(A)由Frank Garside于1968年提出的组合解；以及(B)由JakobNielsen在1932年首次研究并于1982年被威廉·瑟斯顿赋予新含义的动态方法。我们注意到(A)给出了关于两个辫子何时是共轭的确定性检验，而(B)给出了更少的结果。另一方面，(A)在字长和辫子指数上都是指数的，而(B)则表明可能存在多项式解。现在进行一项结合了这两方面的调查的时机似乎已经成熟。Gebhardt在(A)上的新工作表明，“超级峰集”这一完全的类不变量可以被更小的“超峰集”(USS)所取代。我们希望用已知的动态分类来研究USS。我们将从研究可约辫子的约化曲线开始，然后研究有限序(FO)和伪Anosov(PA)辫子。我们推测，对于USS中的编织，减速曲线可以选择为与包含两点穿孔的直线相交的圆。我们进一步推测，PA编织物具有“刚性幂”，其组合特别简单。将辫子群看作映射类群的一个特例，然后进一步期望相关的曲线群将是特殊的和有趣的。如果一切顺利，将有更多的问题需要研究，包括更一般的映射类群中的相关组合学，以及更一般的Garside和Artin群中的相关动力学。近年来，人们对某些代码非常感兴趣，即基于辫子群的公钥密码学。基本的想法是，众所周知，辫子群中的所谓‘单词问题’有一个快速的解决方案。也就是说，检查两个词是否代表辫子群中的同一元素所需的时间是作为字长L和辫子指数N的函数的多项式。另一方面，L和N中认为更困难的共轭问题从根本上是指数的。就像复杂性理论中的大多数这样的问题(例如，将数字分解成素数)，如果能找到更巧妙的解决方案，总是存在这样的可能性：一个被认为是指数的特殊问题将变成多项式的。多年来，PI一直是辫子群研究的主要专家。她现在建议从一种新的角度来研究辫子群中的共轭问题，她希望在L和N中都能证明它是多项式的，就像单词问题一样。其基本思想是研究共轭问题的两种截然不同的方法，一种基于组合学，另一种基于动力学，并应用第二种方法的思想来简化第一种方法。如果成功，这项研究将对公钥密码学中基于编群的码的安全性产生影响。由于辫子群所起的中心作用，它在数学中也应该有很多应用。

The main focus of this proposal is the conjugacy problem in braid groups,and ultimately in Garside and Artin groups and also in surface mappingclass groups. To begin, we propose to investigate the interface betweentwo known approaches to the conjugacy problem in the braid groups: (a) thecombinatorial solution that originated with the work of Frank Garside in1968; and (b) the dynamic approach which was first studied by JakobNielsen in 1932 and later given new meaning, in 1982, by William Thurston.We note that (a) gives a definitive test for when two braids areconjugate, whereas (b) gives less than that. On the other hand (a) isexponential in both word length and braid index, whereas (b) suggests thepossible existence of a polynomial solution. The moment seems to be ripefor an investigation which combines aspects of both. The new work ofGebhardt on (a) shows that the `Super Summit Set', a complete classinvariant, can be replaced by the smaller `Ultra Summit Set' (USS). Ourhope is to use the known dynamic classification to study the USS. We willbegin with a study of reducing curves for reducible braids, and go on tostudy finite order (FO) and pseudo-Anosov (PA) braids. We conjecturethat for braids in the USS the reducing curves can be chosen to be roundcircles which meet a line containing the punctures in 2 points. Weconjecture further that PA braids have `rigid powers whose combinatoricsis particularly simple. Looking at the braid group as a special case ofmapping class groups, one then expects further that the associated traintracks will be special and interesting. If all this goes well, there willbe further problems to investigate, including related combinatorics inmore general mapping class groups, and related dynamics in more generalGarside and Artin groups.In recent years there has been great interest in certain codes, in `PublicKey Cryptography, which are based upon the use of braid groups. Theunderlying idea has been that the so-called `word problem in the braidgroups is known to have a solution which is fast. That is, the timerequired to check whether two words represent the same element in thebraid group is known to be polynomial as a function of word length L andbraid index N. On the other hand, the conjugacy problem, which is moredifficult, has been thought to be fundamentally exponential in L and N.Like most such problems in complexity theory (e.g. the factorization ofnumbers into primes) the possibility always exists that a particularproblem which was thought to be exponential will turn out to be polynomialif a more ingenious solution can be found. The PI has been a leadingexpert in the study of braid groups for many years. She now proposes toinvestigate the conjugacy problem in the braid groups from a new point ofview which she hopes will show it to be polynomial, like the word problem,in both L and N. The underlying idea is to look at two very differentapproaches to the conjugacy problem, one based on `combinatorics and theother on `dynamics, and to apply ideas from the second approach tosimplify the first. If successful, this research would have implicationsin Public Key Cryptography as regards the security of codes based uponbraid groups. It should also have many applications in mathematics becauseof the central role played by the braid groups.