ThRightNormalForm Class Reference

Defines a representation of a right Garside normal form. More...

#include <ThRightNormalForm.h>

List of all members.

Public Types

typedef triple< int, int,
list< Permutation > > 
NF
 Presentation of a normal form.

Public Member Functions

 ThRightNormalForm (int rank=0)
 Default constructor (rank specifies the rank of a braid group the form belongs to).
 ThRightNormalForm (int rank, int p, const list< Permutation > &d)
 Constructor (rank specifies the rank of a braid group the form belongs to, p - a power of a half twist, and d - a list of permutations. So the pair (p,d) is a presentation).
 ThRightNormalForm (const NF &tr)
 Constructor (tr specifies a presentation of the normal form).
 ThRightNormalForm (const BraidGroup &G, const Word &w)
 Constructs the normal form of a braid word w.
 ThRightNormalForm (const Permutation &p)
 Construct a positive braid from a permutation.
ThRightNormalFormoperator= (const NF &tr)
 Assignment operator.
 operator NF () const
 Cast operator (returns a representation of a normal form).
bool operator== (const ThRightNormalForm &rep) const
 Compare (check if equal).
bool operator!= (const ThRightNormalForm &rep) const
 Compare (check if not equal).
bool operator< (const ThRightNormalForm &rep) const
 Compare (check if less, performed componentwise).
ThRightNormalForm operator- () const
ThRightNormalForm operator * (const ThRightNormalForm &rep) const
 Multiply two normal forms.
ThRightNormalFormoperator *= (const ThRightNormalForm &rep)
 Multiply a normal form by the other on the right.
 operator ThLeftNormalForm () const
 Cast operator.
int getRank () const
 Get the rank of a corresponding braid group.
int getPower () const
 Get half-twist power.
const list< Permutation > & getDecomposition () const
 Get a list of permutations.
bool isTrivial () const
 Check if a normal form is trivial.
Word getWord () const
 Computes a word represented by a normal form.
Word getShortWord () const
 Computes a "shorter" word represented by a normal form.
ThRightNormalForm increaseRank (int N) const
 Increase the rank of the braid.
pair< bool, ThRightNormalFormareConjugate (const ThRightNormalForm &rep) const
 Check whether two braids are conjugate.
void adjust ()
 Adjust a normal form.
set< ThRightNormalFormcomputeCentralizer () const
 Compute generators of the centralizer of an element.
pair< ThRightNormalForm, ThRightNormalFormfindSSSRepresentative () const
 (Low level function) Compute super summit set representative.
pair< ThRightNormalForm, ThRightNormalFormcycle () const
 Cycle a normal form.
pair< ThRightNormalForm, ThRightNormalFormdecycle () const
 Decycle a normal form.
Permutation getSimpleConjugator (const Permutation &start) const
 Compute the minimal simple conjugator (permutation) starting from "start".
set< PermutationgetSimpleConjugators () const
 Find a list of simple conjugators (permutations) conjugation by which does not decrease the infimum of the element.
Permutation getSimpleSummitConjugator (const Permutation &start) const
 Compute a minimal simple summit conjugator for starting from "start".
set< PermutationgetSimpleSummitConjugators () const
 Find a list of simple conjugators (permutations) conjugation by which does not change infimum and supremum of the given element.
triple< ThRightNormalForm,
ThRightNormalForm, int > 
findUSSRepresentative () const
 (Low level function) Compute ultra summit set representative.
triple< Permutation, bool,
int > 
getSimpleUltraConjugator (int period, const Permutation &start)
 Compute a simple ultra conjugator for starting from "startSymbol".
set< pair< Permutation, int > > getSimpleUltraConjugators (int period)
 Compute all minimal simple ultra conjugators for "rep".
set< PermutationgetTransports (const Permutation &u, int period) const
 (Aux, for USS simple) Compute a set of transports for a pair *this and (*this)^u where p is a permutation.
Permutation getTransport (const ThRightNormalForm &B, const Permutation &u) const
 (Aux, for USS simple) Compute a transport for *this and B = (*this)^u where p is a permutation.
Permutation getPullback (const Permutation &s) const
 (Aux, for USS simple) Compute a pullback for *this and B = (*this)^s where s is a permutation.
