Coverage for local/lib/python2.7/site-packages/sage/combinat/root_system/pieri_factors.py : 98%

r""" 

Pieri Factors 

""" 

#***************************************************************************** 

# Copyright (C) 2009-2010 Steven Pon <spon at math.ucdavis.edu> 

# Anne Schilling < anne at math.ucdavis.edu> 

# 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 six.moves import range 

from sage.misc.cachefunc import cached_method 

from sage.misc.constant_function import ConstantFunction 

from sage.misc.all import prod, attrcall 

from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets 

from sage.structure.parent import Parent 

from sage.structure.unique_representation import UniqueRepresentation 

from sage.rings.integer import Integer 

from sage.rings.rational_field import QQ 

from sage.rings.infinity import infinity 

from sage.arith.all import binomial 

import sage.combinat.ranker 

from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet 

from sage.combinat.root_system.root_system import RootSystem 

from sage.combinat.root_system.dynkin_diagram import DynkinDiagram 

from sage.combinat.root_system.weyl_group import WeylGroup 

from sage.graphs.digraph import DiGraph 

class PieriFactors(UniqueRepresentation, Parent): 

r""" 

An abstract class for sets of Pieri factors, used for constructing 

Stanley symmetric functions. The set of Pieri factors for a given 

type can be realized as an order ideal of the Bruhat order poset 

generated by a certain set of maximal elements. 

.. SEEALSO:: 

- :meth:`WeylGroups.ParentMethods.pieri_factors` 

- :meth:`WeylGroups.ElementMethods.stanley_symmetric_function` 

EXAMPLES:: 

sage: W = WeylGroup(['A',4]) 

sage: PF = W.pieri_factors() 

sage: PF.an_element().reduced_word() 

[4, 3, 2, 1] 

sage: Waff = WeylGroup(['A',4,1]) 

sage: PFaff = Waff.pieri_factors() 

sage: Waff.from_reduced_word(PF.an_element().reduced_word()) in PFaff 

True 

sage: W = WeylGroup(['B',3,1]) 

sage: PF = W.pieri_factors() 

sage: W.from_reduced_word([2,3,2]) in PF.elements() 

True 

sage: PF.cardinality() 

47 

sage: W = WeylGroup(['C',3,1]) 

sage: PF = W.pieri_factors() 

sage: PF.generating_series() 

6*z^6 + 14*z^5 + 18*z^4 + 15*z^3 + 9*z^2 + 4*z + 1 

sage: [w.reduced_word() for w in PF if w.length() == 2] 

[[2, 3], [1, 0], [2, 0], [0, 1], [2, 1], [3, 1], [3, 0], [3, 2], [1, 2]] 

REFERENCES: 

.. [FoSta1994] \S. Fomin, R. Stanley. Schubert polynomials and the nilCoxeter algebra. Advances in Math., 1994. 

.. [BH1994] \S. Billey, M. Haiman. Schubert polynomials for the classical groups. J. Amer. Math. Soc., 1994. 

.. [TKLam1996] \T.K. Lam. B and D analogues of stable Schubert polynomials and related insertion algorithms. PhD Thesis, MIT, 1996. 

.. [Lam2008] \T. Lam. Schubert polynomials for the affine Grassmannian. J. Amer. Math. Soc., 2008. 

.. [LSS2009] \T. Lam, A. Schilling, M. Shimozono. Schubert polynomials for the affine Grassmannian of the symplectic group. Mathematische Zeitschrift 264(4) (2010) 765-811 (arXiv:0710.2720 [math.CO]) 

.. [Pon2010] \S. Pon. Types B and D affine Stanley symmetric functions, unpublished PhD Thesis, UC Davis, 2010. 

""" 

def _repr_(self): 

r""" 

EXAMPLES:: 

sage: WeylGroup(["A", 2, 1]).pieri_factors() # indirect doctest 

Pieri factors for Weyl Group of type ['A', 2, 1] (as a matrix group acting on the root space) 

""" 

return "Pieri factors for %s"%self.W 

def __contains__(self, w): 

r""" 

EXAMPLES:: 

sage: W = WeylGroup(['C',3,1]) 

sage: w = W.from_reduced_word([3,2,1,0]) 

sage: PF = W.pieri_factors() 

sage: w in PF 

True 

sage: w = W.from_reduced_word([1,0,1]) 

sage: w in PF 

True 

sage: w = W.from_reduced_word([1,0,1,0]) 

sage: w in PF 

False 

sage: w = W.from_reduced_word([0,1,2,3,2,1,0]) 

sage: w in PF 

False 

sage: w = W.from_reduced_word([2,0,3,2,1]) 

sage: w in PF 

True 

sage: W = WeylGroup(['B',4,1]) 

sage: PF = W.pieri_factors() 

sage: w = W.from_reduced_word([1,2,4,3,1]) 

sage: w in PF 

True 

sage: w = W.from_reduced_word([1,2,4,3,1,0]) 

sage: w in PF 

False 

sage: w = W.from_reduced_word([2,3,4,3,2,1,0]) 

sage: w in PF 

True 

sage: W = WeylGroup(['A',4]) 

sage: PF = W.pieri_factors() 

sage: W.from_reduced_word([4,3,1]) in PF 

True 

sage: W.from_reduced_word([1,2]) in PF 

False 

""" 

if w not in self.W: 

return False 

return any(w.bruhat_le(m) for m in self.maximal_elements()) 

@cached_method 

def elements(self): 

