.. _SectGrpCoxOp:

.. _group-op:

Operations on Coxeter Groups
============================

See Chapter :ref:`ChapGrpFP` for general functions for finitely
presented groups, or Chapter :ref:`ChapGrpPerm` for general
functions for permutation groups.

.. magma:function:: IsIsomorphic(W1, W2)
   :input_types: GrpPermCox, GrpPermCox
   :output_types: BoolElt
   :label: IsIsomorphic_GrpPermCox_GrpPermCox

   Returns ``true`` if, and only if, :math:`W_1` and :math:`W_2` are isomorphic as
   abstract groups. This is only implemented for permutation Coxeter groups.

.. magma:function:: IsCoxeterIsomorphic(W1, W2)
   :input_types: GrpFPCox, GrpFPCox
   :output_types: BoolElt
   :label: IsCoxeterIsomorphic_GrpFPCox_GrpFPCox

.. magma:function:: IsCoxeterIsomorphic(W1, W2)
   :input_types: GrpPermCox, GrpPermCox
   :output_types: BoolElt
   :label: IsCoxeterIsomorphic_GrpPermCox_GrpPermCox

   Tests if :math:`W_1` and :math:`W_2` are isomorphic as Coxeter systems. If
   ``true``, a sequence giving the permutation of the generators which takes
   :math:`W_1` to :math:`W_2` is also returned.

.. magma:function:: IsCartanEquivalent(W1, W2)
   :input_types: GrpPermCox, GrpPermCox
   :output_types: BoolElt
   :label: IsCartanEquivalent_GrpPermCox_GrpPermCox

   Returns ``true`` if and only if the crystallographic Coxeter groups :math:`W_1`
   and :math:`W_2` have Cartan equivalent Cartan matrices. This only makes sense
   for permutation Coxeter groups.

.. magma:example:: Example: Coxeter Isomorphism
   :label: CoxeterIsomorphism

   An example of abstractly isomorphic Coxeter groups whose Coxeter systems not
   isomorphic: An example of Coxeter isomorphic groups which are not Cartan
   equivalent:

   .. code-block:: magma

      > W1 := CoxeterGroup(GrpFPCox, "B4");
      > W2 := CoxeterGroup(GrpFPCox, "C4");
      > IsCoxeterIsomorphic(W1, W2);
      true [ 1, 2, 3, 4 ]
      > W1 := CoxeterGroup("G2");
      > W2 := CoxeterGroup("A1A2");
      > IsIsomorphic(W1, W2);
      true
      %%a> assert $1;
      > IsCoxeterIsomorphic(W1, W2);
      false
      %%a> assert not $1;
      > W1 := CoxeterGroup("B3");
      > W2 := CoxeterGroup("C3");
      > IsIsomorphic(W1, W2);
      true
      %%a> assert $1;
      > IsCoxeterIsomorphic(W1, W2);
      true [ 1, 2, 3 ]
      > IsCartanEquivalent(W1, W2);
      false
      %%a> assert not $1;

.. magma:function:: RootSystem(W)
   :input_types: GrpPermCox
   :output_types: RootDtm
   :label: RootSystem_GrpPermCox

   The underlying root system of the permutation Coxeter group :math:`W`.

.. magma:function:: RootDatum(W)
   :input_types: GrpPermCox
   :output_types: RootDtm
   :label: RootDatum_GrpPermCox

   The root datum of the permutation Coxeter group :math:`W`. If :math:`W` does not
   have a root datum, an error is flagged.

.. magma:example:: Example: Group To Root
   :label: GroupToRoot

   .. code-block:: magma

      > W := CoxeterGroup("C5");
      > RootSystem(W);
      Root system of type C5
      > RootDatum(W);
      Root datum of type C5
      > 
      > W := CoxeterGroup("H4");
      > RootSystem(W);
      Root system of type H4
      \< RootDatum(W);
      Error: This group does not have a root datum

.. magma:function:: CartanName(W)
   :input_types: GrpFPCox
   :output_types: List
   :label: CartanName_GrpFPCox

.. magma:function:: CartanName(W)
   :input_types: GrpPermCox
   :output_types: MonStgElt
   :label: CartanName_GrpPermCox

   The Cartan name of the finite or affine Coxeter group :math:`W`
   (Section :ref:`SectCartanFinAff`).

.. magma:function:: CoxeterDiagram(W)
   :input_types: GrpFPCox
   :label: CoxeterDiagram_GrpFPCox

.. magma:function:: CoxeterDiagram(W)
   :input_types: GrpPermCox
   :label: CoxeterDiagram_GrpPermCox

   Print the Coxeter diagram of the finite or affine Coxeter group :math:`W`
   (Section :ref:`SectCartanFinAff`).

.. magma:function:: DynkinDiagram(W)
   :input_types: GrpPermCox
   :label: DynkinDiagram_GrpPermCox

   Print the Dynkin diagram of the permutation Coxeter group :math:`W`. If
   :math:`W` is not crystallographic, an error is flagged.

.. magma:example:: Example: Names Diagrams
   :label: NamesDiagrams

   .. code-block:: magma

      > W := CoxeterGroup("F4");
      > CartanName(W);
      F4
      > DynkinDiagram(W);
 
      F4    1 - 2 =>= 3 - 4
      > CoxeterDiagram(W);
 
      F4    1 - 2 === 3 - 4

.. magma:function:: CoxeterMatrix(W)
   :input_types: GrpFPCox
   :output_types: AlgMatElt
   :label: CoxeterMatrix_GrpFPCox

.. magma:function:: CoxeterMatrix(W)
   :input_types: GrpPermCox
   :output_types: AlgMatElt
   :label: CoxeterMatrix_GrpPermCox

   The Coxeter matrix of the Coxeter group :math:`W`.

.. magma:function:: CoxeterGraph(W)
   :input_types: GrpFPCox
   :output_types: GrphUnd
   :label: CoxeterGraph_GrpFPCox

.. magma:function:: CoxeterGraph(W)
   :input_types: GrpPermCox
   :output_types: GrphUnd
   :label: CoxeterGraph_GrpPermCox

   The Coxeter graph of the Coxeter group :math:`W`.

.. magma:function:: CartanMatrix(W)
   :input_types: GrpPermCox
   :output_types: AlgMatElt
   :label: CartanMatrix_GrpPermCox

   The Cartan matrix of the permutation Coxeter group :math:`W`.

.. magma:function:: DynkinDigraph(W)
   :input_types: GrpPermCox
   :output_types: GrphDir
   :label: DynkinDigraph_GrpPermCox

   The Dynkin digraph of the permutation Coxeter group :math:`W`.

.. magma:function:: Rank(W)
   :input_types: GrpFPCox
   :output_types: RngIntElt
   :label: Rank_GrpFPCox

.. magma:function:: Rank(W)
   :input_types: GrpPermCox
   :output_types: RngIntElt
   :label: Rank_GrpPermCox

.. magma:function:: NumberOfGenerators(W)
   :input_types: GrpFPCox
   :output_types: RngIntElt
   :label: NumberOfGenerators_GrpFPCox

.. magma:function:: NumberOfGenerators(W)
   :input_types: GrpPermCox
   :output_types: RngIntElt
   :label: NumberOfGenerators_GrpPermCox

   The rank of the Coxeter group :math:`W`.

.. magma:function:: NumberOfPositiveRoots(W)
   :input_types: GrpFPCox
   :output_types: RngIntElt
   :label: NumberOfPositiveRoots_GrpFPCox

.. magma:function:: NumberOfPositiveRoots(W)
   :input_types: GrpPermCox
   :output_types: RngIntElt
   :label: NumberOfPositiveRoots_GrpPermCox

.. magma:function:: NumPosRoots(W)
   :input_types: GrpFPCox
   :output_types: RngIntElt
   :label: NumPosRoots_GrpFPCox

.. magma:function:: NumPosRoots(W)
   :input_types: GrpPermCox
   :output_types: RngIntElt
   :label: NumPosRoots_GrpPermCox

   The number of positive roots of the Coxeter group :math:`W`.

.. magma:function:: Dimension(W)
   :input_types: GrpPermCox
   :output_types: RngIntElt
   :label: Dimension_GrpPermCox

   The dimension of the permutation Coxeter group :math:`W`, ie. the dimension of
   the root space.

.. magma:example:: Example: Rank Dimension
   :label: RankDimension

   .. code-block:: magma

      > R := StandardRootSystem("A", 4);
      > W := CoxeterGroup(R);
      > Rank(W);
      4
      %%a> assert $1 eq 4;
      > Dimension(W);
      5
      %%a> assert $1 eq 5;

.. magma:function:: ConjugacyClasses(W)
   :input_types: GrpFPCox
   :output_types: [GrpFPCoxElt]
   :label: ConjugacyClasses_GrpFPCox

.. magma:function:: ConjugacyClasses(W)
   :input_types: GrpPermCox
   :output_types: [GrpPermElt]
   :label: ConjugacyClasses_GrpPermCox

   The conjugacy classes of the finite Coxeter group :math:`W`. This uses the
   algorithm of :cite:`GeckPfeiffer`.

.. magma:function:: FundamentalGroup(W)
   :input_types: GrpPermCox
   :output_types: GrpAb
   :label: FundamentalGroup_GrpPermCox

   The fundamental group of the permutation Coxeter group :math:`W`. The roots and
   coroots of :math:`W` must have integral components.

.. magma:function:: IsogenyGroup(W)
   :input_types: GrpPermCox
   :output_types: GrpAb
   :label: IsogenyGroup_GrpPermCox

   The isogeny group of the permutation Coxeter group :math:`W`. The roots and
   coroots of :math:`W` must have integral components.

