Coverage for local/lib/python2.7/site-packages/sage/categories/weyl_groups.py : 78%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
r""" Weyl Groups """ #***************************************************************************** # Copyright (C) 2009 Nicolas M. Thiery <nthiery at users.sf.net> # # Distributed under the terms of the GNU General Public License (GPL) # http://www.gnu.org/licenses/ #******************************************************************************
from sage.misc.cachefunc import cached_method, cached_in_parent_method from sage.misc.lazy_import import LazyImport from sage.categories.category_singleton import Category_singleton from sage.categories.coxeter_groups import CoxeterGroups from sage.rings.infinity import infinity from sage.rings.rational_field import QQ
class WeylGroups(Category_singleton): r""" The category of Weyl groups
See the :wikipedia:`Wikipedia page of Weyl Groups <Weyl_group>`.
EXAMPLES::
sage: WeylGroups() Category of weyl groups sage: WeylGroups().super_categories() [Category of coxeter groups]
Here are some examples::
sage: WeylGroups().example() # todo: not implemented sage: FiniteWeylGroups().example() The symmetric group on {0, ..., 3} sage: AffineWeylGroups().example() # todo: not implemented sage: WeylGroup(["B", 3]) Weyl Group of type ['B', 3] (as a matrix group acting on the ambient space)
This one will eventually be also in this category::
sage: SymmetricGroup(4) Symmetric group of order 4! as a permutation group
TESTS::
sage: C = WeylGroups() sage: TestSuite(C).run() """
def super_categories(self): r""" EXAMPLES::
sage: WeylGroups().super_categories() [Category of coxeter groups] """
def additional_structure(self): r""" Return ``None``.
Indeed, the category of Weyl groups defines no additional structure: Weyl groups are a special class of Coxeter groups.
.. SEEALSO:: :meth:`Category.additional_structure`
.. TODO:: Should this category be a :class:`CategoryWithAxiom`?
EXAMPLES::
sage: WeylGroups().additional_structure() """
Finite = LazyImport('sage.categories.finite_weyl_groups', 'FiniteWeylGroups')
class ParentMethods: def coxeter_matrix(self): """ Return the Coxeter matrix associated to ``self``.
EXAMPLES::
sage: G = WeylGroup(['A',3]) sage: G.coxeter_matrix() [1 3 2] [3 1 3] [2 3 1] """
def pieri_factors(self, *args, **keywords): r""" Returns the set of Pieri factors in this Weyl group.
For any type, the set of Pieri factors forms a lower ideal in Bruhat order, generated by all the conjugates of some special element of the Weyl group. In type `A_n`, this special element is `s_n\cdots s_1`, and the conjugates are obtained by rotating around this reduced word.
These are used to compute Stanley symmetric functions.
.. SEEALSO::
* :meth:`WeylGroups.ElementMethods.stanley_symmetric_function` * :mod:`sage.combinat.root_system.pieri_factors`
EXAMPLES::
sage: W = WeylGroup(['A',5,1]) sage: PF = W.pieri_factors() sage: PF.cardinality() 63
sage: W = WeylGroup(['B',3]) sage: PF = W.pieri_factors() sage: [w.reduced_word() for w in PF] [[1, 2, 3, 2, 1], [1, 2, 3, 2], [2, 3, 2], [3, 1, 2], [1, 2, 3, 1], [1, 2, 1], [3, 1], [2, 1], [2, 3, 2, 1], [1, 2, 3], [3, 1, 2, 1], [2, 3], [3, 2], [1, 2], [3], [], [2], [3, 2, 1], [2, 3, 1], [1]] sage: W = WeylGroup(['C',4,1]) sage: PF = W.pieri_factors() sage: W.from_reduced_word([3,2,0]) in PF True """ # Do not remove this line which makes sure the pieri factor # code is properly inserted inside the Cartan Types raise NotImplementedError("Pieri factors for type {}".format(ct))
@cached_method def quantum_bruhat_graph(self, index_set=()): r""" Return the quantum Bruhat graph of the quotient of the Weyl group by a parabolic subgroup `W_J`.
INPUT:
- ``index_set`` -- (default: ()) a tuple `J` of nodes of the Dynkin diagram
By default, the value for ``index_set`` indicates that the subgroup is trivial and the quotient is the full Weyl group.
EXAMPLES::
sage: W = WeylGroup(['A',3], prefix="s") sage: g = W.quantum_bruhat_graph((1,3)) sage: g Parabolic Quantum Bruhat Graph of Weyl Group of type ['A', 3] (as a matrix group acting on the ambient space) for nodes (1, 3): Digraph on 6 vertices sage: g.vertices() [s2*s3*s1*s2, s3*s1*s2, s1*s2, s3*s2, s2, 1] sage: g.edges() [(s2*s3*s1*s2, s2, alpha[2]), (s3*s1*s2, s2*s3*s1*s2, alpha[1] + alpha[2] + alpha[3]), (s3*s1*s2, 1, alpha[2]), (s1*s2, s3*s1*s2, alpha[2] + alpha[3]), (s3*s2, s3*s1*s2, alpha[1] + alpha[2]), (s2, s1*s2, alpha[1] + alpha[2]), (s2, s3*s2, alpha[2] + alpha[3]), (1, s2, alpha[2])] sage: W = WeylGroup(['A',3,1], prefix="s") sage: g = W.quantum_bruhat_graph() Traceback (most recent call last): ... ValueError: the Cartan type ['A', 3, 1] is not finite """
# This is a modified form of quantum_bruhat_successors. # It does not do any error checking and also is more efficient # with how it handles memory and checks by using data stored # at this function level rather than recomputing everything. len(ref) == double_rho.scalar(alphacheck) - 1, # is_quantum NPR_sum.scalar(alphacheck)] # the scalar # We also create a temporary cache of lengths as they are # relatively expensive to compute and needed frequently # coset_representative returns wr if nothing gets changed
name="Parabolic Quantum Bruhat Graph of %s for nodes %s"%(self, index_set), format="dict_of_dicts", data_structure="static_sparse")
class ElementMethods:
def is_pieri_factor(self): r""" Returns whether ``self`` is a Pieri factor, as used for computing Stanley symmetric functions.
.. SEEALSO::
* :meth:`stanley_symmetric_function` * :meth:`WeylGroups.ParentMethods.pieri_factors`
EXAMPLES::
sage: W = WeylGroup(['A',5,1]) sage: W.from_reduced_word([3,2,5]).is_pieri_factor() True sage: W.from_reduced_word([3,2,4,5]).is_pieri_factor() False
sage: W = WeylGroup(['C',4,1]) sage: W.from_reduced_word([0,2,1]).is_pieri_factor() True sage: W.from_reduced_word([0,2,1,0]).is_pieri_factor() False
sage: W = WeylGroup(['B',3]) sage: W.from_reduced_word([3,2,3]).is_pieri_factor() False sage: W.from_reduced_word([2,1,2]).is_pieri_factor() True """
def left_pieri_factorizations(self, max_length = infinity): r""" Returns all factorizations of ``self`` as `uv`, where `u` is a Pieri factor and `v` is an element of the Weyl group.
.. SEEALSO::
* :meth:`WeylGroups.ParentMethods.pieri_factors` * :mod:`sage.combinat.root_system.pieri_factors`
EXAMPLES:
If we take `w = w_0` the maximal element of a strict parabolic subgroup of type `A_{n_1} \times \cdots \times A_{n_k}`, then the Pieri factorizations are in correspondence with all Pieri factors, and there are `\prod 2^{n_i}` of them::
sage: W = WeylGroup(['A', 4, 1]) sage: W.from_reduced_word([]).left_pieri_factorizations().cardinality() 1 sage: W.from_reduced_word([1]).left_pieri_factorizations().cardinality() 2 sage: W.from_reduced_word([1,2,1]).left_pieri_factorizations().cardinality() 4 sage: W.from_reduced_word([1,2,3,1,2,1]).left_pieri_factorizations().cardinality() 8
sage: W.from_reduced_word([1,3]).left_pieri_factorizations().cardinality() 4 sage: W.from_reduced_word([1,3,4,3]).left_pieri_factorizations().cardinality() 8
sage: W.from_reduced_word([2,1]).left_pieri_factorizations().cardinality() 3 sage: W.from_reduced_word([1,2]).left_pieri_factorizations().cardinality() 2 sage: [W.from_reduced_word([1,2]).left_pieri_factorizations(max_length=i).cardinality() for i in [-1, 0, 1, 2]] [0, 1, 2, 2]
sage: W = WeylGroup(['C',4,1]) sage: w = W.from_reduced_word([0,3,2,1,0]) sage: w.left_pieri_factorizations().cardinality() 7 sage: [(u.reduced_word(),v.reduced_word()) for (u,v) in w.left_pieri_factorizations()] [([], [3, 2, 0, 1, 0]), ([0], [3, 2, 1, 0]), ([3], [2, 0, 1, 0]), ([3, 0], [2, 1, 0]), ([3, 2], [0, 1, 0]), ([3, 2, 0], [1, 0]), ([3, 2, 0, 1], [0])]
sage: W = WeylGroup(['B',4,1]) sage: W.from_reduced_word([0,2,1,0]).left_pieri_factorizations().cardinality() 6 """
@cached_in_parent_method def stanley_symmetric_function_as_polynomial(self, max_length = infinity): r""" Returns a multivariate generating function for the number of factorizations of a Weyl group element into Pieri factors of decreasing length, weighted by a statistic on Pieri factors.
.. SEEALSO::
* :meth:`stanley_symmetric_function` * :meth:`WeylGroups.ParentMethods.pieri_factors` * :mod:`sage.combinat.root_system.pieri_factors`
INPUT:
- ``self`` -- an element `w` of a Weyl group `W` - ``max_length`` -- a non negative integer or infinity (default: infinity)
Returns the generating series for the Pieri factorizations `w = u_1 \cdots u_k`, where `u_i` is a Pieri factor for all `i`, `l(w) = \sum_{i=1}^k l(u_i)` and ``max_length`` `\geq l(u_1) \geq \cdots \geq l(u_k)`.
A factorization `u_1 \cdots u_k` contributes a monomial of the form `\prod_i x_{l(u_i)}`, with coefficient given by `\prod_i 2^{c(u_i)}`, where `c` is a type-dependent statistic on Pieri factors, as returned by the method ``u[i].stanley_symm_poly_weight()``.
EXAMPLES::
sage: W = WeylGroup(['A', 3, 1]) sage: W.from_reduced_word([]).stanley_symmetric_function_as_polynomial() 1 sage: W.from_reduced_word([1]).stanley_symmetric_function_as_polynomial() x1 sage: W.from_reduced_word([1,2]).stanley_symmetric_function_as_polynomial() x1^2 sage: W.from_reduced_word([2,1]).stanley_symmetric_function_as_polynomial() x1^2 + x2 sage: W.from_reduced_word([1,2,1]).stanley_symmetric_function_as_polynomial() 2*x1^3 + x1*x2 sage: W.from_reduced_word([1,2,1,0]).stanley_symmetric_function_as_polynomial() 3*x1^4 + 2*x1^2*x2 + x2^2 + x1*x3 sage: W.from_reduced_word([1,2,3,1,2,1,0]).stanley_symmetric_function_as_polynomial() # long time 22*x1^7 + 11*x1^5*x2 + 5*x1^3*x2^2 + 3*x1^4*x3 + 2*x1*x2^3 + x1^2*x2*x3 sage: W.from_reduced_word([3,1,2,0,3,1,0]).stanley_symmetric_function_as_polynomial() # long time 8*x1^7 + 4*x1^5*x2 + 2*x1^3*x2^2 + x1*x2^3
sage: W = WeylGroup(['C',3,1]) sage: W.from_reduced_word([0,2,1,0]).stanley_symmetric_function_as_polynomial() 32*x1^4 + 16*x1^2*x2 + 8*x2^2 + 4*x1*x3
sage: W = WeylGroup(['B',3,1]) sage: W.from_reduced_word([3,2,1]).stanley_symmetric_function_as_polynomial() 2*x1^3 + x1*x2 + 1/2*x3
Algorithm: Induction on the left Pieri factors. Note that this induction preserves subsets of `W` which are stable by taking right factors, and in particular Grassmanian elements. """
for (u,v) in self.left_pieri_factorizations(max_length) if u != W.one()))
def stanley_symmetric_function(self): r""" Return the affine Stanley symmetric function indexed by ``self``.
INPUT:
- ``self`` -- an element `w` of a Weyl group
Returns the affine Stanley symmetric function indexed by `w`. Stanley symmetric functions are defined as generating series of the factorizations of `w` into Pieri factors and weighted by a statistic on Pieri factors.
.. SEEALSO::
* :meth:`stanley_symmetric_function_as_polynomial` * :meth:`WeylGroups.ParentMethods.pieri_factors` * :mod:`sage.combinat.root_system.pieri_factors`
EXAMPLES::
sage: W = WeylGroup(['A', 3, 1]) sage: W.from_reduced_word([3,1,2,0,3,1,0]).stanley_symmetric_function() 8*m[1, 1, 1, 1, 1, 1, 1] + 4*m[2, 1, 1, 1, 1, 1] + 2*m[2, 2, 1, 1, 1] + m[2, 2, 2, 1] sage: A = AffinePermutationGroup(['A',3,1]) sage: A.from_reduced_word([3,1,2,0,3,1,0]).stanley_symmetric_function() 8*m[1, 1, 1, 1, 1, 1, 1] + 4*m[2, 1, 1, 1, 1, 1] + 2*m[2, 2, 1, 1, 1] + m[2, 2, 2, 1]
sage: W = WeylGroup(['C',3,1]) sage: W.from_reduced_word([0,2,1,0]).stanley_symmetric_function() 32*m[1, 1, 1, 1] + 16*m[2, 1, 1] + 8*m[2, 2] + 4*m[3, 1]
sage: W = WeylGroup(['B',3,1]) sage: W.from_reduced_word([3,2,1]).stanley_symmetric_function() 2*m[1, 1, 1] + m[2, 1] + 1/2*m[3]
sage: W = WeylGroup(['B',4]) sage: w = W.from_reduced_word([3,2,3,1]) sage: w.stanley_symmetric_function() # long time (6s on sage.math, 2011) 48*m[1, 1, 1, 1] + 24*m[2, 1, 1] + 12*m[2, 2] + 8*m[3, 1] + 2*m[4]
sage: A = AffinePermutationGroup(['A',4,1]) sage: a = A([-2,0,1,4,12]) sage: a.stanley_symmetric_function() 6*m[1, 1, 1, 1, 1, 1, 1, 1] + 5*m[2, 1, 1, 1, 1, 1, 1] + 4*m[2, 2, 1, 1, 1, 1] + 3*m[2, 2, 2, 1, 1] + 2*m[2, 2, 2, 2] + 4*m[3, 1, 1, 1, 1, 1] + 3*m[3, 2, 1, 1, 1] + 2*m[3, 2, 2, 1] + 2*m[3, 3, 1, 1] + m[3, 3, 2] + 3*m[4, 1, 1, 1, 1] + 2*m[4, 2, 1, 1] + m[4, 2, 2] + m[4, 3, 1]
One more example (:trac:`14095`)::
sage: G = SymmetricGroup(4) sage: w = G.from_reduced_word([3,2,3,1]) sage: w.stanley_symmetric_function() 3*m[1, 1, 1, 1] + 2*m[2, 1, 1] + m[2, 2] + m[3, 1]
REFERENCES:
- [BH1994]_
- [Lam2008]_
- [LSS2009]_
- [Pon2010]_ """
@cached_in_parent_method def reflection_to_root(self): r""" Returns the root associated with the reflection ``self``.
EXAMPLES::
sage: W=WeylGroup(['C',2],prefix="s") sage: W.from_reduced_word([1,2,1]).reflection_to_root() 2*alpha[1] + alpha[2] sage: W.from_reduced_word([1,2]).reflection_to_root() Traceback (most recent call last): ... ValueError: s1*s2 is not a reflection sage: W.long_element().reflection_to_root() Traceback (most recent call last): ... ValueError: s2*s1*s2*s1 is not a reflection """
raise ValueError("{} is not a reflection".format(self))
@cached_in_parent_method def reflection_to_coroot(self): r""" Returns the coroot associated with the reflection ``self``.
EXAMPLES::
sage: W=WeylGroup(['C',2],prefix="s") sage: W.from_reduced_word([1,2,1]).reflection_to_coroot() alphacheck[1] + alphacheck[2] sage: W.from_reduced_word([1,2]).reflection_to_coroot() Traceback (most recent call last): ... ValueError: s1*s2 is not a reflection sage: W.long_element().reflection_to_coroot() Traceback (most recent call last): ... ValueError: s2*s1*s2*s1 is not a reflection """
raise ValueError("{} is not a reflection".format(self))
def inversions(self, side = 'right', inversion_type = 'reflections'): """ Returns the set of inversions of ``self``.
INPUT:
- ``side`` -- 'right' (default) or 'left' - ``inversion_type`` -- 'reflections' (default), 'roots', or 'coroots'.
OUTPUT:
For reflections, the set of reflections r in the Weyl group such that ``self`` ``r`` < ``self``. For (co)roots, the set of positive (co)roots that are sent by ``self`` to negative (co)roots; their associated reflections are described above.
If ``side`` is 'left', the inverse Weyl group element is used.
EXAMPLES::
sage: W=WeylGroup(['C',2], prefix="s") sage: w=W.from_reduced_word([1,2]) sage: w.inversions() [s2, s2*s1*s2] sage: w.inversions(inversion_type = 'reflections') [s2, s2*s1*s2] sage: w.inversions(inversion_type = 'roots') [alpha[2], alpha[1] + alpha[2]] sage: w.inversions(inversion_type = 'coroots') [alphacheck[2], alphacheck[1] + 2*alphacheck[2]] sage: w.inversions(side = 'left') [s1, s1*s2*s1] sage: w.inversions(side = 'left', inversion_type = 'roots') [alpha[1], 2*alpha[1] + alpha[2]] sage: w.inversions(side = 'left', inversion_type = 'coroots') [alphacheck[1], alphacheck[1] + alphacheck[2]]
"""
raise ValueError("inversion_type {} is invalid".format(inversion_type))
def inversion_arrangement(self, side='right'): r""" Return the inversion hyperplane arrangement of ``self``.
INPUT:
- ``side`` -- ``'right'`` (default) or ``'left'``
OUTPUT:
A (central) hyperplane arrangement whose hyperplanes correspond to the inversions of ``self`` given as roots.
The ``side`` parameter determines on which side to compute the inversions.
EXAMPLES::
sage: W = WeylGroup(['A',3]) sage: w = W.from_reduced_word([1, 2, 3, 1, 2]) sage: A = w.inversion_arrangement(); A Arrangement of 5 hyperplanes of dimension 3 and rank 3 sage: A.hyperplanes() (Hyperplane 0*a1 + 0*a2 + a3 + 0, Hyperplane 0*a1 + a2 + 0*a3 + 0, Hyperplane 0*a1 + a2 + a3 + 0, Hyperplane a1 + a2 + 0*a3 + 0, Hyperplane a1 + a2 + a3 + 0)
The identity element gives the empty arrangement::
sage: W = WeylGroup(['A',3]) sage: W.one().inversion_arrangement() Empty hyperplane arrangement of dimension 3 """ for root in inv])
def bruhat_lower_covers_coroots(self): r""" Return all 2-tuples (``v``, `\alpha`) where ``v`` is covered by ``self`` and `\alpha` is the positive coroot such that ``self`` = ``v`` `s_\alpha` where `s_\alpha` is the reflection orthogonal to `\alpha`.
ALGORITHM:
See :meth:`.bruhat_lower_covers` and :meth:`.bruhat_lower_covers_reflections` for Coxeter groups.
EXAMPLES::
sage: W = WeylGroup(['A',3], prefix="s") sage: w = W.from_reduced_word([3,1,2,1]) sage: w.bruhat_lower_covers_coroots() [(s1*s2*s1, alphacheck[1] + alphacheck[2] + alphacheck[3]), (s3*s2*s1, alphacheck[2]), (s3*s1*s2, alphacheck[1])] """ for x in self.bruhat_lower_covers_reflections()]
def bruhat_upper_covers_coroots(self): r""" Returns all 2-tuples (``v``, `\alpha`) where ``v`` is covers ``self`` and `\alpha` is the positive coroot such that ``self`` = ``v`` `s_\alpha` where `s_\alpha` is the reflection orthogonal to `\alpha`.
ALGORITHM:
See :meth:`~CoxeterGroups.ElementMethods.bruhat_upper_covers` and :meth:`.bruhat_upper_covers_reflections` for Coxeter groups.
EXAMPLES::
sage: W = WeylGroup(['A',4], prefix="s") sage: w = W.from_reduced_word([3,1,2,1]) sage: w.bruhat_upper_covers_coroots() [(s1*s2*s3*s2*s1, alphacheck[3]), (s2*s3*s1*s2*s1, alphacheck[2] + alphacheck[3]), (s3*s4*s1*s2*s1, alphacheck[4]), (s4*s3*s1*s2*s1, alphacheck[1] + alphacheck[2] + alphacheck[3] + alphacheck[4])] """ for x in self.bruhat_upper_covers_reflections()]
def quantum_bruhat_successors(self, index_set=None, roots=False, quantum_only=False): r""" Return the successors of ``self`` in the quantum Bruhat graph on the parabolic quotient of the Weyl group determined by the subset of Dynkin nodes ``index_set``.
INPUT:
- ``self`` -- a Weyl group element, which is assumed to be of minimum length in its coset with respect to the parabolic subgroup
- ``index_set`` -- (default: ``None``) indicates the set of simple reflections used to generate the parabolic subgroup; the default value indicates that the subgroup is the identity
- ``roots`` -- (default: ``False``) if ``True``, returns the list of 2-tuples (``w``, `\alpha`) where ``w`` is a successor and `\alpha` is the positive root associated with the successor relation
- ``quantum_only`` -- (default: ``False``) if ``True``, returns only the quantum successors
EXAMPLES::
sage: W = WeylGroup(['A',3], prefix="s") sage: w = W.from_reduced_word([3,1,2]) sage: w.quantum_bruhat_successors([1], roots = True) [(s3, alpha[2]), (s1*s2*s3*s2, alpha[3]), (s2*s3*s1*s2, alpha[1] + alpha[2] + alpha[3])] sage: w.quantum_bruhat_successors([1,3]) [1, s2*s3*s1*s2] sage: w.quantum_bruhat_successors(roots = True) [(s3*s1*s2*s1, alpha[1]), (s3*s1, alpha[2]), (s1*s2*s3*s2, alpha[3]), (s2*s3*s1*s2, alpha[1] + alpha[2] + alpha[3])] sage: w.quantum_bruhat_successors() [s3*s1*s2*s1, s3*s1, s1*s2*s3*s2, s2*s3*s1*s2] sage: w.quantum_bruhat_successors(quantum_only = True) [s3*s1] sage: w = W.from_reduced_word([2,3]) sage: w.quantum_bruhat_successors([1,3]) Traceback (most recent call last): ... ValueError: s2*s3 is not of minimum length in its coset of the parabolic subgroup generated by the reflections (1, 3) """ raise ValueError("the Cartan type {} is not finite".format(W.cartan_type())) else: else: else:
|