AMC day4 の記事の補題の証明

概要

この記事はAMC2022 (Advent Math Calendar2022) というイベントに筆者が参加するにあたって書いた次の記事( https://mathlog.info/articles/3735 ) に登場する補題の証明を記したものである
この記事自体は正直つまらないのでブラウザバック推奨です

補題の証明

補題0,3

非負整数$a,b$について $f^a(f^b(x))=f^{a+b}(x)$

証明

定義より明らか

補題1,1

非負整数$k,l,m$について、$f^m(x)=x\Rightarrow f^{km+l}(x)=f^l(x)$

証明

補題0,3より明らか

補題1,2

非負整数$i$について、
$f^i(\alpha)=\alpha\Leftrightarrow i\equiv 0\hspace{6pt}(mod\hspace{4pt}m)$

証明

$\Leftarrow i=km$とおけるので補題1,1を適用して$f^i(\alpha)=f^0(\alpha)=\alpha$
$\Rightarrow i\hspace{4pt}mod\hspace{4pt}m=n$とすると$f^i(\alpha)=f^n(\alpha)=\alpha\hspace{4pt}(0\leq n< m)$となる
$cyc_m(f)$の定義より、このような$n$は$0$しかないので$i\equiv 0\hspace{6pt}(mod\hspace{4pt}m)$

補題2,1

$cyc_m(f,\alpha)=cyc_m(f,\beta)\Leftrightarrow\beta=f^k(\alpha)$なる非負整数$k$が存在する

証明

$\Rightarrow$明らかに$\beta\in cyc_m(f,\beta)$なので$\beta\in cyc_m(f,\alpha)$
$cyc_m(f,\alpha)$の定義より$\beta=f^k(\alpha)$なる非負整数$k$が存在する
$\Leftarrow$仮定より$f^l(\beta)=f^{k+l}(\alpha)$なので$cyc_m(f,\alpha)\supset cyc_m(f,\beta)$
また、$k\hspace{4pt}mod\hspace{4pt}m=n$とすると$f^{m-n}(\beta)=f^{k+m-n}(\alpha)=\alpha$より、同様にして$cyc_m(f,\alpha)\subset cyc_m(f,\beta)$
よって$cyc_m(f,\alpha)=cyc_m(f,\beta)$

補題2,3

$cyc_m(f,\alpha)=${$f^k(\alpha)$|$k$は$m$未満の非負整数$\hspace{0pt}$}、特に$|cyc_m(f,\alpha)|=m$である

証明

補題1,1より明らか

補題2,4

$f^k(\alpha)\in cyc_m(f)$、特に$cyc_m(f,\alpha)\subset cyc_m(f)$である

証明

$f^n(f^k(\alpha))=f^{n+k}(\alpha)=f^k(\alpha)\Leftrightarrow n+k\equiv k\hspace{4pt}(mod\hspace{4pt}m)\Leftrightarrow n\equiv 0\hspace{4pt}(mod\hspace{4pt}m)$より
$f^m(f^k(\alpha))=f^k(\alpha)$かつ$m$未満のすべての正整数$n$について$f^n(f^k(\alpha))\neq f^k(\alpha)$
よって$f^k(\alpha)\in cyc_m(f)$、また定義より$cyc_m(f,\alpha)\subset cyc_m(f)$