gradedalgebras.H

#ifndef _GRADEDALGEBRAS_H_
#define _GRADEDALGEBRAS_H_


#include "algebras.H"
#include <set>
using namespace std;


template <class K>
class GradedAlgebra : public AffineAlgebra<K> {
public:

  map<long, long> hom_degrees;

  // first we need to do the usual work of rewriting the**************************
  // methods related to the variables ********************************************

  Polynomial<K> new_variable(const string& name, long degree){
    Polynomial<K> ans;    

    ans= AffineAlgebra<K>::new_variable(name);
    hom_degrees[this->var_in_use]= degree;

    return ans;
  }
 
  virtual void swap_variables_order(long i, long j,list< Polynomial<K> >& polys){
    long dummy;

    AffineAlgebra<K>::swap_variables_order(i,j,polys);
    dummy= hom_degrees[i];
    hom_degrees[i]= hom_degrees[j];
    hom_degrees[j]= dummy;
  }

  // code below is the same as for affinealgebra !!
  // however, since we redefine a method with the
  // same name (but different arguments), the
  // compiler would be confused if we did not rewrite
  // this one as well.
  virtual void swap_variables_order(long i, long j){
    list< Polynomial<K> > empty_list;
    
    this->swap_variables_order(i,j,empty_list);
  }


  virtual void kill_top_variable(const Polynomial<K>& replacement,list< Polynomial<K> >& polys){
    AffineAlgebra<K>::kill_top_variable(replacement,polys);
    hom_degrees.erase(this->var_in_use + 1);
  }


  virtual void kill_top_variable(const Polynomial<K>& replacement){
    list< Polynomial<K> > empty_list;

    this->kill_top_variable(replacement,empty_list);
  }

  // more interesting things related to the grading ********************
  // *******************************************************************


  long hom_degree_of(const Polynomial<K>& x) const {
    PowProd pow= x.lp();
    long ans=0;


    for(long i= 1; i <= pow.nvars(); i++){
      ans+= pow.power_of(i)*hom_degrees.find(i)->second;
    }
    return ans;

  }
  
  bool is_homogeneous(const Polynomial<K> x) const {
    typename map<PowProd, K>::const_iterator it;
    long deg;
    
    it= x.coeffs.begin();
    if( it == x.coeffs.end() ) // zero poly?
      return true;
    deg= hom_degree_of(it->first);
    
    for(it++; it!= x.coeffs.end(); it++){
      if( deg != hom_degree_of(it->first) )
        return false;
    }
    
    return true;
    
  }
  
  Polynomial<K> hom_part_of(const Polynomial<K>& x, long n) const {
    Polynomial<K> ans;
    typename map<PowProd, K>::const_iterator it;

    for(it= x.coeffs.begin(); it != x.coeffs.end(); it++){
      if( hom_degree_of(it->first) == n )
        ans.add_term(it->first, it->second);
    }

    ans.alphabet= (Alphabet*) this;
    return ans;
  }

  void add_relation(const Polynomial<K>& rel) {
    typename map<PowProd, K>::const_iterator it;
    Polynomial<K> add;
    Polynomial<K> buf= rel;
    long deg;

    it= buf.coeffs.begin();
    while( it != buf.coeffs.end() ) {
      deg= hom_degree_of(it->first);
      add= hom_part_of(buf, deg);
      this->relations.generators.push_back(add);
      buf+= add*(-1);
      it= buf.coeffs.begin();
    }

  }


  void split_and_sort_relations(){
    long i;
    Polynomial<K> P;
    typename list< Polynomial<K> >::iterator total_it;
    list< Polynomial<K> > total_relations;
    
    if(this->verbose)
      cout << endl 
           << "{\\bf Now splitting into homogeneous parts}" 
           << endl << endl;


    i= 0;
    total_relations.splice(total_relations.begin(), this->relations.generators);

    while( !total_relations.empty() ){
      i++;

      if(this->very_verbose)
        cout << "adding the relations in degree " << i 
             << endl << endl;

      for(total_it= total_relations.begin();
          total_it != total_relations.end();){
        P= hom_part_of(*total_it, i);
        if( !P.is_zero() ){
          if( this->very_verbose)
            cout << "adding $" << P << " = 0$" 
                 << endl << endl;
          this->relations.generators.push_back(P);
          *total_it += P*(-1);
        }
        if( total_it->is_zero() )
          total_it= total_relations.erase(total_it);
        else
          total_it++;
      }
    }// end of WHILE

  }

  //returns info on the algebra *********************************
  //*************************************************************

