お話しする内容：

何がしたいのか

計算群論の手法

置換パズルについて

Minkwitz factorization の解説

html canvas で作成したパズルの紹介

課題・目標・夢

何がしたいのか

群論の教科書はたくさんあるが, 視覚に訴える具体例やプログラミングとの関連の和書は数少ない

群論の視覚的で面白い具体例をたくさん作りたい.

GAPやmagmaなどの既存のソフトウェアに頼らない.

最もお手軽な JavaScript で計算群論の手法を実装し計算する.

html canvas によって可視化する.

参考となる本：

　 　 　 　

計算群論の手法

群をどう作るか？ 大きく２つある

置換群(=対称群の部分群)

→ Schreier-Sims のアルゴリズム

→ 置換群の基底を作る

群の表示(=生成元＋関係式)

→ coset enumeration (Todd-Coxeter method)

→ 表示と同型な置換群を作る

置換パズルについて

置換群を可視化する上で非常に有用であり興味を引きやすい

群論の教科書の具体例をパズルで置き換えて実験すると楽しそう

実際にやれること

html canvas による置換パズル UI の実装

Schreier-Sims + Minkwitz により BSGS 作る

→ 計算機群論によるアルゴリズムによって置換パズルごとに「鍵」（Minkwitz data）を作る

→ 置換パズルの任意のシャッフル状態から「鍵」によってそれを解くための手順を作成

これらをすべて JavaScript のみによって実行する

置換パズル(Permutation Puzzles)とは

有限の点集合 $\Omega$ 上の対称群を $\mathfrak{S}_{\Omega}$ と表す

$\Omega$ を「色」の集合 $C$ で着色する

$a\in \mathrm{Map}(\Omega,C)$ に $\sigma\in \mathfrak{S}_{\Omega}$ が次のように右から作用

これは $a$ によってに着色された小石 $\omega$ を小石 $\omega^{\sigma}$ の場所へ移動させることと解釈される

初期状態 $\iota\in \mathrm{Map}(\Omega,C)$ を一つとり

操作の集まり $\sigma_1,\cdots,\sigma_m\in \mathfrak{S}_{\Omega}$ を固定して

これらによって生成された群 $G:=\langle \sigma_1,\cdots,\sigma_m\rangle$ について

$\iota$ の $G$-軌道 $\iota^G$ がシャッフルされたパズルの状態全体であると考えられる

従って, 以下では簡単のために

$C=\Omega$, $\iota=id_{\Omega}$ ($\Omega$ 上の恒等写像)

の場合についてのみ置換パズルおよびそのソルバーの構成について考察していく

即ち

$G=\langle \sigma_1,\cdots,\sigma_m\rangle \leq \mathfrak{S}_{\Omega}$ に対し $id_{\Omega}^G$ のみを扱っていく

$\Omega$ が $\Omega$ 自身によって着色されていると考える

Schreier-Sims アルゴリズムの紹介

置換パズルの群論的ソルバーを実装する上で基本的となるアルゴリズム

与えられた生成系で生成された群の位数を求めることができるだけではなく

任意の置換に対し, それがその群に属するか否か

属した場合, BSGS とよばれる基底のようなものの積として一意的に表すことができる

Schreier の補題

部分群の生成系を与える, 基本的かつ重要な補題

$G=\langle X\rangle$, $H$ を $G$の部分群,

$T$ を $G$ における $H$ の右剰余類分解の完全代表系

$G\rightarrow T\quad (\sigma \mapsto \overline{\sigma})$ を $H\sigma = H\overline{\sigma}$ なる写像

とするとき

$H$ の生成系の濃度が $|T||X|$ となり, $G$ の生成系 $X$ よりも大きくなることに注意！！

Jerrum's filter アルゴリズム

Schreier-Sims アルゴリズムでは, 部分群の列を作っていくが, Schrier の補題から分かるように

(部分群の生成系の濃度)=(右剰余類の濃度)×(元の群の生成系の濃度)

