↓ メインコンテンツへスキップ
組合せ論、楽しい！
組合せ論、楽しい！

【月刊組合せ論 Natori】Hall-Littlewood 多項式と Kostka-Foulkes 多項式【2023 年 6 月号】

·
対称関数 代数的組合せ論
箱星
著者
箱星
のんびり暮らしたい。
目次

月刊組合せ論 Natori は面白そうな組合せ論のトピックを紹介していく企画です。今回は対称多項式の世界に足を踏み入れてみましょう。

シューア多項式
#

シューア多項式については過去に記事にしました。ぜひお読みください。

【月刊組合せ論 Natori】シューア多項式とヤコビ・トゥルーディ公式【2023 年 3 月号】

ここでは定義のみ紹介します。λ\lambda を分割、xx を (x1,…,xn)(x_1,\ldots,x_n) の略記とし、SSYT(λ,n)\mathrm{SSYT}(\lambda,n) を形が λ\lambda で書かれている数字が nn 以下の半標準タブロー全体の集合とします。シューア多項式を

sλ(x)=∑T∈SSYT(λ,n)xT s_{\lambda}(x)=\sum_{T\in\mathrm{SSYT}(\lambda,n)}x^T

と定義します。ここで TT に ii が μi\mu_i 回書かれているとき、xT=x1μ1⋯xnμnx^T=x_1^{\mu_1}\cdots x_n^{\mu_n} です。

モノミアル対称多項式
#

例えば対称多項式に x3yzx^3yz という単項式があるとき、xy3zxy^3z や xyz3xyz^3 も現れなければなりません。単項式を一個決めたとき、現れるべき単項式をすべて集めた対称多項式をモノミアル対称多項式といいます。

厳密な定義はこうです。λ\lambda を分割とするとき

mλ(x)=∑μ:λの並べ替えxμ m_{\lambda}(x)=\sum_{\mu:\lambda \text{の並べ替え}}x^{\mu}

と定義します。ここで xμ=x1μ1⋯xnμnx^{\mu}=x_1^{\mu_1}\cdots x_n^{\mu_n} です。

sλs_{\lambda} を mμm_{\mu} の線形結合として表したときの mμm_{\mu} の係数は、sλs_{\lambda} における xμx^{\mu} の係数と等しいです。これは形が λ\lambda で ii が μi\mu_i 回書かれている半標準タブローの個数となります。これを KλμK_{\lambda\mu} とおくと

sλ(x)=∑μKλμmμ(x) s_{\lambda}(x)=\sum_{\mu}K_{\lambda\mu}m_{\mu}(x)

となります。この KλμK_{\lambda\mu} はコストカ数と呼ばれます。

Hall-Littlewood 多項式
#

シューア多項式とモノミアル対称多項式をつなぐのが Hall-Littlewood 多項式です。新たに tt というパラメータを導入します。

Hall-Littlewood 多項式は

Pλ(x1,…,xn;t)=1vλ(t)∑σ∈Snσ(x1λ1⋯xnλn∏1≤i<j≤nxi−txjxi−xj) P_{\lambda}(x_1,\ldots,x_n;t)=\frac{1}{v_{\lambda}(t)}\sum_{\sigma\in S_n}\sigma\left(x_1^{\lambda_1}\cdots x_n^{\lambda_n}\prod_{1\le i<j\le n}\frac{x_i-tx_j}{x_i-x_j}\right)

により定義されます。ここで λ\lambda に現れる ii の個数を mi(λ)m_i(\lambda) とおき、tt 階乗を

[m]t!=[m]t[m−1]t⋯[1]t([k]t=1+t+⋯+tk−1) [m]_t!=[m]_t[m-1]_t\cdots [1]_t \quad ([k]_t=1+t+\cdots+t^{k-1})

と定義するとき

vλ(t)=∏i=0∞[mi(λ)]t! v_{\lambda}(t)=\prod_{i=0}^{\infty}[m_i(\lambda)]_t!

