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 all1\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 all1\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

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


  1. […] 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. […]

  2. Anonymous Says:

    Happy to see you found time to learn math!

    • liuxiaochuan Says:

      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.


  3. […] 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 […]


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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 25 other followers

%d bloggers like this: