（计算数学专业论文）有限阿贝尔群中的零和问题.pdf

囊鑫攀秘 掣 蠹丫差l 蚕蚕 匀i 蓑薹主抖_ 鬟矗；鞋l 一 萎#壁_ ，0 “；譬 墓舅基嚣 鬓誊蒌竖翼粪l h 墓楚 翳硒萋嚣瞿 薹惑禹萤矍 萧港蓦蒲 羞掣蓦量 毽驾囊堂 霉妻塑蓊 篱霸 篓篓里墓砭i m ! 耋耋i 掣妻勰毫薹i 叫 再誓誓纠 察嚣馨韩鹱嚣婴 符号说明 下面给出本文中常用符号代表的含义 1 对任一实数z ，m 表示不大于z 的最大整数；茹 表示不小于。的最小正整数 2 对任一序列s ，用i s l 表示s 的长度( 项数) 3 用磊表示n 阶循环群，磊，0 磊。o 0 磊。表示磊。，磊。，磊。的直和，当 礼1 _ n 2 一- = n k = 礼时，磊，o 磊。o o 磊 简记为磷 4 。一个序列s = ( o l ，0 2 ，) 的两个子序列t = ( 吼，。乜，o k ) ，1 t 1 ( i 。，和w = ( ，q 。，) ，lsj 1 矗s 南不相交是指0 1 ，i m ) n 扎，a ) = 庐( 空集) 5 设s = ( 。1 ，0 2 ，口k ) 是个序列令口( s ) = 冬l 吼若仃( s ) = o ，则称s 是个零 和序列t = ( 吼。，o 协，o 谝) ，正，霸，耳是s 的两两不交之子序列，用髓1 = s 一丑记s 的子序列( i l 。，o k ) ， f l ，k = 1 ，k ) 一0 1 ，一， ，归纳 地定义s 一孔一乃= ( s 一丑) 一乃，s 一噩耳= ( s 一丑一霉一z ) 一耳； 定义乃死= 乃+ 乃为s 的子序列合于一乃= 乃，归纳地定义五+ 孔+ 死= ( 丑+ 咒) + b ，五+ + 耳= ( 丑+ 一+ 耳一1 ) + 耳 6 用a 表示空序列 7 用 o l ，0 2 ，。】表示整数0 1 ，0 2 ，a 。的最小公倍数 8 对一有限群g ，用e ( g ) 表示其所有元的阶之最小公倍数。 9 定理、定义、引理、推论的编号方法为：定理2 3 1 表示第二章第三节的第一个定理， 其余类推 1 基本概念及定理 e g z 定理和d a v e n p o r t 常数是零和问题的两个起点。本章第一节介 绍了零和问题的概况以及本文结构；第二节介绍了数论及加性数论中的基 本概念及定理；第三节介绍了e g z 定理及其五种证明方法 1 1 零和问题的概况及本文结构 组合数论主要研究整数环z 或者抽象群g 的子集或者序列的组合性质。近几十年， 在以p e r d ；s 为代表的一批数学家的推动下，组合数论得到了很大的发展目前，已成 为国际上热门的研究内容之一国内的研究主要包含以下三个方面： ( 1 ) 零和问题；研究元素在a b e l i a n 加群g 中的序列( n 1 ，a 2 ，) 是否有， l ，2 ，n 使得f 符合指定要求且划吼= o ( 2 ) 子集和问题：给定a b e l i a n 加群g 或者整数环z 的有限子集a l ，a 2 ，估 计受限制子集和s = 口l + 0 2 + + 恢a ，且o l ，0 2 一，口。满足给定的限制条件 的下界。 ( 3 ) 覆盖问题：研究整数环z 的覆盖a = o 。+ 砜z ) ( 由k 个剩余类构成) 中模 n t ，n 2 ，礼具有怎样的特性，更一般地，对于群g 的左陪集覆盖虢= i g i ) 冬1 ，指标 n 1 = g ：g l ，礼= f g ：g d 满足什么样的规律 其中，设= 佃，1 ，2 ， 且z + = ( o ) ，对所有o z ，站z + ，令d ( 珏) = 口+ n z = z z l z 三o ( m d d n ) ) 则有限集a = a 。( ) k 1 称为z 的覆盖，如果z 中 的每一个整数都属于a 中的元素 本文中，我们主要讨论有限a b e l i a n 群中的零和问题，加性数论，图论和因数分解理 论为有限a b e l i a n 群中的组合问题提供了无穷无尽的源泉，零和问题就是当中很有意义的 一个这个领域有两个起点；1 9 6 1 年，p e r d i s ，g 饥抽u r g 和z 妇证明了下面的现被称 为e g z 定理的著名的结果：对于元素在循环群况中的任何序列( 毗，。2 ，0 2 。一1 ) ( 啦 未必互异) ，我幻都能找到一个集合c l ，2 ，2 n 一1 ) 且j 州= 船，使得淄口；= o 另一个开端是d a v e n p o r t 常数d ( g ) ，它表示满足下面条件的最小正整数t ：元素在g 中 且长为t 的序列中都包含非空零和子序列 工 骜蔓赛薹：；量噩垂至z 妻薹毒誊耋望；鸯誉霎薹囊囊墓辇雨篓嚣燕荦 ! 亨i 簦二墓l b 女e s 藿蓬鼯研昨醍至靼蓉霜岂酏蛟“纠獬= 臻嘴磴崾咋绡嘣j 幅侔亳 雾薹配蚕翥辂美警姆鲥盯鞋 j 塑氡理宝瞎怯噬忑。立蹙髓丁1 f 。肾色划邑 ；妻= l 目i i ；量搴；冀差篓i li 基裂鸵强d 删霹j 必潮孵戡嬲泌明啪i 罄霹塞霪甄i i l ：l 。镬箱蓝舅甜判塞蓥墨誊授圊羹丽萎蓄罂罄蔓= 守卸 朝两。辁q 垂羹礞 l 霉 ；蠹斧! i i i ；l ! ! ! ： i 殂二；i l ；鞲抬磋蕊鬣艇美手| j i 拓芸羁掣坠墨掣； 曩蚕眇副匿嗵坦世罔了嗡嚯淄嘣洱盈一i 自| 蚕l 目i i g ge = ! | | 薹l 。 ! ? _ _ ；i ；二；i g l i j “澎毛蓄茬裂蓄拜辨蜷秘霭翮毋稚骟兰鲥强蠢甏粤主：贯磊 琴生重别第构的瑶福套菇茸着。鱼黾搦澄嬖蔷l 笠娶捌圣晕型靶il 雾雾囊羹 薹蠢薹鏊i 雾茎要面鑫爹羲薹鎏羹霎。雾薹霎雾罄零等蠡稚鲤蠢。雾窆1 i 蠢彗塞妻 ! ； | g 筇右瞳? h 婆舅鞭晕受萋雾囊磊警蓉纂啬强蒂；i ： | ? 妻? 主鋈耄翼塑萋塞囊霉鎏篓 毫强鼍盟墨萋翼囊荔疆j 嚣葫；髦荔氟篓萤薹制r 毹鞘磊嘲示弱承加祜j 矗疆潦逻弹盐工磊堡囊鞘羹豪，融瓿翼鬻三焉氆逼溪垮愕磁噍截t 髀裕选爹基 ：嚣曼；蕊蘑；曼蠢娃薹：蕃尊j 香蕊翟蝗雾辫! 磊妻蓄型； 等晶曼囊；蟹轧 夯鎏鐾盈田讯弱笾蓄瓮；0 确羔型鞭曼雨寥晕掣f 争蚤要鬻群。 蠢院燮矍霞笃蔓醐髫髯呵曩嶷导 i 疆睫御诸i 憎h ；壹i 嚣i ，* ；。矗芝薹妻嘉 霸嚣墼瑟巍“髦薪箍菩丰集翼! i 墨i 蔓翼垂曩：l ；i ! ：翼篓慕菱萋薹；疆i ? 霾蓁i 辇l 篓莓令岔翠童舞：羹冀鍪嚣堪溷葡瑶馑筒荆浅要哗z 骂工蹲。霉善墓填韧印乖斑 鬈浠缘啦爱礓遇( 蓟爨薹l 稿以 证明很多结果下面给出e 变换的性质：设a ，b 是a b e l i 塞妻群g 中的非空子集，e 是g 中的任意元素， (a(e)，b(e)是(a， b)的e一变换，贝4(1) aa(e)，b(e)b(2) a(ej+丑(e)五+口(3) a(e)a=e+(bbii)、(4) 若a 和b 都是有限集，则i a ( e ) i + i b ( e ) l = l a i + i b j(5) 若ea且ob，则ea(e)且ob；i)定理12 2 ( c 塞c ：! i d e n p o r t t h e o | | m ) 设p 是一个素数a ，b 是磊中的非空子集，则 x 大连理工大学顼士学位论文：有限阿贝尔群中的零和问题 一个盒子含有两件或更多的东西 ( 2 ) ( 鸽笼原理的加强形式) 设吼，眈，一，是正整数如果把g l + 9 2 + + 如一n + i 件东西放入n 个盒子里，灵i 或者第一个盒子至少含有g i 件东西，或者第二个 盒子至少含有9 2 件东西，或者第n 个盒子至少含有件东西 当然，鸽笼原理还有别的形式； 推论1 2 3 ( 1 ) 如果把n ( r 一1 ) + 1 件东西放入礼个盒子中，则至少有一个盒子含有 r 件或更多的东西 ( 2 ) 如果n 个整数m i ，m 2 ，仇。的平均数驰地篙 血大于r 一1 ，则 整数m 1 ，m 2 ，m n 中至少有一个大干或等于r 定理1 2 ，7 ( 胁n s e y 定理) 设吼，翰，是正整数且砚2t ，驰2 ，铷2z ， 从而存在最小正整数( 口l ，匏，；t ) ，它仅依赖于g l ，9 2 ，和t ，并且具有下面 的性质：如果m ( q 1 ，口2 ，t 一，g n ；t ) 且s 是m 个元素的集合，把s 的亡- 元子集分布 在几个盒子中，那么或者有q 1 个元素使它们全部的扣元子集都分布在第一个盒子里， 或者有吼个元素使它们全部的扛元子集都分布在第二个盒子里，或者有甄个元素 使它们全部的t - 元子集都分布在第n 个盒子里 ( 9 1 ，q 2 ，；t ) 称为r a 皿s e y 数 1 3 e g z 定理及其证明 1 9 6 1 年，p e r d ；s ，g i z b u 曙和z i v 证明了下面现被称为e g z 定理的著名结果： 定理1 ，3 。1 1 q 对于元素在循环群磊哼的任何序列如i ，幻，盘加_ ) l 是整数贝i l ( i ) s ( 磁，) s 七f d ( 8 l p ( 巧) 一1 ) + 4 + k 一1 ( i i ) s ( 露) 曼2 4 n + 3 3 1 一1 ，其中n = 2 印 ( i i i ) s ( 露) 7 2 n + 女3 2 4 2 一1 ，其中n = 3 女p ( i v ) 设p 7 ，则8 ( 露) s2 5 9 2 n + 4 5 1 9 3 七一l ，其中佗= 6 幼， ( 8 ) f 4 0 】( i ) s ( 凌) = 1 9 ；s ( 乏) = 4 1 ( i i ) 9 l s ( 厨) 1 2 1 ；8 ( 瑶8 ) 3 0 0 2 拢 ( i i i ) s ( 霉) = d ( 3 d ) 矧捌) 2 1 7 9 d ，d d ，其中足够大， ( 9 ) 【1 3 设g 是秩为七，阶为n 的有限舢e f i 口n 群，r - 1 ( g ) ( 1 + 学) n 一1 2 3 几个组合常数之间的关系 在介绍组合常数的关系之前，先介绍几个定义； 定义2 3 1 ( 1 ) 设g 是指数为m 的有限a b e l i a n 群，j d ( g ) 表示满足下面条件的最 小正整数t ：元素在g 中的任何长为t 的序列中都包含长不超过m 的非空零和子序列， ( 2 ) 设g 是指数为m 的有限a b e l i a n 群，f ( g ) 表示满足下面条件的最小 正整数t ：对任意的t ，都有s k 。( g ) = m + d ( g ) 一1 _ 第2 章几个重要组合常数及它们之间的关系 引理2 3 3 6 】设g 是阶为n 的有限a b e l i a n 群s 是由g 中元素构成的长为n 的序 列。令 = ( s ) ，则o 。 ( s ) 我们将给出引理2 3 3 的简单证明，这个证明为解决类似问题提供了很有效的方法。 设最，& 是s 中的t 个不相交子序列，从s 中去掉研可得到子序列s & ，由 归纳法，定义s s 1 - 一& 为子序列( s s l 一最一1 ) 一最，0 = 2 ，t ) 当 n 时，引理2 3 2 显然成立 假设危n 一1 ，不妨设6 = 0 ( 否则我们就用序列山+ s 代替s ) 显然，我们可以 将s 重新排列成如下形式： s = ( o l ，。n + k 一 ，o ，一，o ) ，其中。的个数为 且啦o ，( i = l ，n + 一 ) 设是序列0 l ，o 蚪女一 ) 中最长的零和子序列由引理2 3 2 的假设可知， n + 一危一l i 矿i ，因此，i t 矿l n 一 若i 彤l 墨礼，则。可被表示成如下形式to = o + + o + 玎( w ) ，其中等式右边。的 个数为n 1 w l ，这也说明o 。( s ) 若l w l n + 1 ，对w 重复运用引理2 3 3 ，则能找到w 中互不相交的子序列磁满 足：口( 暇) = o ，1si m i ，o = 1 ，u ) 且i 1 吼一一w ，u 1 n 一1 设口表示满足1 w i 魄- 一t 砚1 n 一1 的最小整数t ： 则l 一矾一一矾i n 一1 且i w 一吼一一矾一1 l 礼 这说明n l l 彬一m 一- - 一眠f n l 眠f 礼一九 令甄= w m 一一峨，从而n 一1 i l n 一 所以有o = o + + o + ，其中等式右边。的个数为n i | 这也说明o 。( s ) 口 定理2 3 3 的证明：设t = ( 口l ，。d ( g ) 一1 ) 是元素在g 申且长为d ( g ) 一1 的 序列，o 岳( t ) 令s = ( 口1 ，d 2 ，o d ( g ) “o ，o ，一，o ) ，其中。的个数为n 一1 显 然，o 芒。( s ) ，从而( g ) n + d ( g ) 一1 ；在引理2 3 2 中令忌= d ( g ) 一1 ，即得 s 。( g ) n + d ( g ) 一1 从而( g ) = 礼十d ( g ) 一1 口 2 4 s ( 兹) 的计算及主要结果 对所有有限a b e l i a n 群计算s ( g ) 的值是非常困难的，人们的许多工作都集中在讨 论s ( 露) 的值及相关结果上，这节中我们详细介绍 1 9 8 3 年，a k e m n i t z 提出下述猜想： 猜想2 4 1 【4 0 】对所有整数n ，都有s ( 露) = 轨一3 1 5 缝里王盔堂垦主堂垡堡塞：查堕堕堡堡登! 堕里塑塑璺 上述4 n 一3 不能换成4 礼一4 ，因为由( o ，o ) ，( o ，1 ) ，( 1 ，o ) ，( 1 ，1 ) 各重复n 一1 次构成的 长为4 n 一4 的序列中不包含长为礼的零和子序列k e m n i t z 证明了s ( 露) = 4 p 一3 ， 其中p 一2 ，3 ，5 ，7 因此，由定理2 2 1 可知s ( 霹) = 4 扎一3 ，其中礼= 2 4 3 6 5 。一。尽管在 4 中已经证明了：对所有整数儿，都有s ( 霹) 6 扎一5 ，且当p 为足够大的素数时，有 s ( 露) 5 p 一2 ，但是猜想2 4 1 至今仍未被证明不过，围绕这个猜想已经有了很多结 果，下面将详细论述 2 0 0 0 年，三冗6 忍o 取得了重要突破，他仓4 造新方法证明了 定理2 4 1 ( 5 3 猜想2 4 1 中4 礼一3 换成【等】时结论正确，礼为素数时，4 扎一3 还可 换成4 n 一2 三r 6 扎o 得到上述结果的关键性引理如下： 引理2 。4 1 设f 为域，礼为正整数以y 表示全体从 0 ，1 p 到f 的函数所构成的 f 上的线性空问，则y 有组基底 l ，2 2 ，z 。) = n i ；f 戤( ，( 1 ，2 ，n ) 。 定理2 4 2 2 8 】若s ( 露) = 4 礼一3 ，且n 垒竺蛆杀卫生墨，m 2 ，则s ( 穰。) = 4 礼m 一3 引理2 4 2 【4 1s ( z ：) s6 礼一5 引理2 4 3 2 8 】设( 口1 ，口2 ，o “一3 ) 是元素在露中且长为4 n 一3 的序列，若此序列 中有一个元素至少重复n 1 次，则此序列中必定存在一个长为礼的零和子序列 证明；不失一般性，设0 1 = 0 2 一= o 。一1 = o ，考虑长为3 礼一2 的序列 ( 一o ，。+ l a ，口4 。一3 一口) 由定理2 3 1 ( 2 ) 知，此序列中存在订i 1 i 2 i 。 4 礼一3 满足；：1 ( 。d 一口) = o ，其中1sc n 因此，稳 l + 。幻+ + 啦。+ 口+ o + + 。= o ， 其中。的个数为礼一c 口 定理2 4 2 的证明：首先证明s ( 霹。) 冬4 礼m 一3 设s = ( 0 1 ，口2 ，吼。一3 ) 是元 素在瑶。中且长为4 n m 一3 的序列，我们只须证明此序列中包含长为n m 的零和子序 列 设妒是从爱。到瑞的同态映射，其中女e r ) = 露对罨中的任意元素g ，用岛表 示由满足咖( 吼) = g 的所有o 构成的s 的子序列设 s 满足i i = m o z 1 岛怕z 翥) ， 下面我们证明s 中至少存在4 n 一3 个长为m 且不相交的子序列且每个子序列的和都在 e r ( 咖) = 露中分如下几步讨论： 第一步：我们能找到s 一最中一些长为m 的不相交子序列月z ，疡，觑( 七o ) 满足盯( r f ) e r = 露若s 一& 一咒l - 一凰中不包含长为m 且和在七e r ( ) = 露 中的子序列，则由引理2 4 2 知，s 一既一只l 一总l 6 m 一6 第二步：令= s 一品一r l 一风，我们要说明中的u o ) 个不相交的 非空子序列a t ，a 2 ，也和w 中的钍个不相交的子序列b 1 ，b 2 ，玩满足下面条 件( i ) 和( 虮 ( i ) 让= o 或对每个口= 1 ，2 ，让，a + 玩的和都在e r ( 妒) = 露中，且j 山+ 玩f = 1 6 塑兰查兰堡兰兰些堡兰塑丝塑塑查至笪墨亘圭茎壅耋兰堡堑丝堑壅 低温贮减下叶片的f v f m 保持稳定，后期在正常范围内略有下降。表明低温显著 抑制了叶片f “f m 值的下降( j p 0 0 5 ) 。 2 2 5 不同贮藏温度下切花菊叶片f v f m 的变化 f v y f m 的变化是激发能传递至开放的反应中心的比例受调控变化后引起的， 植物组织衰老过程中由于受体不能承受整个高能电子流，p si i 能通过电子传递链 将它还原，使激发能传递至开放的p si i 中心的效率降低( d e m m 堙等，1 9 9 6 ) 。 如图2 - 6 所示，2 5 下，处理后6d 内，基部叶片l 1 ，l 2 ，l 3 的f v f m 分别由 o 6 7 9 、o 6 9 3 、o 6 8 7 降至o 4 4 5 、o 4 5 8 和o 4 6 5 ：近花端时片l 4 ，l 5 ，l 6 的f v ，f m ， 下降较平缓，分别由初始的0 7 1 2 、o 7 1 4 、o 7 2 6 ，至1 0d 降至0 5 2 4 、0 5 4 0 和o 6 0 8 ： l 处理可显著抑制叶片的f v f m 值下降( p o 0 5 ) 。 1 0 0 e 告o u - o 0 0 l 1 一国一农絮一田一。 西一敝= ：一。一。 l 1【l2 一日一母一田口 l 3 ：旨一圆寸固鼋 匡蜀 。 印一一一毋8 l 6 d a y sa 他rt r e a t m e n t 图2 5 各叶位不同处理f 胛m 的变化情况 f i g 2 5t h ec h 姐g e o ff 胛mo nk a v 黜w n hd i 凰n n t 臼坤a t l e 吣 1 h 船虹如rm 皿l e nd e g 憎e x 3 序列的结构 前两章研究的问题基本可以归为两类： 问题1 ：设g 为有限a b e l i a n 群，确定最小的正整数t ，使得：元素在g 中的长为t 的序列中总包含一个零和子序列即确定d a v e n p o r t 常数d ( g ) 问题2 ：设g 为有限a b e l i a n 群，确定最小的正整数t ，使得：元素在g 中的长为 t 的序列中总包含一个零和子序列t 满足下面的条件之一： ( 1 ) l t l 茎e 茁p ( g ) ( 2 ) l t l = e 印( g ) ( 3 ) l t i = j g f 本章中，对应于上面的问题，我们考虑： 问题1 4 ：确定元素在g 中的不包含零和子序列的最长序列s ( 即i s l = d ( g ) 一1 ) 的 结构 问题2 。：确定元素在g 中的不包含零和子序列t 的最长序列s 的结构其中t 是 下面情况之一t ( 1 ) t i e 印( g ) ( 2 ) i t i = e 印( g ) ( 3 ) i t = j g 问题2 4 ( 1 ) 是p me m d e 研究长为3 礼一3 且不包含长度不超过n 的零和子序列 的序列结构时提出的问题1 + 是在非唯一问题分解的研究中产生的问题2 + f 2 ) 最先由 g a o 【4 1 】提出问题1 + ，2 ( 1 ) ，2 + ( 2 ) 至今仍未被解决，不过已经有能解决这些问题的猜想 和支持这些猜想的结果 3 1 基本概念及相关结果 本节中我们主要介绍基本概念及相关结果； 定义3 1 1 ( 1 ) 若序列s 是一个零和序列且s 中不包含真零和子序列，则称s 是最 卜零和序列 ( 2 ) 若序列s 是零和序列且l s i 【1 ，e 印( g ) ，则称s 是短零和序列。 2 1 盔蔓望三盔兰堡主堂垡! ! 窭：宣垦匝墨叠壁! 堕墨塑堕望 一 设妒是从z 言到露的自然同态且k e r 毋= 霹对罐中的每一个元素g ，用s 表 示由满足妒( 吼) = g 的所有啦构成的s 的子序列记s = 岛。岛：品，其中f 岛，i l 岛。f f 1 1 设屯= i & f 0 = 1 ，2 ，r ) ，因为s ( z 言) = 1 9 ，所以能在s 中找 到8 个不相交的子序列乃，霸满足：l 正f = 3 且汜) 0 1 ，8 ) ) 是罐中的零 和子序列因此，a ) k e r ( ) = 罐，0 = l ，8 ) 因为s 中不包含长为6 的零和子 序列且s ( 霉) = 9 所以， 盯( 乃) ，盯( 正) ，盯( 霸) 是互不相同的( 3 2 1 ) 其中( 丑如) - 1 ) 中不包含长为3 的零和子序列。因为口( 霹) = 1 0 ，所以 咖( s ( 丑乃) - 1 ) = a ；n ；磋a 。( 3 2 2 ) 其中d t ，0 ：2 ，。在露中，且是互不相等的 我们断言： 如果i 岛。i 4 ，则s 0 = 舻i 其中，九s ( 3 2 3 ) 事实上，假设 岛。i 4 ，但s 鲥中至少包含两个不同元素不失一般性，我们假设 ( 0 1 ) = ( 0 2 ) = ( 0 3 ) = 池) = 肌且口i 令t = s ( 。l ，口2 ，口3 ，0 4 ) ，因为5 ( 霹) = 1 9 ，所以能在r 中找到7 个不相交子序列丑，正，乃满足l 五f = i 乃f 一= 1 乃i = 3 且庐亿) ，“= 1 ，2 ，7 ) 都是霹中的零和子序列因此，仃慨) k e r = 砑，( = 1 ，7 ) 若存在1 f 7 满足：盯( 靠) = 仃仍) ，则以丑是长为6 的零和子序列， 矛盾 因此，可假设盯( 噩) ，盯( 乃) 是互不相同的又已知口1 + 0 3 + 毗和0 2 + 口3 + 。4 都在驾中，且d 1 + n 3 + 0 4 口2 + 0 3 + a 4 ，从而可以推出 。1 + 0 3 + 0 4 ，0 2 + 锄+ ) n 矿m ) ，盯( 乃) ) 0 不失一般性，假设口，+ 口a + 0 4 = 仃( 乃) ，则( 0 1 ，0 3 ，口t ) 丑是长为 6 的零和子序列，矛盾( 3 2 3 ) 得证 显然，由( 3 2 3 ) 可以得到： 黾i 5 对j o ，l ，2 ) ，定义0 = mj 1 i nf 岛一三jm o d3 ) 我们断言t 2 0 1 ，2 1 = 1 ，2 2 = 8 2 4 ( 3 2 4 ) ( 3 2 5 ) 第3 章序列的结构 下面证明z l = 1 记i 1 = 3 吼+ m i ，( i = 1 ，r ) ，其中o m i 2 且m 和吼都是整数显然， 我们在& 中能找到吼个不相交的子序列满足t 每一个子序列的和都在k e r 中且这些 子序列的长都为3 ，用这种方法，我们总共能在s 中找到q l + q 2 + + 个不相交的子 序列正，正i + q 2 + 斗和 令w = s ( 五五。+ 驰+ 拇) ，则( ) = ，y 幢历屈，其中饥， 卢圹一，屈。是互不相同的重复运用9 ( 霉) = 1 0 ，我们在7 l 伪m 。中能找到足够多的不 相交零和子序列m - ，眠，( 让o ) ，其中l 尬i = 3 ，0 = 1 ，扎) 因此，在中能找 到2 u 个不相交子序列满足：这些子序列的长都为3 且每一个的和都在k e r 妒= 雹中 从w 中去掉这2 “个子序列，剩下的子序列记为溉，则庐( 矾) = 赁幢风屈。， 其中f 3 = f 2 3 “且，y l 仇m 。不包含长为3 的零和子序列由9 ( 霉) = 1 0 知，f 3s 9 又由( 3 2 2 ) 知f 3 8 因此，1 3 = 8 或9 显然2 3 + l l 三4 1 三2m o d3 ，从而l l 1 下 面假设c l 1 ，则f l 2 我们分两种情况讨论： 情况1 _ f 3 = 8 因为2 f 3 + 2 1 兰4 1 三2m o d3 且l l 2 ，所以f 1 4 又9 ( 霉) = 1 0 ，我 们能找到7 l 舶卢l 阮中长为3 的零和子序列q l 和饥竹风风中长为3 的零和子序列 q 。满足：q - 和q 。是不相交的设r - = 1 ( q 1 ) ，r 2 = 砂_ ( q z ) 且啊= 甄( r t 岛) ， 则口( 丑t ) ，盯( 岛) 在霉中且( i 班) 中至少有7 个元素出现两次，与( 3 2 。2 ) 矛盾 情况2 3 = 9 因为f l 2 ，由g ( 霹) = l o ，我们能找到7 l 帕卢l 中长为3 的零和 子序列曰1 和，y 1 - t 伪岛中长为3 的零和子序列q 2 ，满足：q 1 和q 2 是不相交的设 r l = “( q 1 ) ，r 2 = 庐_ 1 ( q 2 ) 且帆= i ( r 1 冗2 ) ，则a ( r 1 ) ，盯( | r 2 ) 在雹中且曲( n ) 中至多有7 个元素出现两次，与( 3 2 2 ) 矛盾 口 下面证明f 2 = 8 由( 3 2 2 ) 知f 2 8 ，现在我们只须证明j 2s8 假设f 2 9 ，因为f l = 1 且 2 f 3 + e i 三4 l 三2m o d3 ，我们得到z 2 = 1 1 + 3 口，扣o ) 由9 ( 霉) = 1 0 知，7 i 他仉2 中存在 个长为3 的不相交零和子序列从而我们能找到s 中2 个长为3 且不相交 的子序列噩，乃。满足：矿伍) 0 = 1 ，2 ) 在z 耆中设w j = w ( 互正。) _ 。， 则咖( w j ) = ，y 7 矗崩现在总共能找到s 中! ! 三p = 6 个长为3 的不相交子序列 丑，正，乃，噩，死，霸满足：每一个子序列的和都在罐中，且由( 3 2 1 ) ，这6 个子序列的 和是互不相同的由g ( 霉) = l o ，我们能在曲( t 确) 中找到一个长为3 的零和子序列q 1 分下面两种情况考虑； 情况1 q 1 中包含尻不失一般性，令q l = ，y 1 0 7 l i 风设r l = _ 1 ( q 1 ) 且满足； l r l l = 3 ，盯( r 1 ) 在硪中因为口( z ) = 1 0 ，所以( w o ) q 1 1 1 中也包含长为3 的零和子序 列q 2 不失一般性，令q 2 = 怕拍饥o ，设岛= 毋_ 1 ( q 2 ) ，且满足i r 2 i = 3 ，盯( r 2 ) 罐记 第3 章序列的结构 s ( 霹) = 9 所以， 盯) ，盯( 马) ，a ( 乃) 是互不相同的( 3 ，2 ，6 ) 其中妒( 乃霸) _ 1 ) 中不包含长为3 的零和子序列因为9 ( 露) = 1 0 ，所以 多 磊) _ ) = a 霹盘；霹( 3 2 ，7 ) 其中q ，q 。，n 9 在z ；中，且是互不相等的 同样地，我们可以证明： 如果l 岛；i 4 ，则= 驴其中， s 显然，由( 3 2 ，8 ) 可以得到： i 岛；l 5 对j o ，1 ，2 ) ，定义0 = 俐1 i r j 矗i 兰jm o d3 ) 我们断言： l o = 0 ，i 1 = 0 ，c 2 = 9 ( 32 8 ) ( 3 2 9 ) ( 3 2 1 0 ) 下面证明f 1 = 0 记i 瓯= 3 吼+ m l ，0 = l ，r ) ，其中o m t 2 且m i 和m 都是整数显然， 我们在s 。中能找到m 个不相交的子序列满足，每一个子序列的和都在k e r 中且这些 子序列的长都为3 ，用这种方法，我们总共能在s 中找到q 1 + q 2 + + q r 个不相交的子 序列乃，马，+ 。+ + 令w = s ( 冗- 蜀，+ 即+ 咖，) ，则妒( 1 矿) = 7 幢尻屈。， 其中7 l ，讹，m 。，p l ，屈。是互不相同的重复运用g ( 研) = 1 0 ，我们在，y l 讹m 。 中能找到足够多的不相交零和子序列尬，尬。，( 札o ) ，其中l 舰i = 3 ，0 = 1 ，“) 因此，在w 中能找到2 u 个不相交子序列满足：这些子序列的长都为3 且每一个的和都 在k e r 簪= 雹中。 从中去掉这2 u 个子序列。剩下的子序列记为1 ，则庐( - ) = 7 镌卢l 岛， 其中f 3 = f 2 3 u 且7 l 加不包含长为3 的零和子序列由g ( 瑶) = 1 0 知，2 3 9 又由( 3 ，2 7 ) 知2 3 9 因此，f 3 = 9 假设f 1 0 ，显然2 f 3 + f 1 三4 2 三0m o d3 从而 f l 1 ，因为f 3 = 9 且f l 1 ，由9 ( 霉) = 1 0 ，我们能找到饥帕岛中长为3 的零和子 序列q 1 设r l = 曲_ 1 ( q 1 ) ，w l = r i l ，则仃( r 1 ) 在罐中且咖( 啊、) 中至多有7 个元 素出现两次，与( 3 2 7 ) 矛盾 口 盔垄里塾兰堡圭兰垡丝窒! 童里堕里堡登主塑墨塑堕里 c o u n c i li 8 r a e l1 0 f ( 1 ；l l t ；? ；i 羹黼妻至耄l 玎藜 ；| l 蜓；需叭强；u 曼；荔静誊i ；墨萋；莲i i 甚曼。誊i 董 嵯旧i ! i 藉荽摹稽- 寸薹，整囊 - 矗4 h r j | 0 1 i i ) 亨i 囊鼙霉崔| 叫薹。蔓? 謦至t 亨霪窭? j 甍鲞茎争；誊；纛! “篓喜i 】参擎；j 譬i 薹冀引毫雒蚕i 7 蠢f r ，l 岛j = 2 ) i ，其中码+ 磋= f 2 l = l i 1 1se r ，1 & l = 4 ) l 且磕= l t 1 1 t 茎r 】1 s 。l = 1 ) 1 ，其中l + l = 1 1 f 6 = m i l i r ，l 岛。i = 3 ) l 且瑶= m 1 1 兰 r ，i i = o 扎其中玷+ 略=f o 首先，我们证明6 碹8 显然，碹f 2 = 8 ，所以只须证碹6 设码5 ，不 失一般性，只考虑硅= 5 显然可知磕= 3 ，因为f 0 + z i + f 2 = 9 或1 0 ，我们只须考虑 酷= l，玷= 1 从而可记s = 岛。岛。岛，。，但i 岛。s 。岛，。i = 3 8 而旧= 4 1 ，矛盾， 理6得证 在证明定理3 2 1 之前，先看一个引理： 引理32 2 设s 是元素在露中的长为4 1 的序列，s 中不包含长为6 的零和子序 列若 l s i = 3 ，则对 s ，有品= 舻 证明： 由i 岛i = 3 可知z 5 = 1 又因为码6 ，可得西( s ) 形为坩坩荫前嵋嚼矿 或7 增啸蝣哺饷9 3 对于这两种形式，可以用相似的方法证明因此，只考虑第一种 形式； 下面假设f 岛f = 3 ，但岛中至少包含两个不同元素不失一般性，假设( a - ) = 妒( o2 ) = 毋( 口3 ) = g 且0 1 n