とします。また σ∈Sn\sigma\in S_n は xix_i の置換として作用します。

Hall-Littlewood 多項式は t=0t=0 のときシューア多項式、t=1t=1 のときモノミアル対称多項式となります。

例: P(3,1)(x1,x2;t)=x13x2+(1−t)x12x22+x1x23P_{(3,1)}(x_1,x_2;t)=x_1^3x_2+(1-t)x_1^2x_2^2+x_1x_2^3

Hall-Littlewood 多項式の起源は有限アーベル群の数え上げ問題にあるそうです。これについてもいつか記事にする予定です。

Kostka-Foulkes 多項式
#

シューア多項式を Hall-Littlewood 多項式の線形結合として表すことができます。そのときの係数が Kostka-Foulkes 多項式です。

式で書くと次のようになります。Kλμ(t)K_{\lambda\mu}(t) が Kostka-Foulkes 多項式です。

sλ(x)=∑μKλμ(t)Pμ(x;t) s_{\lambda}(x)=\sum_{\mu}K_{\lambda\mu}(t)P_{\mu}(x;t)

t=1t=1 を代入すると

sλ(x)=∑μKλμ(1)mμ(x) s_{\lambda}(x)=\sum_{\mu}K_{\lambda\mu}(1)m_{\mu}(x)

になることから、Kλμ(1)K_{\lambda\mu}(1) は Kostka 数になることがわかります。

例: K(3,1),(2,1,1)=t2+tK_{(3,1),(2,1,1)}=t^2+t

Kostka-Foulkes 多項式 Kλμ(t)K_{\lambda\mu}(t) の係数は非負整数になることが知られています。Kazhdan-Lusztig 多項式の理論から証明することができますが、combinatorialist としては次のように証明したくなります。すなわち、Kostka-Foulkes 多項式の係数をある集合の要素数として組合せ論的に解釈できないでしょうか？

Lascoux と Schützenberger は、この問題をチャージと呼ばれる量を導入することで解決しました。チャージの定義は後回しにして、結果を先に紹介します。

Kλμ(t)=∑T∈SSYT(λ,μ)tcharge(T) K_{\lambda\mu}(t)=\sum_{T\in\mathrm{SSYT}(\lambda,\mu)}t^{\mathrm{charge}(T)}

すなわち、Kλμ(t)K_{\lambda\mu}(t) の tkt^k の係数は、形が λ\lambda でウェイトが μ\mu の（すなわち ii が μi\mu_i 回書かれている）半標準タブローであって、チャージが kk に等しいものの個数となります。

チャージの定義
#

それではチャージを定義しましょう。

順列に対するチャージ
#

ww を (1,2,…,n)(1,2,\ldots,n) の順列とします。このとき ww のチャージは、jj が j+1j+1 より前に現れるような jj に関する n−jn-j の総和として定義されます。

例えば w=31425w=31425 のとき、条件を満たす jj は 3,1,43,1,4 なのでチャージは (5−3)+(5−1)+(5−4)=7(5-3)+(5-1)+(5-4)=7 です。

数列に対するチャージ
#

次に重複がある数列について考えます。ただし (1 の個数)≧(2 の個数)≧… という条件を付けます。

  • i=1i=1 とする。右から左に読む。
  • ii が現れたとき、そこに印をつけ ii を 1 増やす。
  • 左端に到着したとき、再び右端に戻る。
  • 最大値に印をつけたとき、印のつけた数を取り出して順列を得る。残った数からなる数列に再び最初の操作を行う。
  • これをすべての数が取り出されるまで繰り返す。

例えば 21314132 で試してみましょう。印をつけた数を太字にします。まず右から左に読むと 21314132 となり、右に戻って再び読むと 21314132 となります。取り出される順列は 2413 となり、残った数列は 1312 です。残った数列に同じ操作を行うと 1312 となります。取り出される順列は 312 です。最後に 1 が残り、そのまま取り出されます。よって 21314132 から 2413, 312, 1 が取り出されました。