r""" 

Returns the elements of ``self`` 

Those are constructed as the elements below the maximal 

elements of ``self`` in Bruhat order. 

OUTPUT: a :class:`RecursivelyEnumeratedSet_generic` object 

EXAMPLES:: 

sage: PF = WeylGroup(['A',3]).pieri_factors() 

sage: [w.reduced_word() for w in PF.elements()] 

[[3, 2, 1], [2, 1], [3, 1], [3, 2], [2], [1], [3], []] 

.. SEEALSO:: :meth:`maximal_elements` 

.. TODO:: 

Possibly remove this method and instead have this class 

inherit from :class:`RecursivelyEnumeratedSet_generic`. 

""" 

return RecursivelyEnumeratedSet(self.maximal_elements(), 

attrcall('bruhat_lower_covers'), structure=None, 

enumeration='naive') 

def __iter__(self): 

r""" 

Returns an iterator over the elements of ``self`` 

EXAMPLES:: 

sage: PF = WeylGroup(['A',3,1]).pieri_factors() 

sage: f = PF.__iter__() 

sage: [next(f).reduced_word() for i in range(5)] 

[[], [0], [1], [2], [3]] 

""" 

return iter(self.elements()) 

def generating_series(self, weight = None): 

r""" 

Returns a length generating series for the elements of ``self`` 

EXAMPLES:: 

sage: PF = WeylGroup(['C',3,1]).pieri_factors() 

sage: PF.generating_series() 

6*z^6 + 14*z^5 + 18*z^4 + 15*z^3 + 9*z^2 + 4*z + 1 

sage: PF = WeylGroup(['B',4]).pieri_factors() 

sage: PF.generating_series() 

z^7 + 6*z^6 + 14*z^5 + 18*z^4 + 15*z^3 + 9*z^2 + 4*z + 1 

""" 

if weight is None: 

weight = self.default_weight() 

return sum(weight(w.length()) for w in self) 

@cached_method 

def default_weight(self): 

r""" 

Returns the function `i\mapsto z^i`, where `z` is the 

generator of ``QQ['z']``. 

EXAMPLES:: 

sage: W = WeylGroup(["A", 3, 1]) 

sage: weight = W.pieri_factors().default_weight() 

sage: weight(1) 

z 

sage: weight(5) 

z^5 

TESTS:: 

sage: weight(4) in QQ['z'] 

True 

sage: weight(0) in QQ['z'] 

True 

sage: weight(0).parent() == QQ['z'] # todo: not implemented 

True 

""" 

R = QQ['z'] 

z = R.gen() 

return lambda i: z**i 

def _test_maximal_elements(self, **options): 

r""" 

Check that the conjectural type-free definition of Pieri 

factors matches with the proven type-specific definition. 

See also :class:`TestSuite`. 

EXAMPLES:: 

sage: W = WeylGroup(['A',4,1]) 

sage: PF = W.pieri_factors() 

sage: PF._test_maximal_elements() 

sage: WeylGroup(['B',5]).pieri_factors()._test_maximal_elements() 

TESTS:: 

sage: W = WeylGroup(['C',4,1]) 

sage: PF = W.pieri_factors() 

sage: PF._test_maximal_elements() 

sage: WeylGroup(['D',5,1]).pieri_factors()._test_maximal_elements() 

sage: WeylGroup(['A',5,1]).pieri_factors()._test_maximal_elements() 

sage: WeylGroup(['B',5,1]).pieri_factors()._test_maximal_elements() 

""" 

tester = self._tester(**options) 

tester.assertTrue(set(self.maximal_elements()) == set(self.maximal_elements_combinatorial())) 

@cached_method 

def max_length(self): 

r""" 

Return the maximal length of a Pieri factor. 

EXAMPLES: 

In type A and A affine, this is `n`:: 

sage: WeylGroup(['A',5]).pieri_factors().max_length() 

5 

sage: WeylGroup(['A',5,1]).pieri_factors().max_length() 

5 

In type B and B affine, this is `2n-1`:: 

sage: WeylGroup(['B',5,1]).pieri_factors().max_length() 

9 

sage: WeylGroup(['B',5]).pieri_factors().max_length() 

9 

In type C affine this is `2n`:: 

sage: WeylGroup(['C',5,1]).pieri_factors().max_length() 

10 

In type D affine this is `2n-2`:: 

sage: WeylGroup(['D',5,1]).pieri_factors().max_length() 

8 

""" 

return self.maximal_elements()[0].length() 

class PieriFactors_finite_type(PieriFactors): 

r""" 

The Pieri factors of finite type A are the restriction of the 

Pieri factors of affine type A to finite permutations (under the 

canonical embedding of finite type A into the affine Weyl group), 

and the Pieri factors of finite type B are the restriction of the 

Pieri factors of affine type C. The finite type D Pieri factors 

are (weakly) conjectured to be the restriction of the Pieri 

factors of affine type D. 

""" 

def maximal_elements(self): 

r""" 

The current algorithm uses the fact that the maximal Pieri factors 

of affine type A,B,C, or D either contain a finite Weyl group 

element, or contain an affine Weyl group element whose reflection 

by `s_0` gets a finite Weyl group element, and that either of 

these finite group elements will serve as a maximal element for 

finite Pieri factors. A better algorithm is desirable. 

EXAMPLES:: 

sage: PF = WeylGroup(['A',5]).pieri_factors() 

sage: [v.reduced_word() for v in PF.maximal_elements()] 

[[5, 4, 3, 2, 1]] 

sage: WeylGroup(['B',4]).pieri_factors().maximal_elements() 

[ 

[-1 0 0 0] 

[ 0 1 0 0] 

[ 0 0 1 0] 

[ 0 0 0 1] 

] 

""" 

