unstable.cpp

#include "unstable.H"
using namespace std;


void UnstableAlgebra::swap_variables_order(long i, 
                                           long j, 
                                           list< Polynomial<F_2> >& polys){
  Tuple< Polynomial<F_2> > dummy;
  long a, b;

  GradedAlgebra<F_2>::swap_variables_order(i, j, polys);
  dummy.steal(steenrod[i]);
  steenrod[i].steal( steenrod[j] );
  steenrod[j].steal( dummy );

  for(a=1; a<= var_in_use; a++)
    for(b=0; b<= hom_degrees[a]; b++)
      steenrod[a][b].swap_variables(i, j);
}


void UnstableAlgebra::swap_variables_order(long i, long j){
  list< Polynomial<F_2> > empty_list;
  
  this->swap_variables_order(i,j,empty_list);
}

void UnstableAlgebra::kill_top_variable(const Polynomial<F_2>& replacement,
                                        list< Polynomial<F_2> >& polys){
  long a,b;

  GradedAlgebra<F_2>::kill_top_variable(replacement, polys);
  steenrod.erase(this->var_in_use + 1);

  for(a=1; a<= this->var_in_use; a++)
    //we check if the steenrod operations are
    //defined at all for variable a...
    if(steenrod[a].size() == hom_degrees[a] + 1)
      for(b=0; b<= hom_degrees[a]; b++)
        steenrod[a][b].substitute_variable(var_in_use + 1, replacement);

}


void UnstableAlgebra::kill_top_variable(const Polynomial<F_2>& replacement){
  list< Polynomial<F_2> > empty_list;
  
  this->kill_top_variable(replacement,empty_list);
}


void UnstableAlgebra::fix_alphabets() {

  GradedAlgebra<F_2>::fix_alphabets();

  long a, b;
  for(a=1; a<= var_in_use; a++)
    for(b=0; b<= hom_degrees[a]; b++)
      steenrod[a][b].alphabet= this;
}


//new stuff /////////////////////////////////////////////////////////
void UnstableAlgebra::write_trivial_steenrod_operations(){
  long i, n;
  Tuple< Polynomial<F_2> > vars= get_variables();

  for(i=1; i<=this->var_in_use; i++){
    n= hom_degrees[i];
    steenrod[i].resize( n + 1 );
    steenrod[i][0]= vars[i]; // Sq^0(x) = x
    steenrod[i][n]= vars[i] * vars[i]; //Sq^|x|(x) = x^2
  }// for i
}


Polynomial<F_2> UnstableAlgebra::Sq(long i, 
                                    const Polynomial<F_2>& x) const {

  if(i==0)
    return x;

  long n= hom_degree_of(x);
  Polynomial<F_2> ans= x;


  if(i < 0 || i > n || ans.is_zero() ){
    ans.sets_to_zero();
    return ans;
  }
  //else...
  Polynomial<F_2> P= ans.lt();
  ans+= P;
  if( !ans.is_zero() ) // x not a power product ?
    return Sq(i, ans) + Sq(i, P);
  //else, P==x is a power product
  PowProd pow= P.lp(); // same as P but viewed as a powprod
  long s= pow.nvars();
  if(s==0){ // x== 1 ?
    ans.sets_to_zero();//since i > 0
    return ans;
  }
  //else ! -- use Cartan's formula
  P= Polynomial<F_2>( pow/PowProd(s) ); //so x=P * variable s
  P.alphabet= (Alphabet *) this;
  long k, min, deg;
  deg= hom_degrees.find(s)->second; //deg= degree of variable s
  min= deg > i ? i : deg;
  ans.sets_to_zero();

  for(k=0; k<= min; k++)
    ans+= (steenrod.find(s)->second[k]) * Sq(i-k, P);
  
  return ans;
}

