Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

/magnus/back_end/NilpotentGroup/include/BasicCommutators.h

Go to the documentation of this file.
00001 
00002 // Copyright (C) 1994 The New York Group Theory Cooperative
00003 // See magnus/doc/COPYRIGHT for the full notice.
00004 //
00005 // Principal Authors: Eugene Paderin, Sergei Lyutikov
00006 //
00007 // Description:
00008 //
00009 // A declaration of classes BCEntry, BasicCommutators.
00010 //
00011 //
00012 // Status: Draft
00013 //
00014 // Revision History:
00015 //
00016 // * first built April 31, 1995 (says SL :)
00017 //
00018 // * This is a EP's remake of SL's BasicCommutators class. I had to
00019 //   make some changes for my special needs.
00020 //   BCEntry is taken from SL's BasicCommutators.h file.
00021 //
00022 // * Class BasicCommutators contains an ordered set of basic 
00023 //   commutators (BC) ( see Khukhro? ) corresponding to nilpotent 
00024 //   group of particular number of generators and particular nilpotency 
00025 //   class. Each BC is stored as BCEntry, which keeps an index of left 
00026 //   part, an index of right part of BC and a weight of BC ( see comment
00027 //   below. ) There is a correspondence between the set of BC and the set 
00028 //   of natural numbers (0...(#ofBC-1)) given by a member of BasicCommutators
00029 //   BCEntry* entries.                  ( Note: less BC has less index )
00030 //   
00031 // 
00032 // * March 1997: remake
00033 //
00034 
00035 #ifndef _BASIC_COMMUTATOR_H_
00036 #define _BASIC_COMMUTATOR_H_
00037 
00038 #include "Vector.h"
00039 #include "Word.h"
00040 #include "Generator.h"
00041 #include "PolyWord.h"
00042 
00043 
00044 //====================================================================
00045 //====================== class BCEntry ===============================
00046 //====================================================================
00047 
00048 //@ep Borrowed from SL
00049 
00050 class BCEntry {
00051 
00052   //
00053   // Basic commutators are defined as follows:
00054 
00055   //   1. All generators of the free nilpotent group G are basic commutators of
00056   //   weight 1. Commutators of weight 1 are lineary ordered. If g and h
00057   //   are Generators then the order is defined by the function ord().
00058   //   2. If u and v are basic commutators of weight i and j respectively
00059   //   then ( u, v ) is a basic commutator of weight i + j if the following
00060   //   two conditions are satisfied:
00061   //     a. u > v
00062   //     b. If u = (u1,u2), where u1 and u2 are basic commutators, then u2 < v.
00063   //   The order on basic commutators u and v is defined in the following way:
00064   //     1. If weight of u is less than weight of v then u < v
00065   //     2. If weight of u is equal to weight of v, different from 1, than
00066   //        u = ( u1, u2 ), v = ( v1, v2 ) and order is defined
00067   //        lexicographically on pairs ( u1, u2 ) and ( v1, v2 ).
00068   //
00069 
00070   //------------------------------------------------------------------
00071   //  Constructors
00072   //------------------------------------------------------------------
00073 
00074 public:
00075 
00076   BCEntry( ) { }
00077 
00078   BCEntry(const Generator& g) : weight(1), rPart(ord(g)) { }
00079   // to make a basic commutator of a generator.
00080 
00081   BCEntry(int i) : weight(1), rPart(i) { }
00082   // to make a basic commutator of an integer representing a generator.
00083 
00084   BCEntry(int left, int right, int aWeight) :
00085     weight(aWeight), lPart(left), rPart(right)
00086   { }
00087   
00088 
00089   //------------------------------------------------------------------
00090   //  Operators
00091   //------------------------------------------------------------------
00092 
00093   BCEntry& operator = ( int i ) {
00094     weight = 1; 
00095     rPart = i; 
00096     return *this;
00097   }
00098 
00099 
00100   bool operator == ( const BCEntry& v ) const;
00101 
00102   bool operator != ( const BCEntry& v ) const {
00103     return ( !( *this == v ) );
00104   }
00105 
00106   bool operator < ( const BCEntry& v ) const;
00107 
00108   bool operator > ( const BCEntry& v ) const {
00109     return ( v < *this );
00110   }
00111 
00112   bool operator <= ( const BCEntry& v ) const {
00113     return ( *this == v || *this < v );
00114   }
00115 
00116   bool operator >= ( const BCEntry& v ) const {
00117     return ( *this == v || *this > v );
00118   }
00119 
00120   friend ostream& operator << (ostream& s, const BCEntry& );
00121 
00122   //------------------------------------------------------------------
00123   // IPC tools:                                                   
00124   //------------------------------------------------------------------
00125 
00126   friend ostream& operator < ( ostream& ostr, const BCEntry& BC )
00127   {
00128     ostr < BC.weight < BC.lPart < BC.rPart;
00129     return ostr;
00130   }
00131   
00132   friend istream& operator > ( istream& istr, const BCEntry& bc)
00133   {
00134     BCEntry& BC = (BCEntry&)bc;
00135     istr > BC.weight > BC.lPart > BC.rPart;
00136     return istr;
00137   }
00138   
00139   //------------------------------------------------------------------
00140   //   Friends:
00141   //------------------------------------------------------------------
00142 
00143   friend class BasicCommutators;
00144 
00145 
00146   //------------------------------------------------------------------
00147   //   Data members:
00148   //------------------------------------------------------------------
00149 
00150 private:
00151 
00152   int weight;
00153   int lPart, rPart;
00154 
00155 };
00156 
00157 
00158 
00159 //====================================================================
00160 //================ class BasicCommutators ============================
00161 //====================================================================
00162 
00163 
00164 class BasicCommutators {
00165 
00166 public:
00167 
00168 
00169   //------------------------------------------------------------------
00170   //  Constructors and initialization
00171   //------------------------------------------------------------------
00172 
00173   BasicCommutators(int numgen, int nilclass, bool initialize = true);
00174   // To construct the set of basic commutators which constitute a Mal'cev
00175   // basis for free nilpotent group of `numgen' generators and nilpotency
00176   // class `nilclass'.
00177   // Flag initialize shows whether the initialization should be
00178   // performed immediately or delayed
00179 
00180   //copy constructor, destructor and assignment operator provided by compiler
00181 
00182 
00183   void initialize() const;    // Logical const!
00184   // initializes uninitialized object
00185 
00186 
00187   //------------------------------------------------------------------
00188   //  Methods dealing with the whole set of basic commutators
00189   //  (accessors)
00190   //------------------------------------------------------------------
00191 
00192   int theHirschNumber() const { return theNumberOfBC; }
00193   // the Hirsch number (the number of basic commutators)
00194 
00195   int numberOfGenerators() const { return numGens; }
00196   // the number of generators
00197 
00198   int nilpotencyClass() const { return nilClass; }
00199   // the nilpotency class
00200 
00201   int numberOfWeight(int i) const { 
00202     return firstOfWeight.val(i+1) - firstOfWeight.val(i); 
00203   }
00204   // The number of basic commutators of given weight
00205 
00206   int theFirstOfWeight(int i) const { 
00207     return firstOfWeight.val(i);
00208   }
00209   // The number of first basic commutator of given weight
00210   
00211 
00212   bool isInitialized() const { return initialized; }
00213   // true iff the structure is initialized
00214 
00215   class NGWordForms wordForm() const;   // inline
00216   // produces an object of helper class
00217 
00218 
00219   //------------------------------------------------------------------
00220   //  Methods dealing with basic commutators
00221   //------------------------------------------------------------------
00222 
00223   // Here basic commutators are given by indices of corresponding
00224   // entries in the table
00225 
00226 
00227   //--------------- access to BCEntry properties ---------------------
00228 
00229   int weightOf(int i) const { 
00230     return entries.val(i).weight; 
00231   }
00232 
00233   int leftIndexOf(int i) const {
00234     return entries.val(i).lPart;
00235   }
00236 
00237   int rightIndexOf(int i) const {
00238     return entries.val(i).rPart;
00239   }
00240 
00241   virtual Chars commutatorName(int i) const {
00242     return (Chars)"c" + Chars(i);
00243   }
00244   // default name for basic commutator, can be overridden
00245     
00246   VectorOf<Chars> commutatorNames() const;
00247   // names of basic commutators
00248 
00249   //-------------- properties of commutator [g,h] --------------------
00250 
00251   bool commutatorIsBasic(int g, int h) const {
00252     if( g > numGens && entries.val(g).rPart > h)
00253       return false;
00254     return ( g > h );
00255   }
00256   // returns true iff the commutator [g,h] is proper basic.
00257 
00258   int findBC(int g, int h) const;
00259   // returns the index of the commutator [g,h].
00260   // If the commutator is not basic, generates an error.
00261   // If [g,h] = 1, returns 0.
00262 
00263   bool generatorsCommute(int g, int h) const {
00264     return ( entries.val(g).weight + entries.val(h).weight > nilClass );
00265   }
00266   // return true iff [g,h] = 1
00267 
00268 
00269   //------------- methods for collecting process ----------------------
00270 
00271 
00272   PolyWord commuteLetters(const Letter& left, const Letter& right) const;
00273   // If left.gen < right.gen, returns the word ( left + right ).
00274   // If left.gen == right.gen, collects them.
00275   // If left.gen > right.gen, commutes the letters.
00276   // "Commutes" means: result.firstLetter().gen < left.gen.
00277 
00278   PolyWord findCommutationRelation( Letter Cj, Letter Ci ) const;
00279   // finds a commutation relation for Ci^-1 Cj Ci
00280   // Note: only signs of powers are taken into account, not powers themselves
00281 
00282   PolyWord decomposeLetter(Letter C) const;
00283   // decomposes the given letter [a,b]^p into a PolyWord:
00284   // a^-1 b^-1 a b  a^-1 b^-1 a b  ...  a^-1 b^-1 a b (p times)
00285 
00286 
00287   //------------------------------------------------------------------
00288   //  I/O and debugging stuff
00289   //------------------------------------------------------------------
00290 
00291 
00292   friend ostream& operator < ( ostream& ostr, const BasicCommutators& BC );
00293   friend istream& operator > ( istream& istr, const BasicCommutators& BC );
00294   // IPC tools
00295 
00296   virtual void print( ostream& BClist, const VectorOf<Chars>& genNames ) const;
00297   // outputs basic commutators to a file
00298 
00299   //------------------------------------------------------------------
00300   //   Friends:
00301   //------------------------------------------------------------------
00302 
00303   friend class NGWordForms;
00304 
00305   //------------------------------------------------------------------
00306   //   Data members:
00307   //------------------------------------------------------------------
00308 
00309 
00310 private:
00311 
00312   int nilClass;
00313   // the nilpotency class
00314 
00315   int numGens;
00316   // the number of generators
00317 
00318   int theNumberOfBC;
00319   // the number of basic commutators
00320 
00321   bool initialized;
00322   // true iff the commutators are built
00323 
00324   VectorOf<int> firstOfWeight;
00325   // for fast access to basic commutators of certain weight.
00326   // firstOfWeight[i] is the index of the first basic commutator of weight i.
00327   // 1-based indices ( well, we don't have any BC's of weight less than 1. )
00328 
00329   VectorOf<BCEntry> entries;
00330   // ordered array of all basic commutators.
00331   // 1-based indices.
00332 
00333 };
00334 
00335 
00336 //===========================================================================
00337 //===================== class NGWordForms ===================================
00338 //===========================================================================
00339 
00340 
00341 // The class contains procedures that perform conversions of various word
00342 // presentations: PolyWord, Word in terms of the group, or basic commutators,
00343 // and so on.
00344 
00345 // This is merely a procedure package, controls no data.
00346 
00347 class NGWordForms {
00348 
00349 public:
00350 
00351   NGWordForms(const BasicCommutators& bc) : BC(bc) { }
00352   // The only constructor (except copy constructor)
00353 
00354 
00355   //@ep I deliberately use no conversion operators to avoid
00356   //    undesirable implicit conversions
00357 
00358 
00359   //-----------------------------------------------------------------
00360   //  Conversions to the Word
00361   //-----------------------------------------------------------------
00362 
00363   // A result of the conversion is a Word in terms of the group
00364   // generators
00365 
00366   Word toWord(int commIndex) const;
00367   // The argument is a commutator index
00368 
00369   Word toWord(const PolyWord& w) const;
00370   // The argument is a PolyWord in terms of basic commutators
00371 
00372   Word toGroupWord(const Word& basicWord) const;
00373   // The argument is a Word given in terms of basic commutators
00374 
00375 
00376   //-----------------------------------------------------------------
00377   //   Conversions to the text string
00378   //-----------------------------------------------------------------
00379 
00380 
00381   //--- to string in terms of basic commutators (c1, c2, c3....) ----
00382 
00383 
00384   Chars commutatorStructure(int commIndex) const;
00385   // If weight(commIndex) == 1, outputs generatorName(commindex).
00386   // Else outputs "[cj,ci]".
00387 
00388   Chars asCommutatorWord(const PolyWord& w) const;
00389   // Outputs the given word in terms of basic commutator names:
00390   //           c1 c2^-3 c4^2
00391 
00392   Chars asCommutatorWord(Letter s) const;
00393   // Outputs the given letter in terms of basic commutator names:
00394   //            c2^-3
00395 
00396 
00397   //---- to string in terms of group generators ----------------------
00398   //  Names of the generators are provided
00399 
00400 
00401   Chars asBracketedWord(int commIndex, const VectorOf<Chars>& genNames,
00402                         bool embeddingBrackets = true) const;
00403   // Produces a string representing the given basic commutator commIndex
00404   // as a word of genNames in commutator form, e.g.:
00405   //       [x,[x,y],z]
00406   // The parameter embeddingBrackets defines whether the outermost
00407   // brackets should present.
00408 
00409   Chars asBracketedWord(const PolyWord& w, const VectorOf<Chars>& genNames) const;
00410   // Outputs PolyWord in the bracketed form (in terms of group generators)
00411 
00412 
00413 private:
00414 
00415   const BasicCommutators& BC;
00416 
00417 };
00418 
00419 
00420 inline NGWordForms BasicCommutators::wordForm() const {
00421   return NGWordForms(*this);
00422 }
00423 // produces an object of helper class
00424 
00425 
00426 #endif
00427 
00428 
00429 
00430 
00431 
00432 
00433 
00434 
00435 
00436 

Generated at Tue Jun 19 09:49:37 2001 for Magnus Classes by doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001