ct = self.W.cartan_type() 

# The following line may need to be changed when generalizing to more than types A and B. 

if ct.type() != 'A' and ct.type() != 'B': 

raise NotImplementedError("currently only implemented for finite types A and B") 

ct_aff = ct.dual().affine() 

max_elts_affine = WeylGroup(ct_aff).pieri_factors().maximal_elements() 

for w in max_elts_affine: 

if 0 not in w.reduced_word(): 

return [self.W.from_reduced_word(w.reduced_word())] 

for w in max_elts_affine: 

if 0 not in w.apply_simple_reflection(0).reduced_word(): 

return [self.W.from_reduced_word(w.apply_simple_reflection(0).reduced_word())] 

class PieriFactors_affine_type(PieriFactors): 

def maximal_elements(self): 

r""" 

Return the maximal elements of ``self`` with respect to Bruhat order. 

The current implementation is via a conjectural type-free 

formula. Use maximal_elements_combinatorial() for proven 

type-specific implementations. To compare type-free and 

type-specific (combinatorial) implementations, use method 

:meth:`_test_maximal_elements`. 

EXAMPLES:: 

sage: W = WeylGroup(['A',4,1]) 

sage: PF = W.pieri_factors() 

sage: sorted([w.reduced_word() for w in PF.maximal_elements()], key=str) 

[[0, 4, 3, 2], [1, 0, 4, 3], [2, 1, 0, 4], [3, 2, 1, 0], [4, 3, 2, 1]] 

sage: W = WeylGroup(RootSystem(["C",3,1]).weight_space()) 

sage: PF = W.pieri_factors() 

sage: sorted([w.reduced_word() for w in PF.maximal_elements()], key=str) 

[[0, 1, 2, 3, 2, 1], [1, 0, 1, 2, 3, 2], [1, 2, 3, 2, 1, 0], 

[2, 1, 0, 1, 2, 3], [2, 3, 2, 1, 0, 1], [3, 2, 1, 0, 1, 2]] 

sage: W = WeylGroup(RootSystem(["B",3,1]).weight_space()) 

sage: PF = W.pieri_factors() 

sage: sorted([w.reduced_word() for w in PF.maximal_elements()], key=str) 

[[0, 2, 3, 2, 0], [1, 0, 2, 3, 2], [1, 2, 3, 2, 1], 

[2, 1, 0, 2, 3], [2, 3, 2, 1, 0], [3, 2, 1, 0, 2]] 

sage: W = WeylGroup(['D',4,1]) 

sage: PF = W.pieri_factors() 

sage: sorted([w.reduced_word() for w in PF.maximal_elements()], key=str) 

[[0, 2, 4, 3, 2, 0], [1, 0, 2, 4, 3, 2], [1, 2, 4, 3, 2, 1], 

[2, 1, 0, 2, 4, 3], [2, 4, 3, 2, 1, 0], [3, 2, 1, 0, 2, 3], 

[4, 2, 1, 0, 2, 4], [4, 3, 2, 1, 0, 2]] 

""" 

ct = self.W.cartan_type() 

s = ct.translation_factors()[1] 

R = RootSystem(ct).weight_space() 

Lambda = R.fundamental_weights() 

orbit = [R.reduced_word_of_translation(x) 

for x in (s*(Lambda[1]-Lambda[1].level()*Lambda[0]))._orbit_iter()] 

return [self.W.from_reduced_word(x) for x in orbit] 

class PieriFactors_type_A(PieriFactors_finite_type): 

r""" 

The set of Pieri factors for finite type A. 

This is the set of elements of the Weyl group that have a reduced 

word that is strictly decreasing. May also be viewed as the 

restriction of affine type A Pieri factors to finite Weyl group 

elements. 

""" 

def __init__(self, W): 

r""" 

EXAMPLES:: 

sage: PF = WeylGroup(['A',5]).pieri_factors() 

sage: PF 

Pieri factors for Weyl Group of type ['A', 5] (as a matrix group acting on the ambient space) 

TESTS:: 

sage: PF = WeylGroup(['A',3]).pieri_factors() 

sage: PF.__class__ 

<class 'sage.combinat.root_system.pieri_factors.PieriFactors_type_A_with_category'> 

sage: TestSuite(PF).run() 

""" 

Parent.__init__(self, category = FiniteEnumeratedSets()) 

self.W = W 

def maximal_elements_combinatorial(self): 

r""" 

Returns the maximal Pieri factors, using the type A 

combinatorial description 

EXAMPLES:: 

sage: W = WeylGroup(['A',4]) 

sage: PF = W.pieri_factors() 

sage: PF.maximal_elements_combinatorial()[0].reduced_word() 

[4, 3, 2, 1] 

""" 

return [self.W.from_reduced_word(range(self.W.cartan_type().n,0,-1))] 

def stanley_symm_poly_weight(self,w): 

r""" 

EXAMPLES:: 

sage: W = WeylGroup(['A',4]) 

sage: PF = W.pieri_factors() 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([3,1])) 

0 

""" 

return 0 

class PieriFactors_type_B(PieriFactors_finite_type): 

r""" 

The type B finite Pieri factors are realized as the set of elements that have 

a reduced word that is a subword of 12...(n-1)n(n-1)...21. They are the restriction 

of the type C affine Pieri factors to the set of finite Weyl group elements under 

the usual embedding. 

""" 

def __init__(self, W): 