Polynomial<F_2> UnstableAlgebra::Q(long i, 
                                   const Polynomial<F_2>& x) const {
  long n, j;

  if( i < 0 )
    return x;
  if( i == 0 )
    return Sq(1, x);
  //set n= 2^i
  n= 1;
  for(j= 0; j< i; j++)
    n*= 2;
  return Sq(n, Q(i-1, x)) + Q(i-1, Sq(n, x));
}


    
// insert the polynomial in the list 'pretty_relations' in
// the first position that keeps this list sorted with the
// degrees nondecreasing. Insert the comment correspondingly
void UnstableAlgebra::insert(const Polynomial<F_2>& P, 
                             const string& com, 
                             list< Polynomial<F_2> >& thelist){
  list< Polynomial<F_2> >::iterator locit; //loc= local
  list< string >::iterator locitcom;//ditto

  for(locit= thelist.begin(), locitcom= comments.begin();
      locit!= thelist.end();
      locit++, locitcom++)
    if( hom_degree_of( *locit) >= hom_degree_of(P) )
      break;
  //now locit and locitcom point at the right position
  thelist.insert(locit, P);
  comments.insert(locitcom, com);
}



AbstractHomomorphism<F_2> UnstableAlgebra::saturate_and_reduce(){
  bool grobner_done;
  long nb_relations, current_relation, var;
  Polynomial<F_2> rel, P;
  list< Polynomial<F_2> > pretty_relations;
  list< Polynomial<F_2> >::iterator it;
  list< string >::iterator itcom;
  AbstractHomomorphism<F_2> ans, temphom;
  ostringstream autoname;
  long k;


  if(verbose)
    cout << "{\\bf Now saturating & reducing variables and relations}"
         << endl << endl;

  grobner_done= false;
  ans.make_identity(this->var_in_use);
  nb_relations= 0;
  current_relation= 1;
  //copy the relations in pretty_relations
  //fill 'comments' with empty strings
  pretty_relations.splice(pretty_relations.begin(), relations.generators );
  comments.clear();
  for(it= pretty_relations.begin(); it!= pretty_relations.end(); it++)
    comments.push_back("");

  //now browse through pretty_relations

  for(it= pretty_relations.begin(), itcom= comments.begin(); 
      it!= pretty_relations.end();){
      
    if( (var= it->has_lonely_variable(rel)) > 0 ){
      if(very_verbose)
        cout << "relation " << current_relation
             << " yields a variable redundancy: $"
             << this->nameof(var) << " = " << rel 
             << "$" << endl << endl;
      it= pretty_relations.erase(it);
      itcom= comments.erase(itcom);
      kill_variable(var, rel, pretty_relations);
      grobner_done= false;
      // now write the corresponding homomorphism
      rel.swap_variables(var, this->var_in_use + 1); // rel itself must be updated !!
      temphom.make_identity(this->var_in_use + 1);
      temphom.set_image(this->var_in_use + 1, Polynomial<F_2>( PowProd(var) ) );
      temphom.set_image(var, rel);
      ans= temphom * ans;
    }
    else{
        
      if( !grobner_done ){
        find_grobner_basis();
        grobner_done= true;
      }
      rel= reduced_form( *it );
      if( !rel.is_zero() ){//not redundant ?
        nb_relations++;
        if(very_verbose)
          cout << "adding relation " << current_relation
               << " (total " << nb_relations << " relations added): "
               << "$" << rel << "$" << endl << endl;
        add_relation(rel);
        grobner_done= false;

        //now let's find a name for this relation, if needed
        if( *itcom == "" ){//not named yet ?
          autoname.str("");
          autoname << "(" << nb_relations << ")";
          *itcom= autoname.str();
        }
        //now deal with the steenrod operations
        for(k=1; k < hom_degree_of( *it ); k++){
          P= Sq(k, *it);
          if( !P.is_zero() ){
            autoname.str("");
            autoname << "Sq^" << k << *itcom;
            insert( P, autoname.str(), pretty_relations );
          }
        }//done with steenrod!
        it++;
        itcom++;
      }
      else{//redundant !
        if(very_verbose)
          cout << "relation " << current_relation << " redundant"
               << endl << endl;
        it= pretty_relations.erase(it);
        itcom= comments.erase(itcom);
      }
    }
    current_relation++;
  }
  //cut_down_variables();
  if(verbose)
    cout << "{\\bf Final presentation: } " 
         << var_in_use << " variables kept, " 
         << nb_relations << " relations kept" 
         << endl << endl;
  //copy pretty_relations into relations.generators
  relations.generators.clear();
  relations.generators.splice( relations.generators.begin(), pretty_relations);
  return ans;
}

