TheGrigorchukGroupAlgorithms.h

Go to the documentation of this file.

// Copyright (C) 2006 Alexander Ushakov
// Contents: Definition of class TheGrigorchukGroupAlgorithms
//
// Principal Authors: Alexander Ushakov
//
// Revision History:
//


#ifndef _TheGrigorchukGroupAlgorithms_h_
#define _TheGrigorchukGroupAlgorithms_h_



#include "map"
#include "list"
#include "set"
using namespace std;

#include "tuples.h"
#include "Word.h"


//---------------------------------------------------------------------------//
//----------------------- TheGrigorchukGroupAlgorithms ----------------------//
//---------------------------------------------------------------------------//



class TheGrigorchukGroupAlgorithms
{
  
  //                                                     //
  //  Constructors:                                      //
  //                                                     //

public:
  
  TheGrigorchukGroupAlgorithms( );
  
  
  //                                                     //
  //  Accessors:                                         //
  //                                                     //

public:



  static bool trivial( const Word& w );



  static bool trivial_reduced( const Word& w );


  /*
    Result belongs to \f$\mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2\f$.
    \f$(1,0,0)\f$ corresponds to \f$a\f$, \f$(0,1,0)\f$ corresponds to \f$b\f$, 
    \f$(0,0,1)\f$ corresponds to \f$c\f$.
  */
  static triple< int , int , int > abelianImage( const Word& w );



  static Word reduce( const Word& w );
  
  

  static int findOrder( const Word& w );

  
  /*
    See Section 5 of "Solved and Unsolved Problems Around One Group".
  */
  static bool conjugate( const Word& w1 , const Word& w2 ) {
    return conjugate_Kcosets( w1 , w2 ).size()!=0;
  }


  /*
    For a pair of words \f$w_1\f$, \f$w_2\f$, \f$Q(w_1,w_2) = \{ xK \mid w_1^x = w_2\}\f$, 
    where \f$K = ncl(abab)\f$.
    See Section 5 of "Solved and Unsolved Problems Around One Group".
  */
  static set< int > conjugate_Kcosets( const Word& w1 , const Word& w2 );
  
  
  /*
    See Section 5 of "Solved and Unsolved Problems Around One Group".
  */
  static set< Word > findConjugator_Kcosets( const Word& w1 , const Word& w2 );
  


  static pair< Word , Word > split( const Word& w );


  //                                                     //
  //  Element routines:                                  //
  //                                                     //

public:

  static void push_back( Word& w , int g );


  static void push_front( Word& w , int g );
  
  
  static Word randomWord( int len );

  
  //                                                     //
  //  Certain subgroups:                                 //
  //                                                     //

public:


  static pair< Word , list< Word > > decompositionBSbgp( const Word& w );
    



  static pair< Word , Word > liftToSTone( const Word& w1 , const Word& w2 );
  
  
  /*
    The index of \f$K\f$ in \f$\Gamma\f$ is \f$8\f$.
    Cosets are numbered by 0,...,7 - ground level, 8,...,15 above level (involving b).
    On the level elements are numbered from the trivial element, d-element next, and so on.
  */
  static int cosetRepresentativeKSbgp( const Word& w );


  /*
    The index of \f$K\f$ in \f$\Gamma\f$ is \f$8\f$.
    Cosets are numbered by 0,...,7 - ground level, 8,...,15 above level (involving b).
    On the level elements are numbered from the trivial element, d-element next, and so on.
  */
  static Word cosetRepresentativeKSbgp( int c );
  
  

  static int liftPairKcosetsUP( int x , int y );
  
  

  static set< int > liftPairsKcosetsUP( const set< int >& K1 , const set< int >& K2 );


  //                                                     //
  //  Internal functions:                                //
  //                                                     //

 private:
 public:

  static map< pair< int , int > , int > KCosetLiftTable( );
  
  //                                                     //
  //  Data:                                              //
  //                                                     //

private:

};


#endif