TheGrigorchukGroupAlgorithms Class Reference

Static class TheGrigorchukGroupAlgorithms encapsulates algorithms for the original Grigorchuk group. More...

#include <TheGrigorchukGroupAlgorithms.h>

Public Member Functions
	TheGrigorchukGroupAlgorithms ()
	Default constructor is not instantiated to protect from creating the obects of this class.
Static Public Member Functions
static bool	trivial (const Word &w)
	Solve the Identity Problem for a non-reduced word.
static bool	trivial_reduced (const Word &w)
	Solve the Identity Problem for a reduced word.
static triple< int, int, int >	abelianImage (const Word &w)
	Compute the abelian image of an element.
static Word	reduce (const Word &w)
	Reduce a word.
static int	findOrder (const Word &w)
	Find the order of an element.
static bool	conjugate (const Word &w1, const Word &w2)
	Determine if 2 words represent conjugate elements of the Grigorchuk group.
static set< int >	conjugate_Kcosets (const Word &w1, const Word &w2)
	Compute the -set for a pair of words.
static set< Word >	findConjugator_Kcosets (const Word &w1, const Word &w2)
	Determine if 2 words represent conjugate elements of the Grigorchuk group and find the actual conjugators, one for each K-coset.
static pair< Word, Word >	split (const Word &w)
	Split an element of .
static void	push_back (Word &w, int g)
	Multiply an element by a generator on the right and perform a reduction if possible.
static void	push_front (Word &w, int g)
	Multiply an element by a generator on the left and perform a reduction if possible.
static Word	randomWord (int len)
	Generate a random reduced word.
static pair< Word, list< Word > >	decompositionBSbgp (const Word &w)
	Compute the decomposition of a word as an element of a subgroup .
static pair< Word, Word >	liftToSTone (const Word &w1, const Word &w2)
	Compute the preimage of along $\psi : St_{\Gamma}(1) \rightarrow \Gamma \times \Gamma$ .
static int	cosetRepresentativeKSbgp (const Word &w)
	Find a number of a right K-coset where $K = ncl_\Gamma(abab)$ .
static Word	cosetRepresentativeKSbgp (int c)
	Get a word representative of a right K-coset with number c.
static int	liftPairKcosetsUP (int x, int y)
	Lift the pair of right K-cosets to if possible.
static set< int >	liftPairsKcosetsUP (const set< int > &K1, const set< int > &K2)
	For two sets of K-cosets find all K-lifts.
static map< pair< int, int >, int >	KCosetLiftTable ()
	For each pair of K-cosets that can be lifted up to $ST_\Gamma(1)$ it associates such a lift.

Detailed Description

Static class TheGrigorchukGroupAlgorithms encapsulates algorithms for the original Grigorchuk group.

The class TheGrigorchukGroupAlgorithms is static, i.e., all member functions are static and there is no constructor defined. For introduction to the original Grigorchuk group see P. de la Harpe "Topics in Geometric Group Theory". For more on algorithmic properties see survey by R. Grigorchuk "Solved and Unsolved Problems Around One Group".

Definition at line 36 of file TheGrigorchukGroupAlgorithms.h.

Constructor & Destructor Documentation

TheGrigorchukGroupAlgorithms::TheGrigorchukGroupAlgorithms ( )

Default constructor is not instantiated to protect from creating the obects of this class.

Member Function Documentation

static triple< int , int , int > TheGrigorchukGroupAlgorithms::abelianImage ( const Word & w ) [static]

Compute the abelian image of an element.

static bool TheGrigorchukGroupAlgorithms::conjugate	(	const Word &	w1,
		const Word &	w2
	)			`[inline, static]`

Determine if 2 words represent conjugate elements of the Grigorchuk group.

Definition at line 103 of file TheGrigorchukGroupAlgorithms.h.

References conjugate_Kcosets().

static set< int > TheGrigorchukGroupAlgorithms::conjugate_Kcosets	(	const Word &	w1,
		const Word &	w2
	)			`[static]`

Compute the $Q$ -set for a pair of words.

Referenced by conjugate().

static Word TheGrigorchukGroupAlgorithms::cosetRepresentativeKSbgp ( int c ) [static]

Get a word representative of a right K-coset with number c.