Permutation getPullback (const Permutation &u, int period) const
 (Aux, for USS simple) Compute the main pullback for *this and a permutation u
void setPower (int p)
 Set a power of a half-twist.
void setDecomposition (const list< Permutation > &d)
 Set a decomposition of a normal form (without any check of "greedy conditions").

Static Public Member Functions

static ThRightNormalForm randomPositive (int rank, int decomp_length)
 Generate random positive normal form.
static void adjustDecomposition (int rank, int &power, list< Permutation > &decomp)
 Adjust a normal form.

Private Types

enum  transformationResult { TWO_MULTIPLIERS, ONE_MULTIPLIER, NO_CHANGE }
 The main function which "canonify" a product of two permutations. More...

Private Member Functions

NF inverse () const
 (Low level function) Invert a normal form.
NF multiply (const ThRightNormalForm &rep) const
 (Low level function) Multiply normal forms.
pair< bool, ThRightNormalFormsssConstructionIteration (map< ThRightNormalForm, ThRightNormalForm > &sss_new1, map< ThRightNormalForm, ThRightNormalForm > &sss_checked1, const map< ThRightNormalForm, ThRightNormalForm > &sss_new2, const map< ThRightNormalForm, ThRightNormalForm > &sss_checked2) const
 I think function processes a vertex in a Super Summit Set graph.

Static Private Member Functions

static transformationResult transform (int theIndex, Permutation &p1, Permutation &p2)

Private Attributes

int theRank
 The rank of the braid group (number of strands).
int theOmegaPower
 Power of omega.
list< PermutationtheDecomposition
 Sequence of permutations.


Detailed Description

Defines a representation of a right Garside normal form.

Right Garside normal form has the following presentation $ \xi_1 \ldots \xi_{t-1} \xi_t \Delta^\omega$ where $\Delta$ is a half-twist permutation and $\xi_1 \ldots \xi_{t-1} \xi_t$ is a right-weighted sequence of permutation braids. A sequence of permutation braids is called right-weighted if for any pair $\xi_i\xi_{i+1}$ $F(\xi_i) \subseteq S(\xi_{i+1})$. Here $S(\xi) = \{i \mid \xi = x_i \xi' \mbox{ for some permutation } \xi' \}$ and $F(\xi) = \{i \mid \xi = \xi' x_i \mbox{ for some permutation } \xi' \}$ are starting and finishing sets.

Permutations $\xi$ are translated to braids "from right to left". So, you construct a minimal positive braid where points on the right will go to positions defined by $\xi$ on the left.

Definition at line 42 of file ThRightNormalForm.h.


Member Typedef Documentation

typedef triple< int , int , list< Permutation > > ThRightNormalForm::NF
 

Presentation of a normal form.

The first component specifies the rank of a braid group. The second component specifies the power of the half twist. The third component specifies the list of braid permutations.

Definition at line 51 of file ThRightNormalForm.h.


Member Enumeration Documentation

enum ThRightNormalForm::transformationResult [private]
 

The main function which "canonify" a product of two permutations.

Enumerator:
TWO_MULTIPLIERS 
ONE_MULTIPLIER 
NO_CHANGE 

Definition at line 444 of file ThRightNormalForm.h.


Constructor & Destructor Documentation

ThRightNormalForm::ThRightNormalForm int  rank = 0  )  [inline]
 

Default constructor (rank specifies the rank of a braid group the form belongs to).

Default rank value is for map<...> only make sure to provide the argument for this constructor

Definition at line 66 of file ThRightNormalForm.h.

ThRightNormalForm::ThRightNormalForm int  rank,
int  p,
const list< Permutation > &  d
[inline]
 

Constructor (rank specifies the rank of a braid group the form belongs to, p - a power of a half twist, and d - a list of permutations. So the pair (p,d) is a presentation).

There is no check that the pair (p,d) defines a correct normal form representation. If you are not sure if (p,d) is correct apply static function adjustDecomposition first.

Definition at line 77 of file ThRightNormalForm.h.

ThRightNormalForm::ThRightNormalForm const NF tr  )  [inline]
 

Constructor (tr specifies a presentation of the normal form).

Definition at line 84 of file ThRightNormalForm.h.

ThRightNormalForm::ThRightNormalForm const BraidGroup G,
const Word w
 

