僕の頭の備考欄

徒然なるままに日々の発見を書き綴ります。数学/情報技術/ダンス 要するに雑記です。

ヤング図形のRS対応とPlancherel測度

表現論的組合せ論という分野をちょこっと勉強したのでそのまとめ(というか例のごとくメモ)です. 自然数の分割とヤング図形の対応, n次対称群と標準盤とのRS対応, ヤング図形の極限形状までを概観します.

分割とYoung図形

分割

定義(分割)

自然数 nについて n \ge \lambda _1 \ge \lambda _2 \ge \cdots \ge \lambda _l \ge 0となる自然数 \lambda _1, \lambda _2, \cdots , \lambda _lを用いて n = \lambda _1 + \lambda _2 + \cdots +\lambda _lと表すことを n分割といい,  (\lambda _1 , \lambda _2 , \cdots ,\lambda _l)と書く.

 nの分割の全体の集合のことを \mathcal{P}(n)と書く. すなわち

\begin{align} \mathcal{P}(n) = \left \{ (\lambda _1 , \lambda _2 , \cdots ,\lambda _l) \ ; \sum _{i=1}^{l} \lambda _i = n , \ (\lambda _1 \ge \lambda _2 \ge \cdots \ge \lambda _l \ge 0)\right \} \end{align}

である.

 \mathcal{P}(n)の元の数, すなわち nの分割の総数を分割数といい,  p(n)で表す.

例)  n=4のとき.

 \mathcal{P}(4)の元, すなわち自然数 4の分割をすべて書くと (4), (3,1), (2,2), (2, 1, 1), (1, 1, 1, 1)であり,  p(4) = 5.

分割数の母関数表示

 1未満の xについての形式的べき級数

\begin{align} \frac{1}{1-x^k} = 1 + x^k + x^{2k} + x^{3k} + \cdots \ (k=1,2,3,\ldots) \end{align}

を用いて分割数 p(n)の母関数表示を与えられることが知られています.

定理(分割数の母関数表示)

形式的に p(0)=1とする. このとき,

\begin{align} \prod _{k=1} ^{\infty} \frac{1}{1-x^k} = \sum _{n=0} ^{\infty} p(n) x^n \end{align}

つまり左辺をn次の項まで級数展開すれば, そのn次の項の係数が分割数と対応しているということです.

Young図形(ヤング図形)

定義(Young図形)

大きさの等しい n個の正方形(ハコ)を上詰めかつ左詰めに並べたものをサイズ nYoung図形という.

サイズ nのYoung図形全体を y(n)と書く.

例)  n=4のYoung図形を列挙すると以下のようになります.

f:id:shuhoyo:20190215170632p:plain

ここで重要なのはサイズ nのYoung図形について, 各行のハコの数の組が nの分割に対応しているということです.

つまり以下の定理が成り立ちます.

定理

全単射

\begin{align} y(n) & \tilde{\longrightarrow} \mathcal{P}(n) \\ \lambda & \longmapsto (\lambda _1 , \lambda _2 , \cdots ,\lambda _l) \end{align}

が存在する.

サイズ nのYoung図形と自然数 nの分割には一対一対応の関係が成り立つことから, 通常サイズ nのYoung図形の型を自然数 nの分割の書き方で書き表します.

盤(tableau)と標準盤(standard tableau)

定義(盤, 標準盤, 型)

サイズ nのYoung図形のハコの中に nまでの自然数を1度ずつ書き入れたものを盤(tableau)という.

このとき盤 Tについて, 元のYoung図形 \lambda T型(shape)という.

また, 盤 Tに書き入れた自然数が, 各行ごとに左から右に単調増加でかつ各列ごとに上から下に単調増加となるとき,  T標準盤(standard tableau)という.

Young図形\lambda \in \mathcal{P}(n)に対して,  \lambdaを型とする盤全体を Tab(\lambda)と表します. 同様に,  \lambdaを型とする標準盤全体を STab(\lambda)と表します.

例) 標準盤(n=6)

f:id:shuhoyo:20190223185007p:plain

Young図形上の確率測度

何もない状態からハコを上詰め左詰めで1つずつ並べていき, サイズ nのYoung図形ができた時点で, 今度はハコを1つずつ取り除いていき, 何もない状態に戻す過程を考えます.