このとき、チャージは取り出された順列のチャージの総和として定義されます。上の例では 2413, 312, 1 のチャージの和が 21314132 のチャージとなります。

半標準タブローに対するチャージ
#

形が λ\lambda、ウェイトが μ\mu の半標準タブローが与えられたとき、一番下の行から上の行に向かって行を連結することで語を得ることができます。この語のチャージをタブローのチャージと定義します。μ\mu は分割、すなわち μ1≥μ2≥⋯\mu_1\ge \mu_2\ge\cdots をみたすので、(1 の個数)≧(2 の個数)≧… をみたします。

例えば次の半標準タブローから得られる数列は 434223311112 です。この数列のチャージがタブローのチャージとなります。

チャージの正体
#

チャージが定義できました。しかし定義が理解できても何故このようになるのかよくわかりません。

別の観点からチャージを理解する試みがあります。次のような観点があります。

  • 結晶グラフ [5]
  • energy function [7]
  • affine Grassmannian [8]

一般化
#

ここで紹介した Hall-Littlewood 多項式と Kostka-Foulkes 多項式は A 型です。他のルート系に一般化することができます。定義は割愛します。

A 型の Kostka-Foulkes 多項式はチャージを用いて表せましたが、一般化された Kostka-Foulkes 多項式についてこのようなことができるかという問題は未解決です。具体的には次のような未解決問題です。

  1. SSYT(λ,μ)\mathrm{SSYT}(\lambda,\mu) の代わりとなる集合 S(λ,μ)S(\lambda,\mu) を見つける。
  2. Kλμ(t)=∑T∈S(λ,μ)tcharge(T)K_{\lambda\mu}(t)=\sum_{T\in S(\lambda,\mu)}t^{\mathrm{charge}(T)} をみたす関数 charge\mathrm{charge} を見つける。

C 型の場合部分的に解決されています。 [2], [4], [9] をご覧ください。

おわりに
#

Hall-Littlewood 多項式、Kostka-Foulkes 多項式を紹介して、最後には未解決問題にも触れました。

皆さんも未解決問題に挑んでみませんか？

参考文献
#

  1. Butler, Lynne M. Subgroup lattices and symmetric functions. Mem. Am. Math. Soc. 539, 160 p. (1994).
  2. Dołęga, Maciej; Gerber, Thomas; Torres, Jacinta; A positive combinatorial formula for symplectic Kostka-Foulkes polynomials. I: Rows. J. Algebra 560. (2020).
  3. Désarménien, J.; Leclerc, B.; Thibon, J.-Y. Hall-Littlewood functions and Kostka-Foulkes polynomials in representation theory. Sémin. Lothar. Comb. 32, B32c, 38 p. (1994).
  4. Lecouvey, Cédric; Lenart, Cristian; Combinatorics of generalized exponents. Int. Math. Res. Not. 2020 (2020).
  5. Lascoux, Alain; Leclerc, Bernard; Thibon, Jean-Yves; Crystal graphs and $q$-analogues of weight multiplicities for the root system $A_n$. Lett. Math. Phys. 35, No. 4, 359-374 (1995).
  6. Macdonald, Ian Grant; Symmetric functions and Hall polynomials. 2nd ed. Oxford: Clarendon Press. x, 475 p. (1995).
  7. Nakayashiki, Atsushi; Yamada, Yasuhiko; Kostka polynomials and energy functions in solvable lattice models. Sel. Math., New Ser. 3, No. 4, 547-599 (1997).
  8. Patimo, Leonardo; The charge statistic in type A via the affine Grassmannian. J. Algebra 679, 169-211 (2025).
  9. Patimo, Leonardo; Torres, Jacinta; Atoms and charge in type $C_2$. Algebr. Comb. 8, No. 2, 521-574 (2025).