Constructs the normal form of a braid word w.

ThRightNormalForm::ThRightNormalForm const Permutation p  )  [inline]
 

Construct a positive braid from a permutation.

Definition at line 95 of file ThRightNormalForm.h.

References Permutation::getHalfTwistPermutation(), Permutation::isTrivial(), Permutation::size(), theOmegaPower, and theRank.


Member Function Documentation

void ThRightNormalForm::adjust  )  [inline]
 

Adjust a normal form.

Use this function if there is a possiblitiy that the sequence of permutations does not satisfy the "greedy conditions". Right now this might happen only after use of a constructor ThRightNormalForm (const NF &tr) or, more likely, in function setDecomposition(...). This function uses adjustDecomposition( ... ).

Definition at line 260 of file ThRightNormalForm.h.

static void ThRightNormalForm::adjustDecomposition int  rank,
int &  power,
list< Permutation > &  decomp
[static]
 

Adjust a normal form.

Use this function if the triple of arguments does not satisfy "greedy conditions".

pair< bool , ThRightNormalForm > ThRightNormalForm::areConjugate const ThRightNormalForm rep  )  const
 

Check whether two braids are conjugate.

Very slow function. Checks if super summit sets of two braids contain the same element (i.e., coincide). ... and the super summit sets are typically huge even for decent parameters.

Returns:
- a pair (R,C), where R is a boolean value (true if braids are conjugate, false otherwise), and C is a conjugator (if braids conjugate)

set<ThRightNormalForm> ThRightNormalForm::computeCentralizer  )  const
 

Compute generators of the centralizer of an element.

Very slow function. Function computes the graph with the super summit set of the element as the vertex set. Even for a small rank of a braid group (say 10) and a short braid word (say 100) the super summit set is typically huge.

pair< ThRightNormalForm , ThRightNormalForm > ThRightNormalForm::cycle  )  const
 

Cycle a normal form.

Operation: $ \xi_1 \ldots \xi_{t-1} \xi_t \Delta^s ~\mapsto~ \xi_t \Delta^s \xi_1 \ldots \xi_{t-1} \Delta^s$. Main purpose of the function is to increase the infimum (half twist power) of a normal form. If $n$ cyclings do not increase infimum then the infimum is already maximal.

Returns:
a pair (R,C), where R is the result of a cycling and C is a conjugator (if A is an input then $R = C^{-1} A C$)

pair<ThRightNormalForm,ThRightNormalForm> ThRightNormalForm::decycle  )  const
 

Decycle a normal form.

Operation: $ \xi_1 \xi_2 \ldots \xi_t \Delta^s ~\mapsto~ \Delta^s \xi_2 \ldots \xi_t \Delta^s \xi_1$. Main purpose of the function is to decrease the supremum (size of the decomposition) of a normal form. If $n$ decyclings do not decrease supremum then the supremum is already minimal.

Returns:
a pair (R,C), where R is the result of a cycling and C is a conjugator (if A is an input then $R = C^{-1} A C$)

pair< ThRightNormalForm , ThRightNormalForm > ThRightNormalForm::findSSSRepresentative  )  const
 

(Low level function) Compute super summit set representative.

triple< ThRightNormalForm , ThRightNormalForm , int > ThRightNormalForm::findUSSRepresentative  )  const
 

(Low level function) Compute ultra summit set representative.

Returns:
a triple (R,C,P), where R is the result, C is a conjugator (if A is an input then $R = C^{-1} A C$), and P is the period of the trajectory.

const list< Permutation >& ThRightNormalForm::getDecomposition  )  const [inline]
 

Get a list of permutations.

Definition at line 195 of file ThRightNormalForm.h.

int ThRightNormalForm::getPower  )  const [inline]
 

Get half-twist power.

Definition at line 193 of file ThRightNormalForm.h.

Permutation ThRightNormalForm::getPullback const Permutation u,
int  period
const
 

(Aux, for USS simple) Compute the main pullback for *this and a permutation u

Permutation ThRightNormalForm::getPullback const Permutation s  )  const
 

(Aux, for USS simple) Compute a pullback for *this and B = (*this)^s where s is a permutation.

