Logo Search packages:      
Sourcecode: magnus version File versions  Download package

QEqnSolutions.C

// Copyright (C) 1994 The New York Group Theory Cooperative
// See magnus/doc/COPYRIGHT for the full notice.

// Contents: Implementation of class QEqnSolutionsInFreeGroup
//
// Principal Authors: Dmitry Pechkin, Eugeny Paderin
//
// Status: Under trial
//
// Revision History:
//
// * 7/96 Dmitry B. made porting to gcc 2.7.2.
//
// * 10/96 EP has added a routine for checking equation validity.

// Special Notes:
//
// Here is a brief description of Comerford & Edmunds main ideas.
//
// Any solution of W = 1 over group G can be represented as S*P*E,
// where S is an automorphism mapping W to itself (i.e. element of
// stabilizer of W in Aut(G), P is a certain endomorphism from a
// finite set of "basic solutions", and E is any "specializing"
// endomorphism. According to Comerford & Edmunds (C&E), we can
// choose P as some combinations of elementary Nielsen transformations
// (to be exact, elementary regular automorphisms (ERA) x -> xy, not
// lengthening the word, and elementary singular endomorphisms (ESE)
// x -> 1, shortening the word; here x is a variable). In this case,
// instead of stabilizer we can take its regular subset RegStab,
// generated by RA.
//
// Let W be a minimal word (i.e. it cannot be shortened by RA). We
// build a graph where vertices are images of W (their number is finite),
// and edges are ERA mapping one word to another. Then elements of
// RegStab are all the reduced paths starting and ending at W; if we
// find some (any) maximal subtree in the graph, then any edge not
// included in the tree defines certain generator of RegStab.
//
// If there is a path (RA) R leading from W to some vertex V, and T
// is a SE mapping V to 1, then TR is a solution of W=1. C&E say
// that all these TR make a set of basic solutions of W=1.
//
// If W is not minimal, then we necessarily find a shorter word
// when building the graph. C&E say: if V is some minimal image of W
// and N is RA mapping W to V, then solutions of W and V are the same
// up to N. So we can find a stabilizer and basic solutions for V
// and then multiply them to N (if S is a generator of RegStab(V),
// then NSN^-1 is a generator of RegStab(W), and if P is a basic
// solution of V then NP is one of W).
//

#include "QEqnSolutions.h"
#include "GeneralWhitehead.h"
//#include "SGofFreeGroup.h"
#include "unistd.h"
#include "VertexInfo.h"


//@db 2.91 these functions are defined at the end of this file 
//    (template instantiation)

//@njz:
//int SetData<Endomorphism>::hashElement(const Endomorphism& t) const;
//int SetData<Automorphism>::hashElement(const Automorphism& t) const;
//int SetData<QEqnSolutionsInFreeGroup::Edge>
//      ::hashElement( const QEqnSolutionsInFreeGroup::Edge& t) const;
//int SetData< QuickAssociation<Word,ElementaryRegularAuto> >
//      ::hashElement( const QuickAssociation<Word,ElementaryRegularAuto>& t) 
//      const;
//int SetData< QuickAssociation<Automorphism,Automorphism> >
//      ::hashElement( const QuickAssociation<Automorphism,Automorphism>& t) 
//      const;
template <> int SetData<Endomorphism>::hashElement(const Endomorphism& t) const;
template <> int SetData<Automorphism>::hashElement(const Automorphism& t) const;
template <> int SetData<QEqnSolutionsInFreeGroup::Edge>
      ::hashElement( const QEqnSolutionsInFreeGroup::Edge& t) const;
template <> int SetData< QuickAssociation<Word,ElementaryRegularAuto> >
      ::hashElement( const QuickAssociation<Word,ElementaryRegularAuto>& t) 
      const;
template <> int SetData< QuickAssociation<Automorphism,Automorphism> >
      ::hashElement( const QuickAssociation<Automorphism,Automorphism>& t) 
      const;
//

//@db 2.95

//@njz
//void QueueOf<QEqnSolutionsInFreeGroup::Edge>::push(const QEqnSolutionsInFreeGroup::Edge& t);
template <> void QueueOf<QEqnSolutionsInFreeGroup::Edge>::push(const QEqnSolutionsInFreeGroup::Edge& t);
//


//////////////////// constructor //////////////////////////////////

