まえがき
この記事は
仮の人
さんの企画
AMC2023 (Advent Math Calendar2023)
のDay3に当たります. ほかの人の記事もぜひ見よう. 修正点があったら遠慮なくコメント欄で教えてください.
内容
この記事に分割数は出てきません. 出てくるのは整数の分割です. (しいて言えば今回の結果から分割数の上界としてが得られるが, 上界としてはあまりにも大きい)
グラフ理論と共役作用の話が主です. 群と群の作用の定義を知っておくといいかもしれない.
概要
この記事では, 全単射な写像のfunctional graph(以降関数グラフと呼ぶ)の自己同型群(対称群の共役作用の安定化群)を考えることにより, 整数の分割に関する以下の等式を導く.
分割に対するスコアの逆数の総和は1
自然数の分割について, スコアを以下のように定義する.
ここで, は分割に含まれるの個数である.
例えば分割のとき
このとき, の分割全体の集合をとすると
議論の要点
整数の分割と関数グラフの対応
「整数の分割」と「全単射な写像のなす関数グラフの形」の間に一対一の対応があることを使う. 具体的には,
が個の, 個の, , 個の, に分割されたとき,
この分割に対して
個の長さの有向サイクル, 個の長さの有向サイクル, , 個の長さkの有向サイクル, で構成された関数グラフを対応させる. このとき, 関数グラフは一意に定まらないが, 関数グラフの形は一意に定まる.
関数グラフの「形が等しい」の言い換え
関数グラフは, 頂点にという関係があるときからに有向辺をつなげてできたものだった. つまり, 写像の関数グラフが「形が等しい」ということは
ある全単射な写像が存在しとなる, と言い換えられる.
これを変形すると, つまりとなる. これは対称群の共役作用を考えたときの軌道との軌道が一致するということである.
「頂点を区別する場合の数」と「区別しない場合の数」の関係
例えばある「頂点を区別していない」頂点数のグラフがあったとして, 各頂点にからを対応させようと思ったとき, その「対応の数」はである. ただし, このとき対称性の分で割る必要が出てくる(例えばサイクルならで割る必要がある(数珠順列)). そしてこの「対称性の分」は, 頂点の置換であって, 頂点を「その置換で入れ替えてもグラフの形が変わらない」ような置換の数である. そのような置換全体の集合をと表せば, 「対応の数」はと表せる. ちなみには群になり, 自己同型群と呼ばれる.
関数グラフの基本的な性質
定義:関数グラフ
この記事では, 関数グラフを集合と写像の組であるとする.
関数グラフの同型
「議論の要点」の節で言っていたように, 関数グラフの形が等しい, という同値関係は次のように定義できる.
ある全単射な写像が存在し
このときを(あるいは)から(あるいは)へのグラフ同型と言うことにする.
有限集合の要素数をで表し, 関数グラフの頂点数をと定義する.
頂点数が有限な関数グラフ全体の集合をとし, その元を有限関数グラフと呼ぶ. とする.
の元を非標識関数グラフと言うことにする.
について, でのにおける同値類を表す.
グラフの和, 非負整数倍
について,
ただしはとの非交和を表し(つまりの時も, においてはの元との元は区別する), 写像は
という写像である.
またについてとする. ただしのときは, を空集合から空集合への写像のなす関数グラフとする.
この和はで考えてもwell-definedである. また交換法則や結合法則が成り立つ.
サイクル
を以上未満の整数の集合とする. このとき長さのサイクルをとする.
ただしはという写像である.
よく知られている事実として以下の補題がある.
全単射な写像のなす有限関数グラフはサイクルの和で表される
で, が全単射な写像であるとき
となるが存在する. ただし十分大きな整数が存在し
自己同型群
グラフの自己同型群
関数グラフについて, からへのグラフ同型全体の集合は写像の合成を積として群をなす.
これをの自己同型群と呼び, と書く.
特にのとき, はの, 次の対称群の共役作用の安定化群である.
また, について, を, となるようなを取ってきてと定義すると, これは同型の分を除いて一意的に定まる.
安定化群の性質と, グラフ同型の定義を考えれば次の補題が成り立つ.
自己同型群と同値類
頂点数の任意の非標識関数グラフと, となるような集合について, 写像でとなるようなものの個数は個
「議論の要点」の節で言っていたように, の各頂点にを書き込めばいいので通り, ただし同型(=対称性)の分で割る必要があるといった感覚の式である.
上の補題のを, 頂点数の写像のなす関数グラフ全体とすれば次の定理が成り立つ.
自己同型群の位数の逆数和
である. より, 頂点数の関数グラフの数が以上であることがわかる.
ほとんどのグラフは対称性がないので, この評価はが大きいときには有効である(多分).
またを全単射な写像のなす非標識関数グラフの集合とすると
ちなみに, ほとんど同じ手順で関数グラフだけでなく単純グラフや木についても同様の等式を導くことが可能.
「議論の要点」の節で言っていたように, 次のような写像を考える.
ただし十分大きな整数が存在し, またのときとする.
このとき, の要素のうち頂点数がであるものと, の分割は一対一に対応する.
よってあとはを示せばよい.
について, によってはに移る. 個あるサイクルをどのサイクルに移すかで通り. 個のサイクルそれぞれについて, そのまま移動先のサイクルへ移すか, だけずらして移すか, , だけずらして移すかの通りあるので通り.
これをすべてのについて考えるので,
上記の式を写像で整数の分割に対応させると, 右辺はである. よって示された.
ちなみに, 明らかには次の対称群の部分群なのでは右辺で割り切れます.
分割に対するスコアの逆数の総和は1
自然数の分割について, スコアを以下のように定義する.
ここで, は分割に含まれるの個数である.
例えば分割のとき
このとき, の分割全体の集合をとすると