ルービックキューブと群論

ルービックキューブと群論 宇佐見 公輔 2020 年 10 月 3 日 1/22 宇佐見 公輔 ルービックキューブと群論

自己紹介 職業：プログラマ / 趣味：数学 最近の活動（登壇・ブログ・Twitter）： 平面の敷き詰めとルート系（2020 年 6 月 / 日曜数学会） 四元数のはなし（2020 年 5 月 / 関西日曜数学友の会） はじめて学ぶリー環 ノート（2020 年 4 月〜 / Twitter） Ising 模型 ノート（2020 年 3 月〜4 月 / Twitter） Onsager 代数の話（2020 年 3 月 / 京都某所） はじめて学ぶリー群 ノート（2020 年 1 月〜3 月 / Twitter） 2/22 宇佐見 公輔 ルービックキューブと群論

今日の話 今日はルービックキューブの話です。過去の発表内容とは特に関 係ありません。 ルービックキューブを数学的に考えるにはどうするのかという話 と、SageMath での計算の紹介になります。 3/22 宇佐見 公輔 ルービックキューブと群論

ルービックキューブ 3 × 3 × 3 が普通ですが、2 × 2 × 2 など別サイズもあります。 4/22 宇佐見 公輔 ルービックキューブと群論

ルービックキューブの数学的な解析 ルービックキューブに対する興味の持ち方は様々です。 6 面完成させる解法は？ スピードキューブ（完成までの時間を競う） キューブの機構はどうなっているのか？ ここでは、ルービックキューブパズルを数学的に解析することを 考えます。ルービックキューブは、群論の言葉を用いて記述する ことが可能です。 5/22 宇佐見 公輔 ルービックキューブと群論

考察にあたっての前提 3 次元空間の中でキューブの位置や向きを固定して考えます。 キューブそのものを回転させることは考えません。 キューブの操作は、各面を時計回りまたは反時計回りに 90 度ずつ 動かすことを考えます。真ん中の列を回転させることはしません。 6/22 宇佐見 公輔 ルービックキューブと群論

小方体（cubelet） 小方体：キューブを構成する小立方体。中心を除いて 26 個。 1 面体：1 つの面が外側に見えている小方体。6 個。 2 面体：2 つの面が外側に見えている小方体。12 個。 3 面体：3 つの面が外側に見えている小方体。8 個。 先ほどの前提から、1 面体は動きません。2 面体と 3 面体がキュー ブの操作によって移動します。 7/22 宇佐見 公輔 ルービックキューブと群論

小面（facet） キューブの各面を構成する正方形を小面と呼びます。各面で中央 を除いて 8 個、全体で 48 個あります。 +--------------+ | 1 2 3 | | 4 top 5 | | 6 7 8 | +------------+--------------+-------------+------------+ | 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 | | 12 left 13 | 20 front 21 | 28 right 29 | 36 rear 37 | | 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 | +------------+--------------+-------------+------------+ | 41 42 43 | | 44 bottom 45 | | 46 47 48 | +--------------+ 番号づけの規則は何でもよいです。上図は SageMath の出力です。 8/22 宇佐見 公輔 ルービックキューブと群論

小面のシングマスター記法 番号づけの代わりに、シングマスター記法という方法もあります。 上下左右前後の各面に u, d, l, r, f , b を割り当てる 2 面体上の小面：xy 形式 x は小面を含む面 y は隣接する面 3 面体上の小面：xyz 形式 x は小面を含む面 y と z は隣接する面 例：下図の 7 は uf 、18 は fu、6 は ufl、17 は flu と書けます。 +--------------+ | 1 2 3 | | 4 top 5 | | 6 7 8 | +------------+--------------+-------------+------------+ | 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 | | 12 left 13 | 20 front 21 | 28 right 29 | 36 rear 37 | | 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 | +------------+--------------+-------------+------------+ | 41 42 43 | | 44 bottom 45 | | 46 47 48 | +--------------+ 9/22 宇佐見 公輔 ルービックキューブと群論

キューブ操作のシングマスター記法 各面を時計回りに 90 度回転する操作を U, D, L, R, F, B と書くこ とにします。 10/22 宇佐見 公輔 ルービックキューブと群論

キューブ操作と置換 X を小面 48 個の集合とします。キューブ操作は、X の置換写像で あると考えることができます。 例えば操作 R は、以下のような置換です。小面を 20 個動かしま す。4 個の元の巡回置換が 5 つ起こります。 rf ↦→ ru ↦→ rb ↦→ rd ↦→ rf ruf ↦→ rub ↦→ rbd ↦→ rdf ↦→ ruf fr ↦→ ur ↦→ br ↦→ dr ↦→ fr fur ↦→ ubr ↦→ bdr ↦→ dfr ↦→ fur fdr ↦→ ufr ↦→ bur ↦→ dbr ↦→ fdr 11/22 宇佐見 公輔 ルービックキューブと群論

