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 groups, Category of enumerated sets]
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_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
alias of CoxeterGroupAlgebras
Return whether self is smaller than other 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
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
Conjugates self by the i-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]
Returns the Demazure or 0-Hecke product of self with another Coxeter group element.
See CoxeterGroups.ParentMethods.simple_projections().
INPUT:
group as self or a tuple or a list (such as a reduced word) of elements from the index set of the Coxeter group.
side of self on which the element should be applied. If side is ‘left’ then the operation is applied on the left.
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
INPUT:
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
Returns self multiplied by the simple reflection s[i]
INPUT:
This default implementation simply calls apply_simple_reflection_left() or apply_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'
Returns self multiplied by the simple reflection s[i] on the left
This 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'
Returns self multiplied by the simple reflection s[i] on the right
This 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'
INPUT:
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)
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 comparison
INPUT:
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 for self 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
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.
Returns all 2-tuples of lower_covers and reflections (v, r) where v is covered by self and r is the reflection such that self = 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)]
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 all in the
index set. Let
equal self. If
has 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
Returns all 2-tuples of covers and reflections (v, r) where v covers self and r is the reflection such that self = 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)]
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]
INPUT:
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()
[]
Returns the set of reflections t such that self t covers self.
If side is ‘left’, t self covers self.
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]
Returns Deodhar’s Bruhat order factoring element.
INPUT:
It is assumed that v = self and w are minimum length coset representatives
for W/W' such that v w in Bruhat order.
OUTPUT:
Deodhar’s element f(v,w) is the unique element of W' such that,
for all v' and w' in W', vv' ww' in W if and only if
v'
f(v,w) * w' in W' 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.
Letting v = self, given a Bruhat relation v W' w W' among cosets
with respect to the subgroup W' given by the Dynkin node subset index_set,
returns the Bruhat-maximum lift x of wW' such that v
x.
INPUT:
OUTPUT:
The unique Bruhat-maximum element x in W such that x W' = w W' and v `\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
Letting v = self, given a Bruhat relation v W' w W' among cosets
with respect to the subgroup W' given by the Dynkin node subset index_set,
returns the Bruhat-minimum lift x of wW' such that v
x.
INPUT:
OUTPUT:
The unique Bruhat-minimum element x in W such that x W' = w W'
and v 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
INPUT:
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 by index_set.
If positive is True, then returns the non-descents instead
TODO: 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
Returns the first left (resp. right) descent of self, as ane element of index_set, or None 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
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() and has_right_descent().
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'
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
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]
Returns the set of reflections r such that self 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]
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
Returns the set of reflections r such that r 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]
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)
Returns the reflections t such that self covers self t.
If side is ‘left’, self covers t 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]
Returns all elements that self covers in weak order.
INPUT:
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]]
Finds the unique Bruhat-minimum element u such that v w * u where v is self, w is element and * is the Demazure product.
INPUT:
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
Returns a reduced word for self.
This is a word of minimal length
such that
, where
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]
SEE ALSO: reduced_words(), reduced_word_reverse_iterator(), length()
Returns 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 reduced_word()
Default implementation: recursively remove the first right descent until the identity is reached (see first_descent() and apply_simple_reflection()).
Returns all reduced words for self.
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).
Returns all elements that cover self in weak order.
INPUT:
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]]
Returns all elements that self covers in weak order.
INPUT:
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]]
comparison in weak order
INPUT:
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')
alias of FiniteCoxeterGroups
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]
Return the canonical faithful representation of self.
EXAMPLES:
sage: W = WeylGroup("A3")
sage: W.canonical_representation()
Coxeter group over Universal Cyclotomic Field with Coxeter matrix:
[1 3 2]
[3 1 3]
[2 3 1]
Returns the Demazure product of the list Q in self.
INPUT:
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]
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]
INPUT:
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]
INPUT:
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,)]
Implements Groups.ParentMethods.group_generators() by returning the simple reflections of self.
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]}
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]
Return a random element of length n in self.
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
Implements Groups.ParentMethods.group_generators() by returning the simple reflections of self.
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]}
INPUT:
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)
Returns the family of simple projections, also known as 0-Hecke or Demazure operators.
INPUT:
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)
INPUT:
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)
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() and simple_reflection().
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
Returns a weak order ideal defined by a predicate
INPUT:
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 element of 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).
EXAMPLES:
sage: CoxeterGroups().super_categories()
[Category of groups, Category of enumerated sets]