QEqnSolutionsInFreeGroup::QEqnSolutionsInFreeGroup(const FreeGroup& G,
                                       const Word& equation, int numOfVar)
  :
  theEquation(equation),
  theNumberOfGenerators(G.numberOfGenerators()),
  theNumberOfVariables(numOfVar),
  theGroup(G),
  theRank(-1),

  // initialize flags
  computationIsStarted(false),
  computationIsDone(false),
  tempRank(-1),

  // these data members have no default constructor
  // so we initialize them by a dummy value.
  // Proper value is assigned when all necessary information
  // is gathered

  removeVarEndo(theGroup),
  toSurface(theGroup),
  surfaceFormIsComputed(false),
  startPath(theGroup),
  invStartPath(theGroup),

  theEliminator(theGroup)
{

  // set up the eliminator

  for(int i= theNumberOfVariables; i < theNumberOfGenerators; i++) {
    theEliminator.setGeneratingImages(i, Generator(i+1));
  }

  status.enableBuildingSolutions = true;
  status.enableBuildingRegStab = true;

}

///////////////////////// TREE BUILDER ///////////////////////////////////

// This is an iteration of tree building process

// The maximal subtree is represented with pairs (associations) of
// a word (some image of the root) and an edge -- an elementary
// regular transformation mapping the word to its PARENT. So,
// edges in the tree are directed from offsprings to parents,
// and we can easily reconstruct a regular automorphism mapping
// the root to the vertex.

void QEqnSolutionsInFreeGroup::startComputation()
{
  // On start we should prepare: initial vertex (root) of tree
  // which is a minimal form of the equation;
  // automorphism (startPath) mapping theEquation to root;

  root = toSurfaceForm().imageOf(theEquation).freelyReduce(); 
  // Take a minimal form.
  // Comerford & Edmunds work with free reduced words, but not cyclically 
  // reduced ones.

  if( root.length() == theEquation.length() ) {
    // The equation has minimal form, use it as root.
    root = theEquation;
    // startPath is the identity auto.
  }
  else {
    //
    startPath = toSurface;
    invStartPath = Automorphism(theGroup, theGroup.inverseAutomorphism(startPath.generatingImages()));

#ifdef DEBUG 
    {
      if( root.length()-root.cyclicallyReduce().length() > 2 )
      error("internal error: too many cyclic reductions in the surface "
            "automorphism in QEqnSolutionsInFreeGroup::startComputation()");
                  
      Automorphism id = startPath | invStartPath;
      id.reduceGenImages();
      for(int i = 0; i<theNumberOfGenerators; i++)
      if( !(id.imageOf(Generator(i+1)) == Word(Generator(i+1))) )
        error("can't construct the inverse of the surface automorphism "
            "in QEqnSolutionsInFreeGroup::startComputation()");
    }
#endif
  } 

/*******************************
  // Now we are trying to apply some Whitehead automorphism to constants
  // to reduce their number.

  Word letters = theEliminator.imageOf(root).freelyReduce();
  Automorphism WhiteheadAuto(theGroup);

  if(letters.length() != 1) {
    GeneralWhitehead gw(theGroup);
    gw.startComputation(letters);
    while(! gw.continueComputation() );

    if(gw.extendsToFreeBasis() ) {

      WhiteheadAuto = (Automorphism)gw.getAutomorphism();
      Word reducedWord = WhiteheadAuto.imageOf(letters).freelyReduce();
      if(reducedWord.length() != letters.length() ) {
      startPath = startPath | WhiteheadAuto;
      root = WhiteheadAuto.imageOf(root);

#ifdef DEBUG
      int reduction = letters.length() - reducedWord.length();
      Word reducedEquation = startPath.imageOf(theEquation);
      if(reducedEquation != root || theEquation.length() - root.length() != reduction) {
        error("Internal error in QEqnSolutions::startComputation: bad Whitehead reduction");
      }

      cout << "Whitehead automorphism is: " << endl << WhiteheadAuto << endl;
      cout << "Reduced word is: " << root << endl;

#endif
      }
    }
  }
********************************/


  maxSubTree = QuickAssociationsOf<Word, ElementaryRegularAuto>();
  theRegStabGenerators = VectorPtrOf<Automorphism>(0, true);
  generator = 0;
  theBasicSolutions = VectorPtrOf<Endomorphism>(0, true);
  solution = 0;

  // newVertices is a collection of vertices to be proceed; 
  // we will move them to the maxSubtree
  newVertices.push(root);
  ElementaryRegularAuto dummy(1,2);
  maxSubTree.bind(root, dummy);

  // statistics accumulation.
  status.verticesToPass = 1;

  regStabSet = SetOf<Automorphism>();
  Automorphism identity(theGroup);
  regStabSet |= identity;
  // store identinty to prevent to place the one as new found regStabGen.

  // Make Endo which removes all variables from a word, leaves only constants.
  // It is used for building of basic solutions.
  // This Endo is a trivial one by constructor so we need to redefine
  // mapping of constants.
  for(int c = theNumberOfVariables; c < theNumberOfGenerators; c++) 
    removeVarEndo.setGeneratingImages(c, Generator(c+1));

  computationIsStarted = true;
  computationIsDone = false;
}

