漸く森博嗣「笑わない数学者」のビリヤードの問題／魔円陣を解いたものの要領を良くする(2)

の続き...

7. 次は拡大体を元にする場合。

　$p$ を素数とし, $n$ を $1$ より大きい整数として, $GF(p^n)$ を考える。その3次拡大体 ${GF(p^n)}^3$ から有限射影平面を構成し, その巡回平面から魔円陣を拵えたい。
　例えば, $p=3,\ n=2$ の場合で確認してみよう。先ずは, $GF(3^2)$ を考える必要がある。色々な手段があるが, 2次の既約多項式を用いて拡大する事にしよう。
　既約多項式は$x^2+x+2$で良いだろうか。

\begin{align}
x=0\ とすれば, \ &x^2+x+2=0+0+2=2\ne 0\\
x=1\ とすれば, \ &x^2+x+2=1+1+2=4\equiv 1\ne 0\\
x=2\ とすれば, \ &x^2+x+2=4+2+2=8\equiv 2\ne 0\\
\end{align}

だから, 既約多項式にはなっていそうだ。この $x^2+x+2=0$ の解を $\alpha$ とすれば, $\alpha^2=-\alpha-2\equiv 2\alpha+1$ だからこの事に注意して, $\alpha^i$を確かめてみよう。

\begin{align}
\alpha^0&=1\\
\alpha^1&=\alpha\\
\alpha^2&\equiv 2\alpha+1\\
\alpha^3&=2\alpha^2+\alpha=4\alpha+2+\alpha\equiv 2\alpha+2\\
\alpha^4&=2\alpha^2+2\alpha=4\alpha+2+2\alpha=2\\
\alpha^5&=2\alpha\\
\alpha^6&=2\alpha^2=4\alpha+2\equiv \alpha+2\\
\alpha^7&=\alpha^2+2\alpha=2\alpha+1+2\alpha\equiv \alpha+1\\
\alpha^8&=\alpha^2+\alpha=2\alpha+1+\alpha \equiv 1\\
\end{align}

$8$つの元しかなくて, $3^2$なら$9$個だろうと思うたりするだろうけど, 当然ここに $0$ が加わるので, 有限体 $GF(3^2)$ の構成元は,

\begin{align}
GF(3^2)&=\{0,\ 1,\ \alpha,\ \alpha^2,\ \alpha^3,\ \alpha^4,\ \alpha^5,\ \alpha^6,\ \alpha^7,\ \alpha^8\}\\
&=\{0,\ 1,\ \alpha,\ 2\alpha+1,\ 2\alpha+2,\ 2,\ 2\alpha,\ \alpha+2,\ \alpha+1\}
\end{align}

の $9$ つで上手く出来上がったという事になる。
　今回はこれを更に3次拡大するわけだ。新しく, 別の3次の既約多項式が要る。係数は $GF(3^2)$ の元になるので, $x^3+x+\alpha$ のようなものが簡単な例としては想定される。
　順に確認するが, この程度でも手作業だと大概だ。