r""" 

EXAMPLES:: 

sage: WeylGroup(['B',5]).pieri_factors() 

Pieri factors for Weyl Group of type ['B', 5] (as a matrix group acting on the ambient space) 

TESTS:: 

sage: PF = WeylGroup(['B',3]).pieri_factors() 

sage: PF.__class__ 

<class 'sage.combinat.root_system.pieri_factors.PieriFactors_type_B_with_category'> 

sage: TestSuite(PF).run() 

""" 

Parent.__init__(self, category = FiniteEnumeratedSets()) 

self.W = W 

def maximal_elements_combinatorial(self): 

r""" 

Returns the maximal Pieri factors, using the type B 

combinatorial description 

EXAMPLES:: 

sage: PF = WeylGroup(['B',4]).pieri_factors() 

sage: PF.maximal_elements_combinatorial()[0].reduced_word() 

[1, 2, 3, 4, 3, 2, 1] 

""" 

N = self.W.cartan_type().n 

li = list(range(1, N)) + list(range(N, 0, -1)) 

return [self.W.from_reduced_word(li)] 

def stanley_symm_poly_weight(self,w): 

r""" 

Weight used in computing Stanley symmetric polynomials of type 

`B`. The weight for finite type B is the number of components 

of the support of an element minus the number of occurrences 

of `n` in a reduced word. 

EXAMPLES:: 

sage: W = WeylGroup(['B',5]) 

sage: PF = W.pieri_factors() 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([3,1,5])) 

2 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([3,4,5])) 

0 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([1,2,3,4,5,4])) 

0 

""" 

r = w.reduced_word().count(self.W.n) 

return WeylGroup(self.W.cartan_type().dual().affine()).pieri_factors().stanley_symm_poly_weight(w) - r 

class PieriFactors_type_A_affine(PieriFactors_affine_type): 

r""" 

The set of Pieri factors for type A affine, that is the set of 

elements of the Weyl Group which are cyclically decreasing. 

Those are used for constructing (affine) Stanley symmetric functions. 

The Pieri factors are in bijection with the proper subsets of the 

index_set. The bijection is given by the support. Namely, let `f` 

be a Pieri factor, and `red` a reduced word for `f`. No simple 

reflection appears twice in red, and the support `S` of `red` 

(that is the `i` such that `s_i` appears in `red`) does not depend 

on the reduced word). 

""" 

@staticmethod 

def __classcall__(cls, W, min_length = 0, max_length = infinity, min_support = frozenset([]), max_support = None): 

r""" 

TESTS:: 

sage: W = WeylGroup(['A',5,1]) 

sage: PF1 = sage.combinat.root_system.pieri_factors.PieriFactors_type_A_affine(W) 

sage: PF2 = W.pieri_factors() 

sage: PF3 = W.pieri_factors(min_support = []) 

sage: PF4 = W.pieri_factors(max_support = [0,1,2,3,4,5]) 

sage: PF5 = W.pieri_factors(max_length = 10) 

sage: PF6 = W.pieri_factors(min_length = 0) 

sage: PF2 is PF1, PF3 is PF1, PF4 is PF1, PF5 is PF1, PF6 is PF1 

(True, True, True, True, True) 

""" 

assert W.cartan_type().is_affine() and W.cartan_type().letter == 'A' 

# We use Python's frozenset's rather that Sage's Set's because 

# the latter do not yet support the issubset method 

min_support = frozenset(min_support) 

if max_support is None: 

max_support = frozenset(W.index_set()) 

else: 

max_support = frozenset(max_support) 

min_length = max(min_length, len(min_support)) 

max_length = min(len(max_support), max_length, len(W.index_set()) - 1) 

return super(PieriFactors_type_A_affine, cls).__classcall__(cls, W, min_length, max_length, min_support, max_support) 

def __init__(self, W, min_length, max_length, min_support, max_support): 

r""" 

EXAMPLES:: 

sage: PF = WeylGroup(["A", 3, 1]).pieri_factors(); PF 

Pieri factors for Weyl Group of type ['A', 3, 1] (as a matrix group acting on the root space) 

INPUT: 

- ``W`` -- a Weyl group of affine type `A` 

- ``min_length``, ``max_length`` -- non negative integers 

- ``min_support``, ``max_support`` -- subsets of the index set of `W` 

TESTS:: 

sage: PF = WeylGroup(['A',3,1]).pieri_factors() 

sage: PF.__class__ 

<class 'sage.combinat.root_system.pieri_factors.PieriFactors_type_A_affine_with_category'> 

sage: TestSuite(PF).run() 

sage: PF = WeylGroup(['A',3,1]).pieri_factors(min_length = 3) 

sage: [w.reduced_word() for w in PF] 

[[2, 1, 0], [1, 0, 3], [0, 3, 2], [3, 2, 1]] 

sage: PF = WeylGroup(['A',4,1]).pieri_factors(min_support = [0,2]) 

sage: [w.reduced_word() for w in PF] 

[[2, 0], [2, 1, 0], [3, 2, 0], [0, 4, 2], [3, 2, 1, 0], [2, 1, 0, 4], [0, 4, 3, 2]] 

sage: PF = WeylGroup(['A',5,1]).pieri_factors(min_support = [0,1,2], max_support = [0,1,2,3]) 

sage: [w.reduced_word() for w in PF] 

[[2, 1, 0], [3, 2, 1, 0]] 

sage: PF = WeylGroup(['A',5,1]).pieri_factors(min_length = 2, max_length = 5) 

sage: PF.generating_series() 

6*z^5 + 15*z^4 + 20*z^3 + 15*z^2 

""" 