void QEqnSolutionsInFreeGroup::continueComputation()
{
  if( computationIsDone ) return;
  if( !computationIsStarted )
    error("calling `continueComputation' without `startComputation' for "
        "QEqnSolutionsInFreeGroup");
  if( newVertices.isEmpty() ) {
    // Clean up work structures.
    regStabSet = SetOf<Automorphism>();
    maxSubTree = QuickAssociationsOf<Word, ElementaryRegularAuto>();
    setOfBasicSolutions = SetOf<Endomorphism>();

    theRank = tempRank;
    if(theRank == -1) theRank = 0;

    computationIsDone = true;
    return;
  }

  // proceed one vertex 

  int lastKnownSolution = theBasicSolutions.length();
  Word curVertex = newVertices.pop();

  if( status.enableBuildingSolutions )
    buildSolutionsOfOneVertex(curVertex);

  buildNewVerticesAndLoopsFrom(curVertex);

  // statistics accumulation.
  status.verticesToPass--;
  status.verticesPassed++;


  // proceed all loops which are found on this iteration.

  while( !loops.isEmpty() ) {
    if( status.enableBuildingRegStab )
      processOneLoop( loops.pop() );
    else
      loops.pop();

    // statistics accumulation.
    status.loopsToPass--;
    status.loopsPassed++;
  }

  // compute rank of new solutions which found at current iteration.
  for(int i = lastKnownSolution; i<theBasicSolutions.length(); i++)
    tempRank = max(tempRank, rankOfBasicSolution(theBasicSolutions[i]));

}

void QEqnSolutionsInFreeGroup::buildNewVerticesAndLoopsFrom(const Word& vertex)
{
  // during this iteration we proceed all "offsprings" of the
  // curVertex -- find all regular automorphisms applicable
  // to the curVertex

  for(int i = 0; i < vertex.length()-1; i++) {
    // take a pair of neighbors
    Generator x = vertex[i];
    Generator y = vertex[i+1];
    if( x != y ) {
      if( isVariable(x) ) {
      // x is a variable, and we can apply the mapping x -> x y^-1
      ElementaryRegularAuto phi(x, inv(y));
      Word newVertex = phi(vertex).freelyReduce();
      registerEdge(vertex, phi, newVertex);
      }
      if( isVariable(y) ) {
      // y is a variable, and we can apply the mapping
      // y^-1 -> y^-1 x  (the same as y -> x^-1 y)
      ElementaryRegularAuto theta(inv(y), x);
      Word newVertex = theta(vertex).freelyReduce(); 
      registerEdge(vertex, theta, newVertex);
      }
    }
  } 
}

// builds a path from one vertex to another within the built subtree

// This function never used immediately in the program; instead, we
// use buildPathTo (see below). But the function is very general and
// can be used in future improvements.

RegularAuto QEqnSolutionsInFreeGroup::buildPath(const Word& from, 
                                    const Word& to)
{
  RegularAuto path;
  Word curVertex = from;
  while( curVertex != to ) {
    ElementaryRegularAuto phi = maxSubTree.valueOf(curVertex);
    path = path | phi;
    curVertex = phi(curVertex).freelyReduce();
  }
  return path;
}

// Builds path from the root to the given word

RegularAuto QEqnSolutionsInFreeGroup::buildPathTo(const Word& destination)
{
  return buildPath(destination, root).inv();
}

// Tries to include the given edge to the subtree. If the edge
// forms a loop we certainly should not include; instead, we place it
// to the list of loops.

void QEqnSolutionsInFreeGroup::registerEdge(const Word& source,
                                  const ElementaryRegularAuto& edge, const Word& target)
{
  if( maxSubTree.bound(target) ) {
    // the target vertex already presents in the tree
    if( edge != maxSubTree[source] ) {
      // if equals, then target is the source's parent, and
      // we discard this edge. Otherwise, it is a loop.
      loops.push( Edge(source, edge) );

      // statistics accumulation.
      status.loopsToPass++;
    }
  }
  else {
    // the target does not present in the tree -- so it will.
    maxSubTree.bind(target, edge.inv());
    newVertices.push(target); // to be proceeded

    // statistics accumulation.
    status.verticesToPass++;
  }
}

//////////////// BASIC SOLUTION BUILDER /////////////////////////////

// builds solutions for the given word