  void even_subalgebra(GradedAlgebra<K>& ans,
                       AffineHomomorphism<K>& inclusion) const {
    GradedAlgebra<K> empty;
    Tuple< Polynomial<K> > gens;
    list< Polynomial<K> > odds;
    typename list< Polynomial<K> >::iterator it, itp;
    long i;
    ostringstream autoname;

    //setup
    ans= empty;
    inclusion.clear();
    inclusion.source= &ans;
    inclusion.target= this;

    //sorts even and odd generators
    gens= this->get_variables();
    for(i= 1; i< gens.size(); i++)
      if( hom_degree_of( gens[i] ) % 2 == 0 ) { 
        ans.new_variable( this->nameof(i),
                          hom_degree_of( gens[i] ) );
        inclusion.set_image(ans.variables_in_use(), gens[i]);
      }
      else
        odds.push_back( gens[i] );
    //add the squares

    for(it= odds.begin(); it!= odds.end(); it++) {
      autoname.str("");
      autoname << "S" << *it;
      ans.new_variable( autoname.str(), 
                        2*hom_degree_of(*it) );
      inclusion.set_image( ans.variables_in_use(),
                           (*it) * (*it) );
    }

    //add the twofold products
    i= 0;
    for(it= odds.begin(); it!= odds.end(); it++)
      for(itp= it, itp++; itp != odds.end(); itp++) {
        i++;
        autoname.str("");
        autoname << "p_" << i;
        ans.new_variable(autoname.str(), 
                         hom_degree_of(*it)+hom_degree_of(*itp) );
        inclusion.set_image( ans.variables_in_use(),
                             (*it) * (*itp) );
      }

  }


  long top_degree() const {
    typename list< Polynomial<K> >::const_iterator it;
    PowProd pow;
    long i, n;
    Tuple<long> nilp;
    Tuple< Polynomial<K> > vars= this->get_variables();
    Polynomial<K> P;

    nilp.resize(this->var_in_use + 1);

    for(i=1; i<= this->var_in_use; i++){
      P= vars[i];
      n= 0;
      //finds n such that P**(n+1) = 0
      while( !this->reduced_form(P).is_zero() ){
        P*= vars[i];
        n++;
      }
      nilp[i]= n;
    }//for i among variables
    
    //now the result is sum_i degree(variable i)*nilp(i)
    long ans=0;
    for(i= 1; i<= this->var_in_use; i++)
      ans+= nilp[i] * hom_degrees.find(i)->second;

    return ans;
  }


  void list_monomials(long degree, Tuple< Polynomial<K> >& result) const {
    long d;
    long i, j;
    Tuple< Polynomial<K> > temp;
    set< PowProd > ans;
    // note: ans is a set of powprods rather than
    // polynomials, because there is an order on 
    // powprods, and this is required for set<>.
    // The container set<> is very convenient right
    // here, even if there are some annoying conversions
    // between polynomials and powprods below (we certainly
    // want the final answer given with polynomials !)
    Polynomial<K> P, P_red;
    static map< long, Tuple< Polynomial<K> > > already_computed;

    // if degree is absurd
    if(degree < 0){
      result.resize(0);
      return;
    }
    //in degree 0, there is only 1
    if(degree == 0){
      result.resize(1);
      result[0]= this->one();
      return;
    }
    //else, have we computed this already ?
    if(already_computed.count(degree) > 0){
      result= already_computed[degree];
      return;
    }
    //else... need some work !
    ans.clear();

    for(i=1; i<= this->var_in_use; i++){
      d= degree - hom_degrees.find(i)->second;
      if(already_computed.count(d) > 0)
        temp= already_computed[d];
      else{
        list_monomials(d, temp);
        already_computed[d]= temp;
      }
      for(j=0; j< temp.size(); j++){
        P= temp[j]*Polynomial<K>( PowProd(i) );
        P_red= this->reduced_form(P);
        if( !P_red.is_zero() )
          ans.insert(P.lp());
        
      }//end inside for
    }//endfor

    result.resize( ans.size() );
    typename set< PowProd >::iterator it;
    
    for(it= ans.begin(), i=0;
        it!= ans.end();
        it++, i++){
      result[i]= Polynomial<K>(*it);
      result[i].alphabet= (Alphabet *) this;
    }
  }// done !


  // friend which prints *******************************
  // ***************************************************


  friend ostream& operator<<(ostream& os, const GradedAlgebra<K>& R){
    typename map<long, string>::const_iterator it_gen;
    typename map<long, long>::const_iterator it_deg;
    typename list< Polynomial<K> >::const_iterator it_rel;

    os << "generators:" << endl << endl;
    for(it_gen= R.names.begin(), it_deg= R.hom_degrees.begin(); 
        it_gen!= R.names.end(); 
        it_gen++, it_deg++)
      os << it_gen->second
         << " of degree "
         << it_deg->second << endl << endl;
    
    os << endl << "relations:" << endl << endl;
    for(it_rel=R.relations.generators.begin(); 
        it_rel!= R.relations.generators.end(); it_rel++)
      os << *it_rel << endl << endl;

    return os;
  }
  friend ofstream& operator<<(ofstream& file, GradedAlgebra<K>& A){

    // write the underlying affine algebra
    AffineAlgebra<K> *ptr;
    ptr= &A;
    file << *ptr;
    // write the degrees
    for(long i=1; i <= A.var_in_use; i++)
      file << A.hom_degrees[i] << " ";

    return file;
  }

  friend void operator>>(ifstream& file, GradedAlgebra<K>& A){

    //read the underlying affine algebra
    AffineAlgebra<K> *ptr;
    ptr= &A;
    file >> *ptr;
    //read the degrees
    long deg;
    for(long i=1; i<= A.var_in_use; i++){
      file >> deg;
      A.hom_degrees[i]=deg;
    }
  }


};



#endif

---