void UnstableAlgebra::display() const {
  list< Polynomial<F_2> >::const_iterator it;
  list< string >::const_iterator itcom;
  map<long, string>::const_iterator it_gen;
  map<long, long>::const_iterator it_deg;


  cout << "generators:" << endl << endl;
  for(it_gen= names.begin(), it_deg= hom_degrees.begin(); 
      it_gen!= names.end(); 
      it_gen++, it_deg++)
    cout << "$" << it_gen->second << "$"
         << " of degree "
         << it_deg->second << endl << endl;
  

  cout << endl << "relations:" << endl;

  for(it= relations.generators.begin(), itcom= comments.begin(); 
      it!= relations.generators.end(); it++, itcom++){
    cout << *itcom << " :    " << *it << endl << endl;
  }

  //steenrod operations
  long i, j;

  cout << "Steenrod operations:" << endl << endl;
  for(i=1; i<= var_in_use; i++)
    for(j=1; j< steenrod.find(i)->second.size()-1; j++)
      cout << "$Sq^" << j << "(" << nameof(i) << ") = "
         << steenrod.find(i)->second[j] << "$" << endl << endl;



}



bool UnstableAlgebra::is_saturated() const {
  list< Polynomial<F_2> >::const_iterator it;
  long k;

  for(it= relations.generators.begin();
      it!= relations.generators.end();
      it++)
    for(k=1; k < hom_degree_of( *it ); k++)
      if(!reduced_form( Sq(k, *it) ).is_zero() )
        return false;

  return true;

}


bool UnstableAlgebra::has_closure_of(const AffineHomomorphism<F_2>& f) const {
  long i, k;
  Polynomial<F_2> P;

  for(i=1; i<= f.source->variables_in_use(); i++) {
    P= f.of_generator(i);
    for(k=1; k < this->hom_degree_of(P); k++)
      if( !f.maps_onto( Sq(k, P) ) ) {
        cout << "no! one has Sq^" << k
             << "(" << P << ") = " 
             << Sq(k, P) << " which is not in the image"
             << endl;
        return false;
      }
  }
  return true;
}




// friend printing /////////////////////////////////////////////////

ostream& operator<<(ostream& os, const UnstableAlgebra& A){
  const GradedAlgebra<F_2> *ptr;

  ptr= &A;
  os << *ptr;

  long i, j;

  os << "Steenrod operations:" << endl << endl;
  for(i=1; i<= A.variables_in_use(); i++)
    for(j=1; j< A.steenrod.find(i)->second.size()-1; j++)
      os << "Sq^" << j << "(" << A.nameof(i) << ") = "
         << A.steenrod.find(i)->second[j] << endl << endl;

  return os;
}

ofstream& operator<<(ofstream& file, UnstableAlgebra& A){
  GradedAlgebra<F_2> *ptr;

  ptr= &A;
  file << *ptr;

  //now write the steenrod operations
  long i, j;

  for(i=1; i<= A.variables_in_use(); i++)
    for(j=1; j< A.steenrod.find(i)->second.size()-1; j++)
      file << A.steenrod[i][j];


  //and now the comments
  list< string >::iterator it;
  i= 0;
  for(it= A.comments.begin(); it!= A.comments.end(); it++)
    i++;
  file << i << " ";
  for(it= A.comments.begin(); it!= A.comments.end(); it++)
    file << *it << " ";

  return file;
}

void operator>>(ifstream& file, UnstableAlgebra& A){
  GradedAlgebra<F_2> *ptr;
  
  ptr= &A;
  file >> *ptr;

  //now steenrod
  A.write_trivial_steenrod_operations();

  long i, j;

  for(i=1; i<= A.variables_in_use(); i++)
    for(j=1; j< A.steenrod.find(i)->second.size()-1; j++)
      file >> A.steenrod[i][j];

  A.fix_alphabets();

  //now comments
  string foo;
  A.comments.clear();
  file >> i;
  while( i>0 ){
    file >> foo;
    A.comments.push_back( foo );
    i--;
  }

}

---