フィボナッチ数列の研究まとめ4
フィボナッチ数列の研究まとめの続きです. フィボナッチ数列を群論の視点で扱うことで素数で割った余りの周期がわかるという話を書いていきます.
- 数2Bまでの知識
- 集合, 写像についての記法, 用語が一通りわかる
- 群論についてある程度(正規部分群, ラグランジュの定理など. 赤雪江2章くらいまで)
- 線形代数を少し使う
また, 前回の記事 を先に読むことを推奨します.
前回までのまとめ
数列$\{F_n\}^\infty_{n=-\infty}$を$F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n$$(n\in\Z)$で定め, フィボナッチ数列と呼ぶ. この集合に登場する整数をフィボナッチ数と呼ぶ.
任意の$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$が成立する.
最近気づいたのですが, 加法定理が沿え字の加法について言及しているのに乗法定理はフィボナッチ数自体の乗法について言及していて一貫性がないですね. まあ添え字の整数倍の計算に便利なのでいいでしょう(適当).
正整数$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\}$$
これらはそれぞれ, フィボナッチ数を$n$で割った余りを考えたときに何個周期で$0$が出てくるか, 何個周期で余りが循環するか, ということを表しています( まとめ2 参照).
任意の正整数$n$に対して$L(n)/l(n)$の値は$1,2,4$のいずれかになる. 特に$p$を$2, 5$以外の素数としたとき$L(p)/l(p)$の値は以下の表で与えられる.
![!FORMULA[19][-498813063][0]の値](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2F20221219202526.jpg?alt=media)
$L(p)/l(p)$の値
フィボナッチ数を群論的に捉えたい!
群の定義
$p$を素数とする.
$(\Z/p\Z)^2$に以下のような演算を入れると可換モノイド(アーベル群の公理から逆元の存在を除いたもの)になる.
$$(x, y)\cdot(z, w):=(xw+yz-xz, xz+yw)$$
閉じていること, 可換性
自明.
単位元の存在
$(0, 1)$が単位元である.
結合性
$((a, b)\cdot(c, d))\cdot(e, f)=(a, b)\cdot((c, d)\cdot(e, f))$
$=((adf+bcf+bde)-(bce+ade+acf)+2ace, (bce+ade+acf)-ace+bdf)$
よりok.
また, 以下の補題よりここから群を構成できます.
$M$をモノイドとする. このとき, $M$の加逆元全体は群構造を持つ.
結合性, 単位元の存在は明らか.
閉じていることは$x, y\in M$が可逆のとき$xy\cdot(y^{-1}x^{-1})=e$なのでok.
可逆性は$x\in M$が可逆のとき$x$は$x^{-1}$の逆元なのでok.
定義3のモノイドに補題を適用して構成された群を$p$-フィボナッチ群と呼ぶことにし, $\cF_p$と書く.
$(0, 0)\notin\cF_p$です. (前々回思い付きで$G_{Fi}(p)$とか適当に記号作ってて発狂しそう. あとで別の表記に直します. )
$p$-フィボナッチ群の性質
さて, 前の章でいきなり非自明な演算を出されていきなり結合性が成り立つことが示されいきなりフィボナッチ数の名を借りて命名され意味が分からないと思うのでこれがフィボナッチ数列とどう関係あるか書きます. 以下$\Z/p\Z$の元$\overline{x}$を単に$x$と書きます. また, 以下$(\Z/p\Z)^2$の演算$\cdot$は特に断りのない限り$p$-フィボナッチ群での演算です.
$n, m\in\Z$に対して
$$(F_n, F_{n+1})\cdot(F_m, F_{m+1})=(F_{n+m}, F_{n+m+1})$$
である.
加法定理を使って計算していけば示せる(詳細略).
$(F_n, F_{n+1})$として取り得るもの全体は$\cF_p$の巡回部分群になる. さらに位数は$L(p)$である.
命題5より$\langle(F_1, F_2)\rangle=\langle(1, 1)\rangle$と一致する. 位数は$L(p)$の定義より明らか.
$|\cF_p|= \left\{
\begin{array}{ll}
p^2-2p+1 & p\equiv1, 4\pmod5 \\
p^2-1 & p\equiv2, 3\pmod5\\
p^2-p & p=5
\end{array}
\right.$
である.
$|(\Z/p\Z)^2|=p^2$なのでこの中で非可逆元の個数を数え上げればよい.
$(0, 1)=(x, y)\cdot(z, w):=(xw+yz-xz, xz+yw)$において$(x, y)$を固定し逆元の存在を考える.
$\begin{pmatrix}
y-x & x \\
x & y
\end{pmatrix}
\begin{pmatrix}
z \\
y
\end{pmatrix}
=
\begin{pmatrix}
0 \\
1
\end{pmatrix}$
となり
$\begin{vmatrix}
y-x & x \\
x & y
\end{vmatrix}=y^2-xy-x^2$であるので, これが$\Z/p\Z$で$0$になることと逆元を持たないことは同値である($\Z/p\Z$が体になることから実数のように行列演算ができる). $p$が$5$でない奇素数のとき, $x\neq0$を固定すると
$y=\dfrac{x}2 (1\pm\sqrt5)$となることから, $p\equiv1, 4\pmod5$のとき$2$つずつ非可逆元が存在し, $p\equiv2, 3\pmod5$のときは存在せず, $p=5$のときは$1$つずつ非可逆元が存在する(感覚的な書き方をしているが厳密には平方完成して平方剰余を考えればok). $x=0$のときはいずれの場合も$y=0$のみ逆元を持たない. さらに, $p=2$のときも逆元は持たないことを併せて主張は示された.
これらの話からなんとなく周期を考えられそうなことが分かると思います.
また, 実は$p\equiv2, 3\pmod5$のときは$(0,0)$を加えて成分ごとの加法を入れると体になり, $x$と$(0, x)$を同一視することによって$\Z/p\Z$代数と見ることができます. この演算は成分ごとに$(\Z/p\Z)^\times$の元倍していることと同じ演算になっています.
周期を考える
以下$p$を$5$でない素数とします.
前々回の$G_{Fi}(p)$, すなわち$\Z/p\Z$上のフィボナッチ数列における$0$の後に登場しうる元に群構造を入れたものを$\cE_p$と書くことにする.
任意の$x, y\in (\Z/p\Z)^\times$について$x\langle(1, 1)\rangle$と$y\langle(1, 1)\rangle$が共通の元を持つときそれらは一致し, かつ$x\cE_p=y\cE_p$が必要十分である.
一致することは一般の群の剰余類の議論よりok.
十分性はうまく整数$k$をとり$((1, 1)^{l(p)})^k$を掛けることで示される.
必要性は第一成分が$0$の元であるという性質は$(0, x)$をかける操作によって保たれることからわかる.
$(\Z/p\Z)^\times\langle(1, 1)\rangle$は$\cF_p$の部分群であり, これを$\cH_p$とおく.
一般に$H_1, H_2$をアーベル群$G$の部分群としたとき$H_1\cdot H_2$は$G$の部分群になるのでよい.
$p=13$でのイメージ図です.
![!FORMULA[105][-286450272][0]のイメージ](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2F20221219234203.png?alt=media)
$\cF_{13}$のイメージ
$p\equiv1, 4\pmod5$のとき$l(p)|p-1, L(p)|p-1$
$p\equiv2, 3\pmod5$のとき$l(p)|p+1, L(p)|2(p+1)$
$p\equiv1, 4\pmod5$のとき
今回の内容でも$p\equiv2, 3\pmod5$のときのようにできる. が, この場合は前回の命題10みたいに$\Z/p\Z$で$\phi$をとって
$$F_n=\frac1{\sqrt5}(\phi^n-(-1)^n\phi^{-n})$$
として, Fermatの小定理から$F_{p-1}=0, F_{p}=1$とすることもできる.
$p\equiv2, 3\pmod5$のとき
$|\cH_p|=L(p)\cdot|(\Z/p\Z)^\times/\cE_p|=(p-1)l(p)$である. $\cH_p\subset\cF_p$とラグランジュの定理, 命題7より $|\cH_p|$は$p^2-1$の約数, 従って$l(p)$は$p+1$の約数. また, まとめ2の主定理より$L(p)/l(p)=1, 2,4$となる. $L(p)/l(p)=4$のとき前回の補題7より$l(p)$は奇数, 特に$l(p)|(p+1)/2$であるので, いずれにしても$L(p)|2(p+1)$である.
おわりに
群論の視点で考えると周期が分かるというお話でした！急いで書いたのでミスがあったら教えてください. あと$p\equiv2, 3\pmod5$のときに標数$p$位数$p^2$の有限体になることからもう少し色々言えそうな気もしています. 今後の課題です.
フィボナッチ数の研究まとめもあと$3$回くらいでひと段落すると思います. 最後まで読んでいただきありがとうございます！次回はもう少し競技数学っぽい視点で書こうと思っています.
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