キューブ操作と置換 (2) もうひとつ例を見ます。R を 2 回行った R2 は、以下のような置換 です。2 個の元の互換が 10 個起こります。 rf ↦→ rb ↦→ rf ru ↦→ rd ↦→ ru ruf ↦→ rbd ↦→ ruf rub ↦→ rdf ↦→ rub fr ↦→ br ↦→ fr ur ↦→ dr ↦→ ur fur ↦→ bdr ↦→ fur ubr ↦→ dfr ↦→ ubr fdr ↦→ bur ↦→ fdr ufr ↦→ dbr ↦→ ufr 12/22 宇佐見 公輔 ルービックキューブと群論

対称群 集合 X の置換全体の集合 SX は群になります。これを X の対称群 と呼びます。 SX := {f : X → X | f は全単射} キューブ操作（の組み合わせ）は、小面集合 X の対称群に含まれ ます。 13/22 宇佐見 公輔 ルービックキューブと群論

ルービックキューブ群 小面集合 X の対称群 SX の中にはキューブ操作の組み合わせだけ では実現できないものもあります。 例えば、3 面体のひとつをルービックキューブから取り外して、小 面のうち 2 つの色を逆に貼り替えてからルービックキューブに戻 す、ということをします。これは小面集合 X の置換にはなってい ますが、キューブ操作だけでは元の配置に戻すことができません。 基本操作 U, D, L, R, F, B で生成される SX の部分群 G を、ルー ビックキューブ群と呼びます。 G := hU, D, L, R, F, Bi ⊂ SX 14/22 宇佐見 公輔 ルービックキューブと群論

SageMath SageMath は数学関連のソフトウェアを統合したものです。 SageMath には、ルービックキューブ群を扱うプログラムが最初 から組み込まれています。 15/22 宇佐見 公輔 ルービックキューブと群論

ルービックキューブ群を SageMath で扱う sage : rub ik = CubeGroup ( ) sage : rub ik . p l o t _ c u b e ( " " ) sage : rub ik . plot3d_cube ( " " ) 16/22 宇佐見 公輔 ルービックキューブと群論

ルービックキューブ群を SageMath で扱う (2) sage : rub ik = CubeGroup ( ) sage : rub ik . p l o t _ c u b e ( "R" ) sage : rub ik . p l o t _ c u b e ( "R∗U" ) 17/22 宇佐見 公輔 ルービックキューブと群論

SageMath とシングマスター記法 sage : rub ik = CubeGroup ( ) sage : rub ik . d i s p l a y 2 d ( " " ) +--------------+ | 1 2 3 | | 4 top 5 | | 6 7 8 | +------------+--------------+-------------+------------+ | 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 | | 12 left 13 | 20 front 21 | 28 right 29 | 36 rear 37 | | 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 | +------------+--------------+-------------+------------+ | 41 42 43 | | 44 bottom 45 | | 46 47 48 | +--------------+ sage : from sage . groups . perm_gps . cubegroup import ∗ sage : i n d e x 2 s i n g m a s t e r ( 1 7 ) ’ flu ’ 18/22 宇佐見 公輔 ルービックキューブと群論

ルービックキューブ群の位数 ルービックキューブ群は定義から有限群ですが、その大きさがど れくらいなのか見てみます。 sage : rub ik = CubeGroup ( ) sage : rub ik . order ( ) 43252003274489856000 sage : rub ik . order ( ) . f a c t o r ( ) 2^27 ∗ 3^14 ∗ 5^3 ∗ 7^2 ∗ 11 19/22 宇佐見 公輔 ルービックキューブと群論

元の位数 ルービックキューブ群の元の位数（gm = 1 を満たす最小の m）も 見てみましょう。 操作 R は 4 回行えば元に戻ります。 sage : R = rub ik . move ( "R" ) [ 0 ] sage : R . order ( ) 4 ルービックキューブ群には位数 1260 の元があります。そのひとつ が RU2 D−1 BD−1 です。これより大きい位数の元はありません。 sage : J = rub ik . move ( "R∗U^2∗D^−1∗B∗D^−1" ) [ 0 ] sage : J . order ( ) 1260 20/22 宇佐見 公輔 ルービックキューブと群論

その他の豆知識 どんな配置でも 20 手以内で 6 面完成できることが知られて います（ただし、180 度回転も 1 手とみなして数えた場合。 180 度回転を 2 手とするときは 26 手となる）。 ルービックキューブ群は単純群ではありません（非自明な正 規部分群を持つ）。 分解の例：G  (Z73 × Z11 2 ) o ((A8 × A12 ) o Z2 ) 21/22 宇佐見 公輔 ルービックキューブと群論

まとめ・参考文献 ルービックキューブ群は群論の題材として（ちょっと大きいです が）良いものだと思います。また、SageMath を使うといろいろ 遊べるのも良いと思います。 参考文献： David Joyner、群論の味わい −置換群で解き明かすルービッ クキューブと 15 パズル− 島内剛一、ルービック・キューブと数学パズル 22/22 宇佐見 公輔 ルービックキューブと群論