OMCB011(H) - 周期性の発見について

todo $\pmod{\star}$ が抜けている場所の修正あるいは $\pmod{\star}$ をすべて略すか？

～はじめに～

　公式解説 同様の考察ステップを踏み, $10$ の剰余を $5$ と $2$ の剰余に分けて考えることで, $$a_0=2,\quad a_1=3,\quad a_{n+2}=3a_{n+1}+a_{n}\pmod{5}$$ と定めた時に $a_{n}=1\pmod {5}$ なる $n$ の決定が目標となります.
すると, 公式解説にもあるように数列の周期性を利用が得策のようです.

　本ユーザー解説ではこの周期の発見及びその後の処理を楽に行う方法について説明します.

～具体的な方法～

　$b_n:=\frac{a_{n+1}}{a_{n}}\pmod{5}$ とします. $b_n$ の前 $4$ 項を愚直に計算をすると, $4,2,1,4$ となっています.
ここで, $b_{n+1}$ は $b_{n}$ の値のみから定まります.
実際, $a_{n+2}=3a_{n+1}+a_{n}=a_{n+1}(3+\frac{1}{b_{n}})$ より, $b_{n+1}=3+\frac{1}{b_n}\pmod{5}$ です.
すなわち, $b$ は $4,2,1,4,2,1,4,2,1,\dots$ と周期 $3$ で繰り返すことがわかります.
(注: $b$ は $a_{n}=0$ とならないため, 今回の数値設定の元で定義できているように感じるかもしれません. しかし実際には $b_n=0$ となる場合でもある種の正当化ができます. 詳細は次節へ)

　今,

• $\frac{a_{n+1}}{a_{n}}$ は $4,2,1,4,2,1,4,\dots$ と周期 $3$ で繰り返す.
• $a_{3}=3a_{0} \pmod{5}$ である.

が分かっています.
ここで, 周期性から $\frac{a_{1}}{a_{0}}=\frac{a_{4}}{a_{3}}$ であるので, $a_{4}=3a_{1}\pmod{5}$ が分かります. 以下同様にして, $a_{n+3}=3a_{n}\pmod{5}$ が全ての $n$ で成り立ちます.

　以上から, $a$ の前 $3$ 項の値 $(2,3,1)$ と併せて, $$a_{n}= \begin{cases} 2\times 3^{m} &(n\mod 3=0)\\ 3^{m+1} &(n\mod 3=1)\\ 3^{m} &(n\mod 3=2)\\ \end{cases}$$

と求まります. ただし, $m=\left\lfloor\frac{n}{3}\right\rfloor$ とし, $a_{n}$ 直後の等号は$\mod{5}$ で考えています.

　さらに, $3$ の $5$ を法とした位数が $4$ であることを用いると, 以下が分かります.

• 数列 $a\pmod{5}$ は周期 $12$ である.
• $n=0,1,\dots,11$ の中に $a_{n}=1\pmod{5}$ なる $n$ は丁度 $3$ つあり, それら $n$ の $3$ での剰余は全て異なる.

　さらにさらに今回都合の良いことに, $a_3=a_4=1$ を愚直計算の際に既に知っており, 残りの $n=1\pmod{3}, a_{n}=1\pmod{5}$ を満たす $n$ に関しても, $3^{4}=1\pmod{5}$ から, $n=10$ がたちどころに得られます.

　 以上から $n=2,3,10\pmod{12}$ の時に $a_{n}=1\pmod{5}$ となるという結論を得られました.

～解説の解説～

　この節では上記の解説について少しだけ深掘りします.

前節の解法の拡張

まずは前節の 注 で触れた, $a_n=0$ となりうる場合でも同様の手法が使えるという点について説明します.

今回は, $$a_{0}=a_{1}=1, a_{n+2}=2a_{n}+3a_{n+1}\pmod{5}$$ で定まる数列の周期を考えることにしましょう.
この数列は, $(1,1,0,2,1,2,3,3,0,1,3,1,4,4,0,3,4,3,2,2,0,4,2,4,1,1,\dots)$ のように, $24$ 項で $1$ 周期となります.

