• No results found

PDF srvubudsp002.uct.ac.za

N/A
N/A
Protected

Academic year: 2023

Share "PDF srvubudsp002.uct.ac.za"

Copied!
114
0
0

Loading.... (view fulltext now)

Full text

This thesis focuses on the evolution of solutions to the conjugation search and decision problems for random braids. We are also looking at improving the super top set solution that uses the lowest common denominators.

Mathematical braids

Geometric braids

Finally, we can conclude that the set of all possible braids on strands forms a group under the chaining of braids. As we already mentioned in the first description of braid chaining, the ann-braid can only be combined with the second-braid - the number of strands cannot be mixed when chaining.

Algebraic braids

There are two relations that we must impose in order to have a complete representation of the algebraic lattice group. Since the group of algebraic braiding in n threads is isomorphic to the group of geometric braiding in n threads, we will also denote it by Bn.

The braid conjugacy problem(s)

A group of B1 braids on 1 strand contains only one element - a single strand that goes straight down, as there are no other strands to cross. 4 In his paper, Garside uses Cayley's diagrams to illustrate all the different ways in which the word W could be 'constructed'; I omit this and related terms for brevity.

Figure 2.1Artin proposes a normal form for braids in [Art47b]. With this
Figure 2.1Artin proposes a normal form for braids in [Art47b]. With this

The canonical form(s)

Improvement from Joan Birman’s seminal braid textbook

Birman introduces the idea of ​​a "cyclic diagram" and the "cyclic permutation" of a braid, which I consider a precursor to the cycling operation introduced by El-Rifai and Morton (we see it in the next section). The cycling operation of El-Rifai and Morton is widely used in subsequent solutions and inspired related operations that enabled even more improvements. Note that the statement in the original textbook has a stronger statement, but an errata [Bir82].

If P ∼=AB, then the positive word BA is called a cyclic permutation of P, and the positive word Bτ(A) is a reflected3 cyclic permutation of P. The cyclic diagram C(∆mP) of ∆mP is a list of positive words in Bnsuch dat. ii). If one of the elements in the cyclic diagram of W contains a factor ∆, we say: “the cyclic diagram contains ∆”, as in the statement of the theorem.

In particular, the reflected cyclic permutation of σ3·σ12 and σ32·σ1 both gives σ31, and the reflected cyclic permutation of σ21·σ3 and σ1·σ23 both gives σ33. This example that we considered does not lead to the appearance of a factor Δ in the cyclic diagram. However, if we have an element of the form C1∆C2 for some positive C1, C2 in the cyclic diagram of W = ∆mP, it means that there exists an element conjugate to W such that W.

The super summit set

From this we have that the canonical lengthℓ(P) = supP−infP is the number of factors remaining when all ∆'s have been joined to the left in the left-canonical form of a positive concatenation. Therefore, we have identified infB and supB for a general splicingB in terms of the left-canonical form of an appropriate positive splicing. Thus, we can identify at least one element of the supersummit of X by cycling and decycling without computing the entire supersummit of X.

The following algorithm allows us to cycle to find a representative ˜X of the top set of X, thus finding the maximum value of inf for the conjugation class. The following algorithm finds a representative of the supertopset using the previous algorithm and decycling, finding the minimum canonical length for the conjugation class of X. The equivalent definition for the left-canonical form is not given in the text, but is easy to translate to the left: the factorization V =V1V2.

Vr for V ∈ Bn+ is in left-canonical form if every Vj is in Sn and Vj is the largest element (w.r.t ≼) of Sn satisfying Vj ≼VjVj+1. A word braid is in mixed canonical form if the word braid is of the minimum word length of the form U−1V, where U and V are both positive and in left canonical form. Vk are braids in left canonical form, then U−1V is in mixed canonical form if and only if.

Garside groups

Thinking back to the braid group, it is clear that the basic braid is the Garside element of Bn+, which is a Garside monoid. Finally, a group G is called a Garside group if it is the group of fractions4 of a Garside monoid. Left lcm∨, left gcd ∧, right lcm∨↰, and right gcd∧↰ are defined in the same way as before, but for elements of G, with the result of each of these operations also in G.

An element a joins a line with an element b in the line above if and only if a ≼ b. Furthermore, we can use this diagram to find the left gcd (or left lcm) of any two simple braids. We used (iii) and (iv) in Section 4.1 to help us find the left gcd and left lcm of the two braids, by the method for finding the right lcm and right gcd.

The inverse notation for the left complement makes sense if we consider ∂ as a map from S to S. We can use this definition of left-weightedness and see that for u ∈ M the first factor in the left-normal form of u∧∆ will be. The right complement is useful in finding the left-normal form of an element's inverse.

Minimal simple elements

