Hales-Jewett 定理的归纳证明

Hales-Jewett 定理作为一个有关染色的定理，属于Ramsey theory.是一个很一般的定理。很多定理像van der Waerden’s theorem都是它的特例。下面的证明是在Terence Tao和Van Vu的书 Additive Combinatorics 中第257页。(我一直在断断续续的学习这本书，但是内容很庞杂，比较难线性的从头到尾看下来。事实上，Van Vu教授本人曾经告诉我不要这样做，而是按照喜欢或者所需的东西有目的的去看)这个定理也出现在陶教授关于遍历论的课程中，使用另外的方法进行证明。这本书中的证明就是归纳法，但是归纳过程比较复杂。

Hales-Jewett 定理：令 $m\geq 1, n\geq 1$ . 则一定存在整数 $d=d(n,m)\geq 1$ 使得如果 $\{0,\cdots,n-1\}^d\subseteq \Bbb Z^d$ 的每一个点染成m种不同颜色 $\{0,\cdots,n-1\}^d=E_1\cup\cdots\cup E_m$ , 则至少其中一个 $E_j$ 包含一个长为n的等差数列 $a+\{0,\cdots,n-1\}v$ .其中 $a\in \{0,\cdots,n-1\}^d, v\in\{0,1\}^d$ 且不为零。

定理的证明需要双重的归纳，我们首先将定理推广到另一个更一般的性质。该性质关注的不仅是长为n的等差数列，而且还涉及到一系列相关的长为n-1的等差数列用于联系归纳法中的每一步骤。

性质：令 $m\geq 1,n\geq 1, 1\leq s\leq m$ ,则存在整数 $\widehat d=\widehat d(n,m,s)$ 使得如果 $\{0,\cdots,n-1\}^{\widehat d}\subseteq \Bbb Z^{\widehat d}$ 中的元素被染为任意有限个颜色 $\{0,\cdots,n-1\}^{\widehat d}=E_1\cup\cdots\cup E_m$ .则或者至少一个颜色 $E_j$ 中包含长为n的等差数列 $a+\{0,\cdots,n-1\}v$ ,或者存在不同的s个颜色 $E_{j_1},\cdots,E_{j_s}$ 和 $a\in \{0\cdots,n-1\}^{\widehat d}$ 以及 $v_1, \cdots, v_s\in\{0,1\}^{\widehat d}$ ，使得 $a+\{1,n-1\}\cdot v_i \subseteq E_{j_i}$ for all $1\leq i\leq s$ .

证明：首先，我们说明该性质确实是可以推出Hales-Jewett定理。为此，我们只需要在上面令 $s=m$ .这样，如果我们有m个不同颜色的单色的长为n-1的等差数列 $a+\{1,\cdots,n\}\cdot v_i$ （注意一共只有这m个颜色）,则由于a一定属于某个颜色，我们知道 $a+\{0,\cdots,n\}\cdot v_i$ 一定对某个i是单色的长为n的等差数列。

为了简化证明，我们使用‘等差数列’来表示等差数列 $a+\{0,\cdots,n-1\}\cdot v_i$ 或者 $a+\{1,n-1\}\cdot v_i$ ,其中 $a\in \{0,\cdots,n-1\}^d$ , 以及 $v\in\{0,1\}^d$ 且不为零。

我们已经说过，证明过程应用了双重的归纳法。对于外层我们对n归纳.当 $n=1$ 时候，命题是平凡的。我们假设 $n-1$ 的情况我们已经证明，由上面的说明我们亦假设了定理在n-1情况下成立。

下面我们进行内层，对s进行归纳。当 $s=1$ 时，由定理对n-1成立，我们可以将 $\{1,\cdots,n-1\}$ 变成 $\{0,\cdots,n-2\}$ 就直接证明此种情况。因此假设$2\leq s\leq m$，并假设我们已经证明了 $s-1$ 的情况（当然还是外层的n，但是假设中对一切m成立。）我们定义 $\widehat d=\widehat d(n,m,s)=d_1+d_2$ ,其中 $d_1=\widehat d(n,m,s-1)$ 以及 $d_2=d(n-1,m^sn^{sd_1})$ . 令 $\{0,\cdots,n-1\}^{\widehat d}$ 中的元素被染为m个颜色 $\{0,\cdots,n-1\}^{\widehat d}=E_1\cup\cdots\cup E_m$ . 假设没有一个颜色 $E_j$ 中包含长为n的等差数列，我们的任务就是证明存在不同的s个颜色 $E_{j_1},\cdots,E_{j_s}$ 和 $a\in \{0\cdots,n-1\}^{\widehat d}$ 以及 $v_1, \cdots, v_s\in\{0,1\}^{\widehat d}$ ，使得 $a+\{1,n-1\}\cdot v_i \subseteq E_{j_i}$ for all $1\leq i\leq s$ .

我们记 $\{0,\cdots,n-1\}^{\widehat d}= \{0,\cdots,n-1\}^{d_1}\times \{0,\cdots,n-1\}^{d_2}$ ,对每个 $x\in\{0,\cdots,n-1\}^{d_2}$ 我们考察分割 $\{0,\cdots,n-1\}^{d_1}=E_{1,x}\cup\cdots\cup E_{m,x}$ ,其中 $E_{j,x}=\{y\in\{0,\cdots,n-1\}^{d_1}:(y,x)\in E_j\}$ .由于假设 $E_j$ 中都不包含长为n的等差数列， $E_{i,x}$ 也不包含。由 $d_1$ 的定义和内层归纳假设，我们推断对于每个x存在不同的色类 $j_{1,x},\cdots,j_{s-1,x}, a_x\in \{0,\cdots,n-1\}^{d_1}$ 和 $v_{1,x},\cdots,v_{s-1,x}\in \{0,1\}^{d_1}$ 且不为零，使得

