weyl.h

Go to the documentation of this file.

/*
  This is weyl.h

  Copyright (C) 2004,2005 Fokko du Cloux
  part of the Atlas of Lie Groups and Representations

  For license information see the LICENSE file
*/

#ifndef WEYL_H  /* guard against multiple inclusions */
#define WEYL_H

#include "../Atlas.h"

#include <cstring>
#include <cassert>

#include "constants.h"
#include "tags.h"

#include "size.h"   // for stored order of the Weyl group
#include "matrix.h" // for Coxeter matrix


/******** type declarations *************************************************/

namespace atlas {

namespace weyl {

  class RowBase; // information at one coset element in one transducer table
  typedef RowBase ShiftRow; // the case of a transition entry
  typedef RowBase OutRow;   // the case of a transduction entry

  class Transducer;


/******** constant declarations *********************************************/

  const unsigned char UndefValue = constants::ucharMax;
  const unsigned long UndefOrder = 0; // is never a valid value


/******** type definitions **************************************************/

  class Twist // also used by synonym |WeylInterface|
  {
    Generator d[constants::RANK_MAX];
  public:
    Twist () // assures definite values are always set
      { std::memset(d,~0,sizeof(d)); }
    Generator& operator[] (size_t i) { return d[i]; }
    const Generator& operator[] (size_t i) const { return d[i]; }

    bool operator!=(const Twist& y) const
    { for (unsigned i=0; i<constants::RANK_MAX; ++i)
    if (d[i]!=y.d[i])
      return true;
      return false;
    }
    bool operator==(const Twist& y) const { return not operator!=(y); }

  };


/******** function declaration *********************************************/

Twist make_twist(const RootDatum& rd,
         const WeightInvolution& d);

/******** main class definitions *******************************************/

class WeylElt // a.k.a. |TwistedInvolution|
{

  friend class WeylGroup; // so we can shield implementation from all others

public:
  typedef unsigned char EltPiece;

 private:

  EltPiece d_data[constants::RANK_MAX];

 public:

// constructors and destructors

  WeylElt() {
    std::memset(d_data,0,sizeof(d_data));
  }

  WeylElt(const WeylWord& w, const WeylGroup& W);

// copy and assignment
// use standard definitions (raw copy of array)

// accessors


  bool operator< (const WeylElt& w) const {
    return std::memcmp(d_data,w.d_data,sizeof(d_data)) < 0;
  }

  bool operator== (const WeylElt& w) const {
    return std::memcmp(d_data,w.d_data,sizeof(d_data))==0;
  }

  bool operator!= (const WeylElt& w) const {
    return std::memcmp(d_data,w.d_data,sizeof(d_data))!=0;
  }

protected: // these are for |WeylGroup| and |TI_Entry|'s eyes only

  EltPiece operator[] (size_t j) const {
    return d_data[j];
  }

// manipulators
  EltPiece& operator[] (size_t j) {
    return d_data[j];
  }

public:
// dummy methods that mark transition of interpretation

  // from WeylElt interpretation to TwistedInvolution
  // nothing: cast to TwistedInvolution is allowed, would do construction if
  // TwistedInvolution were a derived class, and is a no-op in reality

  // from TwistedInvolution interpretation to WeylElt
  // calls of these mark referral to the "base" class of |TwistedInvolution|
  const WeylElt& w() const { return *this; }
  WeylElt& contents() { return *this; }

}; // |class WeylElt|

const WeylElt Identity; // default constructor initialises to identity

class RowBase {

 private:

  unsigned char d_data[constants::RANK_MAX];

 public:

// constructors and destructors
  RowBase() {
    std::memset(d_data,UndefValue,sizeof(d_data));
  }

  ~RowBase() {}

// copy and assignment
  RowBase(const RowBase& r) {
    std::memcpy(d_data,r.d_data,sizeof(d_data));
  }

  RowBase& operator=(const RowBase& r) {
    std::memcpy(d_data,r.d_data,sizeof(d_data)); return *this;
  }

// accessors
  Generator operator[] (size_t j) const {
    return d_data[j];
  }

// manipulators
  Generator& operator[] (size_t j) {
    return d_data[j];
  }
}; // |class RowBase|

class Transducer {
  // there is one such object for each $r\in\{1,2,\ldots,n\}$
  // but $r$ is not explicitly stored in the Tranducer object

  std::vector<ShiftRow> d_shift;

  std::vector<OutRow> d_out;

  std::vector<unsigned long> d_length;

  std::vector<WeylWord> d_piece;

 public:

// constructors and destructors
  Transducer() {}