Parent.__init__(self, category = FiniteEnumeratedSets()) 

self.W = W 

self._min_support = frozenset(min_support) 

self._max_support = frozenset(max_support) 

if not self._min_support.issubset(self._max_support): 

raise ValueError("the min support must be a subset of the max support") 

self._extra_support = self._max_support.difference(self._min_support) 

self._min_length = min_length 

self._max_length = max_length 

def subset(self, length): 

r""" 

INPUT: 

- ``length`` -- a non-negative integer 

Returns the subset of the elements of ``self`` of length ``length`` 

sage: PF = WeylGroup(["A", 3, 1]).pieri_factors(); PF 

Pieri factors for Weyl Group of type ['A', 3, 1] (as a matrix group acting on the root space) 

sage: PF3 = PF.subset(length = 2) 

sage: PF3.cardinality() 

6 

TESTS: 

We check that there is no reference effect (there was at some point!):: 

sage: PF.cardinality() 

15 

""" 

return self.__class__(self.W, 

min_support = self._min_support, 

max_support = self._max_support, 

min_length = length, 

max_length = length) 

def maximal_elements_combinatorial(self): 

r""" 

Returns the maximal Pieri factors, using the affine type A 

combinatorial description 

EXAMPLES:: 

sage: W = WeylGroup(['A',4,1]) 

sage: PF = W.pieri_factors() 

sage: [w.reduced_word() for w in PF.maximal_elements_combinatorial()] 

[[3, 2, 1, 0], [2, 1, 0, 4], [1, 0, 4, 3], [0, 4, 3, 2], [4, 3, 2, 1]] 

""" 

return self.subset(self._max_length) 

def _test_maximal_elements(self, **options): 

r""" 

Same as :meth:`PieriFactors._test_maximal_elements`, but skips 

the tests if ``self`` is not the full set of Pieri factors. 

sage: W = WeylGroup(['A',4,1]) 

sage: W.pieri_factors()._test_maximal_elements(verbose = True) 

sage: W.pieri_factors(min_length = 1)._test_maximal_elements(verbose = True) 

Strict subset of the pieri factors; skipping test 

""" 

tester = self._tester(**options) 

index_set = self.W.index_set() 

if self._min_length > 0 or self._max_length < len(self.W.index_set())-1 or self._max_support != frozenset(index_set): 

tester.info("\n Strict subset of the pieri factors; skipping test") 

return 

return super(PieriFactors_type_A_affine, self)._test_maximal_elements(**options) 

def __contains__(self, w): 

r""" 

Returns whether w is in self. 

EXAMPLES:: 

sage: W = WeylGroup(['A',6,1]) 

sage: PF = W.pieri_factors() 

sage: w=W.from_reduced_word([4,3,1,0,6]) 

sage: w in PF 

True 

sage: w=W.from_reduced_word([4,3,1,0,2]) 

sage: w in PF 

False 

sage: w=W.from_reduced_word([4,3,1,0,6,0]) 

sage: w in PF 

False 

sage: w=W.from_reduced_word([]) 

sage: w in PF 

True 

sage: w=W.from_reduced_word([3,2,1,0]) 

sage: w in PF 

True 

sage: W=WeylGroup(['A',3,1]) 

sage: PF = W.pieri_factors() 

sage: w=W.from_reduced_word([3,2,1,0]) 

sage: w in PF 

False 

""" 

if w not in self.W: 

raise ValueError("{} is not an element of the Weyl group".format(w)) 

n = len(self.W.index_set()) - 1 

red = w.reduced_word() 

support = set(red) 

if len(support) < len(red): # There should be no repetitions 

return False 

if not(self._min_length <= len(support) and 

len(support) <= self._max_length and 

self._min_support.issubset(support) and 

support.issubset(self._max_support)): 

return False 

[rank, unrank] = sage.combinat.ranker.from_list(red) 

for i in red: 

j = (i+1) % (n+1) 

if j in support: 

if rank(i) < rank(j): 

return False 

return True 

def __getitem__(self, support): 

r""" 

Return the cyclically decreasing element associated with ``support``. 

INPUT: 

- ``support`` -- a proper subset of the index_set, as a list or set 

EXAMPLES:: 

sage: W = WeylGroup(["A", 5, 1]) 

sage: W.pieri_factors()[[0,1,2,3,5]].reduced_word() 

[3, 2, 1, 0, 5] 

sage: W.pieri_factors()[[0,1,3,4,5]].reduced_word() 

[1, 0, 5, 4, 3] 

sage: W.pieri_factors()[[0,1,2,3,4]].reduced_word() 

[4, 3, 2, 1, 0] 

""" 

index_set = sorted(self.W.index_set()) 

support = sorted(support) 

if not set(support).issubset(set(index_set)) or support == index_set: 

raise ValueError("the support must be a proper subset of the index set") 

if not support: 

return self.W.one() 

s = self.W.simple_reflections() 

i = 0 

while i < len(support) and support[i] == index_set[i]: 

i += 1 

# This finds the first hole: either ley[i] is maximal or support[i] < support[i+1]+1 

return prod((s[j] for j in list(reversed(support[0:i])) + list(reversed(support[i:]))), self.W.one()) 

def cardinality(self): 

r""" 

EXAMPLES:: 

sage: WeylGroup(["A", 3, 1]).pieri_factors().cardinality() 

15 

""" 

if self._min_length == len(self._min_support) and self._max_length == len(self._max_support) -1: 

