# Finite Coxeter Groups¶

class sage.categories.finite_coxeter_groups.FiniteCoxeterGroups(base_category)

The category of finite Coxeter groups.

EXAMPLES:

sage: FiniteCoxeterGroups()
Category of finite coxeter groups
sage: FiniteCoxeterGroups().super_categories()
[Category of finite groups, Category of coxeter groups]

sage: G = FiniteCoxeterGroups().example()
sage: G.cayley_graph(side = "right").plot()
Graphics object consisting of 40 graphics primitives


Here are some further examples:

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 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$$.

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 of self

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 of FiniteGroups. 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.coxeter_groups'
sage: W.__iter__.__module__
'sage.categories.coxeter_groups'

sage: W.some_elements()
[(1,), (2,), (), (1, 2)]
sage: list(W)
[(), (1,), (1, 2), (1, 2, 1), (2,), (2, 1)]


Returns 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.
long_element(index_set=None)

INPUT:

• index_set - a subset (as a list or iterable) of the nodes of the Dynkin diagram; (default: all of them)

Returns the longest element of self, or of the parabolic subgroup corresponding to the given index_set.

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)

some_elements()

Implements Sets.ParentMethods.some_elements() by returning some typical element of $$self$$.

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

w0()

Return the longest element of self.

This attribute is deprecated.

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)


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.

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.

Fields

Finite Crystals