Math.Combinat.Groups.Braid

Braids. See eg. https://en.wikipedia.org/wiki/Braid_group

Based on:

• Joan S. Birman, Tara E. Brendle: BRAIDS - A SURVEY https://www.math.columbia.edu/~jb/Handbook-21.pdf

Note: This module GHC 7.8, since we use type-level naturals to parametrize the Braid type.

Artin generators

data BrGen

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.

Constructors

Sigma !Int

i goes under (i+1)

SigmaInv !Int

i goes above (i+1)

Instances

Eq BrGen

Defined in Math.Combinat.Groups.Braid

Methods

(==) :: BrGen -> BrGen -> Bool

(/=) :: BrGen -> BrGen -> Bool

Ord BrGen

Defined in Math.Combinat.Groups.Braid

Methods

compare :: BrGen -> BrGen -> Ordering

(<) :: BrGen -> BrGen -> Bool

(<=) :: BrGen -> BrGen -> Bool

(>) :: BrGen -> BrGen -> Bool

(>=) :: BrGen -> BrGen -> Bool

max :: BrGen -> BrGen -> BrGen

min :: BrGen -> BrGen -> BrGen

Show BrGen

Defined in Math.Combinat.Groups.Braid

Methods

showsPrec :: Int -> BrGen -> ShowS

show :: BrGen -> String

showList :: [BrGen] -> ShowS

brGenIdx :: BrGen -> Int

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

brGenSign :: BrGen -> Sign

brGenSignIdx :: BrGen -> (Sign, Int)

invBrGen :: BrGen -> BrGen

The inverse of a braid generator

The braid type

newtype Braid (n :: Nat)

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.

Constructors

Braid [BrGen]

Instances

Show (Braid n)

Defined in Math.Combinat.Groups.Braid

Methods

showsPrec :: Int -> Braid n -> ShowS

show :: Braid n -> String

showList :: [Braid n] -> ShowS

KnownNat n => DrawASCII (Braid n)

Defined in Math.Combinat.Groups.Braid

Methods

ascii :: Braid n -> ASCII

numberOfStrands :: KnownNat n => Braid n -> Int

The number of strands in the braid

data SomeBraid

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

Constructors

forall n.KnownNat n => SomeBraid (Braid n)

someBraid :: Int -> (forall (n :: Nat). KnownNat n => Braid n) -> SomeBraid

withSomeBraid :: SomeBraid -> (forall n. KnownNat n => Braid n -> a) -> a

mkBraid :: (forall n. KnownNat n => Braid n -> a) -> Int -> [BrGen] -> a

withBraid :: Int -> (forall (n :: Nat). KnownNat n => Braid n) -> (forall (n :: Nat). KnownNat n => Braid n -> a) -> a

braidWord :: Braid n -> [BrGen]

braidWordLength :: Braid n -> Int

extend :: n1 <= n2 => Braid n1 -> Braid n2

Embeds a smaller braid group into a bigger braid group

freeReduceBraidWord :: Braid n -> Braid n

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.

Some specific braids

sigma :: KnownNat n => Int -> Braid (n :: Nat)

The braid generator sigma_i as a braid

sigmaInv :: KnownNat n => Int -> Braid (n :: Nat)

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

doubleSigma :: KnownNat n => Int -> Int -> Braid (n :: Nat)

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 :: KnownNat n => [Int] -> Braid (n :: Nat)

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

halfTwist :: KnownNat n => Braid n

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

_halfTwist :: Int -> [Int]

The untyped version of halfTwist

theGarsideBraid :: KnownNat n => Braid n

Synonym for halfTwist

tau :: KnownNat n => Braid n -> Braid n

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).

tauPerm :: Permutation -> Permutation

The involution tau on permutations (permutation braids)

Group operations

identity :: Braid n

The trivial braid

inverse :: Braid n -> Braid n

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.

compose :: Braid n -> Braid n -> Braid n

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

composeMany :: [Braid n] -> Braid n

composeDontReduce :: Braid n -> Braid n -> Braid n

Composes two braids without doing any reduction.

Braid permutations

isPureBraid :: KnownNat n => Braid n -> Bool

A braid is pure if its permutation is trivial

braidPermutation :: KnownNat n => Braid n -> Permutation

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.

_braidPermutation :: Int -> [Int] -> Permutation

This is an untyped version of braidPermutation

Permutation braids

isPositiveBraidWord :: KnownNat n => Braid n -> Bool

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

isPermutationBraid :: KnownNat n => Braid n -> Bool

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

_isPermutationBraid :: Int -> [Int] -> Bool

Untyped version of isPermutationBraid for positive words.

permutationBraid :: KnownNat n => Permutation -> Braid n

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

_permutationBraid :: Permutation -> [Int]

Untyped version of permutationBraid

_permutationBraid' :: Permutation -> [[Int]]

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

linkingMatrix :: KnownNat n => Braid n -> UArray (Int, Int) Int

We compute the linking numbers between all pairs of strands:

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

_linkingMatrix :: Int -> [BrGen] -> UArray (Int, Int) Int

Untyped version of linkingMatrix

strandLinking :: KnownNat n => Braid n -> Int -> Int -> Int

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

Growth

bronfmanH :: Int -> [Int]

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

bronfmanHsList :: [[Int]]

An infinite list containing the Bronfman polynomials:

bronfmanH n = bronfmanHsList !! n

expandBronfmanH :: Int -> [Int]

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

ASCII diagram

horizBraidASCII :: KnownNat n => Braid n -> ASCII

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

horizBraidASCII' :: KnownNat n => Bool -> Braid n -> ASCII

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)

List of all words

allPositiveBraidWords :: KnownNat n => Int -> [Braid n]

All positive braid words of the given length

allBraidWords :: KnownNat n => Int -> [Braid n]

All braid words of the given length

_allPositiveBraidWords :: Int -> Int -> [[BrGen]]

Untyped version of allPositiveBraidWords

_allBraidWords :: Int -> Int -> [[BrGen]]

Untyped version of allBraidWords

Random braids

randomBraidWord :: (RandomGen g, KnownNat n) => Int -> g -> (Braid n, g)

Random braid word of the given length

randomPositiveBraidWord :: (RandomGen g, KnownNat n) => Int -> g -> (Braid n, g)

Random positive braid word of the given length

randomPerturbBraidWord :: forall n g. (RandomGen g, KnownNat n) => Int -> Braid n -> g -> (Braid n, g)

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.

withRandomBraidWord

Arguments

:: RandomGen g

=> (forall n. KnownNat n => Braid n -> a)

-> Int

number of strands

-> Int

length of the random word

-> g

-> (a, g)

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

withRandomPositiveBraidWord

Arguments

:: RandomGen g

=> (forall n. KnownNat n => Braid n -> a)

-> Int

number of strands

-> Int

length of the random word

-> g

-> (a, g)

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

_randomBraidWord

Arguments

:: RandomGen g

=> Int

number of strands

-> Int

length of the random word

-> g

-> ([BrGen], g)

Untyped version of randomBraidWord

_randomPositiveBraidWord

Arguments

:: RandomGen g

=> Int

number of strands

-> Int

length of the random word

-> g

-> ([BrGen], g)

Untyped version of randomPositiveBraidWord