フィボナッチ数列の研究まとめ 2
体験記の合間にフィボナッチ数列を少しまとめます(体験記はもう少しお待ちを). 初めに重要な公式をいくつか復習しましょう. 余談ですが, フィボナッチ数列全体の集合を $\fib$ とかしてしまったので有限体の議論が見づらくなりそうで困っています...
- 数2Bまでの知識
- 集合, 写像についての記法, 用語が一通りわかる
- 群論, 環論についての基本的な事項がわかる
また, 前回の記事 を先に読むことを推奨します.
前回のまとめ
数列$\{F_n\}^\infty_{n=-\infty}$を$F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n$$(n\in\Z)$で定め, フィボナッチ数列と呼ぶ. この集合に登場する整数をフィボナッチ数と呼ぶ.
- 正のフィボナッチ数全体の集合を$\fib$とあらわす
- フィボナッチ数全体の集合を$\Fib$とあらわす
任意の$n,m\in\Z$に対し$F_{n+m+1}=F_nF_m+F_{n+1}F_{m+1}$が成立する.
任意の$n,m\in\Z$に対し$F_{n+m}F_{n-m}=F_n^2-(-1)^{n+m}F_m^2$
$\fib\rightarrow\fib_{\ge2},\fib_{\ge2}\rightarrow\fib$への関数をそれぞれ
$$n\mapsto\frac{n+\sqrt{5n^2\pm4}}{2},n\mapsto\frac{-n+\sqrt{5n^2\pm4}}{2}$$
で定め, それぞれ$\suc$, $\pre$とする. これらのwell-defined性, 互いに逆写像(従っていずれも全単射)であることは前回の記事を参照.
周期関数
今回のメインの話題になる, フィボナッチ数をある整数で割った余りがどれくらいの周期で現れるかという関数, 周期関数を二つ定義します.
正整数$n$に対して関数$l, L:\Z_{>0}\rightarrow\Z_{>0}$を以下のように定める:
$$l(n)=\min\{k\in\Z_{>0}\mid F_k\equiv0\pmod n\}$$
$$L(n)=\min\{k\in\Z_{>0}\mid F_k\equiv0\pmod n\land F_{k+1}\equiv1\pmod n\}$$
イメージとしては小文字のほうは$0$がいくつ間隔で現れるか, 大文字のほうは余りがいくつ周期か, という感じです. (このイメージは実際に成立します)
ところで, 実際にこのような関数は存在するのでしょうか? かなり自明ではありますが, 一応証明しておきます.
全ての$n\in\Z_{>0}$に対しある正整数$k$が存在し, $F_k\equiv0\pmod n\land F_{k+1}\equiv1\pmod n$が成立する.
正整数$n$に対して$\Z/n\Z$を剰余環とし, 剰余類$[k]$を単に$k$と書き, $\Z/n\Z$の元と同一視する. 以下$\Z/n\Z$で考える. 正整数$i$に対し順序対$(F_i,F_{i+1})\in(\Z/n\Z)^2$として取り得るものは高々有限である. すなわち, ある$a< b$なる正整数の組$(a,b)$が存在し$(F_a,F_{a+1})=(F_b,F_{b+1})$となる. $(F_a,F_{a+1})$が決まると帰納的に$\{F_n\}$が一意に定まることに留意すると, $(F_{a-a},F_{a+1-a})=(F_{b-a},F_{b+1-a})$が成立する. このとき$(F_{b-a},F_{b+1-a})=(0,1)$となり, $b-a>0$より題意は示された.
あまりの周期性についてもほとんど同様に示せるのでここでは省略します.
また, 周期性の系として$l(n)|L(n)$もわかりますね.
少しこの関数の観察をしてみましょう.
| $n$ | $l(n)$ | $L(n)$ | $L(n)/l(n)$ |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 3 | 3 | 1 |
| 3 | 4 | 8 | 2 |
| 4 | 6 | 12 | 2 |
| 5 | 5 | 20 | 4 |
| 6 | 12 | 24 | 2 |
| 7 | 8 | 16 | 2 |
| 8 | 6 | 12 | 2 |
| 9 | 12 | 24 | 2 |
| 10 | 15 | 60 | 4 |
予想できることとしては$L(n)/l(n)$が$2$べきになることなどがあると思います. あとは$n$が素数になるときに$L(n)$の値がある程度絞れたりとか...
実は結論から言いますと以下の命題が成立します.
任意の$n\in\Z_{\ge1}$に対して$L(n)/l(n)=1, 2, 4$
これを示していきましょう!
主定理の証明
まず, $L(n)/l(n)$の言い換えを行います.
$m$を$2$以上の整数とする. $\Z/m\Z$で$F_{nl(m)+1}$として取り得る値は積について巡回群の構造をなす.その群を$G_{Fi}(m)$と定める.
加法定理より
$$F_{nl(m)+1}=F_{(n-1)l(m)}F_{l(m)}+F_{(n-1)l(m)+1}F_{l(m)+1}=F_{(n-1)l(m)+1}F_{l(m)+1}$$
が成立し, $F_{1}=1$であるのでこれらは$\langle F_{l(m)+1}\rangle$と記述でき, 特に巡回群である.
$m$を$2$以上の自然数とする. $\#G_{Fi}(m)=L(m)/l(m)$が成立する.
$G_{Fi}(m)$は巡回群であるので, $\#G_{Fi}(m)$の値は生成元$F_{l(m)-1}$の位数と等しい. 上の補題の証明より, 非負整数$n$に対して$F_{nl(m)+1}=F_{l(m)+1}^n$が帰納的にわかる. よって, 位数の定義より$F_{nl(m)+1}=1$となる最小の正整数$n$は$\#G_{Fi}(m)$であり, $L(m)$の定義と$0$の出現の周期性より$\#G_{Fi}(m)=L(m)/l(m)$.
従って, 結局$G_{Fi}(m)$の群構造を調べればよいことになります(そもそもが巡回群なのでかなり単純な構造になるが).
今, $F_{l(m)+1}$として表せる項は$\Z/m\Z$上で$0$の"後"に現れる項です. このことから, 剰余環上において後者関数で$0$を飛ばすという発想に行きつきます. 実際には, はじめその方法で行ったのですが平方根や除算の扱いが難しく若干方針を変えました. 中国剰余定理の適用を考えればまず素べきについて考えればよさそうです.
奇素数$p$, 正の整数$n$に対して$G_{Fi}(p^n)\subset C_4$が成立する.
後者関数導出の際の$F_{x}^2+F_xF_{x+1}-F_{x+1}^2-(-1)^{x}=0$を考えることで($x=ml(p^n)$を代入)$F_{ml(p^n)+1}=\sqrt{\pm1}$を考えればよい. $\sqrt{1}$について,
$$k^2=1\Leftrightarrow(k-1)(k+1)=0\Leftrightarrow k=1,-1$$
が成立する. (ただし最後の$\Leftrightarrow$は法が素べきであるため). さらに,$\alpha^2=-1$なる$\alpha\in\Z/p^n\Z$の存在を仮定すると, $\alpha\notin p\Z/p^n\Z$ であることから
$$k^2=-1\Leftrightarrow(k-\alpha)(k+\alpha)=0\Leftrightarrow k=\alpha,-\alpha$$
が成立($\alpha\neq-\alpha$). $\alpha$が存在するとき, 上の議論より, $\{\sqrt{\pm1}\}$は位数$4$の群になり,特に
$\langle\alpha\rangle \cong C_4$に同型. 存在しないとき,
$\{\sqrt{\pm1}\}=\{\sqrt{1}\}$となり, 上の議論よりこれは$C_2(\subset C_4)$に同型.
$G_{Fi}(p^n)$はこれの部分群なので$G_{Fi}(p^n)\subset C_4$.
$2$べきの場合は少し違う議論が必要ですが, 大筋は変わりません.
正の整数$n$に対して$G_{Fi}(2^n)\subset C_2$が成立する.
$n=1, 2$のとき明らかなので以下$n\ge3$とする. 先の補題と同様に$F_{ml(2^n)+1}=\sqrt{\pm1}$を考えればよい. $\sqrt{1}$について,
$$k^2=1\Leftrightarrow(k-1)(k+1)=0\Leftrightarrow k=1,-1, 2^{n-1}+1, 2^{n-1}-1$$
が成立する. ($k+1, k-1$のちょうど一方のみが$4\Z/2^n\Z$に属することを用いた). また, $\mod4$で考えることで$k^2=-1$の解は存在しない.
よって,
$$\sqrt{\pm1}=1,-1, 2^{n-1}+1, 2^{n-1}-1$$
となり, これには$C_2\times C_2$に同型な構造が入る. $G_{Fi}(2^n)$はこれの部分群かつ巡回群なので位数を考えれば$G_{Fi}(2^n)\subset C_2$が従う.
これらより, 素べきの場合には$G_{Fi}(m)$が$E, C_2, C_4$のいずれかになることが言えましたね. あとはすぐです.
任意の$n\in\Z_{\ge1}$に対して$L(n)/l(n)=1, 2, 4$
$L(1)/l(1)=1$より$n=1$で成立.以下$n\ge2$とする.
中国剰余定理より互いに素である自然数$n, m\ge2$に対して$\Z/n\Z\times\Z/m\Z\cong\Z/nm\Z$である. この同型写像を$\varphi:\Z/n\Z\times\Z/m\Z\rightarrow\Z/nm\Z$とおく. 今, 積についてのモノイドとして$G_{Fi}(n)\subset\Z/n\Z,G_{Fi}(m)\subset\Z/m\Z$が成立している. さらに, $G_{Fi}$の定義より, $a\in\Z/nm\Z$に対し, $a\in G_{Fi}(nm)$であるとき$\varphi^{-1}(a)\in G_{Fi}(n)\times G_{Fi}(m)$が成立する. よって, $G_{Fi}(nm)\subseteq\varphi(G_{Fi}(n)\times G_{Fi}(m))$.
今, $G_{Fi}(n)\times G_{Fi}(m)$は成分ごとの演算で群になるので, $\varphi(G_{Fi}(n)\times G_{Fi}(m))$も群になり, これは$G_{Fi}(n)\times G_{Fi}(m)$と同型.
$(a,b)\in G_{Fi}(n)\times G_{Fi}(m)$をとったとき, $(a,b)$の位数は$a$の位数と$b$の位数の最小公倍数となる. 特にいずれも$1,2,4$のいずれかの場合, $(a,b)$の位数も$1,2,4$のいずれかになる. よって, 任意の$c\in G_{Fi}(nm)$に対して位数は$1,2,4$のいずれか. 補題5より$G_{Fi}(nm)$は巡回群なので$\#G_{Fi}(nm)=1,2,4$.
今, 全ての素べき$p^n$について$\#G_{Fi}(p^n)=1,2,4$が示されているので, 帰納的に任意の$n$に対して$\#G_{Fi}(n)=1,2,4$となる. これと補題6より主張が従う.
まとめ
フィボナッチ数と群論, 面白くないですか?僕はこの方法に気づいたとき結構感動しました. 次回は$L(n)/l(n)$の具体的な値について考えていきます.
余談ですが, りんさん(@.rin_math28)の固ツイの問題の解答に近い内容だったのでそれに沿って記事を書いてみました. また次回!
この記事を高評価した人
この記事に送られたバッジ
投稿者