void QEqnSolutionsInFreeGroup::buildSolutionsOfOneVertex(const Word& w)
{
  // quick check for equations with quotients:
  // if we eliminate all variables and the word does not reduce
  // to 1 then there is no solutions at all

  if( removeVarEndo.imageOf(w).freelyReduce().length() != 0 ) return;

      // analyze every variable whether it can/must be eliminated

  VectorOf<int> varProperties = checkProperties(w);

  // rootEndo eliminates those variables that must be eliminated in
  // any case

  Endomorphism rootEndo(theGroup);
  rootEndo.makeIdentity();
  Word emptyWord;

  for(int variable = 0; variable<theNumberOfVariables; variable++) {
    if( varProperties[variable] == MUST_BE_MAPPED_TO_1 ) 
      rootEndo.setGeneratingImages(variable, emptyWord );
  }

  Word localRoot = rootEndo.imageOf(w).freelyReduce();

      // build solutions of the reduced word

  ListOf<SingularEndo> solutions = buildSingulars(localRoot, varProperties);

  // The returned solutions are endos mapping localRoot to 1. To obtain
  // solutions of theEquation, we must append (left) the path from
  // root to localRoot.

  rootEndo = buildPathTo(w).makeAutomorphism(theGroup) | rootEndo;
  rootEndo.reduceGenImages();
      
  ListIterator< ListOf<SingularEndo> > I(solutions);

  while( ! I.done() ) {
    Endomorphism solution = rootEndo | I.value().makeEndomorphism(theGroup);
    solution.reduceGenImages();
    if( !setOfBasicSolutions.contains( solution ) ) {
      theBasicSolutions.append(solution);
      setOfBasicSolutions |= solution;
    }
    I.next();
  }

  // Note that if V is a cyclic permutation of W then it has
  // the same solutions as W. So we could build all solutions
  // for W and then find all its (and its inverse's) cyclic
  // permutations and generate their solutions immediately.
  // We did not implement this idea, because there were suspicions
  // that in some cases it can greatly slow down performance.
  // This requires careful studying...

}

// checks for every variable of the group whether it can/must/cannot
// be eliminated in given word w. Running costs are O(|w|).

VectorOf<int> QEqnSolutionsInFreeGroup::checkProperties(const Word& w)
{
  enum  { NO_OCCURRENCE   = 0,
        POSITIVE_POWERS = 2,  //@ep or "degrees"?
        INVERSE_POWERS  = 3,
        NEGATIVE_POWERS = 4
  };    // the numeric values are hard-wired and cannot be changed

  static const int UNDEFINED_LOCATION = -1;

  VectorOf<int> varProperties(theNumberOfVariables);
  VectorOf<int> firstLocation(theNumberOfVariables);
  VectorOf<int> lastLocation(theNumberOfVariables);

  for(int variable = 0; variable<theNumberOfVariables; variable++) {
    varProperties[variable]  = NO_OCCURRENCE;
    firstLocation[variable] = UNDEFINED_LOCATION;
    lastLocation[variable]  = UNDEFINED_LOCATION;
  }

  // explore for every pair of variables what are their powers

  for(int pos = 0; pos<w.length(); pos++) {
    int Ord = abs(ord(w[pos]))-1;
    if( Ord < theNumberOfVariables ) {
      varProperties[Ord] = (int)varProperties[Ord] + ( ord(w[pos]) > 0 ? 1 : 2 );
      //@ep a bit tricky construction, but simple and effective

      if( firstLocation[Ord] == UNDEFINED_LOCATION )
      firstLocation[Ord] = pos;
      else
      lastLocation[Ord] = pos;
    }
  }

  // determine a destiny of every variable

  Word piece;
  for(int variable = 0; variable<theNumberOfVariables; variable++) {
    switch( varProperties[variable] ) {
    case POSITIVE_POWERS:
    case NEGATIVE_POWERS:
      varProperties[variable] = MUST_BE_MAPPED_TO_1;
      break;
      // the variables are of the same power, so they
      // never will reduce and must be eliminated

    case INVERSE_POWERS:
      piece = w.subword( (int)firstLocation[variable]+1, (int)lastLocation[variable]);
      if( removeVarEndo.imageOf(piece).freelyReduce().length() == 0 )
      varProperties[variable] =  CAN_BE_MAPPED_TO_1;
      else
      varProperties[variable] = MUST_BE_MAPPED_TO_1;
      break;
      // we can eliminate the inverses or leave them hoping
      // that they will reduce. But if there are constants
      // between them which do not reduce, the variables
      // must be eliminated.

    case NO_OCCURRENCE:
      varProperties[variable] = MUST_BE_MAPPED_TO_ITSELF;
      // there is no such variable in the word
    }
  }
  return varProperties;
}


// this procedure immediately builds a graph of eliminations