\begin{align}
x=0\ とすれば, \ &x^3+x+\alpha=\alpha\ne 0\\
x=1\ とすれば, \ &x^3+x+\alpha=1+1+\alpha=\alpha+2\ne 0\\
x=\alpha\ とすれば, \ &x^3+x+\alpha=\alpha^3+\alpha+\alpha=\alpha(2\alpha+1)+\alpha\\
&=2\alpha^2+\alpha+\alpha=4\alpha+2+2\alpha\equiv 2\ne 0\\
x=2\alpha+1\ とすれば, \ &x^3+x+\alpha=(2\alpha+1)^3+2\alpha+1+\alpha\\
&=8\alpha^3+12\alpha^2+6\alpha+1+3\alpha+1\\
&\equiv 2\alpha^3+2\equiv 2\alpha(2\alpha+1)+2\\
&=4\alpha^2+2\alpha+2\equiv \alpha^2+2\alpha+2\\
&=2\alpha+1+2\alpha+2\equiv \alpha\ne 0\\
x=2\alpha+2\ とすれば, \ &x^3+x+\alpha=(2\alpha+2)^3+2\alpha+2+\alpha\\
&=8\alpha^3+24\alpha^2+24\alpha+8+3\alpha+2\\
&\equiv 2\alpha^3+1\equiv 2\alpha(2\alpha+1)+1\\
&=4\alpha^2+2\alpha+1\equiv \alpha^2+2\alpha+1\\
&=2\alpha+1+2\alpha+1\equiv \alpha+2\ne 0\\
x=2\ とすれば, \ &x^3+x+\alpha=8+2+\alpha=\alpha+1\ne 0\\
x=2\alpha\ とすれば, \ &x^3+x+\alpha=8\alpha^3+2\alpha+\alpha\equiv 2\alpha^3\\
&=2\alpha(2\alpha+1)=4\alpha^2+2\alpha\equiv \alpha^2+2\alpha\\
&=2\alpha+1+1=2\alpha+2\ne 0\\
x=\alpha+2\ とすれば, \ &x^3+x+\alpha=(\alpha+2)^3+\alpha+2+\alpha\\
&=\alpha^3+6\alpha^2+12\alpha+8+2\alpha+2\\
&\equiv\alpha^3+2\alpha+1=\alpha(2\alpha+1)+2\alpha+1\\
&=2\alpha^2+3\alpha+1\equiv4\alpha+2+1\equiv\alpha\ne 0\\
x=\alpha+1\ とすれば, \ &x^3+x+\alpha=(\alpha+1)^3+\alpha+1+\alpha\\
&=\alpha^3+3\alpha^2+3\alpha+1+2\alpha+1\\
&\equiv\alpha^3+2\alpha+2=\alpha(2\alpha+1)+2\alpha+2\\
&=2\alpha^2+3\alpha+2\equiv4\alpha+2+2\equiv\alpha+1\ne 0
\end{align}

となり, 既約多項式の条件は満たしていそうだ。
　そうなると, $x^3+x+\alpha=0$ の解を $\omega$ として, $\omega$ の累乗で3次拡大体な${GF(3^2)}^3$ の構成元を確認することとなる。$\omega^3+\omega+\alpha=0$ だから, $\omega^3=-\omega-\alpha=2\omega+2\alpha$ となる。

\begin{align}
\omega^0&=1\\
\omega^1&=\omega\\
\omega^2&=\omega^2\\
\omega^3&=2\omega+2\alpha\\
\omega^4&=2\omega^2+2\omega\alpha\\
\omega^5&=2\omega^3+2\omega^2\alpha=2\omega^2\alpha+4\omega+4\alpha\\
&\equiv 2\omega^2\alpha+\omega+\alpha\\\
\omega^6&=2\omega^3\alpha+\omega^2+\omega\alpha=(4\omega+4\alpha)\alpha+\omega^2+\omega\alpha\\
&\equiv \omega^2+2\omega\alpha+\alpha^2=\omega^2+2\omega\alpha+2\alpha+1 \\
\omega^7&=\omega^3+2\omega^2\alpha+2\omega\alpha+\omega=2\omega+2\alpha+2\omega^2\alpha+2\omega\alpha+\omega\\
&\equiv 2\omega^2\alpha+2\omega\alpha+2\alpha\\
\omega^8&=2\omega^3\alpha+2\omega^2\alpha+2\omega\alpha=(\omega+\alpha)\alpha+2\omega^2\alpha+2\omega\alpha\\
&\equiv 2\omega^2\alpha+\alpha^2=2\omega^2\alpha+2\alpha+1\\
&\vdots
\end{align}

まぁこのまま計算を続けても良いのだけど... この煩雑な計算を, 漸化式で計算できないかというのが, 今回の計算の要領を良くする肝心な部分だから, そちらの方向で考えてみよう。
　${GF(3^2)}^3$ の構成元は $\alpha$の高々1次のものと, $\omega$の高々2次の組み合わせで得られる。具体的に書けば,

\begin{align} 
\omega^i=a_i\omega^2\alpha+b_i\omega^2+c_i\omega\alpha+d_i\omega+e_i\alpha+f_i
\end{align}

という式であり, この式の係数である$(a_i,b_i,c_i,d_i,e_i,f_i)$が計算できれば良い事になる。
当然, 比較することで漸化式が得られる。

