JavaScript で Computational Group Theory

きっかけ

Schreier-Sims アルゴリズムを実装したい

M24 などの元(244823040個ある)を具体的に記述したい

permutation puzzle の solver を作りたい

2018年8月ぐらいのこと

お題目

ca.js の紹介

Schreier-Sims の実装紹介

Minkwitz の方法の実装紹介

Three.js にはまる

よく知られた置換パズルを Schreier-Sims で解く

今回のゴール

Three.js で実装した 2x2x2 の rubik's cube の solver を

Minkwitz の方法で実装する

ca.js とは

JavaScript の多倍長整数ライブラリ big-integer.js のみを利用した

自作数式処理ライブラリ

web ブラウザの計算能力のみで計算したい

2016年頃から作り始める

元々自身の知的探求と数式処理の教科書の勉強のためにJSを利用したことが動機

SymPy もライブラリを利用せず Python のみで書かれており, 目標が共通

具体的に何をしてきたのか

• Pell 方程式 [00-07]
• groebner 基底 [05-12]
  (丸山正樹著 「グレブナー基底とその応用」 p82 「性能の低い計算機代数のソフトでは相当待っても答えが出ない」)
• 単因子計算 [13-02]
• Jordan 標準形計算 [13-03]
• Hensel 構成による因数分解 [02-15, 02-21]
• Schreier-Sims アルゴリズム [15-11] など
• Minkwitz factorization [15-15, 15-16] など
• ADHD?

Schreier-Sims Algorithm とは

• BSGS を求める方法
• BSGS = Base + Strong Generating Set
• 有限集合 $\Omega$ 上の対称群を $\mathfrak{S}_{\Omega}$ と表す
• 特に $\Omega=\{0,1,\cdots,n-1\}$ のときは $\mathfrak{S}_n$ と表す
• 以下では $G=\langle \sigma_1,\cdots,\sigma_r\rangle \leq \mathfrak{S}_n$ とする
• Base $0\leq b_0\leq \cdots \leq b_s \leq n-1$ が構成し
• $G=\prod_{i=0}G_{\{b_0,\cdots,b_i\}}\backslash G_{\{b_0,\cdots,b_{i-1}\}}$ と集合で表す方法
• これを JavaScript で実装しました ca.js [15-05~15-08]

Schreier-Sims Algorithm の困難

• 途中で生成される $G_{\{b_0,\cdots,b_i\}}$ の生成系が肥大化
• それを解消する方法が Jerrum's filter
• $G_{\{b_0,\cdots,b_i\}}$ の位数を $n$ 以下に抑えることができる
• cycle を潰し, spanning tree にするグラフ理論的方法
• ca.js [15-09]

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

• Minkwitz の方法
• strong generating set を 元の生成系とその逆元の語で表示する方法
• オンラインの論文(理解できない)を見て, 無理やり実装
• 正直正しいものかどうかどうか怪しいが一応実装できた
• ca.js [15-14]

BSGS は時間が掛かる

• 生成系は小さいので, ca.js に配列として保存しておく
• A24 の生成には標準的なノートPCで30秒ほどかかる
• 利用のたびに何度もBSGSを生成するのは不合理
• BSGS とその Minkwitz factors は一度計算すれば web storage に保存
• 利用のたびにBSGSを web storage から呼び出せばよい
• ca.js [20-00]

Rubik's cube に適用したくなる

• Three.js を使おう　
• 和島茂先生のサイトに感銘を受ける
• 遠藤理平氏のサンプルコードから頑張って自力で実装
• 最終的に633行で収まる
• Minkwitz's factorization を適用しようとするが,
• うまくいかず懇親会に行けず, ホテルで徹夜でデバッグ
• 2x2x2 と 1x1x1 で Minkwit の方法が上手く働いた

Rubik's cube をやってみよう

今後の目標

より大きな rubik's cube の solver 作成

他の置換パズルの solver 作成

coset enumeration の実装