Ask Your Question
3

Lusztig's a-function for the symmetric group via Sage

asked 2020-08-13 20:20:42 +0100

klaaa gravatar image

updated 2022-02-11 21:24:19 +0100

FrédéricC gravatar image

Given a Weyl group $W$, Lusztig's $a$-function from W to the natural numbers is defined as a function constant on two-sided cells and $a(w)=l(w)-2 d(w)$ when $w$ is an involution, where $l(w)$ is the length function and $d(w)$ is the degree of the Kazhdan-Lusztig polynomial $P_{1,w}$. Since every two-sided cell contains an involution the function a is defined on all of W. See for example before conjecture 15 in https://msp.org/pjm/2007/232-2/pjm-v2... for this definition.

My question is how to obtain the $a$-function for the symmetric group as a Weyl group via Sage.

A more explicit formula in this case is given as follows: Let $x$ be a permutation corresponding to the pair of tableaux $(P(x),Q(x))$ by the Robinson-Schensted correspondence and $\operatorname{shape}(Q(x)')=( \lambda_1,...,\lambda_k)$ where $Q(x)'$ is the transposed tableau. Then $a(x)=\sum\limits_{i=1}^{k}{\binom{\lambda_i}{2}}$, see for example exercise 10 on page 198 in the book by Björner and Brenti "Combinatorics of Coxeter Groups".

The values of the function can be seen for example for the symmetric group on 3 symbols on top of page 323 of https://msp.org/pjm/2007/232-2/pjm-v2... .

edit retag flag offensive close merge delete
add a comment

1 Answer

Sort by » oldest newest most voted
2

answered 2020-08-14 18:03:38 +0100

dan_fulea gravatar image

updated 2020-08-14 18:10:11 +0100

From the first definition in the OP, it is enough to compute the $a$-funcition on involutions. Here is a simple piece of code doing this in a verbose form for $S_3$, the group of permutations of the set ${1,2,3}$:

W = WeylGroup('A2', prefix='s')                                                                                                       
print(f"W = {W}")
print(f"W has order |W| = {W.order()}\n")

R.<q> = LaurentPolynomialRing(QQ)                                                                                                     
KL = KazhdanLusztigPolynomial(W, q)                                                                                                   
involutions = [w for w in W if w.order() in (1, 2)]

for w in involutions:
    lw = w.length()
    pw = KL.P( W(1), w )
    dw = pw.degree()
    aw = lw - 2*dw
    print(f"w = {w} = {w.to_permutation()} has:\n"
          f"l(w) = {lw}\n"
          f"d(w) = deg P(1,w) = deg( {pw} ) = {dw}\n"
          f"a(w) = l(w) - 2d(w) = {aw}\n")

Results:

W = Weyl Group of type ['A', 2] (as a matrix group acting on the ambient space)
W has order |W| = 6

w = 1 = (1, 2, 3) has:
l(w) = 0
d(w) = deg P(1,w) = deg( 1 ) = 0
a(w) = l(w) - 2d(w) = 0

w = s1 = (2, 1, 3) has:
l(w) = 1
d(w) = deg P(1,w) = deg( 1 ) = 0
a(w) = l(w) - 2d(w) = 1

w = s2 = (1, 3, 2) has:
l(w) = 1
d(w) = deg P(1,w) = deg( 1 ) = 0
a(w) = l(w) - 2d(w) = 1

w = s1*s2*s1 = (3, 2, 1) has:
l(w) = 3
d(w) = deg P(1,w) = deg( 1 ) = 0
a(w) = l(w) - 2d(w) = 3

(All K-L polynomials are trivial.) To do the same for the group $S_4$, using a less verbose output...

W = WeylGroup('A3', prefix='s')                                                                                                       
print(f"W = {W}")
print(f"W has order |W| = {W.order()}\n")

R.<q> = LaurentPolynomialRing(QQ)                                                                                                     
KL = KazhdanLusztigPolynomial(W, q)                                                                                                   
involutions = [w for w in W if w.order() in (1, 2)]

for w in involutions:
    lw = w.length()
    pw = KL.P( W(1), w )
    dw = pw.degree()
    aw = lw - 2*dw
    print(f"w = {w} = {w.to_permutation()} has:\n"
          f"a(w) = l(w) - 2d(w) = {lw} - 2deg({pw}) = {aw}\n")

Results:

W = Weyl Group of type ['A', 3] (as a matrix group acting on the ambient space)
W has order |W| = 24

w = 1 = (1, 2, 3, 4) has:
a(w) = l(w) - 2d(w) = 0 - 2deg(1) = 0

w = s3 = (1, 2, 4, 3) has:
a(w) = l(w) - 2d(w) = 1 - 2deg(1) = 1

w = s2 = (1, 3, 2, 4) has:
a(w) = l(w) - 2d(w) = 1 - 2deg(1) = 1

w = s2*s3*s2 = (1, 4, 3, 2) has:
a(w) = l(w) - 2d(w) = 3 - 2deg(1) = 3

w = s2*s3*s1*s2 = (3, 4, 1, 2) has:
a(w) = l(w) - 2d(w) = 4 - 2deg(1 + q) = 2

w = s1 = (2, 1, 3, 4) has:
a(w) = l(w) - 2d(w) = 1 - 2deg(1) = 1

w = s3*s1 = (2, 1, 4, 3) has:
a(w) = l(w) - 2d(w) = 2 - 2deg(1) = 2

w = s1*s2*s3*s2*s1 = (4, 2, 3, 1) has:
a(w) = l(w) - 2d(w) = 5 - 2deg(1 + q) = 3

w = s1*s2*s1 = (3, 2, 1, 4) has:
a(w) = l(w) - 2d(w) = 3 - 2deg(1) = 3

w = s1*s2*s3*s1*s2*s1 = (4, 3, 2, 1) has:
a(w) = l(w) - 2d(w) = 6 - 2deg(1) = 6

I would like to have the KL-cells inside sage, but i do not know how to get them now.

Personal note: There was some years ago the chance to use gap3+chevie, then make sage know about them, then get the corresponding information from chevie. Since gap4 i no longer use gap. After repeated switches between linux distros and linux reinstallations, i decided that it is simpler to rewrite all pieces of code inside chevie to be inside sage. But i need time and some support... maybe this could be a project for this year.

Let's try to get the same numbers using the RSK correspondence. The code results are also formatted to be printed in an array...

W = WeylGroup('A3', prefix='s')                                                                                                       
print(f"W = {W}")
print(f"W has order |W| = {W.order()}\n")


R.<q> = LaurentPolynomialRing(QQ)                                                                                                     
KL = KazhdanLusztigPolynomial(W, q)

def a_involution(w):
    lw = w.length()
    pw = KL.P( W(1), w )
    dw = pw.degree()
    aw = lw - 2*dw
    return aw

def a_page198(shape):
    return sum([binomial(entry, 2) for entry in shape])

def transposed_shape(shape):
    """this should be a basic method, but i could not find it...
    For the shape [3,2,2,1] we return [4,3,1] and conversely...

    [3,2,2,1] is     [4,3,1] is
    XXX              XXXX
    XX               XXX
    XX               X
    X
    """
    n = shape[0]
    return [len([rowlength for rowlength in shape if rowlength > k]) for k in range(n)]

for w in W:
    wp = w.to_permutation()
    Q = RSK( list(wp) )[1]
    sh = list(Q.shape())
    sht = transposed_shape(sh)
    if w.order() in (1, 2):
        a_inv = a_involution(w)
    else:
        a_inv = ''
    aw = a_page198(sht)
    print(r"{} & {} & {} & {} & {} & {} & {}\\\hline"
          .format(latex(w), wp, Q, sh, sht, a_inv, aw))

Results:

W = Weyl Group of type ['A', 2] (as a matrix group acting on the ambient space)
W has order |W| = 6

1 & (1, 2, 3) & [[1, 2, 3]] & [3] & [1, 1, 1] & 0 & 0\\\hline
s_{1}s_{2} & (2, 3, 1) & [[1, 2], [3]] & [2, 1] & [2, 1] &  & 1\\\hline
s_{2}s_{1} & (3, 1, 2) & [[1, 3], [2]] & [2, 1] & [2, 1] &  & 1\\\hline
s_{1} & (2, 1, 3) & [[1, 3], [2]] & [2, 1] & [2, 1] & 1 & 1\\\hline
s_{2} & (1, 3, 2) & [[1, 2], [3]] & [2, 1] & [2, 1] & 1 & 1\\\hline
s_{1}s_{2}s_{1} & (3, 2, 1) & [[1], [2], [3]] & [1, 1, 1] & [3] & 3 & 3\\\hline

In latex: $$ \begin{array}[|l|c|l|l|l|r|r|] \hline w\in W & w\in S_3 & Q &\text{shape}(Q) &\text{shape}(Q)^t & a\text{ if inv.} &a\\\hline\hline 1 & (1, 2, 3) & [[1, 2, 3]] & [3] & [1, 1, 1] & 0 & 0\\\hline s_{1}s_{2} & (2, 3, 1) & [[1, 2], [3]] & [2, 1] & [2, 1] & & 1\\\hline s_{2}s_{1} & (3, 1, 2) & [[1, 3], [2]] & [2, 1] & [2, 1] & & 1\\\hline s_{1} & (2, 1, 3) & [[1, 3], [2]] & [2, 1] & [2, 1] & 1 & 1\\\hline s_{2} & (1, 3, 2) & [[1, 2], [3]] & [2, 1] & [2, 1] & 1 & 1\\\hline s_{1}s_{2}s_{1} & (3, 2, 1) & [[1], [2], [3]] & [1, 1, 1] & [3] & 3 & 3\\\hline \end{array} $$

Let us do the same also for the $A_3$ case. The code remains, we only change the type in the WeylGroup constructor to A3, the result is in a table...

Later edit: the hline's are not parsed here, so i remove them... (Same computing code, the one print format is changed.) $$ \begin{array}[|l|c|l|l|l|r|r|] \\ w\in W & w\in S_3 & Q &\text{shape}(Q) &\text{shape}(Q)^t & a\text{ if inv.} &a\\\\ 1 & (1, 2, 3, 4) & [[1, 2, 3, 4]] & [4] & [1, 1, 1, 1] & 0 & 0\\ s_{3} & (1, 2, 4, 3) & [[1, 2, 3], [4]] & [3, 1] & [2, 1, 1] & 1 & 1\\ s_{3}s_{2} & (1, 4, 2, 3) & [[1, 2, 4], [3]] & [3, 1] & [2, 1, 1] & & 1\\ s_{3}s_{2}s_{1} & (4, 1, 2, 3) & [[1, 3, 4], [2]] & [3, 1] & [2, 1, 1] & & 1\\ s_{2} & (1, 3, 2, 4) & [[1, 2, 4], [3]] & [3, 1] & [2, 1, 1] & 1 & 1\\ s_{2}s_{3} & (1, 3, 4, 2) & [[1, 2, 3], [4]] & [3, 1] & [2, 1, 1] & & 1\\ s_{2}s_{3}s_{2} & (1, 4, 3, 2) & [[1, 2], [3], [4]] & [2, 1, 1] & [3, 1] & 3 & 3\\ s_{2}s_{3}s_{2}s_{1} & (4, 1, 3, 2) & [[1, 3], [2], [4]] & [2, 1, 1] & [3, 1] & & 3\\ s_{2}s_{1} & (3, 1, 2, 4) & [[1, 3, 4], [2]] & [3, 1] & [2, 1, 1] & & 1\\ s_{2}s_{3}s_{1} & (3, 1, 4, 2) & [[1, 3], [2, 4]] & [2, 2] & [2, 2] & & 2\\ s_{2}s_{3}s_{1}s_{2} & (3, 4, 1, 2) & [[1, 2], [3, 4]] & [2, 2] & [2, 2] & 2 & 2\\ s_{2}s_{3}s_{1}s_{2}s_{1} & (4, 3, 1, 2) & [[1, 4], [2], [3]] & [2, 1, 1] & [3, 1] & & 3\\ s_{1} & (2, 1, 3, 4) & [[1, 3, 4], [2]] & [3, 1] & [2, 1, 1] & 1 & 1\\ s_{3}s_{1} & (2, 1, 4, 3) & [[1, 3], [2, 4]] & [2, 2] & [2, 2] & 2 & 2\\ s_{3}s_{1}s_{2} & (2, 4, 1, 3) & [[1, 2], [3, 4]] & [2, 2] & [2, 2] & & 2\\ s_{3}s_{1}s_{2}s_{1} & (4, 2, 1, 3) & [[1, 4], [2], [3]] & [2, 1, 1] & [3, 1] & & 3\\ s_{1}s_{2} & (2, 3, 1, 4) & [[1, 2, 4], [3]] & [3, 1] & [2, 1, 1] & & 1\\ s_{1}s_{2}s_{3} & (2, 3, 4, 1) & [[1, 2, 3], [4]] & [3, 1] & [2, 1, 1] & & 1\\ s_{1}s_{2}s_{3}s_{2} & (2, 4, 3, 1) & [[1, 2], [3], [4]] & [2, 1, 1] & [3, 1] & & 3\\ s_{1}s_{2}s_{3}s_{2}s_{1} & (4, 2, 3, 1) & [[1, 3], [2], [4]] & [2, 1, 1] & [3, 1] & 3 & 3\\ s_{1}s_{2}s_{1} & (3, 2, 1, 4) & [[1, 4], [2], [3]] & [2, 1, 1] & [3, 1] & 3 & 3\\ s_{1}s_{2}s_{3}s_{1} & (3, 2, 4, 1) & [[1, 3], [2], [4]] & [2, 1, 1] & [3, 1] & & 3\\ s_{1}s_{2}s_{3}s_{1}s_{2} & (3, 4, 2, 1) & [[1, 2], [3], [4]] & [2, 1, 1] & [3, 1] & & 3\\ s_{1}s_{2}s_{3}s_{1}s_{2}s_{1} & (4, 3, 2, 1) & [[1], [2], [3], [4]] & [1, 1, 1, 1] & [4] & 6 & 6\\ \end{array} $$

edit flag offensive delete link more

Comments

Thank you very much!

klaaa gravatar imageklaaa ( 2020-08-14 20:28:49 +0100 )edit

A small question: Your code seems very nice but I am not able to understand it completely as I am relatively new to sage. How do I have to modify it so that it returns $a(w_0 w)$ instead of $a(w)$, where $w_0$ is the longest element in the symmetric group which is the permutation [n,n-1,n-2,...,3,2,1].

klaaa gravatar imageklaaa ( 2020-08-14 20:44:41 +0100 )edit

One can add u=W.w0 print(u) to your code and then use return au*w instead of return aw in your code for def a_involutio(w). But this gives an error and I do not understand why or how to fix it.

klaaa gravatar imageklaaa ( 2020-08-14 21:05:19 +0100 )edit

Nevermind, I managed to do it by changing the last part of your code. Thanks again!

klaaa gravatar imageklaaa ( 2020-08-14 21:55:32 +0100 )edit
add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

subscribe to rss feed

Stats

Asked: 2020-08-13 20:20:42 +0100

Seen: 444 times

Last updated: Aug 14 '20

Related questions

multi-symmetric functions and multi-partitions

A Combinatorics Problem - Product Rule Indices

Iterator for conjugacy classes of Sn

Dictating the roots to RootSystem

iterating over a combinatorial class

Can I create these sequences with Sage?

A proper combinatorics tutorial?

How to make a vector space with basis a *graded* one, and how to do linear algebra on its homogeneous parts?

All decompositions of a prime as a sum of four squares

S3's elements

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59