.. magma:function:: CoisogenyGroup(W)
   :input_types: GrpPermCox
   :output_types: GrpAb
   :label: CoisogenyGroup_GrpPermCox

   The coisogeny group of the permutation Coxeter group :math:`W`. The roots and
   coroots of :math:`W` must have integral components.

.. magma:function:: BasicDegrees(W)
   :input_types: GrpFPCox
   :output_types: RngIntElt
   :label: BasicDegrees_GrpFPCox

.. magma:function:: BasicDegrees(W)
   :input_types: GrpPermCox
   :output_types: RngIntElt
   :label: BasicDegrees_GrpPermCox

   The degrees of the basic invariant polynomials of the Coxeter group :math:`W`.
   These are computed using the table in
   :raw-latex:`\cite[page 155]{Carter-small}`.

.. magma:function:: BasicCodegrees(W)
   :input_types: GrpFPCox
   :output_types: RngIntElt
   :label: BasicCodegrees_GrpFPCox

.. magma:function:: BasicCodegrees(W)
   :input_types: GrpPermCox
   :output_types: RngIntElt
   :label: BasicCodegrees_GrpPermCox

   The basic codegrees of the Coxeter group :math:`W`. These are computed using the
   algorithm in :cite:`LehrerTaylor`.

.. magma:example:: Example: Basic Degrees
   :label: BasicDegrees

   The product of the basic degrees is the order of the Coxeter group; the sum of
   the basic degrees is the sum of the rank and the number of positive roots.

   .. code-block:: magma

      > W := CoxeterGroup("E6");
      > degs := BasicDegrees(W);
      > degs;
      [ 2, 5, 6, 8, 9, 12 ]
      > &*degs eq #W;
      true
      %%a> assert $1;
      > &+degs eq NumPosRoots(W) + Rank(W);
      true
      %%a> assert $1;

.. magma:function:: \name{bruhatlessorequal}{BruhatLessOrEqual}(x, y)

GrpPermElt, GrpPermElt -> BoolElt

If Coxeter group element :math:`x` is less than or equal to :math:`y` in the
Bruhat order :cite:`Deodhar`. Suppose :math:`x` is an element of the
Coxeter group :math:`W`. The Bruhat order is the partial order generated by the
relations: :math:`x \leq xw` if :math:`l(x) < l(xw)`, and :math:`xw \leq
x` if :math:`l(xw) < l(x)`, for :math:`x\in W` and :math:`w` a reflection. If
:math:`l(xw) =
l(x) + 1`, then :math:`x` is called a *Bruhat descendant* of :math:`xw`. The
algorithm used is a straightforward recursive procedure.

.. magma:function:: \name{bruhatdescendants}{BruhatDescendants}(x)
   :input_types: GrpPermElt
   :output_types: SetEnum
   :parameters: z : GrpPermElt : 

   Let :math:`x` be an element of the Coxeter group :math:`W`, then the returned
   set :math:`S` contains the Bruhat descendants of :math:`x`. If
   :math:`l(yw) = l(y) + 1`, then :math:`y` is called a *Bruhat descendant* of
   :math:`yw`. If the optional parameter :math:`z` is set, only those descendants
   :math:`y` with :math:`z
   \leq y` are returned. Algorithm: For each fundamental reflection in :math:`x` it
   is tested whether leaving it out decreases the length of :math:`x` by exactly 1.
   If so, it is included in the result. In particular, this algorithm does not use
   .

.. magma:function:: BruhatDescendants(X)
   :input_types: SetEnum
   :output_types: SetEnum
   :label: BruhatDescendants_SetEnum
   :parameters: z : GrpPermElt : 

   Let :math:`X` consist of elements of the Coxeter group :math:`W`, then the
   returned set :math:`S` contains the Bruhat descendants of every element of
   :math:`X`.

   If the optional parameter :math:`z` is set, only those :math:`w` are returned
   for which :math:`z \leq w` in the Bruhat ordering.

.. magma:example:: Example: Bruhat Descendants
   :label: BruhatDescendants

   Bruhat descendants:

   .. code-block:: magma

      > R := RootDatum("D4" : Isogeny := "SC");
      > W := CoxeterGroup(GrpPermCox, R);
      > Wfp,phi := CoxeterGroup(GrpFPCox, W);
      > x := W.1*W.3*W.2*W.4*W.2*W.2*W.2*W.1;
      > Eltseq(phi(x));
      [ 1, 3, 2, 4, 2, 1 ]
      > S := BruhatDescendants(x);
      > { Eltseq(phi(w)) : w in S };
      {
           [ 1, 3, 2, 4, 2 ],
           [ 3, 2, 4, 2, 1 ],
           [ 1, 2, 4, 2, 1 ],
           [ 1, 3, 2, 1, 4 ],
           [ 1, 3, 4, 2, 1 ]
      }