  Transducer(const int_Matrix&, size_t);

  ~Transducer() {}

// accessors


  unsigned long length(WeylElt::EltPiece x) const { return d_length[x]; }


  unsigned long maxlength() const { return d_length.back(); }


  Generator out(WeylElt::EltPiece x, Generator s) const { return d_out[x][s]; }

  WeylElt::EltPiece shift(WeylElt::EltPiece x, Generator s) const
   { return d_shift[x][s]; }

  unsigned long size() const {
    return d_shift.size();
  }


  const WeylWord& wordPiece(WeylElt::EltPiece x) const { return d_piece[x]; }

// this class should have no manipulators!
}; // |class Transducer|


class WeylGroup
{
  size_t d_rank;
  size::Size d_order;
  unsigned long d_maxlength;
  WeylElt d_longest;
  int_Matrix d_coxeterMatrix;
  Twist Chevalley;

  std::vector<Transducer> d_transducer;
  WeylInterface d_in;
  WeylInterface d_out;
  std::vector<Generator> d_min_star;

  WeylGroup(const WeylGroup&); // forbid copying; Weyl groups should be shared

// private member functions
// these interpret Generators and WeylWords internally, so not for public use!

  // set |w=ws|, return value is $l(ws)-l(w)\in\{+1,-1}$
  int multIn(WeylElt& w, Generator s) const;

  // set |w=wv|, return value is $l(wv)-l(w)-l(v)\in -2\N$
  int multIn(WeylElt& w, const WeylWord& v) const;

  // set |w=sw|, return value is $l(sw)-l(w)\in\{+1,-1}$
  int leftMultIn(WeylElt& w, Generator s) const;

  // get WeylWord for piece |j| of |w|
  const WeylWord& wordPiece(const WeylElt& w, Generator j) const
    { return d_transducer[j].wordPiece(w[j]); }

  Generator min_neighbor (Generator s) const { return d_min_star[s]; }

  WeylElt genIn (Generator i) const; // $s_i$ as Weyl group element

// From this point on each Generator or WeylWord uses external numbering
public:

// constructors and destructors
  WeylGroup(const int_Matrix& cartan); // from Cartan matrix

// accessors

  WeylElt generator (Generator i) const // $s_i$ as Weyl group element
    { return genIn(d_in[i]); }

  // set |w=ws|, return length change
  int mult(WeylElt& w, Generator s) const { return multIn(w,d_in[s]); }

  // set |w=wv|
  void mult(WeylElt& w, const WeylElt& v) const;

  // set |w=wv|
  void mult(WeylElt&, const WeylWord&) const;

  // set |w=sw| (argument order motivated by modification effect on |w|)
  int leftMult(WeylElt& w, Generator s) const { return leftMultIn(w,d_in[s]); }
  void leftMult(WeylElt& w, const WeylWord& ww) const
  {
    for (size_t i=ww.size(); i-->0; ) // use letters from right to left
      leftMult(w,ww[i]);
  }
  void leftMult(WeylElt& w, const WeylElt& x) const; // |w=xw|

  WeylElt prod(const WeylElt& w, Generator s) const
    { WeylElt result=w; mult(result,s); return result; }
  WeylElt prod(Generator s, const WeylElt& w) const
    { WeylElt result=w; leftMult(result,s); return result; }
  WeylElt prod(const WeylElt& w, const WeylElt& v) const
    { WeylElt result=w; mult(result,v); return result; }
  WeylElt prod(const WeylElt& w, const WeylWord& ww) const
    { WeylElt result=w; mult(result,ww); return result; }
  WeylElt prod(const WeylWord& ww,const WeylElt& w) const
    { WeylElt result=w; leftMult(result,ww); return result; }


  /* These additional definitions would be needed if TwistedInvolutions were a
     type distinct from WeylElt (but they are not allowed as it is):

  void leftMult(TwistedInvolution& w, Generator s) const {
    leftMultIn(w.contents(),d_in[s]);
  }
  void leftMult(TwistedInvolution& w, const WeylWord& ww) const {
    leftMult(w.contents(),ww);
  }
  void leftMult(TwistedInvolution& w, const WeylElt& x) const {
    leftMult(w.contents(),x);
  }
  */


  unsigned int length(const WeylElt&) const;

  // return (only) $l(w.s)-l(w)$
  int length_change(WeylElt w, Generator s) const
  {
    return multIn(w,d_in[s]); // discard copied |w|
  }

  // return $l(s.w)-l(w)$
  int length_change(Generator s,const WeylElt& w) const
  {
    return hasDescent(s,w) ? -1 : 1;
  }