\begin{align} 
\omega^{i+1}&=a_{i+1}\omega^2\alpha+b_{i+1}\omega^2+c_{i+1}\omega\alpha+d_{i+1}\omega+e_{i+1}\alpha+f_{i+1}\\
&=a_i\omega^3\alpha+b_i\omega^3+c_i\omega^2\alpha+d_i\omega^2+e_i\omega\alpha+f_i\omega\\
&=a_i(2\omega+2\alpha)\alpha+b_i(2\omega+2\alpha)+c_i\omega^2\alpha+d_i\omega^2+e_i\omega\alpha+f_i\omega\\
&=c_i\omega^2\alpha+d_i\omega^2+e_i\omega\alpha+f_i\omega+2a_i\omega\alpha+2a_i\alpha^2+2b_i\omega+2b_i\alpha\\
&=c_i\omega^2\alpha+d_i\omega^2+(2a_i+e_i)\omega\alpha+(2b_i+f_i)\omega+2a_i(2\alpha+1)+2b_i\alpha\\
&=c_i\omega^2\alpha+d_i\omega^2+(2a_i+e_i)\omega\alpha+(2b_i+f_i)\omega+(a_i+2b_i)\alpha+2a_i
\end{align}

つまり,

\begin{align}
a_{i+1}&=c_i\\
b_{i+1}&=d_i\\
c_{i+1}&=2a_i+e_i\\
d_{i+1}&=2b_i+f_i\\
e_{i+1}&=a_i+2b_i\\
f_{i+1}&=2a_i
\end{align}

となっていることが分かるわけだ。$\omega^0=1$ は配列だと $(0,0,0,0,0,1)$だから,

\begin{align}
(0,0,0,0,0,1)\\
(0,0,0,1,0,0)\\
(0,1,0,0,0,0)\\
(0,0,0,2,2,0)\\
(0,2,2,0,0,0)\\
(2,0,0,1,1,0)\\
(0,1,2,0,2,1)\\
(2,0,2,0,2,0)\\
(2,0,0,0,2,1)\\
\end{align}

上手く計算できている。問題は一般化か。

8. 一般化してみよう

　$GF(p^n)$を構成する。これには, 既約多項式な $x^n+A_1x^{n-1}+\cdots+A_{n}$ が要る。$A_1,\cdots,A_n$ は $GF(p)$ の元である。ただし, $A_n\ne 0$ だし, $A_1,\cdots,A_{n-1}$ の全てが $0$ であることはない。その上で, 既約多項式となるかどうかは $0,1,\cdots,p-1$ を代入して $0$ にならない事で確認できそうだ。
　その上で, $x^n+A_1x^{n-1}+\cdots+A_{n}=0$ の解 $\alpha$ の累乗が有限体 $GF(p^n)$ の元を構成できることが確認できれば, つまり, $i=1,\cdots, p^n-1$ で $1$ になる事がなく, $\alpha^{p^n}=1$ となれば, 構成できているというわけだ。
　ここで更に, $x^3+B_1x^2+B_2x+B_3$という3次の既約多項式を想定する。この$B_1,B_2,B_3$は$GF(p^n)$の元である。同じように $B_3\ne 0$ , $B_1=0$ かつ $B_2=0$ の場合は除く。その上で, $GF(p^n)$ の全ての元 $e$ に対して, 代入しても $0$ にならなければ, 既約多項式である。
　その上で, $x^3+B_1x^2+B_2x+B_3=0$ の解を $\omega$ としたときに, $\omega$ の累乗が有限体 $GF(p^n)$ の3次拡大である ${GF(p^n)}^3$ を構成することが確認できれば良い。
　このとき, 例えば $\omega^2$ の係数が $0$ となるものを集めると, それは巡回平面の一つとなっており, その指数を確認すれば, (巡回)完全差集合が得られ, 魔円陣が構成できるという段取りだ。
　構成手順から, ${GF(p^n)}^3$ の元である $\omega^i$ は,

\begin{align}
\omega^i=(a_i^1\alpha^{n-1}+\cdots+a_i^{n})\omega^2+(b_i^1\alpha^{n-1}+\cdots+b_i^{n})\omega+(c_i^1\alpha^{n-1}+\cdots+c_i^{n})
\end{align}

とおけて, $\omega^3=-B_1\omega^2-B_2\omega-B_3$ であり, $B_1,B_2,B_3$は$GF(p^n)$の元であるから, $B_k^l$ を$GF(p)$の元とすれば,

