はじめに
この記事で話すこと:
- パズルを例題にして実験計画法っぽい問題の解法を紹介する
- その背景にある数学的構造を紹介する
この記事を読む際に仮定する知識：
- 高校レベルの数学（因数分解）
- 簡単な線形代数
ガロア体（有限体）の理論
この章で話すこと：
- 一番簡単なガロア体について時計算を例として紹介する
- ガロア体を拡大する話を紹介する
- 簡単な計算例を紹介して感じを知ってもらう
体とは
体（たい, 英語だとfield,ドイツ語だとKörper(bodyの意味)）とは、すごく大雑把な話をすると足し算、引き算、掛け算、割り算ができる集合のことです。
ここでいう割り算とは、「０でない数に対し、かけて１になることができる数(逆数)が存在すること」を意味します。例を見ていきましょう。
体の例：
- 実数は $\mathbb{R}$ は体。足し算、引き算、掛け算は普通に小学校で習いますし、実数 $a$ の逆数は $1/a$ であり、これは実数なので体です。
- 複素数 $\mathbb{C}$ も同様に足し算、引き算、掛け算ができ、逆元も存在するので体。
- 整数 $\mathbb{Z}$ は足し算、引き算、掛け算はできますが、逆元が存在しないので体ではありません（ 1/2 は整数ではないので割り算ができない）
まあなんか普通の数のことを偉そうに言うとんなと思ってください。
次に実数以外の体の世界を紹介します。
ガロア体（有限体）の例
時計算ってあるじゃないですか。１４時は２時だし、５時は１７時だとみんな計算できます。
１１時の２時間後は１時と足し算もできますし、４時の５時間前は１１時と引き算もできます。
式で書くと以下の意味不明な計算式を頭の中でやっているわけです。
$$14 = 2,\ 5 = 17 \\
11 + 2 = 1, \ 4-5 = 11$$
これって何故できるかというと、１２を０としてグルグル回るイメージを持っているかと思います。
こういう計算方法を導入することで有限体（以下ガロア体と呼びます）が構成できます。
以下数学:
$p$ を素数とする。整数をpで割った際の余りの世界を考えると足し算、引き算、掛け算ができる。
例えば $p = 5$ とすると、
- $2 + 3 = 0$
- $3 * 3 = 9 = 4$
- $2- 3 = -1 = 4$
になります。
また、逆元については
$3 * 2 = 1$ なので $1/3 = 2$ ということが言えます。
逆元の存在が任意の素数と、任意の数について言えることは証明が必要ですが、今回は見送ります。
大事なのは素数の時にのみ逆元が存在するということです。
こういうものを $\mathbb{F}_p$ と書き、ガロア体と呼びます。
ここまでのまとめ：
時計算を１２時基準から素数基準にしたら、足し算、引き算、掛け算、逆元の存在が言え、これは体になる。
この体を $\mathbb{F}_p$ と書く。 $\mathbb{F}_p$ の要素は $0,1, \ldots, p-1 $ であり、 $p$ 個の要素からなる集合であり、足し算、引き算、掛け算、割り算が可能。
ガロア体の二次拡大
ここでガロア体をより大きくする話を考えたいのですが、その前に実数体 $\mathbb{R}$ から複素数体 $\mathbb{C}$ を作ったときの話を思い出すとスムーズなのでそっちをやります。
複素数体は $a + bi$, ($a, b \in \mathbb{R}$) というものでした。
では「 $i$ ってなんでしょう？」と聞かれると「２乗すると $-1$になる謎の数」みたいな返答が返ってきます。
この $i$ の正体を数学的に定義すると、実数 $\mathbb{R}$ に $x$ という変数を付け加えて $x^2 +1 = 0$ という関係式を入れたものになります。
つまり $x^2 = -1$ の解となるものを仮想的に付け加えたものが複素数体になるわけです。
この様にもうこれ以上因数分解できないという多項式を関係式として導入することで、解をその体に付け加えて拡大体を作る事が可能になります。
ちなみに複素平面が２次元的にイメージできるのは $x^2 +1 = 0$ という関係式が２次式だからです。
ここまでのまとめ：
- 複素数体というのは実数体に $x$ という変数を付け加えて、 $x^2 + 1 = 0$ という関係式で割ったもの。
- あるいは同じことだが、実数体に $x^2 + 1 = 0$ の解付け加えたものを複素数体という。その解を $i$ と書いて虚数と呼ぶ。
- $x^2 + 1 = 0$ というのは実数の範囲ではこれ以上因数分解ができないのがポイント。
では有限体でその拡大体を考えてみましょう。簡単のために $p = 2$として進めます。
ここで考えるガロア体 $\mathbb{F}_2$ というのは2で割った余りの世界なので、集合としては $\{0, 1\}$の２つの元からなる集合です。
ではこの世界で因数分解できない２次式を考えてみましょう。
少し考えてみると $f(x) = x^2 + x + 1$ という2次式は $\mathbb{F}_2$ では因数分解できません。というのも 0,1を代入しても $f(x)=0$とはならないため因数を持たないからです。
よって $\mathbb{F}_2$ に $x$ という変数を付け加えて $x^2 + x + 1 = 0$ という関係式を加えると２次拡大が得られます。
別の言い方をすると $\mathbb{F}_2$ に $x^2 + x + 1 = 0$ の解を付け加えたものが $\mathbb{F}_2$ の２次拡大になります。
これを
$$\mathbb{F}_{2^2} = \mathbb{F}_4 $$ と書くことにします。
ここまでのまとめ：
- ガロア体 $\mathbb{F}_2$ に $x^2 + x + 1 = 0$ の解を付け加えたものを $\mathbb{F}_4$ と書く。これは $\mathbb{F}_2$ の拡大体になる。
- $x^2 + x + 1 = 0$ は $\mathbb{F}_2$ では因数分解できないことに注意。
計算例
では $\mathbb{F}_4$ の元はどんなものかを考えます。
$x^2 + x + 1 = 0$ の解を $\alpha$ とすると、 $\mathbb{F}_4 = \{ n + m \alpha \ |\ n,m \in \mathbb{F}_2\}$ となります。
もうちょっとちゃんと元を書くと $\mathbb{F}_4 = \{ 0, 1, \alpha, 1 + \alpha \}$ と４つの元からなります。
$\alpha$ は $x^2 + x + 1 = 0$ の解なので $\alpha^2 + \alpha + 1 = 0$ を満たすことに注意します。
では体なので掛け算の例をみてみましょう。
- $\alpha^2 = - \alpha - 1 = \alpha + 1$ (2で割った余りの世界なので $-1 = 1$ に注意)
- $ (1 + \alpha )^2 = 1 + 2 \alpha + \alpha^2 = 1 + \alpha^2 = 1 + \alpha + 1 = \alpha$ (2で割った余りの世界なので$2 = 0$に注意)
こんな感じで掛け算ができます。逆元もみてみましょう。
- $\alpha (1+\alpha) = \alpha + \alpha^2 = 2\alpha + 1 = 1 $
より $\alpha$ と $(1+\alpha)$ は互いに逆元の関係になっています。
こんな感じで４つの元からなる体が構成できました。
麻雀問題
ここから有限体と実験計画法と線形代数を用いてパズルを解いていきます。
問題
「16 人で麻雀を 5 回戦行なう（各回で 4 卓ずつ延 20 組できる）とき， どの 2 人もちょうど 1 回ずつ顔が合うような集合を作れ」
この問題文については、こちらのサイトから借用しました。
もうちょっと噛み砕くと、「16人参加している麻雀大会で5回戦まで行いました。終わってみれば全員とちょうど一回ずつ麻雀やったなあとみんなが思う組み合わせを作れ」ということになります。
こういうのがアルゴリズムで解けるようになると、いろんな企画を行う際に実際に使えそうですね。
解法
先に言っちゃうと答えはこれです。
$$
\begin{pmatrix}
0 & 0 & 0 & 0 & \ 1 & \ 1 & \ 1 & \ 1 & \ 2 & \ 2 & \ 2 & \ 2 & \ 3 & \ 3 & \ 3 & \ 3 \\
0 & \ 1 & \ 2 & \ 3 & 0 & \ 1 & \ 2 & \ 3 & 0 & \ 1 & \ 2 & \ 3 & 0 & \ 1 & \ 2 & \ 3 \\
0 & \ 1 & \ 2 & \ 3 & \ 1 & 0 & \ 3 & \ 2 & \ 2 & \ 3 & 0 & \ 1 & \ 3 & \ 2 & \ 1 & 0 \\
0 & \ 2 & \ 3 & \ 1 & \ 1 & \ 3 & \ 2 & 0 & \ 2 & 0 & \ 1 & \ 3 & \ 3 & \ 1 & 0 & \ 2 \\
0 & \ 3 & \ 1 & \ 2 & \ 1 & \ 2 & 0 & \ 3 & \ 2 & \ 1 & \ 3 & 0 & \ 3 & 0 & \ 2 & \ 1 \\
\end{pmatrix}
$$
それぞれの列ベクトル（縦）が人を表しており、行ベクトル（横）が各回戦を表しています。
成分の各数字が麻雀卓を表しており、よく見ると（各列ベクトルごとに同じ数字の人を消していく操作を16*5回繰り返して確認していくと）答えになっています。
ではどうやってこの行列を作ったのかの解法に移ります。
まず各成分が $\mathbb{F}_{4} $ の元を持つ 5 * 16 の行列を作ることを考えます。
ここで、5は5回戦まで行うことから来ており、16は人数、 $ \mathbb{F}_{4}$ の元は4種類あるので $0,1,α, α+1$ の4つの卓を表します。
さて、この行列で問題文の条件に合うような行列を作りたいわけですが、これだけだと $4^{16\times5}$ 通りの行列を考えることになるため条件を付け加える必要があります。
そこで実験計画法由来で必要な条件が以下の条件です。
- 行列内の任意の行ベクトルに対して0,1,2,3がそれぞれ４つずつある（麻雀は４人でやるゲーム）
- 行列内の任意の２つの行ベクトルに対して抜き出して2行16列の行列を作る。行列の各列ベクトルを見ると１６通りの組み合わせがすべて網羅されている
ここからかなり飛躍があるのですが、以下の定理を使うことで簡単に条件に適合する行列を作成することができます。
定理:
$\mathbb{F}_{4}$ からなるベクトルを5つ用意し、どの2つも一次独立であるとする。
これらのベクトルを並べた行列を $G$ とする。
この時
$$
\Gamma = \{ v = G \theta \ | \ \theta \in \mathbb{F}_4^2 \}
$$
は求めたい条件を満たす行列になる。
例として実際に計算してみましょう。
5本のベクトルを並べた行列として以下の行列を用意します。
$$
G = \begin{pmatrix}
1 & 0 \\
0 & 1 \\
1 & 1 \\
1 & \alpha \\
1 & 1 + \alpha \\
\end{pmatrix}
$$
ここに $\mathbb{F}_4^2$ の全通りを並べた行列 $\theta$ をかけます。
$$
\begin{pmatrix}
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & \alpha & \alpha & \alpha & \alpha & 1 + \alpha & 1 + \alpha & 1 + \alpha & 1 + \alpha \\
0 & 1 & \alpha & 1 + \alpha & 0 & 1 & \alpha & 1 + \alpha & 0 & 1 & \alpha & 1 + \alpha & 0 & 1 & \alpha & 1 + \alpha \\
\end{pmatrix}
$$
$G, \theta$ はそれぞれ5行2列と2行16列の行列なので積を計算すると 5行16列の行列になり題意に沿っています。
実験計画法的な言葉で捉えるとここで生成された行列は 因子=5, 大きさ = 16, 水準=4, 強さ=2の直交計画を作成したことになります。
因子や大きさや水準はなんとなく行列のサイズとか成分であることが分かると思いますが、強さ2というのが謎ですね。
実は強さというのは先に挙げた以下の条件を指します（本などに書いてある定義とは違うけれども今回は同値）
- 行列内の任意の２つの行ベクトルに対して抜き出して2行16列の行列を作る。行列の各列ベクトルを見ると１６通りの組み合わせがすべて網羅されている
行列$G$を作る際にどの2つも一次独立という仮定を設けましたが、実はこの強さ2というのはここから来ているわけですね。
なお、今回は行列を計算するにあたってgaloisというライブラリを使用しました。
https://pypi.org/project/galois/
numpyと同様に計算ができるのでめっちゃ便利でした。
最後に宣伝
Supershipではプロダクト開発やサービス開発に関わる人を絶賛募集しております。
ご興味がある方は以下リンクよりご確認ください。
Supershipグループ 採用サイト
是非ともよろしくお願いします。
参考文献
組合せ理論とその応用, 高橋磐郎, 岩波全書
https://www.ne.jp/asahi/music/marinkyo/matematiko/kombinajxteorio.html.ja
https://peng225.hatenablog.com/entry/2021/04/20/135228