羅 新， 王利萍

(北京建筑大學(xué) 理學(xué)院，北京102616)

1 引 言

1979年，Kazhdan和Lusztig提出了著名的Kazhdan-Lusztig理論.胞腔是該理論中的一個主要研究對象.為了研究Coxeter群的相關(guān)代數(shù)結(jié)構(gòu)，Kazhdan和Lusztig根據(jù)左(右)等價關(guān)系，把群元素劃分成不同的等價類，即雙邊胞腔、左(右)胞腔[1].當(dāng)W是一個Weyl群時，Barbasch, Lusztig, Joseph, Vogan等人對其胞腔進行了研究.Weyl群中胞腔在李型群的表示理論以及半單李代數(shù)的普遍包絡(luò)代數(shù)的本原理想理論中都有重要的應(yīng)用[2].

對于對稱群Sn，它有著很好的組合方面的結(jié)論和性質(zhì)，更希望有方便好用的工具可以描述和計算對稱群的雙邊胞腔(或左胞腔、右胞腔)，從而應(yīng)用到表示理論中.文章主要分為三部分，首先介紹了對稱群以及胞腔等基本概念，并且指出了Sn內(nèi)不等價的不可約表示、其每一個左胞腔所對應(yīng)的W-圖與n的整數(shù)無序劃分之間存在關(guān)系；其次，通過計算機編程，實現(xiàn)了用Matlab構(gòu)建標準Young表，對于對稱群中的任意一個置換，可以很快得出其所對應(yīng)的標準Young表；最后，運用程序給出了一類對稱群所對應(yīng)的雙邊、右(左)胞腔的個數(shù).

2 預(yù)備知識

2.1 雙邊胞腔及左(右)胞腔

定義1[1]對于每一個元素w∈W，令

