1. Schur 定理

1910 年左右, Schur 试图通过将方程 $X^n+Y^n=Z^n$ 模掉素数 $p$ 来解决 Fermat 大定理 ¹, 但是他没有成功. 事实上, 对于每一个正整数 $n$, 该方程对于所有足够大的素数 $p$ 都有非平凡解 mod $p$, Schur 通过证明以下经典结果建立了这一点.

定理 1.1 (Schur 定理). 如果把正整数集用有限多种颜色着色, 那么 $x+y=z$ 总有一组单色解. 即, $x$、$y$、$z$ 都具有相同的颜色.

我们将很快证明 Schur 定理, 但首先我们将展示如何使用 Schur 定理推导出 $X^n+Y^n\equiv Z^n(\mathrm{mod}p)$ 的解的存在性.

以上是 Schur 定理的 “无限” 版本, 它等价于以下的 “有限” 版本. 我们定义记号 $\left[N\right]:=\{1,2,\cdots ,N\}$.

定理 1.2 (有限版本 Schur 定理). 对于每个正整数 $r$, 存在一个正整数 $N=N(r)$ 使得如果将 $\left[N\right]$ 用 $r$ 种颜色着色, 则存在一个单色解 $x+y=z$, 其中 $x,y,z\in \left[N\right]$.

对于有限版本, 我们还可以提出定量问题, 例如关于 $r$ 的函数 $N(r)$ 是怎样的. 对于大多数此类问题, 我们不知道答案, 甚至不知道近似结果. 下面让我们证明定理 1.1 和定理 1.2 是等价的. 很明显, Schur 定理的无限版本蕴含了它的有限版本. 下面用反证法说明如何从有限版本推出无限版本, 固定 $r$, 并假设对于每个 $N$ 有着色方案 ${\varphi }_N:[N]\to [r]$ , 并且该方案使得 $x+y=z$ 没有单色解. 我们可以取一个 $({\varphi }_N)$ 的一个无限子序列, 使得对于每一个 $k\in \mathbb{N}$, ${\varphi }_N(k)$ 的值随着 $N$ 沿着子序列的增加而稳定. 然后 ${\varphi }_N$ 沿着这个子序列逐点收敛到某种着色 $\varphi :\mathbb{N}\to [r]$, 使得该着色没有单色解 $x+y=z$. 显然这与定理 1.2 矛盾.

接下来, 让我们来证明 Schur 这个关于 $X^n+Y^n\equiv Z^n(\mathrm{mod}p)$ 存在非平凡解的断言.

定理 1.3. $n$ 为正整数, 对于所有足够大的素数 $p$, 存在 $X,Y,Z\in \{1,\dots ,p-1\}$ 满足 $X^n+Y^n\equiv Z^n(\mathrm{mod}p)$.

定理 1.3 的证明. 我们先默认 Schur 定理 (定理 1.2) 成立. 然后用 $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ 来表示乘法下模掉 $p$ 后的非零元素组成的群, 令 $H$ 表示 $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ 的所有元素的 $n$ 次幂构成的子群. $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ 中, 子群 $H$ 的指数 ²最多为 $n$. 所以 $H$ 的陪集最多将 $\{1,2,\dots ,p-1\}$ 划分为 $n$ 个集合. 根据有限版本 Schur 定理, 对于足够大的 $p$, 存在一个解$$x+y=z\text{ in }\mathbb{Z}$$使得 $x,y,z$ 属于其中的同一个集合. 假设他们属于陪集 $aH$ (其中 $a\in (\mathbb{Z}/p\mathbb{Z}{)}^{\times }$) . 注意到 $H$ 由 $n$ 次幂组成, 从而一定存在 $X,Y,Z\in (\mathbb{Z}/p\mathbb{Z}{)}^{\times }$, 使得 $x=a{X}^n,y=a{Y}^n,z=a{Z}^n$ 因此$$a{X}^n+a{Y}^n\equiv a{Z}^n(\mathrm{mod}p)$$于是存在 $X,Y,Z\in \{1,\dots ,p-1\}$ 满足$$X^n+Y^n\equiv Z^n(\mathrm{mod}p)$$

$\square$

现在我们准备借助对完全图进行边着色来证明定理 1.2. 下面给出的结果是 Ramsey 定理的一个特例.

定理 1.4. 对于每一个正整数 $r$, 都存在整数 $N=N(r)$, 使得无论如何对完全图 $K_N$ 的边用 $r$ 种颜色着色, 总是存在一个单色三角形.

定理 1.4 的证明. 我们对 $r$ 进行归纳. 显然 $N(1)=3$ 可以使得 $r=1$ 的情况成立. 令 $r\ge 2$ 并假设 $r-1$ 种颜色的情况下, 命题对 $N=N^{\prime }$ 成立, 我们将证明在 $r$ 种颜色的情况下, 取 $N=r\left(N^{\prime }-1\right)+2$ 可以使命题成立.

假设我们使用 $r$ 种颜色为 $r\left(N^{\prime }-1\right)+2$ 个顶点的完全图的边着色. 任意选取一个顶点 $v$, 考虑与 $v$ 相连的 $r\left(N^{\prime }-1\right)+1$ 条边, 根据鸽巢原理, 至少 $N^{\prime }$ 条与 $v$ 相连的边具有相同的颜色, 比如说是红色. 令 $V_0$ 是通过红色边连到 $v$ 的顶点集. 如果 $V_0$ 内的顶点间有红色边, 我们将获得红色三角形. 否则, $V_0$ 中最多出现 $r-1$ 种颜色, 但顶点数 $\left|V_0\right|\ge N^{\prime }$ , 根据归纳法, 还是存在一个单色三角形.

$\square$

我们现在就要构造一个图, 使得该图的单色三角形对应于 $x+y=z$ 的单色解, 从而允许我们将上述结果应用到到整数上 (来证明 Schur 定理) .

定理 1.2 的证明. 令 $\varphi :[N]\to [r]$ 是一种对 $[N]$ 的着色方案. 我们通过给满足 $i<j$ 的无向边 $\{i,j\}$ 上色 $\varphi (j-i)$, 来为顶点集 $\{1,\dots ,N+1\}$ 的完全图的边着色. 根据定理 1.4, 如果 $N$ 足够大, 则存在一个单色三角形. 假设它的顶点是 $i<j<k$, 我们一定有 $\varphi (j-i)=\varphi (k-j)=\varphi (k-i)$, 取 $x=j-i$、$y=k-j$、$z=k-i$ , 那么我们发现 $\varphi (x)=\varphi (y)=\varphi (z)$ 并且 $x+y=z$, 这正是我们想要的.

$\square$

请注意我们是如何通过转移到图论的方式来解决数论问题的. 定理 1.4 中的类似 Ramsey 定理的论证很难直接在整数内部进行. 因此, 我们通过考虑图从而获得了更大的灵活性. 稍后我们将看到这个想法的其他更复杂的例子, 在这些例子中, 将数论问题带到图论领域会给我们一个新的视角.

1.	^ Fermat’s Last Theorem: 当整数 $n>2$ 时, 不定方程 $X^n+Y^n=Z^n$ 无正整数解 (Wiles 1995) .
2.	^ 群 $G$ 中子群 $H$ 的指数是 $G$ 中 $H$ 的左陪集数, 或等效地, $G$ 中 $H$ 的右陪集数. (译者注: 这里 $H$ 的指数至多为 $n$, 是由于数论中的 Lagrange 定理, $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ 上映射 $x\to x^n$ 的核 (kernel) 最大为 $n$. )