return Integer(2**(len(self._extra_support)) - 1) 

else: 

return self.generating_series(weight = ConstantFunction(1)) 

def generating_series(self, weight = None): 

r""" 

Returns a length generating series for the elements of ``self`` 

EXAMPLES:: 

sage: W = WeylGroup(["A", 3, 1]) 

sage: W.pieri_factors().cardinality() 

15 

sage: W.pieri_factors().generating_series() 

4*z^3 + 6*z^2 + 4*z + 1 

""" 

if weight is None: 

weight = self.default_weight() 

l_min = len(self._min_support) 

l_max = len(self._max_support) 

return sum(binomial(l_max-l_min, l-l_min) * weight(l) 

for l in range(self._min_length, self._max_length+1)) 

def __iter__(self): 

r""" 

Returns an iterator over the elements of ``self`` 

EXAMPLES:: 

sage: W = WeylGroup(['A',4,1]) 

sage: PF = W.pieri_factors() 

sage: f = PF.__iter__() 

sage: next(f) 

[1 0 0 0 0] 

[0 1 0 0 0] 

[0 0 1 0 0] 

[0 0 0 1 0] 

[0 0 0 0 1] 

sage: [next(f).reduced_word() for i in range(6)] 

[[0], [1], [2], [3], [4], [1, 0]] 

""" 

from sage.combinat.subset import Subsets 

index_set = self.W.index_set() 

for l in range(self._min_length, self._max_length+1): 

for extra in Subsets(self._extra_support, l - len(self._min_support)): 

yield self[self._min_support.union(extra)] 

def stanley_symm_poly_weight(self,w): 

r""" 

Weight used in computing (affine) Stanley symmetric polynomials for affine type A. 

EXAMPLES:: 

sage: W = WeylGroup(['A',5,1]) 

sage: PF = W.pieri_factors() 

sage: PF.stanley_symm_poly_weight(W.one()) 

0 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([5,4,2,1,0])) 

0 

""" 

return 0 

class PieriFactors_type_C_affine(PieriFactors_affine_type): 

r""" 

The type C affine Pieri factors are realized as the order ideal (in Bruhat 

order) generated by cyclic rotations of the element with unique reduced word 

123...(n-1)n(n-1)...3210. 

EXAMPLES:: 

sage: W = WeylGroup(['C',3,1]) 

sage: PF = W.pieri_factors() 

sage: sorted([u.reduced_word() for u in PF.maximal_elements()], key=str) 

[[0, 1, 2, 3, 2, 1], [1, 0, 1, 2, 3, 2], [1, 2, 3, 2, 1, 0], 

[2, 1, 0, 1, 2, 3], [2, 3, 2, 1, 0, 1], [3, 2, 1, 0, 1, 2]] 

""" 

def __init__(self, W): 

r""" 

TESTS:: 

sage: PF = WeylGroup(['C',3,1]).pieri_factors() 

sage: PF.__class__ 

<class 'sage.combinat.root_system.pieri_factors.PieriFactors_type_C_affine_with_category'> 

sage: TestSuite(PF).run() # long time (4s on sage.math, 2011) 

""" 

Parent.__init__(self, category = FiniteEnumeratedSets()) 

self.W = W 

@cached_method 

def maximal_elements_combinatorial(self): 

r""" 

Returns the maximal Pieri factors, using the affine type C 

combinatorial description 

EXAMPLES:: 

sage: PF = WeylGroup(['C',3,1]).pieri_factors() 

sage: [w.reduced_word() for w in PF.maximal_elements_combinatorial()] 

[[0, 1, 2, 3, 2, 1], [1, 0, 1, 2, 3, 2], [2, 1, 0, 1, 2, 3], [3, 2, 1, 0, 1, 2], [2, 3, 2, 1, 0, 1], [1, 2, 3, 2, 1, 0]] 

""" 

n = self.W.n 

rho = self.W.from_reduced_word(range(1,n-1))*self.W.from_reduced_word(range(n-1,-1,-1)) 

rotations = [] 

for i in range(0,2*(n-1)): 

rho = rho.apply_simple_reflections(rho.descents()).apply_simple_reflections(rho.descents(),side='left') 

rotations.append(rho) 

return rotations 

def stanley_symm_poly_weight(self,w): 

r""" 

Returns the weight of a Pieri factor to be used in the definition of Stanley 

symmetric functions. For type C, this weight is the number of connected 

components of the support (the indices appearing in a reduced word) of 

an element. 

EXAMPLES:: 

sage: W = WeylGroup(['C',5,1]) 

sage: PF = W.pieri_factors() 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([1,3])) 

2 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([1,3,2,0])) 

1 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([5,3,0])) 

3 

sage: PF.stanley_symm_poly_weight(W.one()) 

0 

""" 

# The algorithm="delete" is a workaround when the set of 

# vertices is empty, in which case subgraph tries another 

# method which turns out to currently fail with Dynkin diagrams 

return DiGraph(DynkinDiagram(w.parent().cartan_type())).subgraph(set(w.reduced_word()), algorithm="delete").connected_components_number() 

class PieriFactors_type_B_affine(PieriFactors_affine_type): 

