0. はじめに
これまで一般化したビリヤード問題を解くため，海外を含めていろいろなサイトを見て学んだ。理屈も分からずに見よう見まねでコーディングしたところ，とりあえず問題が解けたのだが，やはり納得できない。
ということで今回はトリボナッチ数列による解法の謎について，なぜ解けるのか？どんな意味があるのか？考察していこうと思う。
本シリーズでは一貫してトリボナッチ数列という言葉を使っているが，おそらく正しくは「三次線形再帰（剰余）数列」とでも呼ぶべきものであろう。ところが，シリーズ初期に誤って用いてしまい，プログラムのコメント等にもそのまま使用しているため（あくまで自分の）混乱を防ぐためにもそのまま用いることにした。ご了承頂きたい。
1. トリボナッチ数列による解法のおさらい
初項 $t_0 = 0$，$t_1 = 0$，$t_2 = 1$ として，一般項 $t_i$（$i \ge 3$）を
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$ 通りの数列が存在する。このうち周期１３となるケースが４通り，周期２６となるケースが４通りある。
| 係数 | $t_i$ | 周期 | ||||
|---|---|---|---|---|---|---|
| $A$ | $B$ | $C$ | $0 \le i < 13$ | $13 \le i < 26$ | $26 \le i$ | |
| 0 | 0 | 0 | 0,0,1,0,0,0,0,0,0,0,0,0,0 | 0,0,0,0,0,0,0,0,0,0,0,0,0 | 0,0,0 | × |
| 0 | 0 | 1 | 0,0,1,1,1,1,1,1,1,1,1,1,1 | 1,1,1,1,1,1,1,1,1,1,1,1,1 | 1,1,1 | × |
| 0 | 0 | 2 | 0,0,1,2,1,2,1,2,1,2,1,2,1 | 2,1,2,1,2,1,2,1,2,1,2,1,2 | 1,2,1 | × |
| 0 | 1 | 0 | 0,0,1,0,1,0,1,0,1,0,1,0,1 | 0,1,0,1,0,1,0,1,0,1,0,1,0 | 1,0,1 | × |
| 0 | 1 | 1 | 0,0,1,1,2,0,2,2,1,0,1,1,2 | 0,2,2,1,0,1,1,2,0,2,2,1,0 | 1,1,2 | × |
| 0 | 1 | 2 | 0,0,1,2,2,0,2,1,1,0,1,2,2 | 0,2,1,1,0,1,2,2,0,2,1,1,0 | 1,2,2 | × |
| 0 | 2 | 0 | 0,0,1,0,2,0,1,0,2,0,1,0,2 | 0,1,0,2,0,1,0,2,0,1,0,2,0 | 1,0,2 | × |
| 0 | 2 | 1 | 0,0,1,1,0,2,2,0,1,1,0,2,2 | 0,1,1,0,2,2,0,1,1,0,2,2,0 | 1,1,0 | × |
| 0 | 2 | 2 | 0,0,1,2,0,1,2,0,1,2,0,1,2 | 0,1,2,0,1,2,0,1,2,0,1,2,0 | 1,2,0 | × |
| 1 | 0 | 0 | 0,0,1,0,0,1,0,0,1,0,0,1,0 | 0,1,0,0,1,0,0,1,0,0,1,0,0 | 1,0,0 | × |
| 1 | 0 | 1 | 0,0,1,1,1,2,0,1,0,0,1,1,1 | 2,0,1,0,0,1,1,1,2,0,1,0,0 | 1,1,1 | × |
| 1 | 0 | 2 | 0,0,1,2,1,0,2,2,1,1,1,0,1 | 0,0,1,2,1,0,2,2,1,1,1,0,1 | 0,0,1 | 13 |
| 1 | 1 | 0 | 0,0,1,0,1,1,1,2,2,0,1,2,1 | 0,0,1,0,1,1,1,2,2,0,1,2,1 | 0,0,1 | 13 |
| 1 | 1 | 1 | 0,0,1,1,2,1,1,1,0,2,0,2,1 | 0,0,1,1,2,1,1,1,0,2,0,2,1 | 0,0,1 | 13 |
| 1 | 1 | 2 | 0,0,1,2,2,1,0,0,1,2,2,1,0 | 0,1,2,2,1,0,0,1,2,2,1,0,0 | 1,2,2 | × |
| 1 | 2 | 0 | 0,0,1,0,2,1,1,1,0,0,1,0,2 | 1,1,1,0,0,1,0,2,1,1,1,0,0 | 1,0,2 | × |
| 1 | 2 | 1 | 0,0,1,1,0,0,1,1,0,0,1,1,0 | 0,1,1,0,0,1,1,0,0,1,1,0,0 | 1,1,0 | × |
| 1 | 2 | 2 | 0,0,1,2,0,2,0,1,1,1,2,1,1 | 0,0,1,2,0,2,0,1,1,1,2,1,1 | 0,0,1 | 13 |
| 2 | 0 | 0 | 0,0,1,0,0,2,0,0,1,0,0,2,0 | 0,1,0,0,2,0,0,1,0,0,2,0,0 | 1,0,0 | × |
| 2 | 0 | 1 | 0,0,1,1,1,0,2,1,1,2,1,0,1 | 0,0,2,2,2,0,1,2,2,1,2,0,2 | 0,0,1 | 26 |
| 2 | 0 | 2 | 0,0,1,2,1,1,0,2,0,0,1,2,1 | 1,0,2,0,0,1,2,1,1,0,2,0,0 | 1,2,1 | × |
| 2 | 1 | 0 | 0,0,1,0,1,2,1,1,2,0,1,1,1 | 0,0,2,0,2,1,2,2,1,0,2,2,2 | 0,0,1 | 26 |
| 2 | 1 | 1 | 0,0,1,1,2,2,0,0,1,1,2,2,0 | 0,1,1,2,2,0,0,1,1,2,2,0,0 | 1,1,2 | × |
| 2 | 1 | 2 | 0,0,1,2,2,2,1,2,0,1,0,1,1 | 0,0,2,1,1,1,2,1,0,2,0,2,2 | 0,0,1 | 26 |
| 2 | 2 | 0 | 0,0,1,0,2,2,1,2,0,0,1,0,2 | 2,1,2,0,0,1,0,2,2,1,2,0,0 | 1,0,2 | × |
| 2 | 2 | 1 | 0,0,1,1,0,1,0,2,1,2,2,2,1 | 0,0,2,2,0,2,0,1,2,1,1,1,2 | 0,0,1 | 26 |
| 2 | 2 | 2 | 0,0,1,2,0,0,1,2,0,0,1,2,0 | 0,1,2,0,0,1,2,0,0,1,2,0,0 | 1,2,0 | × |
周期１３または周期２６となる場合に着目する。$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$ の位置（指数）を読み出し，それらの位置の間隔を求めるとビリヤード問題の解（魔円陣）が得られるという・・・ホンマか？
2.2 既約多項式
有限体 $\mathbb{F}_3$ 上における三次の多項式は係数 $a,b,c$ が $\lbrace 0, 1, 2 \rbrace$ のいずれかであるから
$3^3 = 27$ 個存在する。このうち既約多項式となるものは８個あり，周期１３のものが４個，周期２６のものが４個存在する。
| $a$ | $b$ | $c$ | 多項式 | 既約 | 周期 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | $x^3$ | × | |
| 0 | 0 | 1 | $x^3 + 1 = (x + 1)^3$ | × | |
| 0 | 0 | 2 | $x^3 + 2 = (x + 2)^3$ | × | |
| 0 | 1 | 0 | $x^3 + x = x(x^2 + 1)$ | × | |
| 0 | 1 | 1 | $x^3 + x + 1 = (x + 2)(x^2 + x + 2)$ | × | |
| 0 | 1 | 2 | $x^3 + x + 2 = (x + 1)(x^2 + 2x + 2)$ | × | |
| 0 | 2 | 0 | $x^3 + 2x = x(x^2 + 2)$ | × | |
| 0 | 2 | 1 | $x^3 + 2x + 1$ | ○ | 26 |
| 0 | 2 | 2 | $x^3 + 2x + 2$ | ○ | 13 |
| 1 | 0 | 0 | $x^3 + x^2 = x^2(x + 1)$ | × | |
| 1 | 0 | 1 | $x^3 + x^2 + 1 = (x + 2)(x^2 + 2x + 2)$ | × | |
| 1 | 0 | 2 | $x^3 + x^2 + 2$ | ○ | 13 |
| 1 | 1 | 0 | $x^3 + x^2 + x = x(x + 2)^2$ | × | |
| 1 | 1 | 1 | $x^3 + x^2 + x + 1 = (x + 1)(x^2 + 1)$ | × | |
| 1 | 1 | 2 | $x^3 + x^2 + x + 2$ | ○ | 13 |
| 1 | 2 | 0 | $x^3 + x^2 + 2x = x(x^2 + x + 2)$ | × | |
| 1 | 2 | 1 | $x^3 + x^2 + 2x + 1$ | ○ | 26 |
| 1 | 2 | 2 | $x^3 + x^2 + 2x + 2 = (x + 1)(x^2 + 2) = (x + 2)(x + 1)^2$ | × | |
| 2 | 0 | 0 | $x^3 + 2x^2 = x^2(x + 2)$ | × | |
| 2 | 0 | 1 | $x^3 + 2x^2 + 1$ | ○ | 26 |
| 2 | 0 | 2 | $x^3 + 2x^2 + 2 = (x + 1)(x^2 + x + 2)$ | × | |
| 2 | 1 | 0 | $x^3 + 2x^2 + x = x(x + 1)^2$ | × | |
| 2 | 1 | 1 | $x^3 + 2x^2 + x + 1$ | ○ | 26 |
| 2 | 1 | 2 | $x^3 + 2x^2 + x + 2 = (x + 2)(x^2 + 1)$ | × | |
| 2 | 2 | 0 | $x^3 + 2x^2 + 2x = x(x^2 + 2x + 2)$ | × | |
| 2 | 2 | 1 | $x^3 + 2x^2 + 2x + 1 = (x + 1)(x + 2)^2 = (x + 2)(x^2 + 2)$ | × | |
| 2 | 2 | 2 | $x^3 + 2x^2 + 2x + 2$ | ○ | 13 |
なお，既約多項式の確認方法はひたすら面倒である。下記のように一次式と二次式の積より可約多項式を列挙して，これらに該当しないものが既約多項式である。※定数項を持たないなど明らかに可約なものを除く
| $x + 1$ | $x + 2$ | |
|---|---|---|
| $x^2 + 1$ | $(x + 1)(x^2 + 1)$ $= x^3 + x^2 + x + 1$ |
$(x + 2)(x^2 + 1)$ $= x^3 + 2x^2 + x + 2$ |
| $x^2 + 2$ | $(x + 1)(x^2 + 2)$ $= x^3 + x^2 + 2x + 2$ |
$(x + 2)(x^2 + 2)$ $= x^3 + 2x^2 + 2x + 1$ |
| $x^2 + x + 1$ | $(x + 1)(x^2 + x + 1)$ $= x^3 + 2x^2 + 2x + 1$ |
$(x + 2)(x^2 + x + 1)$ $= x^3 + 2$ |
| $x^2 + x + 2$ | $(x + 1)(x^2 + x + 2)$ $= x^3 + 2x^2 + 2$ |
$(x + 2)(x^2 + x + 2)$ $= x^3 + x + 1$ |
| $x^2 + 2x + 1$ | $(x + 1)(x^2 + 2x + 1)$ $= x^3 + 1$ |
$(x + 2)(x^2 + 2x + 1)$ $= x^3 + x^2 + 2x + 2$ |
| $x^2 + 2x + 2$ | $(x + 1)(x^2 + 2x + 2)$ $= x^3 + x + 2$ |
$(x + 2)(x^2 + 2x + 2)$ $= x^3 + x^2 + 1$ |
2.3 実際に計算してみる
既約多項式となる８個の場合について，それぞれ実際に計算してみよう。
- $\alpha^3 + 2\alpha + 1 = 0$ すなわち $\alpha^3 = \alpha + 2$ のとき
$\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 3, 9, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 2, 6, 4 \rbrace$ となる。
\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^3 + 2\alpha + 2 = 0$ すなわち $\alpha^3 = \alpha + 1$ のとき
$\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 3, 9, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 2, 6, 4 \rbrace$ となる。
\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^3 + \alpha^2 + 2 = 0$ すなわち $\alpha^3 = 2\alpha^2 + 1$ のとき
$\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 5, 11, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 4, 6, 2 \rbrace$ となる。
\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^3 + \alpha^2 + \alpha + 2 = 0$ すなわち $\alpha^3 = 2\alpha^2 + 2\alpha + 1$ のとき
$\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 4, 6, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 3, 2, 7 \rbrace$ となる。
\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^3 + \alpha^2 + 2\alpha + 1 = 0$ すなわち $\alpha^3 = 2\alpha^2 + \alpha + 2$ のとき
$\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 8, 10, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 7, 2, 3 \rbrace$ となる。
\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^3 + 2\alpha^2 + 1 = 0$ すなわち $\alpha^3 = \alpha^2 + 2$ のとき
$\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 5, 11, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 4, 6, 2 \rbrace$ となる。
\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^3 + 2\alpha^2 + \alpha + 1 = 0$ すなわち $\alpha^3 = \alpha^2 + 2\alpha + 2$ のとき
$\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 4, 6, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 3, 2, 7 \rbrace$ となる。
\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^3 + 2\alpha^2 + 2\alpha + 2 = 0$ すなわち $\alpha^3 = \alpha^2 + \alpha + 1$ のとき
$\alpha^2$ を含まない要素の位置（指数）は $\lbrace 0, 1, 8, 10, 13 \rbrace$ であり，それらの差分を求めると $\lbrace 1, 7, 2, 3 \rbrace$ となる。
\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}
以上より，ボールの個数 $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$ を示す。
| $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $r_i$ | 1 | 0 | 0 | 2 | 0 | 2 | 1 | 2 | 2 | 1 | 0 | 2 | 2 | 2 |
| $s_i$ | 0 | 1 | 0 | 1 | 2 | 1 | 1 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
| $t_i$ | 0 | 0 | 1 | 0 | 1 | 2 | 1 | 1 | 2 | 0 | 1 | 1 | 1 | 0 |
ここで $r_i$，$s_i$，$t_i$ は次の漸化式で書ける。
\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$ は以下のように一対一で対応する。
\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}
こう書いたほうが分かり易いかもしれない。
\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$ の場合の９ケースはすべて「×」となっている。既約性に着目すれば，探索範囲をさらに絞ることが可能になるかもしれない。
次回に続く。
4. 参考文献
参考となったサイトを以下に示す。