1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

Last updated at Posted at 2024-08-18

漸く森博嗣「笑わない数学者」のビリヤードの問題/魔円陣を解いたものの要領を良くする(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$秒という事でした。早い。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?