組合せ論的視点から見た parabolic type の Kazhdan-Lusztig polynomial

\begin{matrix}田川裕之 (和歌山大学教育学部) 述 \\ 森義之 (岡山理科大学理学部) 記^{∗} \end{matrix}

表現論的に重要な意味を持つ Kazhdan-Lusztig polynomial (以下 K-L polynomial) を組合せ論的に考えることは， Coxeter 群の Bruhat order の新しい性質を発見することにつながった．ここでは， 1987 年に Deodhar が導入した parabolic type の K-L polynomial (K-L polynomial のある種の analogue) を対象とし，通常の K-L polynomial に対して得られている組み合わせ論的な結果が parabolic type の場合ではどのようになるか考えて得た最近の結果を述べる．

1 Coxeter group, Bruhat order

Def. (Coxeter group).

(W, S): Coxeter 系 ⇔ S: set, W = ⟨S⟩: group, e ∉ S, S の関係式は次の形に限る：

(st)^{m(s,t)} = e for s, t ∈ S (m(s, t) ∈ {1, 2, ⋯} ⊔ {∞}).

但し，

m(s, s) = 1, m(s, t) = m(t, s) ≥ 2 for s ≠ t ∈ S.

ここで m(s, t) = ∞ は s, t ∈ S に関係が無いことを意味する. 特に W を Coxeter 群と呼ぶ.

Ex. (𝔖_{n}, {σ_{i} = (i, i + 1) ; i ∈ {1, 2, ⋯, n − 1}}): Coxeter 系.

従って対称群は Coxeter 群である．

∗研究集会「表現論とその周辺」 (1996 年 11 月 5 日–11 月 8 日) 講演ノート

Coxeter 系はその定義より m(s, t) により決定されるので， Coxeter graph と呼ばれるものと， Coxeter 系は 1 対 1 に対応している．

Ex.

∘  ∘  ∘ σ_{1}  σ_{2}  σ_{3} ↔ (𝔖_{4}, {σ_{1}, σ_{2}, σ_{3}})
∘  ∘  ∘ 4 s_{1}  s_{2}  s_{3}↔ (B_{3} 型 Weyl 群, {s_{1}, s_{2}, s_{3}})

ここでグラフの意味は， s, t ∈ S (s ≠ t) に対して，

∘  ∘ ⇔ m(s, t) = 2 ( i.e. st = ts)
∘  ∘ ⇔ m(s, t) = 3
∘  ∘ m ⇔ m(s, t) = m ≥ 4

を表す．

以下任意の Coxeter 系 (W, S) を固定して考える．

Def.-Prop. (Bruhat order).

ℓ : W → {0, 1, 2,…} (length function),

