不动点理论

分析观点下的不动点

压缩映射是不动点和 Lipschitz 条件的基础。 在完备的度量空间上，若 $f([a,b])\subset [a,b]$ 并存在 $0<k<1$，则成立 $|f(x)-f(y)|\le k|x-y|$。 即 $d(Tx,Ty)\le d(x,y)$。

Picard-Banach 不动点定理

Banach 空间 $X$ 到 $X$ 之间的映射 $f$ 如果是一个压缩映射，即存在一个严格小于 1 的正实数 $q$，使得 $d\left(f\left(x_1\right),f\left(x_2\right)\right)\le qd\left(x_1,x_2\right),\forall x_1,x_2\in X$ 那么该映射在度量空间 $X$ 上存在一个全局吸引的不动点，即任意 $x_1\in X$ 经过迭代 $x_{n+1}=f(x_n)$ 其极限收敛到 $f$ 在 $X$ 上的唯一不动点。

具体来说：

如果考虑 Cauchy 判别去判断收敛性，那么对于任意的正整数 $k$ 考虑是否有 $d(x_{n+k},x_n)\to 0$ 与 $k$ 无关：

这里完备性主要用在：要在 $X$ 当中存在不动点 $x\in X$，就需要 $x_n\in X,\forall n\in \mathbb{N}$ 其极限要存在于 $X$ 当中。

问题1

数列 $\{b_n\}$ 由 $b_1=1$ 和 $b_{n+1}=1+\frac{1}{b_n}$ 生成，求收敛极限。

尝试构造 $|f(x)-f(y)|\le k|x-y|$，有 $|f(x)-f(y)|=\left|\frac{1}{x}-\frac{1}{y}\right|$。 注意到 $f([1.5,2])\subset [1.5,2]$。 则

我们称 $b_n$ 从第二项进入 $[1.5,2]$，因此由压缩映射保证其收敛性。 再由不动点定理得极限为 $\frac{1+\sqrt{5}}{2}$。

问题2

数列 $\{b_n\}$ 由 $b_0=\frac{\sqrt{2}}{2}$ 和 $b_{n+1}=\frac{1}{2b_n}+\frac{1}{2}{b}_n$ 生成，求收敛极限。

核心想法

为确定范围，假设存在一个上下界 $a,b$，则 $a=\frac{1}{2}(a+\frac{1}{b})\le b_n\le \frac{1}{2}(b+\frac{1}{a})=b$。 得 $ab=1$，又 $b_0=\frac{\sqrt{2}}{2}$，所以取 $\sqrt{2}$。

当 $n=0$ 时 $b_0=\frac{\sqrt{2}}{2}$ 成立。 假设 $\frac{\sqrt{2}}{2}\le b_n\le \sqrt{2}$。 则

又

则满足 $f([\frac{\sqrt{2}}{2},\sqrt{2}])\subset [\frac{\sqrt{2}}{2},\sqrt{2}]$。 导数范围：

由 $|f(x)-f(y)|=|f^{\prime }(\xi )||x-y|\le \frac{1}{2}|x-y|$， 则称其收敛由压缩映射保证，又由不动点得极限为 1。

代数观点下的不动点

1. 从一个计数问题开始

问题1

假设有一条项链，一共有 8 颗珠子组成，每颗珠子可以有四种不同的涂色方式，请问整条项链一共有多少种着色方式?

首先第一反应，因为一共有 8 颗珠子，并且每种涂色有四种，那么一共有 $4^8$ 种组合方式？可是这样是错误的，因为按照常理思考，一串珠子，假设我顺时针拨动它，那么它应该还是同一种着色。

因此我们实在没有理由认为，把一串珠子顺时针旋转后得到的是不同的着色，但是 $4^8$ 种组合里面却是包含了这样的组合。

再者，我们同样可以考虑把这串珠子反转过来，也就是沿着某一条对称轴，做对称，这样得到的结果按道理也应该算是同一种着色。

因此我们不难发现，其实，在 $4^8$ 种组合里面有许多这样的应该归类为同一种着色的组合，也就是一个等价类。那么怎样定义这个等价类呢？