See Definition 4.6 in Gebhardt, "A New Approach to the Conjugacy Problem in Garside Groups". It is important that braids (*this) and (*this)^u belong to their SSS. Also, it is important that (*this) is not a power of $\Delta$ (USS is "trivial" for such elements).

int ThRightNormalForm::getRank  )  const [inline]
 

Get the rank of a corresponding braid group.

Definition at line 191 of file ThRightNormalForm.h.

Word ThRightNormalForm::getShortWord  )  const
 

Computes a "shorter" word represented by a normal form.

Try to use the fact that the square of a half twist generates a center. If the power of half-twist is negative then it cancel them with the other permutation braids. After that, for newly obtained permutations computes braid words and concatenates them.

Permutation ThRightNormalForm::getSimpleConjugator const Permutation start  )  const
 

Compute the minimal simple conjugator (permutation) starting from "start".

Algorithm 1 from Franco, Gonzalez-Menese, "Conjugacy problem for braid and Garside groups". Conjugating by a simple element does not decrease the infimum of the element.

set< Permutation > ThRightNormalForm::getSimpleConjugators  )  const
 

Find a list of simple conjugators (permutations) conjugation by which does not decrease the infimum of the element.

The current version is very simple. For each permutation cycle $(i,i+1)$ it computes the minimal permutation $p$ which starts with $(i,i+1)$ such that conjugation by $p$ does not decrease the infimum of the element and outputs all of such permutations. The output is not guaranteed to be minimal, i.e., some of the permutations can be prefixes of the other.

Permutation ThRightNormalForm::getSimpleSummitConjugator const Permutation start  )  const
 

Compute a minimal simple summit conjugator for starting from "start".

Algorithm 4 from Franco, Gonzalez-Menese, "Conjugacy problem for braid and Garside groups". Conjugating by a simple summit element does not decrease the infimum of the element and does not increase the canonical length.

set< Permutation > ThRightNormalForm::getSimpleSummitConjugators  )  const
 

Find a list of simple conjugators (permutations) conjugation by which does not change infimum and supremum of the given element.

The current version is very simple. For each permutation cycle $(i,i+1)$ it computes the minimal permutation $p$ which starts with $(i,i+1)$ such that conjugation by $p$ does not decrease the infimum of the element and does not increase the canonical length, and outputs all of such permutations. The output is not guaranteed to be minimal, i.e., some of the permutations can be prefixes of the other.

triple< Permutation , bool , int > ThRightNormalForm::getSimpleUltraConjugator int  period,
const Permutation start
 

Compute a simple ultra conjugator for starting from "startSymbol".

Algorithm 4.9 from Gebhardt, "A New Approach to the Conjugacy Problem in Garside Groups". Conjugating by a simple ultra element does not decrease the infimum of the element and does not increase the canonical length. Also, the result of the conjugaction belongs to the USS.

Returns:
a triple (R,M,P), where R is the resulting permutation, M is true if R is minimal, and P is a period of a conjugated braid.

set< pair< Permutation , int > > ThRightNormalForm::getSimpleUltraConjugators int  period  ) 
 

Compute all minimal simple ultra conjugators for "rep".

Permutation ThRightNormalForm::getTransport const ThRightNormalForm B,
const Permutation u
const
 

(Aux, for USS simple) Compute a transport for *this and B = (*this)^u where p is a permutation.

See Proposition 2.1 and Definition 2.4 of Gebhardt "A New Approach to the Conjugacy Problem in Garside Groups". It is important that braids (*this) and B = (*this)^u belong to their SSS. Also, it is important that (*this) is not a power of $\Delta$ (USS is "trivial" for such elements).

set< Permutation > ThRightNormalForm::getTransports const Permutation u,
int  period
const
 

(Aux, for USS simple) Compute a set of transports for a pair *this and (*this)^u where p is a permutation.

F-set, see Definition 4.2 in Gebhardt, "A New Approach to the Conjugacy Problem in Garside Groups". It is important that braids (*this) and (*this)^u belong to their SSS. Also, it is important that (*this) is not a power of $\Delta$ (USS is "trivial" for such elements).

Word ThRightNormalForm::getWord  )  const
 

Computes a word represented by a normal form.

For each permutation-braid computes a braid-word it represents and, finally, concatenate all the results.

ThRightNormalForm ThRightNormalForm::increaseRank int  N  )  const
 

Increase the rank of the braid.