ListOf<SingularEndo> QEqnSolutionsInFreeGroup::buildSingulars(
                                                const Word& w, const VectorOf<int>& varProperties)
{
  QueueOf<VertexInfo> vertices;
  ListOf<SingularEndo> solutions; // output solutions

  vertices.push( VertexInfo(w,-1,SingularEndo() ));

  // perform the procedure for every element of vertices

  while( vertices.isntEmpty() ) {
    VertexInfo vertex = vertices.pop();

    // if the word is reduced then register the new solution

    if( vertex.word.length() == 0 )
      appendNewSolution(solutions, vertex.eliminator);
    else

      // build new eliminations

      for(int variable = vertex.lastVar+1; variable<theNumberOfVariables; variable++) {
      if( varProperties[variable] == CAN_BE_MAPPED_TO_1 &&
          vertex.word.numberOfOccurrences(variable+1) > 0 )
        {
          Word u = vertex.word.replaceGeneratorWithWord(variable+1, Word()).freelyReduce();
          SingularEndo el = vertex.eliminator | ElementarySingularEndo(Generator(variable+1));
          vertices.push( VertexInfo(u,variable,el) );
        }
      }
  }

  return solutions;
}

// include new solution to the list of solutions, unless it is a
// specialization of one of the list

void QEqnSolutionsInFreeGroup::appendNewSolution(
                                     ListOf<SingularEndo>& solutions, const SingularEndo& newSolution)
{
  ListIterator< ListOf<SingularEndo> > I(solutions);

  while( ! I.done() ) {
    if( newSolution.isSpecializationOf(I.value()) ) return;
    I.next();
  }

  solutions.append( newSolution );
}


/////////////////////// RANK COMPUTATION //////////////////////////

int QEqnSolutionsInFreeGroup::rankOfBasicSolution(const Endomorphism& solution)
const
{
  VectorOf<Word> images = solution.generatingImages();
  /*
    SGofFreeGroup G(theGroup, images);
    VectorOf<Word> nielsen = G.nielsenBasis();
    */
  VectorOf<Word> nielsen = theGroup.nielsenBasis(images);
  return nielsen.length();
}



/////////////////////// REGSTAB BUILDER ///////////////////////////

// Here we find generators of RegStab. A generator is defined by
// an edge mapping A to B and forming a loop.


// builds a generator

void QEqnSolutionsInFreeGroup::processOneLoop(const Edge& e)
{
  // construct a cyclic path

  RegularAuto come = buildPathTo(e.vertex);
  RegularAuto back  = buildPathTo(e.edge(e.vertex).freelyReduce());
  RegularAuto loop =  come | e.edge | back.inv();

  status.totalLengthOfLoops += loop.getAutoList().length();

  // convert the cycle to the "real" automorphism

  Automorphism gen = loop.makeAutomorphism(theGroup);
  Automorphism genInv = loop.inv().makeAutomorphism(theGroup);
  gen.reduceGenImages();
  genInv.reduceGenImages();

      // include the new gen to the set of generators (unless it or its inverse
      // already is there)

  if( !regStabSet.contains(gen) && !regStabSet.contains(genInv) ) {
    regStabSet |= gen;
    theRegStabGenerators.append(gen);
  }
}

//////////////////// I/O routines /////////////////////////////////////

// a helper routine showing state of the process

ostream& operator <<(ostream& o, const QEqnSolutionsInFreeGroup& equation)
{
  o << "THE QUADRATIC EQUATION IN THE FREE GROUP:" << endl;
  o << "  free group := " << equation.group() << "," << endl;
  o << "  number of generators := " << equation.numberOfGenerators() << "," << endl;
  o << "  number of variables := " << equation.numberOfVariables() << "," << endl;
  o << "  number of constants := " << equation.numberOfConstants() << "," << endl;
  o << "  equation := ";
  equation.theGroup.printWord(o, equation.theEquation);
  o << "," << endl;

  o << "  status := rec( " << endl;
  if( equation.isComputationDone() )
    o << "     computation is done " << endl;
  else if( equation.isComputationStarted() )
    o << "     computation is in progress " << endl;
  else
    o << "     computation is not started " << endl;
  o << "  )," << endl;

  o << "  solutions := rec(" << endl;
  if( equation.basicSolutions().length() == 0 )
    o << "     has no basic solutions" << endl;
  else {
    o << "     has " << equation.basicSolutions().length();
    o << " basic solutions, " << endl;
    for(int i = 0; i<equation.basicSolutions().length(); i++) {
      o << "     solution #" << i+1 << ": "; // << endl;
      o << (Endomorphism)equation.basicSolutions()[i] << "," << endl;
    }
  }
  o << "  )," << endl;

  o << "  rank := " << equation.rank() << "," << endl;

  o << "  regstab := rec(" << endl;
  if( equation.regStabGenerators().length() == 0 )
    o << "     trivial group" << endl;
  else {
    o << "     has " << equation.regStabGenerators().length();
    o << " generator(s)," << endl;
    for(int gen=0; gen<equation.regStabGenerators().length(); gen++) {
      o << "     generator #" << (gen+1) << ": "; // << endl;
      o << (Automorphism)equation.regStabGenerators()[gen] << "," << endl;
    }
  }
  o << "  )" << endl;

  o << ")" << endl;

  return o;
}

