Coxeter Groups¶
-
class
sage.categories.coxeter_groups.
CoxeterGroups
(s=None)¶ Bases:
sage.categories.category_singleton.Category_singleton
The category of Coxeter groups.
A Coxeter group is a group
with a distinguished (finite) family of involutions
, called the simple reflections, subject to relations of the form
.
is the index set of
and
is the rank of
.
See Wikipedia article Coxeter_group for details.
EXAMPLES:
sage: C = CoxeterGroups(); C Category of coxeter groups sage: C.super_categories() [Category of finitely generated 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() The 5-th dihedral group of order 10 sage: FiniteWeylGroups().example() The symmetric group on {0, ..., 3} sage: WeylGroup(["B", 3]) Weyl Group of type ['B', 3] (as a matrix group acting on the ambient space)
Those will eventually be also in this category:
sage: SymmetricGroup(4) Symmetric group of order 4! as a permutation group sage: DihedralGroup(5) Dihedral group of order 10 as a permutation group
Todo
add a demo of usual computations on Coxeter groups.
See also
WeylGroups
,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
TESTS:
sage: W = CoxeterGroups().example(); TestSuite(W).run(verbose = "True") running ._test_an_element() . . . pass running ._test_associativity() . . . pass running ._test_cardinality() . . . pass running ._test_category() . . . pass running ._test_elements() . . . Running the test suite of self.an_element() running ._test_category() . . . pass running ._test_eq() . . . pass running ._test_not_implemented_methods() . . . pass running ._test_pickling() . . . pass pass running ._test_elements_eq_reflexive() . . . pass running ._test_elements_eq_symmetric() . . . pass running ._test_elements_eq_transitive() . . . pass running ._test_elements_neq() . . . pass running ._test_enumerated_set_contains() . . . pass running ._test_enumerated_set_iter_cardinality() . . . pass running ._test_enumerated_set_iter_list() . . . pass running ._test_eq() . . . pass running ._test_has_descent() . . . pass running ._test_inverse() . . . pass running ._test_not_implemented_methods() . . . pass running ._test_one() . . . pass running ._test_pickling() . . . pass running ._test_prod() . . . pass running ._test_reduced_word() . . . pass running ._test_simple_projections() . . . pass running ._test_some_elements() . . . pass
-
Algebras
¶ alias of
CoxeterGroupAlgebras
-
class
ElementMethods
¶ -
absolute_le
(other)¶ Return whether
self
is smaller thanother
in the absolute order.A general reflection is an element of the form
, where
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]) sage: s = W.simple_reflections() sage: w0 = s[1] sage: w1 = s[1]*s[2]*s[3] sage: w0.absolute_le(w1) True sage: w1.absolute_le(w0) False sage: w1.absolute_le(w1) 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.
See also
EXAMPLES:
sage: W = WeylGroup(["A", 3]) sage: s = W.simple_reflections() sage: (s[1]*s[2]*s[3]).absolute_length() 3
-
apply_conjugation_by_simple_reflection
(i)¶ Conjugates
self
by thei
-th simple reflection.EXAMPLES:
sage: W = WeylGroup(['A',3]) sage: w = W.from_reduced_word([3,1,2,1]) sage: w.apply_conjugation_by_simple_reflection(1).reduced_word() [3, 2]
-
apply_demazure_product
(element, side='right', length_increasing=True)¶ Returns 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") sage: v = W.from_reduced_word([1,2,3,4,3,1]) sage: v.apply_demazure_product([1,3,4,3,3]) s4*s1*s2*s3*s4*s3*s1 sage: v.apply_demazure_product([1,3,4,3],side='left') s3*s4*s1*s2*s3*s4*s2*s3*s1 sage: v.apply_demazure_product((1,3,4,3),side='left') s3*s4*s1*s2*s3*s4*s2*s3*s1 sage: v.apply_demazure_product(v) s2*s3*s4*s1*s2*s3*s4*s2*s3*s2*s1
-
apply_simple_projection
(i, side='right', length_increasing=True)¶ 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
Returns the result of the application of the simple projection
(resp.
) on
self
.See
CoxeterGroups.ParentMethods.simple_projections()
for the definition of the simple projections.EXAMPLE:
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") sage: v = W.from_reduced_word([1,2,3,4,3,1]) sage: v s1*s2*s3*s4*s3*s1 sage: v.apply_simple_projection(2) s1*s2*s3*s4*s3*s1*s2 sage: v.apply_simple_projection(2, side='left') s1*s2*s3*s4*s3*s1 sage: v.apply_simple_projection(1, length_increasing = False) s1*s2*s3*s4*s3
-
apply_simple_reflection
(i, side='right')¶ Returns
self
multiplied by the simple reflections[i]
INPUT:
i
– an element of the index setside
– “left” or “right” (default: “right”)
This default implementation simply calls
apply_simple_reflection_left()
orapply_simple_reflection_right()
.EXAMPLES:
sage: W=CoxeterGroups().example() sage: w = W.an_element(); w (1, 2, 3, 0) sage: w.apply_simple_reflection(0, side = "left") (0, 2, 3, 1) sage: w.apply_simple_reflection(1, side = "left") (2, 1, 3, 0) sage: w.apply_simple_reflection(2, side = "left") (1, 3, 2, 0) sage: w.apply_simple_reflection(0, side = "right") (2, 1, 3, 0) sage: w.apply_simple_reflection(1, side = "right") (1, 3, 2, 0) sage: w.apply_simple_reflection(2, side = "right") (1, 2, 0, 3)
By default,
side
is “right”:sage: w.apply_simple_reflection(0) (2, 1, 3, 0)
TESTS:
sage: w.apply_simple_reflection_right.__module__ 'sage.categories.coxeter_groups'
-
apply_simple_reflection_left
(i)¶ Returns
self
multiplied by the simple reflections[i]
on the leftThis low level method is used intensively. Coxeter groups are encouraged to override this straightforward implementation whenever a faster approach exists.
EXAMPLES:
sage: W=CoxeterGroups().example() sage: w = W.an_element(); w (1, 2, 3, 0) sage: w.apply_simple_reflection_left(0) (0, 2, 3, 1) sage: w.apply_simple_reflection_left(1) (2, 1, 3, 0) sage: w.apply_simple_reflection_left(2) (1, 3, 2, 0)
TESTS:
sage: w.apply_simple_reflection_left.__module__ 'sage.categories.coxeter_groups'
-
apply_simple_reflection_right
(i)¶ Returns
self
multiplied by the simple reflections[i]
on the rightThis low level method is used intensively. Coxeter groups are encouraged to override this straightforward implementation whenever a faster approach exists.
EXAMPLES:
sage: W=CoxeterGroups().example() sage: w = W.an_element(); w (1, 2, 3, 0) sage: w.apply_simple_reflection_right(0) (2, 1, 3, 0) sage: w.apply_simple_reflection_right(1) (1, 3, 2, 0) sage: w.apply_simple_reflection_right(2) (1, 2, 0, 3)
TESTS:
sage: w.apply_simple_reflection_right.__module__ 'sage.categories.coxeter_groups'
-
apply_simple_reflections
(word, side='right')¶ INPUT:
word
– A sequence of indices of Coxeter generatorsside
– Indicates multiplying from left or right
Returns the result of the (left/right) multiplication of word to self.
self
is not changed.EXAMPLES:
sage: W=CoxeterGroups().example() sage: w=W.an_element(); w (1, 2, 3, 0) sage: w.apply_simple_reflections([0,1]) (2, 3, 1, 0) sage: w (1, 2, 3, 0) sage: w.apply_simple_reflections([0,1],side='left') (0, 1, 3, 2)
-
binary_factorizations
(predicate=The constant function (...) -> True)¶ Returns the set of all the factorizations
such that
.
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
.
One can pass as optional argument a predicate p such that
implies
for any
left factor of
and
left factor of
. Then this returns only the factorizations
such
holds.
EXAMPLES:
We construct the set of all factorizations of the maximal element of the group:
sage: W = WeylGroup(['A',3]) sage: s = W.simple_reflections() sage: w0 = W.from_reduced_word([1,2,3,1,2,1]) sage: w0.binary_factorizations().cardinality() 24
The same number of factorizations, by bounded length:
sage: [w0.binary_factorizations(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() for i in [1,2,3]] [12, 12, 12] sage: w0.binary_factorizations(lambda u: False).cardinality() 0
TESTS:
sage: w0.binary_factorizations().category() Category of finite enumerated sets
-
bruhat_le
(other)¶ Bruhat comparison
INPUT:
- other - an element of the same Coxeter group
OUTPUT: a boolean
Returns whether
self
<=other
in the Bruhat order.EXAMPLES:
sage: W = WeylGroup(["A",3]) sage: u = W.from_reduced_word([1,2,1]) sage: v = W.from_reduced_word([1,2,3,2,1]) sage: u.bruhat_le(u) True sage: u.bruhat_le(v) True sage: v.bruhat_le(u) False sage: v.bruhat_le(v) True sage: s = W.simple_reflections() sage: s[1].bruhat_le(W.one()) 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 Mobius function for the Bruhat order. J. Algebraic Combin. 25 (2007), no. 2, 141–148, Proposition 1.1.Complexity:
, where
is the minimum of the lengths of
and of
, and
is the cost of the low level methods
first_descent()
,has_descent()
,apply_simple_reflection()
, etc. Those are typically, where
is the rank of the Coxeter group.
TESTS:
We now run consistency tests with permutations and
bruhat_lower_covers()
:sage: W = WeylGroup(["A",3]) sage: P4 = Permutations(4) sage: def P4toW(w): return W.from_reduced_word(w.reduced_word()) sage: for u in P4: ... for v in P4: ... assert u.bruhat_lequal(v) == P4toW(u).bruhat_le(P4toW(v)) sage: W = WeylGroup(["B",3]) sage: P = W.bruhat_poset() # This is built from bruhat_lower_covers sage: Q = Poset((W, attrcall("bruhat_le"))) # long time (10s) sage: all( u.bruhat_le(v) == P.is_lequal(u,v) for u in W for v in W ) # long time (7s) True sage: all( P.is_lequal(u,v) == Q.is_lequal(u,v) for u in W for v in W) # long time (9s) True
-
bruhat_lower_covers
()¶ Returns all elements that
self
covers in (strong) Bruhat order.If
w = self
has a descent at, then the elements that
covers are exactly
, where the
are elements that
covers that also do not have a descent at
.
EXAMPLES:
sage: W = WeylGroup(["A",3]) sage: w = W.from_reduced_word([3,2,3]) sage: print([v.reduced_word() for v in w.bruhat_lower_covers()]) [[3, 2], [2, 3]] sage: W = WeylGroup(["A",3]) sage: print([v.reduced_word() for v in W.simple_reflection(1).bruhat_lower_covers()]) [[]] sage: print([v.reduced_word() for v in W.one().bruhat_lower_covers()]) [] sage: W = WeylGroup(["B",4,1]) sage: w = W.from_reduced_word([0,2]) sage: print([v.reduced_word() for v in w.bruhat_lower_covers()]) [[2], [0]]
We now show how to construct the Bruhat poset:
sage: W = WeylGroup(["A",3]) sage: covers = tuple([u, v] for v in W for u in v.bruhat_lower_covers() ) sage: P = Poset((W, covers), cover_relations = True) sage: P.show()
Alternatively, one can just use:
sage: P = W.bruhat_poset()
The algorithm is taken from Stembridge’s ‘coxeter/weyl’ package for Maple.
-
bruhat_lower_covers_reflections
()¶ Returns 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") sage: w = W.from_reduced_word([3,1,2,1]) sage: w.bruhat_lower_covers_reflections() [(s1*s2*s1, s1*s2*s3*s2*s1), (s3*s2*s1, s2), (s3*s1*s2, s1)]
-
bruhat_upper_covers
()¶ Returns 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 allin the index set. Let
equal
self
. Ifhas no right descent
, then
is a cover; if
has a decent at
, then
is a cover of
where
is a cover of
.
EXAMPLES:
sage: W = WeylGroup(['A',3,1], prefix="s") sage: w = W.from_reduced_word([1,2,1]) sage: w.bruhat_upper_covers() [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]) sage: w = W.long_element() sage: w.bruhat_upper_covers() [] sage: W = WeylGroup(['A',3]) sage: w = W.from_reduced_word([1,2,1]) sage: S = [v for v in W if w in v.bruhat_lower_covers()] sage: C = w.bruhat_upper_covers() sage: set(S) == set(C) True
-
bruhat_upper_covers_reflections
()¶ Returns 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") sage: w = W.from_reduced_word([3,1,2,1]) sage: w.bruhat_upper_covers_reflections() [(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
-dimension real faithful essential representation, where
is the number of generators of the Coxeter group. Note that this is not always the most natural matrix representation, for instance in type
.
EXAMPLES:
sage: W = WeylGroup(["A", 3]) sage: s = W.simple_reflections() sage: (s[1]*s[2]*s[3]).canonical_matrix() [ 0 0 -1] [ 1 0 -1] [ 0 1 -1]
-
coset_representative
(index_set, side='right')¶ INPUT:
index_set
- a subset (or iterable) of the nodes of the Dynkin diagramside
- ‘left’ or ‘right’
Returns the unique shortest element of the Coxeter group
which is in the same left (resp. right) coset as
self
, with respect to the parabolic subgroup.
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')¶ Returns the set of reflections
t
such thatself
t
coversself
.If
side
is ‘left’,t
self
coversself
.EXAMPLES:
sage: W = WeylGroup(['A',4], prefix="s") sage: w = W.from_reduced_word([3,1,2,1]) sage: w.cover_reflections() [s3, s2*s3*s2, s4, s1*s2*s3*s4*s3*s2*s1] sage: w.cover_reflections(side = 'left') [s4, s2, s1*s2*s1, s3*s4*s3]
-
coxeter_sorting_word
(c)¶ Return the
c
-sorting word ofself
.For a Coxeter element
and an element
, the
-sorting word of
is the lexicographic minimal reduced expression of
in the infinite word
.
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)¶ Returns 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
w
in Bruhat order.OUTPUT:
Deodhar’s element
f(v,w)
is the unique element ofW'
such that, for allv'
andw'
inW'
,vv'
ww'
inW
if and only ifv'
f(v,w) * w'
inW'
where*
is the Demazure product.EXAMPLES:
sage: W = WeylGroup(['A',5],prefix="s") sage: v = W.from_reduced_word([5]) sage: w = W.from_reduced_word([4,5,2,3,1,2]) sage: v.deodhar_factor_element(w,[1,3,4]) s3*s1 sage: W=WeylGroup(['C',2]) sage: w=W.from_reduced_word([2,1]) sage: w.deodhar_factor_element(W.from_reduced_word([2]),[1]) 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] - Deodhar, A splitting criterion for the Bruhat orderings on Coxeter groups. Comm. Algebra, 15:1889-1894, 1987.
-
deodhar_lift_down
(w, index_set)¶ Letting
v = self
, given a Bruhat relationv W'
w W'
among cosets with respect to the subgroupW'
given by the Dynkin node subsetindex_set
, returns the Bruhat-maximum liftx
ofwW'
such thatv
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") sage: v = W.from_reduced_word([1,2,3,2]) sage: w = W.from_reduced_word([3,2]) sage: v.deodhar_lift_down(w, [3]) s2*s3*s2
-
deodhar_lift_up
(w, index_set)¶ Letting
v = self
, given a Bruhat relationv W'
w W'
among cosets with respect to the subgroupW'
given by the Dynkin node subsetindex_set
, returns the Bruhat-minimum liftx
ofwW'
such thatv
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
x
.EXAMPLES:
sage: W = WeylGroup(['A',3],prefix="s") sage: v = W.from_reduced_word([1,2,3]) sage: w = W.from_reduced_word([1,3,2]) sage: v.deodhar_lift_up(w, [3]) s1*s2*s3*s2
-
descents
(side='right', index_set=None, positive=False)¶ 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
)
Returns the descents of self, as a list of elements of the index_set.
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)¶ Returns the first left (resp. right) descent of self, as ane 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)¶ Returns 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)¶ Returns whether
is a left descent of self.
This default implementation uses that a left descent of
is a right descent of
.
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
TESTS:
sage: w.has_left_descent.__module__ 'sage.categories.coxeter_groups'
-
has_right_descent
(i)¶ Returns 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 sage: WeylGroup(['A',2]).long_element().has_right_descent(1) True
-
inverse
()¶ Returns the inverse of self
EXAMPLES:
sage: W=WeylGroup(['B',7]) sage: w=W.an_element() sage: u=w.inverse() sage: u==~w True sage: u*w==w*u True sage: u*w [1 0 0 0 0 0 0] [0 1 0 0 0 0 0] [0 0 1 0 0 0 0] [0 0 0 1 0 0 0] [0 0 0 0 1 0 0] [0 0 0 0 0 1 0] [0 0 0 0 0 0 1]
-
inversions_as_reflections
()¶ Returns the set of reflections
r
such thatself
r < self
.EXAMPLES:
sage: W = WeylGroup(['A',3], prefix="s") sage: w = W.from_reduced_word([3,1,2,1]) sage: w.inversions_as_reflections() [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
, an element
is
-sortable if its
-sorting word decomposes into a sequence of weakly decreasing subwords of
.
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]) sage: c = W.from_reduced_word([1,2,3]) sage: len([w for w in W if w.is_coxeter_sortable(c)]) # number of c-sortable elements in A_3 (Catalan number) 14
-
is_grassmannian
(side='right')¶ INPUT:
side
- “left” or “right” (default: “right”)
Tests whether
self
is Grassmannian, i.e. it has at most one descent on the right (resp. on the left).v 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
-
left_inversions_as_reflections
()¶ Returns the set of reflections
r
such thatr
self
<self
.EXAMPLES:
sage: W = WeylGroup(['A',3], prefix="s") sage: w = W.from_reduced_word([3,1,2,1]) sage: w.left_inversions_as_reflections() [s1, s3, s1*s2*s3*s2*s1, s2*s3*s2]
-
length
()¶ Returns the length of self, that 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: sum((x^w.length()) for w in W) - expand(prod(sum(x^i for i in range(j+1)) for j in range(4))) # This is scandalously slow!!! 0
SEE ALSO:
reduced_word()
TODO: Should use reduced_word_iterator (or reverse_iterator)
-
lower_cover_reflections
(side='right')¶ Returns the reflections
t
such thatself
coversself
t
.If
side
is ‘left’,self
coverst
self
.EXAMPLES:
sage: W = WeylGroup(['A',3],prefix="s") sage: w = W.from_reduced_word([3,1,2,1]) sage: w.lower_cover_reflections() [s1*s2*s3*s2*s1, s2, s1] sage: w.lower_cover_reflections(side = 'left') [s2*s3*s2, s3, s1]
-
lower_covers
(side='right', index_set=None)¶ Returns all elements that
self
covers in weak order.INPUT:
- side - ‘left’ or ‘right’ (default: ‘right’)
- index_set - a list of indices or None
OUTPUT: a list
EXAMPLES:
sage: W = WeylGroup(['A',3]) sage: w = W.from_reduced_word([3,2,1]) sage: [x.reduced_word() for x in w.lower_covers()] [[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')] [[2, 1]] sage: w = W.from_reduced_word([3,2,3,1]) sage: [x.reduced_word() for x in w.lower_covers()] [[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])] [[2, 3, 2]] sage: [x.reduced_word() for x in w.lower_covers(side='left')] [[3, 2, 1], [2, 3, 1]]
-
min_demazure_product_greater
(element)¶ Finds the unique Bruhat-minimum element
u
such thatv
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") sage: v = W.from_reduced_word([2,3,4,1,2]) sage: u = W.from_reduced_word([2,3,2,1]) sage: v.min_demazure_product_greater(u) s4*s2 sage: v.min_demazure_product_greater([2,3,2,1]) s4*s2 sage: v.min_demazure_product_greater((2,3,2,1)) s4*s2
-
reduced_word
()¶ Return a reduced word for
self
.This is a word
of minimal length such that
, where the
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
in a Coxeter group is the graph whose vertices are the reduced words for
(see
reduced_word()
for a definition of this term), and which has an-colored edge between two reduced words
and
whenever
and
differ by exactly one length-
braid move (with
).
This graph is always connected (a theorem due to Tits) and has no multiple edges.
EXAMPLES:
sage: W = WeylGroup(['A',3], prefix='s') sage: w0 = W.long_element() sage: G = w0.reduced_word_graph() sage: G.num_verts() 16 sage: len(w0.reduced_words()) 16 sage: G.num_edges() 18 sage: len([e for e in G.edges() if e[2] == 2]) 10 sage: len([e for e in G.edges() if e[2] == 3]) 8
TESTS:
sage: w1 = W.one() sage: G = w1.reduced_word_graph() sage: G.num_verts() 1 sage: G.num_edges() 0
-
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.EXAMPLES:
sage: W=CoxeterGroups().example() sage: s=W.simple_reflections() sage: w=s[0]*s[2] sage: w.reduced_words() [[2, 0], [0, 2]] sage: W=WeylGroup(['E',6]) sage: w=W.from_reduced_word([2,3,4,2]) sage: w.reduced_words() [[3, 2, 4, 2], [2, 3, 4, 2], [3, 4, 2, 4]]
TODO: the result should be full featured finite enumerated set (e.g. counting can be done much faster than iterating).
-
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)¶ Returns all elements that cover
self
in weak order.INPUT:
- side - ‘left’ or ‘right’ (default: ‘right’)
- index_set - a list of indices or None
OUTPUT: a list
EXAMPLES:
sage: W = WeylGroup(['A',3]) sage: w = W.from_reduced_word([2,3]) sage: [x.reduced_word() for x in w.upper_covers()] [[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')] [[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])] [[2, 3, 1]] sage: [x.reduced_word() for x in w.upper_covers(side = 'left', index_set = [1])] [[1, 2, 3]]
-
weak_covers
(side='right', index_set=None, positive=False)¶ Returns 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]) sage: w = W.from_reduced_word([3,2,1]) sage: [x.reduced_word() for x in w.weak_covers()] [[3, 2]]
To obtain instead elements that cover self, set
positive = True
:sage: [x.reduced_word() for x in w.weak_covers(positive = True)] [[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')] [[2, 1]] sage: w = W.from_reduced_word([3,2,3,1]) sage: [x.reduced_word() for x in w.weak_covers()] [[2, 3, 2], [3, 2, 1]] sage: [x.reduced_word() for x in w.weak_covers(side='left')] [[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])] [[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
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]) sage: u = W.from_reduced_word([1,2]) sage: v = W.from_reduced_word([1,2,3,2]) sage: u.weak_le(u) True sage: u.weak_le(v) True sage: v.weak_le(u) False sage: v.weak_le(v) True
Comparison for left weak order is achieved with the option
side
:sage: u.weak_le(v, side = 'left') False
The implementation uses the equivalent condition that any reduced word for
is a right (resp. left) prefix of some reduced word for
.
Complexity:
, where
is the minimum of the lengths of
and of
, and
is the cost of the low level methods
first_descent()
,has_descent()
,apply_simple_reflection()
. Those are typically, where
is the rank of the Coxeter group.
We now run consistency tests with permutations:
sage: W = WeylGroup(["A",3]) sage: P4 = Permutations(4) sage: def P4toW(w): return W.from_reduced_word(w.reduced_word()) sage: for u in P4: # long time (5s on sage.math, 2011) ... 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')
-
-
CoxeterGroups.
Finite
¶ alias of
FiniteCoxeterGroups
-
class
CoxeterGroups.
ParentMethods
¶ -
bruhat_interval
(x, y)¶ Returns the list of t such that x <= t <= y.
EXAMPLES:
sage: W = WeylGroup("A3", prefix="s") sage: [s1,s2,s3]=W.simple_reflections() sage: W.bruhat_interval(s2,s1*s3*s2*s1*s3) [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") sage: [s0,s1,s2]=W.simple_reflections() sage: W.bruhat_interval(1,s0*s1*s2) [s0*s1*s2, s1*s2, s0*s2, s0*s1, s2, s1, s0, 1]
-
canonical_representation
()¶ Return the canonical faithful representation of
self
.EXAMPLES:
sage: W = WeylGroup("A3") sage: W.canonical_representation() Finite Coxeter group over Universal Cyclotomic Field with Coxeter matrix: [1 3 2] [3 1 3] [2 3 1]
-
demazure_product
(Q)¶ Returns 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]) sage: w = W.demazure_product([2,2,1]) sage: w.reduced_word() [2, 1] sage: w = W.demazure_product([2,1,2,1,2]) sage: w.reduced_word() [1, 2, 1] sage: W = WeylGroup(['B',2]) sage: w = W.demazure_product([2,1,2,1,2]) sage: w.reduced_word() [2, 1, 2, 1]
-
elements_of_length
(n)¶ Return all elements of length
.
EXAMPLES:
sage: A = AffinePermutationGroup(['A',2,1]) sage: [len(list(A.elements_of_length(i))) for i in [0..5]] [1, 3, 6, 9, 12, 15] sage: W = CoxeterGroup(['H',3]) sage: [len(list(W.elements_of_length(i))) for i in range(4)] [1, 3, 5, 7] sage: W = CoxeterGroup(['A',2]) sage: [len(list(W.elements_of_length(i))) for i in range(6)] [1, 2, 2, 1, 0, 0]
-
from_reduced_word
(word)¶ INPUT:
word
- a list (or iterable) of elements ofself.index_set()
Returns the group element corresponding to the given word. Namely, if
word
is, then this returns the corresponding product of simple reflections
.
Note: the main use case is for constructing elements from reduced words, hence the name of this method. But actually the input word need not be reduced.
EXAMPLES:
sage: W = CoxeterGroups().example() sage: W The symmetric group on {0, ..., 3} sage: s = W.simple_reflections() sage: W.from_reduced_word([0,2,0,1]) (0, 3, 1, 2) sage: W.from_reduced_word((0,2,0,1)) (0, 3, 1, 2) sage: s[0]*s[2]*s[0]*s[1] (0, 3, 1, 2)
See also :meth:’._test_reduced_word’:
sage: W._test_reduced_word()
TESTS:
sage: W=WeylGroup(['E',6]) sage: W.from_reduced_word([2,3,4,2]) [ 0 1 0 0 0 0 0 0] [ 0 0 -1 0 0 0 0 0] [-1 0 0 0 0 0 0 0] [ 0 0 0 1 0 0 0 0] [ 0 0 0 0 1 0 0 0] [ 0 0 0 0 0 1 0 0] [ 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 0 0 1]
-
grassmannian_elements
(side='right')¶ INPUT:
side
: “left” or “right” (default: “right”)
Returns the left or right grassmanian elements of self, as an enumerated set
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), (2, 0, 1, 3), (3, 0, 1, 2), (0, 2, 1, 3), (1, 2, 0, 3), (0, 3, 1, 2), (1, 3, 0, 2), (2, 3, 0, 1), (0, 1, 3, 2), (0, 2, 3, 1), (1, 2, 3, 0)] 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,)]
-
group_generators
()¶ Implements
Groups.ParentMethods.group_generators()
by returning the simple reflections ofself
.EXAMPLES:
sage: D10 = FiniteCoxeterGroups().example(10) sage: D10.group_generators() Finite family {1: (1,), 2: (2,)} sage: SymmetricGroup(5).group_generators() Finite family {1: (1,2), 2: (2,3), 3: (3,4), 4: (4,5)}
Those give semigroup generators, even for an infinite group:
sage: W = WeylGroup(["A",2,1]) sage: W.semigroup_generators() Finite family {0: [-1 1 1] [ 0 1 0] [ 0 0 1], 1: [ 1 0 0] [ 1 -1 1] [ 0 0 1], 2: [ 1 0 0] [ 0 1 0] [ 1 1 -1]}
-
index_set
()¶ Returns the index set of (the simple reflections of)
self
, as a list (or iterable).EXAMPLES:
sage: W = FiniteCoxeterGroups().example(); W The 5-th dihedral group of order 10 sage: W.index_set() [1, 2]
-
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
. Thus we most likely get elements with lots of reduced words!
EXAMPLES:
sage: A = AffinePermutationGroup(['A', 7, 1]) sage: p = A.random_element_of_length(10) sage: p in A True sage: p.length() == 10 True sage: W = CoxeterGroup(['A', 4]) sage: p = W.random_element_of_length(5) sage: p in W True sage: p.length() == 5 True
-
rank
()¶ Return the rank of
self
.EXAMPLES:
sage: W = CoxeterGroups().example() sage: W.rank() 3
-
semigroup_generators
()¶ Implements
Groups.ParentMethods.group_generators()
by returning the simple reflections ofself
.EXAMPLES:
sage: D10 = FiniteCoxeterGroups().example(10) sage: D10.group_generators() Finite family {1: (1,), 2: (2,)} sage: SymmetricGroup(5).group_generators() Finite family {1: (1,2), 2: (2,3), 3: (3,4), 4: (4,5)}
Those give semigroup generators, even for an infinite group:
sage: W = WeylGroup(["A",2,1]) sage: W.semigroup_generators() Finite family {0: [-1 1 1] [ 0 1 0] [ 0 0 1], 1: [ 1 0 0] [ 1 -1 1] [ 0 0 1], 2: [ 1 0 0] [ 0 1 0] [ 1 1 -1]}
-
simple_projection
(i, side='right', length_increasing=True)¶ INPUT:
i
- an element of the index set ofself
Returns the simple projection
(or
if
is False).
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)¶ Returns the family of simple projections, also known as 0-Hecke or Demazure operators.
INPUT:
self
- a Coxeter groupside
- ‘left’ or ‘right’ (default: ‘right’)length_increasing
- a boolean (default: True) specifying whether the operator increases or decreases length
Returns the simple projections of
, as a family.
To each simple reflection
of
, corresponds a simple projection
from
to
defined by:
if
is not a descent of
otherwise.
The simple projections
move elements down the right permutohedron, toward the maximal element. They satisfy the same braid relations as the simple reflections, but are idempotents
not involutions
. As such, the simple projections generate the
-Hecke monoid.
By symmetry, one can also define the projections
(when the option
length_increasing
is False):if
is a descent of
otherwise.
as well as the analogues acting on the left (when the option
side
is ‘left’).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: pi=W.simple_projections() sage: 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)
-
simple_reflection
(i)¶ INPUT:
i
- an element from the index set.
Returns the simple reflection
EXAMPLES:
sage: W = CoxeterGroups().example() sage: W The symmetric group on {0, ..., 3} sage: W.simple_reflection(1) (0, 2, 1, 3) sage: s = W.simple_reflections() sage: s[1] (0, 2, 1, 3)
-
simple_reflections
()¶ Returns the simple reflections
, as a family.
EXAMPLES:
sage: W = CoxeterGroups().example() sage: W The symmetric group on {0, ..., 3} sage: s = W.simple_reflections() sage: s Finite family {0: (1, 0, 2, 3), 1: (0, 2, 1, 3), 2: (0, 1, 3, 2)} sage: s[0] (1, 0, 2, 3) sage: s[1] (0, 2, 1, 3) sage: s[2] (0, 1, 3, 2)
This default implementation uses
index_set()
andsimple_reflection()
.
-
some_elements
()¶ Implements
Sets.ParentMethods.some_elements()
by returning some typical element of.
EXAMPLES:
sage: W=WeylGroup(['A',3]) sage: W.some_elements() [ [0 1 0 0] [1 0 0 0] [1 0 0 0] [1 0 0 0] [0 0 0 1] [1 0 0 0] [0 0 1 0] [0 1 0 0] [0 1 0 0] [1 0 0 0] [0 0 1 0] [0 1 0 0] [0 0 0 1] [0 0 1 0] [0 1 0 0] [0 0 0 1], [0 0 0 1], [0 0 1 0], [0 0 0 1], [0 0 1 0] ] sage: W.order() 24
-
weak_order_ideal
(predicate, side='right', category=None)¶ Returns 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,), (1, 2), (1, 2, 1), (2,), (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] [ 3 -2] [ 1 0] [-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] [ 3 -2] [ 1 0] [-1 2] [0 1], [ 0 1], [ 2 -1], [ 2 -1], [-2 3] ]
Background
The weak order is returned as a
SearchForest
. This is achieved by assigning to each elementof the ideal a single ancestor
, where
is the smallest descent of
.
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).
-
-
CoxeterGroups.
super_categories
()¶ EXAMPLES:
sage: CoxeterGroups().super_categories() [Category of finitely generated groups]
-