ライツアウトの数理（4年ゼミ）

ライツアウトの数理も再開．
前期までは何とかして ${\rm rank}(M_n)$ が2項からなる場合だけでも解決できないかと悩んでいたが，この夏にあれこれ考えてみて，任意次数のライツアウトに対しての ${\rm rank}(M_n)$ が決定できることが分かった．そのポイントとなる仕組みが，Fibonacci多項式である．

ここでは $q_0(t)=p_{-1}(t)=0,q_1(t)=p_0(t)=1$ から始めて，
$\begin{pmatrix}p_{n+1}(t)\\q_{n+1}(t)\end{pmatrix}=\begin{pmatrix}t&1\\1&0\end{pmatrix}\begin{pmatrix}p_n(t)\\q_n(t)\end{pmatrix}$
によって定まる多項式をFibonacci多項式と呼ぶことにするが，一般にはこのうち $q_n(t)$ のほうを指す．すぐ分かるように， $q_{n+1}(t)=p_{n}(t)$ なので，漸化式

$p_{n+2}(t)=tp_{n+1}(t)+p_n(t)$

が得られる．この多項式を用いると，結論は

${\rm rank}(M_n)=n-\deg({\rm GCD}(p_n(t),p_n(t+1)))$

となるということだ．ここで ${\rm GCD}(f(t),g(t))$ は多項式 $f(t),g(t)$ の最大共通因子を表し， $\deg(f(t))$ は $f(t)$ の次数を表す．

これが正しそうか，幾つかの例で見てみよう．そのために，写像 $\sigma(n)=2n+1$ を用意しておく．これは，以下のようなFibonacci多項式の性質に由来する．
まず， $n\ge1$ に対して，
$\begin{pmatrix}t&1\\1&0\end{pmatrix}^n=\begin{pmatrix}p_{n}(t)&p_{n-1}(t)\\p_{n-1}(t)&p_{n-2}(t)\end{pmatrix}$
が帰納的に分かるので，等式
$\begin{align*} \begin{pmatrix}p_{m+n}(t)&p_{m+n-1}(t)\\p_{m+n-1}(t)&p_{m+n-2}(t)\end{pmatrix} &=\begin{pmatrix}t&1\\1&0\end{pmatrix}^{m+n}=\begin{pmatrix}t&1\\1&0\end{pmatrix}^m\begin{pmatrix}t&1\\1&0\end{pmatrix}^n\\ &=\begin{pmatrix}p_{m}(t)&p_{m-1}(t)\\p_{m-1}(t)&p_{m-2}(t)\end{pmatrix}\begin{pmatrix}p_{n}(t)&p_{n-1}(t)\\p_{n-1}(t)&p_{n-2}(t)\end{pmatrix} \end{align*}$
を通じて

$\begin{align*} p_{m+n}(t)&=p_m(t)p_n(t)+p_{m-1}(t)p_{n-1}(t)\\ p_{m+n-1}(t)&=p_{m-1}(t)p_{n}(t)+p_{m-2}(t)p_{n-1}(t) \end{align*}$

が得られる．さらに $m=n$ とすると，

$p_{2n-1}(t)=p_{n-1}(t)(p_n(t)+p_{n-2}(t))=tp_{n-1}(t)^2\text{ すなわち }p_{\sigma(n)}(t)=tp_n(t)^2$

が得られる．ただし， $\mathbb{F}_2$ での演算なので，Fibonacci多項式の漸化式が
$p_n(t)+p_{n-2}(t)=tp_{n-1}(t)$
とも表されることを使った．また以下では，しばしば
$(a+b)^{2^i}=a^{2^i}+b^{2^i}$
が成り立つことを使う．たとえば $p(t)^2=p(t^2)$ などと書き換えられる．

2021年度卒論で得られた結果の一つが， $n=2^m-1$ のとき ${\rm rank}(M_n)=n$ ということだった．一方， $2^{m+1}-1=\sigma^m(1)$ に気づけば，帰納的に

$p_1(t)=t,p_3(t)=p_{\sigma(1)}(t)=tp_1(t)^2=t^3,\dots,p_{\sigma^m(1)}(t)=t^{2^{m+1}-1}$

が分かる．すると， $g(t)={\rm GCD}(p_n(t),p_n(t+1))={\rm GCD}(t^n,(t+1)^n)=1$ となり， $\deg(g(t))=0$ なので， $n-\deg(g(t))=n$ で先程の結果に一致する．

また，卒論では $p_n(t)$ が2項からなる場合（ $n=3\cdot2^m-1$ ）について ${\rm rank}(M_n)=2^m+1$ と予想していた． $n=3\cdot2^m-1=\sigma^m(2)$ に気づけば，帰納的に

$\begin{gather*} p_2(t)=t^2+1=(t+1)^2,p_5(t)=p_{\sigma(2)}(t)=tp_2(t)^2=t(t+1)^4,\\ \dots,p_{\sigma^m(2)}(t)=t^{2^m-1}(t+1)^{2^{m+1}}\end{gather*}$

が得られる．さてすると， $2^m-1<2^{m+1}$ なので，

$\begin{align*} g(t)&={\rm GCD}(p_n(t),p_n(t+1))={\rm GCD}(t^{2^m-1}(t+1)^{2^{m+1}},(t+1)^{2^m-1}t^{2^{m+1}})\\ &=t^{2^m-1}(t+1)^{2^m-1} \end{align*}$

となるから， $\deg(g(t))=2(2^m-1)$ であり，

${\rm rank}(M_n)=3\cdot2^m-1-2(2^m-1)=2^m+1$

となって，卒論で予想したとおりの値となった．

タカラから発売された $5\times 5$ のオリジナルのライツアウトでは， $5^2=25$ -次元のライツアウト行列 $A$ を考えることになるが，そのランクが，
${\rm rank}(A)=5\cdot4+{\rm rank}(M_5)=20+(5-2)=23$
となり，よく知られた結果に一致する．つまり，あのゲームでは，2次元分の解の自由度があり，また，解がない（all offにできない）初期配置があるということだ．
drive.google.com

ゼミの風景

おそらくお気楽はしのすけゼミの諸風景

ライツアウトの数理（4年ゼミ）