Braids and Knots

这个建议的主要重点是共轭问题的辫子群，并最终在Garside和Artin群，也在表面mappingclass组。 开始，我们提出研究辫子群中共轭问题的两种已知方法之间的接口：（a）源于Frank Garside在1968年工作的组合解;以及（B）动力学方法，该方法首先由JakobNielsen在1932年研究，后来在1982年被赋予新的含义，我们注意到，（a）给出了两条辫子共轭时的确定性检验，而（B）给出的检验要少一些。另一方面，（a）在字长和辫子指数上都是指数的，而（B）表明可能存在多项式解。 现在似乎是时候进行一项结合两者的调查了。Gebhardt关于（a）的新工作表明，“超级顶点集”，一个完整的类不变量，可以用较小的“超顶点集”（USS）代替。我们希望利用已知的动力学分类来研究USS。我们将从研究可约辫的约化曲线开始，接着研究有限阶（FO）和伪Anosov（PA）辫。 对于USS中的编织物，可以选择与包含2个点的穿孔的线相交的圆形的缩径曲线。 我们进一步推测，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.