ℓ(w) := \{ \begin{matrix}min\{m;^{∃}s_{1}, s_{2},…, s_{m} ∈ S, s.t. w = s_{1}s_{2} ⋯ s_{m}\} & if w ≠ e, \\ 0 & if w = e. \end{matrix}

s_{1}s_{2} ⋯ s_{r} : reduced expression of w ⇔ ^{∀}s_{i} ∈ S, w = s_{1}s_{2} ⋯ s_{r}, ℓ(w) = r.

w ∈ W の reduced expression は一般に一意的でない．例えば， 3 次対称群で， σ_{1}σ_{2}σ_{1} = σ_{2}σ_{1}σ_{2} は最長元の reduced expression である．

Bruhat order ≤ は次のように定義される． w ∈ W の reduced expression を w = s_{1}s_{2} ⋯ s_{m} とするとき， x ∈ W に対して，

x ≤ w ⇔ ^{∃}i_{1}, i_{2},…, i_{k}, s.t. 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ m, x = s_{i_{1}}s_{i_{2}} ⋯ s_{i_{k}}.

記号 <· を次で定義する： x<·w ⇔ x < w, “x ≤ z ≤ w ⇒ z = x or w”

(⇔ x < w, ℓ(x) = ℓ(w) − 1).

Ex. Let x, w ∈ 𝔖_{n}. ℓ(x) = ♯{(i, j); i < j, x(i) > x(j)}. x<·w ⇔ ^{∃}i, j s.t. i < j, w(i) > w(j), x = w(i, j),

w(k) > w(i) or w(j) > w(k) for i < ^{∀}k < j.

半順序集合を表す graph として Hasse diagram と呼ばれるものがある．

Ex. 3 次対称群 𝔖_{3} の Bruhat order に関する Hasse diagram.

[figure: e; σ_{1}; σ_{2}; σ_{1}σ_{2}; σ_{2}σ_{1}; σ_{1}σ_{2}σ_{1}; 123; 213; 132; 231; 312; 321]

2 parabolic type の R-polynomial と K-L polynomial

J ⊆ S に対して， W_{J} := ⟨J⟩,

W^{J} := {y ∈ W ; ℓ(yz) = ℓ(y) + ℓ(z) for ^{∀}z ∈ W_{J}}

とおく． W_{ϕ} := {e}, W^{ϕ} = W となることに注意する．

Def.-Prop.(R-polynomial of parabolic type).

x, w ∈ W^{J}. u = −1 or q.

R_{x,x}^{J}(q)_{u} := 1, R_{x,w}^{J}(q)_{u} := 0 if x ≰ w.

For s ∈ S s.t sw < w,

R_{x,w}^{J}(q)_{u} := \{ \begin{matrix}R_{sx,sw}^{J}(q)_{u} & if ℓ(sx) < ℓ(x), \\ qR_{sx,sw}^{J}(q)_{u} + (q − 1)R_{x,sw}^{J}(q)_{u} & if ℓ(sx) > ℓ(x), sx ∈ W^{J}, \\ (q − 1 − u)R_{x,sw}^{J}(q)_{u} & if ℓ(sx) > ℓ(x), sx ∉ W^{J}. \end{matrix}

R_{x,w}^{J}(q)_{u} = ∑_{i≥0} r_{i}^{J}(x, w)_{u}q^{i}, r̃_{i}^{J}(x, w)_{u} := (−1)^{ℓ(w)−ℓ(x)+i}r_{i}(x, w)_{u}.

R_{x,w}^{ϕ}(q)_{u} = R_{x,w}(q) (= ∑_{i≥0} r_{i}(x, w)q^{i}).

は通常の R-polynomial である．

parabolic type の R-polynomial に対しては次が成立している.

Th.(Deodhar [2])

(i) R_{x,w}^{J}(q)_{u} = ∑_{y∈W_{J}} (−u)^{ℓ(y)}R_{xy,w}(q). (ii) degR_{x,w}^{J}(q)_{u} ≤ ℓ(w) − ℓ(x). (iii) r̃_{0}^{J}(x, w)_{−1} = δ(x ≤ w, [x, w] = [x, w]^{J}), r̃_{0}^{J}(x, w)_{q} = δ(x ≤ w),

[x, w] := {y ∈ W; x ≤ y ≤ w}, [x, w]^{J} := {y ∈ W^{J}; x ≤ y ≤ w},

δ(∗) := \{ \begin{matrix}1 & if ∗ is true, \\ 0 & if ∗ is false. \end{matrix}

(iv) ∑_{x≤y≤w,y∈W^{J}} q^{ℓ(w)−ℓ(y)}R_{x,y}^{J}(q)_{u}R_{y,w}^{J} (\frac{1}{q})_{u} = δ_{x,w}.

次の補題が３章で述べる parabolic type の K-L polynomial の組合せ論的記述を求める上での鍵となる.

The key Lem.

(−q)^{ℓ(w)−ℓ(x)}R_{x,w}^{J} (\frac{1}{q})_{u} = R_{x,w}^{J}(q)ū, where ū := \{ \begin{matrix}q & if u = −1, \\ −1 & if u = q. \end{matrix}

この系として通常の R-polynomial で成立している等式の類似ともいえる次の等式が得られる．

Cor.

∑_{x≤y≤w,y∈W^{J}}(−1)^{ℓ(y)−ℓ(x)}R_{x,y}^{J}(q)_{u}R_{y,w}^{J}(q)ū = δ_{x,w}.

parabolic type の K-L polynomial は parabolic type の R-polynomial を用いて次のように定義される.

Def.-Prop. (K-L polynomial of parabolic type)

∃!{P_{x,w}^{J}(q)_{u}; x, w ∈ W^{J}} s.t.

P_{x,x}^{J}(q)_{u} = 1, P_{x,w}^{J}(q)_{u} = 0 if x ≰ w,

deg P_{x,w}^{J}(q)_{u} ≤ (ℓ(w) − ℓ(x) − 1)/2 if x < w,

q^{ℓ(w)−ℓ(x)}P_{x,w}^{J}(\frac{1}{q})_{u} = ∑_{x≤y≤w,y∈W^{J}} R_{x,y}^{J}(q)_{u}P_{y,w}^{J}(q)_{u} if x < w.

P_{x,w}^{J}(q)_{u} = ∑_{i≥0} p_{i}^{J}(x, w)_{u}q^{i}.

P_{x,w}^{ϕ}(q)_{u} = P_{x,w}(q) (= ∑_{i≥0} p_{i}(x, w)q^{i}).

は通常の K-L polynomial である．

parabolic type の K-L polynomial と通常の K-L polynomial との間には次の関係式が成立している.

Th.(Deodhar [2])

P_{x,w}^{J}(q)_{q} = ∑_{y∈W_{J}} (−1)^{ℓ(y)}P_{xy,w}(q),

P_{x,w}^{J}(q)_{−1} = P_{xz_{0},wz_{0}}(q) if ♯W_{J} < ∞ (z_{0} : the longest element of W_{J}).

Kazhdan と Lusztig は対称群の Hecke 環の既約表現を構成するために K-L polynomial を導入し， K-L 予想と呼ばれる表現論的に重要な予想をたてた．この予想は近年解決されたが, 同時に考えられていた，一般の Coxeter 群の場合の K-L polynomial の係数の非負性の予想は，特別な場合を除いて未解決である．これについては次のことが知られている．

Fact A.

W: crystallographic Coxeter group (i.e. m(s, t) ∈ {2, 3, 4, 6, ∞} for s ≠ t in S)

⇒ p_{i}(x, w) ≥ 0 for ^{∀}i ≥ 0 (by Haddad [3]), p_{i}^{J}(x, w)_{−1} ≥ 0 for ^{∀}i ≥ 0 (by Deodhar [2]).

また, K-L polynomial の低次の係数に関連した組合せ論的結果として次のことが知られている.

Fact B. x, w ∈ W, i ≥ 0.

(i) p_{0}(x, w) = r̃_{0}(x, w) = δ(x ≤ w). (ii) p_{1}(x, w) = c_{1}(x, w) − r̃_{1}(x, w) (by F. Brenti [1]).

C_{i}(x, w) := {y ∈ W; x ≤ y ≤ w, ℓ(y) = ℓ(w) − 1}, c_{i}(x, w) := ♯C_{i}(x, w).

(iii) p_{2}(x, w) = r̃_{2}(x, w) − c_{2}(x, w) + ∑_{y∈C_{1}(x,w)} p_{1}(x, y) + ∑_{y∈C_{3}(x,w)} p_{1}(y, w)

(by Brenti [1])

(iv) If ℓ(w) = ℓ(x) + ℓ(x^{−1}w), p_{1}(x, w) = c_{1}(x, w) − g(x^{−1}w) ≥ 0 (by Tagawa [6]).

G(y) := {s ∈ S; s ≤ y}, g(y) := ♯G(y).

(v) If ℓ(w) = ℓ(x) + ℓ(x^{−1}w), c_{i}(x, w) ≥ ( \begin{matrix}g(x^{−1}w) \\ i \end{matrix} ) (by Tagawa [8]).

(vi) p_{1}(x, w) ≥ 0 for all x, w ∈ W (by Tagawa [7]).

これらを parabolic type に拡張したところ次の結果が得られた．

Th. x, w ∈ W^{J}, i ≥ 0.

(i) p_{0}^{J}(x, w)_{u} = r̃_{0}(x, w)ū (u = −1 のときは定義より容易). (ii) p_{1}^{J}(x, w)_{u} = c_{1}^{J}(x, w)_{u} − r̃_{1}^{J}(x, w)ū,

C_{i}^{J}(x, w)_{−1} := C_{i}(x, w) ∩ W^{J},

C_{i}^{J}(x, w)_{q} := C_{i}(x, w) ∩ W^{J} ∩ {y ∈ W; [x, y] = [x, y]^{J}},
c_{i}^{J}(x, w)_{u} := ♯C_{i}^{J}(x, w)_{u}.

(iii) p_{2}^{J}(x, w)_{u} = r̃_{2}^{J}(x, w)ū−c_{2}^{J}(x, w)_{u}+ ∑_{y∈C_{1}^{J} (x,w)_{−1}} p_{1}^{J}(x, y)_{u}+ ∑_{y∈C_{3}^{J} (x,w)_{u}} p_{1}^{J}(y, w)_{u}

+♯{z ∈ C_{2}^{J}(x, w)_{u}; r̃_{0}^{J}(z, w)_{u} = 0}.

u = q のときは最後の項= 0 である. (iv) If ℓ(w) = ℓ(x) + ℓ(x^{−1}w),

p_{1}^{J}(x, w)_{−1} = c_{1}^{J}(x, w)_{−1} − g^{J}(x^{−1}w) ≥ 0, p_{1}^{J}(x, w)_{q} ≥ 0.

g^{J}(y) := ♯G(y) ∩ W^{J}.

(v) If ℓ(w) = ℓ(x) + ℓ(x^{−1}w), c_{i}^{J}(x, w)_{−1} ≥ ( \begin{matrix}g^{J}(x^{−1}w) \\ i \end{matrix} ).

3 K-L polynomial の組合せ論的記述

Def. For a_{0}, a_{1},…, a_{r+1} ∈ W with a_{0} ≤ a_{1} ≤ … ≤ a_{r+1},

R_{a_{0},a_{1},...,a_{r+1}}(q) := \{ \begin{matrix}(−1)^{ℓ(a_{1})−ℓ(a_{0})}R_{a_{0},a_{1}}(q) & if r = 0, \\ U_{⌈ \frac{d+1}{2} ⌉}(q^{d}R_{a_{1},a_{2},...,a_{r+1}}(\frac{1}{q}))R_{a_{0},a_{1}}(q) & if r ≥ 1, \end{matrix}

d := ℓ(a_{r+1}) − ℓ(a_{1}),

⌈x⌉ := min{z ∈ Z; z ≥ x},

U_{j}(∑_{i≥0} a_{i}q^{i}) := ∑_{i≥j} a_{i}q^{i}.

Th.(Brenti [1]) For x, w ∈ W,

P_{x,w}(q) = ∑_{C∈C(x,w)} R_{C}(q),

C(x, w) := {C : multichain from x to w of W with length ≥ 1}.

Brenti による multichain に対する R-polynomial の定義と上の結果を parabolic type の場合に拡張する．

Def. For a_{0}, a_{1},…, a_{r+1} ∈ W^{J} with a_{0} ≤ a_{1} ≤ … ≤ a_{r+1},

R_{a_{0},a_{1},...,a_{r+1}}^{J}(q)_{u} := \{ \begin{matrix}(−1)^{ℓ(a_{1})−ℓ(a_{0})}R_{a_{0},a_{1}}^{J}(q)ū & if r = 0, \\ U_{⌈ \frac{d+1}{2} ⌉}(q^{d}R_{a_{1},a_{2},...,a_{r+1}}^{J}(\frac{1}{q})_{u})R_{a_{0},a_{1}}^{J}(q)_{u} & if r ≥ 1. \end{matrix}

Th. For x, w ∈ W^{J},

P_{x,w}^{J}(q)_{u} = ∑_{C∈C^{J} (x,w)} R_{C}^{J}(q)_{u},

C^{J}(x, w) := {C : multichain from x to w of W^{J} with length ≥ 1}.

参考文献

[1] F. Brenti, A combinatorial formula for Kazhdan-Lusztig polynomials, Invent. math. 118 (1994), pp. 371–394.

[2] V. V. Deodhar, On some geometric aspects of Bruhat orderings. II. The parabolic analogue of Kazhdan-Lusztig polynomials, J. Alg. 111 (1987), pp. 483–506.

[3] Z. Haddad, Infinite dimensional flag varieties, thesis, M. I. T. (1984).

[4] J. E. Humphreys, Reflection groups and Coxeter groups, Cambridge Univ. Press (1990).

[5] D. Kazhdan and G. Lusztig, Representation of Coxeter groups and Hecke algebras, Invent. math. 53 (1979), pp. 165–184.

[6] H. Tagawa, On the first coefficients in q of the Kazhdan-Lusztig polynomials, Tokyo J. Math. 17, No.1 (1994), pp. 219–228.

[7] H. Tagawa, On the non-negativity of the first coefficient of Kazhdan-Lusztig polynomials, J. Alg. 177 (1995), pp. 698–707.

[8] H. Tagawa, On the second coefficient of R-polynomials, preprint.

[9] H. Tagawa, On the first coefficient of Kazhdan-Lusztig polynomials of parabolic type, Preprint Series UTMS 96-7.