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

【月刊組合せ論 Natori】シューベルト多項式の組合せ論的表示【2024 年 6 月号】

·
箱星
著者
箱星
のんびり暮らしたい。
目次

月刊組合せ論 Natori は面白そうな組合せ論のトピックを紹介していく企画です。今回はシューベルト多項式を扱います。

シューベルト多項式の基礎
#

シューベルト多項式は組合せ論や幾何学などで活躍する多項式です。タイトルにもある通り、この記事では組合せ論に限って扱います。

まずは対称群について復習します。SnS_n を nn 次対称群、すなわち {1,2,…,n}\{1,2,\ldots,n\} の置換全体とします。si=(i,i+1)∈Sns_i=(i,i+1)\in S_n を隣接互換とします。SnS_n の任意の元は sis_i たちの積として表されます。w∈Snw\in S_n をそのように表したときに現れる隣接互換の最小個数を ℓ(w)\ell(w) で表し、長さといいます。そのときの ww の表示を最短表示といいます。ww の最短表示は一意的とは限りません。例えば

(12344213)=s3s2s1s2=s1s3s2s1 \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 1 & 3 \end{pmatrix}=s_3s_2s_1s_2=s_1s_3s_2s_1

のように 2 通りの最短表示で表すことができる場合があります。

次は対称多項式を考えます。f∈Z[x1,…,xn],w∈Snf\in\mathbb{Z}[x_1,\ldots,x_n], w\in S_n のとき、wf∈Z[x1,…,xn]wf\in\mathbb{Z}[x_1,\ldots,x_n] を (wf)(x1,…,xn)=f(xw(1),…,xw(n))(wf)(x_1,\ldots,x_n)=f(x_{w(1)},\ldots,x_{w(n)}) により定めます。すべての ww に対して wf=fwf=f となるような多項式 ff を対称多項式といいます。

多項式 ff に対して、∂i(f)=f−sifxi−xi+1\partial_i(f)=\frac{f-s_if}{x_i-x_{i+1}} により多項式 ∂i(f)\partial_i(f) が定まります。作用素 ∂i\partial_i を差分商作用素といいます。これは次の性質をみたします。

  • ∂i2=0\partial_i^2=0
  • ∣i−j∣>1|i-j|>1 ならば ∂i∂j=∂j∂i\partial_i\partial_j=\partial_j\partial_i
  • ∂i∂i+1∂i=∂i+1∂i∂i+1\partial_i\partial_{i+1}\partial_i=\partial_{i+1}\partial_i\partial_{i+1}

w∈Snw\in S_n の最短表示の一つを si1⋯sils_{i_1}\cdots s_{i_l} としたとき、∂w=∂i1⋯∂il\partial_w=\partial_{i_1}\cdots \partial_{i_l} と定めます。これが最短表示のとり方によらないことは上の性質から示せます。

シューベルト多項式は SnS_n の元で添字づけられた多項式の族です。w0w_0 を SnS_n の長さ最大の元とします。これは

w0=(12⋯n−1nnn−1⋯21) w_0=\begin{pmatrix} 1 & 2 & \cdots & n-1 & n \\ n & n-1 & \cdots & 2 & 1 \end{pmatrix}

です。シューベルト多項式は w∈Snw\in S_n に対して

Sw(x)=∂w−1w0(x1n−1x2n−2⋯xn−1) \mathfrak{S} _ w(x)=\partial_{w^{-1}w_0}(x_1^{n-1}x_2^{n-2}\cdots x_{n-1})

により定義されます。例えば w=3142w=3142 のとき、w−1w0=3142=s2s1s3w^{-1}w_0=3142=s_2s_1s_3 なので

S3142(x)=∂2∂1∂3(x13x22x3)=∂2∂1(x13x22)=∂2(x12x22)=x12(x2+x3) \begin{align*} \mathfrak{S}_{3142}(x) &= \partial_2\partial_1\partial_3(x_1^3x_2^2x_3) \\ &= \partial_2\partial_1(x_1^3x_2^2) \\ &= \partial_2(x_1^2x_2^2) \\ &= x_1^2(x_2+x_3) \end{align*}

となります。計算途中では xnx_n が現れることもありますが、最終的には xnx_n は現れないことに注意します。

関連する多項式として、二重シューベルト多項式も定義します。これは x1,…,xn,y1,…,ynx_1,\ldots,x_n,y_1,\ldots,y_n に関する多項式です。まず

Sw0(x,y)=∏i+j<n+1(xi−yj) \mathfrak{S} _ {w_0}(x,y)=\prod_{i+j<n+1}(x_i-y_j)

とおき

Sw(x,y)=∂w−1w0(x)Sw0(x,y) \mathfrak{S} _ {w}(x,y)=\partial_{w^{-1}w_0}^{(x)}\mathfrak{S}_{w_0}(x,y)

と定めます。ここで ∂(x)\partial^{(x)} は変数 x1,…,xnx_1,\ldots,x_n に作用する差分商作用素であることを表します。この Sw(x,y)\mathfrak{S}_{w}(x,y) を二重シューベルト多項式といいます。yiy_i にすべて 0 を代入すると通常のシューベルト多項式が得られます。

Stanley 予想
#

Sw(x)\mathfrak{S}_w(x) は xix_i に関する単項式の非負整数係数の線形結合として表せます。係数は組合せ論的に意味があるのではないかと考えられます。これについては Stanley による次の予想（解決済み）があります。

w∈Snw\in S_n に対して、R(w)={(i1,…,iℓ(w))∣si1⋯siℓ(w)=w}R(w)=\{(i_1,\ldots,i_{\ell(w)})\mid s_{i_1}\cdots s_{i_{\ell(w)}}=w\} を最短表示の集合とします。a∈R(w)a\in R(w) に対して、正整数の列 bb が aa-compatible であるとは

  • bb は aa と同じ長さ (すなわち ℓ(w)\ell(w))
  • bb は広義単調増加
  • bi≤aib_i\le a_i
  • ai<ai+1a_i<a_{i+1} ならば bi<bi+1b_i<b_{i+1}

をみたすことです。aa-compatible な bb からなる集合を C(a)C(a) とします。このとき

Sw(x)=∑a∈R(w)∑b∈C(a)xb1⋯xbℓ(w) \mathfrak{S} _ w(x)=\sum_{a\in R(w)}\sum_{b\in C(a)}x_{b_1}\cdots x_{b_{\ell(w)}}

と表せるという主張が Stanley の予想です。

w=3142w=3142 の場合、最短表示は s2s1s3s_2s_1s_3 のみであり、(2,1,3)(2,1,3)-compatible な bb は (1,1,2)(1,1,2) と (1,1,3)(1,1,3) の 2 つです。よって S3142(x)=x12x2+x12x3\mathfrak{S}_{3142}(x)=x_1^2x_2+x_1^2x_3 となり、上での計算と一致します。

Pipe dream
#

aa-compatible な bb に対して、マス目を用意し、bib_i 行 ai−bi+1a_i-b_i+1 列目に印をつけます。a=(2,1,3),b=(1,1,2)a=(2,1,3),b=(1,1,2) の場合、(1,2),(1,1),(2,2)(1,2),(1,1),(2,2) に印がつきます。印のついたマスは x+y≤nx+y\le n の領域上にあるので、マス目をこの範囲に限って考えてもよいです。

さて、印のついたマスに十字線を、印のついていないマスに交差しない線を書き込みましょう。

上の例では次のような図形が得られます。

このような図形を pipe dream といいます。RC グラフと呼ばれることもあります。厳密には pipe dream には次のようなものです。

  • ii 行目の左端から出発した曲線は、w(i)w(i) 列目の上端に到着する。
  • どの 2 本の曲線も 2 回以上交わることはない。

2 番目の性質は最短表示であることから来ています。置換をあみだくじとして表すことを考えると、pipe dream はそれの亜種であると見なせます。

シューベルト多項式は pipe dream 上の和として

Sw(x)=∑D∈PD(w)xi1⋯xil \mathfrak{S} _ w(x)=\sum_{D\in PD(w)}x_{i_1}\cdots x_{i_l}

と表せます。ここで i1,…,ili_1,\ldots,i_l は十字のマスがある行の番号です。

より一般に、二重シューベルト多項式は (ik,jk)(i_k,j_k) を十字のマスの行・列番号とすることで

Sw(x,y)=∑D∈PD(w)(xi1−yj1)⋯(xil−yjl) \mathfrak{S} _ w(x,y)=\sum_{D\in PD(w)}(x_{i_1}-y_{j_1})\cdots (x_{i_l}-y_{j_l})

と表せることが知られています。

Bumpless pipe dream
#

bumpless pipe dream は比較的最近導入された新しい図形です。BPD はもっと広く使えるものですが、ここでは（二重）シューベルト多項式に限って考えます。

正方形のマス目を考えます。マス目への線の書き込み方は次の 6 通りです。

pipe dream と比べて、交わる十字線はありますが交わらない二曲線はありません。

w∈Snw\in S_n に対して

  • ii 行目の右端から出発した曲線は w(i)w(i) 列目の下端に到着する。
  • どの 2 本の曲線も 2 回以上交わることはない。

をみたす図形を bumpless pipe dream といいます。w=3142w=3142 の場合は次の 2 通りがあります。

二重シューベルト多項式は BPD 上の和として

Sw(x,y)=∑D∈BPD(w)(xi1−yj1)⋯(xil−yjl) \mathfrak{S} _ w(x,y)=\sum_{D\in BPD(w)}(x_{i_1}-y_{j_1})\cdots (x_{i_l}-y_{j_l})

と表せることが知られています。ここで (ik,jk)(i_k,j_k) は空白のマスを表します。上の例では

S3142(x,y)=(x1−y1)(x1−y2)(x3−y2)+(x1−y1)(x1−y2)(x2−y1) \mathfrak{S}_{3142}(x,y)=(x_1-y_1)(x_1-y_2)(x_3-y_2)+(x_1-y_1)(x_1-y_2)(x_2-y_1)

となります。yy を 0 にすれば通常のシューベルト多項式となります。

PD と BPD の間の全単射
#

シューベルト多項式には 2 種類の表示があることがわかりました。

Sw(x)=∑D∈PD(w)xi1⋯xil=∑D∈BPD(w)xi1⋯xil \mathfrak{S} _ w(x)=\sum_{D\in PD(w)}x_{i_1}\cdots x_{i_l}=\sum_{D\in BPD(w)}x_{i_1}\cdots x_{i_l}

xi=1x_i=1 を代入すれば ∣PD(w)∣=∣BPD(w)∣|PD(w)|=|BPD(w)| がわかるので、PD(w)PD(w) と BPD(w)BPD(w) の間にいい感じの全単射があることを期待したくなります。D∈PD(w)D\in PD(w) に対して weightPD(D)=xi1⋯xil\mathrm{weight} _ {PD}(D)=x_{i_1}\cdots x_{i_l} (iki_k は十字のマスの行番号)、D∈BPD(w)D\in BPD(w) に対して weightBPD(D)=xi1⋯xil\mathrm{weight} _ {BPD}(D)=x_{i_1}\cdots x_{i_l} (iki_k は空白のマスの行番号) としたとき、全単射 ϕ ⁣:PD(w)→BPD(w)\phi\colon PD(w)\to BPD(w) であって weightPD(D)=weightBPD(ϕ(D))\mathrm{weight} _ {PD}(D)=\mathrm{weight} _ {BPD}(\phi(D)) が任意の D∈PD(w)D\in PD(w) に対して成り立つようなものが欲しいです。

Gao, Huang の論文では、モンク公式を保つという意味で “canonical” な全単射が構成されています。

Hybrid pipe dream
#

PD と BPD の間の全単射をより詳しく理解するために、hybrid pipe dream と呼ばれる図形が Knutson, Udell により導入されました。

Kohnert 図形
#

最後に、Kohnert によるシューベルト多項式の表示を紹介します。

置換 w∈Snw\in S_n の Rothe diagram とは、n×nn\times n のマス目において座標 (w(i),i)(w(i),i) とその右側および上側にあるマスをすべて取り除いて得られる図形です。例えば w=3142w=3142 の場合次のようになります。

image

Rothe diagram に操作を行います。ある行の最も右にあるマスを選び、それを下の空きスペースに動かすことができます (他のマスを飛び越えてもよい)。上の例では可能な操作は次の 1 通りのみです。

image

操作を非負整数回行うことで得られる図形の集合を KD(w)KD(w) とおきます。D∈KD(w)D\in KD(w) に対して、yy 座標が ii のマスの個数を mi(D)m_i(D) とおくとき、シューベルト多項式は次のように表せることが知られています。

Sw(x)=∑D∈KD(w)x1m1(D)⋯xnmn(D) \mathfrak{S} _ w(x)=\sum_{D\in KD(w)}x_1^{m_1(D)}\cdots x_n^{m_n(D)}

Assaf は KD(w)KD(w) と PD(w)PD(w) の間にウェイトを保つ全単射を構成することでこの表示を証明しました。

おわりに
#

シューベルト多項式の組合せ論的表示を紹介しました。拾いきれなかった話題もたくさんあります。ぜひ皆さんもシューベルト多項式を調べてみてください！

今後も月刊組合せ論 Natori では様々な楽しい話題をお届けする予定なので、応援のほどよろしくお願いいたします。

参考文献
#

  • 前野俊昭, Schubert 多項式とその仲間たち, 数学書房.
  • Assaf, Sami H. A bijective proof of Kohnert’s rule for Schubert polynomials. Combinatorial Theory 2, No. 1, Paper No. 5, 9 p. (2022).
  • Bergeron, Nantel; Billey, Sara. rc-graphs and Schubert polynomials. Exp. Math. 2, No. 4, 257-269 (1993).
  • Gao, Yibo; Huang, Daoji. The Canonical Bijection between Pipe Dreams and Bumpless Pipe Dreams. International Mathematics Research Notices, Volume 2023, Issue 21, November 2023.
  • Knutson, Allen. Schubert polynomials, pipe dreams, equivariant classes, and a co-transition formula. 2022.
  • Knutson, Allen; Udell, Gabe. Interpolating between classic and bumpless pipe dreams. Séminaire Lotharingien de Combinatoire 89B (2023).
  • Lam, Thomas; Lee, Seung Jin; Shimozono, Mark. Back stable Schubert calculus. Compos. Math. 157, No. 5, 883-962 (2021).