void QEqnSolutionsInFreeGroup::computeSurfaceForm()
{
  Word w = theEquation;
  Word squares, commutators, pinches;
  // squares, commutators, pinches are processed parts of the equation,
  // w is a rest.
  // logical order when combine them together is (left to right): 
  //     squares * commutators * w * pinches
  // hence new found pinch is appended left to previously found pinches,
  // and new found square or commutator is appended right to previously
  // found squares/commutators.

  // quick check

  if( w.length() == 0 ||
      getLocationOfArbitraryVariable(w,0,w.length()) == -1 ) {
    // empty word or it has no variables - computation is not required.
    theSurfaceForm = w;
    surfaceFormIsComputed = true;
    return;
  }

  // First search squares.

  int firstLocation, secondLocation;
  bool oppositeOrders = false; 
  while( getPairOfVariable(w,firstLocation,secondLocation,oppositeOrders) ) {
    squares *= extractSquare(w, firstLocation, secondLocation);
  }

  // Then search for commutators and pinches.
  // these transformations don't change degrees of variables, so
  // squares cann't be came anew.

  oppositeOrders = true;
  while( getPairOfVariable(w, firstLocation,secondLocation,oppositeOrders) ) {
    int yLocation = getLocationOfArbitraryVariable(w, firstLocation+1, 
                                       secondLocation);
    if( yLocation != -1 ) 
      commutators *= extractCommutator(w, firstLocation, secondLocation, 
                               yLocation);
    else
      pinches = extractPinch(w, firstLocation, secondLocation) * pinches;
  }

  if( w.length() > 0 && 
      getLocationOfArbitraryVariable(w,0,w.length()) != -1 )
    error("Internal error or bad equation "
        "in QuadraticEquationRep::computeSurfaceForm()");

  theSurfaceForm = bringToCanonicForm(squares, commutators, w, pinches);
  surfaceFormIsComputed = true;
}

Word QEqnSolutionsInFreeGroup::extractSquare(Word& w, int firstLocation,
                                   int secondLocation)
{
  // w = u x v x z,
  // x is the variable found, u,v,z are subwords

      // Extract components of w.
  Generator x = w[firstLocation];
  Word u = w.initialSegment(firstLocation);
  Word v = w.subword(firstLocation+1, secondLocation);
  Word z = w.terminalSegment(w.length()-secondLocation-1);
  Word U = u.inverse();
  Word V = v.inverse();

      // (uxvxz) is mapped to (xxuVz) by automorphism
      // phi:  x -> UxuV, the others to themselves

  Word t = U * x * u * V;
  toSurface = toSurface | Automorphism(theGroup, x, t);
  toSurface.reduceGenImages();

  w = (u * V * z).freelyReduce(); // the rest is uVz

  return x*x;
}

Word QEqnSolutionsInFreeGroup::extractPinch(Word& w, int firstLocation,
                                  int secondLocation)
{
  // We have : w = u x c X r, where u, r are words, x is a variable, 
  // c is a word of constants.
  // now transform to w' = u r x c X  by automorphism phi: x -> rx

  // Extracts components of w.
  Generator x = w[firstLocation];
  Word u = w.initialSegment(firstLocation);
  Word c = w.subword(firstLocation+1, secondLocation);
  Word r = w.terminalSegment(w.length()-secondLocation-1);

      // Make the transformation and transformed form of w.
  Word t = r * x;
  toSurface = toSurface | Automorphism(theGroup, x, t);
  toSurface.reduceGenImages();
  w = (u * r).freelyReduce();

  return x * c * inv(x);
}

Word QEqnSolutionsInFreeGroup::extractCommutator(Word& w, int xFirstLocation,
                                     int xSecondLocation, int yFirstLocation)
{
  // w = u x p y v X z Y t,
  // x,y are commuting generators,  u,p,v,z,t are subwords
      
      // Extracts components of w.
  Generator x = w[xFirstLocation];
  Generator X = inv(x);
  Generator y = w[yFirstLocation];
  Generator Y = inv(y);

      // Search second occurrence of the variable y in the word w.
  int ySecondLocation;
  for(ySecondLocation = xSecondLocation+1; w[ySecondLocation] != Y;
      ++ySecondLocation) {
    // empty body of `for'
  }
      
  // Extract components of w.
  Word u = w.initialSegment(xFirstLocation);
  Word p = w.subword(xFirstLocation+1, yFirstLocation);
  Word v = w.subword(yFirstLocation+1, xSecondLocation);
  Word z = w.subword(xSecondLocation+1, ySecondLocation);
  Word t = w.terminalSegment(w.length()-ySecondLocation-1);

  // (uxpyvXzYt) is mapped to (uzv xyXY pt) by
  // automorphism x -> zvx, y -> PyV, the others stable.
  // Then we conjugate x, y by (uzv) obtaining (xyXY uzvpt)
      
      // Make the transormation.
      
  Word uzv = (u * z * v).freelyReduce();
  Word tmp = u.inverse() * x * uzv;
  Automorphism phi(theGroup, x, tmp);
  phi.setGeneratingImages(y, p * uzv.inverse() * y * u * z );
      
  toSurface = toSurface | phi;
  toSurface.reduceGenImages();

  w = (uzv * p * t).freelyReduce(); // the new rest is uzvpt
      
  return x*y*X*Y;
}

