0. はじめに
これまで一般化したビリヤード問題を解くため，海外を含めていろいろなサイトを見て学んできた。理屈も分からずに見よう見まねでコーディングしたところ，とりあえず問題が解けたのだが，やはり納得できない。
前回の記事でボールの個数 $n = 1 + p$ のときは，三次の線形再帰剰余数列を用いた解法は有限体 $\mathbb{F}_{p}$ の射影平面による解法と等価であることを示した。
残された最後の謎は，ボールの個数 $n = 1 + p^m$ のとき $3m$ 次の線形再帰剰余数列を用いると何故か解けてしまうということである。下記の記事を執筆した当時は原理不明だったが，おそらく有限体 $\mathbb{F}_{p^m}$ の射影平面による解法と等価であると予想される。
1. 線形再帰剰余数列を用いた解法（再掲）
1.1 解法概要
素数 $p$，自然数 $m$ に対して，ボールの個数 $n = 1 + p^m$ とする。素数のべき乗数（指数）$m$ に応じて $3m$ 次の線形再帰剰余数列 $t_i$ を作る。初項 $t_i$（$0 \le i < 3m$）は
t_i = \left\lbrace \begin{array}{ll}
0 & 0 \le i < 3m - 1 \\
1 & i = 3m - 1
\end{array} \right.
とし，一般項 $t_i$（$i \ge 3m$）は
t_i = \left[ \displaystyle \sum_{k = 1}^{3m} a_{3m - k} \times t_{i - k} \right] \bmod p
とする。ここで数列を決定する重要なパラメータ $0 \le a_k < p$ である。
ここでボールの数値の総和 $\sigma = n(n - 1) + 1$ として，$t_i$ から $t_{i + (m - 1)\sigma}$ まで間隔 $\sigma$ で数列の値がすべてゼロになる $i$ の位置を読み取り，これを数列 $u_j$ とする。
| $i$ | $0$ | $\cdots$ | $u_0$ | $\cdots$ | $u_1$ | $\cdots$ | $u_2$ | $\cdots$ | $2\sigma - 1$ |
|---|---|---|---|---|---|---|---|---|---|
| $t_i$ | $\cdots$ | $\cdots$ | $0$ | $\cdots$ | $0$ | $\cdots$ | $0$ | $\cdots$ | $\cdots$ |
| $t_{i + \sigma}$ | $\cdots$ | $\cdots$ | $0$ | $\cdots$ | $0$ | $\cdots$ | $0$ | $\cdots$ | $\cdots$ |
| $t_{i + 2\sigma}$ | $\cdots$ | $\cdots$ | $0$ | $\cdots$ | $0$ | $\cdots$ | $0$ | $\cdots$ | $\cdots$ |
| $\cdots$ | $\cdots$ | $\cdots$ | $0$ | $\cdots$ | $0$ | $\cdots$ | $0$ | $\cdots$ | $\cdots$ |
| $t_{i + (m - 1)\sigma}$ | $\cdots$ | $\cdots$ | $0$ | $\cdots$ | $0$ | $\cdots$ | $0$ | $\cdots$ | $\cdots$ |
次に数列 $v_j = u_{j + 1} - u_j$ を求める。$u_j$ は純単調増加の数列のため $v_j$ は必ず自然数の数列となる。
パラメータ $a_k$ を正しく設定すると，$v_j$ の任意の位置から連続する $n$ 個の項を抜き出せばビリヤード問題の解になるが，回転対称の解を除くため $v_j = 1$ となる位置から連続する $n + 1$ 個の項を抜き出し，これを数列 $w_h$（$0 \le h \le n$）とおく。正しくビリヤード問題の解を得られていれば必ず $w_n = 1$ となる。
| $h$ | $0$ | $1$ | $\cdots$ | $n - 1$ | $n$ |
|---|---|---|---|---|---|
| $w_h$ | $1$ | $w_1$ | $\cdots$ | $w_{n - 1}$ | $1$ |
左右対称の解を除くため，$w_1 < w_{n - 1}$ の場合は $w_0$ から連続する $n$ 個の項を抜き出し，$w_1 > w_{n - 1}$ の場合は $w_n$ から逆向きに連続する $n$ 個の項を抜き出す。
1.2 具体的な計算例
ボールの個数 $n = 5 = 1 + 2^2$ の場合を考える。素数 $p = 2$，指数 $m = 2$ であるから，$3m = 6$ 次の線形再帰剰余数列を作る。ボールの数値の総和 $\sigma = n(n - 1) + 1 = 21$ となるので $t_i = 0$ かつ $t_{i + 21} = 0$ となる位置を赤色で示す。以下は $a_k = \lbrace 1, 0, 0, 0, 0, 1 \rbrace$ のときの計算例である。
| $0 \le i < 21$ | $21 \le i < 42$ | $42 \le i$ | |
|---|---|---|---|
| $t_i$ | 000001111110101011001 | 101110110100100111000 | 101111 |
| $t_{i + 21}$ | 101110110100100111000 | 101111001010001100001 | 000001 |
$t_i = 0$ かつ $t_{i + 21} = 0$ となる位置 $i$ を読み取ると
u_j = \{ 1, 11, 13, 18, 19, 22, 32, 34, 39, 40, 43, \cdots \}
となり，これらの差分を求めると
v_j = \{ 10, 2, 5, 1, 3, 10, 2, 5, 1, 3, \cdots \}
となる。$1$ の数値から連続する $n = 5$ 個の数値を抜き出すと $w_h = \lbrace 1, 3, 10, 2, 5 \rbrace$ となり，$n = 5$ の場合のビリヤード問題の解が得られた。
2. 有限体の射影平面による解法
以下の議論は，法 $p$ における合同式，すなわち加減乗算の結果を素数 $p$ で割った余りとして演算を定義していることに注意されたい。面倒なので $\bmod p$ の記述は省略した。
2.1 解法概要
ボールの個数 $n = 1 + p^m$ の場合，対応する有限体 $\mathbb{F}_{p^m}$ となる。三次の既約多項式 $f(x)$ を選び，$f(x) = 0$ の解を $\alpha$ とおく。
ボールの数値の総和 $\sigma = n(n - 1) + 1$ とすると，$\alpha$ のべき乗を計算する。
1, \alpha, \alpha^2, \alpha^3, \cdots, \alpha^{\sigma - 1}
$f(\alpha) = 0$ より $\alpha^3$ は $\alpha$ の二次式以下で表すことができるので，$\alpha^i$ は$\alpha$ の二次式以下に次数下げができる。このうち $\alpha^2$ を含まない $\alpha^i$ の指数（位置）を読み出し，これらの差分（間隔）を求めるとビリヤード問題の解が得られる。
2.2 具体的な計算例
ボールの個数 $n = 5 = 1 + 2^2$ の場合を考える。対応する有限体は $\mathbb{F}_4$ となる。有限体 $\mathbb{F}_4$ のメンバーは 四次方程式 $x^4 - x = x(x - 1)(x^2 + x + 1) = 0$ の解である。このうち $x^2 + x + 1 = 0$ の解を $\omega$ とおくと $\omega^2 + \omega + 1 = 0$ より $\omega^2 = \omega + 1$ となる。よって有限体 $\mathbb{F}_4$ のメンバーは $\mathbb{F}_4 = \lbrace 0, 1, \omega, \omega^2 \rbrace = \lbrace 0, 1, \omega, \omega + 1 \rbrace$ である。
三次の既約多項式として $f(x) = x^3 + x^2 + x + \omega$ を選ぶ。$f(x) = 0$ の解を $\alpha$ とすると，$\alpha^3 = \alpha^2 + \alpha + \omega$ となる。これを利用して $\alpha^0$ から $\alpha^{21}$ まで順次求めていき，$\alpha^{i}$ を $\alpha$ の二次式以下に次数下げを行って表す。
\begin{aligned}
\alpha^0 &= 1 & (*) \\
\alpha^1 &= \alpha & (*) \\
\alpha^2 &= \alpha^2 \\
\alpha^3 &= \omega + \alpha + \alpha^2 \\
\alpha^4 &= \omega + \alpha + \omega \alpha & (*) \\
\alpha^5 &= \omega \alpha + \alpha^2 + \omega \alpha^2 \\
\alpha^6 &= 1 + \alpha + \omega \alpha + \alpha^2 \\
\alpha^7 &= \omega + \omega \alpha^2 \\
\alpha^8 &= 1 + \omega + \omega \alpha^2 \\
\alpha^9 &= 1 + \omega + \alpha + \omega \alpha^2 \\
\alpha^{10} &= 1 + \omega + \alpha + \alpha^2 + \omega \alpha^2 \\
\alpha^{11} &= 1 + \omega \alpha^2 \\
\alpha^{12} &= 1 + \omega + \alpha + \omega \alpha + \omega \alpha^2 \\
\alpha^{13} &= 1 + \omega + \alpha + \alpha^2 \\
\alpha^{14} &= \omega + \omega \alpha & (*) \\
\alpha^{15} &= \omega \alpha + \omega \alpha^2 \\
\alpha^{16} &= 1 + \omega + \omega \alpha & (*) \\
\alpha^{17} &= \alpha + \omega \alpha + \omega \alpha^2 \\
\alpha^{18} &= 1 + \omega + \omega \alpha + \alpha^2 \\
\alpha^{19} &= \omega + \omega \alpha + \alpha^2 + \omega \alpha^2 \\
\alpha^{20} &= 1 + \alpha + \alpha^2 \\
\alpha^{21} &= \omega & (*) \\
\end{aligned}
$\alpha^2$ の項を持たない指数（位置）は $0, 1, 4, 14, 16, 21$ となり，これらの差分（間隔）は $1, 3, 10, 2, 5$ となり，$n = 5$ の場合のビリヤード問題の解が得られた。
2.3 線形再帰剰余数列を用いた解法との対応
$\alpha^i$ は高々 $\alpha$ の二次式以下で表すことができるので
\alpha_i = r_i + s_i \alpha + t_i \alpha^2 + u_i \omega + v_i \omega \alpha + w_i \omega \alpha^2
とおく。$\alpha^3 = \alpha^2 + \alpha + \omega$，$\omega^2 = \omega + 1$ のとき
\begin{aligned}
\alpha_{i + 1}
&= (r_i + s_i \alpha + t_i \alpha^2 + u_i \omega + v_i \omega \alpha + w_i \omega \alpha^2) \alpha \\
&= w_i + (r_i + t_i) \alpha + (s_i + t_i) \alpha^2 \\
&+ (t_i + w_i) \omega + (u_i + w_i) \omega \alpha + (v_i + w_i) \omega \alpha^2 \\
&= r_{i + 1} + s_{i + 1} \alpha + t_{i + 1} \alpha^2 + u_{i + 1} \omega + v_{i + 1} \omega \alpha^2 + w_{i + 1} \omega \alpha^2
\end{aligned}
となるので各係数の漸化式は次のようになる。
\begin{aligned}
r_{i + 1} &= w_i \\
s_{i + 1} &= r_i + t_i\\
t_{i + 1} &= s_i + t_i \\
u_{i + 1} &= t_i + w_i \\
v_{i + 1} &= u_i + w_i \\
w_{i + 1} &= v_i + w_i \\
\end{aligned}
$\alpha^2$ の係数である $t_i$ および $w_i$ についてまとめると
\begin{aligned}
t_{i + 3} &= t_{i + 2} + t_{i + 1} + w_i \\
w_{i + 3} &= w_{i + 2} + w_{i + 1} + w_i + t_i \\
\end{aligned}
となる。この漸化式に従って $t_i$ および $w_i$ の値を計算すると以下のようになる。$t_i = 0$ かつ $w_i = 0$ となる位置を赤色で示す。
| $0 \le i < 21$ | $21 \le i < 42$ | $42 \le i$ | |
|---|---|---|---|
| $t_i$ | 001101100010010000111 | 000001011111100101010 | 001 |
| $w_i$ | 000001011111100101010 | 001100111101110101101 | 001 |
$t_i = 0$ かつ $w_i = 0$ となる位置 $i$ を読み取ると
\{ 0, 1, 4, 14, 16, 21, 22, 25, 35, 37, 42, 43 \cdots \}
となり，これらの差分（間隔）を求めると
\{ 1, 3, 10, 2, 5, 1, 3, 10, 2, 5, 1 \cdots \}
となる。$1$ の数値から連続する $n = 5$ 個の数値を取り出すと $\lbrace 1, 3, 10, 2, 5 \rbrace$ となり，$n = 5$ の場合のビリヤード問題の解が得られた。
ここで $w_i = t_{i + 21}$ であることに気づくと，再帰剰余数列を用いた解法と極めて似通っていることが分かる。ここで
\begin{aligned}
t_{i + 3} &= t_{i + 2} + t_{i + 1} + w_i \\
w_{i + 3} &= w_{i + 2} + w_{i + 1} + w_i + t_i \\
\end{aligned}
より，$t_i$ についてまとめると
t_{i + 6} = t_{i + 4} + t_{i + 3} + t_{i + 1} + t_i \\
となり，$t_i$ も六次の線形再帰剰余数列で表すことができる。
このケースでは幸いなことに比較的簡単に $t_i$ 単独の数列を得ることができたが，一般的にはそうとは限らないことを次項で示す。
表４の結果を得るためには初期値 $(t_0, t_1, t_2, t_3, t_4, t_5) = (0, 0, 1, 1, 0, 1)$ から始める必要があるが，どんな場合でも確定しているのは $(t_0, t_1, t_2) = (0, 0, 1)$ のみであり，$(t_3, t_4, t_5)$ については $t_i$ と $w_i$ の双方の値を用いて計算しなくてはならない。これは面倒である。
それでは逆に，表３のように初期値 $(t_0, t_1, t_2, t_3, t_4, t_5) = (0, 0, 0, 0, 0, 1)$ から始めても解けてしまうのは何故か？を考える。実をいうと初期値はオールゼロ以外であれば何でもよい。というのは $t_i$ から連続する６個の数値を１組にして考えると，オールゼロ以外のすべての組を巡回するからだ。オールゼロ以外であれば，どの初期値から始めても解は得られる一例を示そう。
初期値 $(t_0, t_1, t_2, t_3, t_4, t_5) = (0, 0, 0, 0, 0, 1)$，漸化式 $t_{i + 6} = t_{i + 4} + t_{i + 3} + t_{i + 1} + t_i$ の場合の計算例を以下に示す。$t_i = 0$ かつ $t_{i + 21} = 0$ となる位置を赤色で示す。
| $0 \le i < 21$ | $21 \le i < 42$ | $42 \le i$ | |
|---|---|---|---|
| $t_i$ | 000001011111100101010 | 001100111101110101101 | 001101 |
| $t_{i + 21}$ | 001100111101110101101 | 001101100010010000111 | 000001 |
$t_i = 0$ かつ $t_{i + 21} = 0$ となる位置 $i$ を読み取ると
\{ 0, 1, 4, 14, 16, 21, 22, 25, 35, 37, 42, 43 \cdots \}
となり，これらの差分（間隔）を求めると
\{ 1, 3, 10, 2, 5, 1, 3, 10, 2, 5, 1 \cdots \}
となる。やはり，同様にビリヤード問題の解が得られた。
念のためもう一つ試そう。
初期値 $(t_0, t_1, t_2, t_3, t_4, t_5) = (0, 0, 1, 0, 0, 1)$，漸化式 $t_{i + 6} = t_{i + 4} + t_{i + 3} + t_{i + 1} + t_i$ の場合の計算例を以下に示す。$t_i = 0$ かつ $t_{i + 21} = 0$ となる位置を赤色で示す
| $0 \le i < 21$ | $21 \le i < 42$ | $42 \le i$ | |
|---|---|---|---|
| $t_i$ | 001001000011100000101 | 111110010101000110011 | 110111 |
| $t_{i + 21}$ | 111110010101000110011 | 110111010110100110110 | 001001 |
$t_i = 0$ かつ $t_{i + 21} = 0$ となる位置 $i$ を読み取ると
\{ 6, 8, 13, 14, 17, 27, 29, 34, 35, 38, \cdots \}
となり，これらの差分（間隔）を求めると
\{ 2, 5, 1, 3, 10, 2, 5, 1, 3, \cdots \}
となる。やはり，同様にビリヤード問題の解が得られた。
数列の初期値は巡回平面上の点の位置に対応し，その１の例では $\alpha^{21}$，その２の例では $\alpha^8$ の位置に対応する。巡回平面を一周すればビリヤード問題の解を得られるので，スタート地点がシフトしたに過ぎない。
2.4 注意事項
$3m$ 次の線形再帰剰余数列を用いた解法は有限体 $F_{p^m}$ の射影平面による解法と等価であることを示したが，数列の係数 $3m$ 個と有限体の三次既約多項式の係数 $3m$ 個は必ずしも一対一に対応する訳ではない。
一例として $p = 2$，$m = 2$ の場合，すなわち有限体 $\mathbb{F}_4$ 上の三次既約多項式 $f(x)$ を係数 $A \thicksim F$ を用いて
f(x) = x^3 + (A + D\omega)x^2 + (B + E\omega) x + (C + F\omega)
とおき，$f(x) = 0$ となる解を $\alpha$ とおくと
\alpha^3 = (A + D\omega) \alpha^2 + (B + E\omega) \alpha + (C + F\omega)
と書ける。なお $A \thicksim F$ は $p$ より小さい非負の整数，すなわち $\lbrace 0, 1 \rbrace$ の二値のいずれかである。
また $\alpha^i$ は高々 $\alpha$ の二次式以下で表すことができるので
\alpha_i = r_i + s_i \alpha + t_i \alpha^2 + u_i \omega + v_i \omega \alpha + w_i \omega \alpha^2
とおくと，
\begin{aligned}
\alpha_{i + 1}
&= (r_i + s_i \alpha + t_i \alpha^2 + u_i \omega + v_i \omega \alpha + w_i \omega \alpha^2) \alpha \\
&= (C t_i + F w_i) \\
&+ (B t_i + E w_i + r_i) \alpha \\
&+ (A t_i + D w_i + s_i) \alpha^2 \\
&+ \{F t_i + (C + F) w_i\} \omega \\
&+ \{E t_i + (B + E) w_i + u_i\} \omega \alpha \\
&+ \{D t_i + (A + D) w_i + v_i\} \omega \alpha^2 \\
&= r_{i + 1} + s_{i + 1} \alpha + t_{i + 1} \alpha^2 + u_{i + 1} \omega + v_{i + 1} \omega \alpha^2 + w_{i + 1} \omega \alpha^2
\end{aligned}
となるので各係数の漸化式は次のようになる。
\begin{aligned}
r_{i + 1} &= C t_i + F w_i \\
s_{i + 1} &= B t_i + E w_i + r_i \\
t_{i + 1} &= A t_i + D w_i + s_i \\
u_{i + 1} &= F t_i + (C + F)w_i \\
v_{i + 1} &= E t_i + (B + E)w_i + u_i \\
w_{i + 1} &= D t_i + (A + D)w_i + v_i \\
\end{aligned}
$\alpha^2$ の係数である $t_i$ および $w_i$ についてまとめると
\begin{aligned}
t_{i + 3} &= A t_{i + 2} + B t_{i + 1} + C t_i + D w_{i + 2} + E w_{i + 1} + F w_i \\
w_{i + 3} &= D t_{i + 2} + E t_{i + 1} + F t_i + (A + D)w_{i + 2} + (B + E)w_{i + 1} + (C + F)w_i
\end{aligned}
と，ここまでは比較的簡単に導くことができる。しかし，ここから $t_i$ について求めるのがなかなか容易ではない。Z変換を用いて $t_i \rightarrow T(z)$，$w_i \rightarrow W(z)$ と表すと
\begin{aligned}
T(z) &= (A z^{-1} + B z^{-2} + C z^{-3}) T(z) \\
&+ (D z^{-1} + E z^{-2} + F z^{-3}) W(z) \\
W(z) &= (D z^{-1} + E z^{-2} + F z^{-3}) T(z) \\
&+ \{(A + D) z^{-1} + (B + E) z^{-2} + (C + F) z^{-3}\} W(z)
\end{aligned}
となる。これより $W(z)$ を消去して $T(z)$ について求めると
\begin{aligned}
T(z) &= \{ D z^{-1} \\
&+ (A^2 + AD + D^2 + E) z^{-2} \\
&+ (AE + BD + F) z^{-3} \\
&+ (B^2 + BE + E^2 + AF + CD) z^{-4} \\
&+ (BF + CE) z^{-5} \\
&+ (C^2 + CF + F^2) z^{-6} \} T(z)
\end{aligned}
となる。とくに $A \thicksim F$ は $\lbrace 0, 1 \rbrace$ の二値であるので $x^2 = x$ とおき，論理和演算を $x|y = x + xy + y$ と定義すると
\begin{aligned}
T(z) &= \{ D z^{-1} \\
&+ (A|D + E) z^{-2} \\
&+ (AE + BD + F) t_z^{-3} \\
&+ (B|E + AF + CD) z^{-4} \\
&+ (BF + CE) z^{-5} \\
&+ (C|F) z^{-6} \} T(z) \end{aligned}
と書ける。最後は逆Z変換を行って $T(z) \rightarrow t_i$ に戻してやればいい。
\begin{aligned}
t_{i + 6} &= D t_{i + 5} \\
&+ (A|D + E) t_{i + 4} \\
&+ (AE + BD + F) t_{i + 3} \\
&+ (B|E + AF + CD) t_{i + 2} \\
&+ (BF + CE) t_{i + 1} \\
&+ (C|F) t_i\end{aligned}
既約多項式 $f(x)$ の係数 $A \thicksim F$ と数列 $t_i$ の係数は同じ数（自由度）であるが，一対一に対応している訳ではないことが分かる。$f(x)$ が既約多項式である条件から数列 $t_i$ の係数の条件を導くのはなかなか自明でないが，一つだけ簡単に分かる点として $C \ne 0$ または $F \ne 0$ であることが挙げられる。$C = 0$ かつ $F = 0$ になってしまうと $f(x)$ は定数項がなくなり，簡単に因数分解できてしまうからだ。少なくとも $C$ と $F$ の一方が非ゼロであれば数列 $t_i$ の係数 $C|F$ も非ゼロになることが分かる。
ただし，これは $p = 2$ の場合に限る。$2 \equiv 0 \pmod p$ であったり，$x^2 \equiv x \pmod p$ という性質を利用して特別に簡略化できているからだ。$p \ge 3$ の場合はもっと複雑な形になり，$z^{-6}$ の係数が非ゼロという条件も自明でなくなってしまう。
3. まとめ
素数 $p$，自然数 $m$ に対して，ボールの個数 $n = 1 + p^m$ の場合において，$3m$ 次の線形再帰剰余数列を用いた解法は有限体 $F_{p^m}$ の射影平面による解法と等価であることを示した。
謎 は 全 て 解 け た
あ！これ犀川先生の台詞じゃなかったわ。
ただし，有限体の既約多項式の係数と数列の係数は一対一に対応する訳ではないので，多項式の既約判定を速やかに行うアルゴリズムが存在したとしても，これを数列の係数に適用することは難しいと考えられる。
次回は数学的な証明というか補完を行いたい。
4. 参考文献
この本は大変参考になった。