A standard Artin generator of a braid: Sigma i represents twisting the neighbour strands i and (i+1), such that strand i goes under strand (i+1).

Note: The strands are numbered 1..n.

The strand (more precisely, the first of the two strands) the generator twistes

The inverse of a braid generator

The braid group B_n on n strands. The number n is encoded as a type level natural in the type parameter.

Braids are represented as words in the standard generators and their inverses.

The number of strands in the braid

Sometimes we want to hide the type-level parameter n, for example when dynamically creating braids whose size is known only at runtime.

Embeds a smaller braid group into a bigger braid group

Apply "free reduction" to the word, that is, iteratively remove sigma_i sigma_i^-1 pairs. The resulting braid is clearly equivalent to the original.

The braid generator sigma_i as a braid

The braid generator sigma_i^(-1) as a braid

doubleSigma s t (for s<t)is the generator sigma_{s,t} in Birman-Ko-Lee's "new presentation". It twistes the strands s and t while going over all other strands. For t==s+1 we get back sigma s

positiveWord [2,5,1] is shorthand for the word sigma_2*sigma_5*sigma_1.

The (positive) half-twist of all the braid strands, usually denoted by Delta.

The untyped version of halfTwist

Synonym for halfTwist

The inner automorphism defined by tau(X) = Delta^-1 X Delta, where Delta is the positive half-twist.

This sends each generator sigma_j to sigma_(n-j).

The involution tau on permutations (permutation braids)

The trivial braid

The inverse of a braid. Note: we do not perform reduction here, as a word is reduced if and only if its inverse is reduced.

Composes two braids, doing free reduction on the result (that is, removing (sigma_k * sigma_k^-1) pairs@)

Composes two braids without doing any reduction.

A braid is pure if its permutation is trivial

Returns the left-to-right permutation associated to the braid. We follow the strands from the left to the right (or from the top to the bottom), and return the permutation taking the left side to the right side.

This is compatible with right (standard) action of the permutations: permuteRight (braidPermutationRight b1) corresponds to the left-to-right permutation of the strands; also:

(braidPermutation b1) `multiply` (braidPermutation b2) == braidPermutation (b1 `compose` b2)

Writing the right numbering of the strands below the left numbering, we got the two-line notation of the permutation.

This is an untyped version of braidPermutation

A positive braid word contains only positive (Sigma) generators.

A permutation braid is a positive braid where any two strands cross at most one, and positively.

Untyped version of isPermutationBraid for positive words.

For any permutation this functions returns a permutation braid realizing that permutation. Note that this is not unique, so we make an arbitrary choice (except for the permutation [n,n-1..1] reversing the order, in which case the result must be the half-twist braid).

The resulting braid word will have a length at most choose n 2 (and will have that length only for the permutation [n,n-1..1])

braidPermutationRight (permutationBraid perm) == perm
isPermutationBraid    (permutationBraid perm) == True

Untyped version of permutationBraid

Returns the individual "phases" of the a permutation braid realizing the given permutation.

We compute the linking numbers between all pairs of strands:

linkingMatrix braid ! (i,j) == strandLinking braid i j 

Untyped version of linkingMatrix

The linking number between two strands numbered i and j (numbered such on the left side).

Bronfman's recursive formula for the reciprocial of the growth function of positive braids. It was already known (by Deligne) that these generating functions are reciprocials of polynomials; Bronfman [1] gave a recursive formula for them.

let count n l = length $ nub $ [ braidNormalForm w | w <- allPositiveBraidWords n l ]
let convertPoly (1:cs) = zip (map negate cs) [1..]
pseries' (convertPoly $ bronfmanH n) == expandBronfmanH n == [ count n l | l <- [0..] ] 

• [1] Aaron Bronfman: Growth functions of a class of monoids. Preprint, 2001

An infinite list containing the Bronfman polynomials:

bronfmanH n = bronfmanHsList !! n

Expands the reciprocial of H(n) into an infinite power series, giving the growth function of the positive braids on n strands.

Horizontal braid diagram, drawn from left to right, with strands numbered from the bottom to the top

Horizontal braid diagram, drawn from left to right. The boolean flag indicates whether to flip the strands vertically (True means bottom-to-top, False means top-to-bottom)

All positive braid words of the given length

All braid words of the given length

Untyped version of allPositiveBraidWords

Untyped version of allBraidWords

Random braid word of the given length

Random positive braid word of the given length

Given a braid word, we perturb it randomly m times using the braid relations, so that the resulting new braid word is equivalent to the original.

Useful for testing.

This version of randomBraidWord may be convenient to avoid the type level stuff

This version of randomPositiveBraidWord may be convenient to avoid the type level stuff

Untyped version of randomBraidWord

Untyped version of randomPositiveBraidWord