Jerrum's filter は $\mathfrak{S}_n$ の任意の部分群に対し, その生成系の大きさを $n-1$ 以下に抑えられることを証明するだけではなく, 具体的に実装できるアルゴリズム.

$H=\langle X\rangle\leq \mathfrak{S}_n$ を任意の部分群とするとき, $\sigma\in X$ に対し, $i\neq i^{\sigma}$ となる最小の $i$ に対し $\{i,i^{\sigma}\}$ を辺とする無向グラフを作り,

そのグラフから閉路を潰し, 木 (辺の数は $n-1$ 以下になる)にするグラフ理論的方法

Schreier-Sims Algorithm とは

BSGS を求める方法

BSGS = Base + Strong Generating Set

有限集合 $\Omega$ 上の対称群を $\mathfrak{S}_{\Omega}$ と表す

特に $\Omega=\{1,\cdots,n\}$ のときは $\mathfrak{S}_n$ と表す

以下では $G=\langle X \rangle \leq \mathfrak{S}_n$ とする

Base とは $B = (\beta_1, \cdots, \beta_r)$ $(\beta_1,\cdots,\beta_r\in\{1,\cdots,n\})$ であって

とおくとき $G^{(r-1)}\neq 1$ であるが, $G^{(r)}=1$ となるもの.

という形で表すアルゴリズムのことである.

$G^{(i)}\backslash G^{(i-1)}\simeq b_{i}^{G^{(i-1)}}$ はサイズが小さいから,

一般に置換群の濃度は $20!=2432902008176640000$ のように, 計算機で列挙できないサイズであるが,

基底のような役割を演ずる.

Schreier-Sims Algorithm 実装の留意点

$i$ が増えるに連れ Schreier の補題によって構成される $G^{(i)}=G_{\{b_0,\cdots,b_i\}}$ の生成系はそれを含む群の生成系の数倍の大きさになる.

$\rightarrow$ 適切に生成系の大きさを縮小しなければブラウザは簡単にクラッシュ

それを解消する手段として Jerrum's filter を用いる

Schreier-Sims Algorithm だけでは permutation puzzle は解けない

Minkwitz の方法

strong generating set をオリジナルの生成系の語として表示する方法

Minkwitz の原論文を見て, 一応実装できた

JSによる実装の紹介

JSによる実装の紹介(有限行列群への応用)

Minkwitz の方法は実用的ではあるが, 原論文は7ページと短く, 群の表示, 項書換えに関して掘り下げた議論が見いだすことができなかった. (理論的な研究の余地あり？)

BSGS(+Minkwitz) の導出は時間が掛かる

A24 (24 puzzle) の生成には標準的なノートPCで30秒ほどかかる

3x3x3 の rubik's cube では 3 ~ 4 分ほどかかる!

4x4x4 の rubik's cube では 16 時間ほどかかる!

BSGS(+Minkwitz)は置換パズルの鍵なので solver の実装は鍵を使ってドアを開くだけの作業にすぎず, JavaScript であっても容易に実装でき, しかも負荷が少ない.

BSGS の導出および Minkwitz 分解は鍵の鋳造にあたるので高コスト高負荷.

実演

wreath type 1

wreath type 2

Rubik's Torus

Topspin Puzzle

Hungarian Rings

Merge Type

24 Puzzle

Stereographic Rubik's Cube

Stereographic Rubik's Skewb

課題と目標と夢

任意の置換群から, その表示を構成するアルゴリズムを実装

Minkwitz の理論を群の表示や項書換の手法で整理して理解を深める

面白い置換パズルの考察・実装

Klein quartic Rubik's cube 群は24個の位数7の置換によって生成される群

4×4×4 の Rubik's 群の stereographi Rubik's cube パズルの実装

Schreier-Sims + Minkwitz, coset enumeration を RUST などの低レベル言語によって高速化 (JavaScript では 4*4*4 のRubik's cube 群の計算が限界)