BRAID GROUPS, ORDERINGS, A N D ALGORITHMS by DJUN MAXIMILIAN KIM B.Sc. The University of British Columbia, 1988 M.Sc. The University of British Columbia, 1990 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES Department of Mathematics W^accepr-this thesis as conforming to tftti required standard THE UNIVERSITY OF BRITISH COLUMBIA May 1999 © Djun Maximilian Kim, 1999 In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Mathematics The University of British Columbia Vancouver, Canada Abstract We define a natural and readily calculated bi-invariant strict total ordering of the n-strand pure braid group P . It is defined algebraically, using the Artin decomposition of P as a semi-direct product of free groups, together with a specific ordering of free groups using the Magnus expansion. This definition extends to define bi-orderings of more general semi-direct products involving free groups, including the fundamental groups of the complements of fibretype hyperplane arrangements. After basic properties of this "Artin-Magnus" ordering are established, we compare it to existing orderings on P , including the restriction of the Dehornoy ordering to P . Finally, we present algorithms to compute the Dehornoy ordering on the full braid group B , and the Artin-Magnus ordering on P . An implementation of these algorithms is included as part of a library of objects for symbolic computation with braids. n n n n n n ii Table of Contents Abstract ii Table of Contents iii List of Tables vi List of Figures vii Acknowledgement viii Dedication x Chapter 1. Introduction 1.1 Introduction and Statement of Principal Results 1.2 Outline 1.3 Notation 1 1 2 3 Chapter 2. Braids and Orderings 2.1 Braids .' 2.1.1 Definition.. 2.1.2 Group structure 2.1.3 Automorphisms of Free Groups 2.1.4 Artin Combing and the Structure of Pure Braid Groups 2.2 Ordered Groups 2.2.1 Definitions and Examples 2.2.2 Ordering Semi-direct Products 2.3 The Magnus Ordering of the Free Group F 5 5 5 6 8 n Chapter 3. An Explicit Bi-ordering of the Pure Braid Group 3.1 Construction of the Artin-Magnus Ordering 3.2 Properties and Examples 3.2.1 Garside Positive Braids 3.3 Comparison with other orderings iii 10 12 13 13 15 19 19 19 ....23 25 Table of Contents 3.4 . j 3.3.1 The Garside partial order 3.3.2 The partial order of Elrifai and Morton 3.3.3 The Dehornoy ordering Generalized Artin-Magnus Orderings 3.4.1 Fibre-type hyperplane arrangements 3.4.2 Generalized Artin-Magnus orderings 25 26 26 29 29 31 Chapter 4. Algorithms for Ordering Braids 4.1 The Dehornoy ordering 4.1.1 Implementation 4.2 The Artin-Magnus Ordering 4.2.1 Implementation 32 33 34 35 39 Chapter 5. Conclusions and Future Research 5.1 Conclusions 5.2 Future Research 5.2.1 Ordering related groups 5.2.2 Improvements to the algorithms 46 46 47 47 48 Bibliography 50 Appendix A. An API for Computation with Braids A.l J A V A API for Computation with Braids A. 1.1 J A V A Application Programming Interface User's Guide A.1.2 How to use this API A. 1.3 Installing and using the J A V A Class libraries A.1.4 Example programs A.1.5' Class Hierarchy A.1.6 package math.alg.PowerSeries A.l.7 package math.topol.Braid A. 1.8 package math.topol.Braid.CurveDiagram A.1.9 Class math.alg.PowerSeries.Factor A.l.10 Class math.alg.PowerSeries.NCseries A.1.11 Class math.alg.PowerSeries.Term A.l.12 Class math.topol.Braid.braid A.1.13 Class math.topol.Braid.braidCanvas A.l.14 Class math.topol.Braid.CurveDiagram.CutPoint 53 53 iv 54 54 56 56 57 58 58 58 59 61 66 69 77 81 v Table of Contents v A.1.15 Class math.topol.Braid.CurveDiagram.CutSequence . . . 83 A.1.16 Class math.topol.Braid.CurveDiagram.Interval 87 A.1.17 Index of all Fields and Methods 89 Appendix B. Glossary 99 Appendix C. Colophon 101 Index of Notation 103 Index 105 v List of Tables 4.1 4.2 4.3 4.4 4.5 Possible configurations of strand n, before and after untwisting Action of cxfc on arcs with endpoint k: first 8 cases Action of on arcs with endpoint k: remaining 8 cases Action of cr/t on arcs with endpoint k + 1: first 8 cases Action of Ok on arcs with endpoint A; + 1: remaining 8 cases vi 41 42 43 44 45 List of Figures 2.1 2.2 2.3 2.4 2.5 2.6 2.7 Composition of two braids The z-th elementary braid CTj The punctured disk D„ and generators for F The action of a on TTI (D„) The natural inclusion i : P - i > Pn The generator ZJ,* e F j = { x i , x ) C P A pure braid, before and after combing n x t_ n y i i t i n 3.1 The squares of the elementary generators 3.2 The common braid used for hair, on the first three strings 3.3 The generator A of the center of P4 2 6 7 9 9 10 10 11 20 20 21 4.1 4.2 4.3 4.4 The canonical curve diagram for oxc^o^ G B 5 The disk B[l, 14] in p[0,15] is bounded by strands 1 and 3 The disk 8[1,8] is elementary, but not reducing. The disk /3[9,14] is an elementary reducing disk 34 37 38 38 4-5 f (o\O2O\OzO20~\O\OZ~' 0-20-\0-l,Ci2°~\) = 0\a20\a2~' 0\OiO\ 40 1 X vii Acknowledgement "Some months after the first diary was published, we all decided to sit down and have a good look through it (there had been some complaints). We found: [1] errors in printing (back to front, upside-down, etc.) [2] errors in text (misguided generalizations, general falsehoods, [3] errors in illustrations (usual kind of thing) [4] mixed up themes (not knowing what you're talking about, etc.) [5] general errors (to do with v. basic things like difference, etc.) 16] errors of a moral kind (too much evil on one page, etc.) " David Shrigley — An Eplanation (1996) The opportunity to acknowledge one's debts — of scholarship, friendship, and love, among other things — is rare. Thus it gives me great pleasure to thank the many people and organizations who have helped me to get to where I am today. I am very grateful for financial support from the University of British Columbia, from NSERC, and from the Pacific Institute for the Mathematical Sciences. To the many teachers who have guided me to where I am today — thanks for your knowledge, wisdom, inspiration. I would like to thank my parents, Dong Yun Kim and Elisabeth H. B. Kim, for their love and support, encouragement and guidance, and for being constant examples of strength, wisdom, courage, and love. My friends have offered love and support through thick and thin: Janet Donald, Christine Elliott, Ronald Ferguson, Frances Fry, Mary Ann Lacey, Mark MacLean, Judy Maxwell, David Robinson, Helen Savkovic, Kathleen Stormont, Jonathan Walden, and Hank Williams — my deepest thanks to you all! viii Ackno wledgemen t ix Particular thanks are due to Bill Casselman — my "spiritual advisor" — and Larry Roberts, for enthusiasm, many explanations, insights, long conversations, guidance, advice, faith, and friendship. I am saddened that Larry passed away before being able to see that his encouragement and support bore some fruit. To him I dedicate this work. I offer my thanks to the members of my Examining Committee for reading preliminary drafts of this thesis and presenting much useful feedback. It is my greatest pleasure to thank my supervisor, Dale Rolfsen, for making the difficult look easy, for support and enthusiasm, for having confidence, for being an unfailing fountain of knowledge, for intellectual guidance, for generous financial support — all above and beyond the call of duty. ix To Larry t "The heavy trouble, the bewildering care that weighs us down who live and earn our bread, . These idle verses have no power to bear; So let me sing of names remembered, Because they, living not, can ne'er be dead, Or long time take their memory quite away, from us poor singers of an empty day. Dreamer of dreams, born out of my due time, Why should 1 strive to set the crooked straight? Let it suffice me that my murmuring rhyme Beats with a light wing against the ivory gate, Telling a tale not too importunate To those who in the sleepy region stay, Lulled by the singer of an empty day. So with this Earthly Paradise it is. If ye will read aright, and pardon me, Who strive to build a shadowy isle of bliss Midmost the beating of the steely sea, Where tossed about all hearts of men must be; Whose ravening monsters mighty men must slay, Not the poor singer of an empty day." William Morris, The Earthly Paradise x Chapter 1 Introduction "To construct a model—as Mr. Palomar was aware—you have to start with something; that is, yon have to have principles, from which, by deduction, you develop your own line of reasoning. These principles—also known as axioms or postulates—are not something you select; you have them already, because if you did not have them, you coidd not even begin thinking. " Italo Calvino — Mr. 1.1 Palomar Introduction and Statement of Principal Results One of the most fundamental recent discoveries regarding the Artin braid groups B is that they are right-orderable [Deh95], [FGR 98]. A group G is right-orderable if there exists a strict total ordering < of its elements which is right-invariant: g < h implies gk < hk for all g, h, k e G. If in addition g < h implies kg < kh, the group is said to be orderable, or for emphasis, bi-orderable. As observed by Neuwirth [Neu74], B is not bi-orderable if n > 3. By contrast, it was shown in [RZ98] that the subgroups P of pure braids are bi-orderable, but the proof is non-constructive. + n n n This thesis describes an explicit, natural, and easily computed bi-ordering of P , which is constructed from two classical ingredients: the Artin decomposition of P as a semi-direct product of free groups; and the Magnus expansion of free groups in a ring of formal power series. Accordingly, we call this the "Artin-Magnus" ordering of the pure braid groups. n n 1 Chapter 1. Introduction 2 We are grateful to L. Paris for pointing out that the fundamental group of the complement of a hyperplane arrangement of "fibre type" [FR85] has a similar semi-direct product decomposition, and our methods apply to define an explicit bi-invariant ordering for these groups also. We are able to define a fairly general class of semi-direct products involving free groups to which the Artin-Magnus ordering can be applied. Various properties of the Artin-Magnus order on the pure braid group are examined. It is natural in several senses; for example, the orderings of P for various n respect the usual inclusions. We show that pure braids which are positive in the sense of Garside [Gar69], are also positive (greater than the identity element) in the Artin-Magnus ordering. Thus our ordering extends the partial order on B defined by Garside, restricted to P . We show the set of Garside-positive elements is actually well-ordered in the Artin-Magnus ordering. n n n It is noted in [FGR 98] that the Dehornoy right-ordering of B , restricted to P , is not a bi-ordering. However, it has certain properties in common with the Artin-Magnus ordering: the orderings agree on the simplest nontrivial pure braids, of, squares of the usual generators of B . In Section 3.3, we compare the Artin-Magnus ordering with others in the literature. We give a proof that the Artin-Magnus ordering of P does not extend to any right-invariant (or left-invariant) ordering of B , if n > 3. The other aspect of this thesis is computational: we present algorithms for deciding the relative order, or equivalently, the positivity, of elements in B under the Dehornoy ordering, and elements of P under the Artin-Magnus ordering. + n n n n n n n 1.2 Outline Chapter 2 introduces the subject, establishing notation and gathering basic definitions and fundamental results concerning braids and group orderings. In Chapter 3 we construct an explicit, easily computable, invariant order on the n-strand pure braid group. This ordering employs two key ingredients from the classical theory of braids and combinatorial group theory; in recognition of this foundation we call it the Artin-Magnus order. Most of Chapter 3 is the result of joint work with Dale Rolfsen, which is Chapter 1. Introduction 3 being submitted for publication. Basic properties of the Artin-Magnus ordering are established, and examples are presented to illustrate that it is in many senses extremely natural. We compare the ordering with existing orderings on the pure braid group, such as the restriction of the Dehornoy ordering on the full braid groups. In Section 3.4 we present results which extend the ideas involved in the construction of the Artin-Magnus ordering to a more general context, yielding orderings on other classes of groups of geometric and algebraic interest. The theme of Chapter 4 is algorithms for computing the Dehornoy and Artin-Magnus orderings for braids. Algorithms for both orderings manipulate combinatorial representations via operations which are topologically induced. A J A V A language implementation of the algorithms, in the form of a package of routines callable from J A V A programs, is discussed. Finally, in Chapter 5, we summarize the work presented in this thesis, and report on future directions which this research might follow. The appendices present a glossary of basic terminology, an index, and a printed guide to an Application Programming Interface^ (API) specification for the computer code which is discussed in this thesis. This API is intended to be helpful for the programmer wishing to use the implementations of the algorithms presented in Chapter 4. The computer code discussed in this work, and accompanying hypertext documentation, are available on the World Wide Web at the following URL: f i t t p : / / S u n S I T E . U B C . C A / D j u n / t h e s i s /Java/. 1.3 Notation The symbol "•" will denote the end of a proof. Definitions will generally use the notation ":=". The following abbreviations are used: w.l.o.g. = "without loss of generality"; iff = "if-and-only-if"; resp. = "respectively." A brief table of notation appears on page 103; a full index on page 105. In addition, for the convenience of the reader, certain terms and concepts are defined in a glossary (Appendix B), if they are peripheral to the discussion. The first occurrence of such terms is indicated by a raised "t". A text italic font is used to emphasize words or phrases, to indicate a term is being defined, and to set off statements of theorems, lemmas, and the like. Chapter 1. Introduction 4 A typewriter font is used to set off fragments of computer code, and to display user input to a computer program in examples. A bold typewriter font is used to display computer output in examples. The trademark " J A V A " is registered by Sun Microsystems, Inc. "Adobe" and "PostScript" are registered trademarks of Adobe Systems, Incorporated. "T^X" is a registered trademark of the American Mathematical Society. Other trademarks are property of their respective owners. Chapter 2 Braids and Orderings "Te irds de noche, Maria, deeste canton portenato, con la trenza destrenzada y el sueno desabrochado. (You'll go at night, Maria, from this Buenos Aires canton, with all your braids unbraided, and your dreams undone.) " H o r a c i o Ferrer — Maria de Buenos Aires 2.1 Braids Braids made their debut as objects of serious mathematical consideration in Emil Artin's ground-breaking paper [Art25], although it appears that the idea was implicit in the work of other mathematicians prior to this. Since Artin's introduction, braids have taken up an important role, not only in topology, but also in analysis, geometry, algebra, and theoretical physics. 2.1.1 Definition There are several essentially equivalent ways of looking at braids. Each point of view will be introduced as required. We shall begin by following Artin's example, defining braids geometrically as isotopy classes of disjoint, embedded strands in 3-space, monotone in a given direction. To make this all precise, we need to fix a few definitions, which we will 5 Chapter 2. Braids and Orderings 6 construct so as to yield "horizontal" braid diagrams, oriented from left to right, with the braid index increasing as we move up the page. Definition 2.1 Let E — R C M be the (y, z)-coordinate plane in Euclidean 3space; let E' be E translated one unit in the x direction. Let Q c E be marked points on the z-axis at 0,1,... ,n — I and let Q' be the corresponding set in E'. Consider disjoint embedded arcs on: [0,1] — > M (i = 1 , . . . , n), of the form 2 3 n n 3 a (t) = (t,af\t),af (t)) ) i with a.i meeting some point of Q (respectively Q' ) transversely at t = 0 (respectively t = 1) and so that every vertical plane {x = t\ 0<t<l} between E and E' meets the transversely in exactly n points. An n-braid is an isotopy class of such embedded arcs, where the isotopies are isotopies ofR rel E and E'. n n 3 2.1.2 Group structure Given two braids a and r , it is natural to form a new braid by concatenation, that is, "appending r to a", as indicated, for example, in fig. 2.1. To make the result of such an operation a braid according to our definition, one must take representatives, scale each by half and paste together the result, as made precise in the following operation. + (l/2,0 0)) ffOT:=vj(<7)U(^(r) I where cp is the homeomorphism of M given by x t-¥ x/2. Finally one takes the isotopy class of the result. 3 Figure 2.1: Composition of two braids Definition 2.2 Composition as defined above gives a group structure on the set of n-strand braids, which we will denote by B and refer to as the braid group on n Chapter 2. Braids and Orderings 7 n-strands. The identity in B is the n-braid whose strands pass straight through n with no crossings. The inverse of an n-braid 8 is obtained by reflecting the braid in the plane E'; regarding 8 as an n-tuple of arcs /%(£), i = 1,... , n, the inverse 8~ is the "time-reversed" collection of paths 8i {t)' i — I,-- - ,n, with 8~ (t) — l l l {t,^{l-t),pf\l-t)). Given a braid, a suitable choice of representative will give an orthogonal projection onto the (x, z)-coordinate plane which contains at worst transverse double points. We shall use the standard convention of drawing the "lower" (with respect to the y-coordinate) arc at an intersection with a small break to indicate that the "upper" arc passes above it. In such a diagram, we shall label the strands from 1 to n, with increasing z-coordinate of their left endpoint, as shown in Fig. 2.2. We must make a choice of convention as to which of the two possible crossings we take as positive: we choose the so-called i-th elementary braid Ci to be the braid whose only crossing takes the (i + l)-st strand over the i-th; this corresponds to a right-hand half-twist. ] Figure 2.2: The i-th elementary braid Oi Artin showed in [Art25] that B admits a presentation with generators n u i , . . . , < 7 _ i , and relations n OiOj = cjjGi if \i — j\ > 1, = Oi \OiOi \ + 1 < i, j < n — 1 i = l , . . . , n —2 + It is clear that the group B is isomorphic with the integers Z . 2 (2.1) (2.2) Chapter 2. Braids and Orderings 8 Definition 2.3 Corresponding to any braid pis a permutation TT{0) e S , recording how the strings connect the endpoints. In particular, a braid whose permutation is the identity is called a pure braid. The map IT: B -> S is easily seen to be a group homomorphism. Hence the set of pure braids forms a normal subgroup P of index n! in B , which fits into a short exact sequence n n n n n 1 P -> B -> S -> 1. n n n P is called the pure braid group on n-strands. n 2.1.3 Automorphisms of Free Groups Let F := (xi, • • • , x ) be the rank n free group generated by x\,..., x . An object of great interest in combinatorial group theory is Aut(F ), the automorphism group of the free group. Many interesting groups appear naturally as subgroups of Aut(F„), and among these is the n-strand braid group B . The following construction, due to Artin [Art25], exhibits B as a group of automorphisms of F , represented as the fundamental group of a punctured disk. n n n n n n n Let D := D — Q denote the disk with n punctures, denoted by Q := {pi,... ,p } and arranged in order along a straight line in D . Then F can be identified with TTI (D ). To be precise, let x\,..., x be loops in D representing generators of TT\ (D„). We will orient them in the clockwise sense, as shown in Figure 2.3. 2 n n n 2 n n n n n An n-braid can be regarded as the graph of a motion of n distinct points in the disk, beginning and ending in Q ; this motion extends to a self-homeomorphism of B , unique up to an isotopy which fixes the punctures and boundary of D . This homeomorphism in turn induces an automorphism of the fundamental group, i.e., an automorphism of F . By our previous choices, the elementary braid CTJ corresponds to the righthand half-twist interchanging pi and pi+i and fixed off of a small neighborhood of the interval between these points. In terms of generators, the corresponding automorphism is given by n n 2 n Xi Xj i ^ XiXi^-\Xi t - > Xj , (j ^ i,i + 1.) Chapter 2. Braids and Orderings 9 Figure 2.3: The punctured disk D and generators for F n n This action is illustrated in Figure 2.4, where the arcs represent loops which are small regular neighbourhoods of the arcs, given a clockwise orientation. Figure 2.4: The action of o\ on 7r (lD)„) 1 Thus the automorphism corresponding to a braid 8 will take the generator Xi to the word WiX^Wi' , where ir is the permutation corresponding to 3, and Wi also depends on 3. This correspondence determines an embedding of B into Aut(jF ). We point out for later reference that a pure braid corresponds to an automorphism which is a "local conjugation," in which each generator is sent to some conjugate of itself. 1 n n Further details may be found, for example, in [Bir75], or in [BZ89]. Chapter 2. Braids and Orderings 10 2.1.4 Artin Combing and the Structure of Pure Braid Groups The "natural" inclusion i: P _ «-» p adds an n-th strand to an (n - l)-strand pure braid 8, as illustrated in Figure 2.5. n x n — n-l n-l P P Figure 2.5: The natural inclusion i: P -i •->• P n n There is also a retraction / : P —> P _ i defined by "deleting the n-th strand". The kernel of / consists of all braids for which the first n — 1 strands pass straight through and the n-th strand weaves among the remaining ones; it is thus isomorphic with 7Ti (IR \ (n — 1) points), a free group of rank n — 1. Hence we have a representation of F _ i as a normal subgroup of P . We may write B e P as B = (i of(8))(i o f(8)~ 8)-Note that /(/?) € P _ i while iof((3)~ 8 6 F -i- When context allows, we shall drop explicit mention of the inclusion map i and write, for example, 8 = f{ft){f{ft)~ 8). n n 2 n n l n n l n l i+ 1 Figure 2.6: The generator x jti €F =(x ,x t u i y i ) C P. n For any i 6 { l , . . . , n - l } , we may thus regard the subgroup Fi C Pi C P as consisting of those braids whose strands go straight across, except the strand of index % + 1, which may have crossings only with strings of lower index. We shall call elements of Fi free braids. The free generator Xj^ of Fi is illustrated in Figure 2.6. In terms of the Artin generators, n Xj,i — O (7i-\ • • • <Jj i<7j aj l~ • • • 2 l + l + Gi^l~ Gi~ . l X Chapter 2. Braids and Orderings 11 When the context of Ft is understood, we will drop the second subscript on the generators and write simply Fj = (x\,•..., x^. Theorem 2.4 (Artin [Art47]) The map 3 ^ (f{3),f(3)~ 3) l is an isomorphism P = P _ t< F _ i , where the action ip: P -\ -> Aut(F„_i) associated ivith the semi-direct product is given by local conjugation, and therefore induces the identity on the abelianization Hi(F -\) := F _ i / [ F _ i , F -\]. n n 1 n v n n n n n Proof. The subgroups P -i C P and F _ i < P , satisfy P -i D F _ i = 1. Hence P _ i F _ i forms a subgroup of P , and every element of this subgroup has a unique expression cry with a € P -i and 7 € F _ i (see [DF91], page 176). Every element 3 € P may be written (3 = f(3) o f(B)~ 3)), hence the subgroup P _ i F _ i is all of P . The statement about the action ip follows from the fact pointed out in 2.1.3, that the Artin action of B on Aut(F„) is by local conjugation. • n n n n n n n n n n n l n n n n n Figure 2.7: A pure braid, before and after combing. The procedure of isolating all interactions of the last strand with the other strands of a pure braid was called by Artin "combing the braid". Figure 2.7 shows an example of combing a pure braid. We define the full Artin combing of P to be the iterated semi-direct product decomposition P = (• • • ( F i K F ) K F3) x • • • x F _i). By employing the convention that a chain of semi-direct products associates in left-to-right order, we can dispense with the parentheses and write simply P = F\ x F2 x 1 n n 2 n n 1 A r t i n n o t e d [ A r t 4 7 ] that a n y a t t e m p t t o c a r r y o u t this p r o c e d u r e e x p e r i m e n t a l l y o n a l i v i n g p e r s o n w o u l d " o n l y l e a d t o v i o l e n t protests a n d d i s c r i m i n a t i o n a g a i n s t m a t h ematics." Chapter 2. Braids and Orderings 12 This provides a unique factorization of a pure braid 8 as a product 8 = 8182 • •. 8 -i in which the pure braid fa belongs to Fj. Thus we introduce coordinates in the semi-direct product: n 8=(8l,82,--.,Pn-l), where each fa is expressed in terms of the free generators x\,..., x\ of Fj. 2.2 Ordered Groups The theory of orderable groups is over a century old. A classical theorem of Holder [H6101] asserts that an Archimedean^ orderable group is isomorphic (algebraically and in the ordering sense) with a subgroup of the additive reals, and therefore Abelian. Orderability is a strong property. For example, if G is a right-orderable group, then G is torsion-free. (Suppose for a contradiction that g = 1, where g 1 and k > 0. We may assume w.l.o.g. that g > 1. By invariance, we have g > g > 1, and inductively 1 = g > • • • > g > 1. But then 1 > 1, which is a contradiction since the ordering is strict.) Furthermore, if G is right-orderable and R is an integral domain^, then the group ringt RG has no zero-divisors^ and no units^, other than the "trivial units" of the form rg where r is a unit in R and g £ G. A famous conjecture (see [Pas77]) attributed to Kaplansky proposes that if G is a torsion-free group, then the group ring ZG is an integral domain having no non-trivial units. k 2 k Free groups are bi-orderable. This non-trivial but well-known result has an interesting history: it seems to have been first noted in print by G. Birkhoff in a Mathematical Reviews entry on a paper of Everett and Ulam ([EU45]). It also appears in [Neu49] and also in [Iwa48] — the first article of the first volume of the Journal of the Mathematical Society of Japan published after the 2nd World War. Each of these proofs seems to rely on the Magnus-Witt theorem, characterizing the lower central series of the free group F . n More generally, Vinogradov [Vin49] proved that bi-orderability is preserved under free products. Good references on ordered groups are [MR77], or [Pas77], for example. Chapter 2. Braids and Orderings 13 2.2.1 Definitions and Examples Recall from Section 1.1 that a group G is said to be right-orderable if there exists a strict total ordering < of its elements which is right-invariant: g < h implies gk < hk for all g,h,k € G. If in addition g < h implies kg < kh, G is said to be an orderable group, or for emphasis, bi-orderable. A group G is right-orderable if, and only if, there exists a positive cone V C G with the following properties: (1) Closure: V • V c V, i.e., V is multiplicatively closed, and (2) Partition: G \ {1} =VUF' where V~ = {p' 1 l 1 \peP} For if G is a right orderable group, take V = {g | 1 < g}. Conversely, if such a subset V exists, we may define a right order on G by g < h hg~ G V. (Note: the criterion g~ h G V would give a left-invariant ordering; a group is right-orderable if and only if it is left-orderable, but the orderings may differ.) G is bi-orderable if and only if properties (1) and (2) above hold, and in addition, we have: l l (3) Normality: for all g EG, gVg' CV 1 Clearly, subgroups of right-orderable (resp. bi-orderable) groups are rightorderable (resp. bi-orderable) groups. 2.2.2 Ordering Semi-direct Products Right orderability is preserved under group extensions. That is, if G and H are right orderable groups fitting into a short exact sequence of groups 1 —>• G —> K -» H -> 1, then K is right-orderable also: compare two elements g\, g € K by comparing their images in H; if the two map to the same element, they differ by an element of G, hence may be compared by pulling back to G. We consider now the situation for bi-orderability: the first observation is that if G and H are bi-orderable, then the direct product G x H is also biorderable: simply take the lexicographic ordering: 2 (g, h) < (g', h') <=> (g < g') or {g = g' and h < G H ti). In contrast, consider the following common extension. Suppose G acts on H, the action being denoted by h (->• h . In this situation, we can define the 9 Chapter 2. Braids and Orderings 14 semi-direct product G x H with underlying set G x H, and product defined by (g,h)(g',h') := [gg'Mh'). The following example shows that semi-direct products of bi-orderable groups are not necessarily bi-orderable: Example 2.5 The Klein bottle group (x,y I yxy' 1 = x~ ) l is not bi-orderable, although it is a semi-direct product of two infinite-cyclic groups (which are, of course, bi-orderable). The reason this group cannot be bi-orderable is that x and x~ are conjugate, and so one is positive if and only if the other one is, a contradiction. l We remark here that Neuwirth [Neu74] observed that this example implies that the braid groups B ,n > 3 are not bi-orderable, since the Klein bottle group is a subgroup of the braid group B3, taking x — oio^ and n 1 y = Oi020\. The Klein bottle group fails to be bi-orderable because the group action does not preserve the order on the second factor. The following lemma shows that this is the only way in which lexicographic order on the factors can fail to yield a bi-ordering on the semi-direct product. Lemma 2.6 Let G and H be bi-orderable groups. Then the lexicographic order on G x H is a bi-ordering if and only if the action of G on H preserves the order on H (equivalently, if{V ) CV 9 H H for all g G G.) Proof. Let G and H be bi-ordered groups. Suppose that G acts on H such that {V y C V for all g € G. Let V := {(g, h) \ g € V or {g = 1 and h G V )Y, i.e., V is the lexicographically positive cone. First we show closure: V • V C V. Let (g, h) and (g , hi) e V. In the semidirect product {gg',h 'hi), gg' £ VG because G is orderable. Also h ' e VH since VH is by hypothesis closed under the action of G; since H is also orderable, hP'hl G V H H H G 1 9 9 H Next, we show partition: (G x H) \ {(1,1)} = V]\V~ . Suppose {g,h) ^ (1,1) £ V. Then either g £ VG or g = 1 and h £ VH- In the first case, g ^ VG implies that G VG, since G is an orderable group. So (g, h)~ = L l Chapter 2. Braids and Orderings 15 [g' , [h ' )' ) is in V. Otherwise g = 1 and h £ V , so h" G V , which means that (1, h)~ = (1, h~ ) is in V. Finally, we show normality: (g, h)V(g, h)~ C V. Let (g , h') G V. Consider the conjugate 1 9 1 1 1 H l H l l (g,h) • (g',ti) • {g,hY l 1 = (gg',h 'ti) • (<r\ 9 = (h' ) ' ) 1 9 1 (gg'g-\{h 'tih- ) -). 9 1 9 If g' > 1, then since G is orderable, normality implies that gg'g~ G P G / conjugate above is in V. l s o the Otherwise g' = 1, so = 1, and (h 'h'h- ) ' = {hh'h' ) ' . Since (hh'h- ) G P f f by virtue of H being bi-ordered, {hh'h,- ) ' G P # by assumption that the G-action on H respects the positive cone on H. Hence the conjugate is again in V. The "only if" part of the statement follows from the observation that H is normal in G tx H, and the action of G on H is by conjugation, hence must preserve order. • 9 1 9 1 1 1 1 9 1 9 1 2.3 The Magnus Ordering of the Free Group F n Let F = (x\, • • • , x ) be the free group of rank n. Following Magnus (see for example [MKS76]), we produce a representation of F into a ring of power series, via which we can define a bi-ordering of F . This ordering appears to have been considered by Magnus as well as others: see [MKS76], Chapter 5, Exercise 5.6.10, and also [Ber90]. n n n n Let X(n) denote the ordered set {X ,X , ...,X ), and let Z[[X(n)]] be the ring of formal power series in the non-commuting variables X\,... ,X . Let //: F —t Z[[X(n)]] be the Magnus map, defined on generators by 1 2 n n n J M: Xi \ xr 1 + Xi ^ 1 - X + Xi - X i H+ 1 2 l 3 + --- An element of Z[[X(n)]] has the form c 0 + cxW^Xr, ...X )+ n c W (X ,... 2 2 l X) n + ••• , Chapter 2. Braids and Orderings 16 where each coefficient Ci is an integer and the monomials Wi(Xi,..., X ) are strings of powers of the generators. Each term aWi(Xi, • • •, X ) of a such a formal series has a total degree, simply the sum of the exponents of the monomial Wi, and we use the usual notation O(d) to denote the sum of all terms of (total) degree at least d. It is proven in [MKS76] that the subset Q = {1 + 0(1)} of power series with constant term = 1 is a subgroup of Z[[X(n)]]. The inverse of an element 1 + W is simply 1 - W + W - • • •, even when W € 0(1) is itself an infinite series. Magnus goes on to show [MKS76] that the map ti is a representation of F into Q: n n 2 n Theorem 2.7 (Magnus) The map p,: F —>• Q is injective. n We shall use the Magnus map p implicitly to identify F with its image, writing x\ = 1 + X\, etc. n Definition 2.8 Declare X\ -< X 2 -< • • • -< X . If v, w are two distinct series in n Z[[X(n)]], consider the smallest total degree at which they differ, and sort the terms of that degree in lexicographic order. In that order, compare the coefficients of the first term at which V and W differ. Declare V < W precisely when the coefficient of that term in V is smaller than the corresponding coefficient in W. We call this the Magnus ordering on Z[[X(n)]]. Example 2.9 Under the Magnus map, we have x\ = 1 + X\ and x = 1 + X2The images differ in that xi has coefficient 1 at term X\ while x has coefficient 0 in this term. Hence x\ > xi- Similarly, x\ > X2 > • • • > x > 1. 2 2 n Theorem 2.10 The Magnus order on the ring Z[[X(n)]] induces a bi-ordering on Q and hence on F . n Proof. We check that V = {w € G \ w > 1} satisfies V • V C V, that G \ {1} = V LI V~ , and zVz~ x l C V for all z€Q. We shall write series in ascending order. Hence we have w = 1 + cW -i where W = W(X\,..., X ) is the lexicographically least word, among the terms of w of minimal total degree > 0. By definition of the Magnus order, the positive cone V is the set of such w with c > 0. n Chapter 2. Braids and Orderings 17 The first non-constant term of the product of two series v = 1 + bV + • •• and w = 1 + cW + • • • is cW or bV or (6 + c)W, according as W -< V, V ~< W, lexicographically, or V = W. Hence this term has a positive coefficient if b, c > 0; in other words, V • V C V. To see that V partitions Q, suppose that an element w = 1 + cW -j of Q is not positive. Observe that w' contains a term —cW as the first non-constant term. Because c < 0, we have w^ 6 "P. Now let w G 7-> and compute z u i z for z = 1 + dZ + • • • E Q: 1 1 - 1 zwz~ = (I + dZ + •••)(!+ cW + •• - - dZ + •••) = I + cW + •• • l Therefore zwz~ is in V also, and we have established that V is a positive cone for a bi-ordering on Q. That it is the same as the Magnus ordering follows from Lemma 2.11. • l Lemma 2.11 If u, v E G then, in the Magnus ordering o/Z[[X(n)]] we have u < v if and only if vu~ > 1. l Proof. Write u = 1 + U and v = 1 + V where U, V E 0(1). It is clear from the definition that u < v if and only if V — U > 0. The lemma then follows from the calculation: vn' 1 = (1 + V)(l-U +U ) = 1 + V-U 2 + R, where every term of the remainder R = (V — U){—U + U — U + • • •) has degree exceeding the lowest degree term ofV — U. • 2 3 We remark here that there exist uncountably many "Magnus-type" biorderings on Q, determined by a choice of order on each set of monomials of fixed total degree. In particular, there are n\ inequivalent lexicographic Magnus orderings determined by an initial ordering on the list of variables X(n). Theorem 2.12 The Magnus ordering of F is preserved under any cp £ Aut(F ) n n which induces the identity on H\(F ) n — F /[F , n n F ]. n Proof. Consider an automorphism <p: F —>• F which induces the identity on first homology. That is to say, ip(xi)x~ is in the commutator subgroup n l n Chapter 2. Braids and Orderings 18 [F , F ]. As observed in [MKS76], the image of [F , F ] lies in the subgroup {1+0(2)} oiQ. For convenience, write x\ = <p(xi). The corresponding Magnus expansion is n n n n x'i = l + X[ - (1 + 0(2))(1 + Xi) = 1 + Xi + 0(2) and therefore X[ = Xi + 0{2). Now if w = w(xi,..., x ) is a word in the free group F , its image under if is w' = w(x[,... ,x' ). The corresponding Magnus expansion (written in ascending order) w =• 1 + c\W\ + C2W2 + ... has image w' = 1 + c\W{ + C2W2 + • • •, where n n n w;(x --. u ,X ) = n W (X[,---,X' ) J n — Wj (A'I , • • • , X ) + terms of higher degree. n It follows that the first non-constant terms of w and w' are identical, and therefore (p preserves the positive cone of F , which is equivalent to being orderpreserving. • n We observe that a closer examination of this proof shows that for endomorphisms of the group Q, something slightly more general is true: Theorem 2.13 The Magnus ordering ofQ is preserved under any cp e End(C7) such that (pp.: Xi i - > 1 + CiXi + 0(2), where Ci > 0,/or all i = 1,..., n. Chapter 3 An Explicit Bi-ordering of the Pure Braid Group "Such things induced me to untangle the chaos by introducing order where it had never been before ..." Pierre Fournier — Manuel Typographique (1764) 3.1 Construction of the Artin-Magnus Ordering Theorem 3.1 The lexicographic order on P = F\ ix F tx JF3 tx • • • tx F„_i, with terms in the free factors compared using the Magnus order, is a bi-ordering. n 2 Proof. The statement is trivially true for P . We inductively assume that the statement is true for P - i - Theorems 2.4 and 2.12 show that the Artin action of P -i on F -i respects the Magnus order on the second factor of the semi-direct product decomposition P = P -\ tx F -\. Lemma 2.6 then shows that the semi-direct product is bi-ordered under the lexicographic order, with comparisons in the factors done in their respective orders. • 2 n n n n n n We will refer to this order on P as the Artin-Magnus order. n 3.2 Properties and Examples We will begin with some examples in P4 = (F\ t< F ) tx F3. An element 0 € P4 will be written 0 = {0i,P ,0z), where each 0i e Fi. The convention for labeling generators of the Fi is explained in Figure 2.3. 2 2 19 Chapter 3. A Bi-ordering of P 20 n Example 3.2 Figure 3.1 shows the simplest non-trivial pure braids—given by the squares of the usual Artin generators. a 2 2 CT3 2 = (1,1+X ,1). ) = (l,l,l-f-X ). = (l,x ,l) = ( l , l , X 2 3 2 3 Figure 3.1: The squares of the elementary generators This shows that o > <T > 03 > 1. In general, c r ; > O i \ for every power N, illustrating that for n > 2, the Artin-Magnus ordering on P is nonArchimedean (as it must be, by Holder's theorem.) 2 2 2 2 2 N 2 + n (1,0:2 x\ x x\,l) l 2 Figure 3.2: The common braid used for hair, on the first three strings. Example 3.3 Consider the four-strand pure braid illustrated in Figure 3.2. Chapter 3. A Bi-ordering of P 21 r A p p l y i n g the Magnus expansion to the second coordinate, we have i-> x ~ xi~ X2Xi 1 l 2 (1 - X + X 2 - X 2 + XX 2 2 = 1- X X X 3 2 + • • • )(1 - X + X\ 2 x 2 X -X^ + •••){! +X ){1 2 + 0{3) Since the first non-constant term is negative, we conclude (ci c ^ ) - 1 E x a m p l e 3.4 + Xi) 3 < 1- Figure 3.3 shows the generator A of the center of P4. We shall 2 Figure 3.3: The generator A of the center of P 4 2 refer to this example in Prop. 3.12. The Artin-Magnus ordering is natural in several senses. Consider the increasing sequence Pi C P C • • • C P C • • • C Poo, 2 where the group n is the direct limit. Proposition 3.5 If m < n, the Artin-Magnus is the Artin-Magnus ordering of P . m Moreover, the retraction map f: P n 8 < 7 = » ordering of P , restricted to P , n m Therefore, this defines an ordering of P^. -> P -\ n is as order-preserving as possible: f(3) < /( ). 7 Proof. The statement is obvious if one considers the "Artin-coordinate" presentation: P m extends to P via the inclusion map by adding an appropriate n number of "identity" coordinates. The retraction map simply deletes the last coordinate. n Chapter 3. A Bi-ordering of P 22 n It will be useful to consider the linking numbers associated with a pure braid 8. Define the linking number of the i-th strand with the j-th strand, i ^ j, by lk(P) = j £ s i g n ( c ) , c where the sum is over all crossings c involving the two strings of index i and j, and sign(c) is the power, ± 1 , of the corresponding braid generator ak . Each Iky : P -> Z, 1 < i ^ j < n is additive: Iky (a/3) = Iky (a) + Iky (8). ±l n Proposition 3.6 Let 8 be a pure braid with n strands, expressed in Artin coordinates: 8 — (Pi,..., p -i). n Then the Magnus expansion Pi = 1 +.qiXi + •••+ qiXi + 0(2) in Fi C Z[[X(n)]] has linear coefficients: '/,= . 1> , ( Proof. The formula is a straightforward calculation, using two observations. First, the exponent sum of Xj — Xj i in a word w = w(x\,... ,Xi) equals the coefficient of Xj in the Magnus expansion of w. Second, for j < i, XJJ contributes +1 to \kj i i(P) = \ki ij(P) and zero to all other linking numbers. t t + + • The abelianization functor takes all the braid groups P and B , n > 2, to infinite cyclic groups. The abelianization map B -> Z can be taken to be the total exponent count of a braid when expressed in the generators This map sends P to 2Z; in this setting it can also be interpreted as twice the total linking number n n n n p^2 T lk(P). —' %j l<i<j<n The abelianization map on P is clearly not order-preserving. However, it does respect the orderings if one confines attention to the free subgroups Fi c P in the Artin decomposition n P n = Fi K F K F K 2 3 • • • ix F _ i . n Chapter 3. A Bi-ordering of P 23 r The abelianization of Fi is the free abelian group of rank i, which we may identify with j-tuples of integers, 12, and order lexicographically. In this setting the abelianization may be realized as the map abj: Fi —t Z \ given by abi(w) = (qi,..., qi) where qj is the exponent sum of Xj in w. We shall say that a mapping x —> x' of ordered sets is order-respecting if x < y implies ' < y'• Then we see, from the definition of the Magnus ordering of Fi that abi is order respecting. The next proposition follows directly from the above discussion. x Proposition 3.7 With the Artin-Magnus ordering on P and lexicographic ordern ing on the product of infinite cyclic groups, the product of abelianization maps P = Fi K F x • • • x F _ ! n 2 a b l X , , , x a b n - ) Z x Z x • • •x Z"1 2 1 as a mapping, is order-respecting. Moreover, it is compatible with the retraction f: P —> P -i n n in that the following diagram commutes: Fn abi x---xab _i n > Z X Z 2 X • • • X f Pn-1 Z~ n l projection abi x---xab _2 n > Z x Z x • • •x 2 Z ~ n 2 • 3.2.1 Garside Positive Braids In his celebrated solution of the conjugacy problem, Garside [Gar69] introduced the so-called "positive" braids, i.e., nontrivial braids which have an expression in the generators Ui without any negative exponents. We will call such braids Garside positive. We shall denote by the semigroup of Garside positive braids together with the identity. Theorem 3.8 If a braid in P n is Garside positive, then it is also positive in the Artin- Magnus ordering. Proof. The statement is clear for elements of P . Inductively, suppose that it is true for P -i- Let B E P be Garside positive, and consider the braid f(B) £ 2 n n Chapter 3. A Bi-ordering of P 24 n P -\. Note that /(/?) is either Garside positive (case (1)) or has no crossings (case (2)). In case (1), applying induction, /(/?) is Artin-Magnus positive, hence B is positive, by definition of the lexicographic order of P _ i tx F _ i . In case (2), B is an element of F -\. We may assume the first n — 1 strings are straight and read the expression for B in terms of the free generators of F - i from the places where the n string passes under the first n — 1 strings. By our convention (choice of x^j), and Garside positivity, B is therefore a strictly positive word in x\,..., x . It follows that its Magnus expansion has positive leading coefficient (occurring at a linear term). Therefore B > 1. • n n n n n th n Recall that an ordered set is said to be. well-ordered if every non-empty subset has a least element. The following result is similar in spirit to [Lav96] and [Bur97]. Theorem 3.9 The set of Garside positive pure n-braids is well-ordered by the ArtinMagnus ordering. Proof. The statement is clear for n = 2. Now suppose that n > 2 and the theorem holds for n — 1. Consider a non-empty set 5 C P of Garside positive braids. We need to show S has a least element. The set /(S) = {/(/?) € P -i \ B € S}, being a subset of P -i n B*_ has a least element; call it cvo. Let n n n v So = {7 € S I 7(7) = a } ; 0 clearly if there is a least element of So it is also the least element of S. Note that the coordinates of 7 6 So in P„_i K P _ i are 7 = (ao, ao 7)- We now appeal to Lemma 3.10 to find a 70 € So whose last coordinate ao 7o is minimal. Then 70 is the least element of S. • _1 n _1 Lemma 3.10 Consider a subset T c F _ i C P of the form n T = {ao-'j n I 7 e So}, w/zere So is some set of Garside positive pure n-braids and ao is a fixed pure braid in Pn-i C P . Then T has a least element in the Magnus ordering of F _\. n n Chapter 3. A Bi-ordering of P, 25 Proof. The condition a o 7 G F -\ is equivalent to the equation 7(7) = arj. Since ao is in P -\, and 7 is Garside positive, we have lkj (cvo 7) = lkj (7) > 0. This implies that the coefficients ( g i , . . . , q -\) of the linear terms in the Magnus expansion of all elements of T are positive, hence there is a lexicographically minimal one, say (qi,..., q -ij- Let _1 n _1 n ]n )N n n T' = {T€T\T = 1 + Q i X i + • • • g _ i A V i + 0(2)}. n Then T' is nonempty, and its elements are < other elements of T. We now claim that T" is finite. It follows that T" has a least element, which is also the least element of T. To verify the claim, observe that the exponent sum (as a word in x\,..., x _i) of every element of T' is q\ + • • • + q -i- Each Xi has exponent sum +2 when expanded in the braid generatorsCTJ.The oexponent sum is an invariant of braids, and we use it to conclude that for every a o 7 G T", the length of 7 is exactly 2 VJj q% minus the exponent sum of an. There are only finitely many distinct 7 satisfying this. • n n _1 3.3 Comparison with other orderings We compare the Artin-Magnus ordering <AM on P with several other orderings on the braid groups appearing in the literature. n 3.3.1 The Garside partial order Garside [Gar69] defined a partial order -< on the semigroup by a -< 6 for a, 3 G £ + , if there exists a 7 G B+ such that 0 7 = 3. Thurston [ECH+92] showed that this in fact defines a lattice order on the set of non-repeating braids D = {a G £+ I a < A}. Define P+ to be 5+ n P n Proposition 3.11 The Artin-Magnus order on P extends the Garside partial order on P+. n Proof. This follows immediately from Theorem 3.8. • Chapter 3. A Bi-ordering of P 26 n 3.3.2 The partial order of Elrifai and Morton In [EM94], Elrifai and Morton define a partial order on B , as follows: for a , (3 £ B , write a <EM 0 when 0 = 7 1 0 7 2 , for some 7 1 , 7 2 £ J5+. Then 1 <EM os if and only if a e B+. Furthermore, taking A = A„ £ B to be the "half-twist" braid, defined inductively by A = o\, A = A _icr„_i •••o\, they show that in their partial order each generator Oi satisfies n n n 2 1 <EM n A. 0~i <EM n (3.1) We remark that 1 <EM &i <EM A holds also for each generatorCTJ,since A = 7i<7j = a j 7 2 , for some 7 1 , 7 2 £ B+. Hence A = 7 I C T J 7 2 . This is consistent with the Artin-Magnus order on P : 2 2 2 2 n Proposition 3.12 For each generator <TJ £ B , n 1 <AM (Ti 2 <AM A . 2 We have equality in the second inequality only when i — 1, n = 2. Proof. The inequalities follow immediately from Example 3.4. • However, the following example shows that the Artin-Magnus order on P does not extend the partial order defined by Elrifai and Morton. Let a — o\-02~ This has Artin-combing (xi,X2~ ), hence is positive in the ArtinMagnus ordering. Taking 7 1 = 0-102 and 7 2 = C ^ C T I , d defining 0 — 7 1 0 7 2 , we have 0 <AM L so in particular, 0 < a in the Artin-Magnus order. We note that 7 1 C V 7 1 is also negative in the Artin-Magnus ordering — conjugation by non-pure braids is not order-preserving. n 2 1 a n _ 1 3.3.3 The Dehornoy ordering In 1974, Neuwirth [Neu74] produced an example of a 3-braid which is conjugate to its inverse, showing that the braid group B is not bi-orderable for n > 3 (cf. Example 2.5.) The existence of a one-sided invariant ordering on B remained open until 1995, when Dehornoy [Deh95] constructed a leftinvariant ordering on B . n n n Chapter 3. A Bi-ordering of P, 27 The Dehornoy ordering on B may be defined in terms of the generators n <Ti, • • • , c r _ i as follows: A braid 8 is in the positive cone if and only if there is, for some i G {1,..., n — 1}, an expression n 8 = wiOiW20-i • • • w -\OiW k (3.2) k in which each Wj is a word in er^_\, • • • ,On-\e r words, the generator with the lowest subscript appears with only positive exponent. Then we define a right-ordering by a < 7 iff 7 a is in the positive cone. (Actually Dehornoy chose his ordering to be left-invariant by using the criterion O J 7 positive, but the choice is arbitrary and right-invariance seems to dominate the literature on ordered groups.) m o m - 1 _1 Ferm et al. give a more geometric view of the same ordering in [FGR 98], where it is noted that Dehornoy ordering, restricted to P is not bi-invariant. However, there are similarities between the Dehornoy and Artin-Magnus orderings. In both orderings we have + n <J\ » cr > CT » • • • > 1, 2 2 3 2 where the notation a 3> 8 means that a is greater than all powers of 8. Another similarity is that the Dehornoy ordering is also a well-ordering when applied to Garside positive braids (see [Lav96] and [Bur97]). On the other hand, the pure braid ( C T I C ^ ) is clearly Dehornoy positive, whereas we saw that it is negative in the Artin-Magnus ordering. Of course, its inverse is Dehornoy negative and Artin-Magnus positive. We wish to thank R. Fenn for pointing out the following proposition. It shows that the Dehornoy ordering is fundamentally different from the ArtinMagnus ordering of P . - 1 3 n Theorem 3.13 In the Dehornoy ordering, B has a least positive element, namely o -\. Similarly, c r _ i is the greatest element which is < 1 in B . In P , o -\ is the least Dehornoy positive, and c r _ i is the greatest element which is < 1 in the n 2 - 1 n n n n n - 2 n Dehornoy ordering. Proof. If a braid has the form of Equation (3.2), call it i-positive, so that 8 G B is Dehornoy-positive if and only if it is i-positive for some i = 1,... ,n — 1. To prove the first statement, note that a -\ is (n — l)-positive. Suppose that n n Chapter 3. A Bi-ordering of P 28 r there is a 0 € B with 1 < 8 < c -\- Then / ? c r _ i < 1 by right-invariance. Now 8 is i-positive for some i. If i < n — 1 we conclude 0 a - i ~ is also zpositive, contradicting 0u ^\~ < 1. On the other hand, if i = n — I, 0 must be a positive power of c r _ i , contradicting /? < c r _ i . This establishes the first statement. The other parts follow similarly. • n _ 1 n n l n 1 n n n Corollary 3.14 The Dehornoy ordering of B is discrete: every element 0 has a unique successor, a -\0, and predecessor, o -\~ 0. Similarly, in the Dehornoy ordering restricted to P , a pure braid 0 is the only element of P strictly between CT„-I /? ando - p. n l n n n n 2 -2 n X Theorem 3.15 For n > 3, the Artin-Magnus ordering of P is order-dense: given any two pure n-braids a < 7, there exist (infinitely many) pure braids 0 with a < n 0<1- Proof. By invariance, we may assume a = 1. In the free group F -\ = {x\,..., x -i), consider the sequence of commutators {CJ} defined recursively by n n c i = xix xi x \ l 2 2 Ck = x\c -\X\ k Ck-i 1 : . A simple calculation shows that their Magnus expansions are, in ascending order: c = 1+ XX - kX^XzXx k k x 2 + ••• . It follows that each > 1 in the Magnus order of F _ i , but that —> 1 in the sense that if 1 < w G F -i, then 1 < < w for sufficiently large k; just take k bigger than the degree of the first nonzero non-constant term of the Magnus expansion of w. Now, in P , consider the sequence of braids {0(k)} with Artin coordinates n n n 0(k) = (l,...,l,c ). fc It is clear that given any 7 > 1 in P , we have 1 < 0(k) < 7 for all sufficiently large k. • n Since for n > 3, P with the Artin-Magnus ordering is a countable totally ordered set, dense and with no greatest or least element, it is orderisomorphic with the rational numbers, by a classical result. Of course this order-isomorphism cannot be an algebraic isomorphism, as P is non-abelian. n n Chapter 3. A Bi-ordering of P 29 r We note that for or PQQ the Dehornoy ordering is no longer discrete, but is (like the Artin-Magnus ordering) order-dense. Theorem 3.16 For n > 3, the Artin-Magnus ordering on P does not extend to any N right-ordering on B . It also does not extend to a left-invariant ordering on B . n n Proof. We may assume that n = 3. It has already been shown that ( c r i o ^ ) < 1. A similar calculation shows that (<TI <72) < 1. If the ordering extends to a right- (or left-) invariant ordering of B$, we must have o-ia " < 1 and - 1 -1 3 3 x 2 < 1. Ol" 02 1 Assuming right invariance we conclude 0~\0~2 c i c r 2 < 0~\ 02 < 1) 1 r X _ 1 which would imply (CTIO^VI ^) < 1. But a direct calculation shows -1 {a a ~ cr - o f l l 2 l l 2 3 = ( l , ^ ^ ^ ^ . ^ ) = (l,l + X i A - r - - - - ) > 1, - 1 - 1 - 1 2 r 2 a contradiction showing no right-invariant extension to B3 exists. If instead we assume left-invariance, we argue that 0\02~ O\~ G l <0\(T2~ l l 2 < 1, and reach the same contradiction. • Rhemtulla and Rolfsen have recently shown [private communication] that no right-invariant ordering of B can restrict to a bi-invariant ordering of P . n 3.4 N Generalized Artin-Magnus Orderings 3.4.1 Fibre-type hyperplane arrangements We will motivate this section by returning to the definition of the pure braid groups, giving a more homotopy-theoretic treatment. Considering braids as geometric objects which record the motion of points in the plane leads to the following definition. Define C (C) := {{pi, - • • ,p ) € I Pi Pj for i j}/ the so-called configuration space of n ordered points in C; we give C (C) the topology induced from the product topology on C" = n n n Chapter 3. A Bi-ordering of P 30 n C x • • • x C. Observe that C (C) is connected since it is obtained by removing finitely many planes {pi = pj}, of complex co-dimension 1, from C™. Fix a point * in C„(C); this corresponds to a configuration of n distinct points in C. A loop in C (C) based at * corresponds to a motion of a set of n points starting from some initial configuration, and returning to this configuration, always remaining distinct. An element of the fundamental group ni ( C (C), *) n n n is called an n-strund pure braid; we shall denote 7ri (C (C), *) by P and refer n n to it as the pure braid group on n-strands. This configuration space is the complement of a finite set of complex hyperplanes of complex dimension n — 1 in the complex vector space C™, i.e., it is an example of a hyperplane arrangement. The theory of hyperplane arrangements is a deep subject with many unsolved problems, cf. [OT92]. The fundamental group of the complement of the union of the hyperplanes is an important invariant of an arrangement. It is conjectured, but not known in general, that all such groups are torsion-free. The recent article of Luis Paris [Par98] surveys the present state of knowledge. The configuration space C (C) is an example of a special class of so-called fibre-type hyperplane arrangements, defined in [FR85]; the pure braid group P is then a special case of the groups considered in the following: n n Theorem 3.17 Let G be the fundamental group of (the complement of) a fibre-type hyperplane arrangement. Then G is bi-orderable. Proof. By definition of a fibre-type arrangement, its complement M is the top of a tower of fibrations —> Mj_i, with fibre the complex plane minus di points. The space M\ at the bottom of the tower is likewise a punctured complex plane. Therefore TTI (Mi) = 7ri (MJ_I) X F .. Moreover, according to [FR85], proposition 2.5, the action of 7ri (Mj_i) upon F is trivial on Hi(F ). It follows, in the same way as Theorem 3.1, that if each free group F is given the Magnus ordering, then the lexicographic ordering on r d di di di G =* F dl xF d2 xF d3 x• • •x is bi-invariant. F dr • The symmetric group S acts on C (C) by permuting the n coordinates; the quotient space under this (free) action is C (C), the configuration space n n n Chapter 3. A Bi-ordering of P, 31 of n unordered points in C. The fundamental group of this space is B , the full n-strand braid group. n 3.4.2 Generalized Artin-Magnus orderings A key ingredient in the proof of invariance of the Magnus order of F under the Artin action in the decomposition P — P -\ K (Theorem 3.1), and in the proof of Theorem 3.17 in Section 3.4.1, was that this action induces the identity on homology. Using this observation we can restate Theorem 3.1 in more generality. The elements of Aut(F„) which act trivially on Hi(F) form a normal subgroup called the Torelli group which we will denote by K . n n n n Theorem 3.18 Let G be an ordered group, and suppose F is a free group with the Magnus ordering. Let <p: G —> K c Aut(F ) be a homomorphism. Then the lexicographic order onG K F is a bi-ordering. n n n V Proof. This statement simply takes the broadest hypotheses under which we can apply Theorem 2.12 to show that p respects the Magnus order on F. Applying Lemma 2.6 yields the stated result. • Theorem 3.1 is the special case of this theorem where G is P -i with the Artin-Magnus order, and (p is Artin's braid action. In this case, the image of <p lies in H , the subgroup of Aut(F„) consisting of all tp such that ip(xi) is a conjugate of X{, that is, all local conjugations. Clearly H is a subgroup of the Torelli group K . n n n n Chapter 4 Algorithms for Ordering Braids "The elaborate and greedy order that he had intended to make momentarily slips his mind; he stammers; falls back on the most obvious, the most banal, the most advertised, as if the automatons of mass civilization were waiting only for this moment of uncertainty on his part in order to seize him again and have him at their mercy. " Italo Calvino — Mr. Palomar This chapter presents algorithms for computing with the Dehornoy rightordering on B and the Artin-Magnus ordering for P . Implementations of these algorithms have been made, as part of a collection of object libraries for general symbolic computations with braids. The discussion here treats the algorithms in general terms, avoiding implementation details as much as possible. n n The algorithms discussed here have been implemented in J A V A , a popular, object-orientedt programming language. The class libraries are presented as an application programming interface (API) in Appendix A. Source code and class files are available, along with demonstration programs, several of which are implemented as applets. This permits users to run them relatively easily by loading the appropriate web pages with any J A V A enabled Web-browser. The current versions may be found on the world-wide web. 1 x h t t p : //SunSITE.UBC.CA/Djun/thesis/Java/ 32 Chapter 4. Algorithms for Ordering Braids 4.1 33 The Dehornoy ordering In this section we present some algorithms for computing with the geometrically defined version of this right-ordering which appears in [FGR 98]. The basis for these algorithms is a procedure which takes as input an nbraid, given in the standard Artin generators, and computes a canonical curve diagram (defined in [FGR 98]), which records the Artin action (as described in Section 2.1.3) of the braid on an n-times punctured disk. For concreteness, we'll consider this disk to be embedded in the Euclidean plane R as the open circular disk of diameter (n + 1), centered on the x-axis at (n + l)/2, with punctures on the x-axis at 0,1,2,..., n + 1. In applying the isotopy corresponding to a braid 8 to this disk, the x-axis, which started as a straight line, becomes a (possibly) very convoluted curve in the plane. This curve nevertheless visits each of the integer points of the disk (since these are merely permuted amongst themselves by the isotopy); it does not self-intersect, and coincides with the x-axis outside of the disk. This curve will be called a "curve diagram" associated to 8. The canonical curve diagram is the curve diagram (see e.g., fig. 4.1) for which the image curve has the smallest number of components of intersection with the x-axis, consists of round semi-circles in each half-plane above and below the x-axis, and possibly some straight line segments on the x-axis between punctures, and which has the property that the image curve passes through the gaps between the punctures at equally spaced intersections. From the canonical curve diagram we may immediately read off a reduced cutting sequence (see [FGR 98]) for the braid word. This reduced cutting sequence encodes the curve diagram, by recording, as the curve is traversed from 0 to n + 1, where it branches up into the upper half-plane, where it branches down into the lower half-plane, where it remains horizontal; also recorded is the sequence of intersections of the curve with the x-axis, noting in particular when the curve meets an integer point. + + 2 + By [FGR 98], a braid is Dehornoy positive (greater than the identity in the Dehornoy ordering) if the first departure of its canonical curve diagram turns into the upper half-plane. Hence, once we have computed the canonical curve diagram for a braid 8, we can determine its positivity in time linear in the length of the representation of the canonical curve diagram. + Chapter 4. Algorithms for Ordering Braids 34 Output generated by CurveDiagram vl.O <djun ©math.ubc.ca> Figure 4.1: The canonical curve diagram for ciov, ^03 € B§ Similarly, since a < 8 iff a' 3 e V, it is straightforward, though not particularly efficient, to determine the relative order of two elements a , 8 in 1 4.1.1 Implementation The algorithm operates on a representation of a curve diagram. Initially, the diagram represents the x-axis; the diagram therefore consists of a list of curve segments which are straight line segments joining the integer points 0 < i < n + l inside the (closure of the) disk. A braid word is given as a sequence of integers, interpreted as Artin generators via the correspondence ±i >-> of . For example, the sequence 1 - 2 3 - 2 maps to o\oi~ o->,o-2~ • Given a braid word cr^cr^ • • • a\^, where e; is 1 x l 2 Chapter 4. Algorithms for Ordering Braids 35 ±1, the generators are applied in left-to-right order, that is, c^ is applied first, followed by CT| and so on. 1 2 2 The algorithm relies on the observation that the action of an elementary braid generator or its inverse is local: the diagram is unchanged outside of a small neighborhood of the integer points which are transposed by the generator. In order to compute the new curve diagram, one needs only to determine the action of the elementary braid of on the curve segments which have an endpoint at i or i + 1, or which pass through between the integer points i — 1 and i, i and i +1, or i +1 and i + 2. Hence the action ofCTJ(resp. o~ ) on a curve diagram can be taken to fix the diagram outside of a small disk neighborhood of the points i — 1, i, i + 1, i + 2. 1 l The details of the local action ofCTJare given at the end of this chapter in Tables 4.2 through 4.5. The local action for a , is similar; the tables for this case may be found with the documentation for the source code for these routines. - 1 We note here that C. Rourke and B. Wiest have shown [RW98] that mapping class groups are order-automatic, i.e., there exists a finite-state automaton which takes as input two braids (in a particular normal form which they describe) and decides which is greater in the Dehornoy ordering. This decision takes time linear in the length of the input. 4.2 The Artin-Magnus Ordering The Artin-Magnus ordering on the pure braid group P is described in Chapter 3. We will assume that we are given a pure braid 0 as a finite sequence bi, b , • • •, be of elementary braid generators. We wish to compute whether the braid is Artin-Magnus positive, i.e., whether 0 6 VAM- If we can do this, it is a simple matter to compare two pure braids a, 0 in the Artin-Magnus ordering since a <AM 0 iff ct~~ 0 € VAM- Of course, a direct comparison would be computationally cheaper. N 2 l We will compute whether a braid 0 € P is in the positive cone VAM by combing the braid, obtaining a vector of words in F , F ,..., F -\. We explicitly compute the Magnus series corresponding to these words, and compare the vector against ( 1 , 1 , . . . , 1) lexicographically, with the i-th factor being compared in the Magnus ordering in Fi. N x 2 n Chapter 4. Algorithms for Ordering Braids 36 The following code fragment recursively computes the Artin decomposition into free factors for a pure braid pb. V e c t o r A r t i n D e c o m p o s i t i o n ( b r a i d pb) { Vector result; i f ( p b . n u m S t r a n d s > 2) { braid purepart = pb.retract(1); braid freepart = (purepart.inverse()).times(pb); result = ArtinDecomposition(purepart); freepart = freeCanonicalForm(freepart); result.addElement(freepart.toFreeGenList() ) ; } e l s e i f ( p b . n u m S t r a n d s == 2) { r e s u l t = new V e c t o r ( ) ; result.addElement(freeCanonicalForm(pb).toFreeGenList()) } else { result = null; • } return result; } The basis case occurs when pb is a braid of 2-strands, which is already combed, since P = Fi = Z ; we return the free word representing pb as an element of Fi. In this case, o\ = x\. In case pb is an n-strand pure braid, with n > 2, we compute purepart which is the retraction of pb, and freepart which is /(pb) pb, where / is the retraction map. We recursively compute the vector giving the Artin decomposition for the pure factor, then append the expression for freepart as an element of F _ i . 2 2 -1 n Computing this last expression is the crux of the matter from an algorithmic point of view. Define a braid to be free if it is in the kernel of the retraction map / : P -» P -\. In the code above, freeCanonicalForm() returns a braid which is equivalent to the given free n-braid, but which has no crossings except possibly crossings involving the "free" n-th strand. We shall call this the free canonical form for the free braid. Once a braid is in free canonical form, the method toFreeGenList () can be invoked on it to return a representation as an sequence of free group generators representing the braid. n n Chapter 4. Algorithms for Ordering Braids 37 The following algorithm puts a free braid into free canonical form. b r a i d freeCanonicalForm(braid b r a i d i n t disk inbraid) r e s u l t = inbraid.freeReduce(); endindex = r e s u l t . l e n g t h ; D = result.nextElemDisk(0, while(D != n u l l ) { endindex); { r e s u l t . u n t w i s t ( D ) ; endindex D = r e s u l t . l e n g t h ; = result.nextElemDisk(0, endindex); } r e t u r n result.freeReduce(); } The algorithm depends upon finding and operating on certain "disks" in the braid. Let 3 be a pure n-braid, and let i and j be strands of 8. By a disk D in 8 bounded by strands i and j we shall mean a sub-word of 8, whose initial crossing s and final crossing e involve strands i and j. We shall say that a disk D bounded by strands i and j is elementary if sign(s) = — sign(e) and no proper sub-word of D is a disk bounded by i and j. An elementary disk D will be called an elementary reducing disk if i and j are less than n, and for any strand k less than n and not equal to i or j, strand k does not pierce the disk. In terms of linking numbers, this translates into the requirement that l k ^ D ) = lk^^D). Examples of disks, elementary disks, and reducing disks are given in figures 4.2-4.4. Figure 4.2: The disk 8[1,14] in 0[0,15] is bounded by strands 1 and 3. The correctness of the algorithm freeCanonicalForm depends on two claims: C l a i m 1: If 0 is a free braid, then either it contains a non-trivial elementary reducing disk, or 8 is in free canonical form. Chapter 4. Algorithms for Ordering Braids 38 Figure 4.3: The disk B[l, 8] is elementary, but not reducing. Figure 4.4: The disk 8[9,14] is an elementary reducing disk. Claim 2: The operation of untwisting a free n-braid 8 along an elementary reducing disk D reduces by two the number of crossings of 8 between strands of index less than n. Let us assume the truth of these claims for a moment. The algorithm starts with a reduced free braid inbraid. It iteratively finds an elementary reducing disk D and untwists the partial result along it, reducing by two the number of crossings between strands of index less than n in the result. Eventually there will be no more crossings between strands of index less than n, hence no more elementary reducing disks, and by claim 1 the result will be in free canonical form. Now let 8 be a free n-braid, and assume that 8 is not in free canonical form. Then there exist strands i and j, of index less than n, which meet at a crossing c. Since this crossing does not involve strand n, it remains if we apply the retraction map / to 8, and since 8 is in the kernel of this map, there is another crossing c' involving strands i and j, but of sign opposite to that of c, such that c and d cancel in f(8). If there is more than one such crossing, we may choose d among these so that c and d are the ends of an elementary disk D. Since the retraction map does not introduce new crossings, d is a crossing of 8; since c and d must cancel in f{8), there can be no strands other than Chapter 4. Algorithms for Ordering Braids 39 the n-th strand interposing between c and d in 3. Hence c and c' are the endcrossings of an elementary reducing disk in 3, bounded by strands i and j. This proves claim 1. The operation of untwisting an elementary reducing disk deletes the first and last crossings and adjusts the intermediate crossings. An elementary reducing disk bounded by strands i and j corresponds to a topological disk D in the geometric realization of a braid, which is bounded by arcs 7 1 , 7 2 , where 7 i H 72 = {a, b}, and 71 contains strand i and 72 contains strand j. Fixing a small open neighbourhood N of D in K , we can arrange, by a suitable isotopy, that no strands other than i, j, and n lie within N, and that these strands locally take one of the configurations shown in Table 4.1. The configurations are determined by the sign of the start crossing of the elementary reducing disk, the sequence in which the n-th strand crosses the boundary strands, and whether these crossings are over- or under-crossings. Claim 2 follows since the untwist does not introduce any new crossings except between strands i and n or j and n, but eliminates the start and end crossings of the reducing disk. 3 Finally, given a free n-braid in free canonical form, t o F r e e G e n L i s t () traverses the n-th, (free) strand, emitting a free generator xf wherever it under-crosses strand j, where the sign e is determined by the characteristic of the crossings. 4.2.1 Implementation Representation. It will be convenient to consider braids as arrays of crossings, where each crossing records the index of the elementary generator it represents, and also the "over" strand and the "under" strand involved at the crossing. This representation can be computed in time linear in the length of the array of elementary generators; we refer to this process as threading the braid. In order to carry out this threading, it is necessary to keep track of the permutation of the successive heads b\, bib , b\b bz,... of the braid as we scan from left to right. Consequently, when we have finished threading the braid, we have also computed the permutation of the braid. One can determine whether a threaded braid is pure by comparing its permutation to the identity; this may be done in time linear in the number of strands. 2 2 Chapter 4. Algorithms for Ordering Braids 40 Computing the retraction map. A key step in obtaining the combing of a pure braid is the computation of the retraction map / : P —> P -i - This map simply "forgets" the n-th strand. The algorithm for computing the retraction is easy to describe: scan the threaded braid from left to right and delete any crossings which involve the n-th strand. Of course, it is then necessary to decrement the index of crossings which lie "above" the n-th strand. This is best illustrated by an example — see Fig. 4.5. n Figure 4.5:/(cricr o'ia3CT2CTia cr3 2 1 n cr CTi<73cr cri) = cTicr <Ticr 2 2 2 c\020\ 2 2 2 Chapter 4. Algorithms for Ordering Braids Case: 1 Before untwist: ) < \C X 2 3 4 5 6 \>dy 41 After untwist: *A \ \ / V \l Jx -A-A/ J 7 8 1 / / Table 4.1: Possible configurations of strand n, before and after untwisting. Chapter 4. Algorithms for Ordering Braids 42 After twist: no combinatorial change does not happen no combinatorial change o k' o qp^4 no combinatorial change Table 4.2: Action of o on arcs with endpoint k: first 8 cases k Chapter 4. Algorithms for Ordering Braids Table 4.3: Action of a on arcs with endpoint k: remaining 8 cases k 43 Chapter 4. Algorithms for Ordering Braids Table 4.4: Action of a on arcs with endpoint k + l: first 8 cases k 44 Chapter 4. Algorithms for Ordering Braids Case: Initial configuration: 7.1 7.2 o< 7.3 7.4 -1 k+ 1 o •o »® fc+ 1 o does not happen 7* CH After twist: )® no combinatorial change + 1 S X O fc + 1 (k + iy s 8.1 o I ® 8.2 no combinatorial change 8.3 no combinatorial change 8.4 Table 4.5: Action of o on arcs with endpoint k + 1: remaining 8 cases k Chapter 5 Conclusions and Future Research 'But if for a moment he stopped gazing at the harmonious geometrical design drawn in the heaven of ideal models, a human landscape leaped to his eye where monstrosities and disasters had not vanished at all and the lines of the design seemed distorted and twisted. " Italo Calvino — Mr. Palomar 5.1 Conclusions Although the Magnus bi-ordering on the free groups F seems to have been known for several decades, the consequences and interpretation of this ordering, especially in the geometric context, seem to have received fairly little attention, perhaps because of the difficulties involved in computing by hand with this ordering. n Application of the Magnus ordering to the pure braid groups P , via a classical theorem of Artin revealing the semi-direct product structure of these groups, is fruitful, yielding some interesting insights. It is especially interesting to compare the resulting Artin-Magnus bi-ordering with the recently discovered Dehornoy ordering on the full braid groups B . Although the orderings appear in many ways compatible, it turns out that they differ fundamentally, e.g., in terms of the density of the orderings (cf. Theorem 3.15), and in fact the Artin-Magnus ordering does not extend to any right-invariant, or left-invariant, ordering on B (Theorem 3.16). n n n 46 Chapter 5. Conclusions and Future Research 47 Since the construction is fairly general (Theorem 3.18) one can imagine a large class of groups which might be bi-ordered via this approach. One such class of groups are the fundamental groups of fibre-type hyperplane arrangements (Theorem 3.17.) 5.2 Future Research There are many interesting questions raised by the discovery of the Dehornoy and the Artin-Magnus orderings. For example, [FGR 98] give a geometric interpretation of Dehornoy's right-ordering on B . It would be interesting to have a similar geometric understanding of the Magnus ordering on F . In particular, one way in which automorphisms of F have been explored is via the so-called Fox "free calculus". For example, the coefficients in the Magnus series expansion for words in the free group may be obtained by computing Fox derivatives of these words. We have not really touched upon this approach at all. It would be worthwhile to explore the role of the Fox calculus in the theory so-far presented. How general is the Artin-Magnus ordering? Are there examples of groups other than the fundamental groups of Fibre-type hyperplane arrangements discussed in 3.4.1 which can be presented in a way amenable to an ArtinMagnus-type decomposition? Can the Artin-Magnus ordering be expressed more generally than the statement of Theorem 3.18? More generally, for G an arbitrary group with a bi-invariant order <Q, are there other, easily verified criteria of the form "If ip e Aut(G) satisfies property + n n n X then ip preserves the order <G on G."l A further exploration of the connections between the orderings and topology, which we touched upon in Chapter 3, would be most interesting. In particular, what can be said about ordering various completions of the groups P and B l n n 5.2.1 Ordering related groups There are many groups related to the braid groups. For example, consider the Artin groups defined by the presentations with generators c i , . . . , < 7 „ _ i , and Chapter 5. Conclusions and Future Research 48 relations CTJCTJ = Cicr; > +1 ••• if \i — j\ > 1 cfjO~i Oi iai = Oi+\Oi • • • OiO \ + v i = l,...,n-2 l+ ' > 2k + 1 factors (5.1) (5.2) ' v 2k + 1 factors These generalize the n-strand braid groups (which correspond to Artin groups with k = 1) by introducing a more general class of relations to Artin's original presentation (cf. Equations 2.1, 2.2). It is known (see [Cha92]) that Artin groups of finite type are bi-automatic, in the sense of Thurston [ECH+92]. What can be said about orderings? Another type of generalization starts with the definition of B as the fundamental group of a configuration space of n points, B := n.i (C (C)), as discussed in Section 3.4.1. We may substitute any connected manifold M of dimension > 2 for the complex plane C, obtaining B (M) := iti{C (F), *), the so-called braid group of the manifold M. For example (see [Bir75]), it is known that B (S ), the n-strand braid group of the 2-sphere S , has a presentation obtained from the standard Artin presentation for B by adding the relation n n n n n 2 2 n n Cl • ' • C _ c r j _ C T „ _ 2 • • • C\ — 1. 2 n 2 1 It is easy to see from this relation that B (S ) cannot be ordered. Nevertheless it would be interesting to learn what might be said about ordering more general manifold braid groups. The example of B (S ) suggests further difficulties in constructing an analogue of the Artin-Magnus ordering: it shows that B (S ) cannot be faithfully represented as a subgroup of Aut(-?ri(5 \ n points)). 2 n 2 n 2 n 2 We might try to avoid such difficulties by focusing instead on groups which are already represented as subgroups of Aut(F ). There are many interesting groups of automorphisms between the image of B under the Artin representation, and the full automorphism group Aut(i ), including, for example, the Torelli groups already referred to in Section 3.4.2. n n ? n 5.2.2 Improvements to the algorithms On the algorithmic side of things, there remains much to be done. The code which computes the Dehornoy ordering has a worst-case exponential running time in terms of the length of the input, because it must add cut-points Chapter 5. Conclusions and Future Research 49 to intervals for each action of an elementary generator. Since such an action can result in the addition of as many as twice the number of cut-points in some intervals, the practical limit for computing curve diagrams for braids using this algorithm is quickly reached. An elegant simplification of the current representation would use so-called train tracks (see e.g. R. Penner and J. Harer, [PH92]) to represent multiple parallel arcs as a single arc together with an integer representing the number of strands "carried" by the arc. Each action of an elementary generator would then compute the effect on the underlying train track — determining where new "branches" are required, and updating the weights on the arcs. Computing the canonical braid corresponding to the canonical curve diagram is a relatively easy extension of the present code, which I hope to implement. The Fox free calculus has applications in many areas; however, computing the required derivatives by hand is tedious. Routines which compute the Fox derivatives should be added to the class library for non-commutative power series. Deeper analysis of computational complexity issues surrounding these algorithms should be carried out. For example, as alluded to earlier in this section, the naive representation of cut sequences consumes an exponential amount of storage in the worst-case. However, most of this storage is redundant, in precisely the same way that unary representation of numbers is much less efficient than chosing a radix > 2. For example, representing the cut sequences by train tracks would result in only polynomial space storage requirements. Bibliography [Art25] Emil Artin. Theorie der Zopfe. Abh. Math. Sem. Univ. Hamburg, 4:47-72,1925. Cited on page(s) 5, 7, 8 [Art47] Emil Artin. Theory of braids. Ann. of Math., 48:101-126, 1947. Cited on page(s) 11 [Ber90] George Bergman. Ordering co-products of groups. Journal of Algebra, 133:313-339,1990. Cited on page(s) 15 [Bir75] Joan S. Birman. Braids, Links and Mapping Class Groups. Number 82 in Annals of Mathematics Studies. Princeton University Press, Princeton, 1975. Cited on page(s) 9, 48 [Bur97] Serge Burckel. The well-ordering on positive braids. /. Pure Appl. Algebra, 120(1):1-17,1997. Cited on page(s) 24, 27 [BZ89] Gerhard Burde and Heiner Zieschang. Knots, de Grutyer, Inc., New York, 1989. Cited on page(s) 9 [Cha92] Ruth Charney. Artin groups of finite type are biautomatic. Math. Ann., 292(4):671-683,1992. Cited on page(s) 48 [Deh95] Patrick Dehornoy. From large cardinals to braids via distributive algebra. /. Knot Theory Ramifications, 4(l):33-79, 1995. Cited on page(s) 1, 26 [DF91] David S. Dummit and Richard M. Foote. Abstract Algebra. Prentice Hall, Inc, Englewood Cliffs, NJ, 1991. Cited on page(s) 11 [ECH+92] David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston. Word processing in groups. Jones and Bartlett Publishers, Boston, MA, 1992. Cited on page(s) 25, 48 [EM94] Elsayed A. Elrifai and H. R. Morton. Algorithms for positive braids. Quart, f. Math. Oxford Ser. (2), 45(180):479-497, 1994. Cited on page(s) 26 50 Bibliography 51 [EU45] C. J. Everett and Stanislaw Ulam. On ordered groups. Transactions of the American Mathematical Society, 57:208-216, 1945. Cited on page(s) 12 [FGR+98] Roger Fenn, Michael Greene, Dale Rolfsen, Colin Rourke, and Bert Wiest. Ordering the braid groups. To appear, Pacific J. Math., 1998. Cited on page(s) 1,2, 27, 33, 47 [Fla97] David Flanagan. Java in a Nutshell. O'Reilly & Associates, Sebastopol, CA, second edition, 1997. Cited on page(s) 53 [FR85] Michael Falk and Richard Randell. The lower central series of a fiber-type arrangement. Invent. Math., 82(l):77-88, 1985. Cited on page(s) 2, 30 [Gar69] F.A. Garside. The braid group and other groups. Quart. J. Math., 20:235-254, 1969. Cited on page(s) 2, 23, 25 [H6101] O. Holder. Die axiome der Quantitat und die Lehre von Mass. Math.-Phys. Kh, 53:1-64,1901. Cited on page(s) 12 [Iwa48] Kenkichi Iwasawa. On linearly ordered groups. Journal for the Mathematical Society of Japan, l(l):l-9,1948. Cited on page(s) 12 [Lav96] Richard Laver. Braid group actions on left distributive structures, and well orderings in the braid groups. /. Pure Appl. Algebra, 108(l):81-98,1996. Cited on page(s) 24, 27 [MKS76] Wilhelm Magnus, Abraham Karrass, and Donald Solitar. Combinatorial group theory. Dover Publications Inc., New York, revised edition, 1976. Presentations of groups in terms of generators and relations. Cited on page(s) 15,16,18 [MR77] Roberta Mura and Akbar Rhemtulla. Orderable Groups, volume 27 of Lecture Notes in Pure and Applied Mathematics. Marcel Dekker, New York, 1977. Cited on page(s) 12 [Neu49] B. H. Neumann. On ordered groups. American Journal of Mathematics, 71:1-18,1949. Cited on page(s) 12 Bibliography 52 [Neu74] L. P. Neuwirth. The status of some problems related to knot groups. In Topology Conference (Virginia Polytech. Inst, and State Univ., Blacksburg, Va., 1973), pages 209-230. Lecture Notes in Math., Vol. 375. Springer, Berlin, 1974. Cited on page(s) 1,14, 26 [OT92] Peter Orlik and Hiroaki Terao. Arrangements of Hyperplanes. Springer Verlag, New York, 1992. Grundlehren der mathematischen Wissenschaften No. 300. Cited on page(s) 30 [Par98] Luis Paris. On the fundamental group of the complement of a complex hyperplane arrangement. To Appear, 1998. Cited on page(s) 30 [Pas77] Donald S. Passman. The Algebraic Structure of Group Rings. Wiley-Interscience Press, New York, 1977. Cited on page(s) 12 [PH92] R. C. Penner and J. L. Harer. Combinatorics of train tracks. Princeton University Press, Princeton, NJ, 1992. Cited on page(s) 49 [RW98] Colin Rourke and Bert Wiest. Order automatic mapping class groups. To appear, 1998. Cited on page(s) 35 [RZ98] Dale Rolfsen and Jun Zhu. Braids, orderings and zero divisors. Knot Theory and Ramifications, 7(6):837-841, 1998. Cited on page(s) 1 [Tsc91] Jan Tschichold. The Form of the Book. Hartley & Marks, Vancouver, 1991. Cited on page(s) 101 [Vin49] A.A. Vinogradov. On the free product of ordered groups. Mat. Sb., 25:163-168,1949. Cited on page(s) 12 [WCSP96] Larry Wall, Tom Christiansen, Randal L. Schwartz, and Stephen Potter. Programming Perl. O'Reilly & Associates, Inc., Sebastopol, CA, second edition, 1996. Cited on page(s) 102 Appendix A An API for Computation with Braids "The perceptive reader tuill pick up some of the art [... ] of programming. We zvill encourage you to develop the three great virtues of a programmer: laziness, impatience, and hubris." Larry Wall et al. — Programming Perl A.l JAVA API for Computation with Braids This section presents an Application Programming Interface for the routines which have been presented in Chapter 4. The information presented in this API should be sufficient to enable programmers to use the code in their programs. A good background reference for programmers who are new to JAVA is [Fla97]. This API was automatically formatted into TjX input from HyperText (HTML) output generated by the j a v a d o c hypertext documentation utility. The TgX version is inferior to the HTML version in several respects: First, it lacks the dynamic structure of the HTML document. Second, it is bound in the current practial restrictions of printed documents, which limits its use of color as an organizational device. Finally, it is static, while the code which the document describes is likely to evolve for a period of time. The reader is therefore urged to consult the most current HTML version, which may be found at h t t p : //SunSITE .UBC . C A / D j u n / t h e s i s / j a v a / d o c / . 53 Appendix A. An API for Computation with Braids A.1.1 54 J A V A Application Programming Interface User's Guide This subsection is based in part on Sun Microsystems' J A V A Application Programming Interface User's Guide HTML document, which forms part of the HTML documentation tree for the Java Developer Kit QKD). It explains the structure of the following subsections, which are generated automatically from the source code, as explained in the previous section. A.1.2 How to use this API An Application Programming Interface is, as the name suggests, an interface between a given library of code and higher "application level" programs which employ this code. In other words, this API is a document intended for the programmer who wishes to use these code libraries in her or his application software. It contains sufficient information to allow the programmer to understand the functionality provided by the library, and how to employ it. The fundamental building block for J A V A programs is the class — J A V A ' S name for what is commonly called an object. Simply put, a class abstracts some system or entity, modeling it by encapsulating state (via a collection of variables) for that system or entity, and providing methods which operate on that state. Hence, to describe a J A V A program, we must describe the classes which constitute it, and how they interact. In short, classes are specified by describing the variables they contain, and the methods which are accessible within the class to operate on those variables. In addition, classes must be called into being, or instantiated by invoking a constructor which the class supplies. Generally classes present several constructors, which return more-or-less generic instances, depending on what the application program requires. For example, a program might request a specific new braid, with a given braid word; or it might want simply a generic, "empty" braid which it will manipulate, perhaps adding crossings and performing other operations on it. In the following sections, classes constituting the libraries are documented by describing their Variables, Constructors, and Methods. Variables can be instance variables — each invocation of the class has its own copy of these variables, or static variables — all invocations of the class share one copy of such variables; these are available "statically" even if there are no invocations Appendix A. An API for Computation with Braids 55 of the class. Similarly methods can be instance methods or static methods (meaning they can be invoked without a class having to be instantiated). The key below shows how the various variables and methods are keyed in the following API. Within these categories there is additional coding as follows: X Instance Variables # Static Variables f Constructors • Instance Methods o Static Methods Often a collection of classes forms a conceptual unit, in that members of the collection are closely related objects. Such collections of classes can be associated as a package. For example, all of the JAVA classes which abstract input and output operations are grouped together into the package j a v a . i o . Packages can in turn contain other packages, yielding a forest of related classes. The code which is presented in this appendix is divided into three packages: • math.alg.PowerSeries • math.topol.Braid • math.topol.Braid.CurveDiagram The Detailed API This section gives the complete API for each entry. Within the three categories: Variables, Constructors, and Methods, the entries are presented in the order they appear in the source. In addition, at the top of each class/interface there is a drawing of the tree structure down to the current class/interface, in which each superclass is a link. Every method contains a list of exceptions that it may throw. When a method overrides a method in the superclass, the API has the entry "Overrides: foo in class bar." Appendix A. An API for Computation with Braids 56 A.1.3 Installing and using the JAVA Class libraries A complete guide to installing and using the JAVA Class libraries appears with the libraries and source code at the Web site referred to in the introduction to this appendix. The class library is available in several forms, which should be usable on any platform which supports JAVA 1.1 or later. A.1.4 Example programs The following short example program is one of several which are available on the Web site. It is included to familiarize jAVA-novices with some of the formal aspects of working with third-party class libraries. import J a v a . u t i l . * ; import j a v a . u t i l . R a n d o m ; import m a t h . t o p o l . B r a i d . b r a i d ; I ** * T e s t the * (aversion * ©author */ public class random b r a i d r o u t i n e s i n m a t h . t o p o l . B r a i d . $ I d : A P I _ u s e r s _ g u i d e . t e x , v 1.1 1999/02/17 $ Djun Kim <Djun.Kim@SunSITE.UBC.CA> testrand { p u b l i c s t a t i c void main(String args[]) { Random rand_gen = braid.seedRandom(1); b r a i d randombraid = b r a i d . r a n d o m ( 6 , 20, rand_gen); System.out.println(randombraid.toString()); } } This program would be saved in a file called " t e s t r a n d . j ava", or perhaps " t e s t r a n d . jav", if your platform does not support long file names. Running the JAVA compiler j avac t e s t r a n d . j ava should produce a class file t e s t r a n d . c l a s s . This would be executed by typing J a v a t e s t r a n d , assuming that the class libraries m a t h . t o p o l . B r a i d . * have been installed according to instructions supplied with the libraries. Appendix A. An API for Computation with Braids A.1.5 57 Class Hierarchy This section gives an overview of the class libraries, showing the hierarchy between its member classes and the core classes of the J A V A Language API. All classes in J A V A implicitly subclass j ava. l a n g . Ob j ect, so this list can be viewed as a tree, rooted at j ava. l a n g . Ob j ect. • class j ava . awt. Component (implements J a v a . awt. image . ImageObserver, j ava.awt.MenuContainer,j a v a . i o . S e r i a l i z a b l e ) - class j ava. awt. Canvas * class g r a p h i c s . b e z i e r . PlotCanvas • class math. t o p o l . B r a i d . braidCanvas (implements J a v a . awt. event. A c t i o n L i s t e n e r ) • class math. t o p o l . B r a i d . CurveDiagram. C u t P o i n t • class math. t o p o l . B r a i d . CurveDiagram. CutSequence (implements j ava . l a n g . Cloneable) • class math. a l g . PowerSeries . F a c t o r • class math. t o p o l . B r a i d . CurveDiagram. I n t e r v a l (implements j ava . l a n g . Cloneable) • class math . a l g . PowerSeries .NCseries • class math. a l g . PowerSeries . Term • class j a v a . l a n g . Throwable (implements j a v a . i o . S e r i a l i z a b l e ) - class j a v a . l a n g . E x c e p t i o n * class math, t o p o l . Braid.NoCanvasException * class math. a l g . PowerSeries . V a r i a b l e O r d e r E x c e p t i o n • class math. t o p o l . B r a i d . b r a i d Appendix A. An API for Computation with Braids A.1.6 package math.alg.PowerSeries Class Index • Factor • NCseries • Term Exception Index • VariableOrderException A.1.7 package math.topol.Braid Class Index • braid • braidCanvas Exception Index • NoCanvasException A.1.8 package math.topol.Braid.CurveDiagram Class Index • CutPoint • CutSequence • Interval Appendix A. An API for Computation with Braids 59 A.1.9 Class math.alg.PowerSeries.Factor java.lang.Object I + math.alg.PowerSeries.Factor p u b l i c class Factor e x t e n d s Object This class represents Factors of Non-commutative power series, having the form (Aj) . These are represented as a pair ( i n J version: $ I d : math.alg.PowerSeries.Factor.tex,v 1.1 1 9 9 9 / 0 2 / 1 7 0 2 : 1 2 : 0 5 d j u n $ Constructors f Factor public Factor(int int index, pow) Constructs a new factor with the given index and degree. Methods • clone public Object clone() Returns a clone of this factor. Appendix A. An API for Computation with Braids Overrides: clone in class Object • getlndex public i n t getlndex() Gets the variable index for this factor • getPower public i n t getPower() Gets the variable power for this factor • setlndex public void setlndex(int index) Sets the variable index for this factor • setPower public void s e t P o w e r ( i n t power) Sets the variable power for this factor Appendix A. An API for Computation with Braids 61 A.1.10 Class math.alg.PowerSeries.NCseries Java.lang.Object + math.alg.PowerSeries.NCseries public class NCseries extends Object This class represents infinite power series with integer coefficients, in an arbitrary number of non-commuting variables, and provides various methods to implement elmentary algebraic and other manipulations. Version: $Id: math.alg.PowerSeries.NCseries.tex,v 1.11999/02/17 02:12:05$ Variables # DefaultTruncDegree p u b l i c s t a t i c f i n a l i n t DefaultTruncDegree J numvars p u b l i c i n t numvars The number of variables involved in this series. Constructors f NCseries public NCseries(Vector variables) throws V a r i a b l e O r d e r E x c e p t i o n Appendix A. An API for Computation with Braids 62 Creates a new Non-commutative Power Series in the given variables. The variables should be in the form of a vector of N contiguous integers between one and N. The variables will be ordered in ascending order according to the order in which they are given. For example, the input 4 / 3 / 1 / 2 corresponds to an ordering X < X < X\ < X 4 3 2 Throws: VariableOrderException Thrown whenever the variables given are not in the form of a vector of contiguous integers between one and N. Methods • getVariableOrder public Vector getVariableOrder() Returns the variable order of this NCseries, as a vector. • addTerm p u b l i c v o i d addTerm(Term term) Adds a term to this NCseries. • plus p u b l i c N C s e r i e s p l u s ( N C s e r i e s ps) Returns the result of adding ps to this NCseries. Parameters: ps - must have the same variables and order as this series Appendix A. An API for Computation with Braids • minus p u b l i c NCseries minus(NCseries ps) Returns the result of subtracting a given series from this NCseries. Parameters: ps - must have the same variables and order as this NCseries. • dividecLby p u b l i c NCseries divided_by(NCseries ps2) Returns the result of dividing this NCseries by the given NCseries. Parameters: ps2 - must have the same variables and order as this series. • times public NCseries times(NCseries ps2) Returns the product of this NCseries times the given NCseries. Parameters: ps2 - must have the same variables and order as this NCseries • getLength public i n t getLength() Gets the length (number of terms) of this NCseries. Appendix A. An API for Computation with Braids 64 • getTruncDeg public i n t getTruncDeg() Gets t h e t r u n c a t i o n degree o f this NCseries. • setTruncDeg public void setTruncDeg(int truncDeg) Sets t h e t r u n c a t i o n degree o f t h i s N C s e r i e s . • trunc public NCseries trunc(int deg) R e t u r n s t h e r e s u l t o f t r u n c a t i n g this N C s e r i e s after t e r m s o f t o t a l degree d e g . A s s u m e s this N C s e r i e s is sorted. • insertTerm public void insertTerm(Term t) I n s e r t s t h e g i v e n T e r m i n t o t h i s N C s e r i e s i n p r o p e r order. A s s u m e s t h a t t h i s N C s e r i e s is s o r t e d . compare_to public i n t compare_to(NCseries ps) C o m p a r e s t h i s N C s e r i e s w i t h the g i v e n N C s e r i e s : r e t u r n s -1 i f this is < t h e g i v e n N C s e r i e s , 0 i f t h e y ' r e e q u a l , a n d 1 i f this > t h e g i v e n N C s e r i e s . sort public void sort() Sorts t h e t e r m s o f this N C s e r i e s i n t o a s c e n d i n g order, first b y t o t a l degree o f t h e t e r m s , t h e n b y l e x i c o g r a p h i c order, based o n the g i v e n o r d e r o f v a r i a b l e s . Appendix A. An API for Computation with Braids 65 • collect public void collect() Collects like terms in this NCseries. • toString public String toString() Formats this NCseries as a string and returns the result. Overrides: toString in class Object o toMagnus public s t a t i c N C s e r i e s toMagnus(Vector v a r s , i n t A r r a y word) Returns the non-commutative power series (with variable order given by vars) giving the Magnus representation of word in the free group. o compare public s t a t i c int compare(NCseries p s l , NCseries p s 2 ) Compares two NCseries: returns -1 if the first is < the second, 0 if they're equal, and 1 if the first is > the second. invert public s t a t i c NCseries i n v e r t ( N C s e r i e s ps) Returns the result of inverting the given NCseries. Identity public s t a t i c NCseries Identity(Vector variables) Returns an NCseries with the given variable order, representing the identity series. Appendix A. An API for Computation with Braids A.l.ll 66 Class math.alg.PowerSeries.Term j ava.lang.Obj ect + math.alg.PowerSeries.Term' public class Term extends Object Represents terms of a Non-commutative power series.. Terms consist of an integer coefficient and a monomial. Version: $Id: math.alg.PowerSeries.Term.tex,v 1.11999/02/17 02:12:05 djun $ Constructors t Term p u b l i c Term(NCseries parent) Creates a new term for a NCseries of given type. Methods • insertFactor public void insertFactor(Factor int f, posn) Inserts a Factor f into the monomial for this term at the given position. • getMonomial Appendix A. An API for Computation public Vector with Braids 67 getMonomial() Returns the monomial of this term. • setMonomial public void s e t M o n o m i a l ( V e c t o r new_monomial) Sets the monomial of this term to the given monomial. • appendFactor public void appendFactor(Factor f) Appends a Factor f to the monomial for this term. • getTotalDegree public i n t getTotalDegree() Gets the total degree of this term. • getCoeff public i n t getCoeff() Gets the coefficient of this term. • setCoeff public void setCoeff(int value) Sets the coefficient of this term. • compare_to public i n t compare_to(Term t) Compares this term with term t: returns -1 if this < t, 0 if they're equal, and 1 if this > t. Appendix A. An API for Computation with Braids 68 • reduce p u b l i c v o i d reduce(Term t) Reduces the given term, so that adjacent similar variables are coalesced. • times p u b l i c Term times(Term t 2 ) Returns the product (non-commutative!) of this term with the given term. • toString public String toString() Formats this term as a string and returns the result. Note: This prints the coefficient, but not the sign of the coefficient, to make things easier for higher text formating routines. Overrides: toString in class Object o compare p u b l i c s t a t i c i n t compare(Term t l , Term t 2 ) Compares two terms tl, t2: returns -1 if tl < t2, 0 if they're equal, and 1 if tl > tl. Appendix A. An API for Computation with Braids 69 A.1.12 Class math.topol.Braid.braid j ava.lang.Obj ect + math.topol.Braid.braid p u b l i c class braid e x t e n d s Object Represents braids on -N strands and provides methods to manipulate such A-braids. Version: $ I d : m a t h . t o p o l . B r a i d . b r a i d . t e x , v 1.1 1 9 9 9 / 0 2 / 1 7 0 2 : 1 2 : 0 5 d j u n $ Copyright: (c)1998-1999 D j u n K i m . T h e a u t h o r reserves a l l r i g h t s . Variables | crosslist public intArray c r o s s l i s t T h e b r a i d w o r d : a list o f e l e m e n t a r y generators. # zerovect public s t a t i c f i n a l int zerovect[] Constructors t braid Appendix A. An API for Computation with Braids 70 p u b l i c b r a i d ( i n t numStrands) Creates an empty braid with the given number of strands. f braid p u b l i c b r a i d ( i n t braidwor'd[ ] ) Creates a braid from the given word in the standard generators (elementary braids), given as an int[] array. f braid p u b l i c b r a i d ( i n t A r r a y braidword) Creates a braid from the given word in the standard generators (elementary braids), given as an intArray. t braid p u b l i c b r a i d ( S t r i n g braidword) Creates a braid from the given String in the standard generators (elementary braids). Methods • getLength p u b l i c i n t getLength() Returns the length of this braid. • setBraid p u b l i c v o i d s e t B r a i d ( i n t A r r a y braidword) Sets this braid to the given braidword, expressed as an intArray. Appendix A. An API for Computation with Braids 71 o isPure public static b o o l e a n i s P u r e ( b r a i d b) Returns true if and only if the given braid is a pure braid. • getNumStrands public i n t getNumStrands() Returns the braid index (number of strands) of this braid. • setNumStrands public void setNumStrands(int numStrands) Sets the braid index (number of strands) of this braid. • embed public braid embed() Returns this braid naturally embedded in a braid with one more strand. retract public braid retract(int k) Returns the k-fold retraction of this braid, that is, the braid resulting from deleting the last k strands. Assume that this braid has been threaded. Returns null if such a retraction is undefined. inverse public braid inverse() Returns the inverse of this braid. times Appendix A. An API for Computation with Braids public 72 b r a i d t i m e s ( b r a i d b) Returns the product (this braid)*(b). Doesn't attempt to reduce the result. • freeReduce public void freeReduce() Reduces this braid, in the free group. Also removes any zero entries. • untwist public v o i d u n t w i s t ( b r a i d . d i s k D) Untwists an "innermost" twist of form af ••; (other generators involving strand n) • • • af , where Ok and a( involve strands i and j, and are opposite in sign. 1 1 Parameters: startindex - points to the crossing endindex - points to the crossing a . e • ArtinDecomposition p u b l i c Vector ArtinDecomposition(braid pb) Returns a Vector of intArrays, which represents the fully combed form of the given (pure!) braid. comb public b r a i d comb(braid pb) Returns a braid, which represent the fully combed form of the given (pure!) braid. freeCanonicalForm Appendix A. An API for Computation with Braids p u b l i c b r a i d freeCanonicalForm(braid 73 inbraid) R e t u r n s a b r a i d w h i c h is e q u i v a l e n t t o t h i s b r a i d , b u t w h i c h i s p r e s e n t e d as a p r o d u c t o f free g r o u p generators. T h i s assumes that this b r a i d is i n fact a n element of the n o r m a l subgroup of the pure n-strand b r a i d g r o u p w h i c h is the k e r n e l o f t h e r e t r a c t i o n m a p , i n the f o r m o f a p r o d u c t o f t h e free ( A r t i n ) generators. N o c h e c k i n g is d o n e o n i n p u t ! See Also: retract • getPermutation .public int[] getPermutation() R e t u r n s the p e r m u t a t i o n o f this b r a i d . T h e p e r m u t a t i o n is g i v e n as a n a r r a y o f n u m S t r a n d s integers, w h i c h represent the p e r m u t a t i o n o f the b r a i d o n the a r r a y [0,..., n u m S t r a n d s ] . o seedRandom public s t a t i c Random seedRandom(long seed) I n i t i a l i z e s the p s e u d o - r a n d o m b r a i d g e n e r a t o r w i t h t h e g i v e n seed v a l u e o f t y p e l o n g . T h i s r e t u r n s a n instance o f class R a n d o m , w h i c h is a " h a n d l e " t o a r a n d o m n u m b e r generator. o seedRandom p u b l i c s t a t i c Random seedRandom() I n i t i a l i z e s the p s e u d o - r a n d o m b r a i d g e n e r a t o r w i t h a " r a n d o m " v a l u e ( g i v e n b y t h e s y s t e m clock). o random Appendix A. An API for Computation with Braids p u b l i c s t a t i c b r a i d random(int int 74 index, length, Random randgen) Returns a pseudo-random braid of given index, of length less than or equal to the given length, generated by invocations of methods in j ava. utilRandom. A random number generator must be supplied, for example by a call to seedRandom. Note: the value of index should satisfy 1 < index < 128. o random p u b l i c s t a t i c b r a i d random(int index, Random randgen) Returns a pseudo-random braid of given index. The braid is generated by calls to the methods of j ava. u t i l .Random. A random number generator must be supplied, for example by a call to seedRandom. Note: the value of index should satisfy 1 < index < 128. The length of the braid will be a random number between 0 and 128. • thread public void thread() Creates a representation of this braid as a vector of crossings, with each crossing recording its index, which strands are involved, and whether it is a positive or a negative crossing. • toString public String toString() Returns a string representation of this braid. Overrides: toString in class Object Appendix A. An API for Computation with Braids 75 • toTeXForm public String toTeXForm() R e t u r n s a S t r i n g r e p r e s e n t a t i o n o f this b r a i d , f o r m a t t e d as TeX i n p u t . • toFreeGenList public intArray toFreeGenList() R e t u r n s a list ( i n t A r r a y ) r e p r e s e n t a t i o n o f this b r a i d , as a sequence o f free g e n erators. T h i s assumes t h a t this b r a i d has a l r e a d y b e e n p u t i n t o the a p p r o p r i a t e f o r m b y a call t o f r e e C a n o n i c a l F o r m . T h e generators are g i v e n b y Xi = a <r -\ •: • o\cr^\ • • • k 1 k w h i c h is r e p r e s e n t e d as i. T h e inverse is g i v e n b y —i. • toFreeGenTeXForm public String toFreeGenTeXForm() R e t u r n s a S t r i n g r e p r e s e n t a t i o n o f this b r a i d , w r i t t e n as a s t r i n g o f free generators. T h i s assumes that this b r a i d has a l r e a d y b e e n p u t i n t o the a p p r o p r i a t e f o r m b y a call t o f r e e C a n o n i c a l F o r m . T h e generators are g i v e n b y Xi = o Ok-\ k • • • o iOT+i •••'Tk 2 1 initPolys public void initPolys() I n i t i a l i z e s t h e v a r i a b l e s r e q u i r e d f o r the p o l y n o m i a l c o m p u t a t i o n s . T h i s m e t h o d m u s t b e c a l l e d b e f o r e a n y p o l y n o m i a l m a y b e c a l c u l a t e d . Since i t i n i t i a l i z e s a n s t r u c t u r e s w h i c h are f a c t o r i a l l y large i n t h e size o f t h e i n p u t , i t m a y c o n s u m e s i g n i f i c a n t c o m p u t a t i o n a l resources. O n c e t h e g l o b a l tables are i n i t i a l l i z e d , h o w e v e r , s u b s e q u e n t p o l y n o m i a l c o m p u t a t i o n s are fast. two_variable Appendix A. An API for Computation with Braids 76 public void two_variable(PrintWriter out, StringBuffer braidstr) C o m p u t e s the t w o - v a r i a b l e p o l y n o m i a l f r o m a b r a i d . o dbinomial p u b l i c s t a t i c double d b i n o m i a l ( i n t int R e t u r n s large b i n o m i a l coefficient ( — l ) f e l k, kl) x k\/kl\(k - kl)\ o factorialExpansion public s t a t i c int[] factorialExpansion(int int g, rl) R e t u r n s the f a c t o r i a l e x p a n s i o n o f g d o w n t o the ( r l - l ) - t h p o s i t i o n . o binomial public s t a t i c int binomial(int int v, vl) G e t s m a l l b i n o m i a l coefficient (n choose k) as a n i n t , f o r s m a l l v a l u e s o f k. Appendix A. An API for Computation with Braids 77 A.1.13 Class math.topol.Braid.braidCanvas Java.lang.Object + java.awt.Component I + j ava. awt. Canvas + graphics.bezier.PlotCanvas + math.topol.Braid.braidCanvas p u b l i c class braidCanvas extends PlotCanvas implements ActionListener Class braidCanvas encapsulates the data and methods required to draw braids and to interact with them on the screen. Version: $ I d : m a t h . t o p o l . B r a i d . b r a i d C a n v a s . t e x , v 1 . 1 1 9 9 9 / 0 2 / 1 7 02:12:05 d j u n $ Variables # ColArray p u b l i c s t a t i c Color ColArray[] Constructors f braidCanvas Appendix A. An API for Computation with Braids 78 p u b l i c b r a i d C a n v a s ( A p p l e t a, ActionListener al) f braidCanvas p u b l i c b r a i d C a n v a s ( A p p l e t a, ActionListener a l , i n t width, i n t height) Methods • initGfx public void initGfx() Initializes the graphics. • paint public void paint(Graphics g) Calls update to refresh the canvas with the image of the braid. Overrides: paint in class PlotCanvas • register public void register(braid b) Registers this braid with the canvas so that various operations can dispense with such operations as threading the braid. This is done once for every "new" braid. • update Appendix A. An API for Computation with Braids p u b l i c v o i d update(Graphics g) Update this image. Overrides: update in class PlotCanvas • draw p u b l i c v o i d draw() Plots the braid. Overrides: draw in class PlotCanvas • drawCrossing p u b l i c v o i d drawCrossing(int index, RealPoint basepoint) Draws given elementary generator at the given basepoint. • toPostScript public void toPostScript(braid b) Generates PostScript output which draws this braid. • drawBraid p u b l i c v o i d d r a w B r a i d ( b r a i d b) Draws given braid in this braidCanvas. Appendix A. An API for Computation with Braids 80 • addPopup p u b l i c v o i d addPopup(PopupMenu pop) A d d a p o p u p m e n u . W e assume t h a t the p o p u p m e n u has h a d a l l o f its m e n u i t e m s a d d e d , a n d t h a t each has a n a c t i o n listener d e f i n e d i n a n o t h e r class. • processMouseEvent p u b l i c v o i d processMouseEvent(MouseEvent e) Takes care o f M o u s e E v e n t s i n this b r a i d C a n v a s . Pops u p the P o p u p M e n u ; m o s t o t h e r events get p a s s e d u p s t r e a m t o superclasses o f t h i s class. Overrides: p r o c e s s M o u s e E v e n t i n class C o m p o n e n t • actionPerformed p u b l i c v o i d a c t i o n P e r f o r m e d ( A c t i o n E v e n t e) Takes care o f A c t i o n E v e n t s i n this b r a i d C a n v a s . E v e r y t h i n g here gets d i s p a t c h e d t o t h e a c t i o n L i s t e n e r w h i c h is s u p p l i e d i n t h e c o n s t r u c t o r t o t h i s b r a i d C a n v a s class. Appendix A. An API for Computation with Braids 81 A.1.14 Class math.topol.Braid.CurveDiagram.CutPoint j a v a . l a n g . O b j ect + math.topol.Braid.CurveDiagram.CutPoint p u b l i c class CutPoint e x t e n d s Object Implements a geometric cut point in a cut-sequence for a braid curve diagram. Version: $ I d : m a t h . t o p o l . B r a i d . C u r v e D i a g r a m . C u t P o i n t . t e x , v 1.1 1 9 9 9 / 0 2 / 1 7 0 2 : 1 2 d j u n Exp djun$ Copyright: (c)1998-1999 D j u n K i m . T h e a u t h o r reserves a l l r i g h t s . Variables \ integral p u b l i c boolean i n t e g r a l X direction public int direction X next p u b l i c CutPoint next X prev p u b l i c CutPoint prev Appendix A. An API for Computation with Braids X xpos public f l o a t xpos Constructors f CutPoint public CutPoint() Methods • copy p u b l i c C u t P o i n t copy() Returns a copy of this CutPoint. • toString public String toString() Returns a String representing this CutPoint. Overrides: toString in class Object 82 Appendix A. An API for Computation with Braids 83 A.1.15 Class math.topol.Braid.CurveDiagram.CutSequence java.lang.Object + math.topol.Braid.CurveDiagram.CutSequence p u b l i c class CutSequence e x t e n d s Object i m p l e m e n t s Cloneable Implements a geometric cut sequence, as defined in "Ordering the Braid Groups", by Fervn, Green, Rolfsen, Rourke, and Wiest, to appear in Pacific Journal of Mathematics. Version: $ I d : CutSequence.java,v 1.10 1 9 9 9 / 0 2 / 1 2 20:37:54 d j u n $ Copyright: (c)1998-1999 D j u n K i m . T h e a u t h o r reserves all r i g h t s . Variables t start p u b l i c CutPoint start X end p u b l i c CutPoint end X braidword public String # ColArray braidword Appendix A. An API for Computation with Braids public static Color 84 ColArray[] The sequence of colors used to differentiate images of the original intervals under the braid automorphism. Constructors f CutSequence public C u t S e q u e n c e ( i n t index) Returns a new, empty cutsequence of the given index. Methods • setHole public void setHole(CutPoint entry, int index) • setlnterval public void s e t l n t e r v a l ( I n t e r v a l entry, int index) • getlndex public i n t getlndex() o trivial public static CutSequence trivial(int index) Returns the "trivial" CutSequence for the given index. • twistBy public CutSequence twistBy(int k) Appendix A. An API for Computation with Braids 85 Returns the result of acting on this CutSequence by the elementary braid &k • Permitted values of k are (—braidlndex + l)..(braidlndex — 1). A value of 0 indicates the identity braid. • reduce p u b l i c v o i d reduce() Reduce a curve diagram. • append p u b l i c v o i d append(CutPoint t a i l ) Appends the given CutPoint to this CutSequence. • prepend p u b l i c v o i d prepend(CutPoint head) Prepends the given CutPoint to this CutSequence. • delete public void delete(CutPoint del) Delete the CutPoint del. • insertAfter p u b l i c v o i d i n s e r t A f t e r ( C u t P o i n t newpoint, CutPoint here) Insert the CutPoint newpoint after CutPoint here. • insertBefore public void insertBefore(CutPoint newpoint, CutPoint here) Appendix A. An API for Computation with Braids 86 I n s e r t t h e C u t P o i n t n e w p o i n t b e f o r e C u t P o i n t here. • toString public String toString() R e t u r n s a S t r i n g r e p r e s e n t i n g t h i s CutSequence. Overrides: t o S t r i n g i n class Object • PSOutput p u b l i c void PSOutput() W r i t e s PostScript code w h i c h d r a w s the C a n o n i c a l C u r v e D i a g r a m f o r this C u t Sequence t o System.out. Appendix A. An API for Computation with Braids 87 A.1.16 Class math.topol.Braid.CurveDiagram.Interval Java.lang.Object I + math.topol.Braid.CurveDiagram.Interval p u b l i c class Interval extends Object implements Cloneable Implements a list of CutPoints in an interval. Does not include the CutPoints which are endpoints of the interval. Version: $ I d : I n t e r v a l . j a v a , v 1.6 1 9 9 9 / 0 2 / 1 2 20:38:50 d j u n E x p d j u n $ Copyright: (c)1998-1999 D j u n K i m . T h e a u t h o r reserves a l l r i g h t s . Constructors t Interval public Interval(int anchor) Methods • elements p u b l i c Enumeration elements() R e t u r n s a n e n u m e r a t i o n o f t h e C u t P o i n t s i n this i n t e r v a l . Appendix A. An API for Computation with Braids 88 • remove p u b l i c v o i d remove(CutPoint del) Removes the given CutPoint from this Interval. • append p u b l i c v o i d append(CutPoint point) Appends the given CutPoint to this Interval. • lastElement p u b l i c CutPoint lastElement() Gets the last CutPoint in this Interval. • prepend p u b l i c v o i d prepend(CutPoint point) • reverse p u b l i c void reverse() Reverse the order of elements in this interval. • respace p u b l i c v o i d respace() Recomputes the position of each CutPoint in the interval so that the points are equally spaced from each other and the interval endpoints. • toString public String toString() Returns a String which represents this Interval. Overrides: toString in class Object Appendix A. An API for Computation with Braids 89 A.1.17 Index of all Fields and Methods A actionPerformed(ActionEvent). M e t h o d i n class m a t h . t o p o l . B r a i d . b r a i d C a n v a s Takes care o f A c t i o n E v e n t s i n this b r a i d C a n v a s . a d d P o p u p ( P o p u p M e n u ) . M e t h o d i n class m a t h . t o p o l . B r a i d . b r a i d C a n v a s A d d a popup menu. a d d T e r m ( T e r m ) . M e t h o d i n class m a t h . a l g . P o w e r S e r i e s . N C s e r i e s A d d s a t e r m t o this N C s e r i e s . appendFactor(Factor). M e t h o d i n class m a t h . a l g . P o w e r S e r i e s . T e r m A p p e n d s a Factor f t o t h e m o n o m i a l f o r this t e r m . A r t i n D e c o m p o s i t i o n ( b r a i d ) . M e t h o d i n class m a t h . t o p o l . B r a i d . b r a i d R e t u r n s a Vector o f i n t A r r a y s , w h i c h represents t h e f u l l y c o m b e d f o r m o f t h e g i v e n (pure!) braid. B b i n o m i a l ( i n t , i n t ) . Static m e t h o d i n class m a t h , t o p o l . B r a i d , b r a i d G e t s m a l l b i n o m i a l coefficient ( n choose k) as a n i n t , f o r s m a l l v a l u e s o f k. b r a i d ( i n t ) . C o n s t r u c t o r f o r class m a t h . t o p o l . B r a i d . b r a i d Creates a n e m p t y b r a i d w i t h t h e g i v e n n u m b e r o f strands. b r a i d ( i n t [ ] ) . C o n s t r u c t o r f o r class m a t h . t o p o l . B r a i d . b r a i d Creates a b r a i d f r o m t h e g i v e n w o r d i n the s t a n d a r d g e n e r a t o r s ( e l e m e n t a r y b r a i d s ) , g i v e n as a n i n t [ ] array. b r a i d ( i n t A r r a y ) . C o n s t r u c t o r f o r class m a t h . t o p o l . B r a i d . b r a i d Appendix A. An API for Computation with Braids 90 Creates a braid from the given word in the standard generators (elementary braids), given as an intArray. braid(String). Constructor for class math. t o p o l . B r a i d . b r a i d Creates a braid from the given String in the standard generators (elementary braids). braidCanvas(Applet, ActionListener). Constructor for class math, t o p o l . B r a i d . braidCanvas braidCanvas(Applet,ActionListener, int, int). Constructor forclassmath. t o p o l . Braid.braidCanvas C clone(). Method in class math, a l g . PowerSeries . F a c t o r Returns a clone of this factor. ColArray. Static variable in class math. t o p o l . B r a i d . b r a i d C a n v a s collect(). Method in class math. a l g . PowerSeries . N C s e r i e s Collects like terms in this NCseries. comb(braid). Method in class math. t o p o l . B r a i d . b r a i d Returns a braid, which represent the fully combed form of the given (pure!) braid. compare(NCseries, NCseries). Static method in class math. a l g . P o w e r S e r i e s . NCseries Compares two NCseries: returns —1 if the first is < the second, 0 if they're equal, and 1 if the first is > the second. compare(Term, Term). Static method in class math. a l g . PowerSeries . Term Compares two terms tl, tl: returns —1 if tl < tl, 0 if they're equal, and 1 if tl > tl. Appendix A. An API for Computation with Braids compare.to(NCseries). M e t h o d i n class 91 math. a l g . PowerSeries . N C s e r i e s C o m p a r e s this N C s e r i e s w i t h the g i v e n N C s e r i e s : r e t u r n s - . 1 i f this is < t h e g i v e n N C s e r i e s , 0 i f t h e y ' r e e q u a l , a n d 1 i f this > the g i v e n N C s e r i e s . compare.to(Term). M e t h o d i n class math. a l g . PowerSeries . T.erm C o m p a r e s t h i s t e r m w i t h t e r m t: r e t u r n s - 1 i f t h i s < t, 0 i f t h e y ' r e e q u a l , a n d 1 i f this > t. crosslist. V a r i a b l e i n class math. t o p o l . B r a i d . b r a i d T h e b r a i d w o r d : a list o f e l e m e n t a r y generators. D d b i n o m i a l ( i n t , i n t ) . Static m e t h o d i n class math. t o p o l . B r a i d . b r a i d R e t u r n s large b i n o m i a l coefficient ( — l ) f c l DefaultTruncDegree. Static v a r i a b l e i n class d i v i d e d J b y ( N C s e r i e s ) . M e t h o d i n class x k\/kl\(k - kl)\ math. a l g . P o w e r S e r i e s . N C s e r i e s math, a l g . P o w e r S e r i e s . N C s e r i e s R e t u r n s the result o f d i v i d i n g this N C s e r i e s b y t h e g i v e n N C s e r i e s . draw(). M e t h o d i n class math. t o p o l . B r a i d . b r a i d C a n v a s Plots t h e b r a i d . d r a w B r a i d ( b r a i d ) . M e t h o d i n class math. t o p o l . B r a i d . b r a i d C a n v a s D r a w s g i v e n b r a i d i n this b r a i d C a n v a s . drawCrossing(int, RealPoint). M e t h o d i n class math. t o p o l . B r a i d . b r a i d C a n v a s D r a w s g i v e n e l e m e n t a r y g e n e r a t o r at the g i v e n b a s e p o i n t . Appendix A. An API for Computation with Braids 92 embed(). M e t h o d i n class math. t o p o l . B r a i d . b r a i d Returns this b r a i d n a t u r a l l y e m b e d d e d i n a b r a i d w i t h one m o r e strand. Factor(int, i n t ) . C o n s t r u c t o r f o r class math. a l g . PowerSeries . F a c t o r C o n s t r u c t s a n e w factor w i t h t h e g i v e n i n d e x a n d degree. factorialExpansion(int, i n t ) . Static m e t h o d i n class math. t o p o l . B r a i d . b r a i d R e t u r n s t h e f a c t o r i a l e x p a n s i o n o f g d o w n t o the ( r l — l ) - t h p o s i t i o n . freeCanonicalFormfbraid). M e t h o d i n class math. t o p o l . B r a i d . b r a i d R e t u r n s a b r a i d w h i c h is e q u i v a l e n t t o this b r a i d , b u t w h i c h is p r e s e n t e d as a p r o d u c t o f free g r o u p generators. freeReduce(). M e t h o d i n class math. t o p o l . B r a i d . b r a i d Reduces t h i s b r a i d , i n t h e free g r o u p . G getCoeff(). Method in class math. a l g . P o w e r S e r i e s . Term Gets the coefficient of this term. getlndex(). Method in class math. a l g . P o w e r S e r i e s . F a c t o r Gets the variable index for this factor getLength(). Method in class math. t o p o l . B r a i d . b r a i d Returns the length of this braid. Appendix A. An API for Computation with Braids getLength(). M e t h o d i n class 93 math. a l g . PowerSeries . N C s e r i e s Gets the l e n g t h ( n u m b e r o f t e r m s ) o f this NCseries. getMonomial(). M e t h o d i n class math. a l g . PowerSeries . Term R e t u r n s the m o n o m i a l o f this t e r m . getNumStrands(). M e t h o d i n class math. t o p o l . B r a i d . b r a i d R e t u r n s the b r a i d i n d e x ( n u m b e r o f strands) o f this b r a i d . getPermutationQ. M e t h o d i n class math. t o p o l . B r a i d . b r a i d R e t u r n s the p e r m u t a t i o n o f this b r a i d . getPower(). M e t h o d i n class math. a l g . PowerSeries . F a c t o r Gets t h e v a r i a b l e p o w e r f o r this factor getTotalDegree(). M e t h o d i n class math. a l g . PowerSeries . Term Gets t h e t o t a l degree o f this t e r m . getTruncDeg(). M e t h o d i n class math. a l g . PowerSeries . N C s e r i e s Gets t h e t r u n c a t i o n degree o f this NCseries. getVariableOrder(). M e t h o d i n class math. a l g . PowerSeries . N C s e r i e s R e t u r n s t h e v a r i a b l e o r d e r o f this N C s e r i e s , as a vector. I Identity(Vector). Static m e t h o d i n class m a t h . a l g . P o w e r S e r i e s . N C s e r i e s R e t u r n s a n N C s e r i e s w i t h t h e g i v e n v a r i a b l e order, r e p r e s e n t i n g t h e i d e n t i t y series. initPolys(). M e t h o d i n class m a t h . t o p o l . B r a i d . b r a i d I n i t i a l i z e s t h e v a r i a b l e s r e q u i r e d f o r the p o l y n o m i a l c o m p u t a t i o n s . initGfx(). M e t h o d i n class m a t h . t o p o l . B r a i d . b r a i d C a n v a s Appendix A. An API for Computation with Braids 94 I n i t i a l i z e s the g r a p h i c s . insertFactor(Factor, i n t ) . M e t h o d i n class m a t h . a l g . P o w e r S e r i e s . T e r m Inserts a Factor f i n t o t h e m o n o m i a l f o r this t e r m at the g i v e n p o s i t i o n . insertTerm(Term). M e t h o d i n class m a t h . a l g . P o w e r S e r i e s . N C s e r i e s I n s e r t s t h e g i v e n T e r m i n t o t h i s N C s e r i e s i n p r o p e r order. inverse(). M e t h o d i n class m a t h . t o p o l . B r a i d . b r a i d R e t u r n s t h e i n v e r s e of this b r a i d . invert(NCseries). Static m e t h o d i n class m a t h . a l g . P o w e r S e r i e s . N C s e r i e s R e t u r n s the r e s u l t of i n v e r t i n g t h e g i v e n N C s e r i e s . i s P u r e ( b r a i d ) . Static m e t h o d i n class m a t h . t o p o l . B r a i d . b r a i d R e t u r n s t r u e i f a n d o n l y i f the g i v e n b r a i d is a p u r e b r a i d . M m i n u s ( N C s e r i e s ) . M e t h o d i n class m a t h . a l g . P o w e r S e r i e s . N C s e r i e s R e t u r n s the r e s u l t of s u b t r a c t i n g a g i v e n series f r o m this N C s e r i e s . N NCseries(Vector). C o n s t r u c t o r f o r class m a t h . a l g . P o w e r S e r i e s . N C s e r i e s Creates a n e w N o n - c o m m u t a t i v e P o w e r Series i n t h e g i v e n v a r i a b l e s . NoCanvasException(String). C o n s t r u c t o r f o r class m a t h , t o p o l . B r a i d . N o C a n v a s Exception numvars. V a r i a b l e i n class m a t h . a l g . P o w e r S e r i e s . N C s e r i e s T h e n u m b e r of v a r i a b l e s i n v o l v e d i n this series. Appendix A. An API for Computation with Braids 95 P p a i n t ( G r a p h i c s ) . M e t h o d i n class math. t o p o l . B r a i d . b r a i d C a n v a s Calls u p d a t e to refresh the canvas w i t h the i m a g e of t h e b r a i d . p l u s ( N C s e r i e s ) . M e t h o d i n class math. a l g . PowerSeries . N C s e r i e s R e t u r n s t h e r e s u l t of a d d i n g ps t o this NCseries. p r o c e s s M o u s e E v e n t ( M o u s e E v e n t ) . M e t h o d i n class math. Canvas topol. B r a i d . b r a i d - Takes care o f M o u s e E v e n t s i n this b r a i d C a n v a s . R r a n d o m ( i n t , i n t , R a n d o m ) . Static m e t h o d i n class math. t o p o l . B r a i d . b r a i d R e t u r n s a p s e u d o - r a n d o m b r a i d of g i v e n i n d e x , of l e n g t h less t h a n o r e q u a l t o the g i v e n l e n g t h . r a n d o m ( i n t , R a n d o m ) . Static m e t h o d i n class math. t o p o l . B r a i d , b r a i d R e t u r n s a p s e u d o - r a n d o m b r a i d of g i v e n i n d e x . reduce(Term). M e t h o d i n class math. a l g . PowerSeries . Term Reduces t h e g i v e n t e r m , so that adjacent s i m i l a r v a r i a b l e s are coalesced. register(braid). M e t h o d i n class math. t o p o l . B r a i d . b r a i d C a n v a s Registers t h i s b r a i d w i t h the canvas so t h a t v a r i o u s o p e r a t i o n s c a n d i s p e n s e w i t h s u c h o p e r a t i o n s as t h r e a d i n g the b r a i d . retract(int). M e t h o d i n class math, t o p o l . B r a i d , b r a i d R e t u r n s t h e k - f o l d r e t r a c t i o n o f t h i s b r a i d , t h a t is, t h e b r a i d r e s u l t i n g f r o m d e l e t i n g t h e last k strands. Appendix A. An API for Computation with Braids 96 S seedRandom(). Static method i n class math. t o p o l . B r a i d . b r a i d Initializes the pseudo-random braid generator w i t h a "random" value (given by the system clock). seedRandom(long). Static method i n class math. t o p o l . B r a i d . b r a i d Initializes the pseudo-random braid generator w i t h the given seed value of type long. setBraid(intArray). Method i n class math. t o p o l . B r a i d . b r a i d Sets this b r a i d to the given braidword, expressed as an intArray. setCoeff(int). Method in class math. a l g . P o w e r S e r i e s . Term Sets the coefficient of this term. setlndex(int). Method in class math. a l g . P o w e r S e r i e s . F a c t o r Sets the variable index for this factor setMonomial(Vector). Method i n class math. a l g . P o w e r S e r i e s . T e r m Sets the monomial of this term to the given monomial. setNumStrands(int). Method i n class math. t o p o l . B r a i d , b r a i d Sets the braid index (number of strands) of this braid. setPower(int). M e t h o d i n class math. a l g . P o w e r S e r i e s . F a c t o r Sets the variable power for this factor setTruncDeg(int). M e t h o d i n class math. a l g . P o w e r S e r i e s . N C s e r i e s Sets the truncation degree of this NCseries. sort(). M e t h o d i n class m a t h , a l g . P o w e r S e r i e s . N C s e r i e s Sorts the terms of this NCseries into ascending order, first b y total degree of the terms, then b y lexicographic order, based on the given order of variables. Appendix A. An API for Computation with Braids 97 T Term(NCseries). C o n s t r u c t o r f o r class math. a l g . PowerSeries . Term Creates a n e w t e r m f o r a N C s e r i e s of g i v e n t y p e . t h r e a d ( ) . M e t h o d i n class math, t o p o l . B r a i d , b r a i d Creates a r e p r e s e n t a t i o n of this b r a i d as a v e c t o r o f crossings, w i t h each c r o s s i n g r e c o r d i n g its i n d e x , w h i c h strands are i n v o l v e d , a n d w h e t h e r i t is a p o s i t i v e o r a n e g a t i v e crossing. times(braid). M e t h o d i n class math. t o p o l . B r a i d . b r a i d R e t u r n s the p r o d u c t (this b r a i d ) * ( b ) . t i m e s ( N C s e r i e s ) . M e t h o d i n class math, a l g . P o w e r S e r i e s . N C s e r i e s R e t u r n s the p r o d u c t o f this N C s e r i e s t i m e s the g i v e n N C s e r i e s . times(Term). M e t h o d i n class math. a l g . PowerSeries . Term R e t u r n s the p r o d u c t ( n o n - c o m m u t a t i v e ! ) of this t e r m w i t h the g i v e n t e r m . t o F r e e G e n L i s t ( ) . M e t h o d i n class math, t o p o l . B r a i d . b r a i d R e t u r n s a list ( i n t A r r a y ) r e p r e s e n t a t i o n of this b r a i d , as a sequence o f free g e n erators. t o F r e e G e n T e X F o r m Q . M e t h o d i n class math. t o p o l . B r a i d . b r a i d R e t u r n s a S t r i n g r e p r e s e n t a t i o n o f t h i s b r a i d , w r i t t e n as a s t r i n g o f free g e n e r a tors. t o M a g n u s ( V e c t o r , i n t A r r a y ) . Static m e t h o d i n class math. a l g . P o w e r S e r i e s . - NCseries R e t u r n s the n o n - c o m m u t a t i v e p o w e r series ( w i t h v a r i a b l e o r d e r g i v e n b y v a r s ) g i v i n g the M a g n u s r e p r e s e n t a t i o n of w o r d i n the free g r o u p . t o P o s t S c r i p t f b r a i d ) . M e t h o d i n class math. t o p o l . B r a i d . b r a i d C a n v a s Generates PostScript o u t p u t w h i c h d r a w s this b r a i d . t o S t r i n g Q . M e t h o d i n class math, t o p o l . B r a i d , b r a i d Appendix A. An API for Computation with Braids 98 R e t u r n s a s t r i n g r e p r e s e n t a t i o n o f this b r a i d . toString(). M e t h o d i n class math. a l g . PowerSeries . N C s e r i e s F o r m a t s this N C s e r i e s as a s t r i n g a n d r e t u r n s t h e result. toString(). M e t h o d i n class math. a l g . PowerSeries . Term F o r m a t s this t e r m as a s t r i n g a n d r e t u r n s the result. toTeXForm(). M e t h o d i n class math. t o p o l . B r a i d . b r a i d R e t u r n s a S t r i n g r e p r e s e n t a t i o n o f this b r a i d , f o r m a t t e d as TeX i n p u t . trunc(int). M e t h o d i n class math. a l g . PowerSeries . N C s e r i e s R e t u r n s the r e s u l t o f t r u n c a t i n g this N C s e r i e s after t e r m s o f t o t a l degree d e g . two_variable(PrintWriter, S t r i n g B u f f e r ) . M e t h o d i n class math.topol.Braid.- braid Computes the two-variable p o l y n o m i a l f r o m a braid. U u n t w i s t ( b r a i d . d i s k ) . M e t h o d i n class math. t o p o l . B r a i d . b r a i d U n t w i s t s a n " i n n e r m o s t " t w i s t o f f o r m erf 1 ri) ••• of , 1 w h e r e cr a n d fc • • • (other generators i n v o l v i n g s t r a n d i n v o l v e s t r a n d s i a n d j , a n d are o p p o s i t e i n s i g n . u p d a t e ( G r a p h i c s ) . M e t h o d i n class math. t o p o l . B r a i d . b r a i d C a n v a s U p d a t e this i m a g e . V VariableOrderException(String). C o n s t r u c t o r f o r class VariableOrderException math. a l g . P o w e r S e r i e s . - Appendix B Glossary "He hath honour'd me of late; and I have bought Golden opinions from all sorts of people, Which wotdd be worn now in their newest gloss, Not cast aside so soon." W. Shakespeare — MacBeth algebra: Let A be a ring, and let / : R -> A be a ring homomorphism. For a € A and r € R define a product ra = f(r)a. This makes A into an Rmodule, as well as a ring. We say that A is an R-algebra. A common situation has R a field in the center of A, with / being the embedding map. In this case A has a vector-space structure over R. API: Application Programming Interface. The information required by the user (i.e., application programmer) of a software routine or module in order to invoke that module from her or his application code. Archimedean: A right-orderable group G is Archimedean if whenever 1 < x < y in the group, there exists an integer p such that x > y. v class: The terminology for an object; that is, a complete unit or module of a program which models a system or entity by encapsulating some state which describes the system or entity, together with methods, i.e., functions, which operate on the object's state. A programming language is said to be object-oriented if it supports the design of programs which consist of objects, interacting via their methods. JAVA 99 Appendix B. Glossary 100 group action: Let G and H be groups. A homomorphism G -> Aut(rY) is said to be a group action of G on H. We will usually denote the map by g i - > group ring: Let R be a ring, and G a group. The group ring RG of G is the set of all formal sums of elements multiply two such sums: igi where ri e R and gi € G; we can T ngi ] T r jgj i j = Y nrj9i9jhj Under this product, RG has the structure of a ring. integral domain: A ring R is an integral domain-it it has no zero divisors (other thanO). knot: Declare any two homeomorphisms K, K': S —> S to be equivalent if there is a self-homeomorphism h: S -r S such that K — h(K'). An equivalence class under this relation is called a knot. Under the same equivalence relation, the space of continuous maps L: S TJ • • • TJ S -> S is partitioned into links. 1 3 3 3 1 1 3 ring: Let R be a commutative group w.r.t. addition and suppose there is an associative multiplication R x R R with unit element 1, such that this multiplication distributes over addition: Vrr,y,z € R : and (x + y)z = 2:2 + z(x + y) = zx + zy Then i? is a ring. unit: An element a of a ring R with identity element 1 is a unit if it has both left and right inverses, that is, if there exist elements b,b' 6 R such that ba = ab' = 1. zero divisor: An element d of a ring R with identity element 1 is a left zero divisor (respectively right zero divisor), if there exists an element b £ R such that db = 0, (resp. bd = 0). Appendix C Colophon The U.B.C. Library Special Collections division, which sets U.B.C. thesis style and format guidelines, recently relaxed the long-standing requirement that submitted theses be "double spaced" with 1 inch margins. It is to be hoped that this enlightened decision will result in the submission of theses which are considerably more readable (if not more comprehensible!) than their precursors. The page design of this document is based on canons set forth in The Form of the Book by Jan Tschichold [Tsc91], "a lifelong student, teacher and practitioner of typography, passionately concerned with the broadest principles and tiniest details of his chosen art and craft... ." (Robert Bringhurst, Introduction, op. cit.) His designs and teaching have had a significant influence on book and page design in the 20th century. This document was set in Adobe's version of the Palatino fonts, designed by the famed Swiss typographer Hermann Zapf. The text body fonts were set at 11 points. Donald Knuth's Computer Modern Math fonts were used to set the mathematics, along with blackboard bold and Euler fonts from the American Mathematical Society (AMS.) The entire document was typeset using the MpX 2^ macro package for Knuth's TgX software. Anders Svensson wrote the original ETjpC class definitions for the U.B.C. thesis style. Several additional macro packages from the American Mathematical Society were used to typeset displayed equations and diagrams, and to use the AMS fonts. 101 Appendix C. Colophon 102 Many of the illustrations were drawn using the Xf i g program and postprocessed into encapsulated PostScript. Several additional figures were produced by C , Perl [WCSP96] and JAVA programs. The index and notation index were generated from the I^TgX index files by a Perl script written by the author. The bibliography was generated by BibT^X from bibliographic database (. b i b file) entries retrieved from the AMS's WWW-based MathSciNet Mathematical Reviews information server. Index of Notation 'Any inaccuracies in this index may be explained by the fact that it has been sorted with the help of a computer." Donald Knuth — Sorting and Searching Symbol : Meaning = B Bi n Hi(G) Pn Qn RG S n B n A 2 is defined to be n-strand braid group Garside positive braids first homology of the group G n-strand pure braid group set of n marked points the i?-group ring of G Symmetric group on n-letters n-times punctured disk the generator of the center of P free group of rank n series in Z[[X(n)]] with constant term 1 positive cone Euclidean 3-space a is greater than all powers of B natural inclusion the permutation of the braid B i-th elementary generator Q.E.D. (end of proof) "forget the n-th strand" retraction map n F n G V M Page 3 a » B i: P -1 n «-»• P n ir(B) • f'-Pn-* Pn-l 103 3 6 23 11 8 8 12 7 8 21 8 16 13 6 27 10 7 7 3 10 Index of Notation Symbol 0(d) z Z[[X(n)]] X(n) Aut(F ) n 104 Meaning j-th free generator of Fi terms of total degree > d the ring of integers ring of formal power series over Z ordered set of n non-commuting variables Automorphism group of the free group Page 10 16 7 15 15 8 Index abbreviations, 3 abelianization, 11, 22-23 maps, 23 action, 9,13-14 algorithms, 2-3, 33 API, 3 Archimedean, 12, 20, 99 Artin, 1, 5, 8 coordinates, 22, 28 decomposition, 1 Emil, 5 generators, 10 groups, 47 representation of B , 8 -Magnus order, 1-2,19 automorphism, 8-9 axioms, 1 combing the braid, 11 full Artin combing, 11 composition, 6 configuration space of n ordered points in C, 29 of n unordered points in C, 30 convention, 7,11 curve diagram, 33 deduction, 1 degree, 16 Dehornoy, Patrick 2, 26, 48 diary, viii direct limit, 21 direct product, 13 disk, 37 n elementary, 37 elementary reducing disk, 37 errors, viii Euclidean 3-space, 6 extensions, group, 13 bi-automatic, 48 bi-invariant, 30 bi-orderable, 1,13 braid group on n-strands, 6 of the manifold M , 48 pure 8, 30 Bringhurst, Robert, 101 Falk, Michael, 2, 30 Ferrer, Horacio, 5 fibrations, 30 fibre, 30 font, 3-4,101 canonical curve diagram, 33 chaos, 19 clockwise, 8 closure, 13,14 coefficient, 16 The Form of the Book, 101 Fournier, Pierre, 19 free braid, 10, 36 free canonical form, 36 freeCanonicalForm(), 36 105 Index free generator, 10,12 free product, 12 fundamental group, 8 Garside, 2, 23, 25 positive, 23-24, 27 general falsehoods, viii generator, 7-8,10,15,47 glossary, 3 group action, 100 group ring, 12,100 Holder, 12, 20 hyperplane, 30 hyperplane arrangement, 2, 30 fibre-type, 30 i-th elementary braid, 7 identity, 6 implementation, 3 inclusion, 10 integral domain, 12,100 Interface, 3 inverse, 7,16 isotopy, 6 Italo Calvino, 1, 32, 46 Kaplansky, Irving, 12 Klein bottle group, 14 knot, 100 Knuth, Donald, 101,103 lexicographic ordering, 13,14 linking number, 22, 37 links, 100 local, 35 local conjugation, 9,11, 31 106 lower central series, 12 MacBeth, 99 Magnus, 15 : expansion, 1, 21-22, 24-25, 28 map, 15 ordering, 16 series, 15 Magnus-Witt theorem, 12 Manuel Typographique, 19 Maria de Buenos Aires, 5 methods, 99 misguided generalizations, viii model, 1 monomials, 16 Mr. Palomar, 1, 32, 46 n-braid, 6 n-strand pure braid, 30 non-constant, 21, 28 non-repeating braids, 25 normality, 13,15 object, 99 object-oriented, 32, 99 order, 19 order-automatic, 35 order-respecting, 23 orderable group, 1,13 right-orderable, 1,13 bi-orderable, 1,13 ordered set, 15 orienting, 8 Paris, Luis, 2 partition, 13,14 Index 107 Perl, 53 permutation, 7 positive cone, 13,15 postulates, 1 power series, 15 presentation, 7 principles, 1 punctured disk, 8 pure braid, 8 Pt-algebra, 99 Randell, Richard, 2, 30 representation, 10 of F , 15 retraction, 10, 21, 23, 36 ring, 100 n semi-direct product, 1-2,11,14 short exact sequence, 8,13 Shakespeare, William, 99 Shrigley, David, viii Sorting and Searching, 103 state, 99 threading, 39 t o F r e e G e n L i s t (), 36 Torelli group, 31,48 Tschichold, Jan, 101 torsion-free, 12, 30 total degree, 16 train tracks, 49 transversely, 6 twist, 9 unique factorization, 12 unit, 100 units, 12 . untwisting, 38-39 Vinogradov, 12 Wall; Larry, 53 well-ordered, 24 Zapf, Hermann, 101 zero-divisors, 12 left, 100 right, 100
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Braid groups, orderings, and algorithms
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Braid groups, orderings, and algorithms Kim, Djun Maximillian 1999
pdf
Page Metadata
Item Metadata
Title | Braid groups, orderings, and algorithms |
Creator |
Kim, Djun Maximillian |
Date Issued | 1999 |
Description | We define a natural and readily calculated bi-invariant strict total ordering of the n-strand pure braid group Pn. It is defined algebraically, using the Artin decomposition of Pn as a semi-direct product of free groups, together with a specific ordering of free groups using the Magnus expansion. This definition extends to define bi-orderings of more general semi-direct products involving free groups, including the fundamental groups of the complements of fibretype hyperplane arrangements. After basic properties of this "Artin-Magnus" ordering are established, we compare it to existing orderings on Pn, including the restriction of the Dehornoy ordering to Pn. Finally, we present algorithms to compute the Dehornoy ordering on the full braid group Bn, and the Artin-Magnus ordering on Pn. An implementation of these algorithms is included as part of a library of objects for symbolic computation with braids. |
Extent | 3911660 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-06-30 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0079908 |
URI | http://hdl.handle.net/2429/9892 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1999-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1999-389138.pdf [ 3.73MB ]
- Metadata
- JSON: 831-1.0079908.json
- JSON-LD: 831-1.0079908-ld.json
- RDF/XML (Pretty): 831-1.0079908-rdf.xml
- RDF/JSON: 831-1.0079908-rdf.json
- Turtle: 831-1.0079908-turtle.txt
- N-Triples: 831-1.0079908-rdf-ntriples.txt
- Original Record: 831-1.0079908-source.json
- Full Text
- 831-1.0079908-fulltext.txt
- Citation
- 831-1.0079908.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0079908/manifest