今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(7)～解法の謎に迫る

# 0. はじめに

これまで一般化したビリヤード問題を解くため，海外を含めていろいろなサイトを見て学んだ。理屈も分からずに見よう見まねでコーディングしたところ，とりあえず問題が解けたのだが，やはり納得できない。

ということで今回はトリボナッチ数列による解法の謎について，なぜ解けるのか？どんな意味があるのか？考察していこうと思う。

:::note
本シリーズでは一貫してトリボナッチ数列という言葉を使っているが，おそらく正しくは「三次線形再帰（剰余）数列」とでも呼ぶべきものであろう。ところが，シリーズ初期に誤って用いてしまい，プログラムのコメント等にもそのまま使用しているため（あくまで自分の）混乱を防ぐためにもそのまま用いることにした。ご了承頂きたい。
:::

https://qiita.com/TETSURO1999/items/eefbec683a26cc221a57?1

# 1. トリボナッチ数列による解法のおさらい

初項 $t_0 = 0$，$t_1 = 0$，$t_2 = 1$ として，一般項 $t_i$（$i \ge 3$）を

```math
t_i = \left( A \cdot t_{i - 3} + B \cdot t_{i - 2} + C \cdot t_{i - 1} \right) \bmod p
```

と定義する。

ボールの個数 $n = 4$ のとき，すなわち $p = n - 1 = 3$ のときのトリボナッチ数列を計算してみる。係数 $A,B,C$ は $\lbrace 0, 1, 2 \rbrace$ のいずれかの値を取るので $3^3 = 27$ 通りの数列が存在する。このうち周期１３となるケースが４通り，周期２６となるケースが４通りある。

<table>
<caption>表１　$p = 3$ のときのトリボナッチ数列</caption>
<thead>
<tr><th colspan=3 style="text-align:center">係数</th>
    <th colspan=3 style="text-align:center">$t_i$</th>
    <th rowspan=2 style="text-align:center">周期</th></tr>
<tr><th style="text-align:center">$A$</th>
    <th style="text-align:center">$B$</th>
    <th style="text-align:center">$C$</th>
    <th style="text-align:center">$0 \le i < 13$</th>
    <th style="text-align:center">$13 \le i < 26$</th>
    <th style="text-align:center">$26 \le i$</th></tr>