static int TheGrigorchukGroupAlgorithms::cosetRepresentativeKSbgp ( const Word & w ) [static]

Find a number of a right K-coset $Kw$ where $K = ncl_\Gamma(abab)$ .

static pair< Word , list< Word > > TheGrigorchukGroupAlgorithms::decompositionBSbgp ( const Word & w ) [static]

Compute the decomposition of a word as an element of a subgroup $ncl_G(b)$ .

The function returns a pair $(c,L)$ where $c$ is a right coset for $w$ and $L$ is a sequence of conjugators for $b$ comprising the decomposition for $w$ . The equality $w = (\prod_{i=1}^n L_i^{-1} b L_i ) c$ holds.

static set< Word > TheGrigorchukGroupAlgorithms::findConjugator_Kcosets	(	const Word &	w1,
		const Word &	w2
	)			`[static]`

Determine if 2 words represent conjugate elements of the Grigorchuk group and find the actual conjugators, one for each K-coset.

static int TheGrigorchukGroupAlgorithms::findOrder ( const Word & w ) [static]

Find the order of an element.

Compute the smallest positive number $n$ such that $w^n$ is trivial in the Grigorchuk group.

static map< pair< int , int > , int > TheGrigorchukGroupAlgorithms::KCosetLiftTable ( ) [static]

For each pair of K-cosets that can be lifted up to $ST_\Gamma(1)$ it associates such a lift.

static int TheGrigorchukGroupAlgorithms::liftPairKcosetsUP	(	int	x,
		int	y
	)			`[static]`

Lift the pair of right K-cosets $(Kx,Ky)$ to $Kz$ if possible.

If $z = (x,y)$ then knowing cosets $xK$ and $yK$ it is possible to find a coset $xK$ . This operation is defined not for all pairs $x,y$ .

static set< int > TheGrigorchukGroupAlgorithms::liftPairsKcosetsUP	(	const set< int > &	K1,
		const set< int > &	K2
	)			`[static]`

For two sets of K-cosets find all K-lifts.

Function uses liftPairKcosetsUP() for each pair of cosets.

static pair< Word , Word > TheGrigorchukGroupAlgorithms::liftToSTone	(	const Word &	w1,
		const Word &	w2
	)			`[static]`

Compute the preimage of $(w_1,w_2)$ along $\psi : St_{\Gamma}(1) \rightarrow \Gamma \times \Gamma$ .

$\Gamma \times \Gamma \ne \psi(St_{\Gamma}(1))$ . The function returns a pair $(L,C)$ , where $C$ is such that $(w_1 C^{-1},w_2) \in \psi(St_{\Gamma}(1))$ and $L$ is a preimage of $(w_1 C^{-1},w_2)$ .

static void TheGrigorchukGroupAlgorithms::push_back	(	Word &	w,
		int	g
	)			`[static]`

Multiply an element by a generator on the right and perform a reduction if possible.

static void TheGrigorchukGroupAlgorithms::push_front	(	Word &	w,
		int	g
	)			`[static]`

Multiply an element by a generator on the left and perform a reduction if possible.

static Word TheGrigorchukGroupAlgorithms::randomWord ( int len ) [static]

Generate a random reduced word.

static Word TheGrigorchukGroupAlgorithms::reduce ( const Word & w ) [static]

Reduce a word.

See VIII.B(12) of de la Harpe.

static pair< Word , Word > TheGrigorchukGroupAlgorithms::split ( const Word & w ) [static]

Split an element of $St(1)$ .

Make sure $w \in St(1)$ ! The output is a pair of words $(w_0,w_1)$ , $w_0$ acts on the left subtree, and $w_1$ acts on the right subtree.

static bool TheGrigorchukGroupAlgorithms::trivial ( const Word & w ) [static]

Solve the Identity Problem for a non-reduced word.

Check if a word over the original alphabet represents the identity. See VIII.E(47) of de la Harpe.

static bool TheGrigorchukGroupAlgorithms::trivial_reduced ( const Word & w ) [static]

Solve the Identity Problem for a reduced word.

Check if a word over the original alphabet represents the identity. See VIII.E(47) of de la Harpe.

The documentation for this class was generated from the following file:

TheGrigorchukGroup/include/TheGrigorchukGroupAlgorithms.h

TheGrigorchukGroupAlgorithms Class Reference

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation