月刊組合せ論 Natori は面白そうな組合せ論のトピックを紹介していく企画です。今回はシューベルト多項式を扱います。
シューベルト多項式の基礎
#
シューベルト多項式は組合せ論や幾何学などで活躍する多項式です。タイトルにもある通り、この記事では組合せ論に限って扱います。
まずは対称群について復習します。S n S_n S n n n n { 1 , 2 , … , n } \{1,2,\ldots,n\} { 1 , 2 , … , n } s i = ( i , i + 1 ) ∈ S n s_i=(i,i+1)\in S_n s i = ( i , i + 1 ) ∈ S n S n S_n S n s i s_i s i w ∈ S n w\in S_n w ∈ S n ℓ ( w ) \ell(w) ℓ ( w ) w w w w w w
( 1 2 3 4 4 2 1 3 ) = s 3 s 2 s 1 s 2 = s 1 s 3 s 2 s 1
\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 1 & 3 \end{pmatrix}=s_3s_2s_1s_2=s_1s_3s_2s_1
( 1 4 2 2 3 1 4 3 ) = s 3 s 2 s 1 s 2 = s 1 s 3 s 2 s 1 のように 2 通りの最短表示で表すことができる場合があります。
次は対称多項式を考えます。f ∈ Z [ x 1 , … , x n ] , w ∈ S n f\in\mathbb{Z}[x_1,\ldots,x_n], w\in S_n f ∈ Z [ x 1 , … , x n ] , w ∈ S n w f ∈ Z [ x 1 , … , x n ] wf\in\mathbb{Z}[x_1,\ldots,x_n] w f ∈ Z [ x 1 , … , x n ] ( w f ) ( x 1 , … , x n ) = f ( x w ( 1 ) , … , x w ( n ) ) (wf)(x_1,\ldots,x_n)=f(x_{w(1)},\ldots,x_{w(n)}) ( w f ) ( x 1 , … , x n ) = f ( x w ( 1 ) , … , x w ( n ) ) w w w w f = f wf=f w f = f f f f
多項式 f f f ∂ i ( f ) = f − s i f x i − x i + 1 \partial_i(f)=\frac{f-s_if}{x_i-x_{i+1}} ∂ i ( f ) = x i − x i + 1 f − s i f ∂ i ( f ) \partial_i(f) ∂ i ( f ) ∂ i \partial_i ∂ i
∂ i 2 = 0 \partial_i^2=0 ∂ i 2 = 0 ∣ i − j ∣ > 1 |i-j|>1 ∣ i − j ∣ > 1 ∂ i ∂ j = ∂ j ∂ i \partial_i\partial_j=\partial_j\partial_i ∂ i ∂ j = ∂ j ∂ 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} ∂ i ∂ i + 1 ∂ i = ∂ i + 1 ∂ i ∂ i + 1
w ∈ S n w\in S_n w ∈ S n s i 1 ⋯ s i l s_{i_1}\cdots s_{i_l} s i 1 ⋯ s i l ∂ w = ∂ i 1 ⋯ ∂ i l \partial_w=\partial_{i_1}\cdots \partial_{i_l} ∂ w = ∂ i 1 ⋯ ∂ i l
シューベルト多項式は S n S_n S n w 0 w_0 w 0 S n S_n S n
w 0 = ( 1 2 ⋯ n − 1 n n n − 1 ⋯ 2 1 )
w_0=\begin{pmatrix} 1 & 2 & \cdots & n-1 & n \\ n & n-1 & \cdots & 2 & 1 \end{pmatrix}
w 0 = ( 1 n 2 n − 1 ⋯ ⋯ n − 1 2 n 1 ) です。シューベルト多項式は w ∈ S n w\in S_n w ∈ S n
S w ( x ) = ∂ w − 1 w 0 ( x 1 n − 1 x 2 n − 2 ⋯ x n − 1 )
\mathfrak{S} _ w(x)=\partial_{w^{-1}w_0}(x_1^{n-1}x_2^{n-2}\cdots x_{n-1})
S w ( x ) = ∂ w − 1 w 0 ( x 1 n − 1 x 2 n − 2 ⋯ x n − 1 ) により定義されます。例えば w = 3142 w=3142 w = 3142 w − 1 w 0 = 3142 = s 2 s 1 s 3 w^{-1}w_0=3142=s_2s_1s_3 w − 1 w 0 = 3142 = s 2 s 1 s 3
S 3142 ( x ) = ∂ 2 ∂ 1 ∂ 3 ( x 1 3 x 2 2 x 3 ) = ∂ 2 ∂ 1 ( x 1 3 x 2 2 ) = ∂ 2 ( x 1 2 x 2 2 ) = x 1 2 ( x 2 + x 3 )
\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*}
S 3142 ( x ) = ∂ 2 ∂ 1 ∂ 3 ( x 1 3 x 2 2 x 3 ) = ∂ 2 ∂ 1 ( x 1 3 x 2 2 ) = ∂ 2 ( x 1 2 x 2 2 ) = x 1 2 ( x 2 + x 3 ) となります。計算途中では x n x_n x n x n x_n x n
関連する多項式として、二重シューベルト多項式も定義します。これは x 1 , … , x n , y 1 , … , y n x_1,\ldots,x_n,y_1,\ldots,y_n x 1 , … , x n , y 1 , … , y n
S w 0 ( x , y ) = ∏ i + j < n + 1 ( x i − y j )
\mathfrak{S} _ {w_0}(x,y)=\prod_{i+j<n+1}(x_i-y_j)
S w 0 ( x , y ) = i + j < n + 1 ∏ ( x i − y j ) とおき
S w ( x , y ) = ∂ w − 1 w 0 ( x ) S w 0 ( x , y )
\mathfrak{S} _ {w}(x,y)=\partial_{w^{-1}w_0}^{(x)}\mathfrak{S}_{w_0}(x,y)
S w ( x , y ) = ∂ w − 1 w 0 ( x ) S w 0 ( x , y ) と定めます。ここで ∂ ( x ) \partial^{(x)} ∂ ( x ) x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n S w ( x , y ) \mathfrak{S}_{w}(x,y) S w ( x , y ) y i y_i y i
Stanley 予想
#
S w ( x ) \mathfrak{S}_w(x) S w ( x ) x i x_i x i
w ∈ S n w\in S_n w ∈ S n R ( w ) = { ( i 1 , … , i ℓ ( w ) ) ∣ s i 1 ⋯ s i ℓ ( w ) = w } R(w)=\{(i_1,\ldots,i_{\ell(w)})\mid s_{i_1}\cdots s_{i_{\ell(w)}}=w\} R ( w ) = {( i 1 , … , i ℓ ( w ) ) ∣ s i 1 ⋯ s i ℓ ( w ) = w } a ∈ R ( w ) a\in R(w) a ∈ R ( w ) b b b a a a
b b b a a a ℓ ( w ) \ell(w) ℓ ( w ) b b b b i ≤ a i b_i\le a_i b i ≤ a i a i < a i + 1 a_i<a_{i+1} a i < a i + 1 b i < b i + 1 b_i<b_{i+1} b i < b i + 1
をみたすことです。a a a b b b C ( a ) C(a) C ( a )
S w ( x ) = ∑ a ∈ R ( w ) ∑ b ∈ C ( a ) x b 1 ⋯ x b ℓ ( w )
\mathfrak{S} _ w(x)=\sum_{a\in R(w)}\sum_{b\in C(a)}x_{b_1}\cdots x_{b_{\ell(w)}}
S w ( x ) = a ∈ R ( w ) ∑ b ∈ C ( a ) ∑ x b 1 ⋯ x b ℓ ( w ) と表せるという主張が Stanley の予想です。
w = 3142 w=3142 w = 3142 s 2 s 1 s 3 s_2s_1s_3 s 2 s 1 s 3 ( 2 , 1 , 3 ) (2,1,3) ( 2 , 1 , 3 ) b b b ( 1 , 1 , 2 ) (1,1,2) ( 1 , 1 , 2 ) ( 1 , 1 , 3 ) (1,1,3) ( 1 , 1 , 3 ) S 3142 ( x ) = x 1 2 x 2 + x 1 2 x 3 \mathfrak{S}_{3142}(x)=x_1^2x_2+x_1^2x_3 S 3142 ( x ) = x 1 2 x 2 + x 1 2 x 3
Pipe dream
#
a a a b b b b i b_i b i a i − b i + 1 a_i-b_i+1 a i − b i + 1 a = ( 2 , 1 , 3 ) , b = ( 1 , 1 , 2 ) 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) ( 1 , 2 ) , ( 1 , 1 ) , ( 2 , 2 ) x + y ≤ n x+y\le n x + y ≤ n
さて、印のついたマスに十字線を、印のついていないマスに交差しない線を書き込みましょう。
上の例では次のような図形が得られます。
このような図形を pipe dream といいます。RC グラフと呼ばれることもあります。厳密には pipe dream には次のようなものです。
i i i w ( i ) w(i) w ( i ) どの 2 本の曲線も 2 回以上交わることはない。
2 番目の性質は最短表示であることから来ています。置換をあみだくじとして表すことを考えると、pipe dream はそれの亜種であると見なせます。
シューベルト多項式は pipe dream 上の和として
S w ( x ) = ∑ D ∈ P D ( w ) x i 1 ⋯ x i l
\mathfrak{S} _ w(x)=\sum_{D\in PD(w)}x_{i_1}\cdots x_{i_l}
S w ( x ) = D ∈ P D ( w ) ∑ x i 1 ⋯ x i l と表せます。ここで i 1 , … , i l i_1,\ldots,i_l i 1 , … , i l
より一般に、二重シューベルト多項式は ( i k , j k ) (i_k,j_k) ( i k , j k )
S w ( x , y ) = ∑ D ∈ P D ( w ) ( x i 1 − y j 1 ) ⋯ ( x i l − y j l )
\mathfrak{S} _ w(x,y)=\sum_{D\in PD(w)}(x_{i_1}-y_{j_1})\cdots (x_{i_l}-y_{j_l})
S w ( x , y ) = D ∈ P D ( w ) ∑ ( x i 1 − y j 1 ) ⋯ ( x i l − y j l ) と表せることが知られています。
Bumpless pipe dream
#
bumpless pipe dream は比較的最近導入された新しい図形です。BPD はもっと広く使えるものですが、ここでは（二重）シューベルト多項式に限って考えます。
正方形のマス目を考えます。マス目への線の書き込み方は次の 6 通りです。
pipe dream と比べて、交わる十字線はありますが交わらない二曲線はありません。
w ∈ S n w\in S_n w ∈ S n
i i i w ( i ) w(i) w ( i ) どの 2 本の曲線も 2 回以上交わることはない。
をみたす図形を bumpless pipe dream といいます。w = 3142 w=3142 w = 3142
二重シューベルト多項式は BPD 上の和として
S w ( x , y ) = ∑ D ∈ B P D ( w ) ( x i 1 − y j 1 ) ⋯ ( x i l − y j l )
\mathfrak{S} _ w(x,y)=\sum_{D\in BPD(w)}(x_{i_1}-y_{j_1})\cdots (x_{i_l}-y_{j_l})
S w ( x , y ) = D ∈ BP D ( w ) ∑ ( x i 1 − y j 1 ) ⋯ ( x i l − y j l ) と表せることが知られています。ここで ( i k , j k ) (i_k,j_k) ( i k , j k )
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 )
\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)
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 ) となります。y y y
PD と BPD の間の全単射
#
シューベルト多項式には 2 種類の表示があることがわかりました。
S w ( x ) = ∑ D ∈ P D ( w ) x i 1 ⋯ x i l = ∑ D ∈ B P D ( w ) x i 1 ⋯ x i l
\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}
S w ( x ) = D ∈ P D ( w ) ∑ x i 1 ⋯ x i l = D ∈ BP D ( w ) ∑ x i 1 ⋯ x i l x i = 1 x_i=1 x i = 1 ∣ P D ( w ) ∣ = ∣ B P D ( w ) ∣ |PD(w)|=|BPD(w)| ∣ P D ( w ) ∣ = ∣ BP D ( w ) ∣ P D ( w ) PD(w) P D ( w ) B P D ( w ) BPD(w) BP D ( w ) D ∈ P D ( w ) D\in PD(w) D ∈ P D ( w ) w e i g h t P D ( D ) = x i 1 ⋯ x i l \mathrm{weight} _ {PD}(D)=x_{i_1}\cdots x_{i_l} weight P D ( D ) = x i 1 ⋯ x i l i k i_k i k D ∈ B P D ( w ) D\in BPD(w) D ∈ BP D ( w ) w e i g h t B P D ( D ) = x i 1 ⋯ x i l \mathrm{weight} _ {BPD}(D)=x_{i_1}\cdots x_{i_l} weight BP D ( D ) = x i 1 ⋯ x i l i k i_k i k ϕ : P D ( w ) → B P D ( w ) \phi\colon PD(w)\to BPD(w) ϕ : P D ( w ) → BP D ( w ) w e i g h t P D ( D ) = w e i g h t B P D ( ϕ ( D ) ) \mathrm{weight} _ {PD}(D)=\mathrm{weight} _ {BPD}(\phi(D)) weight P D ( D ) = weight BP D ( ϕ ( D )) D ∈ P D ( w ) D\in PD(w) D ∈ P D ( w )
Gao, Huang の論文では、モンク公式を保つという意味で “canonical” な全単射が構成されています。
Hybrid pipe dream
#
PD と BPD の間の全単射をより詳しく理解するために、hybrid pipe dream と呼ばれる図形が Knutson, Udell により導入されました。
Kohnert 図形
#
最後に、Kohnert によるシューベルト多項式の表示を紹介します。
置換 w ∈ S n w\in S_n w ∈ S n n × n n\times n n × n ( w ( i ) , i ) (w(i),i) ( w ( i ) , i ) w = 3142 w=3142 w = 3142
Rothe diagram に操作を行います。ある行の最も右にあるマスを選び、それを下の空きスペースに動かすことができます (他のマスを飛び越えてもよい)。上の例では可能な操作は次の 1 通りのみです。
操作を非負整数回行うことで得られる図形の集合を K D ( w ) KD(w) KD ( w ) D ∈ K D ( w ) D\in KD(w) D ∈ KD ( w ) y y y i i i m i ( D ) m_i(D) m i ( D )
S w ( x ) = ∑ D ∈ K D ( w ) x 1 m 1 ( D ) ⋯ x n m n ( D )
\mathfrak{S} _ w(x)=\sum_{D\in KD(w)}x_1^{m_1(D)}\cdots x_n^{m_n(D)}
S w ( x ) = D ∈ KD ( w ) ∑ x 1 m 1 ( D ) ⋯ x n m n ( D ) Assaf は K D ( w ) KD(w) KD ( w ) P D ( w ) PD(w) P D ( 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).