  // letter |i| of Weyl word for |w|
  Generator letter(const WeylElt& w, unsigned int i) const;

  void conjugacyClass(WeylEltList&, const WeylElt&) const;

  void conjugate(WeylElt& w, Generator s) const
    { leftMult(w,s); mult(w,s); }

  WeylElt inverse(const WeylElt& w) const;

  void invert(WeylElt& w) const { w=inverse(w); }

  Generator leftDescent(const WeylElt& w) const;

  bool commutes (Generator s, Generator t) const
  {
    WeylElt w = generator(s);
    conjugate(w,t);
    return w==generator(s);
  }

  const WeylElt& longest() const { return d_longest; }

  Generator Chevalley_dual(Generator s) const // conjugation by |longest()|
  { assert(s<rank()); return Chevalley[s]; }

  // correspondence with dual Weyl group; is coherent with \delta on the right!
  WeylElt opposite (const WeylElt& w) const { return prod(w,d_longest); }

  unsigned long maxlength() const { return d_maxlength; }

  const size::Size& order() const { return d_order; }

  size_t rank() const { return d_rank; }

  WeylWord word(const WeylElt& w) const;
  WeylElt element(const WeylWord& ww) const { return prod(WeylElt(),ww); }

  WeylEltList reflections() const; // list all reflections

  /* give representation of |w| as integral number, supposing this fits. */
  unsigned long toUlong(const WeylElt& w) const;

  /* inverse operation of |toUlong| */
  WeylElt toWeylElt(unsigned long) const;

  bool hasDescent(Generator, const WeylElt&) const; // on the left
  bool hasDescent(const WeylElt&, Generator) const; // on the right

  // apply automorphism of $(W,S)$ given by |f| in terms of outer numbering
  WeylElt translation(const WeylElt& w, const WeylInterface& f) const;

  void translate(WeylElt& w, const WeylInterface& i) const
    { w=translation(w,i); }

  // reflection action of Weyl group on a root
  void act(const RootDatum& rd, const WeylElt& w, RootNbr& alpha) const;
  // standard reflection action of Weyl group using a root datum
  template<typename C>
    void act(const RootDatum& rd, const WeylElt& w, matrix::Vector<C>& v)
    const;
  // standard reflection action of Weyl group using a root datum
  void act(const RootDatum& rd, const WeylElt& w, RatWeight& v) const;
  // standard reflection action of Weyl group using a root datum
  void act(const RootDatum& rd, const WeylElt& w, LatticeMatrix& M) const;

  // same using only lists of simple (co)roots avoiding construction root datum
  template<typename C>
    void act(const PreRootDatum& prd, const WeylElt& w, matrix::Vector<C>& v)
    const;
  void act(const PreRootDatum& prd, const WeylElt& w, RatWeight& v) const;
  void act(const PreRootDatum& prd, const WeylElt& w, LatticeMatrix& M) const;
  Weight
    image_by(const RootDatum& rd, const WeylElt& w, Weight v) const
    { act(rd,w,v); return v; }

  void inverse_act(const RootDatum& rd, const WeylElt& w, Weight& v) const;

  Weight
    image_by_inverse(const RootDatum& rd, const WeylElt& w, Weight v) const
    { inverse_act(rd,w,v); return v; }


// manipulators

}; // |class WeylGroup|

/*
  We have split off in the following class functionality that involves an
  involutive diagram automorphism |delta|. While WeylElt values are assumed to
  live just in the Weyl group W, this class implements operations that
  are more naturally interprests them in $W semidirect Z/2Z$ (the second
  factor acting on the first via |delta|), namely in the non-identity coset
  for $W$.

  This class is not derived from |WeylGroup|, although many methods are just
  handed over to an underlying |WeylGroup|. We assume the latter to be
  constructed beforehand, and store a reference to it. For one thing, this
  makes it possible for two |TwistedWeylGroup|s with different twists to share
  the same |WeylGroup|; this is useful because the Weyl groups of a root datum
  and its dual can be identified, but not their twists.

  Having no privilege with respect to |WeylGroup|, we are totally ignorant of
  its internal numbering.
*/
class TwistedWeylGroup
{
  const WeylGroup& W;  // non-owned reference
  const Twist d_twist; // cannot be reference, if dual is to be constructible

  void operator=(const TwistedWeylGroup&); // forbid assignment
 protected:
 TwistedWeylGroup(const TwistedWeylGroup& g) // only derived classes may copy
   : W(g.W), d_twist(g.d_twist) {} // share |W|, copy |d_twist|
public:
  TwistedWeylGroup(const WeylGroup&, const Twist&);

