迭代周期

hbghlyj

点$(x,y)$的坐标是有理数，求证$$A (x,y)=(2x+y,x+y){\bmod {1}}.$$
迭代是周期性的

hbghlyj

为了证明每个有理点都是周期性的。假设 $\mathbf{x}$ 有有理数的坐标；我们想要证明存在一个正整数 $n$ 使得 $(A^n - I)\mathbf{x}$ 有整数的坐标。我们可以将 $\mathbf{x}$ 写成 $\mathbf{x} = \frac 1d\mathbf z$ 的形式，其中 $d \in \Bbb Z$ 是一个公分母，$\mathbf{z} \in \Bbb Z^2$ 是一个向量。考虑到这一点，只需证明存在一个 $n$ 使得 $A^n - I$ 的坐标是 $d$ 的倍数。

换句话说，只需证明必然存在一个 $n$ 使得
$$
A^n = I \pmod d.
$$
我们可以如下证明：根据鸽巢原理，存在正整数 $n_1<n_2$ 使得
$$
A^{n_1} \equiv A^{n_2} \pmod d.
$$
然而，$A^{-1}(x,y)=(x-y,2y-x)$ 有整数的坐标。因此，我们可以推断
$$
[A^{-1}]^{n_1} A^{n_1} \equiv [A^{-1}]^{n_1} A^{n_2} \pmod d \implies\\
I \equiv A^{n_2 - n_1} \pmod d.
$$
因此，所需的结论成立，$n = n_2 - n_1$。

hbghlyj

将一幅猫的150x150像素的图片进行变换，可以看到，300次后，“恢复原状”。
这是因为有理数坐标的点是周期的。所以300是各个像素点的周期的最小公倍数。

hbghlyj

一对樱桃图片上的映射。该图像宽 74 像素，需要 114 次迭代才能恢复，尽管它在中间点（第 57 次迭代）看起来是颠倒的。