$a_x+\{1,\cdots,n-1\}\cdot v_{i,x}\in E_{j_{i,x}}$

对一切 $1\leq i\leq s-1$ 成立。注意到 $a_x$ 一定属于某一个色类 $j_{s,x}$ ，不同于 $j_{1,x},\cdots,j_{s-1,x}$ ,否则我们就构造出了n长的等差数列。我们若令 $v_{s,x}=0$ ,则上式对 $i=s$ 也成立。

下面我们开始使用那些 $d_2$ 坐标。映射 $x\to (j_{1,x},\cdots,j_{s,x},a_x,v_{1,x},\cdots,v_{s-1,x})$ 是从 $\{0,\cdots,n-1\}^{d_2}$ 到一个集合之多包含元素个数 $m^sn^{sd_1}$ .这样实际上给出了一个 $\{0,\cdots,n-1\}^{d_2}$ 的染色，颜色个数为 $m^sn^{sd_1}$ 。由 $d_2$ 的定义和外层归纳假设，我们得到一定存在一个色类 $F_t$ 包含长为n-1的等差数列 $a_*+\{1,\cdots,n-1\}\cdot v_*$ . 就是说，存在不同的 $j_{1,(t)},\cdots,j_{s,(t)}\in \{1,\cdots,m\}, a_{(t)}\in\{1,\cdots,m\}^{d_1}$ ,以及 $v_{1,(t)},\cdots,v_{s,(t)}\in \{0,1\}^{d_1}$ (注意，前面提到过 $v_{s,(t)}=0$ )是满足 $a_{(t)}+\{1,\cdots,n-1\}\cdot v_{i,(t)}\in E_{j_{i,x}}$ 对所有的 $x\in a_*+\{1,\cdots n-1\}\cdot v_*$ 和 $1\leq i\leq s$ 成立.

最后，我们设 $a=(a_{(t)},a_*)$ 以及 $v_i=(v_{i,(t)},v_*)\in \{0,1\}^d$ 不为零.这时， $a+\{1,\cdots,n\}\cdot v_i\in E_{j_i}$ 即为所求的长为 n-1的等差数列，完成了证明。

About these ads

Explore posts in the same categories: combinatorics, Ergodic Theory, Maths

This entry was posted on 2009/07/18 at 1:59 am and is filed under combinatorics, Ergodic Theory, Maths. You can subscribe via RSS 2.0 feed to this post's comments. You can comment below, or link to this permanent URL from your own site.

5 Comments on “Hales-Jewett 定理的归纳证明”

the “epsilon and delta” proof of polynomial Van Der Waerdon theorem « Liu Xiaochuan’s Weblog Says:

2009/07/18 at 5:46 pm
[...] the “epsilon and delta” proof of polynomial Van Der Waerdon theorem 七月 18, 2009 at 5:45 下午 | In Ergodic Theory(遍历论), Maths（数学） | Leave a Comment This post is the answer to the exercise 4 of lecture 5 of Professor Tao’s lecture notes of ergodic theory. I write it separately because it’s a little lengthy. Here is the lecture notes. It is very interesting to contrast this proof with the proof of Hales-Jewett theorem, useing induction. One can observe the similarity between these two proofs. I also wrote a post of the the proof of Hales-Jewett theorem in Chinese. [...]

Reply
Anonymous Says:

2009/07/19 at 3:02 am
Happy to see you found time to learn math!

Reply
- liuxiaochuan Says:
  
  2009/07/19 at 11:21 am
  Yeah, I’m happy about this, too. A while ago I was a little frustrated by some unnecessary worries. Right now I am clear about myself. I am back to myself!
  
  Thanks for everything.
  
  Reply
Several Ramsey-type theorems « Liu Xiaochuan’s Weblog Says:

2009/07/19 at 8:22 pm
[...] several Ramsey-type theorems can all be proved by Hales-Jewett theorem. I wrote a post on the combinatorial proof of this theorem.These are also exercises of Professor Tao’s lecture on ergodic [...]

Reply
陶哲轩遍历论习题解答：第五讲 « Liu Xiaochuan’s Weblog Says:

2009/07/29 at 7:49 pm
[...] (注：遍历论为陶哲轩教授于08年年初的一门课程，我尝试将所有习题做出来，这是第五讲的二十一个习题。这里是这门课程的主页，这里是本讲的链接。有一些题目我花费的时间比较多，我将所需要的知识补充在另外的帖子中。关于ultrafilter, 我写过一个帖子.习题一中涉及到一点数论知识，尤其关于二次剩余的知识。我写过一个帖子是关于Hales-Jewett定理的归纳法证明.习题4的解答比较长，我另写了一个帖子。该过程是参考了上一讲中定理四的证明。注意这个证明方法与前述Hales-Jewett定理的归纳证明的异同。仍有几个问题没有完成，我会慢慢补上。) [...]

Reply

Xiaochuan Liu's Weblog

Hales-Jewett 定理的归纳证明

Like this:

5 Comments on “Hales-Jewett 定理的归纳证明”

Leave a Reply Cancel reply

Follow “Xiaochuan Liu's Weblog”