（基础数学专业论文）ramsey理论中的van+der+waerden数和ramsey数研究.pdf

上海人学硕t = 学位论文 摘要 在r a m s e y 理论中，求各种r a m j e y 类数的精确值及其适度的上、下界是研 究的重点和难点。本篇硕士论文主要研究组合数学中的v a i ld e rw a e r d e n 数和 r a m s e y 数。它以v a nd e rw a e r d e n 问题的图形变换、圆周上v a nd e rw a e r d e n 问 题的矩阵形式和含参数的r a m s e y 数新的上界公式作为研究目标和研究重点。 本文首先介绍了r a m s e y 理论的发展历程、研究进展、v a nd e rw a e r d e n 问题简 介以及作者的主要工作。 本文的研究工作主要分为三个方面。首先，研究传统意义上的v a nd e r w a e r d e n 数问题，从图的变换角度，得到了v a i ld e rw a e r d e n 数的一些比较有用 的结果，为研究圆周上的v a i ld e rw a e r d e n 数提供了线索。利用类似的方法，进 一步得到了圆周上v a nd e rw a e r d e n 数呒( 刀，刀) 的新的下界。其次，我们试图避 开抽屉原理，构造新方法，把圆周上的v a nd e rw a e r d e n 问题转化为线性不定方 程组的求解问题，研究其系数矩阵并指出它的解是可求的。最后，我们在原有 的r a m s e y 理论研究的基础上，运用基本公式推导，对r a m s e y 数的上界公式进 行了改进，得到了含参数的r a m s e y 数的新上界公式和一些较好的结果。 关键词：v a nd e rw a e r d e n 数w ( n ，九) ，圆周上的v a nd e rw a e r d e n 数( 门，以) ， r a m s e y 数r ( g l ，g 2 ) ，奇偶分拆 一j ：海人学硕j ：学位论文 a b s tr a c t i th a sc u r r e n t l yb e e nb e c o m ed i f f i c u l ta n df l o u r i n ga r e ao fr a m s e yt h e o r yt o f i n dt h ee x a c tv a l u e sa n dp r o p e ru p p e ra n dl o w e rb o u n d si nr a m s e yt h e o r y 。t h i s m a s t e rt h e s i sf o c u s e so n v a nd e rw a e r d e nn u m b e ra n dr a m s e yn u m b e ri n c o m b i n a t i o nm a t h e m a t i c s 。t h er e s e a r c ha i m sa n dm a i np o i n t sa r eg r a p hc h a n g i n g a n dm a t r i xf o r mo fv a nd e rw a e r d e np r o b l e mo nc i r c l e ，t h en e wu p p e rb o u n d f o r m u l a so fr a m s e yn u l l l b e r s 。f i r s t l y ，w ei n t r o d u c et h ed e v e l o p m e n ts u r v e ya n d m a i nr e s e a r c hd i r e c t i o n so fv a i ld e rw a e r d e np r o b l e ma n dr a m s e yt h e o r y 。a n dt h e a u t h o r sr e s e a r c hw o r k s t h er e s e a r c hw o r k so ft h i st h e s i sc o n s i s t so ft h r e ep a n s t h ef i r s ta s p e c to ft h e r e s e a r c hw o r ki s s t u d y i n g c o n d i t i o n a lv a nd e rw a e r d e nn u m b e r f r o mg r a p h t r a n s f o r m a t i o n ，u s i n go d d e v e np a r t i t i o n ，w eo b t a i ns o m eg o o dr e s u l t s f r o mt h i s f o u n d a t i o nw eu s et h es a m em e t h o d a n da tl a s tw eo b t a i nt h en e wl o w e rb o u n do f v a nd e rw a e r d e nn u m b e ro nc i r c l e s ob vt h er e l a t i o n s h i po fc o n d i t i o n a lv a nd e r w a e r d e nn u m b e ra n dv a nd e rw a e r d e nn u m b e ro nc i r c l e w ea l s oc a no b t a i nt h en e w l o w e rb o u n do fv a nd e rw a e r d e nh u m b e r t h e n ，w et r yt oa v o i dd r a w e rp r i n c i p l e b u i l dt h en e wm e t h o d s a n dt r a n s f o r mv a nd e rw a e r d e nn u m b e ro nc i r c l ei n t ot h e s o l u t i o n so fi i n e a ri n e q u a l i t i e se q u a t i o n s w er e s e a r c ht h ec o e 衔c i e n tm a t r i xo fl i n e a r i n e q u a l i t i e se q u a t i o n sa n dp o i n to u tt h a ti t ss o l u t i o n sc a nb ea s k e d t h eo t h e rp a r to f t h er e s e a r c hw o r ki st h a tw eg e tan e wu p p e rb o u n df o r m u l af o rr a m s e yn u m b e r s w i t hp a r a m e t e r sa n das e r i e so fb e t t e rr e s u l t s ，b yu s i n gt h en e wu p p e rb o u n d f o r m u l a s ，o nt h ef o u n d a t i o no ft h ea l r e a d ye x i s t i n gr e s e a r c ho fr a m s e yt h e o r y k e y w o r d s ：v a nd e rw a e r d e nn u m b e rw ( n ，刀) ，v a nd e rw a e r d e nn u m b e r 陟0 ( 甩，门) o nc i r c l e ，r a m s e yn u m b e r r ( g i ，g 2 ) ，o d d e v e np a r t i t i o n v l 一卜海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：狴至曼至日期：皇墨：曼：12 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：啦导师签名_ 轴期：! 幽 上海大学硕仁学位论文 第一章绪论 1 1 r a m s e y 理论 r a m s e y 理论是组合数学的重要分支。r a m s e y 问题也是图论中极值极图问 题中的重要问题之一。值得一提的是，组合学中的一个重要而基本的原理：抽 屉原理。1 9 世纪以来，这个原理首先是用来建立有理数理论，尔后逐渐应用到 不同的数学领域，如在数论、组合论、几何学等方面有着重要的应用，并且常 常得到一些令人惊异的结果。 r a m s e y 理论是数学世界的一株奇葩。“世界上完全的无序是不可能存在 的。任一足够大的结构( 大数集，点集或事物的集合) 中必定包含有一个给定 大小的规则子结构。”这富有哲理的格言恰是r a m s e y 理论的主导精神。从理 论上说，r a m s e y 理论具有三种引人注目的特点：首先，它具有相当鲜明的哲学 指导思想。其次，理论本身非常质朴，理论的主要内容，包括所研究的问题， 所得到的结论连同结论的证明，只需要用很少一点数学概念就能表述；甚至还 可以完全用同常用语来陈述其绝大部分精彩结果。最后，这个理论是一门面向 未来的学科，从一方面向人们展示了未知数学世界的浩淼无垠。人们普遍认为， 数学家们还只是刚刚丌始探索r a m s e y 理论的真谛和影响。 在r a m s e y 理论中，几乎所有的定理都涉及到使定理成立的最小币整数， 这就是所谓的r a m s e y 类数，其中著名的有：r a m s e y 数，v a nd e rw a e r d e n 数， s c h u r 数等。精确计算这些数需要高超的数学技巧和创新的数学方法，同时涉 及到几乎所有的主要数学领域知识。这是当今r a m s e y 理论研究的热点和难点。 r a m s e y 理论的发展历程及其应用 在理论的发展进程中，相继出现了一个又一个著名的定理，所得到的结果非 常的完美。 舒尔定理问世比r a m s e y 定理早十几年，而舒尔定理本身后来得到一系列推 广和发展，是r a m s e y 理论的源头之一这个定理是德围数学家舒尔( i s c h u r ) 在 1 9 1 6 年发表的一篇研究有限域上的费尔马大定理的论文中证明的，论文的题目 叫做“论同余式x ”+ j ，”三z ”( m o dp ) ”o s c h u r 定理( 有限形式) ：对任一给定的七n ，存在刀n ，使得对【胛】的任 一k - 染色厂：【门】一【k 】，有j r ，j ，【门】使( z ) = f ( y ) - - f ( x + y ) 。上述n 的最小值记 为s ( k ) 。 随后舒尔在1 9 2 0 年提出了一个猜想是这样的：“如果把正整数集任意分拆 成两部分，那么对于任意给定的一个j 下整数l ，二部分中必有一部分含有l 项等差 数列”1 9 2 6 年，当时在德国汉堡大学的范德瓦尔登从哥丁根大学的一位荷兰学 生包特( b a u d e t ) j j j 罩得知了这个猜想并最终完全证明了这个猜想成立。 i ：海大学硕上学位论文 1 9 2 7 年，b l v a i ld e rw a e r d e n 证明了另一个主要的r a m s e y 类经典定理，被称 之为v a nd e rw a e r d e n 定理。前苏联著名数学家辛钦- 在1 9 5 2 年出版了一本题为 数论的三颗明珠的书，v a i ld e rw a e r d e n 定理就是其中的一颗明珠。 v a i ld e rw a e r d e n 定理：对任意给定的，k n ，存在w = w ( t ，k ) n ，使得把 【形】 任意分拆成k 部分后，其中必有一部分含有i 项等差数列： a ，a + d ，口+ ( ，- 1 ) d 哈尔斯朱厄特定理： 对任意的f ，k n ，有h = h ( t ，k ) n ，使得对任一t 元集a 以及a 的任一k 染色，a 中必有各点同色的线。 这个定理是v a i ld e rw a e r d e n 定理在定性方面的一个主要的深化曾有人高 度评价了这一定理：“哈尔斯朱厄特定理舍弃了范德瓦尔登定理的非本质因素并 揭示出它的拉姆塞理论的本质。” 1 9 3 0 年，英国逻辑学家f e r a m s e y 证明了一个后来以他名字命名的定理即： r a m s e y 定理。 r a m s e y 定理：设q i ，留2 ，q 。，t 是正整数，r q ，t ( 1 i 刀) ，则必存在最小 的正整数n ( q l ，9 2 ，q 。；，) ，使得当m n ( q l ，9 2 ，q 。；，) 时，设s 是一集合且 s l = 所，将s 的所有，元子集任意分放到n 个盒子罩，那么要么有s 中的g ，个 元素，它的所有t 元子集全在第一个盒子罩；要么有s 中的g ：个元素，它的所有t 元子集全在第二个盒子里；要么有s 中的q 。个元素，它的所有t 元子集 全在第n 个盒子里。 这个定理是一个非常优美的结果，集中体现了这个数学分支的精神。引起了 许多数学家关注，并吸引他们到组合数学这一领域。然而在此后的二十多年中， r a m s e y 理论没有太大的进展，直到1 9 5 5 年g r e e n w o o d 和g l e a s o n 发现非平儿 的r a m s e y 数。在7 0 年代以自i ，关于r a m s e y 问题研究的文章不是很多。1 9 7 3 年在匈牙利的布达佩斯召开的组合数学大会，成为r a m s e y 理论发展的里程碑。 在最近的几十年里，由于许多著名的数学家对这一理论的关注，特别是p a u l e r d o s 自己的工作和对它的传播，使得r a m s e y 理论得到了很大发展。迄今为 止，经过几代数学家的努力再加上计算机的帮助，所有非平凡的经典r a m s e y 数的精确值也只求出了9 个，由此可见其研究的艰难性。 如今，r a m s e y 理论的研究中越来越多的应用许多现代的数学方法，如：规 划方法、代数方法、分析方法、随机图方法等等。可以说，几乎每一个新的r a m s e y 数的确定都伴随着一种新方法的产生。今天，r a m s e y 理论已经发展成为一个内 2 卜海大学硕t j 学位论文 容丰富、生动，结果优美，证明极具有技巧性和创造性的数学分支，同时，它 也被广泛地应用于几何凸边形问题，矩阵理论等各种研究领域，前景应用十分 广阔。 1 2v a nd e rw a e r d e n 问题简介 1 9 2 0 年，德国数学家1 s c h u r 提出一个猜想：“若把正整数集合任意分拆成二 部分，则对任意给定的正整数刀，这二部分中必有一部分含有行阶等差数列 a ，口+ d ，口+ ( 刀一1 ) d ”1 9 2 7 年，v a nd e rw a e r d e n 完成了这个证明后来就把这 类数冠以他的名字，称为范德瓦尔登数w ( n ，刀) 1 9 5 2 年，苏联数学家辛钦 誉其为数论中的三颗明珠之一1 9 3 6 年，e e r d o s 和e t u r d n 把它推广成这样的猜 想：“若丁为自然数集合的子集，且7 具有f 的上密度，即而l ! ! ! 幽 o ，则t 内含 - + 重 ， 有任一给定项数”的等差数列”这里【，】= f l ，2 ，3 ，l 。证明这个猜想使人们有 可能用上解析数论工具，1 9 5 8 年菲尔兹奖得主k f r o t h 便用了解析数论法在1 9 5 2 年证明了刀= 3 的情形1 9 6 9 年，e s z e m 色r d e d i 更进一步证明了玎= 4 ，且在1 9 7 4 年证明了这个猜想对一切玎成立后来，h f u r s t e n b e r g 又用保测度的遍历结构理 论给予了证明1 9 9 8 年的菲尔兹奖得主w f g o w e r s 又用全新的组合分析法完成 了这个证明一个范德瓦尔登定理及其推广，竟使得那么多世界级大师们为它竟 折腰，这在数学史上也是不多见的直到如今数学家们还只求得了五个范德瓦尔 登数w ( n ，l ， ) 的准确值： w ( 3 ，3 ) = 9 ，w ( 4 ，4 ) = 3 5 ，w ( 5 ，5 ) = 1 7 8 ，w ( 3 ，3 ，3 ) = 2 7 ，w ( 3 ，3 ，3 ，3 ) = 7 6 且后四个还是借助计算机求得的 1 9 2 7 年以来，已有过好几个关于范德瓦尔登定理的不同证明。例：r i g r a h a m 和b l r o t h s c h i l d 就有过一个十分简洁的证明。然而，他们的证明思想皆 脱离彳i 了抽屉原理这个窠臼。真是令人难以置信：一个伟大的定理主要应用了这 么一个初等而简洁的原理! j 下因为他们是在反复运用抽屉原理的基础上证明了范 德瓦尔登定理的，所以也就难于把范德瓦尔登数的上界表达出来。关于范德瓦尔 登数w ( n ，门) 的上界问题一直进展甚微，直到1 9 8 8 年才由后来因此而得w o l f 奖 2 的以色列数学家s s h e l a h 得到，它至今仍是最好的上界 3 ：w ( n ，2 ) s2 ，共有 2 w ( n 一1 ，刀一1 ) 个2 但这个上界大得出奇，连矿都无法与它比较。在1 9 8 2 年的 2 世界数学家大会上，r l g r a h a m 曾提出一个猜想：w ( n ，甩) 2 2 ，刀个2 虽然 这个上界仍是异常的大，却至今无人能解决。关于范德瓦尔登数上界的研究正方 兴未艾，十分引人注目。 其实关于范德瓦尔登数下界的研究也进展甚微。运用非构造性方法曾得到 缈( ，。疗) 一2 n 一! ，当胛是质数时还可改进为w ( n ，门) 力2 “，但它的大小与上界相比 。 2 e n月 显然有天壤之别。下界问题也是摆在数学家面前的重大课题。并且令人深感诧异 f ：海大学硕 学位论文 的是：它与r a m s e y 数r ( n ，刀) 的下界公式一样，也仅能用非构造性的概率论方法求 得。 本文凡表示数字的字母般代表币整数，以下的【1 , b 】表示b a + 1 个相继整 数口，口+ l ，口+ 2 ，b 糊jk 2 1 1 ，6 】【6 】，以fbi 表示不大于鱼的最大整数。 lala 1 3 本文的主要工作 本篇硕士论文主要研究组合数学中的v a l ld e rw a e r d e n 数和r a m s e y 数。它 以v a nd e rw a e r d e n 问题的图形变换、圆周上v a nd e rw a e r d e n 问题的矩阵形式和 含参数的r a m s e y 数新的上界公式作为研究目标和研究重点。本文分为以下三 大部分： 第一部分：研究传统意义上的v a nd e rw a e r d e n 数。我们运用图的奇偶分拆， 得到了v a nd e rw a e r d e n 数的一些比较有用的结果，为研究圆周上的v a i ld e r w a e r d e n 数提供了线索。 第二部分：研究圆周上的v a nd e rw a e r d a n 数。从第一部分研究中得到启发， 通过比较运用类似的方法得到了圆周上v a nd e rw a e r d e n 数的新的下界公式： 2 ，( 七+ ，似+ 呒( 刀，刀) ( 字母意义见文中) 显然，利川公式( 力，甩) ( 丹，疗) ，我们也得剑了传统意义上的v a nd e rw a e r d e n 数的一个新的下界公式。 其次，我们构造新方法，将圆周上的v a nd e rw a e r d e n 数问题转化为线性不 等式组求解问题，研究其系数矩阵，得到了两种特殊情况下的参数解。为进一 步求解圆周上的v a nd e rw a e r d e n 问题提供切实可行的依据。 第三部分：在原有的r a m s e y 理论研究的基础上，我们运用新的上界公式对 r a m s e y 数的上、下界公式做出一些改进，得到了含参数的r a m s e y 数的新的上 界公式，并得到了一些比较好的结果。 4 上海大学硕上学位论文 第二章 v a nd e rw a c r d e n 问题 2 1引言 大数学家v a i ld e rw a e r d e n 在1 9 2 7 年证明了德国数学家i s c h u r 的一个猜想， 这就是后来r a m s e y 理论发展源泉之一的v a n d e rw a e r d e n 定理。 v a nd e rw a e r d e n 定理： 对任意给定的正整数，2 3 ，必存在正整数 w ( n ，k ) ，使当把w ( n ，k ) 个数的集合【】= 1 ，2 ，w n ，七) 任意分拆成k 个部分 后，其中必有一部分含有力阶等差数列6 1 , a + d ，口+ 2 d ，口+ ( 刀一1 ) d 若记 = r + l ，则至少还存在一个分拆【厂】= a iua 2u u4 ，使每个集合4 内皆不含 刀阶等差数列。 v a nd e rw a e r d e n 定理中断言存在的最小j 下整数被称为v a nd e rw a e r d e n 数 和其它r a m s e y 数一样，对函数w 的定量研究将会非常困难。 先来看几个w ( n ，k ) 的几个精确值：当，= 2 时，w ( 2 ，k ) = k + l ，这是平 凡结果；另外用穷举法可以得到w ( 3 ，2 ) = 9 。除此之外，借助于计算机搜索还 求得了4 个值。表1 1 列出了已确定的所有非平凡的w ( n ，k ) 的值。 n k2 34 392 77 6 4 3 5 5l7 8 表l 1 实际上八十多年来人们对范德瓦尔登数最有兴趣的不是求得其精确值，这 似乎超出了人们现有的能力。随着计算机性能飞速提高，个中好的算法不断涌 现，人们自然希望对它有较好的估计，特别是想得到比较“适度”的上、下界。 这一问题已成为当今r a m s e y 理论研究的又一重点和难点。下面就来概述一下 这方面的历史发展。 1 9 5 0 年，厄尔多斯( r e r d 6 s ) 和另一位著名的组合学家拉多( r r a d o ) 用 ； 概率方法求得w ( n ，”) 的下界：w ( n ， ) 2 ”帅卜 1 9 6 8 年，贝勒坎普( b e r l e k a m p ) 改进为：w ( n ，力) 2 ” 上海人学硕j ：学位论文 1 9 8 0 年，格林( r l g r a k a m ) 等人用“非构造法方法 得到 w ( n ，力) 一二，当n 是素数时，得到了更好的下界：w ( n + 1 ，刀+ 1 ) n 2 ” z e 力刀 然而这些下界与目前人们所得到的w ( n ，刀) 的上界有天壤之别。w ( n ，疗) 的 已知上界作为n 的函数其递增速度是如此之快，以至于必须用被称为阿克曼层 次( a c k e r m a nh i e r a r c h y ) 的一系列专门函数才能表示它。 定义2 1所谓阿克曼层次的函数，即第m 层记为a m ( m l 的正整数) ，它的第 k 层函数a k 可以定义第l ( + l 层函数舢汁l ，其中， a i + l ( 1 ) = a ( 1 ) = 2 ，a + l ( 疗) = a ( a t + l ( ，一1 ) ) ( 九 1 ) 第1 层函数a i ( 疗) = 2 n ，是“加倍函数”；第2 层函数彳2 ( 力) = 2 ”，是递 增很快的指数函数。a ：可以用a 。来描述：彳2 ( 刀) 等于a 。在自变量l 处 重复n 次。 、 例如：a 2 ( 3 ) = a i ( 彳i ( 彳。( 1 ) ) ) = 2 2 2 = 2 3 可以递推定义：a ：( 1 ) = a 。( 1 ) = 2 ，a 2 ( 刀) = a 。( 彳2 ( 刀一1 ) ) ( 刀 1 ) 一般地，不难看出有4 ( 行) = a 2 ( 彳，( n - 1 ) ) = 2 州” ，因此可以写成下面这 种2 的“，n 层塔幂”的形式：彳，( ”) ：2 2 2 一 ( 共n 个2 ) 故第3 层函数a ，也称为2 的“塔幂函数”，其递增速度异常之快。 彳3 ( 3 ) = 22 = 1 6 ，a 2 ( 4 ) = 2 1 6 = 6 5 5 3 6 ，a 3 ( 5 ) = 2 6 5 5 3 6 ， 一般地，从第k 层函数a 。到a 川，函数的递增速度又上了一层。但不管 怎么说，对一个固定的正整数m 来说，a ，( 以) 作为n 的函数还是限于第m 个 层次，其递增速度有所约束。下面定义的函数a 将突破任何固定的层次，或者 说它凌驾于任一层次之上。 定义2 2 ： 设a ( n ) = a 。( 九) 即： 彳( 1 ) = a l ( 1 ) = 2 ，彳( 2 ) = a 2 ( 2 ) = 4 ， a ( 3 ) = a 3 ( 3 ) = 1 6 ，a ( 4 ) = a 4 ( 4 ) ， 把函数a 叫做a c h e r m a n 函数。 6 上海大学硕一i ：学位论文 其中函数值彳。( 4 ) 已经大得难以置信，格雷厄斯和斯彭塞是这样形容数 彳。( 4 ) 的：“即使一个数大得必须用世界上所有数的全部篇幅再加上所有计算机 的全部存储能力把它容纳进去，这个数同a 。( 4 ) 相比仍小得微不足道。 从范德瓦尔登数在1 9 2 7 年首先证明以他命名的这个定理以来，7 0 年间又找 到了不少新的证明。但所有证明对量w ( n ，刀) 的估计都必须相当于a ( n ) 。也就是 说，只有把从l 到a ( n ) 这样大的每个整数任意分拆成两部分后，才能保证其 中必有一部分含有n 项等差数列! 定理表述之简单与其相应的数w ( n ，月) 如此庞 大的上界形成极大的反差。数学家当然不会对这种现象安置若素，但试图改变 状况的努力均告失败。 值得一提的是：1 9 8 7 年，以色列数学家谢拉( s s h e l a h ) 证明了w ( n ，疗) 2 的2 w ( n 1 ) 层塔幂。根据前面的定义不难证明2 的2 w ( n l ，刀一1 ) 层塔幂 = 以( 2 w ( n l ，门一1 ) ) a 。( 刀) 。从而可知w ( n ，v ) 的上界不超过第4 层函数a 。( 聆) 。 a 。( 玎) 与a ( n ) = a 。( ) 相比，当然已经根本性地减少。注意到w ( n ，盯) 的已有下 界属第2 层次，而谢拉的上界属第4 层次，问题就更富有挑战性了。 对范德瓦尔登数定理中涉及的数，也就是范德瓦尔登数的界的研究j 下方兴 未艾，十分引人注目，这也正是本文所研究的主要内容之一。 2 2v a nd e rw a e r d e n 数 2 2 1 v a i ld e rw a e r d e n 定理及其等价形式 v a nd e rw a e r d e n 定理( 1 9 2 7 ) 对于正整数疗3 ，k 2 ，必存在j 下整数 t 瓦翱，使当把 】任意分拆成七部分后，其中必有一部分含有门阶等差数 列e l , a + d ，口+ 2 d ，口+ ( 拧一1 ) d 若记w = r + l ，则至少还存在一个分拆 = a iu4 u u 4 ，使每个謇合4 中皆不含有疗阶等差数列，1 f k 一般所谓的v a l ld e rw a e r d e n 数皆指w ( n ，疗) ，以下就w ( n ，刀) 来作研究。 上海大学硕卜学位论文 定理2 1 设p w ( n ，刀) ，( f ) = 薯= 0 或1 ，1 i p ，d ：l 型j ，刀3 ，w ( n ，刀) 是 i _ ，一il 范德瓦尔登数，则以下由阳一兰d ( c ，+ 1 ) ( 力一1 ) 个不等式构成的线性不等式组无解： 1 x l+x2+ + 毛 s1 7 - - 1 1 x 2 + 而 + + + l n - 1 1 而一。+ i + 一i+ 刀一1 1 五 + 弓 + + x 2 。一l n - i 1 屯+ + + 而。 门一1 ： 1 x p - ( n - i ) 2 + x p 一2 + 讳 刀一1 ( 1 2 ) ： 1 xl + 五+ ， + + + ( 月一1 ) ， 力一1 1 x2 + x 2 + d + + x 2 + ( 一i ) ， n 一1 1 x p - ( n - 1 ) ， + + 一d + x p 门一1 ( 1 d ) 以上第五组有p 一( k 一1 ) k 不等式，1 k d 证 设 p 】= a ub 是一个2 分拆，记厂( f ) ：薯： ? ：a 。，l f p 本文总假定对 l 1 l d 于a 中的每数染红色，对于b 中的每数染蓝色。若a 或b 中存在公差为b 的i i 阶 等差数列口，a + b ，a + 2 b ，口+ ( 门一1 ) b ，则必有艺m 2o 或刀，故这罩 p d 一专d ( d + 1 ) ( 丹一1 ) 个不等式表示在a 或口中不存在同色，7 阶等差数列。 显然，由范德瓦尔登数w ( n ，刀) 的定义知：当p w ( n ，力) 时，定理l 中这 p d 一专d ( d + 1 ) ( 刀一1 ) 不等式不能同时成立，于是本定理得证。 由于本文总规定a 中的每数，染红色( f ( i ) = 0 ) ，b 中的每数，染蓝色 ( ( ) = 1 ) ，故定理1 ( 即范德瓦尔登定理) 可这样来叙述：对于充分大的 p ( p w ( n ，门) ) ，任一2 分拆【p 】= aub 中必存在同色刀阶等差数列。 8 上海人学硕土学位论文 2 2 2v a i ld e rw a e r d e n 问题的图形变换 基本定义与说明 定义2 2 设集合科”= 4 ，以，d 2 ，1 4 定义2 3 若2 一分拆【p = a u b , p 为素数，记其特征值( ，) = = ：) ；茎：， 1 f p 有 玉- - - - x i ，( 1 is 口1 ) ， 玉五+ 口i = + q ，( 1 f 口2 ) ， x i2 j i + q + 啦= 一+ q + 吒，( 1 f c 3 ) 2 k2 k 五= 朋+ q ) = ( f + q ) ，( 1 f 口2 川，2 k + l g ) ， q 若p = q ，a i , 口2 ，气中有，个q 2 ( 其余g 一，个口f = 1 ) ，则称2 一分拆 ，= i 【p 】a u b 的o - r 值为( g ，) 其中q 值表示玉经过而，x 3 ，走向x p 时，它们的值 ( o 或1 ) 经历了q 次不同取值。 9 x拍 口 一 2 ，2 ，q ：1 ，2 f g 一1 ，p ：兰q ，= i 不妨假设五= 屯= = = o ，2 i a 1 ( a ) 若q 为奇数，则 q i 讳= 厂( f + 巳) = o ，1 f ，而+ q = x 2 + 口i = l ，1 2 i - 1 _ p - a q 1 = 1 x 2 + q - - - - x 2 ，+ 口l = 0 ，2 2 i p 一口q + l ，显然当a l 为奇数时， 因 l o 卜海入学硕l j ：学位论文 q = x 2 ，- l5 l ，1 2 i 一1 p ) 中q i = 1 而皱= x 2 ，2 2 j p ) 中因x p = x p l = 0 恰 有一个属于d 2 ，故q ：= 3 ，所以2 ，= 吼+ g ：当口l 为偶数时， 由于 q i 而= o ( 2 + q ) ，故吼= 3 ，而x 2 的9 2 = l ，l i ) t 以2 r = q l + q 2 i = l 示意图：oo ooo oxo o o o 0 0 00 0 0 0 0 0 ( 这里q = 7 ) q - i ( b ) 若g 为偶数，则= 1 = 厂( f + q ) ，l ，q 。可与( a ) 相似地得g l = 仍= 2 ，= l 故2 r = q l + 9 2 示意图：00 00 0 0 ( q = 6 ) ( 3 ) 设g = ，2 ，口l 2 ，2 时成立：2 r = g l + 9 2 则当q = ，+ l 时，不 妨假设q 2 ，q 2 ， 口l ，口2 ，呸中有，个q 2 ，f ：窆q ， 2 一i2 0 2 + 2 ，( o f p 一) ，+ 2 ，+ l2 i ( 0 f p ) ，x ，= 一l = l = x ，+ 口口， a q22 ，巳是第，_ + 1 个大于1 的q ( 1 i g ) 示意图： o o 0x0x0 00 x0 000 0x0x0 xx 由归纳假设，对于 _ ，x ：， 成立等式2 r - q 卜g ；，q i 和q ；分别为 研= 2 i - 1 ，1 2 i - 1s ， 和嘎= 2 i ，2 2 i ，) 的q 值 易知，因葺= + z ，x p = 一= l ，若= o ，则从，+ 2 ，走向x p ，其值经历 了一次从0 到i 的改变，而从一i 到+ l = 1 到+ 2 ，+ i = l ( ，+ 1 t + 2 i + l p ) ，其值 也经历了一次变化，故 而，而，x p 的奇偶分拆的q 值( 分别为g l 与q ：) 也成 立关系式2 ( ，+ 1 ) = 吼+ q 2 若= 1 ，则从，埘走向，其值没有变化，而从 - l ，小2 ，走向x p 其值由1 变0 再变1 ，经历了二次变化，也成立2 ( ，+ 1 ) = 吼+ 9 2 j ：海人学硕十学位论文 定理2 3 记范德瓦尔登数w ( n ，刀) = p4 - 1 ， p 】- aub ，a 与b 中皆无r 阶等差数 列存在，a = a ia 2 , - - , a 。) ，b = b i , 包，包 ，s + ，= p 添加0 点使它构成阶图g ，g 是这样构造的：0 与爿中每点订，相邻，0 与b 中每点匆不相邻。任取g 中二点x ，y ， 当l x - y l a 时它们相邻，当i x - y i b 时不相邻。考察每一个，i j p ，当j a ， 以工，表示使( j - a , ) a 的不同的口，的个数( 口，a ，口， j ) ：当j b 时，以j ，表示使 ( 一包) b 的不同的 包 的个数 ( 6 f b ，匆 - ，) 。记 乃= 二茎尝，乙= 喜互，l p 则有c 存在，1 c d ，则必有丁存在，使t t 兰甜( m o dp ) ，“d 它使 圆周c 上的每个整点 ，变成n ( m o d p ) ，a l 变成飘( m o dp ) 于是又可按( 1 ) 来 处理 砌，1 f 2 n 一1 ) ( i i ) 若呒( 2 n 一1 ，2 n 1 ) = 2 r l ，则类似上面，我们可证： 2 w ( n ，甩) ( 2 n - 1 ，2 n 一1 ) + 1 ，另由定义可得w ( n ，疗) ( 玎， ) ，于是本定理得证。 由以上所述可知，若能求得圆周上范德瓦尔登数的较好上下界，也便求得了 经典范德瓦尔登数w ( n ，刀) 较好的上下界。 定义2 5 设p 为奇数，长为p 的圆周上p 个数集合【p 】【= 1 ，2 ，p ，( 1 与p 相距1 ) 。 取【p 】( i ) = l ，3 ，5 ，p ，2 ，4 ，p l ，( 1 与p 相距为2 ) ； 取【p 】2 1 = l ，5 ，9 ，1 + 4 i ( m o dp ) ，0 i p 1 ) ： 取【p 】= l ，1 + 2 ，1 + f 2 ( r o o d p ) ，0 i p 1 ) 则称【p 】为【p 】。的第k 层奇 偶分拆，k 0 ，【p 】( o ) = 【p 】。 注 ：易知，当p 为素数，2 为p 的原根时，【p 】恰有i 1 ( p 1 ) 个是互异的。 例： 1 + 2 i ( m o d i1 ) = 【11 】( 1 = 【11 】1 6 ) = 1 + 2 6 i ( m o d l1 ) ) 1 + 4 i ( m o d i1 ) ) = 1 】2 = 1 】7 = 1 + 2 7 i ( m o d l1 ) ) 定义2 6 若长为p 的圆周上的2 一分拆【p 】。= a w b ，p 为素数，记其特征值 厂c ，= = ? ；茎三，p 彳a b ，而x p 有而= ，( 1 f q ) ，玉_ + 口l = + 口l ，( 1 f 口2 ) ，五= + 口i + 吒- - x , + 功+ 吨，( 1 f 呜) ， 上海人学硕1 ：学位论文 2 k l2 k l 五厂( 1 + 巳) = 州+ a j ) ，( 1 f 口2 。) ， = ij = l ( 9 为偶数) 若p ：羔q ，口i ，口2 ，中有_ r 个口2 ( 其余口一， a i = 1 ) ，则称圆周上的 2 分拆【p 】。= a w b 的o r 值为( g ，) 推论2 5 【p 】。的o r 值中g 必为偶数。 证：因为_ x p 时，显然存在前的某个吒x p ，故从1 到七有奇数部分加上 最后与x p 相同的部分就为偶数部分。若而= x ，x k x k + l ，则可改取后+ 1 和七分 别为起点与终点：取气+ l = 朋，x k + ，= y j ，1 f p ，y p = x k ，于是一蚱，故口 为偶数。 定理2 6 p 为奇数，k 0 ，记【p = l + f 2 ( m o dp ) ，0 i p - l 为【p 】。的第 七层奇偶分拆，【p 】= 爿u b ，= ：) i ，ea b ，t ，p ，x i x p 若记【p 】? 的 o r 值为( g ，r ) ，( q 们，o ) = ( g ，) ，则当，1 时恒成立圆周上奇偶分拆的 关系式：g 叩”= 2 r ，k 0 证： 易知，我们只须证明成立公式q ”= 2 r 即可。因为我们可把【p 】。的第k 层 奇偶分拆当作新的起点【p r ，它的r 。值厂= ，它的奇偶分拆的o 值 = 2 r = 矿“ 若，= 1 ，g 2 ( 五0 ) 设 a i 2 ， 一= 而= x 2 ，+ 口i ， ( 1 q ，2 i + a l p 1 ) ， = 五+ 口i = 而川+ d l ( 2 f + 1 十q p ) 易见，【p 】。的奇偶分拆【p 】1 1 ) 的q - r 值为 1 4 、pg 一 +七2 +强 口 一 ， 可用来证得q = 2 r 若总不存在 吼2 ，a k + l 2 ，那么已证明了，= 1 的情形，也易于用数学归纳法来证 明。 以上证得了q ”= 2 r 也即证明了q “= 2 r 定理2 7 若奇数p ( 力，力) ，【p 】。= 爿ub ，= ：) ，i e a b ，t r p ， 而x ，a 和b 皆不含圆周上的等差数列，【p 是【p 】。的第七层奇偶分拆，且q - r 值为( g ，) ，七0 ，贝0 t 亘有