Finite Coxeter Groups¶
-
class
sage.categories.finite_coxeter_groups.
FiniteCoxeterGroups
(base_category)¶ Bases:
sage.categories.category_with_axiom.CategoryWithAxiom
The category of finite Coxeter groups.
EXAMPLES:
sage: CoxeterGroups.Finite() Category of finite coxeter groups sage: FiniteCoxeterGroups().super_categories() [Category of finite generalized coxeter groups, Category of coxeter groups] sage: G = CoxeterGroups().Finite().example() sage: G.cayley_graph(side = "right").plot() Graphics object consisting of 40 graphics primitives
Here are some further examples:
sage: WeylGroups().Finite().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 other examples 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
-
class
ElementMethods
¶ -
bruhat_upper_covers
()¶ Returns all the elements that cover
self
in Bruhat order.EXAMPLES:
sage: W = WeylGroup(["A",4]) sage: w = W.from_reduced_word([3,2]) sage: print([v.reduced_word() for v in w.bruhat_upper_covers()]) [[4, 3, 2], [3, 4, 2], [2, 3, 2], [3, 1, 2], [3, 2, 1]] sage: W = WeylGroup(["B",6]) sage: w = W.from_reduced_word([1,2,1,4,5]) sage: C = w.bruhat_upper_covers() sage: len(C) 9 sage: print([v.reduced_word() for v in C]) [[6, 4, 5, 1, 2, 1], [4, 5, 6, 1, 2, 1], [3, 4, 5, 1, 2, 1], [2, 3, 4, 5, 1, 2], [1, 2, 3, 4, 5, 1], [4, 5, 4, 1, 2, 1], [4, 5, 3, 1, 2, 1], [4, 5, 2, 3, 1, 2], [4, 5, 1, 2, 3, 1]] sage: ww = W.from_reduced_word([5,6,5]) sage: CC = ww.bruhat_upper_covers() sage: print([v.reduced_word() for v in CC]) [[6, 5, 6, 5], [4, 5, 6, 5], [5, 6, 4, 5], [5, 6, 5, 4], [5, 6, 5, 3], [5, 6, 5, 2], [5, 6, 5, 1]]
Recursive algorithm: write \(w\) for
self
. If \(i\) is a non-descent of \(w\), then the covers of \(w\) are exactly \(\{ws_i, u_1s_i, u_2s_i,..., u_js_i\}\), where the \(u_k\) are those covers of \(ws_i\) that have a descent at \(i\).
-
covered_reflections_subgroup
()¶ Return the subgroup of \(W\) generated by the conjugates by \(w\) of the simple reflections indexed by right descents of \(w\).
This is used to compute the shard intersection order on \(W\).
EXAMPLES:
sage: W = CoxeterGroup(['A',3], base_ring=ZZ) sage: len(W.long_element().covered_reflections_subgroup()) 24 sage: s = W.simple_reflection(1) sage: Gs = s.covered_reflections_subgroup() sage: len(Gs) 2 sage: s in [u.lift() for u in Gs] True sage: len(W.one().covered_reflections_subgroup()) 1
-
coxeter_knuth_graph
()¶ Return the Coxeter-Knuth graph of type \(A\).
The Coxeter-Knuth graph of type \(A\) is generated by the Coxeter-Knuth relations which are given by \(a a+1 a \sim a+1 a a+1\), \(abc \sim acb\) if \(b<a<c\) and \(abc \sim bac\) if \(a<c<b\).
EXAMPLES:
sage: W = WeylGroup(['A',4], prefix='s') sage: w = W.from_reduced_word([1,2,1,3,2]) sage: D = w.coxeter_knuth_graph() sage: D.vertices() [(1, 2, 1, 3, 2), (1, 2, 3, 1, 2), (2, 1, 2, 3, 2), (2, 1, 3, 2, 3), (2, 3, 1, 2, 3)] sage: D.edges() [((1, 2, 1, 3, 2), (1, 2, 3, 1, 2), None), ((1, 2, 1, 3, 2), (2, 1, 2, 3, 2), None), ((2, 1, 2, 3, 2), (2, 1, 3, 2, 3), None), ((2, 1, 3, 2, 3), (2, 3, 1, 2, 3), None)] sage: w = W.from_reduced_word([1,3]) sage: D = w.coxeter_knuth_graph() sage: D.vertices() [(1, 3), (3, 1)] sage: D.edges() []
TESTS:
sage: W = WeylGroup(['B',4], prefix='s') sage: w = W.from_reduced_word([1,2]) sage: w.coxeter_knuth_graph() Traceback (most recent call last): ... NotImplementedError: This has only been implemented in finite type A so far!
-
coxeter_knuth_neighbor
(w)¶ Return the Coxeter-Knuth (oriented) neighbors of the reduced word \(w\) of
self
.INPUT:
w
– reduced word ofself
The Coxeter-Knuth relations are given by \(a a+1 a \sim a+1 a a+1\), \(abc \sim acb\) if \(b<a<c\) and \(abc \sim bac\) if \(a<c<b\). This method returns all neighbors of
w
under the Coxeter-Knuth relations oriented from left to right.EXAMPLES:
sage: W = WeylGroup(['A',4], prefix='s') sage: word = [1,2,1,3,2] sage: w = W.from_reduced_word(word) sage: w.coxeter_knuth_neighbor(word) {(1, 2, 3, 1, 2), (2, 1, 2, 3, 2)} sage: word = [1,2,1,3,2,4,3] sage: w = W.from_reduced_word(word) sage: w.coxeter_knuth_neighbor(word) {(1, 2, 1, 3, 4, 2, 3), (1, 2, 3, 1, 2, 4, 3), (2, 1, 2, 3, 2, 4, 3)}
TESTS:
sage: W = WeylGroup(['B',4], prefix='s') sage: word = [1,2] sage: w = W.from_reduced_word(word) sage: w.coxeter_knuth_neighbor(word) Traceback (most recent call last): ... NotImplementedError: This has only been implemented in finite type A so far!
-
-
class
FiniteCoxeterGroups.
ParentMethods
¶ Ambiguity resolution: the implementation of
some_elements
is preferable to that ofFiniteGroups
. The same holds for__iter__
, although a breath first search would be more natural; at least this maintains backward compatibility after trac ticket #13589.TESTS:
sage: W = FiniteCoxeterGroups().example(3) sage: W.some_elements.__module__ 'sage.categories.complex_reflection_or_generalized_coxeter_groups' sage: W.__iter__.__module__ 'sage.categories.coxeter_groups' sage: W.some_elements() [(1,), (2,), (), (1, 2)] sage: list(W) [(), (1,), (2,), (1, 2), (2, 1), (1, 2, 1)]
-
bruhat_poset
(facade=False)¶ Return the Bruhat poset of
self
.EXAMPLES:
sage: W = WeylGroup(["A", 2]) sage: P = W.bruhat_poset() sage: P Finite poset containing 6 elements sage: P.show()
Here are some typical operations on this poset:
sage: W = WeylGroup(["A", 3]) sage: P = W.bruhat_poset() sage: u = W.from_reduced_word([3,1]) sage: v = W.from_reduced_word([3,2,1,2,3]) sage: P(u) <= P(v) True sage: len(P.interval(P(u), P(v))) 10 sage: P.is_join_semilattice() False
By default, the elements of \(P\) are aware that they belong to \(P\):
sage: P.an_element().parent() Finite poset containing 24 elements
If instead one wants the elements to be plain elements of the Coxeter group, one can use the
facade
option:sage: P = W.bruhat_poset(facade = True) sage: P.an_element().parent() Weyl Group of type ['A', 3] (as a matrix group acting on the ambient space)
TESTS:
sage: [len(WeylGroup(["A", n]).bruhat_poset().cover_relations()) for n in [1,2,3]] [1, 8, 58]
Todo
- Use the symmetric group in the examples (for nicer output), and print the edges for a stronger test.
- The constructed poset should be lazy, in order to handle large / infinite Coxeter groups.
-
cambrian_lattice
(c, on_roots=False)¶ Return the \(c\)-Cambrian lattice on delta sequences.
See Arxiv 1503.00710 and Arxiv math/0611106.
Delta sequences are certain 2-colored minimal factorizations of
c
into reflections.INPUT:
c
– a standard Coxeter element inself
(as a tuple, or as an element ofself
)on_roots
(optional, defaultFalse
) – ifon_roots
isTrue
, the lattice is realized on roots rather than on reflections. In order for this to work, the ElementMethodreflection_to_root
must be available.
EXAMPLES:
sage: CoxeterGroup(["A", 2]).cambrian_lattice((1,2)) Finite lattice containing 5 elements sage: CoxeterGroup(["B", 2]).cambrian_lattice((1,2)) Finite lattice containing 6 elements sage: CoxeterGroup(["G", 2]).cambrian_lattice((1,2)) Finite lattice containing 8 elements
-
codegrees
()¶ Return the codegrees of the Coxeter group.
These are just the degrees minus 2.
EXAMPLES:
sage: CoxeterGroup(['A', 4]).codegrees() (0, 1, 2, 3) sage: CoxeterGroup(['B', 4]).codegrees() (0, 2, 4, 6) sage: CoxeterGroup(['D', 4]).codegrees() (0, 2, 2, 4) sage: CoxeterGroup(['F', 4]).codegrees() (0, 4, 6, 10) sage: CoxeterGroup(['E', 8]).codegrees() (0, 6, 10, 12, 16, 18, 22, 28) sage: CoxeterGroup(['H', 3]).codegrees() (0, 4, 8) sage: WeylGroup([["A",3], ["A",3], ["B",2]]).codegrees() (0, 1, 2, 0, 1, 2, 0, 2)
-
degrees
()¶ Return the degrees of the Coxeter group.
The output is an increasing list of integers.
EXAMPLES:
sage: CoxeterGroup(['A', 4]).degrees() (2, 3, 4, 5) sage: CoxeterGroup(['B', 4]).degrees() (2, 4, 6, 8) sage: CoxeterGroup(['D', 4]).degrees() (2, 4, 4, 6) sage: CoxeterGroup(['F', 4]).degrees() (2, 6, 8, 12) sage: CoxeterGroup(['E', 8]).degrees() (2, 8, 12, 14, 18, 20, 24, 30) sage: CoxeterGroup(['H', 3]).degrees() (2, 6, 10) sage: WeylGroup([["A",3], ["A",3], ["B",2]]).degrees() (2, 3, 4, 2, 3, 4, 2, 4)
TESTS:
sage: CoxeterGroup(['A', 4]).degrees() (2, 3, 4, 5) sage: SymmetricGroup(3).degrees() (2, 3)
-
inversion_sequence
(word)¶ Return the inversion sequence corresponding to the
word
in indices of simple generators ofself
.If
word
corresponds to \([w_0,w_1,...w_k]\), the output is \([w_0,w_0w_1w_0,\ldots,w_0w_1\cdots w_k \cdots w_1 w_0]\).INPUT:
word
– a word in the indices of the simple generators ofself
.
EXAMPLES:
sage: CoxeterGroup(["A", 2]).inversion_sequence([1,2,1]) [ [-1 1] [ 0 -1] [ 1 0] [ 0 1], [-1 0], [ 1 -1] ] sage: [t.reduced_word() for t in CoxeterGroup(["A",3]).inversion_sequence([2,1,3,2,1,3])] [[2], [1, 2, 1], [2, 3, 2], [1, 2, 3, 2, 1], [3], [1]]
-
long_element
(index_set=None, as_word=False)¶ Return the longest element of
self
, or of the parabolic subgroup corresponding to the givenindex_set
.INPUT:
index_set
– a subset (as a list or iterable) of the nodes of the Dynkin diagram; (default: all of them)as_word
– boolean (defaultFalse
). IfTrue
, then return instead a reduced decomposition of the longest element.
Should this method be called maximal_element? longest_element?
EXAMPLES:
sage: D10 = FiniteCoxeterGroups().example(10) sage: D10.long_element() (1, 2, 1, 2, 1, 2, 1, 2, 1, 2) sage: D10.long_element([1]) (1,) sage: D10.long_element([2]) (2,) sage: D10.long_element([]) () sage: D7 = FiniteCoxeterGroups().example(7) sage: D7.long_element() (1, 2, 1, 2, 1, 2, 1)
One can require instead a reduced word for w0:
sage: A3 = CoxeterGroup(['A', 3]) sage: A3.long_element(as_word=True) [1, 2, 1, 3, 2, 1]
-
m_cambrian_lattice
(c, m=1, on_roots=False)¶ Return the \(m\)-Cambrian lattice on \(m\)-delta sequences.
See Arxiv 1503.00710 and Arxiv math/0611106.
The \(m\)-delta sequences are certain \(m\)-colored minimal factorizations of \(c\) into reflections.
INPUT:
- \(c\) – a Coxeter element of
self
(as a tuple, or as an element ofself
) - \(m\) – a positive integer (optional, default 1)
on_roots
(optional, defaultFalse
) – ifon_roots
isTrue
, the lattice is realized on roots rather than on reflections. In order for this to work, the ElementMethodreflection_to_root
must be available.
EXAMPLES:
sage: CoxeterGroup(["A",2]).m_cambrian_lattice((1,2)) Finite lattice containing 5 elements sage: CoxeterGroup(["A",2]).m_cambrian_lattice((1,2),2) Finite lattice containing 12 elements
- \(c\) – a Coxeter element of
-
reflections_from_w0
()¶ Return the reflections of
self
using the inversion set ofw_0
.EXAMPLES:
sage: WeylGroup(['A',2]).reflections_from_w0() [ [0 1 0] [0 0 1] [1 0 0] [1 0 0] [0 1 0] [0 0 1] [0 0 1], [1 0 0], [0 1 0] ] sage: WeylGroup(['A',3]).reflections_from_w0() [ [0 1 0 0] [0 0 1 0] [1 0 0 0] [0 0 0 1] [1 0 0 0] [1 0 0 0] [1 0 0 0] [0 1 0 0] [0 0 1 0] [0 1 0 0] [0 0 0 1] [0 1 0 0] [0 0 1 0] [1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 1 0] [0 0 0 1] [0 0 0 1], [0 0 0 1], [0 0 0 1], [1 0 0 0], [0 1 0 0], [0 0 1 0] ]
-
shard_poset
(side='right')¶ Return the shard intersection order attached to \(W\).
This is a lattice structure on \(W\), introduced in [Reading]. It contains the noncrossing partition lattice, as the induced lattice on the subset of \(c\)-sortable elements.
The partial order is given by simultaneous inclusion of inversion sets and subgroups attached to every element.
The precise description used here can be found in [StThWi].
Another implementation for the symmetric groups is available as
shard_poset()
.EXAMPLES:
sage: W = CoxeterGroup(['A',3], base_ring=ZZ) sage: SH = W.shard_poset(); SH Finite lattice containing 24 elements sage: SH.is_graded() True sage: SH.characteristic_polynomial() q^3 - 11*q^2 + 23*q - 13 sage: SH.f_polynomial() 34*q^3 + 22*q^2 + q
REFERENCES:
[Reading] Nathan Reading, Noncrossing partitions and the shard intersection order, DMTCS Proceedings of FPSAC 2009, 745–756 [StThWi] Christian Stump, Hugh Thomas and Nathan Williams, Cataland: why the fuss?, Arxiv 1503.00710
-
w0
()¶ Return the longest element of
self
.This attribute is deprecated, use
long_element()
instead.EXAMPLES:
sage: D8 = FiniteCoxeterGroups().example(8) sage: D8.w0 (1, 2, 1, 2, 1, 2, 1, 2) sage: D3 = FiniteCoxeterGroups().example(3) sage: D3.w0 (1, 2, 1)
-
weak_lattice
(side='right', facade=False)¶ INPUT:
side
– “left”, “right”, or “twosided” (default: “right”)facade
– a boolean (default:False
)
Returns the left (resp. right) poset for weak order. In this poset, \(u\) is smaller than \(v\) if some reduced word of \(u\) is a right (resp. left) factor of some reduced word of \(v\).
EXAMPLES:
sage: W = WeylGroup(["A", 2]) sage: P = W.weak_poset() sage: P Finite lattice containing 6 elements sage: P.show()
This poset is in fact a lattice:
sage: W = WeylGroup(["B", 3]) sage: P = W.weak_poset(side = "left") sage: P.is_lattice() True
so this method has an alias
weak_lattice()
:sage: W.weak_lattice(side = "left") is W.weak_poset(side = "left") True
As a bonus feature, one can create the left-right weak poset:
sage: W = WeylGroup(["A",2]) sage: P = W.weak_poset(side = "twosided") sage: P.show() sage: len(P.hasse_diagram().edges()) 8
This is the transitive closure of the union of left and right order. In this poset, \(u\) is smaller than \(v\) if some reduced word of \(u\) is a factor of some reduced word of \(v\). Note that this is not a lattice:
sage: P.is_lattice() False
By default, the elements of \(P\) are aware of that they belong to \(P\):
sage: P.an_element().parent() Finite poset containing 6 elements
If instead one wants the elements to be plain elements of the Coxeter group, one can use the
facade
option:sage: P = W.weak_poset(facade = True) sage: P.an_element().parent() Weyl Group of type ['A', 2] (as a matrix group acting on the ambient space)
TESTS:
sage: [len(WeylGroup(["A", n]).weak_poset(side = "right").cover_relations()) for n in [1,2,3]] [1, 6, 36] sage: [len(WeylGroup(["A", n]).weak_poset(side = "left" ).cover_relations()) for n in [1,2,3]] [1, 6, 36]
Todo
- Use the symmetric group in the examples (for nicer output), and print the edges for a stronger test.
- The constructed poset should be lazy, in order to handle large / infinite Coxeter groups.
-
weak_poset
(side='right', facade=False)¶ INPUT:
side
– “left”, “right”, or “twosided” (default: “right”)facade
– a boolean (default:False
)
Returns the left (resp. right) poset for weak order. In this poset, \(u\) is smaller than \(v\) if some reduced word of \(u\) is a right (resp. left) factor of some reduced word of \(v\).
EXAMPLES:
sage: W = WeylGroup(["A", 2]) sage: P = W.weak_poset() sage: P Finite lattice containing 6 elements sage: P.show()
This poset is in fact a lattice:
sage: W = WeylGroup(["B", 3]) sage: P = W.weak_poset(side = "left") sage: P.is_lattice() True
so this method has an alias
weak_lattice()
:sage: W.weak_lattice(side = "left") is W.weak_poset(side = "left") True
As a bonus feature, one can create the left-right weak poset:
sage: W = WeylGroup(["A",2]) sage: P = W.weak_poset(side = "twosided") sage: P.show() sage: len(P.hasse_diagram().edges()) 8
This is the transitive closure of the union of left and right order. In this poset, \(u\) is smaller than \(v\) if some reduced word of \(u\) is a factor of some reduced word of \(v\). Note that this is not a lattice:
sage: P.is_lattice() False
By default, the elements of \(P\) are aware of that they belong to \(P\):
sage: P.an_element().parent() Finite poset containing 6 elements
If instead one wants the elements to be plain elements of the Coxeter group, one can use the
facade
option:sage: P = W.weak_poset(facade = True) sage: P.an_element().parent() Weyl Group of type ['A', 2] (as a matrix group acting on the ambient space)
TESTS:
sage: [len(WeylGroup(["A", n]).weak_poset(side = "right").cover_relations()) for n in [1,2,3]] [1, 6, 36] sage: [len(WeylGroup(["A", n]).weak_poset(side = "left" ).cover_relations()) for n in [1,2,3]] [1, 6, 36]
Todo
- Use the symmetric group in the examples (for nicer output), and print the edges for a stronger test.
- The constructed poset should be lazy, in order to handle large / infinite Coxeter groups.
-
-
FiniteCoxeterGroups.
extra_super_categories
()¶ EXAMPLES:
sage: CoxeterGroups().Finite().super_categories() [Category of finite generalized coxeter groups, Category of coxeter groups]
-
class