r""" 

The type B affine Pieri factors are realized as the order ideal (in Bruhat 

order) generated by the following elements: 

- cyclic rotations of the element with reduced word 234...(n-1)n(n-1)...3210, 

except for 123...n...320 and 023...n...321. 

- 123...(n-1)n(n-1)...321 

- 023...(n-1)n(n-1)...320 

EXAMPLES:: 

sage: W = WeylGroup(['B',4,1]) 

sage: PF = W.pieri_factors() 

sage: W.from_reduced_word([2,3,4,3,2,1,0]) in PF.maximal_elements() 

True 

sage: W.from_reduced_word([0,2,3,4,3,2,1]) in PF.maximal_elements() 

False 

sage: W.from_reduced_word([1,0,2,3,4,3,2]) in PF.maximal_elements() 

True 

sage: W.from_reduced_word([0,2,3,4,3,2,0]) in PF.maximal_elements() 

True 

sage: W.from_reduced_word([0,2,0]) in PF 

True 

""" 

def __init__(self, W): 

r""" 

TESTS:: 

sage: PF = WeylGroup(["B",3,1]).pieri_factors() 

sage: PF.__class__ 

<class 'sage.combinat.root_system.pieri_factors.PieriFactors_type_B_affine_with_category'> 

sage: TestSuite(PF).run() 

""" 

Parent.__init__(self, category = FiniteEnumeratedSets()) 

self.W = W 

@cached_method 

def maximal_elements_combinatorial(self): 

r""" 

Returns the maximal Pieri factors, using the affine type B 

combinatorial description 

EXAMPLES:: 

sage: W = WeylGroup(['B',4,1]) 

sage: [u.reduced_word() for u in W.pieri_factors().maximal_elements_combinatorial()] 

[[1, 0, 2, 3, 4, 3, 2], [2, 1, 0, 2, 3, 4, 3], [3, 2, 1, 0, 2, 3, 4], [4, 3, 2, 1, 0, 2, 3], [3, 4, 3, 2, 1, 0, 2], [2, 3, 4, 3, 2, 1, 0], [1, 2, 3, 4, 3, 2, 1], [0, 2, 3, 4, 3, 2, 0]] 

""" 

n = self.W.n 

rho = self.W.from_reduced_word(range(2,n-1))*self.W.from_reduced_word(range(n-1,-1,-1)) 

rotations = [] 

for i in range(0,2*(n-2)): 

rho = rho.apply_simple_reflections(rho.descents()).apply_simple_reflections(rho.descents(),side='left') 

rotations.append(rho) 

rotations.append(self.W.from_reduced_word(range(1,n-1))*self.W.from_reduced_word(range(n-1,0,-1))) 

rotations.append(self.W.from_reduced_word([0])*self.W.from_reduced_word(range(2,n-1))*self.W.from_reduced_word(range(n-1,1,-1))*self.W.from_reduced_word([0])) 

return rotations 

def stanley_symm_poly_weight(self,w): 

r""" 

Returns the weight of a Pieri factor to be used in the definition of Stanley 

symmetric functions. For type B, this weight involves the number of components 

of the complement of the support of an element, where we consider 0 and 1 to 

be one node -- if 1 is in the support, then we pretend 0 in the support, and vice 

versa. We also consider 0 and 1 to be one node for the purpose of counting 

components of the complement (as if the Dynkin diagram were that of type C). 

Let n be the rank of the affine Weyl group in question (if type ['B',k,1] then 

we have n = k+1). Let chi(v.length() < n-1) be the indicator function that is 1 

if the length of v is smaller than n-1, and 0 if the length of v is greater than or 

equal to n-1. If we say c'(v) = the number of components of the complement of 

the support of v, then the type B weight is given by 

weight = c'(v) - chi(v.length() < n-1). 

EXAMPLES:: 

sage: W = WeylGroup(['B',5,1]) 

sage: PF = W.pieri_factors() 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([0,3])) 

1 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([0,1,3])) 

1 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([2,3])) 

1 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([2,3,4,5])) 

0 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([0,5])) 

0 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([2,4,5,4,3,0])) 

-1 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([4,5,4,3,0])) 

0 

""" 

ct = w.parent().cartan_type() 

support = set(w.reduced_word()) 

if 1 in support or 0 in support: 

support_complement = set(ct.index_set()).difference(support).difference(set([0,1])) 

else: 

support_complement = set(ct.index_set()).difference(support).difference(set([0])) 

return DiGraph(DynkinDiagram(ct)).subgraph(support_complement, algorithm="delete").connected_components_number() - 1 

class PieriFactors_type_D_affine(PieriFactors_affine_type): 

r""" 

The type D affine Pieri factors are realized as the order ideal 

(in Bruhat order) generated by the following elements: 

* cyclic rotations of the element with reduced word 234...(n-2)n(n-1)(n-2)...3210 

such that 1 and 0 are always adjacent and (n-1) and n are always adjacent. 

* 123...(n-2)n(n-1)(n-2)...321 

* 023...(n-2)n(n-1)(n-2)...320 

* n(n-2)...2102...(n-2)n 

* (n-1)(n-2)...2102...(n-2)(n-1) 

EXAMPLES:: 

sage: W = WeylGroup(['D',5,1]) 

sage: PF = W.pieri_factors() 

sage: W.from_reduced_word([3,2,1,0]) in PF 

True 

sage: W.from_reduced_word([0,3,2,1]) in PF 

False 

sage: W.from_reduced_word([0,1,3,2]) in PF 

True 

sage: W.from_reduced_word([2,0,1,3]) in PF 

True 

sage: sorted([u.reduced_word() for u in PF.maximal_elements()], key=str) 

[[0, 2, 3, 5, 4, 3, 2, 0], [1, 0, 2, 3, 5, 4, 3, 2], [1, 2, 3, 5, 4, 3, 2, 1], 

[2, 1, 0, 2, 3, 5, 4, 3], [2, 3, 5, 4, 3, 2, 1, 0], [3, 2, 1, 0, 2, 3, 5, 4], 

[3, 5, 4, 3, 2, 1, 0, 2], [4, 3, 2, 1, 0, 2, 3, 4], [5, 3, 2, 1, 0, 2, 3, 5], 

[5, 4, 3, 2, 1, 0, 2, 3]] 

""" 