  // construct the "dual" twisted Weyl group: differs by a dual twist
  TwistedWeylGroup(const TwistedWeylGroup&, tags::DualTag);

  const WeylGroup& weylGroup() const { return W; }
  size_t rank() const { return W.rank(); }

  int mult(WeylElt& w, Generator s) const { return W.mult(w,s); }
  void mult(WeylElt& w, const WeylElt& v) const { W.mult(w,v); }
  void mult(WeylElt& w, const WeylWord& ww) const { W.mult(w,ww); }

  int leftMult(WeylElt& w, Generator s) const { return W.leftMult(w,s); }
  void leftMult(WeylElt& w, const WeylWord& ww) const { W.leftMult(w,ww); }
  WeylWord word(const WeylElt& w) const { return W.word(w); }

  WeylElt prod(const WeylElt& w, Generator s) const { return W.prod(w,s); }
  WeylElt prod(Generator s, const WeylElt& w) const { return W.prod(s,w); }
  WeylElt prod(const WeylElt& w, const WeylElt& v) const { return W.prod(w,v); }
  WeylElt prod(const WeylElt& w, const WeylWord& ww) const
   { return W.prod(w,ww); }
  WeylElt prod(const WeylWord& ww,const WeylElt& w) const
   { return W.prod(ww,w); }

  bool hasDescent(Generator s, const WeylElt& w) const
    { return W.hasDescent(s,w); }
  bool hasDescent(const WeylElt& w, Generator s) const
    { return W.hasDescent(w,s); }

  Generator twisted(Generator s) const { return d_twist[s]; }
  WeylElt twisted(const WeylElt& w) const { return W.translation(w,d_twist); }

  Generator dual_twisted(Generator s) const
  { return W.Chevalley_dual(d_twist[s]); }
  WeylElt dual_twisted(const WeylElt& w) const;

  const Twist& twist() const { return d_twist; } // noun "twist"
  void twist(WeylElt& w) const { w=twisted(w); } // verb "twist"

  std::vector<ext_gen> twist_orbits () const;
  Twist dual_twist() const; // the twist for the dual twisted Weyl group

  int twistedConjugate(TwistedInvolution& tw, Generator s) const
  {
    WeylElt& w=tw.contents();
    int d = W.leftMult(w,s);
    return d+W.mult(w,d_twist[s]);
  }
  int twistedConjugate(TwistedInvolution& tw, const WeylWord& ww) const
  {
    int d=0;
    for (size_t i=ww.size(); i-->0; )
      d+=twistedConjugate(tw,ww[i]);
    return d;
  }
  int inverseTwistedConjugate(TwistedInvolution& tw, const WeylWord& ww) const
  {
    int d=0;
    for (size_t i=0; i<ww.size(); ++i )
      d+=twistedConjugate(tw,ww[i]);
    return d;
  }

  TwistedInvolution twistedConjugated(TwistedInvolution tw, Generator s) const
    { twistedConjugate(tw,s); return tw; }

  void twistedConjugacyClass(TwistedInvolutionList&, const TwistedInvolution&)
    const;

  void twistedConjugate(TwistedInvolution& tw, const WeylElt& w) const;

  bool hasTwistedCommutation(Generator, const TwistedInvolution&) const;

  unsigned long involutionLength(const TwistedInvolution& tw) const;

   InvolutionWord involution_expr(TwistedInvolution tw) const; // call by value
   InvolutionWord canonical_involution_expr(TwistedInvolution tw) const; // idem

   // extended involution expression for a twist-fixed twisted involution
   InvolutionWord extended_involution_expr(TwistedInvolution tw) const; // idem

  RootNbrList simple_images
    (const RootSystem& rs, const TwistedInvolution& tw) const;

  WeightInvolution
    involution_matrix(const RootSystem& rs,
              const TwistedInvolution& tw) const;

}; // |class TwistedWeylGroup|


// A small derived class to allow hash tables of TwistedInvolution values
// (We might have put |Pooltype| and |hashCode| members in WeylElt directly)

struct TI_Entry
  : public TwistedInvolution
{
  TI_Entry(const TwistedInvolution& tw): TwistedInvolution(tw) {}
  TI_Entry(): TwistedInvolution() {} // identity TwistedInvolution

  // members required for an Entry parameter to the HashTable template
  typedef std::vector<TI_Entry> Pooltype; // associated storage type
  size_t hashCode(size_t modulus) const;  // hash function
}; // class TI_Entry


} // |namespace weyl|

} // |namespace atlas|

#endif