首先要搞清楚，怎样的着色应该算是同一种着色。按照分析，我们可以认为，如果一串（可以理解为正多边形的）着色的珠子 $x$，可以通过某一种旋转或者对称反射的方式（或者他们的复合），转化为 $y$，那么称着色 $x$ 与着色 $y$ 等价，记为 $x\sim y$。

那么一串珠子一共有哪些对称和反射呢？自然是这个几何图形的对称群决定的。问题中的 8 个珠子组成的项链，可以等价为一个正 8 边形，因此对称群自然是八阶 Dihedral 群 $D_8$。

这个道理可以归结为：

如果存在 $g\in D_8$ 以及这串珠子的两种着色 $x,y$ 使得 $g\cdot x=y$，那么称 $x,y$ 是两种等价的着色。定义

这里 $a=(c_1,\dots ,c_8)$ 表示这串珠子每个点的着色的情况，例如问题中说珠子一共有四种着色方式，不失一般性可以假设 $c_i\in \{■,■,■,■\}$。那么按照这种记号，一种特定的珠子着色可以写为

于是 $O_a$ 这个集合实际上就表示与 $a$ 在 $D_8$ 的作用（旋转和反射的各种复合）下等价的着色。于是我们最终需要回答的就是，在集合

当中有多少个不同的集合 $O_x$，也就是说我们需要知道集合 $\{O_x:x\in E\}$ 的大小。

2. 群论的一些语言

以上内容我们将之翻译为群论的语言。

• 群的作用: 我们对集合 $X$，也就是所有着色后的项链的集合进行诸如旋转，反射以及他们的复合等等操作的时候，实际上定义了某种 $f:G\times X\to X$。比如在刚才的例子当中，我们给一种来自于 $D_8$ 的元素 $r$，表示顺时针旋转 $\frac{2\pi }{8}$，然后选某一个着色的项链的集合当中的元素 $a=(■,■,\dots )$，那么旋转后的项链就会变成 $b=(■,■,\dots )$。所以实际上我们通过某种映射完成了 $(g,a)\mapsto b$ 的这样一个映射。不过这样的映射如果用 $f$ 来表示有点麻烦，我们会经常使用 $\cdot :G\times X\to X$ 也就是类比乘法一样来表示。按照这样的记号，那么可以把这里的例子写为 $g\cdot a=b$。

• 轨道: 简而言之就是让群里面所有元素作用在同一个元素上所形成的一个集合。群 $G$ 作用在集合 $X$ 下的某元素 $x$ 的轨道可以表示为

  $${\text{Orb}}_x=G\cdot x:=\{g\cdot x:g\in G\}$$

  这个术语的名称是类比于物理当中物体运动的轨迹。把集合当中某个固定的点 $x$ 想象成空间当中的点，然后群当中的元素相当于是推动这个点运动的力，然后由于这样的力的推动点开始运动，这些运动留下的轨迹 $g\cdot x$ 便是轨道。

所以一开始的问题可以用术语阐述为:

问题2：问题的抽象化

$D_8$ 作用在集合 $E=\{x=(c_1,\dots ,c_8):c_i\in \{■,■,■,■\}\}$ 可以形成多少个不同的轨道?

不过轨道的数量直接去数是不容易的。下面是按照定义去数集合 $X$ 在群 $G$ 作用下轨道的数量的流程:

1. 任选一个固定的 $x_1\in X$ 然后算出 $O_{x_1}$。
2. 在集合 $X$ 当中排除第一条轨道，得到 $X_1$，然后从此集合当中再找一个固定的元素 $x_2$，然后计算出第二条轨道 $X_2$。
3. 重复上述过程直至最后 $X_{n+1}=\varnothing$，那么集合在群 $G$ 的作用下一共就有 $n$ 条轨道。

然而这样并不好算，比如本文中的这个项链着色的问题，集合 $E$ 的元素的个数就有 $4^8$ 个，而单个轨道的最大元素个数是 16，也就是说每次我们最多排除 16 个元素，因此我们需要经过相当多的循环才能最终确认轨道的数量。

而 Burnside 给我们提供了一种更为简单的计算轨道数量的方法。如果我们用 $X/G$ 表示全体轨道的集合，那么 Burnside 告诉我们：

Burnside Lemma