L(w)∶={s∈S|sw

L(wi-1)?L(wi) (L(wi-1)?L(wi) 或R(wi-1)?R(wi)).

類似的，對應(yīng)于關(guān)系w≤Lu,可以定義w≤Ru. 這些關(guān)系≤L,≤R,≤LR是W上的預(yù)次序.

定義2[1]對于W中的元素w和u，如果滿足關(guān)系w≤Lu≤Lw(w≤LRu≤LRw)，則稱它們滿足關(guān)系w～Lu(w～LRu). 類似的，也可以定義w～Ru. 關(guān)系～L,～R,～LR為W中的等價關(guān)系，它們對應(yīng)的等價類分別稱為W的左胞腔，右胞腔，雙邊胞腔.

2.2 a函數(shù)

定義3[1]給定一個Coxeter群W, A=為整系數(shù)的Laurent多項式環(huán)，q為一個變量，定義在A上的代數(shù)H稱為一個Hecke代數(shù)，H有一組典范基{Cw|w∈W}，即為Kazhdan-Lusztig基.

對于任意一個Coxeter群W，Lusztig首次引入a函數(shù)：a∶W→∪{∞}. 該函數(shù)是研究胞腔以及計算Kazhdan-Lusztig多項式首項系數(shù)的一個極其重要的工具.

給定x,y∈W,有

定義5[7]對任意z∈W,定義

2.3 n的整數(shù)無序劃分與Sn的關(guān)系

定義6[8]整數(shù)無序劃分是指把整數(shù)分解成若干整數(shù)的和，若各部分不允許出現(xiàn)0值時，則稱各部分為類，即

引理1[9]兩個置換g1,g2∈Sn共軛?它們對應(yīng)著n的同一劃分.

由引理1知，Sn的共軛類和n的劃分之間一一對應(yīng)，因此，Sn內(nèi)共軛類的個數(shù)等于n的不同劃分的個數(shù).

引理2[10]設(shè)G是有限群，|G|=g,F是代數(shù)封閉域，且charF=0或charF=p但p不整除|G|，又設(shè)G的共軛類數(shù)為s，則G恰有s個不等價的不可約表示.

對于每一個確定的正整數(shù)n，其所對應(yīng)的對稱群Sn顯然是一個有限群，因此符合引理2，根據(jù)引理1和引理2，可以得到以下結(jié)論：

定理1Sn內(nèi)不等價的不可約表示的個數(shù)等于其所對應(yīng)的共軛類的個數(shù)，并且等于n的整數(shù)無序劃分的個數(shù).

引理3[1]令X是對稱群W=Sn的一個左胞腔，Γ是與X相關(guān)的W-圖，ρ是對應(yīng)于Γ的代數(shù)H的表示，則ρ是不可約的，并且Γ的同構(gòu)類只取決于不可約表示ρ的同構(gòu)類，與X無關(guān).

由引理3知，Sn的每一個左胞腔所對應(yīng)的W-圖Γ的同構(gòu)類與Sn的不可約表示有著緊密的聯(lián)系.

3 R-S法則下的Young表構(gòu)建

對于對稱群W=Sn，定義單反射集S由以下元組成：

si=(i,i+1),i=1,2,…,n-1.

并且規(guī)定Sn中置換的乘法是從右向左的.可以根據(jù)Robinson-Schensted法則來描述W的胞腔分解情況[11].同時，我們也可以較為容易地計算出相應(yīng)對稱群的a函數(shù).

對于整數(shù)n的一個劃分λ，都可以找到一個Young表Fλ與之相對應(yīng).該Young表由n個盒子組成，每一列的長度由λ的分量所確定，且按照Robinson-Schensted法則，用1,2,…,n來填充盒子.如果用來填充盒子的數(shù)字按列從上到下遞增且按行從左到右遞增，就稱該表是一個標準的Young表.該法則定義了一個從Sn到標準Young表對組成的集合上的雙射θ∶w→(P(w),Q(w)).

對任意的i=1,2,…,n，令w(i)=ji，標準Young表定義如下：

令T0是一個Young圖，接下來利用數(shù)學(xué)歸納法，按照法則，把數(shù)字j1,j2,…,jn-1依次填入到n-1個盒子中，這樣便定義好了一個Young表Tn-1. 現(xiàn)在定義Young表Tn：如果jn比Tn-1的第一行中的每一個數(shù)字都大，則在Tn-1的第一行的后面再增加一個盒子，并且用jn標記便得到了Tn；否則在Tn-1中找出比jn大的那個最小的數(shù)字，并把它記為z，此時用jn來替換z，而對于z，按照上面同樣的方法，把它插入到Tn-1表的第二行中，這樣經(jīng)過一系列的比較、替代、換行……，最終得到的Young表就是Tn. 令P(w)=Tn，則它就是一個標準的Young表.相對應(yīng)地，Q(w)∶=P(w-1).

定理2[12]令y,w是Sn中的元素，則有

(i)y～Lw當(dāng)且僅當(dāng)Q(y)=Q(w)；

(ii)y～Rw當(dāng)且僅當(dāng)P(y)=P(w)；

(iii)y～LRw當(dāng)且僅當(dāng)P(y)和P(w)有相同的型.

命題1(i)w,u∈Sn,若a(w)=a(u)且w≤LRu，則有w～LRu[7]；

(ii) 在Sn中，a函數(shù)的不同函數(shù)值的個數(shù)小于等于群所對應(yīng)的雙邊胞腔的個數(shù).w,u∈Sn，若w～LRu，則必有a(w)=a(u)；但反之，若a(w)=a(u)，不一定必有w～LRu，即w,u未必在Sn的同一個雙邊胞腔中；

(iii)w,u∈Sn，若w～LRu，則未必有w～Lu或w～Ru成立.反之，若w～Lu或w～Ru成立，則w～LRu.

例如：在A3型Weyl群中，有s2s1s3～LRs1s3s2，但s2s1s3～Ls1s3s2和s2s1s3～Rs1s3s2均不成立.

給出對稱群中的一個元素，在畫它所對應(yīng)的Young表時，若所給元素的長度較短，則很容易畫出Young表，而一旦所給元素的長度較長，Young表的給出較為困難.因此有必要借助計算機編程，以便更加高效地解決問題.根據(jù)標準Young表的相關(guān)描述，可以很清楚地看到：對于一個給定的Sn中的置換，構(gòu)建標準Young表的過程實際是一個具有遞歸思想的圖表構(gòu)建過程，因此可以應(yīng)用matlab編程[附錄1]，從而快速實現(xiàn)標準Young表的構(gòu)建.

對于任意給出的Sn的置換，可以通過程序來給出它們所對應(yīng)的標準Young表.下面以n=22，30為例：

12711141516369132148122051710191822圖1 置換y對應(yīng)的Young表

137101322232481115253056169121814172619212024272829圖2 置換z所對應(yīng)的Young表

4 Sn的雙邊胞腔及右胞腔

4.1 n的無序劃分與Sn的雙邊胞腔

引理4[8]整數(shù)無序劃分的相關(guān)遞推公式

對于任意的正整數(shù)n，可以運用C語言軟件，根據(jù)整數(shù)無序劃分的要求，得到n的每一種具體的劃分[13].根據(jù)標準Young表的相關(guān)描述，對于n的每一種具體劃分，令第一列有n1個盒子，第二列有n2個盒子，……，第k列有nk個盒子，并且每一列第一個盒子左右水平對齊，這樣就把n的每一種劃分，對應(yīng)到同一種型的Young表，根據(jù)定理2(iii)，可以得出以下定理：

定理3Sn的雙邊胞腔的個數(shù)與n的整數(shù)無序劃分的個數(shù)相等.

對于Sn，由于其雙邊胞腔的個數(shù)，等于n的按遞減排序的劃分個數(shù)，而在排列組合中，符合這種條件的劃分，就是n的無序k-劃分，所以要求Sn的雙邊胞腔的個數(shù)，實際上就是求符合一定條件的n的劃分個數(shù).在這里，根據(jù)引理4中整數(shù)無序劃分的相關(guān)遞推公式，運用matlab[附錄2]編程軟件，快速求出不同的正整數(shù)n所對應(yīng)的劃分個數(shù)Pn，即Sn的雙邊胞腔的個數(shù).

在對稱群Sn中，假設(shè)P(y)是一個型為λ=(λ1≥λ2≥…≥λk)的Young表，則有

根據(jù)a函數(shù)的計算公式，可以很快得到：n的每一種具體劃分，都會對應(yīng)一個a函數(shù)，同時也對應(yīng)一種型的Young表，也即符合這種型的標準Young表所對應(yīng)的Sn中的元素，都在同一個雙邊胞腔中.這樣就把Sn中的元素劃分到了不同的雙邊胞腔中，從而得到了Sn的雙邊胞腔分解.

4.2 Sn的右胞腔個數(shù)

在對Sn中的元素進行標準Young表的構(gòu)建過程中，很容易得到：在同一個雙邊胞腔中的元素，都會對應(yīng)相同型的標準Young表，所以也可以間接通過標準Young表的型數(shù)，來得到雙邊胞腔的個數(shù)，而標準Young表的型數(shù)又是由n的無序劃分所決定的；在同一個右胞腔中的元素，都會對應(yīng)相同的標準Young表.由于當(dāng)n比較大時，n!是一個比較大的數(shù)，所以為了得到Sn所對應(yīng)的右胞腔分解及其個數(shù)，不妨換個角度思考問題：在n的無序k-劃分的基礎(chǔ)上，給出一種具體劃分，便可以得到一種型的Young表，然后用matlab進行編程，把從1到n的這些數(shù)填入這種型的Young表中，保證得到的是標準Young表.通過統(tǒng)計滿足給定型的標準Young表的個數(shù)，便可得到它在這種情況下的右胞腔分解個數(shù)，即這種型所對應(yīng)的雙邊胞腔中包含的右胞腔的個數(shù).這樣把Sn中所有雙邊胞腔所包含的右胞腔的個數(shù)一一都求出來再求和，便可以求出Sn的右胞腔的個數(shù)[附錄3].由于Q(w)=P(w-1)，根據(jù)定理2，可得：在對稱群中，左胞腔的個數(shù)等于右胞腔的個數(shù).

由于計算機內(nèi)存和算法的限制，在這里給出了當(dāng)n≤10時，Sn所對應(yīng)的右胞腔分解個數(shù).當(dāng)n比較大時，Sn所對應(yīng)的雙邊胞腔分解個數(shù)，所受影響較小，在這里只列出當(dāng)n≤20時，Sn的雙邊胞腔分解個數(shù).下面以S4為例：

例其生成元為s1=(12),s2=(23),s3=(34)，并且

4=4=3+1=2+2=2+1+1=1+1+1+1，

W={e,s1,s1s2,s1s2s3,s2,s2s1,s2s3,s3,s3s2,s3s2s1,s3s1,s3s1s2,s2s1s3,s2s1s3s2,s1s2s1,

s1s2s1s3,s1s2s1s3s2,s2s3s2,s2s3s2s1,s2s3s2s1s2,s3s1s2s1,s3s1s2s1s3,s1s2s3s2,s1s2s3s1s2s1}，

得到這些元素所對應(yīng)的標準Young表如下：

1234圖3

1342圖4

1243圖5

1234圖6

1324圖7

1234圖8

1423圖9

1234圖10

1324圖11

1234圖12

根據(jù)定理2，可以得出S4的10個右胞腔為

R1∶{e}；R2∶{s1,s1s2,s1s2s3}；R3∶{s2,s2s1,s2s3}；R4∶{s3,s3s2,s3s2s1}；R5∶{s3s1,s3s1s2};
R6∶{s2s1s3,s2s1s3s2}；R7∶{s1s2s1,s1s2s1s3,s1s2s1s3s2}；R8∶{s2s3s2,s2s3s2s1,s2s3s2s1s2};
R9∶{s3s1s2s1,s3s1s2s1s3,s1s2s3s2}；R10∶{s1s2s3s1s2s1}.

表1 S4的右胞腔所對應(yīng)的Young表及a函數(shù)值

根據(jù)定理2以及整數(shù)4的無序劃分數(shù)目，綜合上面圖表可知，對稱群S4所對應(yīng)的標準Young表有5種型，因此它有5個雙邊胞腔，分別為

由于篇幅限制，以下是運行的部分結(jié)果

表2 Sn所對應(yīng)的右胞腔和雙邊胞腔的個數(shù)

5 結(jié) 論

本文主要借助計算機編程，得出了以下主要研究結(jié)論：

(i) 指出了Sn內(nèi)不等價的不可約表示、其每一個左胞腔所對應(yīng)的W-圖與n的整數(shù)無序劃分之間存在關(guān)系；

(ii) 對于對稱群中的任意一個置換，實現(xiàn)了用Matlab快捷構(gòu)建標準Young表；

(iii) 以n的整數(shù)無序劃分的組合公式為出發(fā)點，運用編程，分別計算了一類對稱群的雙邊胞腔以及右(左)胞腔的個數(shù)；

(iv) 從解決問題的角度出發(fā)，體現(xiàn)了數(shù)學(xué)與計算機的緊密結(jié)合，這將是一段時間內(nèi)解決數(shù)學(xué)問題的有效途徑.

致謝本文的完成得到了海軍航空大學(xué)司守奎教授的幫助，他對本文的部分編程提出了有益的建議.同時，也要感謝審稿人對本文提出的寶貴建議.

附錄1(Young表的構(gòu)建)

clc, clear

m=input(′請輸入正整數(shù)m= ′);

A=[1∶m;randperm(m)]

a=A(2,∶) %生成一個1到n的隨機全排列

n=length(a);

b=cell(1,ceil(n/2)); %初始化細胞數(shù)組

b{1}=a(1); k=1;

for i=2∶n

if all(a(i)>b{1})

b{1}=[b{1},a(i)];

else

ind=find(b{1}>=a(i),1,′first′); %從頭開始找第1個數(shù)

t1=b{1}(ind); b{1}(ind)=a(i);

j=2;

while 1

if length(b{j})<1 %b{j}為空

k=k+1; b{k}=t1; break;

elseif all(t1>b{j})

b{j}=[b{j},t1]; break;

else

ind=find(b{j}>=t1,1,′first′); %從頭開始找第1個數(shù)

t2=b{j}(ind); b{j}(ind)=t1;

t1=t2; j=j+1;

end

end

end

end

b(cellfun(@isempty,b))=[]; %刪除細胞數(shù)組的空元素

celldisp(b) %顯示細胞數(shù)組的所有元素值

附錄2(計算對稱群的雙邊胞腔個數(shù))

clc, clear

n=input(′請輸入正整數(shù)n= ′);

a=eye(n);

for i=2∶n

for j=1∶i-1

if j<=i-j

a(i,j)=sum(a(i-j,[1∶j]));

elseif j>i-j

a(i,j)=sum(a(i-j,[1∶i-j]));

end

end

end

a

m=sum(a(end,∶)) %計算分解的個數(shù)

附錄3(計算對稱群的右胞腔個數(shù))

clc, clear

%m=input(′請輸入n劃分的k元數(shù)組∶ ′)

m=[1 2 3 4]; m=sort(m,′descend′); %按降序排列

n=sum(m); %計算n的取值

L1=length(m); %劃分的個數(shù)

b=perms([1∶n]); %生成1,2，…,n的全排列

L2=size(b,1); %計算全排列的個數(shù)

L=0; %計數(shù)初始化

t=cumsum(m);s=[1,t(1∶end-1)+1]; %每一段數(shù)據(jù)的終點和起點編號

e=cell(1); %初始化細胞數(shù)組

for i=1∶L2

a=2*n*ones(L1,m(1)); %矩陣初始化

c=b(i,∶); %利用第i個全排列

for j=1∶L1

a(j,[1∶m(j)])=sort(c(s(j)∶t(j))); %第i個全排列構(gòu)造的分解

end

d=a; d=sort(d); %逐列按照從小到大排列

if isequal(a,d) %相等時滿足要求

for k=1∶length(e)

if isequal(e{k},d)

break; %與已經(jīng)構(gòu)造好的數(shù)組相等，不保存

end

if k==length(e) %與已經(jīng)構(gòu)造好的數(shù)組不重復(fù)

L=L+1;

e{L}=d; %保存

end

end

end

end

for j=1∶length(e)

a=e{j}; a(a==2*n)=0; e{j}=a; %把2n替換為0

E{j}=e{j}′;

end

celldisp(E) %顯示細胞數(shù)組的內(nèi)容