$f^{(p)}(x)=x$，求证$p\mid \abs{Y}$

abababa

设$f$是从非空有限集$X$到$X$的一个映射，并且$f^{(p)}(x)=x,x\in X$，其中$p$是素数，$f^{(p)}$表示函数的复合。集合$Y=\{x\in X:f(x)\neq x\}$，求证$p\mid \abs{Y}$，其中$\abs{Y}$表示$Y$中元素的数量。

业余的业余

和对称群有点相似，可能有些关联。

我们把 $X$ 一一映射到 $\{1,2,\cdots, n\}$. 其中 $n=|X|$.

从 $X$ 中去掉所有 $f(i)=i$ 的元素，得到的自然就是 $Y$, 从这里起，$Y$ 兼指成员从小到大的自然排列.

记 $m=|Y|$. 考虑排列 $P=\{f(Y_1), f(Y_2),\cdots,f(Y_m)\}$ 其中 $Y_i$ 是排列 $Y$ 的第 $i$的元素。我们把这个排列作为生成群的基础元素. 令 $Y=1_G$。这样生成的群 $G$ (算子为 类似对称群的复合)应该(不会证明）有 $m$ 个元素: $1_G,P,P^2,\cdots, P^{m-1}$. 由拉格朗日定理，有 $g^m=g^{|Y|}=1_G $ 对所有 $g\in G$.

由 $P$ 的定义，显然有 $P^p=\{f^{(p)}(Y_1), f^{(p)}(Y_2),\cdots,f^{(p)}(Y_m)\}=\{Y1,Y2,\cdots,Y_m\}=Y=1_G.$

$\therefore p \mid |Y|$.

abababa

回复 2# 业余的业余

完全看不懂啊。
网友给发了一个证明，但我也没全看懂，就是根据$j$的特性可知$j-i=j$那里，还有下面的根据$j$的特性可知$r=0$这两个地方。如果假设这两个都是对的，后面的还能看懂。

业余的业余

回复 3# abababa

看了前面的几行，思维方式和群论的思维方式很相近。我也是刚刚涉猎一点群论，第一章的水平吧，ku版理解肯定比我透彻。

$B(x)$ 没有相同元素是显然的，这和mod n的残余集$\{0，1，2，\cdots, n-1\}$ 中没有相同元素是类似的。只是把乘法理解为加法而已。其证明的方法也是类似的。

假设有 $0\le i<j\le p-1$ 使得 $f^{(i)}(x)=f^{(j)}(x)$ 那么对等式两边再复合 $p-j$ 次，有 $f^{(p-j+i)}(x)=f^{(p)}(x)=x$.  容易知道，当且仅当 $p-j+i=0$ 或 $p-j+i \mid p$ 时 才可能前式成立。而这两种情况都不可能。故 $B(x)$ 无相同元素。

这就像周期函数，周期必须使最小正周期的倍数。因这里的 $p$ 是素数，它只能是 $1$ 的倍数。排除掉最小正周期为 $1$ 的情形，那么我们的周期 $p$ 就是最小正周期了。

abababa

回复 4# 业余的业余

谢谢，这个思路证明的我看懂了，我重新把3楼圈1的那部分按这个思路写一下：
假设$B(x)$中有相同的元素，不妨设$f^{(i)}(x)=f^{(j)}(x)$，其中$0\le i< j\le p-1$，定义$f^{(0)}(x) =x, f^{(1)}(x)=f(x)$。两边复合$p-j$次有
\[f^{(p-j+i)}(x)=f^{(p)}(x)=x\]
设$k$是使得$f^{(k)}(x)=x$成立的最小正整数，由于$f^{(p)}(x)=x$而$f^{(1)}(x)\neq x$，所以$1<k\le p$。设$p=qk+r, 0\le r <k$，于是
\[x=f^{(p)}(x)=f^{(qk+r)}(x)=f^{(r)}(f^{(qk)}(x))=f^{(r)}(x)\]
若$r\neq 0$，则存在比$k$更小的正整数$r$使得$f^{(r)}(x)=x$，这与$k$的选择矛盾，所以$r=0$，于是$p=qk$，但$1< k\le p$而$p$是素数，所以$q=1, k=p$，所以使得$f^{(k)}(x)=x$成立的最小正整数$k$就是$p$。因为$0<p-j+i<p$，所以$p-j+i$不能使$f^{(p-j+i)}(x)=x$成立，这与$f^{(p-j+i)}(x)=f^{(p)}(x)=x$矛盾，所以$B(x)$中的元素互不相同。