前節では, 周期を求めたい数列の, 隣接項の比の値を数列 $b$ としていましたが, そうすると今回は $\frac{2}{0}$ が出てきてしまうので, 代わりに, $[1:1], [1:0], [0:2]$ のように比そのものを値として扱うことにします.
ただし, $[0:0]$ は考えないこととし, $[x:y]$ と $[x^\prime:y^\prime]$ は, $\begin{cases}x=\lambda x^\prime\pmod{5}\\y=\lambda y^\prime\pmod{5}\end{cases}$ をともに満たすような $\lambda=1,2,3,4$ が存在する時に, 同じ値を表すとします.
例えば, $\begin{cases}3=3\times 1\pmod{5}\\4=3\times 3\pmod{5}\end{cases}$ であるので, $[3:4]=[1:3]$ です.
このようにすることで, $[0:4]=[0:3]$ のように比の値では未定義となる場合をもカバーできます.

　この記号の元で, 改めて $b_{n}=[a_{n}:a_{n+1}]$ と定めた列を考えます.
$b_{n+1}=[a_{n+1}:a_{n+2}]=[a_{n+1}:2a_{n}+3a_{n+1}]$ です.
つまり, $f([x:y])=[y:2x+3y]$ として, $b_{n+1}=b_{n}$ です.

　ここで, [:] の取り扱い上で注意が必要な点に触れておきます.
今回定義した $f([x:y])=[y:2x+3y]$ ですが, ちゃんと定義出来ているのは自明な事ではありません.
例えば, $g([x:y])=[y:x^2]$ とした $g$ が定義できているか考えてみましょう.
$g([2:4])=[4:4]$ のように, 一見ちゃんと計算できるようです. しかし, $[2:4]=[1:2]$ とも表示できることを考えると, $g([2:4])=g([1:2])=[2:1]$ とも計算できてしまいます. $[4:4]\neq[2:1]$ であるので, これはあってはならないことです. つまり, $g$ は正しく定義出来ていません.
一方, $f([x:y])=[y:2x+3y]$ の場合, $[x:y]=[\lambda x:\lambda y]$ のような別の表示をしても, $f([\lambda x:\lambda y])=[\lambda y:\lambda (2x+3y)]=[y:2x+3y]$ のように, 一貫した値が得られます. (このようにちゃんと定義できていることを 一般に 'well-defined' と言います. )

　ともあれ, 今回の場合では $f([x:y])=[y:2x+3y]$ とすれば, $f(b_{n})=b_{n+1}$ となり, $b_{n+1}$ の値が $b_{n}$ からのみ計算できると分かりました.

　$[x:y]$ として取りうる値は(考えていない $[0:0]$ を除けば) $[0:1]$, $[1:0]$, $[1:1]$, $[1:2]$, $[1:3]$, $[1:4]$ の $6$ 種類のみです. よって, $b$ として取りうる値も高々 $6$ 通りのみであるので, 周期は $6$ 以下となります.
実際に, $b=(b_{0}=[1:1],[1:0],[0:1],[1:3],[1:2],[1:4],[1:1],\dots)$ と周期 $6$ となります.

　ここまでくれば, 後は先ほどの場合と同様に, $3a_{0}=a_{6}$ の計算と $b$ の周期から $a$ の周期及び各項の値が比較的簡単に求まります.

今回扱った概念について

　今回扱った $[x:y]$ のように, いくつかの値を組にして, 各成分が同じ定数倍で一致する時に等しい値とみなす空間を射影空間と言います. (通常全て $0$ の組は考えません)
今回は整数に $\mod 5$ 上の演算を入れた世界での射影空間 (記号で書くと, $\mathbb{F}_5\mathbb{P}$ や $\mathbb{P}(\mathbb{F}_5)$ と書かれがち) で数列の周期の発見のために導入しましたが, 競技数学の世界ではこの他に, 各成分が実数や複素数の場合などが射影幾何学と呼ばれるジャンルで現れるようです.