夏休みの自由研究～ルービックキューブが群だと何がうれしい？～
皆さんこんにちは。いかのおすしです。
ふるさと納税の返礼品で届いたウニがあまりおいしくなくて萎えていますでしょうか？結構高かったのに。
今回は夏休みということで、ちょっとした長さの記事を書いてみました。
テーマは「ルービックキューブが群だと何がうれしい？」です。
キューブと数学シリーズの第3作になります。
第一作：RとUだけで揃うとはどういうことか？～YruRU methodの話～
導入 本記事を読む上での心構え
「キューブは群である」「だから何？」
よく雑学のような文脈で「ルービックキューブは群論である」と言われます。ルービックキューブをやったことがある理系高校生、大学生であれば、一度は耳にしたことがあるのではないでしょうか？
群論とは数学の一分野で、大学の数学科や物理学科、情報学科などの理系学科で学びます。逆に文系大学や、理系でも数学とは離れた分野の学科では学習しないことが多いです。
実際「ルービックキューブは群論である」は正しくて、群論（の中でも特に「対称群」や「交代群」というやつ）を理解するための教材として、ルービックキューブは非常に優れています。
どころがどっこい、我々キューバ―にとっては「群論の教材としてルービックキューブが優れている！」と言われてもあまりピンときません。そもそも理系大学生の中でも群論を授業でちゃんと習う人は少数派ですし、「確かにキューブ群論じゃん！」となる人は少ないでしょう。
また我々としては、「群論を学ぶ教材としてキューブは最適！」と言われるよりも「群論を使うとキューブについてこんなことがわかるよ！」と言ってほしいものです。
そういうこともあり、キューバ―の中には「なんか群論ってやつがあって、それがキューブと関係しているらしい」ということだけ知っているという人が多いのではないでしょうか？
また巷には、ルービックキューブと群論に関する書籍がそれなりにありますが、「お、ルービックキューブの本だ」と思って手に取ると後悔します。その多くは、ルービックキューブを教材として用いた「群論の教科書」だからです。しかもたいていは、大学数学科3年生以上を対象にした比較的高度な内容です。
今回は、群とは何か？から、それを使うとルービックキューブの何がわかるか？に関してを、中学生程度の知識でもわかるように解説してきます。
本記事の読み方
本記事では、できるだけ中学生や高校生でもわかるように、数学的な厳密性には注目しません。そのため、数学的には「それってちょっと、、」な言い回しを含むことがあります。
厳密性を特に欠く部分は注釈しますが、本記事は数学の教科書ではなく、あくまで読み物として楽しんでください。
また、本記事は「中学生でもわかる」と謳っていますが、そもそも群論を理解するのに高度な数学の前提知識は必要ありません。
群論が難しいと言われる理由の一つに「抽象的すぎる」というのがあります。中学校や高校でやる数学と違い、具体的な数字が全然出てこないままどんどん話が進んでいきます。
抽象数学全般に言えることですが、「ふわっとした概念をふわっと理解する」ことが結構重要です。いちいち具体例を挙げて、一つ一つイメージとして理解することもできなくはないのですが、本質的にはふわっとした概念である以上、なるべくふわっとしたまま理解するのが正しいやり方だと思っています。
１章 「群」とは？
本章では、「群」ってやつはいったい何なんだという話をします。厳密な群の定義を紹介するというよりは、群というもののとらえ方をわかっていただけるように書くつもりです。
群とは何かをなんとなく理解する
wikipediaで「群」を引いてみると、以下のように書いてあります。
数学における群とは、ある二項演算とその対象となる集合とを合わせて見たときに結合性を伴い単位元と逆元を備えるものをいう。
、、、ちょっと待ってください。帰らないでください。さすがに呪文過ぎるので、以下のように言い直してみました。
数学における群とは、２つの「モノ」を使ってもう一つの「モノ」を作り出すことができるような、「モノ」の集まりのこと。
例えば、「色」という集まりを考えてみます。色という集まりの中には、「赤」や「青」や「黒」などのモノが含まれます。この集まりには、珍しい名前の色や、名前がついていないものも含め、色であれば何でも含むことにしましょう。
ここで、色を２つ取ってきて、それを混ぜることで新しい色を作ることを考えます。例えば赤と青を取ってきたら紫ができるというわけです。
ここで出来上がった紫は、当然もとの「色」という集まりに入っています。
当然、紫と別の色を取ってきたり、勿忘草色と錆鉄御納戸色を取ってきて混ぜたとしても、出来上がる色はもとの集まりの中にあるはずです。
このように、「どんな二つを取ってきて混ぜても、新しく生まれたモノもまた元の集まりの中にある」ような集まりのことを「群」と言います。
よって、「色」という集まりは「群」であると言えます。※１
数学では、何かの集まりのことを「集合」と言います。
集合に含まれる一つ一つのモノのことを「要素（または元）」と言います。
※１：「色」の集合には逆元がないと思われるので、厳密に群と言えるかは慎重になる必要があります。
ルービックキューブが群である理由
さて、群とは何かがなんとなく分かったところで、ルービックキューブが群であるという話をしていきます。
ルービックキューブの状態を考えてみましょう。ルービックキューブの状態は、43,252,003,274,489,856,000通りあるそうです。
今、この43,252,003,274,489,856,000通りがすべて入った集まりを考えます。
この集まりには、完成状態、完成状態から「U」した状態、「U2」した状態、「U'」した状態、「R」した状態、…、、、、…、「B D B2 U R2 D' L2 D R2 U R2 U' L F' R2 D2 U L' D' F R」した状態、…（ほかにもいろいろ）
などなど、とにかくすべての状態が入っています。
この箱の中から２つを取り出します。例えば、『「R」した状態』と『「U」した状態』を取り出しましょう。
群であるためには、２つを混ぜてできるモノが、もとの集まりの中にあるかどうかを考えればよいです。
『「R」した状態』と『「U」した状態』を混ぜて、『「R U」した状態』ができあがります。
さて、今出来上がった『「R U」した状態』はもとの集まりにあるでしょうか？答えはもちろんYesです。ルービックキューブの状態すべてが入った集まりを考えたので、当然『「R U」した状態』も入っています。
他にも、どんな二つを取ってきても、それらを混ぜてできる新しい状態はもとの集まりに入っています。
ということで、最初に用意した「ルービックキューブの状態すべてからなる集まり」は群であることがわかりました。
★発展★
もう少しきちんと「群である」ということをいうには、以下の二つが言えるとさらに良いです。
１．「何もしない」に対応する状態がある（単位元の存在）
２．すべての状態に対して、「その逆の状態」がある（逆元の存在）
１．「何もしない」に対応する状態がある
これは、取ってくる２つの状態のうち一つを「完成状態」にすればよいですね。
２．すべての状態に対して、「その逆の状態」がある
これは、ある状態に対して、その逆スクランブルに対応する状態ということにしましょう。例えば「R」した状態の逆は「R'」した状態、「R U F」した状態の逆は「F' U' R'」した状態です。
というわけで、追加の二つもきちんと言えたので、「ルービックキューブの状態すべてからなる集まりは群である」ということがきちんと言えました。
【補足】「状態」と「手順」は同じこと
ある制約下で、「キューブの状態」と「手順」は1対1対応します。制約とは、「同じ状態を与える手順の組は、同一とみなす」というものです。
例えば、A-permを回すのにも、以下のように複数通りの手順があります。
x' R2 D2 R' U' R D2 R' U R' x
R' D' R U' R' D R U2 R' D' R U' R' D R
これらを同一視することで、キューブの状態と手順は同じ意味、と言えます。ある手順を「状態」に言い換えたければ、手順によって得られる状態を持ってくればよいし、ある状態を「手順」に言い換えたければ、完成状態からその状態を得るための手順の一つを持ってくればよいです。
２章 13回の繰り返しで元に戻る手順は存在しない
さて、１章では、どうやら群とかいうよくわからんのがあって、ルービックキューブはそれらしい。ということがわかりました。
２章では、群論の考え方に踏み込んで、ルービックキューブの何がわかる？という話をしていきます。
手順を繰り返すと元に戻るよね
キューブをやっていると経験的にわかりますが、すべての操作は、それを何回か繰り返すと元に戻ります。
例えば「U」は4回で元に戻りますし、U-permは３点交換なので、３回で元に戻ります。
他にどのような操作を持ってきても、その操作を有限回繰り返すことで必ず元に戻ります。これは経験的には明らかですよね。
どころで、これってなぜでしょうか？なんとなく当たり前のように思えますが、ちゃんと証明してみろと言われたら少し難しいですよね。
本章では、群論の考え方を使い、「繰り返しによって元に戻る」という性質について考えていこうと思います。
エッジの配置をすべて集めた群
3*3*3キューブにエッジは12個あります。ここで、この12個のパーツの置換すべてからなる集合を考えてみましょう。
エッジパーツに1~12の番号を付けて、それを並び替えた数列を考えるのと同じです。ここには、
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 11
1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10, 12
1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 10
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
1, 2, 3, 4, 5, 6, 7, 8, 10, 9, 11, 12
……
12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
と、1~12までの並び替え全通りが入っています。そのパターン数は12! = 479001600通りです。そしてこの集合はもちろん群としての条件を満たします。以下、この群のことを「エッジ群」と呼ぶことにします。
ここで、群に入っている元の個数のことを一般に「位数」と言います。すなわち、エッジ群の位数は12!です。
※実際には、エッジには「向き」の概念がありますが、ここでは無視することができます。
ある手順の繰り返しで得られる状態からなる群
先ほど考えたエッジ群を$${ S }$$ とします。また完成状態に対し、ある手順Eを0回以上適用して得ることができるエッジの状態すべてからなる群を$${ A_E }$$とします。
ここで、$${A_E}$$は$${S}$$に完全に包含される、ということが言えます。$${S}$$にはエッジの状態すべてが入っているので、当然手順Eによって生成されるものもすべて含むからです。
※このように、ある群Ａが別の群Ｂを完全に包含していることを、「BはAの部分群である」と言います。
ここで、群論を進めていくうえで欠かせない重要定理を紹介します。
Gを群とする。Gの任意の部分群の位数は、Gの位数を割り切る。
部分群の位数は、それを包含している大きな群の位数の約数になるというわけです。証明は省略しますが、「ラグランジュの定理」として一般的に知られている定理です。
※群論を知らない状態で一から証明するのは難しいと思います。
ひとまずこの定理を使うと、$${S}$$の部分群である$${A_E}$$の位数は、$${S}$$の位数である12!を割り切ることがわかります。
何回繰り返すと元に戻る？
先ほど考えた$${A_E}$$について、もう少し考えてみましょう。
$${A_E}$$の中にはいくつかの"状態"が入っており、それらはすべてある手順Eの繰り返しによって出現するものです。ここで、次のことが言えます。
$${A_E}$$の位数を$${n}$$とする。完成状態に対して手順Eをn回繰り返すと、元の完成状態に戻る。
以下、さらっと証明します。（長くなるので厳密性は省略します。腕に自信のある人は厳密な証明を書いてみてください。）
これを証明するには、以下が言えればよいです。
１．$${A_E}$$は1以上の有限個の元をもつ
２．$${A_E}$$に含まれるすべての状態は、手順Eの繰り返しによって到達可能である
３．$${A_E}$$に含まれるすべての状態について、手順E及び手順Eの逆手順を適用した際に出現する状態がただ一通りに定まる。
では順番に見ていきましょう。
１．$${A_E}$$には少なくとも「完成状態」が含まれ、かつ、前節で示した通り$${A_E}$$の位数は$${S}$$の位数である12!を割り切るため有限です。よってこれはOK
２．$${A_E}$$の作り方より自明です。
３．これも、キューブのことだと思えば自明です。ある状態に対してある手順を適用した後の状態は、ただ一通りに定まります。「同じ手順を回しているのに毎回結果が違う！」ということは起こりません。
よってここまでで、「$${A_E}$$の位数をnとすると、完成状態に対して手順Eをn回繰り返すと元に戻る」ということが証明できました。
１．に反する：元が無限個ある
２．に反する：手順Eによってて到達できない元が含まれている
３．に反する：ある元に手順Eを適用したときの遷移が複数通りある
ちょうど13回の繰り返しで元に戻るような手順は存在しない
さてここまでで、表題のことを言うための準備が整いました。実際に言ってみましょう。
$${A_E}$$の位数をnとする。$${A_E}$$は$${S}$$の部分群であるため、nは12!の約数である。すなわちnは13の倍数でない。したがって、ちょうど13回の繰り返しで元に戻るような手順Eは存在しない。
言えました！群論を使って、キューブの性質を導くことができましたね。
※「『ちょうど』13回」というのは結構重要です。ゼロ手順（キューブの状態を何も変化させないような手順）は、任意のnについてn回の繰り返しで元に戻る、と言えなくもないので。「13回目ではじめて元に戻る」と言い換えてもよいです。
コーナーにも拡張する（練習問題）
ここまではエッジに限って考え、「ちょうど13回の操作によって元に戻るような手順は存在しない」ということを証明しました。
ただ実際のキューブにはエッジの他にコーナーもあります。
実は、コーナーまできちんと考慮して考えても、「ちょうど13回の繰り返しによって元に戻る操手順は存在しない」という結論は変わりません。
同じように考えると導くことができるので、数学好きな方はぜひやってみてください。
３章 群論のすすめ
ここまでで、群論とかいうやつがあって、それを使うと「ちょうど13回の繰り返しによって元に戻る手順は存在しない」ということがわかりました。
ただここまでの内容は、正直群論を使わなくてもギリギリ証明できる話です。ここからは、群論の面白さについて語り、皆さんもぜひ群論を学んでみませんか？という話をしていきます。
加法群の話
群の定義に立ち返ってみましょう。
・ある「モノ」と別の「モノ」を合体させて新しい「モノ」を作る
というのが重要でした。
ここで試しにモノとして正の整数、合体の方法として足し算（加法）を選んでみましょう。加法の下の群ということで、「加法群」と言います。そのままですね。
正の整数は普通に扱うと無限個あるので、「正の整数をpで割ったあまり」を使うことにします。pで割ったあまりは 0～p-1 までのp個あります。すなわち加法群の位数はpです。
ここで、次のことが言えます。
すべての正の整数nについて、nをpで割ったあまりをp回足し合わせたものは、pで割り切れる。
「逆に何言ってるんだ？」というくらい当たり前ですね。後半の「p回足し合わせたものはpで割り切れる」の部分だけで当たり前です。
だからなんやねんというレベルの定理なのですが、いったん次に進みましょう。
乗法群（フェルマーの小定理）
さて次に、モノとして正の整数、合体の方法としてかけ算（乗法）を選んだものを考えましょう。乗法のもとの群ということで「乗法群」と言います。
加法群と同様に、正の整数を無理やり有限個にするために「pで割ったあまり」を考えます。ただし、かけ算において0は特殊な意味を持つので、これを除いて1, 2, 3, … , p-1までのp-1個を考えます。すなわち、乗法群の位数はp-1です。
ここで、次の定理が成り立ちます。
pを素数とする。すべての正の整数nに対して、nをpで割ったあまりをp-1回かけたものをpで割ったあまりは1である。
これはあまり自明ではないですね。でも実はちゃんと成り立ちます。具体的な数字をいくつか入れてみるとわかるかと思います。
実はこれは「フェルマーの小定理」と呼ばれる、整数の分野でよく知られた定理です。高校時代に習った人もギリいるかも。
さて、加法群と乗法群でそれぞれ定理を一つずつ見てきましたが、実はこれらは全く同一の定理と捉えることができます。以下のように書いてみましょう。
Gを群とする。Gに含まれる任意の元について、それをGの位数の数だけ合体させると、単位元になる。
「単位元」とは、「何もしない」に対応する元のことです。加法群の場合は何も足さないということで0が該当し、乗法群の場合は何もかけないということで1が該当します。
加法群に関する定理、乗法群に関する定理とよく見比べてみると、「元に関する一般的な定理」をそれぞれの群に具体的に言い換えただけで、本質的には全く同じことを言っていることがわかります。
ルービックキューブの基本定理の解釈
さて、ルービックキューブの話に戻ってきました。先ほどの、群に関する一般的な定理をルービックキューブ群に適用してみましょう。
Gを群とする。Gに含まれる任意の元について、それをGの位数の数だけ合体させると、単位元になる。
ルービックキューブ群における単位元は「完成状態」であることに注意すると、以下のように書けます。
ルービックキューブに適用することができる任意の手順について、完成状態からその手順をルービックキューブ群の位数の回数だけ繰り返すと、完成状態に戻る。
ルービックキューブ群の位数は43,252,003,274,489,856,000なので、任意の手順は43,252,003,274,489,856,000回繰り返すと元に戻ることが証明できました。
ちなみに43,252,003,274,489,856,000 = 8!×12!×3^7×2^11÷2で、13以上の素因数を含まないため、上記で長々と証明してきた「ちょうど13回の繰り返しで元に戻る手順は存在しない」も、この定理からだと簡単に導くことができます。（例によって興味のある方は導いてみてください）
群論ってすごいのではないか
ここまでお読みいただきありがとうございます。ここまで読んでくれたあなたは、今日から自信をもって「ルービックキューブって群論なんですよ！」と言いまわってよいです。
今回紹介したお話は、群論×ルービックキューブのほんの一部です。
群論では、加法群に関する定理、乗法群に関する定理、（あるいはルービックキューブ群に関する定理も）を、一般化してまとめることができました。これが「抽象化」というやつです。
他にも、群論の考え方を使うことでわかるルービックキューブキューブの性質はたくさんあります。機会があればまた紹介します。
あとがき
わかりやすく書くって難しい
これは抽象数学全般に言えることですが、キューブと群論の話をきちんと掘り下げていくと、結構早い段階でキューブが出てこなくなります。
実際、クロックの記事の時は途中からクロックは出てこず、線形代数とアルゴリズムの話になってました。
ただでさえ難しい群論の話に、キューブすら出てこなくなるとさすがに読んでられません。
自分が理解していることを相手の前提知識に立ってわかりやすく伝えるって難しいなと思いました。特にこういうWeb記事の場合は、途中で飽きられないような書き方も求められますし。
キューブと数学シリーズ第4弾は「『結構揃ってる』は本当に揃っているのか？」の予定です。それではまた次回。