Coxeter Groups#
- class sage.categories.coxeter_groups.CoxeterGroups(s=None)#
Bases:
Category_singleton
The category of Coxeter groups.
A Coxeter group is a group \(W\) with a distinguished (finite) family of involutions \((s_i)_{i\in I}\), called the simple reflections, subject to relations of the form \((s_is_j)^{m_{i,j}} = 1\).
\(I\) is the index set of \(W\) and \(|I|\) is the rank of \(W\).
See Wikipedia article Coxeter_group for details.
EXAMPLES:
sage: C = CoxeterGroups(); C Category of coxeter groups sage: C.super_categories() [Category of generalized coxeter groups] sage: W = C.example(); W The symmetric group on {0, ..., 3} sage: W.simple_reflections() Finite family {0: (1, 0, 2, 3), 1: (0, 2, 1, 3), 2: (0, 1, 3, 2)}
Here are some further examples:
sage: FiniteCoxeterGroups().example() # optional - sage.combinat sage.groups The 5-th dihedral group of order 10 sage: FiniteWeylGroups().example() # optional - sage.combinat sage.groups The symmetric group on {0, ..., 3} sage: WeylGroup(["B", 3]) # optional - sage.combinat sage.groups Weyl Group of type ['B', 3] (as a matrix group acting on the ambient space) sage: S4 = SymmetricGroup(4); S4 # optional - sage.groups Symmetric group of order 4! as a permutation group sage: S4 in CoxeterGroups().Finite() # optional - sage.groups True
Those will eventually be also in this category:
sage: DihedralGroup(5) # optional - sage.groups Dihedral group of order 10 as a permutation group
Todo
add a demo of usual computations on Coxeter groups.
See also
sage.combinat.root_system
Warning
It is assumed that morphisms in this category preserve the distinguished choice of simple reflections. In particular, subobjects in this category are parabolic subgroups. In this sense, this category might be better named
Coxeter Systems
. In the long run we might want to have two distinct categories, one for Coxeter groups (with morphisms being just group morphisms) and one for Coxeter systems:sage: CoxeterGroups().is_full_subcategory(Groups()) False sage: from sage.categories.generalized_coxeter_groups import GeneralizedCoxeterGroups sage: CoxeterGroups().is_full_subcategory(GeneralizedCoxeterGroups()) True
- Algebras#
alias of
CoxeterGroupAlgebras
- class ElementMethods#
Bases:
object
- absolute_covers()#
Return the list of covers of
self
in absolute order.See also
EXAMPLES:
sage: W = WeylGroup(["A", 3]) # optional - sage.combinat sage.groups sage: s = W.simple_reflections() # optional - sage.combinat sage.groups sage: w0 = s[1] # optional - sage.combinat sage.groups sage: w1 = s[1]*s[2]*s[3] # optional - sage.combinat sage.groups sage: w0.absolute_covers() # optional - sage.combinat sage.groups [ [0 0 1 0] [0 1 0 0] [0 1 0 0] [0 0 0 1] [0 1 0 0] [1 0 0 0] [1 0 0 0] [0 0 1 0] [1 0 0 0] [0 0 0 1] [0 1 0 0] [0 0 0 1] [1 0 0 0] [0 0 1 0] [0 0 1 0] [0 0 0 1], [0 0 1 0], [0 0 0 1], [0 1 0 0], [1 0 0 0] ]
- absolute_le(other)#
Return whether
self
is smaller thanother
in the absolute order.A general reflection is an element of the form \(w s_i w^{-1}\), where \(s_i\) is a simple reflection. The absolute order is defined analogously to the weak order but using general reflections rather than just simple reflections.
This partial order can be used to define noncrossing partitions associated with this Coxeter group.
See also
EXAMPLES:
sage: W = WeylGroup(["A", 3]) # optional - sage.combinat sage.groups sage: s = W.simple_reflections() # optional - sage.combinat sage.groups sage: w0 = s[1] # optional - sage.combinat sage.groups sage: w1 = s[1]*s[2]*s[3] # optional - sage.combinat sage.groups sage: w0.absolute_le(w1) # optional - sage.combinat sage.groups True sage: w1.absolute_le(w0) # optional - sage.combinat sage.groups False sage: w1.absolute_le(w1) # optional - sage.combinat sage.groups True
- absolute_length()#
Return the absolute length of
self
.The absolute length is the length of the shortest expression of the element as a product of reflections.
For permutations in the symmetric groups, the absolute length is the size minus the number of its disjoint cycles.
See also
EXAMPLES:
sage: W = WeylGroup(["A", 3]) # optional - sage.combinat sage.groups sage: s = W.simple_reflections() # optional - sage.combinat sage.groups sage: (s[1]*s[2]*s[3]).absolute_length() # optional - sage.combinat sage.groups 3 sage: W = SymmetricGroup(4) # optional - sage.combinat sage.groups sage: s = W.simple_reflections() # optional - sage.combinat sage.groups sage: (s[3]*s[2]*s[1]).absolute_length() # optional - sage.combinat sage.groups 3
- apply_demazure_product(element, side='right', length_increasing=True)#
Return the Demazure or 0-Hecke product of
self
with another Coxeter group element.See
CoxeterGroups.ParentMethods.simple_projections()
.INPUT:
element
– either an element of the same Coxetergroup as
self
or a tuple or a list (such as a reduced word) of elements from the index set of the Coxeter group.
side
– ‘left’ or ‘right’ (default: ‘right’); theside of
self
on which the element should be applied. Ifside
is ‘left’ then the operation is applied on the left.
length_increasing
– a boolean (default True)whether to act length increasingly or decreasingly
EXAMPLES:
sage: W = WeylGroup(['C', 4], prefix="s") # optional - sage.combinat sage.groups sage: v = W.from_reduced_word([1,2,3,4,3,1]) # optional - sage.combinat sage.groups sage: v.apply_demazure_product([1,3,4,3,3]) # optional - sage.combinat sage.groups s4*s1*s2*s3*s4*s3*s1 sage: v.apply_demazure_product([1,3,4,3], side='left') # optional - sage.combinat sage.groups s3*s4*s1*s2*s3*s4*s2*s3*s1 sage: v.apply_demazure_product((1,3,4,3), side='left') # optional - sage.combinat sage.groups s3*s4*s1*s2*s3*s4*s2*s3*s1 sage: v.apply_demazure_product(v) # optional - sage.combinat sage.groups s2*s3*s4*s1*s2*s3*s4*s2*s3*s2*s1
- apply_simple_projection(i, side='right', length_increasing=True)#
Return the result of the application of the simple projection \(\pi_i\) (resp. \(\overline\pi_i\)) on
self
.INPUT:
i
- an element of the index set of the Coxeter groupside
- ‘left’ or ‘right’ (default: ‘right’)length_increasing
- a boolean (default: True) specifying the direction of the projection
See
CoxeterGroups.ParentMethods.simple_projections()
for the definition of the simple projections.EXAMPLES:
sage: W = CoxeterGroups().example() sage: w = W.an_element() sage: w (1, 2, 3, 0) sage: w.apply_simple_projection(2) (1, 2, 3, 0) sage: w.apply_simple_projection(2, length_increasing=False) (1, 2, 0, 3) sage: W = WeylGroup(['C', 4], prefix="s") # optional - sage.combinat sage.groups sage: v = W.from_reduced_word([1,2,3,4,3,1]) # optional - sage.combinat sage.groups sage: v # optional - sage.combinat sage.groups s1*s2*s3*s4*s3*s1 sage: v.apply_simple_projection(2) # optional - sage.combinat sage.groups s1*s2*s3*s4*s3*s1*s2 sage: v.apply_simple_projection(2, side='left') # optional - sage.combinat sage.groups s1*s2*s3*s4*s3*s1 sage: v.apply_simple_projection(1, length_increasing=False) # optional - sage.combinat sage.groups s1*s2*s3*s4*s3
- binary_factorizations(predicate=The constant function (...) -> True)#
Return the set of all the factorizations \(self = u v\) such that \(l(self) = l(u) + l(v)\).
Iterating through this set is Constant Amortized Time (counting arithmetic operations in the Coxeter group as constant time) complexity, and memory linear in the length of \(self\).
One can pass as optional argument a predicate p such that \(p(u)\) implies \(p(u')\) for any \(u\) left factor of \(self\) and \(u'\) left factor of \(u\). Then this returns only the factorizations \(self = uv\) such \(p(u)\) holds.
EXAMPLES:
We construct the set of all factorizations of the maximal element of the group:
sage: W = WeylGroup(['A', 3]) # optional - sage.combinat sage.groups sage: s = W.simple_reflections() # optional - sage.combinat sage.groups sage: w0 = W.from_reduced_word([1,2,3,1,2,1]) # optional - sage.combinat sage.groups sage: w0.binary_factorizations().cardinality() # optional - sage.combinat sage.groups 24
The same number of factorizations, by bounded length:
sage: [w0.binary_factorizations( # optional - sage.combinat sage.groups ....: lambda u: u.length() <= l ....: ).cardinality() ....: for l in [-1,0,1,2,3,4,5,6]] [0, 1, 4, 9, 15, 20, 23, 24]
The number of factorizations of the elements just below the maximal element:
sage: [(s[i]*w0).binary_factorizations().cardinality() # optional - sage.combinat sage.groups ....: for i in [1,2,3]] [12, 12, 12] sage: w0.binary_factorizations(lambda u: False).cardinality() # optional - sage.combinat sage.groups 0
- bruhat_le(other)#
Return whether
self
<=other
in the Bruhat order.INPUT:
other – an element of the same Coxeter group
OUTPUT: a boolean
EXAMPLES:
sage: W = WeylGroup(["A", 3]) # optional - sage.combinat sage.groups sage: u = W.from_reduced_word([1,2,1]) # optional - sage.combinat sage.groups sage: v = W.from_reduced_word([1,2,3,2,1]) # optional - sage.combinat sage.groups sage: u.bruhat_le(u) # optional - sage.combinat sage.groups True sage: u.bruhat_le(v) # optional - sage.combinat sage.groups True sage: v.bruhat_le(u) # optional - sage.combinat sage.groups False sage: v.bruhat_le(v) # optional - sage.combinat sage.groups True sage: s = W.simple_reflections() # optional - sage.combinat sage.groups sage: s[1].bruhat_le(W.one()) # optional - sage.combinat sage.groups False
The implementation uses the equivalent condition that any reduced word for
other
contains a reduced word forself
as subword. See Stembridge, A short derivation of the Möbius function for the Bruhat order. J. Algebraic Combin. 25 (2007), no. 2, 141–148, Proposition 1.1.Complexity: \(O(l * c)\), where \(l\) is the minimum of the lengths of \(u\) and of \(v\), and \(c\) is the cost of the low level methods
first_descent()
,has_descent()
,apply_simple_reflection()
), etc. Those are typically \(O(n)\), where \(n\) is the rank of the Coxeter group.
- bruhat_lower_covers()#
Return all elements that
self
covers in (strong) Bruhat order.If
w = self
has a descent at \(i\), then the elements that \(w\) covers are exactly \(\{ws_i, u_1s_i, u_2s_i,..., u_js_i\}\), where the \(u_k\) are elements that \(ws_i\) covers that also do not have a descent at \(i\).EXAMPLES:
sage: W = WeylGroup(["A", 3]) # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([3,2,3]) # optional - sage.combinat sage.groups sage: print([v.reduced_word() for v in w.bruhat_lower_covers()]) # optional - sage.combinat sage.groups [[3, 2], [2, 3]] sage: W = WeylGroup(["A", 3]) # optional - sage.combinat sage.groups sage: print([v.reduced_word() # optional - sage.combinat sage.groups ....: for v in W.simple_reflection(1).bruhat_lower_covers()]) [[]] sage: print([v.reduced_word() # optional - sage.combinat sage.groups ....: for v in W.one().bruhat_lower_covers()]) [] sage: W = WeylGroup(["B", 4, 1]) # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([0,2]) # optional - sage.combinat sage.groups sage: print([v.reduced_word() for v in w.bruhat_lower_covers()]) # optional - sage.combinat sage.groups [[2], [0]] sage: W = WeylGroup("A3", prefix="s", implementation="permutation") # optional - sage.combinat sage.groups sage: s1, s2, s3 = W.simple_reflections() # optional - sage.combinat sage.groups sage: (s1*s2*s3*s1).bruhat_lower_covers() # optional - sage.combinat sage.groups [s2*s1*s3, s1*s2*s1, s1*s2*s3]
We now show how to construct the Bruhat poset:
sage: W = WeylGroup(["A", 3]) # optional - sage.combinat sage.groups sage: covers = tuple([u, v] # optional - sage.combinat sage.groups ....: for v in W for u in v.bruhat_lower_covers()) sage: P = Poset((W, covers), cover_relations = True) # optional - sage.combinat sage.groups sage.graphs sage: P.show() # optional - sage.combinat sage.groups sage.graphs
Alternatively, one can just use:
sage: P = W.bruhat_poset() # optional - sage.combinat sage.groups sage.graphs
The algorithm is taken from Stembridge’s ‘coxeter/weyl’ package for Maple.
- bruhat_lower_covers_reflections()#
Return all 2-tuples of lower_covers and reflections (
v
,r
) wherev
is covered byself
andr
is the reflection such thatself
=v
r
.ALGORITHM:
EXAMPLES:
sage: W = WeylGroup(['A', 3], prefix="s") # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([3,1,2,1]) # optional - sage.combinat sage.groups sage: w.bruhat_lower_covers_reflections() # optional - sage.combinat sage.groups [(s1*s2*s1, s1*s2*s3*s2*s1), (s3*s2*s1, s2), (s3*s1*s2, s1)]
- bruhat_upper_covers()#
Return all elements that cover
self
in (strong) Bruhat order.The algorithm works recursively, using the ‘inverse’ of the method described for lower covers
bruhat_lower_covers()
. Namely, it runs through all \(i\) in the index set. Let \(w\) equalself
. If \(w\) has no right descent \(i\), then \(w s_i\) is a cover; if \(w\) has a decent at \(i\), then \(u_j s_i\) is a cover of \(w\) where \(u_j\) is a cover of \(w s_i\).EXAMPLES:
sage: W = WeylGroup(['A', 3, 1], prefix="s") # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([1,2,1]) # optional - sage.combinat sage.groups sage: w.bruhat_upper_covers() # optional - sage.combinat sage.groups [s1*s2*s1*s0, s1*s2*s0*s1, s0*s1*s2*s1, s3*s1*s2*s1, s2*s3*s1*s2, s1*s2*s3*s1] sage: W = WeylGroup(['A', 3]) # optional - sage.combinat sage.groups sage: w = W.long_element() # optional - sage.combinat sage.groups sage: w.bruhat_upper_covers() # optional - sage.combinat sage.groups [] sage: W = WeylGroup(['A', 3]) # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([1,2,1]) # optional - sage.combinat sage.groups sage: S = [v for v in W if w in v.bruhat_lower_covers()] # optional - sage.combinat sage.groups sage: C = w.bruhat_upper_covers() # optional - sage.combinat sage.groups sage: set(S) == set(C) # optional - sage.combinat sage.groups True
- bruhat_upper_covers_reflections()#
Return all 2-tuples of covers and reflections (
v
,r
) wherev
coversself
andr
is the reflection such thatself
=v
r
.ALGORITHM:
EXAMPLES:
sage: W = WeylGroup(['A', 4], prefix="s") # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([3,1,2,1]) # optional - sage.combinat sage.groups sage: w.bruhat_upper_covers_reflections() # optional - sage.combinat sage.groups [(s1*s2*s3*s2*s1, s3), (s2*s3*s1*s2*s1, s2*s3*s2), (s3*s4*s1*s2*s1, s4), (s4*s3*s1*s2*s1, s1*s2*s3*s4*s3*s2*s1)]
- canonical_matrix()#
Return the matrix of
self
in the canonical faithful representation.This is an \(n\)-dimension real faithful essential representation, where \(n\) is the number of generators of the Coxeter group. Note that this is not always the most natural matrix representation, for instance in type \(A_n\).
EXAMPLES:
sage: W = WeylGroup(["A", 3]) # optional - sage.combinat sage.groups sage: s = W.simple_reflections() # optional - sage.combinat sage.groups sage: (s[1]*s[2]*s[3]).canonical_matrix() # optional - sage.combinat sage.groups [ 0 0 -1] [ 1 0 -1] [ 0 1 -1]
- coset_representative(index_set, side='right')#
Return the unique shortest element of the Coxeter group \(W\) which is in the same left (resp. right) coset as
self
, with respect to the parabolic subgroup \(W_I\).INPUT:
index_set
- a subset (or iterable) of the nodes of the Dynkin diagramside
- ‘left’ or ‘right’
EXAMPLES:
sage: W = CoxeterGroups().example(5) sage: s = W.simple_reflections() sage: w = s[2]*s[1]*s[3] sage: w.coset_representative([]).reduced_word() [2, 3, 1] sage: w.coset_representative([1]).reduced_word() [2, 3] sage: w.coset_representative([1,2]).reduced_word() [2, 3] sage: w.coset_representative([1,3] ).reduced_word() [2] sage: w.coset_representative([2,3] ).reduced_word() [2, 1] sage: w.coset_representative([1,2,3] ).reduced_word() [] sage: w.coset_representative([], side='left').reduced_word() [2, 3, 1] sage: w.coset_representative([1], side='left').reduced_word() [2, 3, 1] sage: w.coset_representative([1,2], side='left').reduced_word() [3] sage: w.coset_representative([1,3], side='left').reduced_word() [2, 3, 1] sage: w.coset_representative([2,3], side='left').reduced_word() [1] sage: w.coset_representative([1,2,3], side='left').reduced_word() []
- cover_reflections(side='right')#
Return the set of reflections
t
such thatself
t
coversself
.If
side
is ‘left’,t
self
coversself
.EXAMPLES:
sage: W = WeylGroup(['A', 4], prefix="s") # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([3,1,2,1]) # optional - sage.combinat sage.groups sage: w.cover_reflections() # optional - sage.combinat sage.groups [s3, s2*s3*s2, s4, s1*s2*s3*s4*s3*s2*s1] sage: w.cover_reflections(side='left') # optional - sage.combinat sage.groups [s4, s2, s1*s2*s1, s3*s4*s3]
- coxeter_sorting_word(c)#
Return the
c
-sorting word ofself
.For a Coxeter element \(c\) and an element \(w\), the \(c\)-sorting word of \(w\) is the lexicographic minimal reduced expression of \(w\) in the infinite word \(c^\infty\).
INPUT:
c
– a Coxeter element.
OUTPUT:
the
c
-sorting word ofself
as a list of integers.EXAMPLES:
sage: W = CoxeterGroups().example() sage: c = W.from_reduced_word([0,2,1]) sage: w = W.from_reduced_word([1,2,1,0,1]) sage: w.coxeter_sorting_word(c) [2, 1, 2, 0, 1]
- deodhar_factor_element(w, index_set)#
Return Deodhar’s Bruhat order factoring element.
INPUT:
w
is an element of the same Coxeter groupW
asself
index_set
is a subset of Dynkin nodes defining a parabolic subgroupW'
ofW
It is assumed that
v = self
andw
are minimum length coset representatives forW/W'
such thatv
\(\le\)w
in Bruhat order.OUTPUT:
Deodhar’s element
f(v,w)
is the unique element ofW'
such that, for allv'
andw'
inW'
,vv'
\(\le\)ww'
inW
if and only ifv'
\(\le\)f(v,w) * w'
inW'
where*
is the Demazure product.EXAMPLES:
sage: W = WeylGroup(['A', 5], prefix="s") # optional - sage.combinat sage.groups sage: v = W.from_reduced_word([5]) # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([4,5,2,3,1,2]) # optional - sage.combinat sage.groups sage: v.deodhar_factor_element(w, [1,3,4]) # optional - sage.combinat sage.groups s3*s1 sage: W = WeylGroup(['C', 2]) # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([2,1]) # optional - sage.combinat sage.groups sage: w.deodhar_factor_element(W.from_reduced_word([2]),[1]) # optional - sage.combinat sage.groups Traceback (most recent call last): ... ValueError: [2, 1] is not of minimum length in its coset for the parabolic subgroup with index set [1]
REFERENCES:
- deodhar_lift_down(w, index_set)#
Letting
v = self
, given a Bruhat relationv W'
\(\ge\)w W'
among cosets with respect to the subgroupW'
given by the Dynkin node subsetindex_set
, returns the Bruhat-maximum liftx
ofwW'
such thatv
\(\ge\)x
.INPUT:
w
is an element of the same Coxeter groupW
asself
.index_set
is a subset of Dynkin nodes defining a parabolic subgroupW'
.
OUTPUT:
The unique Bruhat-maximum element
x
inW
such thatx W' = w W'
andv
\(\ge\)x
.EXAMPLES:
sage: W = WeylGroup(['A', 3], prefix="s") # optional - sage.combinat sage.groups sage: v = W.from_reduced_word([1,2,3,2]) # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([3,2]) # optional - sage.combinat sage.groups sage: v.deodhar_lift_down(w, [3]) # optional - sage.combinat sage.groups s2*s3*s2
- deodhar_lift_up(w, index_set)#
Letting
v = self
, given a Bruhat relationv W'
\(\le\)w W'
among cosets with respect to the subgroupW'
given by the Dynkin node subsetindex_set
, returns the Bruhat-minimum liftx
ofwW'
such thatv
\(\le\)x
.INPUT:
w
is an element of the same Coxeter groupW
asself
.index_set
is a subset of Dynkin nodes defining a parabolic subgroupW'
.
OUTPUT:
The unique Bruhat-minimum element
x
inW
such thatx W' = w W'
andv
\(\le\)x
.EXAMPLES:
sage: W = WeylGroup(['A', 3], prefix="s") # optional - sage.combinat sage.groups sage: v = W.from_reduced_word([1,2,3]) # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([1,3,2]) # optional - sage.combinat sage.groups sage: v.deodhar_lift_up(w, [3]) # optional - sage.combinat sage.groups s1*s2*s3*s2
- descents(side='right', index_set=None, positive=False)#
Return the descents of self, as a list of elements of the index_set.
INPUT:
index_set
- a subset (as a list or iterable) of the nodes of the Dynkin diagram; (default: all of them)side
- ‘left’ or ‘right’ (default: ‘right’)positive
- a boolean (default:False
)
The
index_set
option can be used to restrict to the parabolic subgroup indexed byindex_set
.If positive is
True
, then returns the non-descents insteadTodo
find a better name for
positive
: complement? non_descent?Caveat: the return type may change to some other iterable (tuple, …) in the future. Please use keyword arguments also, as the order of the arguments may change as well.
EXAMPLES:
sage: W = CoxeterGroups().example() sage: s = W.simple_reflections() sage: w = s[0]*s[1] sage: w.descents() [1] sage: w = s[0]*s[2] sage: w.descents() [0, 2]
Todo
side, index_set, positive
- first_descent(side='right', index_set=None, positive=False)#
Return the first left (resp. right) descent of self, as an element of
index_set
, orNone
if there is none.See
descents()
for a description of the options.EXAMPLES:
sage: W = CoxeterGroups().example() sage: s = W.simple_reflections() sage: w = s[2]*s[0] sage: w.first_descent() 0 sage: w = s[0]*s[2] sage: w.first_descent() 0 sage: w = s[0]*s[1] sage: w.first_descent() 1
- has_descent(i, side='right', positive=False)#
Return whether i is a (left/right) descent of self.
See
descents()
for a description of the options.EXAMPLES:
sage: W = CoxeterGroups().example() sage: s = W.simple_reflections() sage: w = s[0] * s[1] * s[2] sage: w.has_descent(2) True sage: [ w.has_descent(i) for i in [0,1,2] ] [False, False, True] sage: [ w.has_descent(i, side='left') for i in [0,1,2] ] [True, False, False] sage: [ w.has_descent(i, positive=True) for i in [0,1,2] ] [True, True, False]
This default implementation delegates the work to
has_left_descent()
andhas_right_descent()
.
- has_full_support()#
Return whether
self
has full support.An element is said to have full support if its support contains all simple reflections.
EXAMPLES:
sage: W = CoxeterGroups().example() sage: w = W.from_reduced_word([1,2,1]) sage: w.has_full_support() False sage: w = W.from_reduced_word([1,2,1,0,1]) sage: w.has_full_support() True
- has_left_descent(i)#
Return whether \(i\) is a left descent of self.
This default implementation uses that a left descent of \(w\) is a right descent of \(w^{-1}\).
EXAMPLES:
sage: W = CoxeterGroups().example(); W The symmetric group on {0, ..., 3} sage: w = W.an_element(); w (1, 2, 3, 0) sage: w.has_left_descent(0) True sage: w.has_left_descent(1) False sage: w.has_left_descent(2) False
- has_right_descent(i)#
Return whether
i
is a right descent of self.EXAMPLES:
sage: W = CoxeterGroups().example(); W The symmetric group on {0, ..., 3} sage: w = W.an_element(); w (1, 2, 3, 0) sage: w.has_right_descent(0) False sage: w.has_right_descent(1) False sage: w.has_right_descent(2) True
- inversions_as_reflections()#
Return the set of reflections
r
such thatself
r < self
.EXAMPLES:
sage: W = WeylGroup(['A', 3], prefix="s") # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([3,1,2,1]) # optional - sage.combinat sage.groups sage: w.inversions_as_reflections() # optional - sage.combinat sage.groups [s1, s1*s2*s1, s2, s1*s2*s3*s2*s1]
- is_coxeter_sortable(c, sorting_word=None)#
Return whether
self
isc
-sortable.Given a Coxeter element \(c\), an element \(w\) is \(c\)-sortable if its \(c\)-sorting word decomposes into a sequence of weakly decreasing subwords of \(c\).
INPUT:
c
– a Coxeter element.sorting_word
– sorting word (default: None) used to not recompute thec
-sorting word if already computed.
OUTPUT:
is
self
c
-sortableEXAMPLES:
sage: W = CoxeterGroups().example() sage: c = W.from_reduced_word([0,2,1]) sage: w = W.from_reduced_word([1,2,1,0,1]) sage: w.coxeter_sorting_word(c) [2, 1, 2, 0, 1] sage: w.is_coxeter_sortable(c) False sage: w = W.from_reduced_word([0,2,1,0,2]) sage: w.coxeter_sorting_word(c) [2, 0, 1, 2, 0] sage: w.is_coxeter_sortable(c) True sage: W = CoxeterGroup(['A', 3]) # optional - sage.combinat sage.groups sage: c = W.from_reduced_word([1,2,3]) # optional - sage.combinat sage.groups
Number of \(c\)-sortable elements in \(A_3\) (Catalan number):
sage: len([w for w in W if w.is_coxeter_sortable(c)]) # optional - sage.combinat sage.groups 14
- is_fully_commutative()#
Check if
self
is a fully-commutative element.We use the characterization that an element \(w\) in a Coxeter system \((W,S)\) is fully-commutative if and only if for every pair of generators \(s,t \in S\) for which \(m(s,t)>2\), no reduced word of \(w\) contains the ‘braid’ word \(sts...\) of length \(m(s,t)\) as a contiguous subword. See [Ste1996].
EXAMPLES:
sage: W = CoxeterGroup(['A', 3]) sage: len([1 for w in W if w.is_fully_commutative()]) 14 sage: W = CoxeterGroup(['B', 3]) sage: len([1 for w in W if w.is_fully_commutative()]) 24
- is_grassmannian(side='right')#
Return whether
self
is Grassmannian.INPUT:
side
– “left” or “right” (default: “right”)
An element is Grassmannian if it has at most one descent on the right (resp. on the left).
EXAMPLES:
sage: W = CoxeterGroups().example(); W The symmetric group on {0, ..., 3} sage: s = W.simple_reflections() sage: W.one().is_grassmannian() True sage: s[1].is_grassmannian() True sage: (s[1]*s[2]).is_grassmannian() True sage: (s[0]*s[1]).is_grassmannian() True sage: (s[1]*s[2]*s[1]).is_grassmannian() False sage: (s[0]*s[2]*s[1]).is_grassmannian(side="left") False sage: (s[0]*s[2]*s[1]).is_grassmannian(side="right") True sage: (s[0]*s[2]*s[1]).is_grassmannian() True
- kazhdan_lusztig_cell(side='left')#
Compute the left, right, or two-sided Kazhdan-Lusztig cell containing the element
self
depending on the specifiedside
.Let \(C'\) denote the Kazhdan-Lusztig \(C^{\prime}\)-basis of the Iwahori-Hecke algebra \(H\) of a Coxeter system \((W,S)\). Two elements \(x,y\) of the Coxeter group \(W\) are said to lie in the same left Kazhdan-Lusztig cell if there exist sequences \(x = w_1, w_2, \ldots, w_k = y\) and \(y = u_1, u_2, \ldots, u_l = x\) such that for all \(1 \leq i < k\) and all \(1 \leq j < l\), there exist some Coxeter generators \(s,t \in S\) for which \(C'_{w_{i+1}}\) appears in \(C'_s C'_{w_i}\) and \(C'_{u_{j+1}}\) appears in \(C'_s C'_{u_j}\) in \(H\). Right and two-sided Kazhdan-Lusztig cells of \(W\) are defined similarly; see [Lus2013].
In this function, we compute products in the \(C^{\prime}\) basis by using
IwahoriHeckeAlgebra.Cp
. As mentioned in that class, installing the optional packagecoxeter3
is recommended (though not required) before using this function because the package speeds up product computations that are sometimes computationally infeasible without it.INPUT:
w
– an element ofself
side
– (default:'left'
) the kind of cell to compute; must be either'left'
,'right'
, or'two-sided'
EXAMPLES:
We compute the left cell of the generator \(s_1\) in type \(A_3\) in three different implementations of the Coxeter group. Note that the choice of implementation affects the representation of elements in the output cell but not the method used for the cell computation:
sage: W = CoxeterGroup('A3', implementation='permutation') # optional - sage.combinat sage.groups sage: s1, s2, s3 = W.simple_reflections() # optional - sage.combinat sage.groups sage: s1.kazhdan_lusztig_cell() # optional - sage.combinat sage.groups {(1,2,3,12)(4,5,10,11)(6,7,8,9), (1,2,10)(3,6,5)(4,7,8)(9,12,11), (1,7)(2,4)(5,6)(8,10)(11,12)}
The cell computation uses the optional package
coxeter3
in the background if available to speed up the computation, even in the different implementations implementations:sage: W = WeylGroup('A3', prefix='s') # optional - coxeter3 sage: s1,s2,s3 = W.simple_reflections() # optional - coxeter3 sage: s1.kazhdan_lusztig_cell() # optional - coxeter3 {s3*s2*s1, s2*s1, s1} sage: W = CoxeterGroup('A3', implementation='coxeter3') # optional - coxeter3 sage: s1,s2,s3 = W.simple_reflections() # optional - coxeter3 sage: s1.kazhdan_lusztig_cell() # optional - coxeter3 {[1], [2, 1], [3, 2, 1]}
Next, we compute a right cell and a two-sided cell in \(A_3\):
sage: W = CoxeterGroup('A3', implementation='coxeter3') # optional - coxeter3 sage: s1,s2,s3 = W.simple_reflections() # optional - coxeter3 sage: w = s1 * s3 # optional - coxeter3 sage: w.kazhdan_lusztig_cell(side='right') # optional - coxeter3 {[1, 3], [1, 3, 2]} sage: w.kazhdan_lusztig_cell(side='two-sided') # optional - coxeter3 {[1, 3], [1, 3, 2], [2, 1, 3], [2, 1, 3, 2]} Some slightly longer computations in `B_4`:: sage: W = CoxeterGroup('B4', implementation='coxeter3') # optional - coxeter3 sage: s1,s2,s3,s4 = W.simple_reflections() # optional - coxeter3 sage: s1.kazhdan_lusztig_cell(side='right') # long time (4 seconds) # optional - coxeter3 {[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 3], [1, 2, 3, 4, 3, 2], [1, 2, 3, 4, 3, 2, 1]} sage: (s4*s2*s3*s4).kazhdan_lusztig_cell(side='two-sided') # long time (8 seconds) # optional - coxeter3 {[2, 3, 1], [2, 3, 1, 2], [2, 3, 4, 1], [2, 3, 4, 1, 2], [2, 3, 4, 1, 2, 3], [2, 3, 4, 1, 2, 3, 4], [2, 3, 4, 3, 1], [2, 3, 4, 3, 1, 2], ... [4, 3, 4, 2, 3, 4, 1, 2, 3, 4]}
- left_inversions_as_reflections()#
Return the set of reflections
r
such thatr
self
<self
.EXAMPLES:
sage: W = WeylGroup(['A', 3], prefix="s") # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([3,1,2,1]) # optional - sage.combinat sage.groups sage: w.left_inversions_as_reflections() # optional - sage.combinat sage.groups [s1, s3, s1*s2*s3*s2*s1, s2*s3*s2]
- length()#
Return the length of
self
.This is the minimal length of a product of simple reflections giving
self
.EXAMPLES:
sage: W = CoxeterGroups().example() sage: s1 = W.simple_reflection(1) sage: s2 = W.simple_reflection(2) sage: s1.length() 1 sage: (s1*s2).length() 2 sage: W = CoxeterGroups().example() sage: s = W.simple_reflections() sage: w = s[0]*s[1]*s[0] sage: w.length() 3 sage: W = CoxeterGroups().example() sage: R.<x> = ZZ[] sage: s = sum(x^w.length() for w in W) sage: p = prod(sum(x^i for i in range(j)) for j in range(1, 5)) sage: s - p 0
See also
Todo
Should use reduced_word_iterator (or reverse_iterator)
- lower_cover_reflections(side='right')#
Return the reflections
t
such thatself
coversself
t
.If
side
is ‘left’,self
coverst
self
.EXAMPLES:
sage: W = WeylGroup(['A', 3],prefix="s") # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([3,1,2,1]) # optional - sage.combinat sage.groups sage: w.lower_cover_reflections() # optional - sage.combinat sage.groups [s1*s2*s3*s2*s1, s2, s1] sage: w.lower_cover_reflections(side='left') # optional - sage.combinat sage.groups [s2*s3*s2, s3, s1]
- lower_covers(side='right', index_set=None)#
Return all elements that
self
covers in weak order.INPUT:
side
–'left'
or'right'
(default:'right'
)index_set
– a list of indices orNone
OUTPUT: a list
EXAMPLES:
sage: W = WeylGroup(['A', 3]) # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([3,2,1]) # optional - sage.combinat sage.groups sage: [x.reduced_word() for x in w.lower_covers()] # optional - sage.combinat sage.groups [[3, 2]]
To obtain covers for left weak order, set the option side to ‘left’:
sage: [x.reduced_word() for x in w.lower_covers(side='left')] # optional - sage.combinat sage.groups [[2, 1]] sage: w = W.from_reduced_word([3,2,3,1]) # optional - sage.combinat sage.groups sage: [x.reduced_word() for x in w.lower_covers()] # optional - sage.combinat sage.groups [[2, 3, 2], [3, 2, 1]]
Covers w.r.t. a parabolic subgroup are obtained with the option
index_set
:sage: [x.reduced_word() for x in w.lower_covers(index_set=[1,2])] # optional - sage.combinat sage.groups [[2, 3, 2]] sage: [x.reduced_word() for x in w.lower_covers(side='left')] # optional - sage.combinat sage.groups [[3, 2, 1], [2, 3, 1]]
- min_demazure_product_greater(element)#
Find the unique Bruhat-minimum element
u
such thatv
\(\le\)w
*u
wherev
isself
,w
iselement
and*
is the Demazure product.INPUT:
element
is either an element of the same Coxeter group asself
or a list (such as a reduced word) of elements from the index set of the Coxeter group.
EXAMPLES:
sage: W = WeylGroup(['A', 4], prefix="s") # optional - sage.combinat sage.groups sage: v = W.from_reduced_word([2,3,4,1,2]) # optional - sage.combinat sage.groups sage: u = W.from_reduced_word([2,3,2,1]) # optional - sage.combinat sage.groups sage: v.min_demazure_product_greater(u) # optional - sage.combinat sage.groups s4*s2 sage: v.min_demazure_product_greater([2,3,2,1]) # optional - sage.combinat sage.groups s4*s2 sage: v.min_demazure_product_greater((2,3,2,1)) # optional - sage.combinat sage.groups s4*s2
- reduced_word()#
Return a reduced word for
self
.This is a word \([i_1,i_2,\ldots,i_k]\) of minimal length such that \(s_{i_1} s_{i_2} \cdots s_{i_k} = \operatorname{self}\), where the \(s_i\) are the simple reflections.
EXAMPLES:
sage: W = CoxeterGroups().example() sage: s = W.simple_reflections() sage: w = s[0]*s[1]*s[2] sage: w.reduced_word() [0, 1, 2] sage: w = s[0]*s[2] sage: w.reduced_word() [2, 0]
- reduced_word_graph()#
Return the reduced word graph of
self
.The reduced word graph of an element \(w\) in a Coxeter group is the graph whose vertices are the reduced words for \(w\) (see
reduced_word()
for a definition of this term), and which has an \(m\)-colored edge between two reduced words \(x\) and \(y\) whenever \(x\) and \(y\) differ by exactly one length-\(m\) braid move (with \(m \geq 2\)).This graph is always connected (a theorem due to Tits) and has no multiple edges.
EXAMPLES:
sage: W = WeylGroup(['A', 3], prefix='s') # optional - sage.combinat sage.groups sage: w0 = W.long_element() # optional - sage.combinat sage.groups sage: G = w0.reduced_word_graph() # optional - sage.combinat sage.groups sage.graphs sage: G.num_verts() # optional - sage.combinat sage.groups sage.graphs 16 sage: len(w0.reduced_words()) # optional - sage.combinat sage.groups sage.graphs 16 sage: G.num_edges() # optional - sage.combinat sage.groups sage.graphs 18 sage: len([e for e in G.edges(sort=False) if e[2] == 2]) # optional - sage.combinat sage.groups sage.graphs 10 sage: len([e for e in G.edges(sort=False) if e[2] == 3]) # optional - sage.combinat sage.groups sage.graphs 8
- reduced_word_reverse_iterator()#
Return a reverse iterator on a reduced word for
self
.EXAMPLES:
sage: W = CoxeterGroups().example() sage: s = W.simple_reflections() sage: sigma = s[0]*s[1]*s[2] sage: rI=sigma.reduced_word_reverse_iterator() sage: [i for i in rI] [2, 1, 0] sage: s[0]*s[1]*s[2]==sigma True sage: sigma.length() 3
See also
Default implementation: recursively remove the first right descent until the identity is reached (see
first_descent()
andapply_simple_reflection()
).
- reduced_words()#
Return all reduced words for
self
.See
reduced_word()
for the definition of a reduced word.The algorithm uses the Matsumoto property that any two reduced expressions are related by braid relations, see Theorem 3.3.1(ii) in [BB2005].
See also
braid_orbit()
EXAMPLES:
sage: W = CoxeterGroups().example() sage: s = W.simple_reflections() sage: w = s[0] * s[2] sage: sorted(w.reduced_words()) # optional - sage.combinat [[0, 2], [2, 0]] sage: W = WeylGroup(['E', 6]) # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([2,3,4,2]) # optional - sage.combinat sage.groups sage: sorted(w.reduced_words()) # optional - sage.combinat sage.groups [[2, 3, 4, 2], [3, 2, 4, 2], [3, 4, 2, 4]] sage: W = ReflectionGroup(['A',3], # optional - gap3 ....: index_set=["AA","BB","5"]) sage: w = W.long_element() # optional - gap3 sage: w.reduced_words() # optional - gap3 [['BB', '5', 'AA', 'BB', '5', 'AA'], ['5', 'BB', '5', 'AA', 'BB', '5'], ['BB', 'AA', 'BB', '5', 'BB', 'AA'], ['AA', '5', 'BB', 'AA', '5', 'BB'], ['5', 'AA', 'BB', 'AA', '5', 'BB'], ['AA', 'BB', '5', 'AA', 'BB', 'AA'], ['AA', 'BB', 'AA', '5', 'BB', 'AA'], ['AA', 'BB', '5', 'BB', 'AA', 'BB'], ['BB', 'AA', '5', 'BB', 'AA', '5'], ['BB', '5', 'AA', 'BB', 'AA', '5'], ['AA', '5', 'BB', '5', 'AA', 'BB'], ['5', 'BB', 'AA', '5', 'BB', '5'], ['5', 'BB', 'AA', 'BB', '5', 'BB'], ['5', 'AA', 'BB', '5', 'AA', 'BB'], ['BB', '5', 'BB', 'AA', 'BB', '5'], ['BB', 'AA', '5', 'BB', '5', 'AA']]
Todo
The result should be full featured finite enumerated set (e.g., counting can be done much faster than iterating).
- reduced_words_iter()#
Iterate over all reduced words for
self
.See
reduced_word()
for the definition of a reduced word.The algorithm uses the Matsumoto property that any two reduced expressions are related by braid relations, see Theorem 3.3.1(ii) in [BB2005].
See also
braid_orbit_iter()
EXAMPLES:
sage: W = CoxeterGroups().example() sage: s = W.simple_reflections() sage: w = s[0] * s[2] sage: sorted(w.reduced_words_iter()) # optional - sage.combinat [[0, 2], [2, 0]]
- reflection_length()#
Return the reflection length of
self
.The reflection length is the length of the shortest expression of the element as a product of reflections.
See also
EXAMPLES:
sage: W = WeylGroup(['A', 3]) # optional - sage.combinat sage.groups sage: s = W.simple_reflections() # optional - sage.combinat sage.groups sage: (s[1]*s[2]*s[3]).reflection_length() # optional - sage.combinat sage.groups 3 sage: W = SymmetricGroup(4) # optional - sage.combinat sage.groups sage: s = W.simple_reflections() # optional - sage.combinat sage.groups sage: (s[3]*s[2]*s[3]).reflection_length() # optional - sage.combinat sage.groups 1
- support()#
Return the support of
self
, that is the simple reflections that appear in the reduced expressions ofself
.OUTPUT:
The support of
self
as a set of integersEXAMPLES:
sage: W = CoxeterGroups().example() sage: w = W.from_reduced_word([1,2,1]) sage: w.support() {1, 2}
- upper_covers(side='right', index_set=None)#
Return all elements that cover
self
in weak order.INPUT:
side
–'left'
or'right'
(default:'right'
)index_set
– a list of indices orNone
OUTPUT: a list
EXAMPLES:
sage: W = WeylGroup(['A', 3]) # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([2,3]) # optional - sage.combinat sage.groups sage: [x.reduced_word() for x in w.upper_covers()] # optional - sage.combinat sage.groups [[2, 3, 1], [2, 3, 2]]
To obtain covers for left weak order, set the option
side
to ‘left’:sage: [x.reduced_word() for x in w.upper_covers(side='left')] # optional - sage.combinat sage.groups [[1, 2, 3], [2, 3, 2]]
Covers w.r.t. a parabolic subgroup are obtained with the option
index_set
:sage: [x.reduced_word() for x in w.upper_covers(index_set=[1])] # optional - sage.combinat sage.groups [[2, 3, 1]] sage: [x.reduced_word() # optional - sage.combinat sage.groups ....: for x in w.upper_covers(side='left', index_set=[1])] [[1, 2, 3]]
- weak_covers(side='right', index_set=None, positive=False)#
Return all elements that
self
covers in weak order.INPUT:
side – ‘left’ or ‘right’ (default: ‘right’)
positive – a boolean (default: False)
index_set – a list of indices or None
OUTPUT: a list
EXAMPLES:
sage: W = WeylGroup(['A', 3]) # optional - sage.combinat sage.groups sage: w = W.from_reduced_word([3,2,1]) # optional - sage.combinat sage.groups sage: [x.reduced_word() for x in w.weak_covers()] # optional - sage.combinat sage.groups [[3, 2]]
To obtain instead elements that cover self, set
positive=True
:sage: [x.reduced_word() for x in w.weak_covers(positive=True)] # optional - sage.combinat sage.groups [[3, 1, 2, 1], [2, 3, 2, 1]]
To obtain covers for left weak order, set the option side to ‘left’:
sage: [x.reduced_word() for x in w.weak_covers(side='left')] # optional - sage.combinat sage.groups [[2, 1]] sage: w = W.from_reduced_word([3,2,3,1]) # optional - sage.combinat sage.groups sage: [x.reduced_word() for x in w.weak_covers()] # optional - sage.combinat sage.groups [[2, 3, 2], [3, 2, 1]] sage: [x.reduced_word() for x in w.weak_covers(side='left')] # optional - sage.combinat sage.groups [[3, 2, 1], [2, 3, 1]]
Covers w.r.t. a parabolic subgroup are obtained with the option
index_set
:sage: [x.reduced_word() for x in w.weak_covers(index_set=[1,2])] # optional - sage.combinat sage.groups [[2, 3, 2]]
- weak_le(other, side='right')#
Comparison in weak order.
INPUT:
other – an element of the same Coxeter group
side – ‘left’ or ‘right’ (default: ‘right’)
OUTPUT: a boolean
This returns whether
self
<=other
in left (resp. right) weak order, that is if ‘v’ can be obtained from ‘v’ by length increasing multiplication by simple reflections on the left (resp. right).EXAMPLES:
sage: W = WeylGroup(["A", 3]) # optional - sage.combinat sage.groups sage: u = W.from_reduced_word([1,2]) # optional - sage.combinat sage.groups sage: v = W.from_reduced_word([1,2,3,2]) # optional - sage.combinat sage.groups sage: u.weak_le(u) # optional - sage.combinat sage.groups True sage: u.weak_le(v) # optional - sage.combinat sage.groups True sage: v.weak_le(u) # optional - sage.combinat sage.groups False sage: v.weak_le(v) # optional - sage.combinat sage.groups True
Comparison for left weak order is achieved with the option
side
:sage: u.weak_le(v, side='left') # optional - sage.combinat sage.groups False
The implementation uses the equivalent condition that any reduced word for \(u\) is a right (resp. left) prefix of some reduced word for \(v\).
Complexity: \(O(l * c)\), where \(l\) is the minimum of the lengths of \(u\) and of \(v\), and \(c\) is the cost of the low level methods
first_descent()
,has_descent()
,apply_simple_reflection()
), etc. Those are typically \(O(n)\), where \(n\) is the rank of the Coxeter group.We now run consistency tests with permutations:
sage: W = WeylGroup(["A", 3]) # optional - sage.combinat sage.groups sage: P4 = Permutations(4) # optional - sage.combinat sage.groups sage: def P4toW(w): return W.from_reduced_word(w.reduced_word()) # optional - sage.combinat sage.groups sage: for u in P4: # long time (5s on sage.math, 2011) # optional - sage.combinat sage.groups ....: for v in P4: ....: assert u.permutohedron_lequal(v) == P4toW(u).weak_le(P4toW(v)) ....: assert u.permutohedron_lequal(v, side='left') == P4toW(u).weak_le(P4toW(v), side='left')
- Finite#
alias of
FiniteCoxeterGroups
- class ParentMethods#
Bases:
object
- braid_group_as_finitely_presented_group()#
Return the associated braid group.
EXAMPLES:
sage: W = CoxeterGroup(['A', 2]) # optional - sage.combinat sage.groups sage: W.braid_group_as_finitely_presented_group() # optional - sage.combinat sage.groups Finitely presented group < S1, S2 | S1*S2*S1*S2^-1*S1^-1*S2^-1 > sage: W = WeylGroup(['B', 2]) # optional - sage.combinat sage.groups sage: W.braid_group_as_finitely_presented_group() # optional - sage.combinat sage.groups Finitely presented group < S1, S2 | (S1*S2)^2*(S1^-1*S2^-1)^2 > sage: W = ReflectionGroup(['B',3], index_set=["AA","BB","5"]) # optional - gap3 sage: W.braid_group_as_finitely_presented_group() # optional - gap3 Finitely presented group < SAA, SBB, S5 | (SAA*SBB)^2*(SAA^-1*SBB^-1)^2, SAA*S5*SAA^-1*S5^-1, SBB*S5*SBB*S5^-1*SBB^-1*S5^-1 >
- braid_orbit(word)#
Return the braid orbit of a word
word
of indices.The input word does not need to be a reduced expression of an element.
INPUT:
word
: a list (or iterable) of indices inself.index_set()
OUTPUT:
a list of all lists that can be obtained from
word
by replacements of braid relationsSee
braid_relations()
for the definition of braid relations.EXAMPLES:
sage: W = CoxeterGroups().example() sage: s = W.simple_reflections() sage: w = s[0] * s[1] * s[2] * s[1] sage: word = w.reduced_word(); word [0, 1, 2, 1] sage: sorted(W.braid_orbit(word)) # optional - sage.combinat sage.groups [[0, 1, 2, 1], [0, 2, 1, 2], [2, 0, 1, 2]] sage: sorted(W.braid_orbit([2,1,1,2,1])) # optional - sage.combinat sage.groups [[1, 2, 1, 1, 2], [2, 1, 1, 2, 1], [2, 1, 2, 1, 2], [2, 2, 1, 2, 2]] sage: W = ReflectionGroup(['A',3], index_set=["AA","BB","5"]) # optional - gap3 sage: w = W.long_element() # optional - gap3 sage: W.braid_orbit(w.reduced_word()) # optional - gap3 [['BB', '5', 'AA', 'BB', '5', 'AA'], ['5', 'BB', '5', 'AA', 'BB', '5'], ['BB', 'AA', 'BB', '5', 'BB', 'AA'], ['AA', '5', 'BB', 'AA', '5', 'BB'], ['5', 'AA', 'BB', 'AA', '5', 'BB'], ['AA', 'BB', '5', 'AA', 'BB', 'AA'], ['AA', 'BB', 'AA', '5', 'BB', 'AA'], ['AA', 'BB', '5', 'BB', 'AA', 'BB'], ['BB', 'AA', '5', 'BB', 'AA', '5'], ['BB', '5', 'AA', 'BB', 'AA', '5'], ['AA', '5', 'BB', '5', 'AA', 'BB'], ['5', 'BB', 'AA', '5', 'BB', '5'], ['5', 'BB', 'AA', 'BB', '5', 'BB'], ['5', 'AA', 'BB', '5', 'AA', 'BB'], ['BB', '5', 'BB', 'AA', 'BB', '5'], ['BB', 'AA', '5', 'BB', '5', 'AA']]
Todo
The result should be full featured finite enumerated set (e.g., counting can be done much faster than iterating).
See also
- braid_orbit_iter(word)#
Iterate over the braid orbit of a word
word
of indices.The input word does not need to be a reduced expression of an element.
INPUT:
word
– a list (or iterable) of indices inself.index_set()
OUTPUT:
all lists that can be obtained from
word
by replacements of braid relationsEXAMPLES:
sage: W = CoxeterGroups().example() sage: sorted(W.braid_orbit_iter([0, 1, 2, 1])) # optional - sage.combinat sage.groups [[0, 1, 2, 1], [0, 2, 1, 2], [2, 0, 1, 2]]
- braid_relations()#
Return the braid relations of
self
as a list of reduced words of the braid relations.EXAMPLES:
sage: W = WeylGroup(["A", 2]) # optional - sage.combinat sage.groups sage: W.braid_relations() # optional - sage.combinat sage.groups [[[1, 2, 1], [2, 1, 2]]] sage: W = WeylGroup(["B", 3]) # optional - sage.combinat sage.groups sage: W.braid_relations() # optional - sage.combinat sage.groups [[[1, 2, 1], [2, 1, 2]], [[1, 3], [3, 1]], [[2, 3, 2, 3], [3, 2, 3, 2]]]
- bruhat_graph(x=None, y=None, edge_labels=False)#
Return the Bruhat graph as a directed graph, with an edge \(u \to v\) if and only if \(u < v\) in the Bruhat order, and \(u = r \cdot v\).
The Bruhat graph \(\Gamma(x,y)\), defined if \(x \leq y\) in the Bruhat order, has as its vertices the Bruhat interval \(\{ t | x \leq t \leq y \}\), and as its edges are the pairs \((u, v)\) such that \(u = r \cdot v\) where \(r\) is a reflection, that is, a conjugate of a simple reflection.
REFERENCES:
Carrell, The Bruhat graph of a Coxeter group, a conjecture of Deodhar, and rational smoothness of Schubert varieties. Algebraic groups and their generalizations: classical methods (University Park, PA, 1991), 53–61, Proc. Sympos. Pure Math., 56, Part 1, Amer. Math. Soc., Providence, RI, 1994.
EXAMPLES:
sage: W = CoxeterGroup(['H', 3]) # optional - sage.combinat sage.groups sage.graphs sage: G = W.bruhat_graph(); G # optional - sage.combinat sage.groups sage.graphs Digraph on 120 vertices sage: W = CoxeterGroup(['A', 2, 1]) # optional - sage.combinat sage.groups sage.graphs sage: s1, s2, s3 = W.simple_reflections() # optional - sage.combinat sage.groups sage.graphs sage: W.bruhat_graph(s1, s1*s3*s2*s3) # optional - sage.combinat sage.groups sage.graphs Digraph on 6 vertices sage: W.bruhat_graph(s1, s3*s2*s3) # optional - sage.combinat sage.groups sage.graphs Digraph on 0 vertices sage: W = WeylGroup("A3", prefix="s") # optional - sage.combinat sage.groups sage.graphs sage: s1, s2, s3 = W.simple_reflections() # optional - sage.combinat sage.groups sage.graphs sage: G = W.bruhat_graph(s1*s3, s1*s2*s3*s2*s1); G # optional - sage.combinat sage.groups sage.graphs Digraph on 10 vertices
Check that the graph has the correct number of edges (see github issue #17744):
sage: len(G.edges(sort=False)) # optional - sage.combinat sage.groups sage.graphs 16
- bruhat_interval(x, y)#
Return the list of
t
such thatx <= t <= y
.EXAMPLES:
sage: W = WeylGroup("A3", prefix="s") # optional - sage.combinat sage.groups sage: s1, s2, s3 = W.simple_reflections() # optional - sage.combinat sage.groups sage: W.bruhat_interval(s2, s1*s3*s2*s1*s3) # optional - sage.combinat sage.groups [s1*s2*s3*s2*s1, s2*s3*s2*s1, s3*s1*s2*s1, s1*s2*s3*s1, s1*s2*s3*s2, s3*s2*s1, s2*s3*s1, s2*s3*s2, s1*s2*s1, s3*s1*s2, s1*s2*s3, s2*s1, s3*s2, s2*s3, s1*s2, s2] sage: W = WeylGroup(['A', 2, 1], prefix="s") # optional - sage.combinat sage.groups sage: s0, s1, s2 = W.simple_reflections() # optional - sage.combinat sage.groups sage: W.bruhat_interval(1, s0*s1*s2) # optional - sage.combinat sage.groups [s0*s1*s2, s1*s2, s0*s2, s0*s1, s2, s1, s0, 1]
- bruhat_interval_poset(x, y, facade=False)#
Return the poset of the Bruhat interval between
x
andy
in Bruhat order.EXAMPLES:
sage: W = WeylGroup("A3", prefix="s") # optional - sage.combinat sage.groups sage: s1, s2, s3 = W.simple_reflections() # optional - sage.combinat sage.groups sage: W.bruhat_interval_poset(s2, s1*s3*s2*s1*s3) # optional - sage.combinat sage.groups Finite poset containing 16 elements sage: W = WeylGroup(['A', 2, 1], prefix="s") # optional - sage.combinat sage.groups sage: s0, s1, s2 = W.simple_reflections() # optional - sage.combinat sage.groups sage: W.bruhat_interval_poset(1, s0*s1*s2) # optional - sage.combinat sage.groups Finite poset containing 8 elements
- canonical_representation()#
Return the canonical faithful representation of
self
.EXAMPLES:
sage: W = WeylGroup("A3") # optional - sage.combinat sage.groups sage: W.canonical_representation() # optional - sage.combinat sage.groups Finite Coxeter group over Integer Ring with Coxeter matrix: [1 3 2] [3 1 3] [2 3 1]
- coxeter_diagram()#
Return the Coxeter diagram of
self
.EXAMPLES:
sage: W = CoxeterGroup(['H', 3], implementation="reflection") # optional - sage.combinat sage.groups sage: G = W.coxeter_diagram(); G # optional - sage.combinat sage.groups sage.graphs Graph on 3 vertices sage: G.edges(sort=True) # optional - sage.combinat sage.groups sage.graphs [(1, 2, 3), (2, 3, 5)] sage: CoxeterGroup(G) is W # optional - sage.combinat sage.groups sage.graphs True sage: G = Graph([(0, 1, 3), (1, 2, oo)]) # optional - sage.combinat sage.groups sage.graphs sage: W = CoxeterGroup(G) # optional - sage.combinat sage.groups sage.graphs sage: W.coxeter_diagram() == G # optional - sage.combinat sage.groups sage.graphs True sage: CoxeterGroup(W.coxeter_diagram()) is W # optional - sage.combinat sage.groups sage.graphs True
- coxeter_element()#
Return a Coxeter element.
The result is the product of the simple reflections, in some order.
Note
This implementation is shared with well generated complex reflection groups. It would be nicer to put it in some joint super category; however, in the current state of the art, there is none where it is clear that this is the right construction for obtaining a Coxeter element.
In this context, this is an element having a regular eigenvector (a vector not contained in any reflection hyperplane of
self
).EXAMPLES:
sage: CoxeterGroup(['A', 4]).coxeter_element().reduced_word() # optional - sage.combinat sage.groups [1, 2, 3, 4] sage: CoxeterGroup(['B', 4]).coxeter_element().reduced_word() # optional - sage.combinat sage.groups [1, 2, 3, 4] sage: CoxeterGroup(['D', 4]).coxeter_element().reduced_word() # optional - sage.combinat sage.groups [1, 2, 4, 3] sage: CoxeterGroup(['F', 4]).coxeter_element().reduced_word() # optional - sage.combinat sage.groups [1, 2, 3, 4] sage: CoxeterGroup(['E', 8]).coxeter_element().reduced_word() # optional - sage.combinat sage.groups [1, 3, 2, 4, 5, 6, 7, 8] sage: CoxeterGroup(['H', 3]).coxeter_element().reduced_word() # optional - sage.combinat sage.groups [1, 2, 3]
This method is also used for well generated finite complex reflection groups:
sage: W = ReflectionGroup((1,1,4)) # optional - gap3 sage: W.coxeter_element().reduced_word() # optional - gap3 [1, 2, 3] sage: W = ReflectionGroup((2,1,4)) # optional - gap3 sage: W.coxeter_element().reduced_word() # optional - gap3 [1, 2, 3, 4] sage: W = ReflectionGroup((4,1,4)) # optional - gap3 sage: W.coxeter_element().reduced_word() # optional - gap3 [1, 2, 3, 4] sage: W = ReflectionGroup((4,4,4)) # optional - gap3 sage: W.coxeter_element().reduced_word() # optional - gap3 [1, 2, 3, 4]
- coxeter_matrix()#
Return the Coxeter matrix associated to
self
.EXAMPLES:
sage: G = WeylGroup(['A', 3]) # optional - sage.combinat sage.groups sage: G.coxeter_matrix() # optional - sage.combinat sage.groups [1 3 2] [3 1 3] [2 3 1]
- coxeter_type()#
Return the Coxeter type of
self
.EXAMPLES:
sage: W = CoxeterGroup(['H', 3]) # optional - sage.combinat sage.groups sage: W.coxeter_type() # optional - sage.combinat sage.groups Coxeter type of ['H', 3]
- demazure_product(Q)#
Return the Demazure product of the list
Q
inself
.INPUT:
Q
is a list of elements from the index set ofself
.
This returns the Coxeter group element that represents the composition of 0-Hecke or Demazure operators.
See
CoxeterGroups.ParentMethods.simple_projections()
.EXAMPLES:
sage: W = WeylGroup(['A', 2]) # optional - sage.combinat sage.groups sage: w = W.demazure_product([2,2,1]) # optional - sage.combinat sage.groups sage: w.reduced_word() # optional - sage.combinat sage.groups [2, 1] sage: w = W.demazure_product([2,1,2,1,2]) # optional - sage.combinat sage.groups sage: w.reduced_word() # optional - sage.combinat sage.groups [1, 2, 1] sage: W = WeylGroup(['B', 2]) # optional - sage.combinat sage.groups sage: w = W.demazure_product([2,1,2,1,2]) # optional - sage.combinat sage.groups sage: w.reduced_word() # optional - sage.combinat sage.groups [2, 1, 2, 1]
- elements_of_length(n)#
Return all elements of length \(n\).
EXAMPLES:
sage: A = AffinePermutationGroup(['A', 2, 1]) # optional - sage.combinat sage.groups sage: [len(list(A.elements_of_length(i))) for i in [0..5]] # optional - sage.combinat sage.groups [1, 3, 6, 9, 12, 15] sage: W = CoxeterGroup(['H', 3]) # optional - sage.combinat sage.groups sage: [len(list(W.elements_of_length(i))) for i in range(4)] # optional - sage.combinat sage.groups [1, 3, 5, 7] sage: W = CoxeterGroup(['A', 2]) # optional - sage.combinat sage.groups sage: [len(list(W.elements_of_length(i))) for i in range(6)] # optional - sage.combinat sage.groups [1, 2, 2, 1, 0, 0]
- fully_commutative_elements()#
Return the set of fully commutative elements in this Coxeter group.
See also
EXAMPLES:
sage: CoxeterGroup(['A', 3]).fully_commutative_elements() # optional - sage.combinat sage.groups Fully commutative elements of Finite Coxeter group over Integer Ring with Coxeter matrix: [1 3 2] [3 1 3] [2 3 1]
- grassmannian_elements(side='right')#
Return the left or right Grassmannian elements of
self
as an enumerated set.INPUT:
side
– (default:"right"
)"left"
or"right"
EXAMPLES:
sage: S = CoxeterGroups().example() sage: G = S.grassmannian_elements() sage: G.cardinality() 12 sage: G.list() [(0, 1, 2, 3), (1, 0, 2, 3), (0, 2, 1, 3), (0, 1, 3, 2), (2, 0, 1, 3), (1, 2, 0, 3), (0, 3, 1, 2), (0, 2, 3, 1), (3, 0, 1, 2), (1, 3, 0, 2), (1, 2, 3, 0), (2, 3, 0, 1)] sage: sorted(tuple(w.descents()) for w in G) [(), (0,), (0,), (0,), (1,), (1,), (1,), (1,), (1,), (2,), (2,), (2,)] sage: G = S.grassmannian_elements(side = "left") sage: G.cardinality() 12 sage: sorted(tuple(w.descents(side = "left")) for w in G) [(), (0,), (0,), (0,), (1,), (1,), (1,), (1,), (1,), (2,), (2,), (2,)]
- index_set()#
Return the index set of
self
.EXAMPLES:
sage: W = CoxeterGroup([[1,3],[3,1]]) # optional - sage.combinat sage.groups sage: W.index_set() # optional - sage.combinat sage.groups (1, 2) sage: W = CoxeterGroup([[1,3],[3,1]], index_set=['x', 'y']) # optional - sage.combinat sage.groups sage: W.index_set() # optional - sage.combinat sage.groups ('x', 'y') sage: W = CoxeterGroup(['H', 3]) # optional - sage.combinat sage.groups sage: W.index_set() # optional - sage.combinat sage.groups (1, 2, 3)
- kazhdan_lusztig_cells(side='left')#
Compute the left, right, or two-sided Kazhdan-Lusztig cells of
self
ifself
is finite.The cells are computed by using
kazhdan_lusztig_cell()
.As detailed there, installation of the optional package
coxeter3
is recommended (though not required) before using this function as it speeds up the computation.INPUT:
side
– (default:'left'
) either'left'
,'right'
, or'two-sided'
EXAMPLES:
We compute the right cells in the Coxeter group of type \(A_2\) below. Note that each Coxeter group may be created with multiple implementations, namely, ‘reflection’ (default), ‘permutation’, ‘matrix’, or ‘coxeter3’. The choice of implementation affects the representation of elements in the output cells but not the method used for the cell computation:
sage: W = CoxeterGroup('A2') # optional - sage.combinat sage.groups sage: KL_cells = W.kazhdan_lusztig_cells(side='right') # optional - sage.combinat sage.groups sage: set([tuple(sorted(C, key=lambda w: w.reduced_word())) # optional - sage.combinat sage.groups ....: for C in KL_cells]) {( [-1 1] [ 0 -1] [ 0 1], [ 1 -1] ), ( [ 0 -1] [-1 0] ), ( [1 0] [0 1] ), ( [ 1 0] [-1 1] [ 1 -1], [-1 0] )} sage: len(KL_cells) # optional - sage.combinat sage.groups 4 sage: W = CoxeterGroup('A2', implementation='permutation') # optional - sage.combinat sage.groups sage: len(W.kazhdan_lusztig_cells(side='right')) # optional - sage.combinat sage.groups 4
We compute the left cells in the Coxeter group of type \(A_3\) below. If the optional package
coxeter3
is installed, it runs in the background even if the group is not created with the'coxeter3'
implementation:sage: W = CoxeterGroup('A3', implementation='coxeter3') # optional - coxeter3 sage: KL_cells = W.kazhdan_lusztig_cells() # optional - coxeter3 sage: set([tuple(sorted(C)) for C in KL_cells]) # optional - coxeter3 {([],), ([1], [2, 1], [3, 2, 1]), ([1, 2], [2], [3, 2]), ([1, 2, 1], [1, 3, 2, 1], [2, 1, 3, 2, 1]), ([1, 2, 1, 3], [1, 2, 3, 2, 1], [2, 3, 2, 1]), ([1, 2, 1, 3, 2], [1, 2, 3, 2], [2, 3, 2]), ([1, 2, 1, 3, 2, 1],), ([1, 2, 3], [2, 3], [3]), ([1, 3], [2, 1, 3]), ([1, 3, 2], [2, 1, 3, 2])} sage: len(KL_cells) # optional - coxeter3 10 sage: W = CoxeterGroup('A3', implementation='permutation') # optional - coxeter3 sage: len(W.kazhdan_lusztig_cells()) # optional - coxeter3 10
Computing the two sided cells in \(B_3\):
sage: W = CoxeterGroup('B3', implementation='coxeter3') # optional - coxeter3 sage: b3_cells = W.kazhdan_lusztig_cells('two-sided') # optional - coxeter3 sage: len(b3_cells) # optional - coxeter3 6 sage: set([tuple(sorted(C)) # optional - coxeter3 ....: for C in W.kazhdan_lusztig_cells()]) {([],), ([1], [1, 2, 3, 2, 1], [2, 1], [2, 3, 2, 1], [3, 2, 1]), ([1, 2], [1, 2, 3, 2], [2], [2, 3, 2], [3, 2]), ([1, 2, 3], [2, 3], [3], [3, 2, 3]), ([2, 1, 2], [2, 3, 2, 1, 2], [3, 2, 1, 2]), ([2, 1, 2, 3], [2, 3, 2, 1, 2, 3], [3, 2, 1, 2, 3]), ([2, 1, 2, 3, 2], [2, 3, 2, 1, 2, 3, 2], [3, 2, 1, 2, 3, 2]), ([2, 1, 2, 3, 2, 1], [2, 3, 2, 1, 2, 3, 2, 1], [3, 2, 1, 2, 3, 2, 1], [3, 2, 3, 2, 1, 2]), ([2, 3, 1], [3, 1], [3, 2, 3, 1]), ([2, 3, 1, 2], [3, 1, 2], [3, 2, 3, 1, 2]), ([2, 3, 1, 2, 3], [3, 1, 2, 3], [3, 2, 3, 1, 2, 3]), ([2, 3, 1, 2, 3, 2], [3, 1, 2, 3, 2], [3, 2, 3, 1, 2, 3, 2], [3, 2, 3, 2], [3, 2, 3, 2, 1, 2, 3, 2]), ([2, 3, 1, 2, 3, 2, 1], [3, 1, 2, 3, 2, 1], [3, 2, 3, 1, 2, 3, 2, 1], [3, 2, 3, 2, 1], [3, 2, 3, 2, 1, 2, 3]), ([3, 2, 3, 2, 1, 2, 3, 2, 1],)}
- random_element_of_length(n)#
Return a random element of length
n
inself
.Starts at the identity, then chooses an upper cover at random.
Not very uniform: actually constructs a uniformly random reduced word of length \(n\). Thus we most likely get elements with lots of reduced words!
EXAMPLES:
sage: A = AffinePermutationGroup(['A', 7, 1]) # optional - sage.combinat sage.groups sage: p = A.random_element_of_length(10) # optional - sage.combinat sage.groups sage: p in A # optional - sage.combinat sage.groups True sage: p.length() == 10 # optional - sage.combinat sage.groups True sage: W = CoxeterGroup(['A', 4]) # optional - sage.combinat sage.groups sage: p = W.random_element_of_length(5) # optional - sage.combinat sage.groups sage: p in W # optional - sage.combinat sage.groups True sage: p.length() == 5 # optional - sage.combinat sage.groups True
- sign_representation(base_ring=None, side='twosided')#
Return the sign representation of
self
overbase_ring
.INPUT:
base_ring
– (optional) the base ring; the default is \(\ZZ\)side
– ignored
EXAMPLES:
sage: W = WeylGroup(["A", 1, 1]) # optional - sage.combinat sage.groups sage: W.sign_representation() # optional - sage.combinat sage.groups Sign representation of Weyl Group of type ['A', 1, 1] (as a matrix group acting on the root space) over Integer Ring
- simple_projection(i, side='right', length_increasing=True)#
Return the simple projection \(\pi_i\) (or \(\overline\pi_i\) if
length_increasing
isFalse
).INPUT:
i
- an element of the index set ofself
See
simple_projections()
for the options and for the definition of the simple projections.EXAMPLES:
sage: W = CoxeterGroups().example() sage: W The symmetric group on {0, ..., 3} sage: s = W.simple_reflections() sage: sigma = W.an_element() sage: sigma (1, 2, 3, 0) sage: u0 = W.simple_projection(0) sage: d0 = W.simple_projection(0, length_increasing=False) sage: sigma.length() 3 sage: pi=sigma*s[0] sage: pi.length() 4 sage: u0(sigma) (2, 1, 3, 0) sage: pi (2, 1, 3, 0) sage: u0(pi) (2, 1, 3, 0) sage: d0(sigma) (1, 2, 3, 0) sage: d0(pi) (1, 2, 3, 0)
- simple_projections(side='right', length_increasing=True)#
Return the family of simple projections, also known as 0-Hecke or Demazure operators.
INPUT:
self
– a Coxeter group \(W\)side
– ‘left’ or ‘right’ (default: ‘right’)length_increasing
– a boolean (default:True
) specifying whether the operator increases or decreases length
This returns the simple projections of \(W\), as a family.
To each simple reflection \(s_i\) of \(W\), corresponds a simple projection \(\pi_i\) from \(W\) to \(W\) defined by:
\(\pi_i(w) = w s_i\) if \(i\) is not a descent of \(w\) \(\pi_i(w) = w\) otherwise.
The simple projections \((\pi_i)_{i\in I}\) move elements down the right permutohedron, toward the maximal element. They satisfy the same braid relations as the simple reflections, but are idempotents \(\pi_i^2=\pi\) not involutions \(s_i^2 = 1\). As such, the simple projections generate the \(0\)-Hecke monoid.
By symmetry, one can also define the projections \((\overline\pi_i)_{i\in I}\) (when the option
length_increasing
is False):\(\overline\pi_i(w) = w s_i\) if \(i\) is a descent of \(w\) \(\overline\pi_i(w) = w\) otherwise.
as well as the analogues acting on the left (when the option
side
is ‘left’).EXAMPLES:
sage: W = CoxeterGroups().example(); W The symmetric group on {0, ..., 3} sage: s = W.simple_reflections() sage: sigma = W.an_element(); sigma (1, 2, 3, 0) sage: pi = W.simple_projections(); pi Finite family {0: <function ...<lambda> at ...>, 1: <function ...<lambda> at ...>, 2: <function ...<lambda> ...>} sage: pi[1](sigma) (1, 3, 2, 0) sage: W.simple_projection(1)(sigma) (1, 3, 2, 0)
- standard_coxeter_elements()#
Return all standard Coxeter elements in
self
.This is the set of all elements in self obtained from any product of the simple reflections in
self
.Note
self
is assumed to be well-generated.This works even beyond real reflection groups, but the conjugacy class is not unique and we only obtain one such class.
EXAMPLES:
sage: W = ReflectionGroup(4) # optional - gap3 sage: sorted(W.standard_coxeter_elements()) # optional - gap3 [(1,7,6,12,23,20)(2,8,17,24,9,5)(3,16,10,19,15,21)(4,14,11,22,18,13), (1,10,4,12,21,22)(2,11,19,24,13,3)(5,15,7,17,16,23)(6,18,8,20,14,9)]
- weak_order_ideal(predicate, side='right', category=None)#
Return a weak order ideal defined by a predicate
INPUT:
predicate
: a predicate on the elements ofself
defining an weak order ideal inself
side
: “left” or “right” (default: “right”)
OUTPUT: an enumerated set
EXAMPLES:
sage: D6 = FiniteCoxeterGroups().example(5) sage: I = D6.weak_order_ideal(predicate=lambda w: w.length() <= 3) sage: I.cardinality() 7 sage: list(I) [(), (1,), (2,), (1, 2), (2, 1), (1, 2, 1), (2, 1, 2)]
We now consider an infinite Coxeter group:
sage: W = WeylGroup(["A",1,1]) sage: I = W.weak_order_ideal(predicate = lambda w: w.length() <= 2) sage: list(iter(I)) [ [1 0] [-1 2] [ 1 0] [ 3 -2] [-1 2] [0 1], [ 0 1], [ 2 -1], [ 2 -1], [-2 3] ]
Even when the result is finite, some features of
FiniteEnumeratedSets
are not available:sage: I.cardinality() # todo: not implemented 5 sage: list(I) # todo: not implemented
unless this finiteness is explicitly specified:
sage: I = W.weak_order_ideal(predicate = lambda w: w.length() <= 2, ....: category = FiniteEnumeratedSets()) sage: I.cardinality() 5 sage: list(I) [ [1 0] [-1 2] [ 1 0] [ 3 -2] [-1 2] [0 1], [ 0 1], [ 2 -1], [ 2 -1], [-2 3] ]
Background
The weak order is returned as a
RecursivelyEnumeratedSet_forest
. This is achieved by assigning to each element \(u1\) of the ideal a single ancestor \(u=u1 s_i\), where \(i\) is the smallest descent of \(u\).This allows for iterating through the elements in roughly Constant Amortized Time and constant memory (taking the operations and size of the generated objects as constants).
- additional_structure()#
Return
None
.Indeed, all the structure Coxeter groups have in addition to groups (simple reflections, …) is already defined in the super category.
See also
EXAMPLES:
sage: CoxeterGroups().additional_structure()
- super_categories()#
EXAMPLES:
sage: CoxeterGroups().super_categories() [Category of generalized coxeter groups]