</thead>
<tbody>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0,0,1,0,0,0,0,0,0,0,0,0,0</td>
    <td style="text-align:center">0,0,0,0,0,0,0,0,0,0,0,0,0</td>
    <td style="text-align:center">0,0,0</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0,0,1,1,1,1,1,1,1,1,1,1,1</td>
    <td style="text-align:center">1,1,1,1,1,1,1,1,1,1,1,1,1</td>
    <td style="text-align:center">1,1,1</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0,0,1,2,1,2,1,2,1,2,1,2,1</td>
    <td style="text-align:center">2,1,2,1,2,1,2,1,2,1,2,1,2</td>
    <td style="text-align:center">1,2,1</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0,0,1,0,1,0,1,0,1,0,1,0,1</td>
    <td style="text-align:center">0,1,0,1,0,1,0,1,0,1,0,1,0</td>
    <td style="text-align:center">1,0,1</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0,0,1,1,2,0,2,2,1,0,1,1,2</td>
    <td style="text-align:center">0,2,2,1,0,1,1,2,0,2,2,1,0</td>
    <td style="text-align:center">1,1,2</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0,0,1,2,2,0,2,1,1,0,1,2,2</td>
    <td style="text-align:center">0,2,1,1,0,1,2,2,0,2,1,1,0</td>
    <td style="text-align:center">1,2,2</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0,0,1,0,2,0,1,0,2,0,1,0,2</td>
    <td style="text-align:center">0,1,0,2,0,1,0,2,0,1,0,2,0</td>
    <td style="text-align:center">1,0,2</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0,0,1,1,0,2,2,0,1,1,0,2,2</td>
    <td style="text-align:center">0,1,1,0,2,2,0,1,1,0,2,2,0</td>
    <td style="text-align:center">1,1,0</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0,0,1,2,0,1,2,0,1,2,0,1,2</td>
    <td style="text-align:center">0,1,2,0,1,2,0,1,2,0,1,2,0</td>
    <td style="text-align:center">1,2,0</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0,0,1,0,0,1,0,0,1,0,0,1,0</td>
    <td style="text-align:center">0,1,0,0,1,0,0,1,0,0,1,0,0</td>
    <td style="text-align:center">1,0,0</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0,0,1,1,1,2,0,1,0,0,1,1,1</td>
    <td style="text-align:center">2,0,1,0,0,1,1,1,2,0,1,0,0</td>
    <td style="text-align:center">1,1,1</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0,0,1,2,1,0,2,2,1,1,1,0,1</td>
    <td style="text-align:center">0,0,1,2,1,0,2,2,1,1,1,0,1</td>
    <td style="text-align:center">0,0,1</td>
    <td style="text-align:center">13</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0,0,1,0,1,1,1,2,2,0,1,2,1</td>
    <td style="text-align:center">0,0,1,0,1,1,1,2,2,0,1,2,1</td>
    <td style="text-align:center">0,0,1</td>
    <td style="text-align:center">13</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0,0,1,1,2,1,1,1,0,2,0,2,1</td>
    <td style="text-align:center">0,0,1,1,2,1,1,1,0,2,0,2,1</td>
    <td style="text-align:center">0,0,1</td>
    <td style="text-align:center">13</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0,0,1,2,2,1,0,0,1,2,2,1,0</td>
    <td style="text-align:center">0,1,2,2,1,0,0,1,2,2,1,0,0</td>
    <td style="text-align:center">1,2,2</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0,0,1,0,2,1,1,1,0,0,1,0,2</td>
    <td style="text-align:center">1,1,1,0,0,1,0,2,1,1,1,0,0</td>
    <td style="text-align:center">1,0,2</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0,0,1,1,0,0,1,1,0,0,1,1,0</td>
    <td style="text-align:center">0,1,1,0,0,1,1,0,0,1,1,0,0</td>
    <td style="text-align:center">1,1,0</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0,0,1,2,0,2,0,1,1,1,2,1,1</td>
    <td style="text-align:center">0,0,1,2,0,2,0,1,1,1,2,1,1</td>
    <td style="text-align:center">0,0,1</td>
    <td style="text-align:center">13</td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0,0,1,0,0,2,0,0,1,0,0,2,0</td>
    <td style="text-align:center">0,1,0,0,2,0,0,1,0,0,2,0,0</td>
    <td style="text-align:center">1,0,0</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0,0,1,1,1,0,2,1,1,2,1,0,1</td>
    <td style="text-align:center">0,0,2,2,2,0,1,2,2,1,2,0,2</td>
    <td style="text-align:center">0,0,1</td>
    <td style="text-align:center">26</td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0,0,1,2,1,1,0,2,0,0,1,2,1</td>
    <td style="text-align:center">1,0,2,0,0,1,2,1,1,0,2,0,0</td>
    <td style="text-align:center">1,2,1</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0,0,1,0,1,2,1,1,2,0,1,1,1</td>
    <td style="text-align:center">0,0,2,0,2,1,2,2,1,0,2,2,2</td>
    <td style="text-align:center">0,0,1</td>
    <td style="text-align:center">26</td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0,0,1,1,2,2,0,0,1,1,2,2,0</td>
    <td style="text-align:center">0,1,1,2,2,0,0,1,1,2,2,0,0</td>
    <td style="text-align:center">1,1,2</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0,0,1,2,2,2,1,2,0,1,0,1,1</td>
    <td style="text-align:center">0,0,2,1,1,1,2,1,0,2,0,2,2</td>
    <td style="text-align:center">0,0,1</td>
    <td style="text-align:center">26</td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0,0,1,0,2,2,1,2,0,0,1,0,2</td>
    <td style="text-align:center">2,1,2,0,0,1,0,2,2,1,2,0,0</td>
    <td style="text-align:center">1,0,2</td>
    <td style="text-align:center">×</td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0,0,1,1,0,1,0,2,1,2,2,2,1</td>
    <td style="text-align:center">0,0,2,2,0,2,0,1,2,1,1,1,2</td>
    <td style="text-align:center">0,0,1</td>
    <td style="text-align:center">26</td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0,0,1,2,0,0,1,2,0,0,1,2,0</td>
    <td style="text-align:center">0,1,2,0,0,1,2,0,0,1,2,0,0</td>
    <td style="text-align:center">1,2,0</td>
    <td style="text-align:center">×</td></tr>
</tbody>
</table>

周期１３または周期２６となる場合に着目する。$t_i = 0$ となる位置を読み取り，それらの位置の間隔（差分）を求めるとビリヤード問題の解となる。以下，実際に確認してみる。