int QEqnSolutionsInFreeGroup::getLocationOfArbitraryVariable(
                                               const Word& w, int start, int stop) const 
{
#if SAFETY > 0
  if( start >= stop || start < 0 || stop > w.length() ) 
    error("QEqn::getLocationOfArbitaryVariable(): indices out of bounds");
#endif

  for(int i = start; i < stop; i++)
    if( isVariable(w[i]) )
      return i;

  return -1;
}

int QEqnSolutionsInFreeGroup::getPairOfVariable(Word& w, int& firstLocation,
                                    int& secondLocation, bool oppositeOrders) const
{
  if( w.length() == 0 ) return false;

  VectorOf<int> pos(2*theNumberOfVariables+1);
  // pos is a vector of positions of variables in w. A generator g
  // has index ord(g) + theNumberOfVariables.
  // This will help us to search for pairs of generators.

  const int undefined = -1; // marks undefined position of generator

  for(int i=0; i<pos.length(); i++)  // initializing pos
    pos[i] = undefined;

  // forming pos until first pair of opposite variables is found

  for(int i=0; i<w.length(); i++)   {  
    int thisGen = ord(w[i]);
    if( isConstant(thisGen) ) continue;
    int indexOfGen = theNumberOfVariables + thisGen;
    if( oppositeOrders ) {
      int indexOfInvGen = theNumberOfVariables - thisGen;
      if( pos[indexOfInvGen] != undefined ) {
      firstLocation  = pos[indexOfInvGen];
      secondLocation = i;
      return true;
      }     
      pos[indexOfGen] = i;
    }
    else {
      if( pos[indexOfGen] != undefined ) {
      firstLocation  = pos[indexOfGen];
      secondLocation = i;
      return true;
      }
      pos[indexOfGen] = i;
    }
  }
  return false;
}


Word QEqnSolutionsInFreeGroup::bringToCanonicForm(Word& squares, 
                                      Word& commutators, Word constants, Word& pinches)
{
  if( squares.length() > 0 && commutators.length() > 0 ) {
    while( commutators.length() > 0 ) {
      // w = ... z z x y X Y ...
      //  (zzxyXY) can be mapped to (zzxxyy) by automorphism
      //  z -> zzxZy,  x -> YzXZZy,  y -> YYZy
      Generator x = commutators[0];
      Generator y = commutators[1];
      Generator z = squares[squares.length()-1];
      Generator X = inv(x);
      Generator Y = inv(y);
      Generator Z = inv(z);

      Word t = z*z*x*Z*y;
      Automorphism phi(theGroup, z, t);
      phi.setGeneratingImages(x, Y*z*X*Z*Z*y);
      phi.setGeneratingImages(y, Y*Y*Z*y);
                  
      toSurface = toSurface | phi;
      toSurface.reduceGenImages();
      commutators = commutators.terminalSegment( commutators.length()-4 );
      squares *= x * x * y * y;
    }
  }

  Automorphism theta(theGroup);

  for(int i = 0; i < squares.length(); i+=2) {
    Generator x = squares[i];
    if( ord(x) < 0 ) theta.setGeneratingImages(x, (Word)inv(x));
  }
  squares = theta.imageOf(squares).freelyReduce();

  for(int i = 0; i < commutators.length(); i+=4) {
    Generator x = commutators[i];
    if( ord(x) > 0 ) theta.setGeneratingImages(x, (Word)inv(x));
    Generator y = commutators[i+1];
    if( ord(y) > 0 ) theta.setGeneratingImages(y, (Word)inv(y));
  }
  commutators = theta.imageOf(commutators).freelyReduce();

  for(int i = 0; i < pinches.length(); i++) {
    Generator x = pinches[i];
    // Generator X = inv(x);
    if( ord(x) > 0 ) theta.setGeneratingImages(x, inv(x));
    while( isConstant(pinches[++i]) ) ; // skip constants
  }
  pinches = theta.imageOf(pinches).freelyReduce();

  toSurface = toSurface | theta;
  toSurface.reduceGenImages();

  if( constants.length() == 0 ) {
    if( pinches.length() > 0 ) {
      Generator Z = pinches[0];
      Generator z = inv(Z);
      Automorphism phi(theGroup);
      if( squares.length() > 0 ) {
      for(int i = 0; i < squares.length(); i+=2) {
        Generator x = squares[i];
        phi.setGeneratingImages(x, Z * x * z);
      }
      }
      else if( commutators.length() > 0 ) {
      for(int j = 0; j < commutators.length(); j+=4) {
        phi.setGeneratingImages(commutators[j+2], Z * commutators[j+2] * z);
        phi.setGeneratingImages(commutators[j+3], Z * commutators[j+3] * z);
      }
      }

      // Processes 2nd and next pinches, but first skip 1st pinch.
      int k = 0;
      while( isConstant(pinches[++k]) ) {} // skip constants
      constants = pinches.subword(1,k);
      pinches = pinches.subword(k+1, pinches.length());
      for(k = 0; k < pinches.length(); k++) {
      Generator T = pinches[k];
      Generator t = inv(T);
      phi.setGeneratingImages(t, t * z);
      while( isConstant(pinches[++k]) ) {} // skip constants
      }
      toSurface = toSurface | phi;
      toSurface.reduceGenImages();
    }
  }

  return (squares * commutators * constants * pinches).cyclicallyReduce();
}