例えば n=3としたとき, 以下の6通りの過程が考えられます.

f:id:shuhoyo:20190223151255p:plain
n=3の過程

今の6通りの中では (2,1)のYoung図形が最も多く出現している(4回)ことがわかります.

では一般の nに対してこの過程を行ったとき, サイズ nYoung図形のなかでもっとも出現確率が高いものは何かということを考えます. そのためにまずYoung図形上の確率測度を与えなければなりません.

結論だけ言えば, 型が \lambdaである標準盤の個数 d_{\lambda }を用いると, 型が \lambda のYoung図形の出現率 \mathbb{P}^{(n)} (\lambda )は以下のように表せることが知られています.

\begin{align} \mathbb{P}_n (\lambda) = \frac{d_{\lambda} ^2}{n!} \end{align}

この確率測度 \mathbb{P}_n (\lambda)Plancherel測度と言われています.

ちょっと細かい話をするとこの測度は n次対称群と, 型 \lambdaの標準盤同士の直積空間の間に全単射が存在するという事実から導かれます. この全単射Robinson-Schensted対応(RS対応)といいます.

Robinson-Schensted対応

 n次対称群 S_nと, サイズ nのYoung図形 \lambda \in \mathcal{P}(n)からなる標準盤全体 STab(\lambda)に対して全単射

\begin{align} S_n & \tilde{\longrightarrow} \bigcup _{\lambda \in \mathcal{P}(n)}(STab(\lambda) \times STab(\lambda)) \end{align}

存在する.

この両辺の \dimをとることで \mathbb{P}_n (\lambda)を得ます.

例)  n=4のYoung図形の出現率

サイズ4のYoung図形の型は (4), (3,1), (2,2), (2, 1, 1), (1, 1, 1, 1)の5つ. このそれぞれに対して標準盤を列挙してみると以下のようになります.

f:id:shuhoyo:20190223170912p:plain

したがって,

\begin{align} d_{(4)} &= 1\\ d_{(3,1)} &= 3\\ d_{(2,2)} &= 2\\ d_{(2,1,1)} &= 3\\ d_{(1,1,1,1)} &= 1 \end{align}

であり, それぞれの出現率は

\begin{align} \mathbb{P}_4 (4) &= \frac{d_{(4)} ^2}{4!} = \frac{1}{24} \\ \mathbb{P}_4 (3,1) &= \frac{d_{(3,1)} ^2}{4!} = \frac{9}{24}\\ \mathbb{P}_4 (2,2) &= \frac{d_{(2,2)} ^2}{4!} = \frac{4}{24}\\ \mathbb{P}_4 (2,1,1) &= \frac{d_{(2,1,1)} ^2}{4!} = \frac{9}{24}\\ \mathbb{P}_4 (1,1,1,1) &= \frac{d_{(1,1,1,1)} ^2}{4!} = \frac{1}{24} \end{align}

よって,  n=4のときは

f:id:shuhoyo:20190223174453p:plain

が最もよく現れるということがわかりました.

同様に n=3, 5, 6で試してみると左から順に

f:id:shuhoyo:20190223174952p:plain

が最もよく現れることがわかります. なんとなくなめらかな階段状に並ぶ形が出現しやすいのかなということが予想できます.

ヤング図形の極限形状(n → ∞)

では n \rightarrow \inftyのときYoung図形はどのような形に収束するのか. 各列の右端のハコの右上の頂点を連続的に結んだときの曲線の形(極限形状)は以下の式で表されることがVershik-Kerovによって明らかにされています.

\begin{align}
    f(x) = \begin{cases}
    \frac{2}{\pi}(\frac{x}{2} \arcsin x + \sqrt{4-x^2})  & (|x|\le 2)\\
    |x| & (|x|>2)
    \end{cases}
\end{align}

f:id:shuhoyo:20190223182048p:plain

(※図はヤング図形を135度左に回転させたものと見る.)

ちょっと導出までは書く元気がありませんでした...

これ以上はまだよく勉強できていないのですが, 自由確率論と強い関わりがあるのだそう. 容器内の流体の動きとかもこのアプローチでモデル化できるのかなと思ってみたり. これを通して表現論, 特に対称空間理論と表現論的組合せ論にふわっと興味が出てきました.