- $(A,B,C)=(1,0,2)$ の場合，$t_i = 0$ となる位置を読み取ると $\lbrace 0, 1, 5, 11, 13\rbrace$ となり，それらの差分を求めると $\lbrace 1, 4, 6, 2 \rbrace$ となる。
- $(A,B,C)=(1,1,0)$ の場合，$t_i = 0$ となる位置を読み取ると $\lbrace 0, 1, 3, 9, 13\rbrace$ となり，それらの差分を求めると $\lbrace 1, 2, 6, 4 \rbrace$ となる。
- $(A,B,C)=(1,1,1)$ の場合，$t_i = 0$ となる位置を読み取ると $\lbrace 0, 1, 8, 10, 13\rbrace$ となり，それらの差分を求めると $\lbrace 1, 7, 2, 3 \rbrace$ となる。
- $(A,B,C)=(1,2,2)$ の場合，$t_i = 0$ となる位置を読み取ると $\lbrace 0, 1, 4, 6, 13\rbrace$ となり，それらの差分を求めると $\lbrace 1, 3, 2, 7 \rbrace$ となる。
- $(A,B,C)=(2,0,1)$ の場合，$t_i = 0$ となる位置を読み取ると $\lbrace 0, 1, 5, 11, 13\rbrace$ となり，それらの差分を求めると $\lbrace 1, 4, 6, 2 \rbrace$ となる。
- $(A,B,C)=(2,1,0)$ の場合，$t_i = 0$ となる位置を読み取ると $\lbrace 0, 1, 3, 9, 13\rbrace$ となり，それらの差分を求めると $\lbrace 1, 2, 6, 4 \rbrace$ となる。
- $(A,B,C)=(2,1,2)$ の場合，$t_i = 0$ となる位置を読み取ると $\lbrace 0, 1, 8, 10, 13\rbrace$ となり，それらの差分を求めると $\lbrace 1, 7, 2, 3 \rbrace$ となる。
- $(A,B,C)=(2,2,1)$ の場合，$t_i = 0$ となる位置を読み取ると $\lbrace 0, 1, 4, 6, 13\rbrace$ となり，それらの差分を求めると $\lbrace 1, 3, 2, 7 \rbrace$ となる。

以上より，ボールの個数 $n = 4$ のときのビリヤード問題の解 $\lbrace 1, 2, 6, 4 \rbrace$ および $\lbrace 1, 3, 2, 7 \rbrace$ を得ることができた。左右対称解も得られている。

# 2. 有限体の射影平面による解法

有限体の射影平面における巡回平面が魔円陣，すなわちビリヤード問題の解と一対一に対応すること，そしてその証明は参考文献を参照されたい。ここではその解法のみを自分の理解したレベルで説明する。

## 2.1 解法概略

同様にボールの個数 $n = 4$ の場合を考える。$n - 1 = p = 3$ と素数であることが前提である。

素数 $p = 3$ より小さい非負の整数の集合 $\lbrace 0, 1, 2 \rbrace$ は，互いを加減乗算した後に素数 $p = 3$ で割った余りとして演算を定義すれば演算後の値は必ず集合の中のいずれかの値になる。このような性質のものを有限体 $\mathbb{F}_3$ と呼ぶ。

まず，有限体 $\mathbb{F}_3$ 上の三次の多項式 $x^3 + a \cdot x^2 + b \cdot x + c$ を考える。係数 $a,b,c$ は $\lbrace 0, 1, 2 \rbrace$ のいずれかである。三次多項式が既約多項式になる（これ以上因数分解されない）よう係数 $a,b,c$ を上手く選び，三次多項式がゼロとなる三次方程式 $x^3 + a \cdot x^2 + b \cdot x + c = 0$ の解を $\alpha$ とおくと，$\alpha^{13} = \lbrace 1, 2 \rbrace $ となる性質を持つ。ここで $p(p + 1) = 13$ という意味であり，ビリヤード問題におけるボールの数値の総和 $\sigma = n(n - 1) + 1 = 13$ に等しい。