def __init__(self, W): 

r""" 

TESTS:: 

sage: PF = WeylGroup(["D",4,1]).pieri_factors() 

sage: PF.__class__ 

<class 'sage.combinat.root_system.pieri_factors.PieriFactors_type_D_affine_with_category'> 

sage: TestSuite(PF).run() # long time 

""" 

Parent.__init__(self, category = FiniteEnumeratedSets()) 

self.W = W 

@cached_method 

def maximal_elements_combinatorial(self): 

r""" 

Returns the maximal Pieri factors, using the affine type D 

combinatorial description 

EXAMPLES:: 

sage: W = WeylGroup(['D',5,1]) 

sage: PF = W.pieri_factors() 

sage: set(PF.maximal_elements_combinatorial()) == set(PF.maximal_elements()) 

True 

""" 

n = self.W.n 

rho = self.W.from_reduced_word(range(2,n))*self.W.from_reduced_word(range(n-3,-1,-1)) 

rotations = [] 

for i in range(0,2*(n-3)): 

rho = rho.apply_simple_reflections(rho.descents()).apply_simple_reflections(rho.descents(),side='left') 

rotations.append(rho) 

rotations.append(self.W.from_reduced_word(range(1,n))*self.W.from_reduced_word(range(n-3,0,-1))) 

rotations.append(self.W.from_reduced_word([0])*self.W.from_reduced_word(range(2,n))*self.W.from_reduced_word(range(n-3,1,-1))*self.W.from_reduced_word([0])) 

rotations.append(self.W.from_reduced_word(range(n-2,-1,-1))*self.W.from_reduced_word(range(2,n-1))) 

rotations.append(self.W.from_reduced_word([n-1])*self.W.from_reduced_word(range(n-3,-1,-1))*self.W.from_reduced_word(range(2,n-2))*self.W.from_reduced_word([n-1])) 

return rotations 

def stanley_symm_poly_weight(self, w): 

r""" 

INPUT: 

- ``w`` -- a pieri factor for this type 

Returns the weight of `w`, to be used in the definition of 

Stanley symmetric functions. For type D, this weight involves 

the number of components of the complement of the support of 

an element, where we consider 0 and 1 to be one node -- if 1 

is in the support, then we pretend 0 in the support, and vice 

versa. Similarly with `n-1` and `n`. We also consider 0 and 

1, n-1 and n to be one node for the purpose of counting 

components of the complement (as if the Dynkin diagram were 

that of type C). 

Type D Stanley symmetric polynomial weights are still 

conjectural. The given weight comes from conditions on 

elements of the affine Fomin-Stanley subalgebra, but work is 

needed to show this weight is correct for affine Stanley 

symmetric functions -- see [LSS2009, Pon2010] for details. 

EXAMPLES:: 

sage: W = WeylGroup(['D', 5, 1]) 

sage: PF = W.pieri_factors() 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([5,2,1])) 

0 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([5,2,1,0])) 

0 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([5,2])) 

1 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([])) 

0 

sage: W = WeylGroup(['D',7,1]) 

sage: PF = W.pieri_factors() 

sage: PF.stanley_symm_poly_weight(W.from_reduced_word([2,4,6])) 

2 

""" 

ct = w.parent().cartan_type() 

support = set(w.reduced_word()) 

n = w.parent().n 

if 1 in support or 0 in support: 

support = support.union(set([1])).difference(set([0])) 

if n in support or n-1 in support: 

support = support.union(set([n-2])).difference(set([n-1])) 

support_complement = set(range(1,n-1)).difference(support) 

return DiGraph(DynkinDiagram(ct)).subgraph(support_complement).connected_components_number()-1 

# Inserts those classes in CartanTypes 

from sage.combinat.root_system import type_A_affine, type_B_affine, type_C_affine, type_D_affine, type_A, type_B 

type_A_affine.CartanType.PieriFactors = PieriFactors_type_A_affine 

type_B_affine.CartanType.PieriFactors = PieriFactors_type_B_affine 

type_C_affine.CartanType.PieriFactors = PieriFactors_type_C_affine 

type_D_affine.CartanType.PieriFactors = PieriFactors_type_D_affine 

type_A.CartanType.PieriFactors = PieriFactors_type_A 

type_B.CartanType.PieriFactors = PieriFactors_type_B 

# Pieri factors for these types have not yet been mathematically 

# introduced rigorously 

# 

# import type_C, type_D, type_E, type_F, type_G, type_E_affine, type_F_affine, type_G_affine 

#type_C.CartanType.PieriFactors = PieriFactors_type_C 

#type_D.CartanType.PieriFactors = PieriFactors_type_D 

#type_E.CartanType.PieriFactors = PieriFactors_type_E 

#type_F.CartanType.PieriFactors = PieriFactors_type_F 

#type_G.CartanType.PieriFactors = PieriFactors_type_G 

#type_E_affine.CartanType.PieriFactors = PieriFactors_type_E_affine 

#type_F_affine.CartanType.PieriFactors = PieriFactors_type_F_affine 

#type_G_affine.CartanType.PieriFactors = PieriFactors_type_G_affine