#ifdef DEBUG

void QEqnSolutionsInFreeGroup::debugPrint( ostream& o ) const
{
  o << "[enableBuildingSolutions = " << status.enableBuildingSolutions
    << ", enableBuildingRegStab = " << status.enableBuildingRegStab << "," 
    << endl 
    << " vertices (passed/remain) = " << status.verticesPassed << "/" 
    << status.verticesToPass << ", loops (passed/remain) = " 
    << status.loopsPassed << "/" << status.loopsToPass 
    << "average length of loops = " 
    << (status.loopsPassed>0 ? status.totalLengthOfLoops/status.loopsPassed :0)
    << "]";
}

#endif



int hash(const Map& map)
// for use Map objects in sets
// tentative implementation
{
  int h = 0;
  int g;
  int i = map.generatingImages().length();
  while ( i-- > 0  ) {
    h = (h << 4) + map.generatingImages(i).hash();
    if ((g = h & 0xf0000000) != 0)
      h = (h ^ (g >> 24)) ^ g;
  }
  return h;
}

//
//  Some (temporary?!) hacks since gcc 2.6.3 doesn't do templates right:
//

int SetData<Endomorphism>::hashElement(const Endomorphism& t) const
{ return hash(t); }

int SetData<Automorphism>::hashElement(const Automorphism& t) const
{ return hash(t); }

int SetData<QEqnSolutionsInFreeGroup::Edge>::hashElement(
                                           const QEqnSolutionsInFreeGroup::Edge& t) const { return t.hash(); }

int SetData< QuickAssociation<Word,ElementaryRegularAuto> >::hashElement(
                                                       const QuickAssociation<Word,ElementaryRegularAuto>& t) const
{ return t.hash(); }

int SetData< QuickAssociation<Automorphism,Automorphism> >::hashElement(
                                                      const QuickAssociation<Automorphism,Automorphism>& t) const
{ return t.hash(); }

//@db 2.95
void QueueOf<QEqnSolutionsInFreeGroup::Edge>::push(const QEqnSolutionsInFreeGroup::Edge& t)
{ 
  append(t); 
}



///////////////@ep added on October 1996 ////////////////////////////////////////////


Chars checkEquation(const FreeGroup& G, const Word& equation, int numOfVar) {

  int numOfGen = G.numberOfGenerators();
  if( numOfVar == 0 ) 
    return "Equation should have at least one variable.";

  // is this a real quadratic equation? (Every variable must
  // occur 0 or 2 times, and all constants must have ord not greater
  // than numOfGen).

  Word eq = equation.freelyReduce();

  int *occurrences = new int[numOfGen];

  for(int i=0; i<numOfGen; i++)
    occurrences[i] = 0;

  // count number of occurrences of every generator
  for(int i=0; i<eq.length(); i++) {
    Generator g = eq[i];
    int Ord = abs(ord(g))-1;
    ++occurrences[Ord];
  }

  for(int i = 0; i<numOfVar; i++)
    if( occurrences[i] != 2 && occurrences[i] != 0) {
      delete occurrences;
      return "Equation is not quadratic.";
    }

  delete occurrences;
  return Chars();
}


//template class QueueOf<VertexInfo>;

Generated by  Doxygen 1.6.0   Back to index