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 exten-sive 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 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 fibre-type 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 implementa-tion of these algorithms is included as part of a library of objects for symbolic computation with braids. 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.1 Introduction and Statement of Principal Results 1 1.2 Outline 2 1.3 Notation 3 Chapter 2. Braids and Orderings 5 2.1 Braids .' 5 2.1.1 Definition.. 5 2.1.2 Group structure 6 2.1.3 Automorphisms of Free Groups 8 2.1.4 Artin Combing and the Structure of Pure Braid Groups 10 2.2 Ordered Groups 12 2.2.1 Definitions and Examples 13 2.2.2 Ordering Semi-direct Products 13 2.3 The Magnus Ordering of the Free Group Fn 15 Chapter 3. An Explicit Bi-ordering of the Pure Braid Group 19 3.1 Construction of the Artin-Magnus Ordering 19 3.2 Properties and Examples 19 3.2.1 Garside Positive Braids ....23 3.3 Comparison with other orderings 25 iii Table of Contents . j v 3.3.1 The Garside partial order 25 3.3.2 The partial order of Elrifai and Morton 26 3.3.3 The Dehornoy ordering 26 3.4 Generalized Artin-Magnus Orderings 29 3.4.1 Fibre-type hyperplane arrangements 29 3.4.2 Generalized Artin-Magnus orderings 31 Chapter 4. Algorithms for Ordering Braids 32 4.1 The Dehornoy ordering 33 4.1.1 Implementation 34 4.2 The Artin-Magnus Ordering 35 4.2.1 Implementation 39 Chapter 5. Conclusions and Future Research 46 5.1 Conclusions 46 5.2 Future Research 47 5.2.1 Ordering related groups 47 5.2.2 Improvements to the algorithms 48 Bibliography 50 Appendix A. An API for Computation with Braids 53 A.l JAVA API for Computation with Braids 53 A. 1.1 JAVA Application Programming Interface User's Guide 54 A.1.2 How to use this API 54 A. 1.3 Installing and using the JAVA Class libraries 56 A.1.4 Example programs 56 A.1.5' Class Hierarchy 57 A.1.6 package math.alg.PowerSeries 58 A.l.7 package math.topol.Braid 58 A. 1.8 package math.topol.Braid.CurveDiagram 58 A.1.9 Class math.alg.PowerSeries.Factor 59 A.l.10 Class math.alg.PowerSeries.NCseries 61 A.1.11 Class math.alg.PowerSeries.Term 66 A.l.12 Class math.topol.Braid.braid 69 A.1.13 Class math.topol.Braid.braidCanvas 77 A.l.14 Class math.topol.Braid.CurveDiagram.CutPoint 81 iv 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 Possible configurations of strand n, before and after untwisting 41 4.2 Action of cxfc on arcs with endpoint k: first 8 cases 42 4.3 Action of on arcs with endpoint k: remaining 8 cases 43 4.4 Action of cr/t on arcs with endpoint k + 1: first 8 cases 44 4.5 Action of Ok on arcs with endpoint A; + 1: remaining 8 cases 45 vi List of Figures 2.1 Composition of two braids 6 2.2 The z-th elementary braid CTj 7 2.3 The punctured disk D„ and generators for Fn 9 2.4 The action of ax on TTI (D„) 9 2.5 The natural inclusion i : P n - i t_> Pn 10 2.6 The generator ZJ ,* e F j = { x i y i , x i t i ) C Pn 10 2.7 A pure braid, before and after combing 11 3.1 The squares of the elementary generators 20 3.2 The common braid used for hair, on the first three strings 20 3.3 The generator A 2 of the center of P4 21 4.1 The canonical curve diagram for oxc^o^ G B 5 34 4.2 The disk B[l, 14] in p[0,15] is bounded by strands 1 and 3 37 4.3 The disk 8[1,8] is elementary, but not reducing. 38 4.4 The disk /3[9,14] is an elementary reducing disk 38 4-5 f (o\O2O\OzO20~\O\OZ~'10-20-\0-l,Ci2°~\) = 0\a20\a2~'X0\OiO\ 40 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, friend-ship, 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 con-stant 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 con-versations, 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. Palomar 1.1 Introduction and Statement of Principal Results One of the most fundamental recent discoveries regarding the Artin braid groups Bn is that they are right-orderable [Deh95], [FGR+98]. A group G is right-order able 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], Bn is not bi-orderable if n > 3. By contrast, it was shown in [RZ98] that the subgroups Pn of pure braids are bi-orderable, but the proof is non-constructive. This thesis describes an explicit, natural, and easily computed bi-ordering of Pn, which is constructed from two classical ingredients: the Artin decom-position of Pn as a semi-direct product of free groups; and the Magnus expan-sion of free groups in a ring of formal power series. Accordingly, we call this the "Artin-Magnus" ordering of the pure braid groups. 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 Pn 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 Bn defined by Garside, restricted to Pn. We show the set of Garside-positive elements is actually well-ordered in the Artin-Magnus ordering. It is noted in [FGR+98] that the Dehornoy right-ordering of Bn, restricted to Pn, 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 Bn. In Section 3.3, we com-pare the Artin-Magnus ordering with others in the literature. We give a proof that the Artin-Magnus ordering of Pn does not extend to any right-invariant (or left-invariant) ordering of Bn, 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 Bn under the Dehornoy ordering, and elements of Pn under the Artin-Magnus ordering. 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 ingredi-ents 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 exam-ples 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 Sec-tion 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 manipu-late combinatorial representations via operations which are topologically in-duced. A J A V A language implementation of the algorithms, in the form of a package of routines callable from JAVA 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 ex-amples. 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.) " Horac io 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 ex-ample, 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 wil l 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 — R2 C M3 be the (y, z)-coordinate plane in Euclidean 3-space; let E' be E translated one unit in the x direction. Let Qn c E be marked points on the z-axis at 0,1,... ,n — I and let Q'n be the corresponding set in E'. Consider disjoint embedded arcs on: [0,1] —> M3 (i = 1 , . . . , n), of the form ai(t) = (t,af\t),af)(t)) with a.i meeting some point of Qn (respectively Q'n) transversely at t = 0 (respec-tively 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 ofR3 rel E and E'. 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. ffOT:=vj(<7)U(^(r) + ( l / 2 , 0 I 0 ) ) where cp is the homeomorphism of M3 given by x t-¥ x/2. Finally one takes the isotopy class of the result. 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 Bn and refer to as the braid group on Chapter 2. Braids and Orderings 7 n-strands. The identity in Bn is the n-braid whose strands pass straight through 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~l is the "time-reversed" collection of paths 8il{t)' i — I,-- - ,n, with 8~l(t) — {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 Bn admits a presentation with generators u i , . . . , <7 n _i , and relations OiOj = cjjGi if \i — j\ > 1, 1 < i, j < n — 1 (2.1) = Oi+\OiOi+\ i = l , . . . , n —2 (2.2) It is clear that the group B2 is isomorphic with the integers Z . Chapter 2. Braids and Orderings 8 Definition 2.3 Corresponding to any braid pis a permutation TT{0) e Sn, recording how the strings connect the endpoints. In particular, a braid whose permutation is the identity is called a pure braid. The map IT: Bn -> Sn is easily seen to be a group homomorphism. Hence the set of pure braids forms a normal subgroup Pn of index n! in Bn, which fits into a short exact sequence 1 Pn -> Bn -> Sn -> 1. Pn is called the pure braid group on n-strands. 2.1.3 Automorphisms of Free Groups Let Fn := (xi, • • • , xn) be the rank n free group generated by x\,..., xn. An object of great interest in combinatorial group theory is Aut(Fn), the auto-morphism group of the free group. Many interesting groups appear naturally as subgroups of Aut(F„), and among these is the n-strand braid group Bn. The following construction, due to Artin [Art25], exhibits Bn as a group of automorphisms of Fn, represented as the fundamental group of a punctured disk. Let D n := D2 — Qn denote the disk with n punctures, denoted by Qn := {pi,... ,pn} and arranged in order along a straight line in D2. Then Fn can be identified with TTI (D n ) . To be precise, let x\,..., xn be loops in D n representing generators of TT\ (D„). We will orient them in the clockwise sense, as shown in Figure 2.3. An n-braid can be regarded as the graph of a motion of n distinct points in the disk, beginning and ending in Qn; this motion extends to a self-home-omorphism of Bn, unique up to an isotopy which fixes the punctures and boundary of D2. This homeomorphism in turn induces an automorphism of the fundamental group, i.e., an automorphism of Fn. By our previous choices, the elementary braid CTJ corresponds to the right-hand half-twist interchanging pi and pi+i and fixed off of a small neighbor-hood of the interval between these points. In terms of generators, the corre-sponding automorphism is given by Xi i ^ XiXi^-\Xi , Xj t - > Xj (j ^ i , i + 1.) Chapter 2. Braids and Orderings 9 Figure 2.3: The punctured disk D n and generators for Fn 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 7r1(lD)„) Thus the automorphism corresponding to a braid 8 will take the generator Xi to the word WiX^Wi'1, where ir is the permutation corresponding to 3, and Wi also depends on 3. This correspondence determines an embedding of Bn into Aut(jFn). 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. 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: Pn_x «-» pn adds an n-th strand to an (n - l)-strand pure braid 8, as illustrated in Figure 2.5. — n-l P n-l P Figure 2.5: The natural inclusion i: Pn-i •->• Pn There is also a retraction / : Pn —> P n _ 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 (IR2 \ (n — 1) points), a free group of rank n — 1. Hence we have a representation of F n _ i as a normal subgroup of Pn. We may write B e Pn as B = (i of(8))(i o f(8)~l8)-Note that /(/?) € P n _ i while iof((3)~l8 6 Fn-i- When context allows, we shall drop explicit mention of the inclusion map i and write, for example, 8 = f{ft){f{ft)~l8). i + 1 Figure 2.6: The generator xjti € Ft = ( x u , x i y i ) C Pn. For any i 6 { l , . . . , n - l } , we may thus regard the subgroup Fi C Pi C Pn 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, Xj,i — Ol(7i-\ • • • <Jj + i<7j2aj + l~l • • • Gi^l~lGi~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)~l3) is an isomorphism Pn = P n _ 1 t<v F n _ i , where the action ip: Pn-\ -> Aut(F„_i) associated ivith the semi-direct product is given by local conjugation, and therefore induces the identity on the abelianization Hi(Fn-\) := F n _i/[F n _i, Fn-\]. Proof. The subgroups Pn-i C Pn and F n _ i < Pn, satisfy Pn-i D F n _ i = 1. Hence P n _ i F n _ i forms a subgroup of Pn, and every element of this sub-group has a unique expression cry with a € Pn-i and 7 € F n _ i (see [DF91], page 176). Every element 3 € Pn may be written (3 = f(3) o f(B)~l3)), hence the subgroup P n _ i F n _ i is all of Pn. The statement about the action ip follows from the fact pointed out in 2.1.3, that the Artin action of Bn on Aut(F„) is by local conjugation. • The procedure of isolating all interactions of the last strand with the other strands of a pure braid was called by Artin1 "combing the braid". Figure 2.7 shows an example of combing a pure braid. We define the full Artin combing of Pn to be the iterated semi-direct prod-uct decomposition Pn = (• • • ( F i K F 2 ) K F3) x • • • x F n _i) . By employing the convention that a chain of semi-direct products associates in left-to-right or-der, we can dispense with the parentheses and write simply Pn = F\ x F2 x 1 A r t i n n o t e d [A r t47 ] that any a t tempt to carry ou t this p rocedure expe r imen ta 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 lead to v io len t protests a n d d i sc r im ina t i on against m a t h -emat ics . " Figure 2.7: A pure braid, before and after combing. Chapter 2. Braids and Orderings 12 This provides a unique factorization of a pure braid 8 as a product 8 = 8182 • •. 8n-i in which the pure braid fa belongs to Fj. Thus we introduce coordinates in the semi-direct product: 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 gk = 1, where g 1 and k > 0. We may assume w.l.o.g. that g > 1. By invariance, we have g2 > g > 1, and inductively 1 = gk > • • • > 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 conjec-ture (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. 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 vol-ume 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 theo-rem, characterizing the lower central series of the free group Fn. More generally, Vinogradov [Vin49] proved that bi-orderability is pre-served 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'1 where V~l = {p'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~l G V. (Note: the criterion g~lh 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: (3) Normality: for all g EG, gVg'1 C V Clearly, subgroups of right-orderable (resp. bi-orderable) groups are right-orderable (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\, g2 € 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 bi-orderable: simply take the lexicographic ordering: (g, h) < (g', h') <=> (g <G g') or {g = g' and h <H ti). In contrast, consider the following common extension. Suppose G acts on H, the action being denoted by h (->• h9. In this situation, we can define the 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~l are conjugate, and so one is positive if and only if the other one is, a contradiction. We remark here that Neuwirth [Neu74] observed that this example im-plies that the braid groups Bn,n > 3 are not bi-orderable, since the Klein bottle group is a subgroup of the braid group B3, taking x — oio^1 and 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{VH)9 C VH for all g G G.) Proof. Let G and H be bi-ordered groups. Suppose that G acts on H such that {VHy C VH for all g € G. Let V := {(g, h) \ g € VG or {g = 1 and h G VH)Y, i.e., V is the lexicographically positive cone. First we show closure: V • V C V. Let (g, h) and (g1, hi) e V. In the semi-direct product {gg',h9'hi), gg' £ VG because G is orderable. Also h9' e VH since VH is by hypothesis closed under the action of G; since H is also order-able, hP'hl G VH-Next, we show partition: (G x H) \ {(1,1)} = V]\V~L. 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 = Chapter 2. Braids and Orderings 15 [g'1, [h9'1)'1) is in V. Otherwise g = 1 and h £ VH, so h"1 G VH, which means that (1, h)~l = (1, h~l) is in V. Finally, we show normality: (g, h)V(g, h)~l C V. Let (g1, h') G V. Consider the conjugate (g,h) • (g',ti) • {g,hYl = (gg',h9'ti) • (<r\ (h'1)9'1) = (gg'g-\{h9'tih-1)9-). If g' > 1, then since G is orderable, normality implies that gg'g~l G P G / s o the conjugate above is in V. Otherwise g' = 1, so = 1, and (h9'h'h-1)9'1 = {hh'h'1)9'1. Since (hh'h-1) G Pff by virtue of H being bi-ordered, {hh'h,-1)9'1 G P # by as-sumption 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. • 2.3 The Magnus Ordering of the Free Group Fn Let Fn = (x\, • • • , xn) be the free group of rank n. Following Magnus (see for example [MKS76]), we produce a representation of Fn into a ring of power series, via which we can define a bi-ordering of Fn. This ordering appears to have been considered by Magnus as well as others: see [MKS76], Chapter 5, Exercise 5.6.10, and also [Ber90]. Let X(n) denote the ordered set {X1,X2, ...,Xn), and let Z[[X(n)]] be the ring of formal power series in the non-commuting variables X\,... ,Xn. Let //: Fn —t Z[[X(n)]] be the Magnus map, defined on generators by J Xi H + 1 + Xi M: \ xr 1 ^ 1 - Xl + Xi2 - X i 3 + ---A n element of Z[[X(n)]] has the form c 0 + cxW^Xr, ...Xn)+ c2W2(Xl,... Xn) + • • • , Chapter 2. Braids and Orderings 16 where each coefficient Ci is an integer and the monomials Wi(Xi,..., Xn) are strings of powers of the generators. Each term aWi(Xi, • • •, Xn) 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 + W2 - • • •, even when W € 0(1) is itself an infinite series. Magnus goes on to show [MKS76] that the map ti is a representation of Fn into Q: Theorem 2.7 (Magnus) The map p,: Fn —>• Q is injective. We shall use the Magnus map p implicitly to identify Fn with its image, writing x\ = 1 + X\, etc. Definition 2.8 Declare X\ -< X2 -< • • • -< Xn. If v, w are two distinct series in 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 x2 = 1 + X2-The images differ in that xi has coefficient 1 at term X\ while x2 has coefficient 0 in this term. Hence x\ > xi- Similarly, x\ > X2 > • • • > xn > 1. Theorem 2.10 The Magnus order on the ring Z[[X(n)]] induces a bi-ordering on Q and hence on Fn. Proof. We check that V = {w € G \ w > 1} satisfies V • V C V, that G \ {1} = V LI V~x, and zVz~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\,..., Xn) 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. 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'1 contains a term —cW as the first non-constant term. Because c < 0, we have w^1 6 "P. Now let w G 7-> and compute z u i z - 1 for z = 1 + dZ + • • • E Q: zwz~l = (I + dZ + •••)(!+ cW + •• - - dZ + •••) = I + cW + •• • Therefore zwz~l 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. • 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~l > 1. 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 + U2 ) = 1 + V-U + R, where every term of the remainder R = (V — U){—U + U2 — U3 + • • •) has degree exceeding the lowest degree term ofV — U. • We remark here that there exist uncountably many "Magnus-type" bi-orderings on Q, determined by a choice of order on each set of monomials of fixed total degree. In particular, there are n\ inequivalent lexicographic Mag-nus orderings determined by an initial ordering on the list of variables X(n). Theorem 2.12 The Magnus ordering of Fn is preserved under any cp £ Aut(Fn) which induces the identity on H\(Fn) — Fn/[Fn, Fn]. Proof. Consider an automorphism <p: Fn —>• Fn which induces the identity on first homology. That is to say, ip(xi)x~l is in the commutator subgroup Chapter 2. Braids and Orderings 18 [Fn, Fn]. As observed in [MKS76], the image of [Fn, Fn] lies in the subgroup {1+0(2)} oiQ. For convenience, write x\ = <p(xi). The corresponding Magnus expansion is x'i = l + X[ - (1 + 0(2))(1 + Xi) = 1 + Xi + 0(2) and therefore X[ = Xi + 0{2). Now if w = w(xi,..., xn) is a word in the free group Fn, its image under if is w' = w(x[,... ,x'n). The corresponding Magnus expansion (written in ascending order) w =• 1 + c\W\ + C2W2 + ... has image w' = 1 + c\W{ + C2W2 + • • •, where w;(xu--. ,Xn) = WJ(X[,---,X'n) — Wj (A'I , • • • , Xn) + terms of higher degree. It follows that the first non-constant terms of w and w' are identical, and there-fore (p preserves the positive cone of Fn, which is equivalent to being order-preserving. • We observe that a closer examination of this proof shows that for endomor-phisms 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 Pn = F\ ix F2 tx JF3 tx • • • tx F„_i, with terms in the free factors compared using the Magnus order, is a bi-ordering. Proof. The statement is trivially true for P2. We inductively assume that the statement is true for P n - i - Theorems 2.4 and 2.12 show that the Artin ac-tion of Pn-i on Fn-i respects the Magnus order on the second factor of the semi-direct product decomposition Pn = Pn-\ tx Fn-\. 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. • We will refer to this order on Pn as the Artin-Magnus order. 3.2 Properties and Examples We will begin with some examples in P4 = (F\ t< F2) tx F3. An element 0 € P4 will be written 0 = {0i,P2,0z), where each 0i e Fi. The convention for labeling generators of the Fi is explained in Figure 2.3. 19 Chapter 3. A Bi-ordering of Pn 20 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 = ( l , x 2 , l ) = ( 1 , 1 + X 2 , 1 ) . CT3 2 = ( l , l , X 3 ) = ( l , l , l - f - X 3 ) . Figure 3.1: The squares of the elementary generators This shows that o2 > <T22 > 03 2 > 1. In general, cr; 2 > O i + \ 2 N for every power N, illustrating that for n > 2, the Artin-Magnus ordering on Pn is non-Archimedean (as it must be, by Holder's theorem.) (1,0:2 x\ lx2x\,l) 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 r 21 Applying the Magnus expansion to the second coordinate, we have x2~1xi~lX2Xi i - > (1 - X2 + X22 - X 2 3 + • • • )(1 - Xx + X\2 -X^ + •••){! +X2){1 + Xi) = 1 - XXX2 + X2XX + 0{3) Since the first non-constant term is negative, we conclude (ci c ^ - 1 ) 3 < 1-E x a m p l e 3.4 Figure 3.3 shows the generator A 2 of the center of P4. We shall Figure 3.3: The generator A 2 of the center of P 4 refer to this example in Prop. 3.12. The Artin-Magnus ordering is natural in several senses. Consider the in-creasing sequence Pi C P 2 C • • • C Pn C • • • C Poo, where the group is the direct limit. Proposition 3.5 If m < n, the Artin-Magnus ordering of Pn, restricted to Pm, is the Artin-Magnus ordering of Pm. Therefore, this defines an ordering of P^. Moreover, the retraction map f: Pn -> Pn-\ is as order-preserving as possible: 8 < 7 = » f(3) < /(7). Proof. The statement is obvious if one considers the "Artin-coordinate" pre-sentation: Pm extends to Pn via the inclusion map by adding an appropriate number of "identity" coordinates. The retraction map simply deletes the last coordinate. n Chapter 3. A Bi-ordering of Pn 22 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±l. Each Iky : Pn -> Z, 1 < i ^ j < n is additive: Iky (a/3) = Iky (a) + Iky (8). Proposition 3.6 Let 8 be a pure braid with n strands, expressed in Artin coordi-nates: 8 — (Pi,..., pn-i). 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 — Xjti in a word w = w(x\,... ,Xi) equals the coefficient of Xj in the Magnus expansion of w. Second, for j < i, XJJ con-tributes +1 to \kjti+i(P) = \ki+ij(P) and zero to all other linking numbers. • The abelianization functor takes all the braid groups Pn and Bn, n > 2, to infinite cyclic groups. The abelianization map Bn -> Z can be taken to be the total exponent count of a braid when expressed in the generators This map sends Pn to 2Z; in this setting it can also be interpreted as twice the total linking number p ^ 2 T lk(P). —' %j l<i<j<n The abelianization map on Pn 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 Pn = Fi K F2 K F3 K • • • ix F n _ i . Chapter 3. A Bi-ordering of Pr 23 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 set-ting 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 x' < 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. Proposition 3.7 With the Artin-Magnus ordering on Pn and lexicographic order-ing on the product of infinite cyclic groups, the product of abelianization maps Pn = Fi K F2 x • • • x F n _ ! a b l X , , , x a b - 1 ) Z x Z 2 x • • • x Z " - 1 as a mapping, is order-respecting. Moreover, it is compatible with the retraction f: Pn —> Pn-i in that the following diagram commutes: F n f Pn -1 abi x---xab n_i abi x---xabn_2 > Z X Z 2 X • • • X Zn~l projection > Z x Z 2 x • • • x Z n ~ 2 • 3.2.1 Garside Positive Braids In his celebrated solution of the conjugacy problem, Garside [Gar69] intro-duced 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 Pn is Garside positive, then it is also positive in the Artin-Magnus ordering. Proof. The statement is clear for elements of P2. Inductively, suppose that it is true for Pn-i- Let B E Pn be Garside positive, and consider the braid f(B) £ Chapter 3. A Bi-ordering of Pn 24 Pn-\. Note that /(/?) is either Garside positive (case (1)) or has no cross-ings (case (2)). In case (1), applying induction, /(/?) is Artin-Magnus positive, hence B is positive, by definition of the lexicographic order of P n _ i tx F n _ i . In case (2), B is an element of Fn-\. We may assume the first n — 1 strings are straight and read the expression for B in terms of the free generators of F n - i from the places where the nth 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\,..., xn. It follows that its Magnus expansion has positive leading coefficient (occurring at a linear term). Therefore B > 1. • 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 Artin-Magnus 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 Pn of Garside positive braids. We need to show S has a least element. The set /(S) = {/(/?) € Pn-i \ B € S}, being a subset of Pn-i n B*_v has a least element; call it cvo. Let 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 n _ i are 7 = (ao, ao _ 1 7)- We now appeal to Lemma 3.10 to find a 70 € So whose last coordinate ao _ 17o is minimal. Then 70 is the least element of S. • Lemma 3.10 Consider a subset T c F n _ i C Pn of the form T = {ao-'j 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 Pn. Then T has a least element in the Magnus ordering of Fn_\. Chapter 3. A Bi-ordering of P, 25 Proof. The condition ao _ 1 7 G Fn-\ is equivalent to the equation 7(7) = arj. Since ao is in Pn-\, and 7 is Garside positive, we have lkj]n(cvo_17) = lkj ) N(7) > 0. This implies that the coefficients ( g i , . . . , qn-\) of the linear terms in the Magnus expansion of all elements of T are positive, hence there is a lexicographically minimal one, say (qi,..., qn-ij- Let T' = {T€T\T = 1 + Q i X i + • • • g n _ i A V i + 0(2)}. 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\,..., xn_i) of every element of T' is q\ + • • • + qn-i- Each Xi has exponent sum +2 when expanded in the braid generators CTJ. The o-exponent sum is an invariant of braids, and we use it to conclude that for every ao _ 1 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. • 3.3 Comparison with other orderings We compare the Artin-Magnus ordering <AM on Pn with several other order-ings on the braid groups appearing in the literature. 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 Pn-Proposition 3.11 The Artin-Magnus order on Pn extends the Garside partial order on P+. Proof. This follows immediately from Theorem 3.8. • Chapter 3. A Bi-ordering of Pn 26 3.3.2 The partial order of Elrifai and Morton In [EM94], Elrifai and Morton define a partial order on Bn, as follows: for a , (3 £ Bn, 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„ £ Bn to be the "half-twist" braid, defined inductively by A 2 = o\, A n = An_icr„_i •••o\, they show that in their partial order each generator Oi satisfies 1 <EM 0~i <EM A. (3.1) We remark that 1 <EM &i2 <EM A 2 holds also for each generator CTJ, since A = 7i<7j = a j 7 2 , for some 7 1 , 7 2 £ B+. Hence A 2 = 7 I C T J 2 7 2 . This is consistent with the Artin-Magnus order on Pn: Proposition 3.12 For each generator <TJ £ Bn, 1 <AM (Ti2 <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 Pn does not extend the partial order defined by Elrifai and Morton. Let a — o\-02~2- This has Artin-combing (xi,X2~1), hence is positive in the Artin-Magnus ordering. Taking 71 = 0-102 and 7 2 = C ^ C T I , a n 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 _ 1 is also negative in the Artin-Magnus ordering — conjugation by non-pure braids is not order-preserving. 3.3.3 The Dehornoy ordering In 1974, Neuwirth [Neu74] produced an example of a 3-braid which is con-jugate to its inverse, showing that the braid group Bn is not bi-orderable for n > 3 (cf. Example 2.5.) The existence of a one-sided invariant ordering on Bn remained open until 1995, when Dehornoy [Deh95] constructed a left-invariant ordering on Bn. Chapter 3. A Bi-ordering of P, 27 The Dehornoy ordering on Bn may be defined in terms of the generators <Ti, • • • , c r n _ 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 8 = wiOiW20-i • • • wk-\OiWk (3.2) in which each Wj is a word in er^_\, • • • ,On-\- m o m e r words, the genera-tor with the lowest subscript appears with only positive exponent. Then we define a right-ordering by a < 7 iff 7 a - 1 is in the positive cone. (Actually Dehornoy chose his ordering to be left-invariant by using the criterion O J _ 1 7 positive, but the choice is arbitrary and right-invariance seems to dominate the literature on ordered groups.) Ferm et al. give a more geometric view of the same ordering in [FGR+98], where it is noted that Dehornoy ordering, restricted to Pn is not bi-invariant. However, there are similarities between the Dehornoy and Artin-Magnus or-derings. In both orderings we have <J\ » c r 2 2 > CT32 » • • • > 1, where the notation a 3> 8 means that a is greater than all powers of 8. An-other 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 ^ - 1 ) 3 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 Artin-Magnus ordering of Pn. Theorem 3.13 In the Dehornoy ordering, Bn has a least positive element, namely on-\. Similarly, c r n _ i - 1 is the greatest element which is < 1 in Bn. In Pn, on-\2 is the least Dehornoy positive, and c r n _ i - 2 is the greatest element which is < 1 in the Dehornoy ordering. Proof. If a braid has the form of Equation (3.2), call it i-positive, so that 8 G Bn is Dehornoy-positive if and only if it is i-positive for some i = 1,... ,n — 1. To prove the first statement, note that an-\ is (n — l)-positive. Suppose that Chapter 3. A Bi-ordering of Pr 28 there is a 0 € Bn with 1 < 8 < cn-\- Then / ? c r n _ i _ 1 < 1 by right-invariance. Now 8 is i-positive for some i. If i < n — 1 we conclude 0 a n - i ~ l is also z-positive, contradicting 0un^\~1 < 1. On the other hand, if i = n — I, 0 must be a positive power of c r n _ i , contradicting /? < c r n _ i . This establishes the first statement. The other parts follow similarly. • Corollary 3.14 The Dehornoy ordering of Bn is discrete: every element 0 has a unique successor, an-\0, and predecessor, on-\~l0. Similarly, in the Dehornoy or-dering restricted to Pn, a pure braid 0 is the only element of Pn strictly between CT„-I-2/? andon-X2p. Theorem 3.15 For n > 3, the Artin-Magnus ordering of Pn is order-dense: given any two pure n-braids a < 7, there exist (infinitely many) pure braids 0 with a < 0<1-Proof. By invariance, we may assume a = 1. In the free group Fn-\ = {x\,..., xn-i), consider the sequence of commutators {CJ} defined recursively by c i = xix2xi lx2 \ Ck = x\ck-\X\ 1Ck-i : . A simple calculation shows that their Magnus expansions are, in ascending order: ck = 1 + XxkX2 - kX^XzXx + ••• . It follows that each > 1 in the Magnus order of F n _ i , but that —> 1 in the sense that if 1 < w G Fn-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 Pn, consider the sequence of braids {0(k)} with Artin coordinates 0(k) = (l,...,l,c f c). It is clear that given any 7 > 1 in Pn, we have 1 < 0(k) < 7 for all sufficiently large k. • Since for n > 3, Pn with the Artin-Magnus ordering is a countable to-tally ordered set, dense and with no greatest or least element, it is order-isomorphic with the rational numbers, by a classical result. Of course this order-isomorphism cannot be an algebraic isomorphism, as Pn is non-abelian. Chapter 3. A Bi-ordering of Pr 29 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 PN does not extend to any right-ordering on Bn. It also does not extend to a left-invariant ordering on Bn. Proof. We may assume that n = 3. It has already been shown that ( c r i o ^ - 1 ) 3 < 1. A similar calculation shows that (<TI-1<72)3 < 1. If the ordering extends to a right- (or left-) invariant ordering of B$, we must have o-ia2"x < 1 and Ol"102 < 1. Assuming right invariance we conclude 0~\0~2 1 c r i _ 1 c r 2 < 0~\ X02 < 1) which would imply (CTIO^VI - 1^) 3 < 1. But a direct calculation shows {ala2~lcrl-lo2f = ( l , ^ - 1 ^ - 1 ^ - 1 ^ . ^ 2 ) = (l , l + XiA r 2 -r- - - - ) > 1, a contradiction showing no right-invariant extension to B3 exists. If instead we assume left-invariance, we argue that 0\02~lO\~lG2 <0\(T2~l < 1, and reach the same contradiction. • Rhemtulla and Rolfsen have recently shown [private communication] that no right-invariant ordering of Bn can restrict to a bi-invariant ordering of P N . 3.4 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 Cn(C) := {{pi, - • • ,p n) € I Pi Pj for i j}/ the so-called configuration space of n ordered points in C; we give Cn (C) the topology induced from the product topology on C" = Chapter 3. A Bi-ordering of Pn 30 C x • • • x C. Observe that C n(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 n(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 n (C), *) is called an n-strund pure braid; we shall denote 7r i (C n(C), *) by Pn and refer to it as the pure braid group on n-strands. This configuration space is the complement of a finite set of complex hy-perplanes 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 arrange-ments is a deep subject with many unsolved problems, cf. [OT92]. The funda-mental group of the complement of the union of the hyperplanes is an impor-tant 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 Cn (C) is an example of a special class of so-called fibre-type hyperplane arrangements, defined in [FR85]; the pure braid group Pn is then a special case of the groups considered in the following: 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 Mr 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 com-plex plane. Therefore TTI (Mi) = 7r i (MJ_I) X Fd.. Moreover, according to [FR85], proposition 2.5, the action of 7r i (Mj_i) upon Fdi is trivial on Hi(Fdi). It fol-lows, in the same way as Theorem 3.1, that if each free group Fdi is given the Magnus ordering, then the lexicographic ordering on G =* Fdl x Fd2 x Fd3 x • • • x Fdr is bi-invariant. • The symmetric group Sn acts on C n(C) by permuting the n coordinates; the quotient space under this (free) action is Cn(C), the configuration space Chapter 3. A Bi-ordering of P, 31 of n unordered points in C. The fundamental group of this space is Bn, the full n-strand braid group. 3.4.2 Generalized Artin-Magnus orderings A key ingredient in the proof of invariance of the Magnus order of Fn under the Artin action in the decomposition Pn — Pn-\ 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 sub-group called the Torelli group which we will denote by Kn. Theorem 3.18 Let G be an ordered group, and suppose Fn is a free group with the Magnus ordering. Let <p: G —> Kn c Aut(Fn) be a homomorphism. Then the lexi-cographic order onG K V F is a bi-ordering. 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 Pn-i with the Artin-Magnus order, and (p is Artin's braid action. In this case, the image of <p lies in Hn, the subgroup of Aut(F„) consisting of all tp such that ip(xi) is a conjugate of X{, that is, all local conjugations. Clearly Hn is a subgroup of the Torelli group Kn. 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 right-ordering on Bn and the Artin-Magnus ordering for Pn. 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. 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 pro-grams, 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 xhttp: //SunSITE.UBC.CA/Djun/thesis/Java/ 32 Chapter 4. Algorithms for Ordering Braids 33 4.1 The Dehornoy ordering In this section we present some algorithms for computing with the geometri-cally defined version of this right-ordering which appears in [FGR+98]. The basis for these algorithms is a procedure which takes as input an n-braid, 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 2 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 intersec-tion 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 se-quence 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. 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'13 e V, it is straightforward, though not particularly efficient, to determine the relative order of two elements a , 8 in 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 gen-erators via the correspondence ±i >-> of1. For example, the sequence 1 -2 3 -2 maps to o\oi~xo->,o-2~l• Given a braid word cr^cr^2 • • • a\^, where e; is Chapter 4. Algorithms for Ordering Braids 35 ±1, the generators are applied in left-to-right order, that is, c^ 1 is applied first, followed by CT|22 and so on. 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 genera-tor. In order to compute the new curve diagram, one needs only to determine the action of the elementary braid of1 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 of CTJ (resp. o~l) 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. The details of the local action of CTJ are given at the end of this chapter in Tables 4.2 through 4.5. The local action for a , - 1 is similar; the tables for this case may be found with the documentation for the source code for these routines. We note here that C. Rourke and B. Wiest have shown [RW98] that map-ping class groups are order-automatic, i.e., there exists a finite-state automa-ton which takes as input two braids (in a particular normal form which they describe) and decides which is greater in the Dehornoy ordering. This deci-sion takes time linear in the length of the input. 4.2 The Artin-Magnus Ordering The Artin-Magnus ordering on the pure braid group PN is described in Chap-ter 3. We will assume that we are given a pure braid 0 as a finite sequence bi, b2, • • •, 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 order-ing since a <AM 0 iff ct~~l0 € VAM- Of course, a direct comparison would be computationally cheaper. We will compute whether a braid 0 € PN is in the positive cone VAM by combing the braid, obtaining a vector of words in Fx, F2,..., Fn-\. We ex-plicitly compute the Magnus series corresponding to these words, and com-pare the vector against (1 ,1 , . . . , 1) lexicographically, with the i-th factor being compared in the Magnus ordering in Fi. Chapter 4. Algorithms for Ordering Braids 36 The following code fragment recursively computes the Artin decomposi-tion 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) { V e c t o r r e s u l t ; i f (pb.numStrands > 2) { b r a i d p u r e p a r t = p b . r e t r a c t ( 1 ) ; b r a i d f r e e p a r t = ( p u r e p a r t . i n v e r s e ( ) ) . t i m e s ( p b ) ; r e s u l t = A r t i n D e c o m p o s i t i o n ( p u r e p a r t ) ; f r e e p a r t = f r e e C a n o n i c a l F o r m ( f r e e p a r t ) ; r e s u l t . a d d E l e m e n t ( f r e e p a r t . t o F r e e G e n L i s t ( ) ) ; } e l s e i f (pb.numStrands == 2) { r e s u l t = new V e c t o r ( ) ; r e s u l t . a d d E l e m e n t ( f r e e C a n o n i c a l F o r m ( p b ) . t o F r e e G e n L i s t ( ) ) } else { r e s u l t = n u l l ; • } r e t u r n r e s u l t ; } The basis case occurs when pb is a braid of 2-strands, which is already combed, since P2 = Fi = Z ; we return the free word representing pb as an element of Fi . In this case, o\2 = 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)-1pb, 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 n _ i . Computing this last expression is the crux of the matter from an algorith-mic point of view. Define a braid to be free if it is in the kernel of the retraction map / : Pn -» Pn-\. In the code above, freeCanonicalForm() returns a braid which is equivalent to the given free n-braid, but which has no cross-ings 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 repre-sentation as an sequence of free group generators representing the braid. Chapter 4. Algorithms for Ordering Braids 37 The following algorithm puts a free braid into free canonical form. b r a i d f r e e C a n o n i c a l F o r m ( b r a i d i n b r a i d ) { b r a i d r e s u l t = i n b r a i d . f r e e R e d u c e ( ) ; i n t e n d i n d e x = r e s u l t . l e n g t h ; d i s k D = r e s u l t . n e x t E l e m D i s k ( 0 , e n d i n d e x ) ; w h i l e ( D ! = n u l l ) { r e s u l t . u n t w i s t ( D ) ; e n d i n d e x = r e s u l t . l e n g t h ; D = r e s u l t . n e x t E l e m D i s k ( 0 , e n d i n d e x ) ; } r e t u r n r e s u l t . f r e e R e d u c e ( ) ; } 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 lk^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 reduc-ing disk D and untwists the partial result along it, reducing by two the num-ber 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 end-crossings 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 re-ducing 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 3 , we can arrange, by a suitable iso-topy, 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. Finally, given a free n-braid in free canonical form, toFreeGenList () 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 cross-ings, 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\, bib2, b\b2bz,... 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 deter-mine 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. 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 / : Pn —> Pn-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. Figure 4.5:/(cricr2o'ia3CT2CTia1cr3 2cr2CTi<73cr2cri) = cTicr2<Ticr2 2c\020\ Chapter 4. Algorithms for Ordering Braids 41 Case: Before untwist: After untwist: 1 ) < C X * A 2 \ \ 3 \>dy \ / V 4 \l 5 Jx 6 -A-J 1 7 -A/ / 8 / 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 ok on arcs with endpoint k: first 8 cases Chapter 4. Algorithms for Ordering Braids 43 Table 4.3: Action of ak on arcs with endpoint k: remaining 8 cases Chapter 4. Algorithms for Ordering Braids 44 Table 4.4: Action of ak on arcs with endpoint k + l: first 8 cases Chapter 4. Algorithms for Ordering Braids Case: 7.1 7.2 7.3 7.4 8.1 8.2 8.3 8.4 Initial configuration: -1 o k + 1 o< »® o fc+ 1 7* + 1 C H S X O fc + 1 After twist: •o ) ® does not happen no combinatorial change (k + iys o I ® no combinatorial change no combinatorial change Table 4.5: Action of ok on arcs with endpoint k + 1: remaining 8 cases 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 Fn seems to have been known for several decades, the consequences and interpretation of this or-dering, 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. Application of the Magnus ordering to the pure braid groups Pn, via a classical theorem of Artin revealing the semi-direct product structure of these groups, is fruitful, yielding some interesting insights. It is especially inter-esting to compare the resulting Artin-Magnus bi-ordering with the recently discovered Dehornoy ordering on the full braid groups Bn. Although the or-derings appear in many ways compatible, it turns out that they differ funda-mentally, 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 Bn (Theorem 3.16). 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 arrange-ments (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 Bn. It would be interesting to have a similar geometric understanding of the Magnus ordering on Fn. In particular, one way in which automorphisms of Fn 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 Artin-Magnus-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 X then ip preserves the order <G on G."l A further exploration of the connections between the orderings and topol-ogy, which we touched upon in Chapter 3, would be most interesting. In par-ticular, what can be said about ordering various completions of the groups Pn and Bnl 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 = cfjO~i if \i — j\ > 1 (5.1) Cicr; + 1 • • • Oi+iai = Oi+\Oi • • • OiOl+\ i = l , . . . , n - 2 (5.2) > v ' > v ' 2k + 1 factors 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 Bn as the fun-damental group of a configuration space of n points, Bn := n.i (Cn(C)), as dis-cussed in Section 3.4.1. We may substitute any connected manifold M of di-mension > 2 for the complex plane C, obtaining Bn(M) := iti{Cn(F), *), the so-called braid group of the manifold M. For example (see [Bir75]), it is known that Bn(S2), the n-strand braid group of the 2-sphere S2, has a presentation obtained from the standard Artin presentation for Bn by adding the relation Cl • ' • C n _ 2 cr 2 j_ 1 CT„_2 • • • C\ — 1. It is easy to see from this relation that Bn(S2) cannot be ordered. Nev-ertheless it would be interesting to learn what might be said about order-ing more general manifold braid groups. The example of Bn(S2) suggests further difficulties in constructing an analogue of the Artin-Magnus order-ing: it shows that Bn(S2) cannot be faithfully represented as a subgroup of Aut(-?ri(52 \ n points)). We might try to avoid such difficulties by focusing instead on groups which are already represented as subgroups of Aut(Fn). There are many in-teresting groups of automorphisms between the image of Bn under the Artin representation, and the full automorphism group Aut(i?n), including, for ex-ample, the Torelli groups already referred to in Section 3.4.2. 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 run-ning 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 cur-rent 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 un-derlying train track — determining where new "branches" are required, and updating the weights on the arcs. Computing the canonical braid corresponding to the canonical curve di-agram is a relatively easy extension of the present code, which I hope to im-plement. 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 redun-dant, in precisely the same way that unary representation of numbers is much less efficient than chosing a radix > 2. For example, representing the cut se-quences by train tracks would result in only polynomial space storage re-quirements. 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 Hyper planes. 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 J A V A 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 pro-grams. 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 javadoc 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 . CA/Djun/thesis/ java /doc / . 53 Appendix A. An API for Computation with Braids 54 A.1.1 J A V A Application Programming Interface User's Guide This subsection is based in part on Sun Microsystems' J A V A Application Pro-gramming 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 inter-face 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 applica-tion 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 JAVA 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 vari-ables) for that system or entity, and providing methods which operate on that state. Hence, to describe a JAVA program, we must describe the classes which constitute it, and how they interact. In short, classes are specified by describ-ing 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. Gen-erally classes present several constructors, which return more-or-less generic instances, depending on what the application program requires. For exam-ple, 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 as-sociated as a package. For example, all of the JAVA classes which abstract input and output operations are grouped together into the package j ava. io. Pack-ages can in turn contain other packages, yielding a forest of related classes. The code which is presented in this appendix is divided into three pack-ages: • math.alg.PowerSeries • math . topo l .Bra id • 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 * * * Test the random b r a i d rou t ine s i n m a t h . t o p o l . B r a i d . * (aversion $Id : API_users_guide . tex , v 1.1 1999/02/17 $ * ©author Djun Kim <Djun.Kim@SunSITE.UBC.CA> */ p u b l i c c l a s s t e s t r a n d { p u b l i c s t a t i c v o i d m a i n ( S t r i n g a rgs[ ] ) { Random rand_gen = braid.seedRandom(1); b r a i d randombraid = braid . random(6, 20, rand_gen); S y s t e m . o u t . p r i n t l n ( r a n d o m b r a i d . t o S t r i n g ( ) ) ; } } This program would be saved in a file called " t e s t r and . j ava", or per-haps " t e s t r and . jav", if your platform does not support long file names. Running the JAVA compiler j avac t e s t r a nd . 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 Java t e s t r and , 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 57 A.1.5 Class Hierarchy This section gives an overview of the class libraries, showing the hierarchy between its member classes and the core classes of the JAVA Language API. All classes in J A V A implicitly subclass j ava. lang. Ob j ect, so this list can be viewed as a tree, rooted at j ava. lang. Ob j ect. • class j ava . awt. Component (implements Java. 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 graphics .bez ier . PlotCanvas • class math. topo l . B r a i d . braidCanvas (implements Java. awt. event. Act ionListener) • class math. t opo l . B r a i d . CurveDiagram. CutPoint • class math. t opo l . B r a i d . CurveDiagram. CutSequence (implements j ava . lang. Cloneable) • class math. a l g . PowerSeries . Factor • class math. topo l . B r a i d . CurveDiagram. Interva l (implements j ava . lang. Cloneable) • class math . a l g . PowerSeries .NCseries • class math. a l g . PowerSeries . Term • class j ava. lang. Throwable (implements java . io . Ser ia l i zab le ) - class j ava. lang. Exception * class math, topo l . Braid.NoCanvasException * class math. a lg . PowerSeries . VariableOrderExcept ion • 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 pub l i c class Factor extends Object This class represents Factors of Non-commutative power series, having the form (Aj)J. These are represented as a pair ( i n -version: $ Id : math.alg.PowerSeries.Factor. tex,v 1.1 1999/02/1702:12:05 d j u n $ Constructors f Factor p u b l i c F a c t o r ( i n t i n d e x , i n t pow) Constructs a new factor with the given index and degree. Methods • clone p u b l i c O b j e c t c l o n e ( ) Returns a clone of this factor. Appendix A. An API for Computation with Braids Overrides: clone in class Object • getlndex p u b l i c i n t g e t l n d e x ( ) Gets the variable index for this factor • getPower p u b l i c i n t getPower() Gets the variable power for this factor • setlndex p u b l i c v o i d s e t l n d e x ( i n t index) Sets the variable index for this factor • setPower p u b l i c v o i d 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 arbi-trary 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 public i n t numvars The number of variables involved in this series. Constructors f NCseries public NCseries(Vector variables) throws VariableOrderException Appendix A. An API for Computation with Braids 62 Creates a new Non-commutative Power Series in the given variables. The vari-ables 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 4 < X3 < X\ < X2-Throws: VariableOrderException Thrown whenever the variables given are not in the form of a vector of contiguous integers between one and N. Methods • getVariableOrder p u b l i c 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 NCseries plus(NCseries 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 N C s e r i e s 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 N C s e r i e s d i v i d e d _ b y ( N C s e r i e s 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 p u b l i c N C s e r i e s t i m e s ( N C s e r i e s ps2) Returns the product of this NCseries times the given NCseries. Parameters: ps2 - must have the same variables and order as this NCseries • getLength p u b l i c i n t getLength() Gets the length (number of terms) of this NCseries. Appendix A. An API for Computation with Braids 64 • getTruncDeg p u b l i c i n t g e t T r u n c D e g ( ) Gets the t runca t i on degree of this NCseries. • setTruncDeg p u b l i c v o i d s e t T r u n c D e g ( i n t t r u n c D e g ) Sets the t runca t i on degree of th is NCser ies. • trunc p u b l i c N C s e r i e s t r u n c ( i n t d e g ) Returns the resul t of t runca t ing this NCser ies after terms of to ta l degree deg. Assumes this NCser ies is sorted. • insertTerm p u b l i c v o i d i n s e r t T e r m ( T e r m t ) Inser ts the g i v e n T e r m in t o th is NCser ies i n p r o p e r order. Assumes tha t th is NCser ies is sor ted. compare_to p u b l i c i n t c o m p a r e _ t o ( N C s e r i e s p s ) Compares th is NCser ies w i t h the g i v e n NCser ies: re turns -1 i f this is < the g i v e n NCser ies , 0 i f they ' re equal , and 1 i f this > the g i ven NCser ies. sort p u b l i c v o i d s o r t ( ) Sorts the terms of this NCser ies in to ascending order, f i rst b y to ta l degree of the te rms, then b y lex icographic order, based on the g i v e n order of var iables. Appendix A. An API for Computation with Braids 65 • collect p u b l i c v o i d c o l l e c t ( ) Collects like terms in this NCseries. • toString p u b l i c S t r i n g toStr ing() Formats this NCseries as a string and returns the result. Overrides: toString in class Object o toMagnus p u b l i c s t a t i c NCseries toMagnus(Vector vars , in tArray 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 p u b l i c s t a t i c in t compare(NCseries p s l , NCseries ps2) 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 p u b l i c s t a t i c NCseries invert(NCseries ps) Returns the result of inverting the given NCseries. Identity p u b l i c s t a t i c NCseries Ident i ty(Vector var iab les ) Returns an NCseries with the given variable order, representing the identity series. Appendix A. An API for Computation with Braids 66 A.l . l l Class math.alg.PowerSeries.Term j a v a . l a n g . O b j e c t + m a t h . a l g . P o w e r S e r i e s . T e r m ' 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 T e r m ( N C s e r i e s p a r e n t ) Creates a new term for a NCseries of given type. Methods • insertFactor p u b l i c v o i d i n s e r t F a c t o r ( F a c t o r f , i n t posn) Inserts a Factor f into the monomial for this term at the given position. • getMonomial Appendix A. An API for Computation with Braids 67 p u b l i c V e c t o r getMonomial() Returns the monomial of this term. • setMonomial p u b l i c v o i d setMonomial(Vector new_monomial) Sets the monomial of this term to the given monomial. • appendFactor p u b l i c v o i d a p p e n d F a c t o r ( F a c t o r f) Appends a Factor f to the monomial for this term. • getTotalDegree p u b l i c i n t getTo t a l D e g r e e ( ) Gets the total degree of this term. • getCoeff p u b l i c i n t g e t C o e f f ( ) Gets the coefficient of this term. • setCoeff p u b l i c v o i d s e t C o e f f ( i n t value) Sets the coefficient of this term. • compare_to p u b l i c 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 public void reduce(Term t) Reduces the given term, so that adjacent similar variables are coalesced. • times public Term times(Term t2) 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 coef-ficient, but not the sign of the coefficient, to make things easier for higher text formating routines. Overrides: toString in class Object o compare public s t a t i c i n t compare(Term t l , Term t2) 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 pub l i c class braid extends Object Represents braids on -N strands and provides methods to manipulate such A-braids. Version: $ I d : math . topo l .Bra id .bra id . tex ,v 1.1 1999/02/1702:12:05 d j u n $ Copyright: (c)1998-1999 D j u n K i m . The author reserves a l l r ights . Variables | crosslist public intArray crossl ist The b r a i d w o r d : a l ist of e lementary generators. # zerovect public static f inal 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 p u b l i c s t a t i c boolean 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 p u b l i c i n t getNumStrands() Returns the braid index (number of strands) of this braid. • setNumStrands p u b l i c v o i d setNumStrands(int numStrands) Sets the braid index (number of strands) of this braid. • embed p u b l i c b r a i d embed() Returns this braid naturally embedded in a braid with one more strand. retract p u b l i c b r a i d r e t r a c t ( i n t k) Returns the k-fold retraction of this braid, that is, the braid resulting from delet-ing the last k strands. Assume that this braid has been threaded. Returns null if such a retraction is undefined. inverse p u b l i c b r a i d i n v e r s e ( ) Returns the inverse of this braid. times Appendix A. An API for Computation with Braids 72 p u b l i c b r a i d t imes(braid b) Returns the product (this braid)*(b). Doesn't attempt to reduce the result. • freeReduce p u b l i c v o i d freeReduce() Reduces this braid, in the free group. Also removes any zero entries. • untwist p u b l i c v o i d untwis t (bra id . d i sk D) Untwists an "innermost" twist of form af1 ••; (other generators involving strand n) • • • af1, where Ok and a( involve strands i and j, and are opposite in sign. Parameters: startindex - points to the crossing endindex - points to the crossing ae. • ArtinDecomposition p u b l i c Vector ArtinDecomposit ion(braid pb) Returns a Vector of intArrays, which represents the fully combed form of the given (pure!) braid. comb p u b l i c 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 73 p u b l i c b r a i d freeCanonicalForm(braid inbraid) Returns a b r a i d w h i c h is equ iva lent to th is b r a i d , b u t w h i c h is presented as a p r o d u c t of free g r o u p generators. This assumes that this b r a i d is i n fact an e lement of the n o r m a l s u b g r o u p of the p u r e n-s t rand b r a i d g r o u p w h i c h is the ke rne l of the re t rac t ion m a p , i n the f o r m of a p r o d u c t of the free ( A r t i n ) generators. N o check ing is done on i n p u t ! See Also: retract • getPermutation . p u b l i c in t [ ] getPermutation() Returns the p e r m u t a t i o n of this b ra id . The p e r m u t a t i o n is g i v e n as an ar ray of 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 of the b r a i d o n the a r ray [0,..., numSt rands ] . o seedRandom p u b l i c s t a t i c Random seedRandom(long seed) In i t ia l izes the p s e u d o - r a n d o m b r a i d generator w i t h the g i v e n seed va lue of type long . This re turns an instance of class R a n d o m , w h i c h is a " h a n d l e " to 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() In i t ia l izes the p s e u d o - r a n d o m b r a i d generator w i t h a " r a n d o m " va lue (g i ven b y the system clock). o random Appendix A. An API for Computation with Braids 74 p u b l i c s t a t i c b r a i d random(int index, in t 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 see-dRandom. 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 p u b l i c v o i d 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 p u b l i c S t r i n g toString() Returns a string representation of this braid. Overrides: toString in class Object Appendix A. An API for Computation with Braids 75 • toTeXForm p u b l i c S t r i n g toTeXForm() Returns a St r ing representat ion of this b r a i d , f o r m a t t e d as TeX inpu t . • toFreeGenList p u b l i c i n t A r r a y t o F r e e G e n L i s t ( ) Returns a l ist ( i n t A r r a y ) representat ion of this b r a i d , as a sequence of free gen-erators. This assumes that this b r a i d has a l ready been p u t i n to the app rop r ia te f o r m b y a cal l to f reeCanonica lForm. The generators are g i v e n b y Xi = ak<rk-\ •: • o\cr^\ • • • 1 w h i c h is represented as i. The inverse is g i ven b y —i. • toFreeGenTeXForm p u b l i c S t r i n g toFreeGenTeXForm() Returns a St r ing representat ion of this b r a i d , w r i t t e n as a s t r ing of free gener-ators. This assumes that this b r a i d has a l ready been p u t i n to the approp r ia te f o r m b y a cal l to f reeCanonica lForm. The generators are g i ven b y Xi = okOk-\ • • • o2iOT+i •••'Tk1 initPolys p u b l i c v o i d i n i t P o l y s ( ) In i t ia l izes the var iables requ i red for the p o l y n o m i a l computa t ions . Th is m e t h o d m u s t be cal led before any p o l y n o m i a l m a y be calculated. Since i t in i t ia l izes an s t ructures w h i c h are fac tor ia l ly large i n the size of the i n p u t , i t m a y con-sume s igni f icant compu ta t i ona l resources. Once the g loba l tables are in i t i a l -l i zed , however , subsequent p o l y n o m i a l computa t ions are fast. two_variable Appendix A. An API for Computation with Braids 76 p u b l i c v o i d two_variable(PrintWriter out, Str ingBuffer bra ids tr ) C o m p u t e s the two-var iab le 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 dbinomial( int k, in t kl) Returns large b i n o m i a l coeff icient ( — l ) f e l x k\/kl\(k - kl)\ o factorialExpansion p u b l i c s t a t i c int [ ] fac tor ia lExpans ion( in t g, in t r l ) Returns the factor ia l expans ion of g d o w n to the ( r l - l ) - t h pos i t ion . o binomial p u b l i c s t a t i c i n t b inomia l ( in t v, i n t v l ) Get sma l l b i n o m i a l coeff icient (n choose k) as an in t , fo r sma l l va lues of 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 .bez ier .P lotCanvas + math. topol .Braid.braidCanvas p u b l i c class braidCanvas extends P lo tCanvas i m p l e m e n t s Ac t ionL is tener Class braidCanvas encapsulates the data and methods required to draw braids and to interact with them on the screen. Version: $ Id : math . topo l .Bra id .bra idCanvas. tex ,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 braidCanvas(Applet a, Act ionLis tener al) f braidCanvas p u b l i c braidCanvas(Applet a, Act ionLis tener a l , i n t width, i n t height) Methods • initGfx p u b l i c v o i d in i tGfx( ) Initializes the graphics. • paint p u b l i c v o i d paint(Graphics g) Calls update to refresh the canvas with the image of the braid. Overrides: paint in class PlotCanvas • register p u b l i c v o i d r e g i s t e r ( b r a i d 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 vo id 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 p u b l i c vo id toPos tScr ip t (bra id b) Generates PostScript output which draws this braid. • drawBraid p u b l i c vo id drawBraid(braid 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 . We assume that the p o p u p m e n u has h a d a l l o f i ts m e n u i tems a d d e d , a n d that each has an act ion l istener de f ined i n another class. • processMouseEvent p u b l i c v o i d processMouseEvent(MouseEvent e) Takes care of MouseEvents i n this b ra idCanvas. Pops u p the P o p u p M e n u ; mos t o ther events get passed ups t ream to superclasses of th is class. Overrides: processMouseEvent i n class C o m p o n e n t • actionPerformed p u b l i c v o i d actionPerformed(ActionEvent e) Takes care of Ac t ionEven ts i n this b ra idCanvas. E v e r y t h i n g here gets d ispa tched t o the act ionLis tener w h i c h is s u p p l i e d i n the const ructor to th is 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 ava . l ang .Obj ect + ma th . topo l .Bra id .CurveDiagram.Cu tPo in t p u b l i c class CutPoint extends Object Implements a geometric cut point in a cut-sequence for a braid curve diagram. Version: $Id : math . topo l .B ra id .CurveDiagram.CutPo in t . tex ,v 1.1 1 9 9 9 / 0 2 / 1 7 0 2 : 1 2 d j u n Exp d jun$ Copyright: (c)1998-1999 D j u n K i m . The au thor reserves a l l r ights . Variables \ integral p u b l i c boolean i n t e g r a l X direction p u b l i c i n t d i r e c t i o n X next p u b l i c Cu tPo in t next X prev p u b l i c Cu tPo in t prev Appendix A. An API for Computation with Braids 82 X xpos p u b l i c f l oa t xpos Constructors f CutPoint p u b l i c CutPoint() Methods • copy p u b l i c CutPoint copy() Returns a copy of this CutPoint. • toString p u b l i c S t r i n g toString() Returns a String representing this CutPoint. Overrides: toString in class Object Appendix A. An API for Computation with Braids 83 A.1.15 Class math.topol.Braid.CurveDiagram.CutSequence j a v a . l a n g . O b j e c t + math . topol .Braid .CurveDiagram.CutSequence pub l i c class CutSequence extends 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: $ Id : 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 . The au thor reserves al l r ights . Variables t start p u b l i c Cu tPo in t s t a r t X end p u b l i c Cu tPo in t end X braidword p u b l i c S t r i n g bra idword # ColArray Appendix A. An API for Computation with Braids 84 p u b l i c s t a t i c C o l o r C o l A r r a y [ ] The sequence of colors used to differentiate images of the original intervals under the braid automorphism. Constructors f CutSequence p u b l i c C utSequence(int index) Returns a new, empty cutsequence of the given index. Methods • setHole p u b l i c v o i d s e t H o l e ( C u t P o i n t entry, i n t index) • setlnterval p u b l i c v o i d s e t l n t e r v a l ( I n t e r v a l entry, i n t index) • getlndex p u b l i c i n t g e t l n d e x ( ) o trivial p u b l i c s t a t i c CutSequence t r i v i a l ( i n t index) Returns the "trivial" CutSequence for the given index. • twistBy p u b l i c CutSequence t w i s t B y ( i n t 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 p u b l i c v o i d delete(CutPoint del) Delete the CutPoint del. • insertAfter p u b l i c v o i d inser tAfter (CutPoint newpoint, CutPoint here) Insert the CutPoint newpoint after CutPoint here. • insertBefore p u b l i c vo id insertBefore(CutPoint newpoint, CutPoint here) Appendix A. An API for Computation with Braids 86 Inser t the C u t P o i n t n e w p o i n t before Cu tPo in t here. • toString p u b l i c S t r i n g toStr ing() Returns a S t r ing represent ing th is CutSequence. Overrides: toSt r ing i n class Object • PSOutput p u b l i c v o i d PSOutput() Wri tes PostScr ipt code w h i c h d r a w s the Canonica l C u r v e D i a g r a m fo r this Cu t -Sequence to 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 i m p l e m e n t s Cloneable Implements a list of CutPoints in an interval. Does not include the CutPoints which are endpoints of the interval. Version: $ I d : In terva l . java,v 1.6 1 9 9 9 / 0 2 / 1 2 20:38:50 d j u n Exp d j u n $ Copyright: (c)1998-1999 D j u n K i m . The au thor reserves a l l r igh ts . Constructors t Interval p u b l i c I n t e r v a l ( i n t anchor) Methods • elements p u b l i c Enumeration elements() Returns an e n u m e r a t i o n of the CutPo in ts i n this in terva 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 vo id reverse() Reverse the order of elements in this interval. • respace p u b l i c vo id 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 p u b l i c S t r i n g 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 math. t o p o l . B r a i d . b r a i d C a n v a s Takes care of Ac t ionEvents i n this b ra idCanvas. a d d P o p u p (PopupMenu) . 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 A d d a p o p u p m e n u . addTerm(Term). 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 A d d s a t e r m to this NCser ies. appendFactor(Factor). M e t h o d i n class math. a l g . P o w e r S e r i e s . Term A p p e n d s a Factor f to the m o n o m i a l for this te rm. ArtinDecomposit ion(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 Returns a Vector of i n t A r r a y s , w h i c h represents the f u l l y c o m b e d f o r m o f the g i v e n (pure! ) b r a i d . B binomial ( int , in 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 Get smal l b i n o m i a l coeff icient (n choose k) as an int , fo r sma l l va lues of k. braid ( int) . Const ruc tor fo r class math. t o p o l . B r a i d . b r a i d Creates an e m p t y b r a i d w i t h the g i v e n n u m b e r of strands. braid ( int [ ] ) . Cons t ruc to r fo r class math. 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 the g i v e n w o r d i n the s tandard generators (e lementary b ra ids ) , g i v e n as an in t [ ] array. bra id ( in tAr ray ) . Const ruc tor fo r 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 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 . -Bra id .b r a idCanvas C clone(). Method in class math, a l g . PowerSeries . Fac to r Returns a clone of this factor. ColArray. Static variable in class math. t o p o l . B r a i d . braidCanvas collect(). Method in class math. a l g . PowerSeries . NCser ies 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 . PowerSeries . -NCser ies 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 91 compare.to(NCseries). M e t h o d i n class math. a l g . PowerSeries . NCser ies Compares this NCser ies w i t h the g i ven NCser ies: re turns - . 1 i f this is < the g i v e n NCser ies , 0 i f they ' re equal , a n d 1 i f this > the g i ven NCser ies. 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 th is t e r m w i t h t e r m t: re turns - 1 i f th is < t, 0 i f they ' re equal , a n d 1 i f this > t. crosslist. Var iable i n class math. t o p o l . B r a i d . b r a i d The b r a i d w o r d : a l ist of e lementary generators. D dbinomial( int , in 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 Returns large b i n o m i a l coeff icient ( — l ) f c l x k\/kl\(k - kl)\ DefaultTruncDegree. Static var iab le 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 dividedJby(NCseries). 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 Returns the resul t o f d i v i d i n g this NCser ies b y the g i ven NCser ies. 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 the b r a i d . drawBraid(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 D r a w s g i v e n b r a i d i n this b ra idCanvas. 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 lementary generator at the g i ven basepoint . Appendix A. An API for Computation with Braids 92 embed(). M e t h o d i n class math. topol. Braid. braid Returns th is 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 s t rand. Factor(int, i n t ) . Cons t ruc to r fo r class math. a l g . PowerSeries . Factor Const ruc ts a n e w factor w i t h the g i ven i ndex a n d degree. factorialExpansion(int, in t ) . Static m e t h o d i n class math. topol. Braid.braid Returns the fac tor ia l expans ion of g d o w n to the ( r l — l ) - t h pos i t ion . freeCanonicalFormfbraid). M e t h o d i n class math. topol. Braid. b r a i d Returns a b r a i d w h i c h is equ iva lent to this b r a i d , b u t w h i c h is presented 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. topol. Braid. braid Reduces th is b r a i d , i n the free g roup . G getCoeff(). Method in class math. a l g . PowerSeries . Term Gets the coefficient of this term. getlndex(). Method in class math. a l g . PowerSeries . Fac to 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 93 getLength(). M e t h o d i n class math. a l g . PowerSeries . NCser ies Gets the leng th (number of terms) of this NCseries. getMonomial(). M e t h o d i n class math. a l g . PowerSeries . Term Returns the m o n o m i a l of this te rm. 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 Returns the b r a i d index (number of strands) of 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 Returns the p e r m u t a t i o n of this b r a i d . getPower(). M e t h o d i n class math. a l g . PowerSeries . Fac to r Gets the var iab le p o w e r fo r this factor getTotalDegree(). M e t h o d i n class math. a l g . PowerSeries . Term Gets the to ta l degree of this te rm. getTruncDeg(). M e t h o d i n class math. a l g . PowerSeries . NCser ies Gets the t runca t ion degree of this NCseries. getVariableOrder(). M e t h o d i n class math. a l g . PowerSeries . NCser ies Returns the var iab le order of this NCser ies, 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 Returns an NCser ies w i t h the g i ven var iab le order, represent ing the 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 In i t ia l izes the var iables requ i red fo r the p o l y n o m i a l computa t ions . 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 In i t ia l izes the graphics. insertFactor(Factor, in 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 to the m o n o m i a l fo r this t e r m at the g i v e n pos i t ion . 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 Inserts the g i v e n T e r m i n t o th is NCser ies 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 Returns the inverse 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 Returns the resul t of i n v e r t i n g the g iven NCser ies. isPure(braid). 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 Returns t rue i f a n d on l y i f the g i ven b r a i d is a p u r e b r a i d . M minus (NCser ies) . 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 Returns the resul t of subt rac t ing a g i ven series f r o m this NCser ies. N NCseries(Vector). Const ruc tor fo 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 Power Series i n the g i v e n var iables. NoCanvasException(Str ing). Const ruc tor for class m a t h , t o p o l . B r a i d . N o C a n v a s -E x c e p t i o n numvars. Var iable 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 The n u m b e r of var iables i n v o l v e d i n this series. Appendix A. An API for Computation with Braids 95 P paint(Graphics). 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 Cal ls u p d a t e to refresh the canvas w i t h the image of the b r a i d . plus (NCseries). M e t h o d i n class math. a l g . PowerSeries . N C s e r i e s Returns the resul t of a d d i n g ps to this NCseries. processMouseEvent(MouseEvent). 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 Takes care of MouseEvents i n this b ra idCanvas. R random( int , in 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 Returns a p s e u d o - r a n d o m b r a i d of g i ven index, of l eng th less than or equa l to the g i v e n length . random( int , 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 Returns a p s e u d o - r a n d o m b r a i d of g i v e n index. reduce(Term). M e t h o d i n class math. a l g . PowerSeries . Term Reduces the g i v e n t e r m , so that adjacent s imi lar var iables are coalesced. register(braid). M e t h o d i n class math. t o p o l . B r a i d . braidCanvas Registers th is b r a i d w i t h the canvas so that va r ious opera t ions can d ispense w i t h such operat ions as th read ing the b ra id . 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 Returns the k - fo ld re t rac t ion of th is b r a i d , that is, the b r a i d resu l t i ng f r o m delet-i n g the last k strands. Appendix A. An API for Computation with Braids 96 S seedRandom(). Static method in class math. t o p o l . B r a i d . b r a i d Initializes the pseudo-random braid generator with a "random" value (given by the system clock). seedRandom(long). Static method in class math. t o p o l . B r a i d . b r a i d Initializes the pseudo-random braid generator with the given seed value of type long. setBraid(intArray). Method in class math. t o p o l . B r a i d . b r a i d Sets this braid 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 in class math. a l g . P o w e r S e r i e s . Term Sets the monomial of this term to the given monomial. setNumStrands(int). Method in 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). 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 power for this factor setTruncDeg(int). Method in 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(). Method in 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 by total degree of the terms, then by lexicographic order, based on the given order of variables. Appendix A. An API for Computation with Braids 97 T Term(NCseries). Const ruc tor for class math. a l g . PowerSeries . Term Creates a n e w t e r m for a NCser ies of g i ven type. th read( ) . 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 representat ion of this b r a i d as a vector of crossings, w i t h each crossing reco rd ing its index , 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 pos i t i ve or a negat ive 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 Returns the p r o d u c t ( this bra id)* (b) . t imes(NCser ies) . M e t h o d i n class math, a l g . PowerSeries .NCser ies Returns the p r o d u c t o f this NCser ies t imes the g i v e n NCser ies. times(Term). M e t h o d i n class math. a l g . PowerSeries . Term Returns the p r o d u c t (non-commuta t i ve ! ) of this t e r m w i t h the g i v e n t e r m . toF reeGenL is 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 Returns a l ist ( i n t A r r a y ) representat ion of this b r a i d , as a sequence of free gen-erators. toFreeGenTeXFormQ. 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 a S t r ing representat ion of th is b r a i d , w r i t t e n as a s t r ing of free genera-tors. toMagnus(Vec to r , i n t A r r a y ) . Static m e t h o d i n class math. a l g . PowerSeries . -NCser i e s Returns 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 var iab le order g i v e n b y vars) g i v i n g the M a g n u s representat ion of w o r d i n the free g r o u p . toPos tSc r ip t fb ra id ) . M e t h o d i n class math. t o p o l . B r a i d . braidCanvas 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 Returns a s t r ing representat ion of this b ra id . toString(). M e t h o d i n class math. a l g . PowerSeries . NCser ies Formats this NCser ies as a s t r ing a n d re turns the result. toString(). M e t h o d i n class math. a l g . PowerSeries . Term Formats this t e r m as a s t r ing and re turns 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 Returns a St r ing representat ion of 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 .NCser ies Returns the resul t o f t runca t ing this NCser ies after te rms o f to ta l degree deg. two_variable(PrintWriter, St r ingBuf fer ) . 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 o m p u t e s the two-var iab le p o l y n o m i a l f r o m a b r a i d . U untwist(braid. d isk) . 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 an " i n n e r m o s t " tw is t o f f o r m erf1 • • • (other generators i n v o l v i n g s t rand ri) ••• of1, w h e r e crfc a n d i n v o l v e st rands i a n d j , a n d are oppos i te i n s ign. update(Graphics). M e t h o d i n class math. t o p o l . B r a i d . braidCanvas U p d a t e this image. V VariableOrderException(String). Const ruc tor for 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 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 R-module, 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 xv > y. class: The J A V A 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. 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 Tigi where ri e R and gi € G; we can multiply two such sums: ngi ]T rjgj = Y nrj9i9j-i j hj 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': S1 —> S 3 to be equivalent if there is a self-homeomorphism h: S3 -r S3 such that K — h(K'). An equiv-alence class under this relation is called a knot. Under the same equivalence relation, the space of continuous maps L: S1 TJ • • • TJ S1 -> S3 is partitioned into links. r ing: 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 : (x + y)z = 2:2 + and 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 pre-cursors. 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 prac-titioner of typography, passionately concerned with the broadest principles and tiniest details of his chosen art and craft... ." (Robert Bringhurst, Intro-duction, 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 defi-nitions 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 post-processed into encapsulated PostScript. Several additional figures were pro-duced 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 au-thor. The bibliography was generated by BibT^X from bibliographic database (. b i b file) entries retrieved from the AMS's WWW-based MathSciNet Math-ematical 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 Page : = is defined to be 3 Bn n-strand braid group 6 Bi Garside positive braids 23 Hi(G) first homology of the group G 11 Pn n-strand pure braid group 8 Qn set of n marked points 8 RG the i?-group ring of G 12 Sn Symmetric group on n-letters 7 Bn n-times punctured disk 8 A 2 the generator of the center of Pn 21 Fn free group of rank n 8 G series in Z[[X(n)]] with constant term 1 16 V positive cone 13 M 3 Euclidean 3-space 6 a » B a is greater than all powers of B 27 i: Pn-1 «-»• Pn natural inclusion 10 ir(B) the permutation of the braid B 7 i-th elementary generator 7 • Q.E.D. (end of proof) 3 f'-Pn-* Pn-l "forget the n-th strand" retraction map 10 103 Index of Notation 104 Symbol Meaning Page j-th free generator of Fi 10 0(d) terms of total degree > d 16 z the ring of integers 7 Z[[X(n)]] ring of formal power series over Z 15 X(n) ordered set of n non-commuting variables 15 A u t ( F n ) Automorphism group of the free group 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 Bn, 8 -Magnus order, 1-2,19 automorphism, 8-9 axioms, 1 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 canonical curve diagram, 33 chaos, 19 clockwise, 8 closure, 13,14 coefficient, 16 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 elementary, 37 elementary reducing disk, 37 errors, viii Euclidean 3-space, 6 extensions, group, 13 Falk, Michael, 2, 30 Ferrer, Horacio, 5 fibrations, 30 fibre, 30 font, 3-4,101 The Form of the Book, 101 Fournier, Pierre, 19 free braid, 10, 36 free canonical form, 36 freeCanonicalForm(), 36 105 Index 106 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 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 Zapf, Hermann, 101 zero-divisors, 12 left, 100 right, 100 Wall; Larry, 53 well-ordered, 24 Vinogradov, 12 units, 12 . untwisting, 38-39 Pt-algebra, 99 Randell, Richard, 2, 30 representation, 10 of Fn, 15 retraction, 10, 21, 23, 36 ring, 100 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 toFreeGenList (), 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
- 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 |
FileFormat | 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 |
GraduationDate | 1999-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | 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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0079908/manifest