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

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 close merge delete

Sort by » oldest newest most voted

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

more

Thank you very much!

( 2020-08-14 13:28:49 -0500 )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].

( 2020-08-14 13:44:41 -0500 )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.

( 2020-08-14 14:05:19 -0500 )edit

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

( 2020-08-14 14:55:32 -0500 )edit