（运筹学与控制论专业论文）完美差族的存在性及其相关问题.pdf

北京交通大学硕士学位论文中文摘要 中文摘要 完美差族是组合设计理论中一个重要的概念是具有某种特殊性质的一类差 族，它可用于构造循环s t e i n e r2 一设计c ( v ，k ，1 ) ；此外，完美差族与完美差集合系统 具有紧密的联系，它们在射电天文学、图论、实验设计、数字通讯以及计算机编 码等重要领域都有广泛的应用 本论文主要研究具有特定参数的完美差族、有向完美差族、完美差集 合系统的存在性等相关问题，给出了一些关于z 知中( g v ，g ，k ，1 ) 一有向完美差族 与乙。中( g l ，g ，3 ，1 ) - 有向完美差族以及( m ，k ，0 系统( k = 4 ，5 ) 的新的存在性结 果 全文共分五章 第一章简要介绍完美差族及其相关问题的研究背景，给出完美差族、有向 完美差族、完美差集合系统、加性置换序列、( m ，k ，0 一系统及其分裂点等内容的 基本概念及已有的相关定理和结论 第二章对于任意正整数g ，给出知中( g v ，g ，k ，1 ) 一有向完美差族存在的一个 必要条件并予以证明 第三章首先给出乙，中( g v ，g ，3 ，1 ) - 有向完美差族存在的必要条件，其次，列 出磊，中c g v ，g ，3 ，1 ) - 有向完美差族的两类存在性结果以及其他类的某些小阶数的 结果 第四章首先列出( m ，k ，c ) 一系统存在的必要条件及一些已知的存在结果，其 次，利用已知的某些存在结果和第一章中所述的知识，来直接构造和递归构造一 些新的( m ，k ，c ) 系统( k = 4 ，5 ) 第五章总结本文得到的主要结果，并提出完美差族及其相关内容可待进一 步研究的问题 关键词：完美差族；有向完美差族；完美差集合系统：加性置换序列；分裂点； ( m ，k ，c ) 一系统 分类号：0 1 5 7 2 北京交通大学硕士学位论文 a b s t r a c t p e r f e c td i f f e r e n c ef a m i l yi sa l li m p o r t a n tk i n do fc o m b i n a t o r i a ld e s i g n s a n di tc a n b eu s e dt oc o n s t r u c tc y c l i cs t e i n e r2 - d e s i g nc ( v ，k ，1 ) i th a sc l o s er e l a t i o n s h i pw i t h p e r f e c ts y s t e mo fd i f f e r e n c es e t s ，w h i c hh a v eb e e na p p l i e di nt h es i g n i f i c a n tf i e l d so fr a - d i o a s t r o n o m y , g r a p ht h e o r y , e x p e r i m e n t a ld e s i g n ，d i g i t a lc o m m u n i c a t i o na n dc o m p u t e r c o d i n g ，e t c i nt h i st h e s i s ，t h ee x i s t e n c eo fp e r f e c td i f f e r e n c ef a m i l i e s ，d i r e c t e dp e r f e c td i f f e r - e n c ef a m i l i e sa n dp e r f e c ts y s t e m so fd i f f e r e n c es e t sw i t hc e r t a i np a r a m e t e r sa n do t h e r r e l a t e dp r o b l e m sa r ei n v e s t i g a t e d s o m en e we x i s t e n c er e s u l t so n 国，g ，k ，d - d i r e c t e d p e r f e c td i f f e r e n c ef a m i l i e si nz 如， ，g ，3 ，1 ) 一d i r e c t e dp e r f e c td i f f e r e n c ef a m i l i e si n 磊v a n d ( m ，k ，c ) - s y s t e m s ( k = 4 ，5 ) a r cp r e s e n t e d t h e r ea r ef i v ec h a p t e r si nt h i st h e s i s i nc h a p t e r1 ，w ei n t r o d u c es o m eb a s i cd e f i n i t i o n sa n ds o m ek n o w nc o n c l u s i o n so f p e r f e c td i f f e r e n c ef a m i l y , d i r e c t e dp e r f e c td i f f e r e n c ef a m i l y , p e r f e c ts y s t e mo f d i f f e r e n c e s e t s ，a d d i t i v es e q u e n c eo fp e r m u t a t i o n s ，( m ，k ，c ) s y s t e ma n di t ss p l i t , e t c i nc h a p t e r2 ，an e c e s s a r yc o n d i t i o nf o rt h ee x i s t e n c eo f ( g v ，g ，七，1 ) - d i r e c t e dp e r f e c t d i f f e r e n c ef a m i l i e si nz 如i so b t a i n e d i nc h a p t e r3 ，t h en e c e s s a r yc o n d i t i o n sf o rt h ee x i s t e n c eo f ( g v ，g ，3 ，i ) 一d i r e c t e d p e r f e c td i f f e r e n c ef a m i l i e si n 乙va l eg i v e n ，a n ds o m ee x i s t e n c er e s u l t so n ( g v ，g ，3 ，1 ) - d i r e c t e dp e r f e c td i f f e r e n c ef a m i l i e si n 知a r es h o w n i nc h a p t e r4 ，t h en e c e s s a r yc o n d i t i o n sf o rt h ee x i s t e n c eo f ( m ，k ，c ) 一s y s t e m sa l e s h o w na n ds o m ek n o w ne x i s t e n c er e s u l t sa r el i s t e d b e s i d e s ，a p p l y i n gs o m ek n o w n r e s u l t sa n dt h er e l a t e dc o n t e n t sm e n t i o n e di nc h a p t e r1 ，s e v e r a ln e wr e s u l t so n ( m ，k ，c ) - s y s t e m s ( k = 4 ，5 ) a r eo b t a i n e db yd i r e c tc o n s t r u c t i o n sa n dr e c u r s i v ec o n s t r u c t i o n s i nc h a p t e r5 ，t h em a i nr e s u l t so ft h i st h e s i sa r es u m m a r i z e d ，a n df i n a l l yt h ef u r t h e r r e s e a r c hp r o b l e m sa r ep r e s e n t e d k e y w o r d s ：p e r f e c td i f f e r e n c ef a m i l y ；d i r e c t e dp e r f e c td i f f e r e n c ef a m i l y ；p e r f e c t s y s t e mo fd i f f e r e n c es e t s ；a d d i t i v es e q u e n c eo fp e r m u t a t i o n s ；s p l i t ；( m ，k ，c ) 一s y s t e m c l a s s n o ：015 7 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。 特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者躲弘研 签字隰砷年石月2 ：7 日 导师签名： 签字日期：饰妾7 。7 年6 月砻 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 学位论文作者签名弘四 一期：刁年6 月穸日 致谢 本论文的工作是在我的导师常彦勋教授的悉心指导下完成的，无论是在科 研、学习上，还是在平时的生活中，他都给予了我无微不至的关怀与鼓励当我在 课程学习中遇到难点时，常老师总是耐心地举出实例进行讲解：当我在科研上遇 到困惑而停滞不前甚至消沉时，他总是不厌其烦地给我提出新的建议，鼓励我开 拓思路、大胆细心；他还教育我们要谦逊做人，并且以身作则常老师严谨细致、 一丝不苟的作风一直是我学习、工作中的榜样：他循循善诱的教导和不拘一格的 思路给予我无尽的启迪；他严谨的治学风格，广博的知识，精益求精的科研作风， 敏锐的学术思想和忘我的工作精神影响并鞭策了我，是我今后工作与生活中一笔 极大的财富在论文选题、研究、定稿的过程中，常老师自始至终给予我大力的 支持和无私的关怀在此谨向常老师表示我最衷心的感谢 感谢王小苗师姐对我的帮助和指点，无论是在平时的学习，还是在论文的写 作中，她都给我提出了很多宝贵建议，在此向小苗师姐表示真诚的感谢此外，在 撰写论文期间，周君灵老师、单秀玲老师、冯破老师以及吴艳、马增花、李靖 尘、林伟伟、封二强、王晓等师兄师姐都给予我热情的帮助，我也从中学到很多 知识，在此向他们表达我的感激之情 同时还要感谢在两年的研究生生活中帮助过我的所有的人感谢授课的所有 老师，是他们使我夯实了数学基础，给予了我科研的前进动力：感谢同窗，两年来 我们在生活中互帮互助，共同学习、共同进步：感谢亲朋好友给予我的关心、支 持与鼓励，是他们无私伟大的爱赋予我积极乐观的态度和克服困难的勇气 最后，感谢各位专家和学者在百忙之中审阅我的论文我愿意认真听取专家 的宝贵意见，在今后的学习工作中不断改进 北京交通大学硕士学位论文 1 1 背景介绍 第1 章引言 第1 章引言 差族是差集概念的自然推广，差族方法是构作b i b 设计的最常用也是最有 效的方法之一完美差族是具有某种特殊性质的一类差族，它可用于构造循 环s t e i n e r2 设计c ( v ，k ，1 ) t 1 9 1 一个( y ，k ，1 ) 完美差族( 其中，= k ( k 1 ) m + 1 ) 等价于一个( 朋，k ，1 ) 一系统，完美差族与c = l 的正则的完美差集合系统密切相 关d 9 2 0 射电天文学中，在一些连续的行星方位上，可用一组可移动的天线来测定 从宇宙空间中不同信号源发出的无线信号的频率这就涉及到要调节这组可移动 的天线的位置，以符合特定的条件要求，从而准确地测定出所需结果最初，由计 算机可搜索出部分解决方案，但当多于4 条天线和5 个方位时，计算机搜索就需要 花费很长的时间由此，j c b e r m o n d ，a k o t z i g ，j t u r g e o n 等人提出了完美差集 合系统的概念，将这个问题抽象化为一个组合学问题加以研究，从而使得该问题 得到了较为理想的解决具体相关内容可参考文献1 5 , 7 , 8 上世纪七八十年代，一些学者对完美差族和完美差集合系统做过较为深 入的研究：j c b e r m o n d ，a k o t z i g 和j t u r g e o n 给出( y ，k ，1 ) 完美差族存在 的一个必要条件【5 1 ；j e s i m p s o n 等人给出了( m ，3 ，c ) 系统存在的充要条件嘲； 以t s k o l e m 命名的s k o l e m 序列以及之后的l a n g f o r d 序列的概念，对于( m ，3 ，d 一 系统和( g v ，g ，3 ，1 ) 有向完美差族的构造都起到了重要作用；a k o t z i g 和p j l a u f e r 改进了( m ，5 ，c ) 系统存在的必要条件【1 刀；p j l a u f e r 和j m t u r g e o n 对著 名的p a i i e r d o s 猜想进行了证明【1 8 1 ；j a b r h a m 和a k o t z i g 对加性置换序 列进行了一些研究【1 2 1 ，j t u r g e o n 给出了加性置换序列长度的上界 2 7 1 ；d g r o g e r s 对k = 3 ，4 时( 埘，k ，c ) 系统的分裂点进行了初步的研究，并提出运用乘法 定理和分裂点相关的定理，由小阶数的完美差集合系统构造较大阶数的完美差集 合系统【刎；j a b r h a m t 3 】和r m a t h o n l l 9 1 提到并列举了某些小阶数的加性置换序 列的存在性，用某些完美差集合系统构造一些特殊阶数的加性置换序列，以及由 小阶数的完美差族( 或完美差集合系统) 与特定阶数和长度的加性置换序列、 相应的具有分裂性质的系统，共同递归构造大阶数的完美差族( 或完美差集合系 统) 的方法；a k o t z i g 和p j l a u f e r 列出了由已知小阶数的加性置换序列递归构 造相应大阶数的加性置换序列的方法【1 6 1 ：等等 到九十年代，d g r o g e r s 较为集中系统地研究讨论了严格的完美差集合 系统，非正则的严格的完美差集合系统以及具有分裂性质的非正则的严格的 北京交通大学硕士学位论文第l 章引言 完美差集合系统等内容【1 2 1 3 2 1 2 2 ，2 3 二十世纪初，yc h a n g ，l j i 。ym i a o ，j y i n 和r e h a m 等学者在p 为素数，n 较小时的( n p ，n ，4 ，1 ) 一差族和( n p ，n ，5 ，1 ) 差 族的存在性等方面的研究取得了很大进展【9 i o 1 1 1 但对于( n p ，n ，4 ，1 ) 完美差族 与( n p ，n ，5 ，1 ) 完美差族的研究，目前已知结果很少到目前为止，长度大于4 的加 性置换序列的存在性研究，以及k = 5 时( r n ，k ，c ) 系统的分裂点的存在性研究等内 容尚无相关文献可供参考 完美差族和完美差集合系统在图论、实验设计、数字通讯以及计算机编 码、译码等重要领域也有广泛的应用j a b r h a m 在文献1 3 】中提到完美差集合系 统在图论中的应用，即完美差集合系统与图的优美计数之间的关系具体相关的 内容可参考文献 6 , 2 5 , 2 6 , 2 8 】等 前人对完美差族、完美差集合系统、加性置换序列等内容研究得已较为深 入细致，但它们的存在性结果还有待进一步扩大本文将给出( g v ，g ，k ，1 ) 一有向完美 差族存在的一个必要条件并予以证明；列出( g ，g ，3 ，1 ) 有向完美差族的两类存在 性结果以及其他类的某些小阶数的结果；此外，利用直接构造和递归构造方法得 到了一些( m ，k ，c ) 系统( 七= 4 ，5 ) 的存在结果 1 2 基本概念 差族是组合设计理论中一个重要的概念，差族方法是构作其它组合设计的最 常用也是最有效的方法之一下面给出差族的概念 定义1 2 1 设g 为 ，阶a b e l 群，其运算为加法设m 为正整数，又设勿为 由g 的m 个子集a f = 西l ，如，呶l ，l fsm 所组成的子集族，其中各 个a f ( 1sfsm ) 叫做初始区组( 或基区组) 如果g 中任一非零元a 都恰好有a 次 表成如下形式的差：a = 如一幽，l f m ，1 工z k ，j z ，则称9 为g 中的一 个( 1 ，k ， ) 一差族( d i f f e r e n c ef a m i l y , 简记为d f ) 关于v 阶a b e l 群g 中( y ，k ，a ) 一差族的存在性，有下述必要条件 引理1 2 1 【划若存在g 中的( 1 ，k ，a ) d e 则 a ( v 一1 ) 兰0 ( m o dk ( k 1 ) ) 完美差族、有向完美差族与完美差集合系统等内容紧密相关下面介绍它们 的基本概念 定义1 2 2 设9 为由z l ，中的m 个k 元子集a j = 西l ，d a ，如l ，0 = 西l 如 比，l f m 所组成的子集族，y = k ( k 1 ) m + l ，如果所有k ( k 1 ) m 2 个 2 北京交通大学硕士学位论文第1 章引言 差由一d i j ，1 冬is 小，1s _ l 1 = 恰为 1 ，2 ，( y 一1 ) 2 ，则称勿为乙中的一 个( 1 ，k ，1 ) 完美差族( p e r f e c td i f f e r e n c ef a m i l y , 简记为p d f ) 定义1 2 - 3 设9 为由z , v 中的m 个足元子集a i = d i l ，如，如l ，0 = 幽 如 呶，l f t n 所组成的子集族，如果所有有向差, u 一如，l i 加，l z k 恰为f 1 ，2 ， ，一l l ，则称9 为z , v 中的一个( y ，k ，1 ) 有向完美差族( d i r e c t e d p e r f e c td i f f e r e n c ef a m i l y , 简记为p d d f ) 注：可见，定义1 2 3 中的v = k ( k 一1 ) m 2 + 1 比较上述两个定义，我们易 知乙中的一个( y ，k ，1 ) p d d f 也是乙州中的一个( 2 v 一1 ，k ，1 ) p d f 定义1 2 4 令c ，小，k l ，七2 ，k 为正整数设a i = f 西l ，如，如；l ，0 = 4 i 如 d i k , ，- 1si sm 为整数序列，且设d i = d i l 一磷，：lsj f zsk i l ，1s f t n 为它们的差集合如果ud i = f c ，c + l ，c + 2 ，c l + k i ( k i 1 ) 2 l ， 则称 d l ，d 2 ，如l 为一个以c 做起点的完美差集合系统( p e r f e c ts y s t e mo f d i f f e r e n c es e t s ，简记为p s d s ) 此外，若岛= k ，lsf m ，则称这个系统是正则的，此 时我们把 a l ，a 2 ，a 肌l 称为一个( m ，k ，c ) 系统( s y s t e m ) ，把各个a i ( 1 f m ) 称 为该伽，k ，c ) 系统的元素组 注：由定义1 2 2 、定义1 2 3 和定义1 2 4 可知，一个( k ( k 一1 ) m 2 + l ，k ，1 ) p d d f 既是一个 ( 七一1 ) m + 1 ，k ，i ) - p d e 又是一个细，k ，1 ) 系统 例1 2 1 设子集族= a l ，a 2 ，a 3 ，a 4 l ，其中 a l = 0 ，1 ，7 ，2 3 ， a 3 = 0 ，3 ，1 3 ，2 1 ， a 2 = 0 ，2 ，1 4 ，1 9 ， a 4 = 0 ，4 ，1 5 ，2 4 如定义1 2 4 ，作a 的差集合历，i = 1 ，2 ，3 ，4 则 d i = 1 ，6 ，7 ，1 6 ，2 2 ，2 3 ， d 3 = 3 ，8 ，1 0 ，1 3 ，1 8 ，2 1 l ， d 2 = 1 2 ，5 ，1 2 ，1 4 ，1 7 ，1 9 l ， 仇= 4 ，9 ，1 1 ，1 5 ，2 0 ，2 4 4 可见，u d i = l ，2 ，3 ，2 4 ，则子集族= i a l ，a 2 ，a 3 ，a 4 l 是z 4 9 中的一 f ：1 个( 4 9 ，4 ，1 ) p d f , 也是汤5 中的一个( 2 5 ，4 ，1 ) p d d e 同时还是一个( 4 ，4 ，1 ) 系统 由小阶数的完美差族、( m ，足，c ) 系统递归构造较大阶数的完美差族、( m ，k ，c ) 系统时，加性置换序列和具有分裂性质的( ，l ，k ，c ) 系统在其中起到了很重要的作 用现在分别介绍加性置换序列和( 小，k ，c ) 系统的分裂点的概念 3 北京交通大学硕士学位论文 第1 章引言 定义1 2 5 令x 1 为z 维向量( 一一，+ l ，- 1 ，0 ，1 ，r l ，) ，f = 2 r4 - l ，并 令舻，x 3 ，f 为x 1 的置换如果每个由相邻置换构成的子序列的向量扣也都 是x 1 的置换( 即下表的三角中的每个元素都是x 1 的置换) ，则称x 1 ，酽，f 是 一个长度为阶数为f 的加，| 生置换序列( a d d i t i v es e q u e n c eo fp e r m u t a t i o n s ，筒记 为a s p ) x 1 + 砰+ + f x 1 + r + + 驴1 酽+ x 3 + 4 - f ；!； x 1 + 妒+ fr + p + 一 _ 24 - 刀一i + f x 1 + 舻酽+ x 3 f 一24 - 一1 f 一14 - r x 1妒x 3 r 一2f 一1f 注：由上述加性置换序列的定义，我们易知：若x 1 ，弘，f 是一个长度为以 阶数为f 的a s p , 则任意_ 个相邻的向量膏，x 川，矽+ 户1 ( 2sj n ，lsf n4 - l j ) 也是一个长度为歹，阶数为z 的a s r 例1 2 2 令 x 1 = ( 一3 ，一2 ，一i ，0 ，1 ，2 ，3 ) x 2 = ( 2 ，0 ，一2 ，3 ，1 ，- 1 ，一3 ) x 3 = ( 一1 ，3 ，0 ，一3 ，1 ，一2 ，2 ) 显然，舻和x 3 是x 1 的置换，且 x 1 + x 2 = ( 一1 ，一2 ，一3 ，3 ，2 ，1 ，0 ) 舻+ 妒= ( 1 ，3 ，- 2 ，0 ，2 ，一3 ，- 1 ) x 1 + x 2 + x 3 = ( - 2 ，1 ，一3 ，0 ，3 ，一1 ，2 ) 都是x 1 的置换故x 1 ，磐，x 3 构成一个长度为3 ，阶数为7 的a s e 定义1 2 6 设 a l a 2 ，a m l 是一个( m ，k ，c ) 一系统，其中a f = 1 4 l ，如，如 ，0 = 西l 如 呶，1 i m 且设x ua f ，对于正整数p ，定义集合a j ( p ) = i d i l ( p ) ，如( p ) ，砝( p ) ，1 ism 为 办( = 2 + p 若若如d i r cx x , 其中1 r k 设伪( p ) = i d i l ( p ) 一d q ( p ) ：1sj l 七l ，1sism ，今d ( p ) = u md i ( p ) 如果对于某个满足c z5c + m ( ：) 的正整数工，有d ( p ) = l i ：c i 4 北京交通大学硕士学位论文 第l 章引言 工luu ：p + x j p + c + m ( ! ) ) 对于所有的正整数p 都成立，别称集合x 为 该( m ，k ，d - 系统的一个分裂集( s p l i t t i n gs e t ) ，正整数工为该( 小，k ，f ) 系统的一个由 分裂集x 产生的分裂点( s p l i t ) 对于任意一个( m ，k ，c ) 系统= a i ，a 2 ，a 册 ，如果取x = 0 ，则对于v 1s f m ，v 1s ，k ，y p z + ，都有d 0 ( p ) = a i r ，则a i ( p ) = a f ，d i ( p ) = d f ，ud f ( p ) = r c l f - l ud i = i f ：c f c + ，l ( ：) 一l 此时，该系统由分裂集x = 0 产生的分裂点 i - l一 为c + ，l ( ：) 事实上，所有( m ，k ，c ) 系统都有一个分裂点为c + m ，我们将这种由 分裂集x = 0 产生的( m ，k ，c ) 系统的分裂点c + m 称为平凡分裂点( u i v i a ls p l i t ) ， 而将其它的分裂点称为严格分裂点( p r o p e rs p l i t ) 但是，并非所有的( m ，七，c ) 系统 都有严格分裂点；而另一方面，某些( m ，k ，c ) 系统有若干不同的严格分裂点 例1 2 3 对于例1 2 1 中所列出的( 4 ，4 ，1 ) 一系统= a l ，a 2 ，a 3 ，山l ，取 x = 1 1 3 ，1 4 ，1 5 ，1 9 ，2 l ，2 3 ，2 4 ， 则对于v p z + ，根据定义1 2 6 ，相应地有 a l ( p ) = 0 ，1 ，7 ，2 3 + p l ， a 3 ( p ) = 1 0 ，3 ，1 3 + p ，2 1 + p l ， a 2 ( p ) = 0 ，2 ，1 4 + p ，1 9 + p l ， a 4 ( p ) = f 0 ，4 ，1 5 + p ，2 4 - i - p 1 如定义1 2 6 ，作a f ( p ) 的差集合d f ( p ) ，i = 1 ，2 ，3 ，4 则有 d l ( p ) = 1 1 ，6 ，7 ，1 6 + p ，2 2 + p ，2 3 + p ， d 2 ( p ) = 2 ，5 ，1 2 + p ，1 4 + p ，1 7 + p ，1 9 + p ， d 3 ( p ) = 1 3 ，8 ，1 0 + p ，1 3 + p ，1 8 + p ，2 1 + p l ， d 4 ( p ) = 1 4 ，9 ，11 + p ，1 5 + p ，2 0 + p ，2 4 + p 4 可见，纠d i ( p ) = i f ：l f 9 ui ，：1 0 + psj 2 4 + p 则集合x 为 该( 4 ，4 ，1 ) 一系统的一个分裂集，由x 产生的该系统的分裂点为1 0 ，且1 0 为严格分 裂点若取x = 0 ，则该系统的由0 产生的平凡分裂点为2 5 最后，我们介绍有空缺差且l = l 的完美差族、有向差族、有向完美差族的 概念 定义1 2 7 设为由毛中的m 个k 元子集a f 西l ，如，比 ，0 = 西l 如 如，1 ism 所组成的子集族今d i = 幽一如：1s 工z k ，f l 研= 幽一哳：1 j ，s 七j ，15i ，1 如果 ( 1 ) 纠d f2 弓i o ，y ，2 v ，( g 一1 ) ， ； 5 北京交通大学硕士学位论文 第l 章引言 ( 2 ) _ d + e f 1 2 ，3 ，嘲l 则称为知中的一个( g v ，g ，k ，1 ) 一完美差族，简记为( g v ，g ，k ，1 ) 一p d f 定义1 2 8 设为由z 矗中的m 个k 元子集a i = 西i ，如，如l ，1 i m 所 组成的子集族令协= 锄一如：1s l 七l ，i m ，若纠皿= 弓 0 ，v ，2 v ， 一1 ) ，l ，则称为匆中的一个( g v ，g ，k ，1 ) - 有向差族，简记 为( g v ，g ，k ，1 ) - d d e 关于知中( g v ，g ，k ，1 ) - d d f 的存在性，有下述必要条件 引理1 2 2 2 9 1 若存在乙中的( g v ，g ，k ，i ) - d d f , 则 g ( v 一1 ) 兰0 ( r o o d ( 舢 定义1 2 9 设为由乙中的m 个k 元子集a i = 慨l ，如，比l ，0 = 西i 如 如，lsi5m 所组成的子集族令d i = i 幽一南：1sj zs 七 ，l fsm ， 若u m 功：乙 o ，v ，2 v ，( g 1 ) v ，则称为中的一个( g v ，g ，k ，1 ) 一有向完美 f = l 差族，简记为( g v ，g ，k ，1 ) - p d d e 注：由定义1 2 7 和定义1 2 9 不难推知，乙中的一个( g v ，g ，k ，1 ) - p d d f 也 是汤中的一个( 2 9 v ，2 9 ，k ，1 ) - p d f 特别地，当g = 1 时，一个( 2 v ，2 ，k ，1 ) 一p d f 既是 一个( 1 ，l ，k ，1 ) p d d f 即( ，七，1 ) 一p d d e 又是一个( 2 y 一1 ，k ，1 ) 一p d f 例1 2 4 取k = 3 ，g = 2 ， ，= 7 ，令= a i ，a 2 ，a 3 ，a 4 1 其中 a l = 1 0 ，1 ，1 3 ，a 2 = 0 ，2 ，1 1 ) ，a 3 = 1 0 ，3 ，8 ) ，山= 0 ，4 ，l o 如定义1 2 9 则 d l = 1 ，1 2 ，1 3 ，跳= 2 ，9 ，1i ，d 3 = 1 3 ，5 ，8 l ， 风= ( 4 ，6 ，1 0 可见，u 4d f ：1 1 , 2 ，3 ，4 ，5 ，6 ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 ：z 1 4 o ，7 1 则为z 1 4 中的 i = l 一个( 1 4 ，2 ，3 ，1 ) p a d f , 也为乙8 中的一个( 2 8 ，4 ，3 ，1 ) p d e 1 3 相关定理及结论 本节主要介绍与完美差族、完美差集合系统、加性冕换序列、，k ，c ) 系统 的分裂点等内容相关的一些定理和结论 关于加性置换序列长度的上界，有下面的定理 6 北京交通大学硕士学位论文第l 章引言 定理1 3 1 【钥若存在n 长l 阶的a s p , 则疗1 1 关于加性置换序列，目前文献【3 】中所列出的已知结果有： ( 1 ) 2 长的所有正奇数阶的a s p 都存在； ( 2 ) 3 长z 阶( z 2 0 ) 的a s p 中，5 阶、7 阶、1 3 阶、1 5 阶、1 7 阶、1 9 阶 的a s p 都存在，9 阶、1 1 阶的a s p 不存在； ( 3 ) 4 长f 阶( f 1 1 ) 的a s p 中，5 阶的a s p 存在，7 阶、9 阶、1 l 阶 的a s p 均不存在 关于加性置换序列的递归构造，根据文献【16 】中提到的构造方法，可得到下述 定理 定理1 3 2 【1 6 】如果存在万长z 阶的a s p 与，l 长“阶的a s p , 那么必存在几长比阶 的a s p 某些特殊阶数和长度的a s p 可由相应的( m ，k ，1 ) 系统来构造 引理1 3 1 3 1 设 x 1 = ( 一，一j r 一j t ，一r s ，- - t ，一j ，一厂 j ， ，+ j ，j + t ，r + j - i - f ) - 令 妒= ( t ，r + j + t ，j ，s + t ，一t ，一j t ，一r s ，厂 r + s ，一，一j t ，一j ，一r ) x 3 = ( j ，一，一s j t ，r + s + t ，t ，一厶r s r ，一，j + t ，r + s ，一s ) 则舻，x 3 ，x 1 + 妒，舻+ x 3 ，x 1 + x 2 + x 3 均为x 1 的置换 引理1 3 2f 3 】设 令 = ( - r s t 一，一s t h ，一r s t ，- t u ，一j 一 一，一j ，一一t ，一j ，- r , r ，s ，t ，u ，r + j ，s + t ，t + u ，厂+ j + t ，s + t + “，r + s + t + “) 芹= ( ，j ，t ，u ，一r j t 一“) ( r + s ，t + u ，一j t u ，s + t ，一r s t ) ( r + j + t ，一j t ，j + t + u ，- t m ，一，一s ) ( r + j + t + u ，一，一f ，一j ，一，- ) x 3 = ( ，0 一r j t 一j ，“) ( 厂+ s ，- - s t u ，一r f t ，t + “，s + t ) ( ，+ s + t ，j + t + u ，一，一j ，一j t ，- t 一“) ( r + j + t + “，- t ，一， 一“，一j ) x 4 = ( ，h ，j ，一，一j t m ，t ) ( r + j ，j + t ，t + “，一r s t ，一s t 一“) ( r + j + t ，- t u ，一j t ，一，一墨，j + t + “) ( r + j + t + “，一j ，一“，一， - t ) 7 北京交通大学硕士学位论文第1 章引言 则舻，f ，酽，x 1 + 舻，弘+ 妒，x 3 + 一，x 1 + 妒+ p ，弘+ x 3 + f ，x 1 + f + p + 一均为x 1 的置换 注：引理1 3 2 中的舻，f ，f 都表示成了相对于x 1 的5 轮换乘积的形式 因此，( m ，4 ，1 ) 系统中的每一个4 长元素组，都对应一个形如引理1 3 1 中的 由1 2 维向量x i ，r ，x 3 构成的3 长序列；( m ，5 ，1 ) 系统中的每一个5 长元素组， 都对应一个形如引理1 3 2 中的由2 0 维向量x i ，弘，x 3 ，酽构成的4 长序列将 它们合并起来，再在相同的分量位置上补入元素 0 l ，便得到相应较大阶数的a s e 故有如下定理 定理1 3 3 【3 1 ( 1 ) 若存在( m ，4 ，1 ) 系统，则存在3 长1 2 m + l 阶的a s e ( 2 ) 若存在( n ，5 ，1 ) 系统，则存在4 长2 0 n4 - l 阶的a s e 从而也存在3 长 2 0 n - i - 1 阶的a s e ( 3 ) 若存在咖，n ；4 ，5 ；1 ) 系统，则存在3 长1 2 m + 2 0 n + 1 阶的a s e 注：定理1 3 3 ( 3 ) 中的( m ，n ；4 ，5 ；1 ) 系统表示该系统中有m 个4 长元素组 和n 个5 长元素组，同定义1 2 4 中所述，d f 为元素组a j 的差集合( 1 fs m + n m + 厅) ，ud i = - ，：l j 6 m + 1 0 n f - l 下面介绍关于构造( m ，k ，c ) 一系统的著名的乘法定理 定理1 3 41 2 0 l 若存在一个( m ，k ，c ) 系统，则当 ( 1 ) k = 3 ，z 为正奇数； ( 2 ) k = 4 ，z = 5 7 6 1 3 。1 9 d ( 其中a ，6 ，c ，d 0 ，且a ，b ，c ，d 不全为0 ) 时，盛定存在一个( 1 m ，k ，l c i 2 + 1 2 ) 一系统 定理1 3 50 9 1 设9 = a l ，a 2 ，a 。l ，a f = 0 ，a i , b f ，c i ，0 a f b f c i ，j = l ，2 ，m 是z l2 ，l + l 中的一个( 1 2 m4 - l ，4 ，1 ) p d e 并设x 1 ，酽，x 3 为一个3 长z 阶 的a s p , f = 2 r4 - l ，2 则对于f - 1 ，2 ，m 和j = l ，2 ，厶由下面的砌个区 组： 枷一m + j = 0 ，l a i + a j ，l b i + 岛，l c i4 - 竹l 所产生的6 1 m 个有向差恰好为 r + 1 ，+ 2 ，r + 6 l m 其中，口= x i ，卢= x 1 + 妒，y = x 1 + x 2 + x 3 ；岛表示z 维向量6 的第j 个分量，6 = 口，卢，7 注：由定理1 3 5 所述，可知a m i m + j 中，0 a i4 - 口， l b i + 房 6 ，则不存在z 知中的( ，g ，k ，1 ) 一p d d f ；当眙( 七( 七一1 ) ) 与( 4 k - 6 ) g ( k ( k - 1 ) ) 中 至少有一个不是整数时，若k 6 ，则不存在z 0 中的( g v ，g ，k ，1 ) 一p d d e 证明：若存在乙中的一个( g v ，g ，k ，1 ) 一p d d f , 设它的基区组个数为s ，则 g v g2 9 ( v 一1 ) 泸百2 丽可 记该( g v ，g ，k ，1 ) 一p d d f 为舅= a i ，a 2 ，a ，l ，其中a 产 a l f ，a 2 i ，口“l ， 0 = a l i a 2 f 0 ，矛盾 所以此种情况下，当k 6 时，不存在z 0 中的 ，g ，k ，1 ) p d d e ( 2 ) 石= 志一1 ，y = 【耥】幽k ( k - 1 ) 耻鼎一l ，箫一1 0 若存在乙中的一个( g v ，g ，k ，1 ) p d d e 则幻2 【( 七一9 2 ) 2 9 4 v + r 0 ， 即4 9 2 ( k - 9 2 ) 2 9 4 vs - r 0 而当k 6 时，幻2 【( j i ：一9 2 ) 2 9 4 v 0 ，矛盾 所以此种情况下，当k 6 时，不存在乙中的( g ，g ，j i ：，1 ) p d d e ( 3 ) z = 【志】且k ( k - i ) ，y = t 4 k - 6 ) g _ 1 即南一1 0 后面的讨论同( 2 ) 所以此种情况下，当七6 时，不存在z 知中的( g v ，g ，k ，1 ) 一p d d e ( 4 ) z = 【莉6 9 】志，y = r 业k ( k - i ) j 1 业k ( k - i ) 即： 立k ( k - 1 ) 一l 石 鼎，黼一l - 4 9 k 3 + l o g k 2 6 9 k + 1 6 9 2 j i ：2 4 8 9 2 k + 3 6 9 2 ， r = 一1 6 9 2 k 2 + 4 8 9 2 k