The current braid does not change as an element of $F_\infty$. We simply increase the rank and recompute the normal form presentation. If N<theRank then output *this.

NF ThRightNormalForm::inverse  )  const [private]
 

(Low level function) Invert a normal form.

bool ThRightNormalForm::isTrivial  )  const [inline]
 

Check if a normal form is trivial.

Definition at line 199 of file ThRightNormalForm.h.

NF ThRightNormalForm::multiply const ThRightNormalForm rep  )  const [private]
 

(Low level function) Multiply normal forms.

ThRightNormalForm ThRightNormalForm::operator * const ThRightNormalForm rep  )  const [inline]
 

Multiply two normal forms.

Definition at line 169 of file ThRightNormalForm.h.

References multiply().

ThRightNormalForm& ThRightNormalForm::operator *= const ThRightNormalForm rep  )  [inline]
 

Multiply a normal form by the other on the right.

Definition at line 174 of file ThRightNormalForm.h.

References multiply().

ThRightNormalForm::operator NF  )  const [inline]
 

Cast operator (returns a representation of a normal form).

Definition at line 127 of file ThRightNormalForm.h.

ThRightNormalForm::operator ThLeftNormalForm  )  const
 

Cast operator.

bool ThRightNormalForm::operator!= const ThRightNormalForm rep  )  const [inline]
 

Compare (check if not equal).

Definition at line 142 of file ThRightNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

ThRightNormalForm ThRightNormalForm::operator-  )  const [inline]
 

Definition at line 164 of file ThRightNormalForm.h.

bool ThRightNormalForm::operator< const ThRightNormalForm rep  )  const [inline]
 

Compare (check if less, performed componentwise).

Definition at line 150 of file ThRightNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

ThRightNormalForm& ThRightNormalForm::operator= const NF tr  )  [inline]
 

Assignment operator.

Definition at line 110 of file ThRightNormalForm.h.

References triple< T1, T2, T3 >::first, triple< T1, T2, T3 >::second, and triple< T1, T2, T3 >::third.

bool ThRightNormalForm::operator== const ThRightNormalForm rep  )  const [inline]
 

Compare (check if equal).

Definition at line 133 of file ThRightNormalForm.h.

References theDecomposition, theOmegaPower, and theRank.

static ThRightNormalForm ThRightNormalForm::randomPositive int  rank,
int  decomp_length
[static]
 

Generate random positive normal form.

Function returns a right normal form with canonical length decomp_length (it can be smaller due to possible cancellations).

void ThRightNormalForm::setDecomposition const list< Permutation > &  d  )  [inline]
 

Set a decomposition of a normal form (without any check of "greedy conditions").

Definition at line 425 of file ThRightNormalForm.h.

void ThRightNormalForm::setPower int  p  )  [inline]
 

Set a power of a half-twist.

Definition at line 423 of file ThRightNormalForm.h.

pair< bool , ThRightNormalForm > ThRightNormalForm::sssConstructionIteration map< ThRightNormalForm, ThRightNormalForm > &  sss_new1,
map< ThRightNormalForm, ThRightNormalForm > &  sss_checked1,
const map< ThRightNormalForm, ThRightNormalForm > &  sss_new2,
const map< ThRightNormalForm, ThRightNormalForm > &  sss_checked2
const [private]
 

I think function processes a vertex in a Super Summit Set graph.

static transformationResult ThRightNormalForm::transform int  theIndex,
Permutation p1,
Permutation p2
[static, private]
 


Member Data Documentation

list< Permutation > ThRightNormalForm::theDecomposition [private]
 

Sequence of permutations.

Definition at line 469 of file ThRightNormalForm.h.

Referenced by operator!=(), operator<(), and operator==().

int ThRightNormalForm::theOmegaPower [private]
 

Power of omega.

Definition at line 466 of file ThRightNormalForm.h.

Referenced by operator!=(), operator<(), operator==(), and ThRightNormalForm().

int ThRightNormalForm::theRank [private]
 

The rank of the braid group (number of strands).

Definition at line 463 of file ThRightNormalForm.h.

Referenced by operator!=(), operator<(), operator==(), and ThRightNormalForm().


The documentation for this class was generated from the following file:
Generated on Sun Dec 3 10:59:05 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.6