次に $\alpha^0, \alpha^1, \alpha^2, \alpha^3, \cdots, \alpha^{13} $ を計算していく。$\alpha^3 + a \cdot \alpha^2 + b \cdot \alpha + c = 0$ であるから，$\alpha$ の三次以上の項は次数下げができ，$\alpha^i$ はせいぜい $\alpha$ の二次式以下で表される。ここで $\alpha^2$ を含まない $\alpha^i$ の位置（指数）を読み出し，それらの位置の間隔を求めるとビリヤード問題の解（魔円陣）が得られるという・・・ホンマか？

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
caption {
  fontSize 16
}
</style>
sprite FIGURE <svg width="500" height="500" viewbox="0 0 500 500">
<circle cx="250" cy="250" r="200" fill="none" stroke="2" />
<circle cx="250" cy="50" r="4" fill="black" />
<circle cx="157.1" cy="72.9"  r="4" fill="black" />
<circle cx="342.9" cy="72.9"  r="4" fill="black" />
<circle cx="85.4"　cy="136.4" r="4" fill="black" />
<circle cx="414.6" cy="136.4" r="4" fill="black" />
<circle cx="51.5"  cy="225.9" r="4" fill="black" />
<circle cx="448.5" cy="225.9" r="4" fill="black" />
<circle cx="63.0"  cy="320.9" r="4" fill="black" />
<circle cx="437.0" cy="320.9" r="4" fill="black" />
<circle cx="117.4" cy="399.7" r="4" fill="black" />
<circle cx="382.6" cy="399.7" r="4" fill="black" />
<circle cx="202.1" cy="444.2" r="4" fill="black" />
<circle cx="297.9" cy="444.2" r="4" fill="black" />
<text x="245"   y="40"    fill="black" font-size="16">α⁰</text>
<text x="147.1" y="62.9"  fill="black" font-size="16">α¹</text>
<text x="342.9" y="62.9"  fill="black" font-size="16">α¹²</text>
<text x="70.4"  y="131.4" fill="black" font-size="16">α²</text>
<text x="419.6" y="131.4" fill="black" font-size="16">α¹¹</text>
<text x="26.5"  y="229.9" fill="black" font-size="16">α³</text>
<text x="458.5" y="229.9" fill="black" font-size="16">α¹⁰</text>
<text x="38.0"  y="325.9" fill="black" font-size="16">α⁴</text>
<text x="447.0" y="325.9" fill="black" font-size="16">α⁹</text>
<text x="92.4"  y="409.7" fill="black" font-size="16">α⁵</text>
<text x="390.1" y="409.7" fill="black" font-size="16">α⁸</text>
<text x="192.1" y="464.2" fill="black" font-size="16">α⁶</text>
<text x="295.4" y="464.2" fill="black" font-size="16">α⁷</text>
</svg>
title <$FIGURE>
caption 図１　有限体の射影平面
@enduml
```

## 2.2 既約多項式

有限体 $\mathbb{F}_3$ 上における三次の多項式は係数 $a,b,c$ が $\lbrace 0, 1, 2 \rbrace$ のいずれかであるから
$3^3 = 27$ 個存在する。このうち既約多項式となるものは８個あり，周期１３のものが４個，周期２６のものが４個存在する。

<table>
<caption>表２　有限体 $F_3$ における三次多項式一覧</caption>
<thead>
<tr><th style="text-align:center">$a$</th>
    <th style="text-align:center">$b$</th>
    <th style="text-align:center">$c$</th>
    <th style="text-align:center">多項式</th>
    <th style="text-align:center">既約</th>
    <th style="text-align:center">周期</th></tr>
</thead>
<tbody>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td>$x^3$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td>$x^3 + 1 = (x + 1)^3$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td>$x^3 + 2 = (x + 2)^3$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td>$x^3 + x = x(x^2 + 1)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td>$x^3 + x + 1 = (x + 2)(x^2 + x + 2)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td>$x^3 + x + 2 = (x + 1)(x^2 + 2x + 2)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td>$x^3 + 2x = x(x^2 + 2)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td>$x^3 + 2x + 1$</td>
    <td style="text-align:center">○</td>
    <td style="text-align:center">26</td></tr>
<tr><td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td>$x^3 + 2x + 2$</td>
    <td style="text-align:center">○</td>
    <td style="text-align:center">13</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td>$x^3 + x^2 = x^2(x + 1)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td>$x^3 + x^2 + 1 = (x + 2)(x^2 + 2x + 2)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td>$x^3 + x^2 + 2$</td>
    <td style="text-align:center">○</td>
    <td style="text-align:center">13</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td>$x^3 + x^2 + x = x(x + 2)^2$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td>$x^3 + x^2 + x + 1 = (x + 1)(x^2 + 1)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td>$x^3 + x^2 + x + 2$</td>
    <td style="text-align:center">○</td>
    <td style="text-align:center">13</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td>$x^3 + x^2 + 2x = x(x^2 + x + 2)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td>$x^3 + x^2 + 2x + 1$</td>
    <td style="text-align:center">○</td>
    <td style="text-align:center">26</td></tr>
<tr><td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td>$x^3 + x^2 + 2x + 2 = (x + 1)(x^2 + 2) = (x + 2)(x + 1)^2$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td>$x^3 + 2x^2 = x^2(x + 2)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td>$x^3 + 2x^2 + 1$</td>
    <td style="text-align:center">○</td>
    <td style="text-align:center">26</td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td>$x^3 + 2x^2 + 2 = (x + 1)(x^2 + x + 2)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td>$x^3 + 2x^2 + x = x(x + 1)^2$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td>$x^3 + 2x^2 + x + 1$</td>
    <td style="text-align:center">○</td>
    <td style="text-align:center">26</td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td>$x^3 + 2x^2 + x + 2 = (x + 2)(x^2 + 1)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td>$x^3 + 2x^2 + 2x = x(x^2 + 2x + 2)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td>$x^3 + 2x^2 + 2x + 1 = (x + 1)(x + 2)^2 = (x + 2)(x^2 + 2)$</td>
    <td style="text-align:center">×</td>
    <td></td></tr>
<tr><td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td>$x^3 + 2x^2 + 2x + 2$</td>
    <td style="text-align:center">○</td>
    <td style="text-align:center">13</td></tr>
<tr><td colspan=6></td></tr>
</tbody>
</table>

なお，既約多項式の確認方法はひたすら面倒である。下記のように一次式と二次式の積より可約多項式を列挙して，これらに該当しないものが既約多項式である。※定数項を持たないなど明らかに可約なものを除く

<table>
<caption>表３　可約多項式の列挙</caption>
<thead>
<tr><th>
    <th style="text-align:center">$x + 1$</th>
    <th style="text-align:center">$x + 2$</th></tr>
</thead>
<tbody>
<tr><td style="text-align:center">$x^2 + 1$</td>
    <td>$(x + 1)(x^2 + 1)$<br>$= x^3 + x^2 + x + 1$</td>
    <td>$(x + 2)(x^2 + 1)$<br>$= x^3 + 2x^2 + x + 2$</td></tr>
<tr><td style="text-align:center">$x^2 + 2$</td>
    <td>$(x + 1)(x^2 + 2)$<br>$= x^3 + x^2 + 2x + 2$</td>
    <td>$(x + 2)(x^2 + 2)$<br>$= x^3 + 2x^2 + 2x + 1$</td></tr>
<tr><td style="text-align:center">$x^2 + x + 1$</td>
    <td>$(x + 1)(x^2 + x + 1)$<br>$= x^3 + 2x^2 + 2x + 1$</td>
    <td>$(x + 2)(x^2 + x + 1)$<br>$= x^3 + 2$</td></tr>
<tr><td style="text-align:center">$x^2 + x + 2$</td>
    <td>$(x + 1)(x^2 + x + 2)$<br>$= x^3 + 2x^2 + 2$</td>
    <td>$(x + 2)(x^2 + x + 2)$<br>$= x^3 + x + 1$</td></tr>
<tr><td style="text-align:center">$x^2 + 2x + 1$</td>
    <td>$(x + 1)(x^2 + 2x + 1)$<br>$= x^3 + 1$</td>
    <td>$(x + 2)(x^2 + 2x + 1)$<br>$= x^3 + x^2 + 2x + 2$</td></tr>
<tr><td style="text-align:center">$x^2 + 2x + 2$</td>
    <td>$(x + 1)(x^2 + 2x + 2)$<br>$= x^3 + x + 2$</td>
    <td>$(x + 2)(x^2 + 2x + 2)$<br>$= x^3 + x^2 + 1$</td></tr>
</tbody>
</table>

## 2.3 実際に計算してみる

既約多項式となる８個の場合について，それぞれ実際に計算してみよう。

- $\alpha^3 + 2\alpha + 1 = 0$ すなわち $\alpha^3 = \alpha + 2$ のとき
  ```math
  \begin{aligned}
  \alpha^0 &= 1 & (*) \\
  \alpha^1 &= \alpha & (*) \\
  \alpha^2 &= \alpha^2 \\
  \alpha^3 &= \alpha + 2 & (*) \\
  \alpha^4 &= \alpha^2 + 2\alpha \\
  \alpha^5 &= 2\alpha^2 + \alpha + 2 \\
  \alpha^6 &= \alpha^2 + \alpha + 1 \\
  \alpha^7 &= \alpha^2 + 2\alpha + 2 \\
  \alpha^8 &= 2\alpha^2 + 2 \\
  \alpha^9 &= \alpha + 1 & (*) \\
  \alpha^{10} &= \alpha^2 + \alpha \\
  \alpha^{11} &= \alpha^2 + \alpha + 2 \\
  \alpha^{12} &= \alpha^2 + 2 \\
  \alpha^{13} &= 2 & (*) \\
  \alpha^{26} &= 1 & (*)
  \end{aligned}
  ```
  $\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 3, 9, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 2, 6, 4 \rbrace$ となる。
- $\alpha^3 + 2\alpha + 2 = 0$ すなわち $\alpha^3 = \alpha + 1$ のとき
  ```math
  \begin{aligned}
  \alpha^0 &= 1 & (*) \\
  \alpha^1 &= \alpha & (*) \\
  \alpha^2 &= \alpha^2 \\
  \alpha^3 &= \alpha + 1 & (*) \\
  \alpha^4 &= \alpha^2 + \alpha \\
  \alpha^5 &= \alpha^2 + \alpha + 1 \\
  \alpha^6 &= \alpha^2 + 2\alpha + 1 \\
  \alpha^7 &= 2\alpha^2 + 2\alpha + 1 \\
  \alpha^8 &= 2\alpha^2 + 2 \\
  \alpha^9 &= \alpha + 2 & (*) \\
  \alpha^{10} &= \alpha^2 + 2\alpha \\
  \alpha^{11} &= 2\alpha^2 + \alpha + 1 \\
  \alpha^{12} &= \alpha^2 + 2\\
  \alpha^{13} &= 1 & (*)
  \end{aligned}
  ```
  $\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 3, 9, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 2, 6, 4 \rbrace$ となる。
- $\alpha^3 + \alpha^2 + 2 = 0$ すなわち $\alpha^3 = 2\alpha^2 + 1$ のとき
  ```math
  \begin{aligned}
  \alpha^0 &= 1 & (*) \\
  \alpha^1 &= \alpha & (*) \\
  \alpha^2 &= \alpha^2 \\
  \alpha^3 &= 2\alpha^2 + 1 \\
  \alpha^4 &= \alpha^2 + \alpha + 2 \\
  \alpha^5 &= 2\alpha + 1 & (*) \\
  \alpha^6 &= 2\alpha^2 + \alpha \\
  \alpha^7 &= 2\alpha^2 + 2 \\
  \alpha^8 &= \alpha^2 + 2\alpha + 2 \\
  \alpha^9 &= \alpha^2 + 2\alpha + 1 \\
  \alpha^{10} &= \alpha^2 + \alpha + 1\\
  \alpha^{11} &= \alpha + 1 & (*) \\
  \alpha^{12} &= \alpha^2 + \alpha \\
  \alpha^{13} &= 1 & (*)
  \end{aligned}
  ```
  $\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 5, 11, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 4, 6, 2 \rbrace$ となる。
- $\alpha^3 + \alpha^2 + \alpha + 2 = 0$ すなわち $\alpha^3 = 2\alpha^2 + 2\alpha + 1$ のとき
  ```math
  \begin{aligned}
  \alpha^0 &= 1 & (*) \\
  \alpha^1 &= \alpha & (*) \\
  \alpha^2 &= \alpha^2 \\
  \alpha^3 &= 2\alpha^2 + 2\alpha + 1 \\
  \alpha^4 &= 2\alpha + 2 & (*) \\
  \alpha^5 &= 2\alpha^2 + 2\alpha \\
  \alpha^6 &= \alpha + 2 & (*) \\
  \alpha^7 &= \alpha^2 + 2\alpha \\
  \alpha^8 &= \alpha^2 + 2\alpha + 1 \\
  \alpha^9 &= \alpha^2 + 1 \\
  \alpha^{10} &= 2\alpha^2 + 1 \\
  \alpha^{11} &= \alpha^2 + 2\alpha + 2 \\
  \alpha^{12} &= \alpha^2 + \alpha + 1 \\
  \alpha^{13} &= 1 & (*)
  \end{aligned}
  ```
  $\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 4, 6, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 3, 2, 7 \rbrace$ となる。
- $\alpha^3 + \alpha^2 + 2\alpha + 1 = 0$ すなわち $\alpha^3 = 2\alpha^2 + \alpha + 2$ のとき
  ```math
  \begin{aligned}
  \alpha^0 &= 1 & (*) \\
  \alpha^1 &= \alpha & (*) \\
  \alpha^2 &= \alpha^2 \\
  \alpha^3 &= 2\alpha^2 + \alpha + 2 \\
  \alpha^4 &= 2\alpha^2 + \alpha + 1 \\
  \alpha^5 &= 2\alpha^2 + 1 \\
  \alpha^6 &= \alpha^2 + 1 \\
  \alpha^7 &= 2\alpha^2 + 2\alpha + 2 \\
  \alpha^8 &= \alpha + 1 & (*) \\
  \alpha^9 &= \alpha^2 + \alpha \\
  \alpha^{10} &= \alpha + 2 & (*) \\
  \alpha^{11} &= \alpha^2 + 2\alpha \\
  \alpha^{12} &= \alpha^2 + \alpha + 2 \\
  \alpha^{13} &= 2 & (*) \\
  \alpha^{26} &= 1 & (*)
  \end{aligned}
  ```
  $\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 8, 10, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 7, 2, 3 \rbrace$ となる。
- $\alpha^3 + 2\alpha^2 + 1 = 0$ すなわち $\alpha^3 = \alpha^2 + 2$ のとき
  ```math
  \begin{aligned}
  \alpha^0 &= 1 & (*) \\
  \alpha^1 &= \alpha & (*) \\
  \alpha^2 &= \alpha^2 \\
  \alpha^3 &= \alpha^2 + 2 \\
  \alpha^4 &= \alpha^2 + 2\alpha + 2 \\
  \alpha^5 &= 2\alpha + 2 & (*) \\
  \alpha^6 &= 2\alpha^2 + 2\alpha \\
  \alpha^7 &= \alpha^2 + 1 \\
  \alpha^8 &= \alpha^2 + \alpha + 2 \\
  \alpha^9 &= 2\alpha^2 + 2\alpha + 2 \\
  \alpha^{10} &= \alpha^2 + 2\alpha + 1 \\
  \alpha^{11} &= \alpha + 2 & (*) \\
  \alpha^{12} &= \alpha^2 + 2\alpha \\
  \alpha^{13} &= 2 & (*) \\
  \alpha^{26} &= 1 & (*)
  \end{aligned}
  ```
  $\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 5, 11, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 4, 6, 2 \rbrace$ となる。
- $\alpha^3 + 2\alpha^2 + \alpha + 1 = 0$ すなわち $\alpha^3 = \alpha^2 + 2\alpha + 2$ のとき
  ```math
  \begin{aligned}
  \alpha^0 &= 1 & (*) \\
  \alpha^1 &= \alpha & (*) \\
  \alpha^2 &= \alpha^2 \\
  \alpha^3 &= \alpha^2 + 2\alpha + 2 \\
  \alpha^4 &= \alpha + 2 & (*) \\
  \alpha^5 &= \alpha^2 + 2\alpha \\
  \alpha^6 &= 2\alpha + 2 & (*) \\
  \alpha^7 &= 2\alpha^2 + 2\alpha \\
  \alpha^8 &= \alpha^2 + \alpha + 1 \\
  \alpha^9 &= 2\alpha^2 + 2 \\
  \alpha^{10} &= 2\alpha^2 + 1 \\
  \alpha^{11} &= 2\alpha^2 + 2\alpha + 1 \\
  \alpha^{12} &= \alpha^2 + 2\alpha + 1\\
  \alpha^{13} &= 2 & (*) \\
  \alpha^{26} &= 1 & (*) \\
  \end{aligned}
  ```
  $\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 4, 6, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 3, 2, 7 \rbrace$ となる。
- $\alpha^3 + 2\alpha^2 + 2\alpha + 2 = 0$ すなわち $\alpha^3 = \alpha^2 + \alpha + 1$ のとき
  ```math
  \begin{aligned}
  \alpha^0 &= 1 & (*) \\
  \alpha^1 &= \alpha & (*) \\
  \alpha^2 &= \alpha^2 \\
  \alpha^3 &= \alpha^2 + \alpha + 1 \\
  \alpha^4 &= 2\alpha^2 + 2\alpha + 1 \\
  \alpha^5 &= \alpha^2 + 2 \\
  \alpha^6 &= \alpha^2 + 1 \\
  \alpha^7 &= \alpha^2 + 2\alpha + 1 \\
  \alpha^8 &= 2\alpha + 1 & (*) \\
  \alpha^9 &= 2\alpha^2 + \alpha \\
  \alpha^{10} &= 2\alpha + 2 \\
  \alpha^{11} &= 2\alpha^2 + 2\alpha \\
  \alpha^{12} &= \alpha^2 + 2\alpha + 2 \\
  \alpha^{13} &= 1 & (*)
  \end{aligned}
  ```
  $\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 8, 10, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 7, 2, 3 \rbrace$ となる。

以上より，ボールの個数 $n = 4$ のときのビリヤード問題の解 $\lbrace 1, 2, 6, 4 \rbrace$ および $\lbrace 1, 3, 2, 7 \rbrace$ を得ることができた。左右対称解も得られている。

## 2.4 トリボナッチ数列との対応

$\alpha^i$ は $\alpha$ の二次式以下になるので各項の係数を $r_i$，$s_i$，$t_i$ とおくと $\alpha^i = r_i + s_i \cdot \alpha + t_i \cdot \alpha^2$ と書ける。

一例として $\alpha^3 + 2\alpha + 1 = 0$ すなわち $\alpha^3 = \alpha + 2$ のときの係数 $r_i$，$s_i$，$t_i$ を示す。

<table>
<caption>表４　$\alpha^3 + 2\alpha + 1 = 0$ のとき</caption>
<thead>
<tr><th>$i$</th>
    <th style="text-align:center">0</th>
    <th style="text-align:center">1</th>
    <th style="text-align:center">2</th>
    <th style="text-align:center">3</th>
    <th style="text-align:center">4</th>
    <th style="text-align:center">5</th>
    <th style="text-align:center">6</th>
    <th style="text-align:center">7</th>
    <th style="text-align:center">8</th>
    <th style="text-align:center">9</th>
    <th style="text-align:center">10</th>
    <th style="text-align:center">11</th>
    <th style="text-align:center">12</th>
    <th style="text-align:center">13</th></tr>
</thead>
<tbody>
<tr><td style="text-align:center">$r_i$</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">2</td></tr>
<tr><td style="text-align:center">$s_i$</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0</td></tr>
<tr><td style="text-align:center">$t_i$</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">2</td>
    <td style="text-align:center">0</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">1</td>
    <td style="text-align:center">0</td></tr>
</tbody>
</table>

ここで $r_i$，$s_i$，$t_i$ は次の漸化式で書ける。

```math
\begin{align}
r_{i + 1} &= 2 t_i \bmod 3\\
s_{i + 1} &= (r_i + t_i) \bmod 3\\
t_{i + 1} &= s_i
\end{align}
```

これを $t_i$ についてまとめると $t_{i + 3} = (2 t_i + t_{i + 1}) \bmod 3$ となる。また $t_0 = 0$，$t_1 = 0$，$t_2 = 1$ である。$\alpha^2$ の係数がゼロ，すなわち $t_i = 0$ となる位置 $i$ を読み出して，これらの位置の間隔（差分）がボールの配置になることから，既約多項式を用いて解く方法はトリボナッチ数列を用いて解く方法と完全に等価であることが分かった。

一般的に既約多項式とトリボナッチ数列 $t_i$ は以下のように一対一で対応する。

```math
\begin{array}{c}
x^3 + a \cdot x^2 + b \cdot x + c \\
\Updownarrow \\
t_{i + 3} = \{ (p - c) t_i + (p - b) t_{i + 1} + (p - a) t_{i + 2} \} \bmod p
\end{array}
```

こう書いたほうが分かり易いかもしれない。

```math
\begin{array}{c}
x^3 - \bar{a}\cdot x^2 - \bar{b} \cdot x - \bar{c} \\
\Updownarrow \\
t_{i + 3} = \left( \bar{a} \cdot t_{i + 2} + \bar{b} \cdot t_{i + 1} + \bar{c} \cdot t_i \right) \bmod p
\end{array}
```

# 3. まとめ

既約多項式における $\alpha^0, \alpha^1, \alpha^2, \alpha^3, \cdots$ の計算はひたすら面倒で間違い易いが，トリボナッチ数列のように漸化式で表せるならプログラム化も容易であるし，表計算ソフトを使っても計算できる。

一方，謎であったトリボナッチ数列のパラメータは，有限体における三次の既約多項式の係数と一対一に対応することが分かった。これまでしらみつぶしに探索してきたトリボナッチ数列のパラメータについても，対応する既約多項式の係数から必要な条件をある程度類推できる。たとえば三次多項式 $x^3 + a \cdot x^2 + b \cdot x + c$ が既約であるための条件として $c \ne 0$ が挙げられる。トリボナッチ数列 $t_{i + 3} = \left( A \cdot t_i + B \cdot t_{i + 1} + C \cdot t_{i + 2} \right) \bmod p$ とおくと $A = (p - c) \bmod p$ という対応から $A \ne 0$ という条件が導かれる。実際，表１を見て確認すると $A = 0$ の場合の９ケースはすべて「×」となっている。既約性に着目すれば，探索範囲をさらに絞ることが可能になるかもしれない。

次回に続く。

https://qiita.com/TETSURO1999/items/051bb652fb5c9b6c8b6e

# 4. 参考文献

参考となったサイトを以下に示す。

- [http://www.inference.org.uk/cds/index.htm](http://www.inference.org.uk/cds/index.htm)
- [http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/JustinColannino/](http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/JustinColannino/)
- [秋山茂樹，魔円陣と有限幾何，数学セミナー2013年7月号，25～31頁，日本評論社](http://math.tsukuba.ac.jp/~akiyama/papers/proc/MagicCircle.pdf)
- [小林吹代，ガロアの数学「体」入門～魔円陣とオイラー方陣を例に～，技術評論社](https://gihyo.jp/book/2018/978-4-7741-9748-7)