Sv≥m is the set of the smallest simple element among those conjugate v to the element v C≥m(x). SvSSS is the set of minimal simple elements among those conjugate v to an element in SSS(x). The appropriate set of minimal simple elements depends on the element C≥m(x) or SSS(x) at hand.

Now, takev∈C≥m(x), put an atom of M and consider the set. i.e., the set of simple elements satisfying Pv≥m also having the atom a as a prefix). Both of these rely on a third algorithm, which finds minimal simple elements for the ultra peak set. Gebhardt also introduces simple minimal elements for the ultra-summit group, in a similar way as done in [FGM03].

We also have3 SyUSS = min(SPUSS . y ), the set of minimal simple elements that conjugate y∈ USS(x) to another element in USS(x) (we let PyUSS be the property “conjugates y∈USS(x) to another element in USS(x)” for simple elements). So we have the following algorithm to determine the ultratop set of an element. So the rest of this section is devoted to these minimal, simple elements for the ultra-top kit.

Partial cycling and partial twisted decycling

The core of the improved solution is that it is faster to determine one of these components than the entire USS. In particular, x and y are conjugate if and only if the intersection of the black component of x and the gray component of y is not empty. A result from the first article in the trilogy is highlighted at the beginning of the section we are discussing.

Then one and only one of the following conditions applies: ii) φ(x)s are left-weighted as written. In the case we consider, the subgraphs have the same vertex as the original graph, but only a subset of the edges of the original graph. We will use it and apply it to representatives of the elements for which we are solving the conjugation problem.

We see a new subset of the conjugation class, the set of slip rings, which is a subset of the ultra-summit set. In particular, it replaces cycling and decycling to allow us to find a representative of the supersum set (with only one kind of conjugation!), and repeated cyclic sliding eventually reaches a period, which we use to insert the set of sliding rings to build in a similar way as the ultra-summit is built by cycling. The difficult part of the above procedure is to find the entire SC(x).

Let N be the length of the sliding circle y. ii) If fu̸≼tza all t∈F(r), then κu is not an indecomposable conjugator beginning aty (i.e., not minimal with respect to. Note that the logic of this algorithm has been slightly adapted for consistency with the other algorithms in this dissertation.

Cycling and decycling changing the canonical length

We can make an educated guess about the results of some of the calculations, based on our understanding of the left and right gcd and left and right lcm. Even if we didn't realize it, we can see that both braids can end up with the braid σ−11 σ3σ2, where the remaining factor is positive at the beginning; so the real gcd is σ1−1σ3σ2 =X1. If we rewrite X2 as σ1−1σ3σ3σ2 (due to the first braid ratio), we see that both braids can start withσ−11 σ3 so that the factor left at the end is positive.

We will need to concatenate factors to the right of both X1 and X2 to create a multiple that can start with either concatenation. We need to move the positive crossing down so that the two negative crossings occur first.

Finding a minimal simple element in USS(x) using transports and pullbacks . 101

We consider the plot of γX for a few different braids of X to get an idea of ​​what this plot might look like, paying attention to the black and gray arrows (corresponding to partial cycling and partial twisted decycling, respectively). Algorithms 5.2.14 and 5.2.15 can be used repeatedly until all nodes and arrows in the graph are created. We are more interested in the structure of the graphs in these cases, as it adds intuition to many of the results discussed in Section 5.2.

In this case, each black arrow is a cycling and each gray arrow is a twisted decycling. The labels of the gray arrows are not given in the example, but since the authors say that the gray arrows correspond to twisted decyclings, we can find the labels of the gray arrows as∂(φ(·)). For space considerations, I have retained the right complement notation if the final result is too long to fit in the diagram.

Now each arrow is bi-colored, because each conjugation corresponds to both a partial cycle and a partial twisted decycling. USS(Y) has 12 elements (each also with canonical length 1) and there is 1 black component and 1 gray component in γY. In this case, the black arrows correspond to partial cycles, the gray arrows correspond to partially twisted decyclings, and where they occur simultaneously (that is, the two-tone arrows) the conjugation corresponds to both.

Finding a minimal simple element in SC(x) using transports and pullbacks . 105

To use the equation, however, we also need to find all si(p−1Y p) and their associated prefixes.

Corrections

In minimal simple elements for SSS(x) paper

In USS(x) paper

Figure

Figure 2.1Artin proposes a normal form for braids in [Art47b]. With this
Figure 2.4 illustrates statement (i) for σ 3 ∆ = ∆τ (σ 3 ) = ∆σ 2 in B 5 . I like to think of ∆ as a twisted ribbon which delivers σ i from the top to τ (σ i ) = σ n−i at the bottom.

References

Related documents

The reports and statements set out below comprise the annual financial statements presented to the Council: Page Accounting Officer's Responsibilities and Approval 4 Statement of