\begin{align}
B_1&=B_1^1\alpha^{n-1}+\cdots+B_n^{1}\\
B_2&=B_1^2\alpha^{n-1}+\cdots+B_n^{2}\\
B_3&=B_1^3\alpha^{n-1}+\cdots+B_n^{3}
\end{align}

とおけて,

\begin{align}
\omega^3=&-(B_1^1\alpha^{n-1}+\cdots+B_n^{1})\omega^2
-(B_1^2\alpha^{n-1}+\cdots+B_n^{2})\omega\\
&-(B_1^3\alpha^{n-1}+\cdots+B_n^{3})
\end{align}

となることに注意すれば,

\begin{align}
\omega^{i+1}=&(a_{i+1}^1\alpha^{n-1}+\cdots+a_{i+1}^{n})\omega^2+(b_{i+1}^1\alpha^{n-1}+\cdots+b_{i+1}^{n})\omega\\&+(c_{i+1}^1\alpha^{n-1}
+\cdots+c_{i+1}^{n})\\
=&(a_i^1\alpha^{n-1}+\cdots+a_i^{n})\omega^3+(b_i^1\alpha^{n-1}+\cdots+b_i^{n})\omega^2+(c_i^1\alpha^{n-1}+\cdots+c_i^{n})\omega\\
=
&-(a_i^1\alpha^{n-1}+\cdots+a_i^{n})(B_1^1\alpha^{n-1}+\cdots+B_n^{1})\omega^2\\
&-(a_i^1\alpha^{n-1}+\cdots+a_i^{n})(B_1^2\alpha^{n-1}+\cdots+B_n^{2})\omega\\
&-(a_i^1\alpha^{n-1}+\cdots+a_i^{n})(B_1^3\alpha^{n-1}+\cdots+B_n^{3})\\
&+(b_i^1\alpha^{n-1}+\cdots+b_i^{n})\omega^2\\
&+(c_i^1\alpha^{n-1}+\cdots+c_i^{n})\omega\\
=&\{(b_i^1\alpha^{n-1}+\cdots+b_i^{n})-(a_i^1\alpha^{n-1}+\cdots+a_i^{n})(B_1^1\alpha^{n-1}+\cdots+B_n^{1})\}\omega^2\\
&+\{(c_i^1\alpha^{n-1}+\cdots+c_i^{n})-(a_i^1\alpha^{n-1}+\cdots+a_i^{n})(B_1^2\alpha^{n-1}+\cdots+B_n^{2})\}\omega\\
&-(a_i^1\alpha^{n-1}+\cdots+a_i^{n})(B_1^3\alpha^{n-1}+\cdots+B_n^{3})
\end{align}

となり, とても面倒そうだ。
　これでは, 今のところ手に負えそうになりので, 最終的には$\omega^2$の係数が$0$になるものを選べれば良いというわけだから, $\alpha$の部分の計算は Nemo に任せる事にすれば見通しは良くなるのかも。

9. Nemo を使って $\alpha$ の部分を計算することにすると...

\begin{align}
a_{i+1}&=-Aa_i+b_i\\
b_{i+1}&=-Ba_i+c_i\\
c_{i+1}&=-Ca_i
\end{align}

のところは同じだから, 直ぐにでも組めるのだろうか。折角だから行列で書いておこう。

\begin{align}
\begin{pmatrix}a_{i+1}\\b_{i+1}\\c_{i+1}\end{pmatrix}=
\begin{pmatrix}-A & 1 & 0\\-B & 0 & 1\\-C & 0 & 0\end{pmatrix}
\begin{pmatrix}a_{i}\\b_{i}\\c_{i}\end{pmatrix}\\
\end{align}

こうしておけば,

\begin{align}
P=\begin{pmatrix}-A & 1 & 0\\-B & 0 & 1\\-C & 0 & 0\end{pmatrix}
\end{align}

とおけば, $P^i$ で $\omega^i$ を計算(というよりは表現)できるから見易いかも。この場合は, $x^3+B_1x^2+B_2x+B_3$ としているので, $A=B_1,B=B_2,C=B_3$と読み替える必要がある。

10. では中途半端だけどこれでプログラムしてみよう

やってみた。

試してみたのは ${GF(2^{10})}^3$ による玉の数が $1025$ で, 玉の数の合計が $1049601$ , という魔円陣。計算とチェックに掛かった時間は $7.973$秒という事でした。早い。