Path: blob/master/src/sage/libs/coxeter3/coxeter_group.py
8817 views
"""1Coxeter Groups implemented with Coxeter32"""3#*****************************************************************************4# Copyright (C) 2009-2013 Mike Hansen <[email protected]>5#6# Distributed under the terms of the GNU General Public License (GPL)7# http://www.gnu.org/licenses/8#*****************************************************************************9from sage.groups.group import Group10from sage.libs.coxeter3.coxeter import get_CoxGroup, CoxGroupElement11from sage.structure.element import MultiplicativeGroupElement12from sage.misc.cachefunc import cached_method1314from sage.structure.unique_representation import UniqueRepresentation15from sage.structure.element_wrapper import ElementWrapper16from sage.categories.all import CoxeterGroups, FiniteCoxeterGroups17from sage.structure.parent import Parent1819class CoxeterGroup(UniqueRepresentation, Parent):20@staticmethod21def __classcall__(cls, cartan_type, *args, **options):22"""23TESTS::2425sage: from sage.libs.coxeter3.coxeter_group import CoxeterGroup # optional - coxeter326sage: CoxeterGroup(['B',2]) # optional - coxeter327Coxeter group of type ['B', 2] implemented by Coxeter32829"""30from sage.combinat.all import CartanType31ct = CartanType(cartan_type)32return super(CoxeterGroup, cls).__classcall__(cls, ct, *args, **options)3334def __init__(self, cartan_type):35"""36TESTS::3738sage: from sage.libs.coxeter3.coxeter_group import CoxeterGroup # optional - coxeter339sage: CoxeterGroup(['A',2]) # optional - coxeter340Coxeter group of type ['A', 2] implemented by Coxeter341sage: TestSuite(CoxeterGroup(['A',2])).run() # optional - coxeter342"""43Parent.__init__(self, category=(FiniteCoxeterGroups() if cartan_type.is_finite() else CoxeterGroups()))44self._coxgroup = get_CoxGroup(cartan_type)45self._cartan_type = cartan_type4647def _repr_(self):48"""49EXAMPLES::5051sage: W = CoxeterGroup(['A', 3], implementation='coxeter3'); W # optional - coxeter3 # indirect doctest52Coxeter group of type ['A', 3] implemented by Coxeter353sage: W = CoxeterGroup(['A', 3, 1], implementation='coxeter3'); W # optional - coxeter354Coxeter group of type ['A', 3, 1] implemented by Coxeter355"""56return "Coxeter group of type %s implemented by Coxeter3"%(self.cartan_type())5758def __iter__(self):59"""60EXAMPLES::6162sage: W = CoxeterGroup(['A', 2], implementation='coxeter3') # optional - coxeter363sage: list(W) # optional - coxeter364[[], [1], [2], [1, 2], [2, 1], [1, 2, 1]]65"""66for x in self._coxgroup:67yield CoxeterGroup.Element(self, x)6869def cartan_type(self):70"""71Return the Cartan type for this Coxeter group.7273EXAMPLES::7475sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter376sage: W.cartan_type() # optional - coxeter377['A', 3]78"""79return self._cartan_type8081def index_set(self):82"""83Return the index set for the generators of this Coxeter group.8485EXAMPLES::8687sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter388sage: W.index_set() # optional - coxeter389[1, 2, 3]90sage: C = CoxeterGroup(['A', 3,1], implementation='coxeter3') # optional - coxeter391sage: C.index_set() # optional - coxeter392[0, 1, 2, 3]93"""94return self.cartan_type().index_set()95#return range(1, self.rank()+1)9697def bruhat_interval(self, u, v):98"""99Return the Bruhat interval between ``u`` and ``v``.100101EXAMPLES::102103sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3104sage: W.bruhat_interval([1],[3,1,2,3]) # optional - coxeter3105[[1], [1, 2], [1, 3], [1, 2, 3], [1, 3, 2], [1, 2, 3, 2]]106"""107u, v = self(u), self(v)108return self._coxgroup.bruhat_interval(u.value, v.value)109110def cardinality(self):111"""112Return the cardinality of this Coxeter group.113114EXAMPLES::115116sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3117sage: W.cardinality() # optional - coxeter311824119"""120return self._coxgroup.order()121122def one(self):123"""124Return the identity element of this Coxeter group.125126EXAMPLES::127128sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3129sage: W.one() # optional - coxeter3130[]131132"""133return self([])134135def simple_reflections(self):136"""137Return the family of generators for this Coxeter group.138139EXAMPLES::140141sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3142sage: s = W.simple_reflections() # optional - coxeter3143sage: s[2]*s[1]*s[2] # optional - coxeter3144[2, 1, 2]145"""146from sage.combinat.family import Family147return Family(self.index_set(), lambda i: self([i]))148149gens = simple_reflections150151def rank(self):152"""153Return the rank of this coxeter group, that is, the number of generators.154155EXAMPLES::156157sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3158sage: W.rank() # optional - coxeter31593160"""161return self._coxgroup.rank()162163def is_finite(self):164"""165Return True if this is a finite Coxeter group.166167EXAMPLES::168169sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3170sage: W.is_finite() # optional - coxeter3171True172"""173return self._coxgroup.is_finite()174175def length(self, x):176"""177Return the length of an element ``x`` in this Coxeter group.178This is just the length of a reduced word for ``x``.179180EXAMPLES::181182sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3183sage: W.length(W([1,2])) # optional - coxeter31842185sage: W.length(W([1,1])) # optional - coxeter31860187188"""189return len(x.value)190191@cached_method192def coxeter_matrix(self):193"""194Return the Coxeter matrix for this Coxeter group.195196The columns and rows are ordered according to the result of197:meth:`index_set`.198199EXAMPLES::200201sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3202sage: W.coxeter_matrix() # optional - coxeter3203[1 3 2]204[3 1 3]205[2 3 1]206207"""208return self._coxgroup.coxeter_matrix()209210def root_system(self):211"""212Return the root system associated with this Coxeter group.213214EXAMPLES::215216sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3217sage: R = W.root_system(); R # optional - coxeter3218Root system of type ['A', 3]219sage: alpha = R.root_space().basis() # optional - coxeter3220sage: alpha[2] + alpha[3] # optional - coxeter3221alpha[2] + alpha[3]222"""223return self.cartan_type().root_system()224225def _an_element_(self):226"""227Return an element of this Coxeter group.228229EXAMPLES::230231sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3232sage: W._an_element_() # optional - coxeter3233[]234235"""236return self([])237238def m(self, i, j):239"""240Return the entry in the Coxeter matrix between the generator241with label ``i`` and the generator with label ``j``.242243EXAMPLES::244245sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3246sage: W.m(1,1) # optional - coxeter32471248sage: W.m(1,0) # optional - coxeter32492250"""251return self.coxeter_matrix()[i-1,j-1]252253def kazhdan_lusztig_polynomial(self, u, v, constant_term_one=True):254r"""255Return the Kazhdan-Lusztig polynomial `P_{u,v}`.256257INPUT:258259- ``u``, ``v`` -- elements of the underlying Coxeter group260- ``constant_term_one`` -- (default: True) True uses the constant equals one convention,261False uses the Leclerc-Thibon convention262263.. SEEALSO::264265- :class:`~sage.combinat.kazhdan_lusztig.KazhdanLusztigPolynomial`266- :meth:`parabolic_kazhdan_lusztig_polynomial`267268EXAMPLES::269270sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3271sage: W.kazhdan_lusztig_polynomial([], [1,2, 1]) # optional - coxeter32721273sage: W.kazhdan_lusztig_polynomial([1],[3,2]) # optional - coxeter32740275sage: W = CoxeterGroup(['A',3],implementation='coxeter3') # optional - coxeter3276sage: W.kazhdan_lusztig_polynomial([2],[2,1,3,2]) # optional - coxeter3277q + 1278279.. NOTE::280281Coxeter3, as well as Sage's native implementation in282:class:`~sage.combinat.kazhdan_lusztig.KazhdanLusztigPolynomial`283use the convention under which Kazhdan-Lusztig284polynomials give the change of basis from the `(C_w)_{w\in W}`285basis to the `(T_w)_{w\in W}` of the Hecke algebra of `W` with286parameters `q` and `q^{-1}`:287288.. MATH:: C_w = \sum_u P_{u,w} T_w289290In particular, `P_{u,u}=1`::291292sage: all(W.kazhdan_lusztig_polynomial(u,u) == 1 for u in W) # optional - coxeter3293True294295This convention differs from Theorem 2.7 in [LeclercThibon1998]_ by:296297.. MATH::298299{}^{LT} P_{y,w}(q) = q^{\ell(w)-\ell(y)} P_{y,w}(q^{-2})300301To access the Leclerc-Thibon convention use::302303sage: W = CoxeterGroup(['A',3],implementation='coxeter3') # optional - coxeter3304sage: W.kazhdan_lusztig_polynomial([2],[2,1,3,2],constant_term_one=False) # optional - coxeter3305q^3 + q306307TESTS:308309We check that Coxeter3 and Sage's implementation give the same results::310311sage: C = CoxeterGroup(['B', 3], implementation='coxeter3') # optional - coxeter3312sage: W = WeylGroup("B3",prefix="s")313sage: [s1,s2,s3]=W.simple_reflections()314sage: R.<q>=LaurentPolynomialRing(QQ)315sage: KL=KazhdanLusztigPolynomial(W,q)316sage: all(KL.P(1,w) == C.kazhdan_lusztig_polynomial([],w.reduced_word()) for w in W) # optional - coxeter3 # long (15s)317True318"""319u, v = self(u), self(v)320p = u.value.kazhdan_lusztig_polynomial(v.value)321if constant_term_one:322return u.value.kazhdan_lusztig_polynomial(v.value)323q = p.parent().gen()324return q**(v.length()-u.length())*p.substitute(q=q**(-2))325326def parabolic_kazhdan_lusztig_polynomial(self, u, v, J, constant_term_one=True):327"""328Return the parabolic Kazhdan-Lusztig polynomial `P_{u,v}^{-,J}`.329330INPUT:331332- ``u``, ``v`` -- minimal length coset representatives of `W/W_J` for this Coxeter group `W`333- ``J`` -- a subset of the index set of ``self`` specifying the parabolic subgroup334335This method implements the parabolic Kazhdan-Lusztig polynomials336`P^{-,J}_{u,v}` of [Deodhar1987]_, which are defined as337`P^{-,J}_{u,v} = \sum_{z\in W_J} (-1)^{\ell(z)} P_{yz,w}(q)`338with the conventions in Sage.339As for :meth:`kazhdan_lusztig_polynomial` the convention340differs from Theorem 2.7 in [LeclercThibon1998]_ by:341342.. MATH::343344{}^{LT} P_{y,w}^{-,J}(q) = q^{\ell(w)-\ell(y)} P_{y,w}^{-,J}(q^{-2})345346REFERENCES:347348.. [Deodhar1987] V.V. Deodhar, On some geometric aspects of Bruhat orderings II. The parabolic analogue of Kazhdan-Lusztig polynomials, J. Alg. 111 (1987) 483-506.349350.. [LeclercThibon1998] B. Leclerc, J.-Y. Thibon, Littlewood-Richardson coefficients and Kazhdan-Lusztig polynomials, http://front.math.ucdavis.edu/9809.5122351352EXAMPLES::353354sage: W = CoxeterGroup(['A',3], implementation='coxeter3') # optional - coxeter3355sage: W.parabolic_kazhdan_lusztig_polynomial([],[3,2],[1,3]) # optional - coxeter33560357sage: W.parabolic_kazhdan_lusztig_polynomial([2],[2,1,3,2],[1,3]) # optional - coxeter3358q359360sage: C = CoxeterGroup(['A',3,1], implementation='coxeter3') # optional - coxeter3361sage: C.parabolic_kazhdan_lusztig_polynomial([],[1],[0]) # optional - coxeter33621363sage: C.parabolic_kazhdan_lusztig_polynomial([],[1,2,1],[0]) # optional - coxeter33641365sage: C.parabolic_kazhdan_lusztig_polynomial([],[0,1,0,1,2,1],[0]) # optional - coxeter3366q367sage: w=[1, 2, 1, 3, 0, 2, 1, 0, 3, 0, 2]368sage: v=[1, 2, 1, 3, 0, 1, 2, 1, 0, 3, 0, 2, 1, 0, 3, 0, 2]369sage: C.parabolic_kazhdan_lusztig_polynomial(w,v,[1,3]) # optional - coxeter3370q^2 + q371sage: C.parabolic_kazhdan_lusztig_polynomial(w,v,[1,3],constant_term_one=False) # optional - coxeter3372q^4 + q^2373374TESTS::375376sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3377sage: type(W.parabolic_kazhdan_lusztig_polynomial([2],[],[1])) # optional - coxeter3378<type 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>379"""380from sage.rings.all import ZZ381u = self(u)382v = self(v)383if any(d in J for d in u.descents()) or any(d in J for d in v.descents()):384raise ValueError, "u and v have to be minimal coset representatives"385P = ZZ['q']386q = P.gen()387subgroup = [ z for z in self.weak_order_ideal(lambda x: set(x.descents()).issubset(set(J))) if (u*z).bruhat_le(v) ]388if constant_term_one:389return P.sum((-1)**(z.length())*self.kazhdan_lusztig_polynomial(u*z,v) for z in subgroup)390return P.sum((-q)**(z.length())*self.kazhdan_lusztig_polynomial(u*z,v, constant_term_one=False) for z in subgroup)391392393class Element(ElementWrapper):394wrapped_class = CoxGroupElement395396def __init__(self, parent, x):397"""398TESTS::399400sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3401sage: W([2,1,2]) # optional - coxeter3402[1, 2, 1]403"""404if not isinstance(x, CoxGroupElement):405x = CoxGroupElement(parent._coxgroup, x).reduced()406ElementWrapper.__init__(self, parent, x)407408def _repr_(self):409"""410TESTS::411412sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3413sage: W([1,2,1]) # indirect doctest # optional - coxeter3414[1, 2, 1]415"""416return repr(self.value)417418def __iter__(self):419"""420Return an iterator for the elements in the reduced word.421422EXAMPLES::423424sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3425sage: w = W([1,2,1]) # optional - coxeter3426sage: list(iter(w)) # optional - coxeter3427[1, 2, 1]428"""429return iter(self.value)430431def coatoms(self):432"""433Return the coatoms (or co-covers) of this element in the Bruhat order.434435EXAMPLES::436437sage: W = CoxeterGroup(['B', 3], implementation='coxeter3') # optional - coxeter3438sage: w = W([1,2,3]) # optional - coxeter3439sage: w.coatoms() # optional - coxeter3440[[2, 3], [1, 3], [1, 2]]441"""442W = self.parent()443return [W(w) for w in self.value.coatoms()]444445def __cmp__(self, other):446"""447Return lexicographic comparison of ``self`` and ``other``.448449EXAMPLES::450451sage: W = CoxeterGroup(['B', 3], implementation='coxeter3') # optional - coxeter3452sage: w = W([1,2,3]) # optional - coxeter3453sage: v = W([3,1,2]) # optional - coxeter3454sage: w.__cmp__(v) # optional - coxeter3455-1456sage: v.__cmp__(w) # optional - coxeter34571458"""459if type(self) is not type(other):460return cmp(type(self), type(other))461return cmp(list(self), list(other))462463def reduced_word(self):464"""465Return the reduced word of ``self``.466467EXAMPLES::468469sage: W = CoxeterGroup(['B', 3], implementation='coxeter3') # optional - coxeter3470sage: w = W([1,2,3]) # optional - coxeter3471sage: w.reduced_word() # optional - coxeter3472[1, 2, 3]473"""474return list(self)475476def __invert__(self):477"""478Return the inverse of this Coxeter group element.479480EXAMPLES::481482sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3483sage: w = W([1,2,3]) # optional - coxeter3484sage: ~w # optional - coxeter3485[3, 2, 1]486"""487return self.parent()(~self.value)488489inverse = __invert__490491def __getitem__(self, i):492"""493EXAMPLES::494495sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3496sage: w0 = W([1,2,1]) # optional - coxeter3497sage: w0[0] # optional - coxeter34981499sage: w0[1] # optional - coxeter35002501502"""503if i >= len(self):504raise IndexError505return self.value[i]506507def _mul_(self, y):508"""509EXAMPLES::510511sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3512sage: s = W.gens() # optional - coxeter3513sage: s[1]._mul_(s[1]) # optional - coxeter3514[]515sage: s[1]*s[2]*s[1] # optional - coxeter3516[1, 2, 1]517"""518result = self.value * y.value519return self.parent()(result)520521def __eq__(self, y):522"""523Return whether this Coxeter group element is equal to ``y``.524525This is computed by computing the normal form of both elements.526527EXAMPLES::528529sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3530sage: W([1,2,1]) == W([2,1,2]) # optional - coxeter3531True532sage: W([1,2,1]) == W([2,1]) # optional - coxeter3533False534535"""536if not isinstance(y, self.parent().element_class):537return False538539return list(self) == list(y)540541def __len__(self):542"""543EXAMPLES::544545sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3546sage: len(W([1,2,1])) # optional - coxeter35473548"""549return self.parent().length(self)550551552def bruhat_le(self, v):553"""554Return whether ``self`` `\le` ``v`` in Bruhat order.555556EXAMPLES::557558sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3559sage: W([]).bruhat_le([1,2,1]) # optional - coxeter3560True561"""562v = self.parent()(v)563return self.value.bruhat_le(v.value)564565def poincare_polynomial(self):566"""567Return the Poincare polynomial associated with this element.568569EXAMPLES::570571sage: W = CoxeterGroup(['A', 2], implementation='coxeter3') # optional - coxeter3572sage: W.long_element().poincare_polynomial() # optional - coxeter3573t^3 + 2*t^2 + 2*t + 1574sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3575sage: W([2,1,3,2]).poincare_polynomial() # optional - coxeter3576t^4 + 4*t^3 + 5*t^2 + 3*t + 1577sage: W([1,2,3,2,1]).poincare_polynomial() # optional - coxeter3578t^5 + 4*t^4 + 6*t^3 + 5*t^2 + 3*t + 1579580sage: rw = sage.combinat.permutation.from_reduced_word # optional - coxeter3581sage: p = map(attrcall('poincare_polynomial'), W) # optional - coxeter3582sage: [rw(w.reduced_word()) for i,w in enumerate(W) if p[i] != p[i].reverse()] # optional - coxeter3583[[3, 4, 1, 2], [4, 2, 3, 1]]584"""585return self.value.poincare_polynomial()586587def has_right_descent(self, i):588"""589Return whether ``i`` is a right descent of this element.590591EXAMPLES::592593sage: W = CoxeterGroup(['A', 4], implementation='coxeter3') # optional - coxeter3594sage: W([1,2]).has_right_descent(1) # optional - coxeter3595False596sage: W([1,2]).has_right_descent(2) # optional - coxeter3597True598"""599return i in self.value.right_descents()600601def has_left_descent(self, i):602"""603Return True if ``i`` is a left descent of this element.604605EXAMPLES::606607sage: W = CoxeterGroup(['A', 4], implementation='coxeter3') # optional - coxeter3608sage: W([1,2]).has_left_descent(1) # optional - coxeter3609True610sage: W([1,2]).has_left_descent(2) # optional - coxeter3611False612"""613return i in self.value.left_descents()614615def action(self, v):616"""617Return the action of of this Coxeter group element on the root space.618619INPUT:620621- ``v`` -- an element of the root space associated with the Coxeter group for ``self``622623EXAMPLES::624625sage: W = CoxeterGroup(['B', 3], implementation='coxeter3') # optional - coxeter3626sage: R = W.root_system().root_space() # optional - coxeter3627sage: v = R.an_element(); v # optional - coxeter36282*alpha[1] + 2*alpha[2] + 3*alpha[3]629sage: w = W([1,2,3]) # optional - coxeter3630sage: w.action(v) # optional - coxeter3631-alpha[1] + alpha[2] + alpha[3]632"""633#TODO: Find a better way to do this634W = self.parent().root_system().root_space().weyl_group()635w = W.from_reduced_word(list(self))636return w.action(v)637638def action_on_rational_function(self, f):639r"""640Return the natural action of this Coxeter group element on a641polynomial considered as an element of `S(\mathfrak{h}^*)`.642643.. NOTE::644645Note that the number of variables in the polynomial646ring must correspond to the rank of this Coxeter647group. The ordering of the variables is assumed to648coincide with the result of :meth:`index_set`.649650EXAMPLES::651652sage: W = CoxeterGroup(['A', 3], implementation='coxeter3') # optional - coxeter3653sage: S = PolynomialRing(QQ, 'x,y,z').fraction_field() # optional - coxeter3654sage: x,y,z = S.gens() # optional - coxeter3655sage: W([1]).action_on_rational_function(x+y+z) # optional - coxeter3656(x^2*y + x*z + 1)/x657sage: W([2]).action_on_rational_function(x+y+z) # optional - coxeter3658(x*y^2 + y^2*z + 1)/y659sage: W([3]).action_on_rational_function(x+y+z) # optional - coxeter3660(y*z^2 + x*z + 1)/z661"""662Q = f.parent()663Q_gens = Q.gens()664W = self.parent()665R = W.root_system().root_space()666alpha = R.basis()667n = W.rank()668669if Q.ngens() != n:670raise ValueError, "the number of generators for the polynomial ring must be the same as the rank of the root system"671672basis_elements = [alpha[i] for i in W.index_set()]673basis_to_order = dict([(s, i) for i, s in enumerate(W.index_set())])674675results = []676for poly in [f.numerator(), f.denominator()]:677result = 0678exponents = poly.exponents()679680for exponent in exponents:681#Construct something in the root lattice from the exponent vector682exponent = sum([e*b for e, b in zip(exponent, basis_elements)])683exponent = self.action(exponent)684685monomial = 1686for s, c in exponent.monomial_coefficients().iteritems():687monomial *= Q_gens[basis_to_order[s]]**int(c)688689result += monomial690691results.append(result)692693numerator, denominator = results694return numerator / denominator695696697