写像方程式の解は存在するのか？
予想(否定的に解決)
任意の集合$ Xと写像$ f:X\to X、整数$ n\geq 1に対し方程式
$ \varphi^n(x) = f(x)\hspace{1em} \forall x\in X
の解$ \varphi:X\to Xが存在する。
(反例)
$ X = \{1, 2\},\ f(1) = 2,\ f(2)=1,\ n=2とする。
このとき$ \mathrm{I}_2(X) = \{\varphi^2 \mid \varphi:X\to X\} = \{ 1_X, f\mapsto 1, x\mapsto 2 \}\not\ni f
命題
$ mを$ 2以上の整数とし、$ X=\{0, 1,\dots, m-1\}、$ f(x) = x+1\mod mとする。このとき、方程式
$ \varphi^m(x) = f(x)\hspace{1em} \forall x\in X
の解$ \varphi:X\to Xは存在しない。
(証明)
$ \varphiを与えられた方程式の解とする。$ fは全単射であるから$ \varphiもそうである。$ fは周期が$ m未満の周期点を持たないから$ \varphiもそうである。
$ \because $ pを周期が$ k< mの周期点とする。このとき$ \varphi^m(p) = p+1\mod 1となるため$ p+1は$ pの軌道に含まれる。よって$ p+1も周期が$ kの周期点である。同じ理屈で$ p+2, p+3,\dots,p+m-1 \mod mも$ pの軌道に含まれる。一方これは$ pの軌道に$ k個の元しかないことに矛盾する。
ゆえに$ x, \varphi(x),\varphi^2(x),\dots,\varphi^{m-1}(x)は全て異なる。
$ \becauseもし$ \varphi^i(x)=\varphi^j(x)ならば$ \varphi^i(x)及び$ \varphi^j(x)は周期$ |i-j|<mの周期点である。
よって$ \varphiの全単射性から$ \varphi(x),\varphi^2(x),\dots,\varphi^m(x)全て異なる。よって$ \varphi^m(x)=xであり$ \varphi^m(x)=f(x)=x+1\mod mに矛盾。$ \square
注意 上の命題の$ fを「周期$ m未満の周期点を持たない全単射な写像」に置き換えても良い
予想
$ Xを濃度が$ m\geq2の有限集合とする。このとき、$ m未満の整数$ n\geq 1に対し
$ \varphi^n(x) = f(x)\hspace{1em}\forall x\in X
の解$ \varphi:X\to Xが存在する。
そうでない場合まず、$ X_0^0 = X\setminus\{0, f(0)\}とする。そして$ \varphi(0)を$ X_0^0の中で最小の数として定める。次に$ X_0^1=X_0^0\setminus\{\varphi(0), f(\varphi(0))\}とし、$ \varphi^2(0)を$ X_0^1の中で最小の数として定める。同様にして$ \varphi^{n-1}(0)まで定義する。そして$ \varphi^n(0)=f(0)として定める。
予想
$ Xを無限集合、$ f:X\to Xを写像、$ n\geq 1を整数とする。このとき、$ fが$ nを割り切る周期$ n未満の周期点を持たず、各$ k\geq nに対し、$ \mathrm{Per}_k(f)の濃度が$ knの倍数であるか無限濃度であり、全てのサイクルの尾の長さが高々$ 1とする。このとき選択公理の下で
$ \varphi^n(x) = f(x)\hspace{1em} \forall x\in X
の解$ \varphi:X\to Xが存在する。
証明(考え中)
$ n=1の時は$ \varphi(x)=f(x)とすれば良い。
そうでない場合、$ Xから$ n-1個の元$ x_1,\dots,x_{n-1}で$ \forall i\leq n-1,\ x_i\not\in\{f(x_0),x_1,f(x_1),x_2,\dots,f(x_{i-2}),x_{i-2},f(x_{i-1})\}となるようなものを選べる。そして$ \varphi(x_i)=x_{i+1}\hspace{1em}(1\leq i\leq n-2)とする。
そして$ \varphi(x_{n-1})=f(x_0)とする。さらに$ \varphi(f(x_0)) = f(x_1),\ \varphi(f(x_1)) = f(x_2),\ \dots,\ \varphi(f(x_{n-2})) = f(x_{n-1})と定める。
$ fに周期点が存在しない場合は$ f(x_0),\dots,f(x_{n-1})に対して同様の方法で$ \varphi(f(f(x_0)))の値を定める。これを$ Xの全ての元に対して言及するまで行う。
$ fに周期点がある場合はやばすぎる
系
$ f:X\to Xの各周期の周期点の数が無限の場合、任意の正整数$ n,mに対して
$ \varphi^n(x)=\varphi^m(f(x))
の解$ \varphi:X\to Xが存在する。
メモ
選択公理の仮定は必要だと思う
てか誰かがもう証明か反例あげてるんじゃね？
一意性は成り立たない
$ X=\{0, 1\},\ f=1_X, n=2に対し$ \varphi(x)=xおよび$ \phi(x)=1-xは解となる