knot theory more prominent; a bit more on Alexander's thm; -Mathworld link as not helpful |
m →Some properties: typo in what I added |
||
(2 intermediate revisions by the same user not shown) | |||
Line 86: | Line 86: | ||
== Some properties == |
== Some properties == |
||
The groups ''B''<sub>0</sub> and ''B''<sub>1</sub> are trivial; ''B''<sub>2</sub> is already infinite and [[group isomorphism|isomorphic]] to the infinite [[cyclic group]] '''Z'''. ''B''<sub>3</sub> is a quite complicated non-[[abelian group|abelian]] infinite group ; in fact, ''B''<sub>3</sub> is isomorphic to the [[knot group]] of the [[Trefoil knot|trefoil]]. |
The groups ''B''<sub>0</sub> and ''B''<sub>1</sub> are trivial; ''B''<sub>2</sub> is already infinite and [[group isomorphism|isomorphic]] to the infinite [[cyclic group]] '''Z'''. ''B''<sub>3</sub> is a quite complicated non-[[abelian group|abelian]] infinite group ; in fact, ''B''<sub>3</sub> is isomorphic to the [[knot group]] of the [[Trefoil knot|trefoil]]. ''B''<sub>3</sub> maps onto the [[modular group]] <math>SL_2(\mathbb{Z})</math> by means of the map |
||
:<math>\sigma_1 \mapsto \begin{bmatrix}1 & 1 \\ 0 & 1 \end{bmatrix} |
|||
\qquad \sigma_2 \mapsto \begin{bmatrix}1 & 0 \\ -1 & 1 \end{bmatrix} |
|||
</math> |
|||
The standard [[presentation of a group|presentation]] for the modular group is |
|||
:<math>\langle s,t | s^2=t^3\rangle</math> |
|||
where |
|||
:<math>s = \sigma_1 \sigma_2 \sigma_1 |
|||
\mapsto \begin{bmatrix}0 & 1 \\ -1 & 0 \end{bmatrix}</math> |
|||
and |
|||
:<math>t = \sigma_1 \sigma_2 |
|||
\mapsto \begin{bmatrix}0 & 1 \\ -1 & 1 \end{bmatrix}</math> |
|||
with the [[center of a group|center]] |
|||
:<math>c = s^2 = t^3 |
|||
\mapsto \begin{bmatrix}-1 & 0 \\ 0 & -1 \end{bmatrix}</math> |
|||
The braid group ''B''<sub>3</sub> modded out by this center is the [[projective group|projective]] modular group; that is, |
|||
:<math>PSL_2(\mathbb{Z}) \simeq B_3/\langle c\rangle</math> |
|||
In general, ''B''<sub>''n''</sub> is a [[subgroup]] of ''B''<sub>''n'' + 1</sub>: it can be viewed as consisting of all those braids on ''n'' + 1 strands in which the bottom strand is horizontal and does not cross nor is crossed by any other strand. |
In general, ''B''<sub>''n''</sub> is a [[subgroup]] of ''B''<sub>''n'' + 1</sub>: it can be viewed as consisting of all those braids on ''n'' + 1 strands in which the bottom strand is horizontal and does not cross nor is crossed by any other strand. |
Revision as of 01:34, 27 February 2007
In mathematics, the braid group on n strands, denoted by Bn, is a certain group which has an intuitive geometrical representation, and in a sense generalizes the symmetric group Sn. Here, n is a natural number; if n > 1, then Bn is an infinite group. Braid groups find applications in knot theory since knots can be represented by braids.
Intuitive description
This introduction takes n to be 4; the generalization to other values of n will be straightforward. Consider two sets of four items lying on a table, with the items in each set being arranged in a vertical line, and such that one set sits next to the other. (In the illustrations below, these are the black dots.) Using four strands, each item of the first set is connected with an item of the second set so that a one-to-one correspondence results. Such a connection is called a braid. Often some strands will have to pass over or under others, and this is crucial: the following two connections are different braids:
is different from |
On the other hand, two such connections which can be made to look the same by "pulling the strands" are considered the same braid:
is the same as |
All strands are required to move from left to right; knots like the following are not considered braids:
is not a braid |
Any two braids can be composed by drawing the first next to the second, identifying the four items in the middle, and connecting corresponding strands:
composed with | yields |
Another example:
composed with | yields |
The composition of the braids σ and τ is written as στ.
The set of all braids on four strands is denoted by B4. The above composition of braids is indeed a group operation. The neutral element is the braid consisting of four parallel horizontal strands, and the inverse of a braid consists of that braid which "undoes" whatever the first braid did. (The first two example braids above are inverses of each other.)
Generators and relations
Consider the following three braids:
Every braid in B4 can be written as a composition of a number of these braids and their inverses. In other words, these three braids generate the group B4. To see this, an arbitrary braid is scanned from left to right; whenever a crossing of strands i and i + 1 (counting from the top at the point of the crossing) is encountered, σi or σi−1 is written down, depending on whether strand i moves under or over strand i + 1. Upon reaching the right hand end, the braid has been written as a product of the σ's and their inverses.
It is clear that
- σ1σ3 = σ3σ1,
while the following two relations are not quite as obvious:
- σ1σ2σ1 = σ2σ1σ2
- σ2σ3σ2 = σ3σ2σ3
(these can be appreciated best by drawing the braid on a piece of paper). It can be shown that all other relations among the braids σ1, σ2 and σ3 already follow from these relations and the group axioms.
Generalising this example to n strands, the group Bn can be abstractly defined via the following presentation:
- generators σ1,...,σn−1
- relations (known as the braid relations):
- σi σj = σj σi whenever |i − j| ≥ 2 ;
- σi σi+1 σi = σi+1 σi σi+1 for i = 1,..., n − 2 (sometimes called the Yang-Baxter equation)
Some properties
The groups B0 and B1 are trivial; B2 is already infinite and isomorphic to the infinite cyclic group Z. B3 is a quite complicated non-abelian infinite group ; in fact, B3 is isomorphic to the knot group of the trefoil. B3 maps onto the modular group by means of the map
The standard presentation for the modular group is
where
and
with the center
The braid group B3 modded out by this center is the projective modular group; that is,
In general, Bn is a subgroup of Bn + 1: it can be viewed as consisting of all those braids on n + 1 strands in which the bottom strand is horizontal and does not cross nor is crossed by any other strand.
So in particular, Bn is abelian if and only if n ≤ 2.
There is a useful notion of "length" for the elements of the braid group, given by the group homomorphism Bn → Z that maps every σi to 1. So for instance, the length of the braid σ2σ3σ1−1σ2σ3 is 1 + 1 − 1 + 1 + 1 = 3. This notion gives rise, for example, to the subgroup of Bn consisting of all even-length braids.
Relation to the symmetric group, group actions
Every braid on n strands basically consists of a one-to-one correspondence between two sets of n items, and some topological information about how the strands establish this correspondence. Without this topological information every braid yields a one-to-one correspondence of n items; these are precisely the elements of the symmetric group Sn. This assignment is in fact a surjective group homomorphism Bn → Sn.
The kernel of this group homomorphism is called the pure braid group on n strands; it consists of those braids which connect the ith item of the left set to the ith item of the right set, for all i.
The symmetric group Sn has a very similar presentation to the one given above for the braid group: taking the braid relations and adding the relations
- σi2 = 1 for i = 1, ..., n − 1
yields a presentation for Sn (the σi can then be thought of as transpositions of two neighboring elements).
In situations where n items are being permuted "up to a twist", there is often an underlying group action of the braid group Bn. As a prototypical example, consider an arbitrary group G and the set X of all n-tuples of elements of G whose product is 1, the identity element of G. Then Bn operates on X in the following natural fashion: given a tuple x = (x1, ..., xn) in X define σi.x = (x1, ..., xi−1, xi+1, xi+1−1xixi+1, xi+2, ..., xn), so xi and xi+1 exchange places, but xi is in addition "twisted" by the inner automorphism corresponding to xi+1; this twist ensures that the product of the components of σi.x is the same as that of the components of x, namely 1. This operation satisfies the braid relations and thus defines a group action of Bn on X.
Connection to knot theory and computational aspects
If a braid is given and one connects the first left-hand item to the first right-hand item using a new string, the second left-hand item to the second right-hand item etc. (without creating any braids in the new strings), one obtains a link, and sometimes a knot. Alexander's theorem in braid theory states that the converse is true as well: every knot and every link arises in this fashion from at least one braid; such a braid can be obtained by cutting the link. Since braids can be concretely given as words in the generators σi, this is often the preferred method of entering knots into computer programs.
The word problem for the braid relations is efficiently solvable and there exists a normal form for elements of Bn in terms of the generators σ1,...,σn−1. (In essence, computing the normal form of a braid is the algebraic analogue of "pulling the strands" as illustrated in our second set of images above.) The free GAP computer algebra system can carry out computations in Bn if the elements are given in terms of these generators. There is also a package called CHEVIE for GAP3 with special support for braid groups.
Since there are nevertheless several hard computational problems about braid groups, applications in cryptography have been suggested.
Formal treatment
To put the above informal discussion of braid groups on firm ground, one needs to use the homotopy concept of algebraic topology, defining braid groups as fundamental groups of a configuration space. This is outlined in the article on braid theory.
Alternatively, one can eschew topology altogether and define the braid group purely algebraically via the braid relations, keeping the pictures in mind only to guide the intuition.
History
Braid groups were introduced explicitly by Emil Artin in 1925, although (as Wilhelm Magnus pointed out in 1974[1]) they were already implicit in Adolf Hurwitz's work on monodromy (1891). In fact, as Magnus says, Hurwitz gave the interpretation of a braid group as the fundamental group of a configuration space (cf. braid theory), an interpretation that was lost from view until it was rediscovered by Ralph Fox and Lee Neuwirth in 1962.
References
- ^ Wilhelm Magnus. Braid groups: A survey. In Lecture Notes in Mathematics, volume 372, pages 463-487. Springer, 1974.
External links
- "Braid group". PlanetMath.
- CRAG: CRyptography and Groups at Algebraic Cryptography Center Contains extensive library for computations with Braid Groups