$X/G$ 表示集合 $X$ 在有限群 $G$ 作用下的全体轨道的集合，那么集合元素的个数可以表示为 $|X/G|=\frac{1}{|G|}{\sum }_{g\in G}|X^g|$ 其中 $X^g$ 表示集合 $X$ 中所有的在群元素 $g$ 的作用下保持不变的元素组成的集合。 $X^g:=\{x\in X:g\cdot x=x\}$

• 换言之，群 $G$ 上的元素作用在 $X$ 上的不动点的数目的平均值就是这个作用的不同轨道的数目。

这个方法的高明之处在于，给定一个群的元素 $g$，我们往往能通过一些群元素的几何或者代数性质来直接确定 $X^g$ 的大小，而不需要真的一个个去尝试。

比如说给一种来自于 $D_8$ 的元素 $r$，表示顺时针旋转 $\frac{2\pi }{8}$，然后考虑集合 $E$ 当中哪些元素是在 $r$ 的作用下保持不变的，我们很容易就得出只有所有颜色都一样的项链才能保持这种不变性，因此我们立刻就知道 $|E^r|=4$。这就要比按照定义去计算轨道要来的快得多。

而证明这个结果需要考虑一个在数量上和轨道有关系的概念。

• 稳定子：集合的元素 $x$ 在群作用下的稳定子实际上是群 $G$ 的一个子群，它包含那些对元素 $x$ 不起作用的群的元素，记作 $G_x$: $$G_x:=\{g\in G:g\cdot x=x\}$$ 为什么 $G_x$ 在 Burnside 问题中有关系呢？因为 $$\sum _{g\in G}|X^g|=\sum _{x\in X}|G_x|$$ 因为两个求和都表示集合 $G\times X$ 当中所有那些满足等式 $g\cdot x=x$ 的元素 $(g,x)$ 的集合的元素个数，只不过两个等式采用了两种不同的计数方法。

而后者中涉及的稳定子的尺寸与轨道的尺寸，以及群的尺寸之间有直接的关系，这个关系被称之为轨道-稳定子引理 (Orbit-stabilizer lemma)。

3. 轨道-稳定子引理

轨道-稳定子引理

群 $G$ 作用在集合 $X$ 上，$x\in X$ 是集合中一个固定的元素，那么 $|G|=|O_x|\cdot |G_x|$ 其中 $O_x$ 表示 $x$ 在群作用下形成的轨道，$G_x$ 表示所有对 $x$ 不起作用的群的元素形成的稳定子。

其本质是群的第一同构定理，对于 $x$ 我们可以定义一个 $G\to X$ 的定义为 $f_x:g\mapsto g\cdot x$ 的映射，那么：

1. 此映射的像是 $x$ 的轨道，即 $\text{im}{f}_x=O_x$。
2. 此映射的核是 $x$ 对应的稳定子，即 $\text{ker}{f}_x=G_x$。
3. 那么群 $G$ 关于映射的核 $G_x$ 的陪集做成的集合 $G/G_x$ 的数量和映射的像的数量一样，也就是 $|G/G_x|=|O_x|$。这个关系主要是来自于第一同构定理。这并非群的第一同态，集合 $X$ 并非群，我们单纯从集合的角度理解： $$G\twoheadrightarrow G/\text{ker}{f}_x\stackrel{\sim }{\to }\text{im}{f}_x\hookrightarrow X$$
4. 而陪集的集合 $G/G_x$ 的数目一共是多少呢？当然就是子群 $G_x$ 在群 $G$ 中的指数，根据 Lagrange 定理实际上就是 $\frac{|G|}{|G_x|}$，因此便有了这个结果。

从这里也能看得出来引入轨道、稳定子的想法是自然的。因为我们定义了 $f:G\times X\to X$ 的群的作用，这就是一个二元的映射 $f(g,x)\in X$，对于这种映射一个自然的想法是固定其中一个元素，如果我们固定 $x=x_0$，那么我们也就得到了一个 $G\to X$ 的映射 $f_{x_0}=f(g,x_0)$。而此映射的像与核分别是 $x_0$ 的轨道与稳定子。

按照这种理解，我们可以证明 Burnside 的结果:

第三个等式中，我们把整个集合 $X$ 分为了一条条轨道，在每个轨道 $O_{x_i}$ 的长度为 $|O_{x_i}|$，于是便有了上面的证明。