（应用数学专业论文）4m44pcdps的构作.pdf

( 4 m ，4 ，4 ) - p c d p s 的构作 摘要 摘要 设t ，m 及a 为正整数我们用磊表示模 的剩余类环又设d = d o ，d 。，一， d 一，为磊上的一个划分，其中每个d ；称为基区组若对任意模 非零剩 余d 彩，方程z y = d ，z ，y d ( 0 i m 一1 ) 至多有a 个解，则称d 为 ( ”，k ，入) - 可划分循环差填充，简称为( u ，k ，a ) p c d p ，其中k = i d i l ：d ；d ) 这里k 为无序重集，通常表为指数形式我们用户( u ，m ) 表示使得( u ，k ，入) p c d p 存在的最小指标a ，当a = p ( v ，m ) 时，一个( u ，k ，a ) p c d p 称为最优 的最优p c d p 可以直接用来构造最优跳频序列和无逗点码给定正整数m 和u = 肌+ e ，0 e m 一1 ，已知p ( t j ，m ) p 最近，c h e e ，l i n g 和y i n 系统地 研究了达到上述下界最优p c d p 的存在性和构造方法，完整地解决了最优 ( 3 m ，【3 m 】，3 ) 一p c d p 的存在性问题本文研究达到上述下界的最优( 4 m ，【4 m 】，4 ) p c d p 的存在性问题借助齐次循环差矩阵，齐次循环带洞差矩阵，我们证 明了：当m 0 ( r o o d4 ) 时，一个最优( 4 m ，【4 m 】，4 ) p c d p 存在当m 三0 ( r o o d4 ) 时，本文给出若干有效的构作方法和部分存在性结果 关键词：可划分差填充，循环差矩阵，跳频序列，无逗点码，构作 作者：魏学娟 导师：殷剑兴( 教授) c o n s t r u c t i o n so f ( 4 m ，4 ，4 ) 一p c d p sa b s t r a c t c o n s t r u c t i o n so f ( 4 m ，4 ，4 ) - p c d p s a b s t r a c t ap a r t i t i o n e dc y c l i cd i f f e r e n c ep a c k i n g ( p c d p ) ，o ra ( u ，k ，入) 一p c d pi n 磊，i sa p a r t i t i o nd = d o ，d 1 ，d m i ) o f 磊i n t oms u b s e t s ( c a l l e db a s eb l o c k s ) s u c ht h a t t h ed i f f e r e n c e sf r o mt h e s eb a s eb l o c k sc o v e re a c hn o n z e r or e s i d u e ( r o o du ) a tm o s t 入t i m e s l e t 御，a ，mb ep o s i t i v ei n t e g e r s ，w ed e n o t eb yp ( t ，m ) t h em i n i m u mi n d e x s u c ht h a ta ( 口，k ，a ) 一p c d pe x i s t s a n dw ec a l la ( t j ，k ，a ) - p c d po p t i m a li fi t si n d e x 入= v ( v ，仇) s u c hp c d p s c a nb eu s e dd i r e c t l yt op r o d u c eo p t i m a lf r e q u e n c yh o p p i n g s e q u e n c e sa n dc o m m a f r e ec o d e s i ti sk n o w nt h a tf o ra n yp o s i t i v ema n dt ，= m 肛+ e w i t h0 e m 一1 ，p ( v ，m ) p c h e e ，l i n ga n dy i nh a ss t u d i e dt h ee x i s t e n c ea n d t h ec o n s t r u c t i o no ft h eo p t i m a lp c d pa t t a i n i n gt h el o w e rb o u n do fa b o v ei n e q u a l i t y e s p e c i a l l y , ac o m p l e t es o l u t i o nt ot h ee x i s t e n c ep r o b l e mf o rt h eo p t i m a l ( 3 m ，【3 m 】，3 ) 一 p c d ei nt h i sp a p e r ，w es t u d yt h ee x i s t e n c ep r o b l e mf o rt h eo p t i m a l ( 4 m ，【4 m 】，4 ) 一 p c d pa t t a i n i n gt h el o w e rb o u n do fa b o v ei n e q u a l i t y w i t hc y c l i cd i f f e r e n c em a t r i x a n dc y c l i ch o l e yd i f f e r e n c em a t r i xw et a c k l et h ee x i s t e n c eo fa ( 4 m ，【4 m l ，4 ) 一p c d p s ( m s 0 ( m o d4 ) ) f o r ( 4 m ，【4 m 】，4 ) - p c d p s ( m - - = 0 ( r o o d4 ) ) ，w ep r e s e n ts o m e c o n s t r u c t i v em e t h o d sa n de x i s t e n c er e s u l t s k e y w o r d s ：p a r t i t i o n e dd i f f e r e n c ep a c k i n g s ，c y c l i cd i f f e r e n c em a t r i x ，f r e q u e n c yh o p - p i n gs e q u e n c e s ，c o m m a - f r e ec o d e s ，c o n s t r u c t i o n s i i w r i t t e nb yw e ix u e j i a n s u p e r v i s e db yp r o f y i nj i a n x i n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文。 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名：垄整垦竭e l 期： 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文本人电子文档的内容和纸质论文的内容相一致除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏：f - l 大学学位办办理 研究生签名幽日期： 导师签名日 期： ( 4 m ，4 ，4 ) 一p c d p s 的构作 一引言 1 1 定义与记号 芦f 士 一弓i 百 一j 设磊表示模移的剩余类环给定磊的m 个子集( 称为基区组) 所组成 的族，d = d o ，d 1 i 一，d m 一。) ，我们定义z ：- z u o ) 上的一个差函数： t n l 垂d ( 9 ) = i ( d i + g ) n 取i i = o 记k = 【l 玖l ：d t 习 ，为方便起见，我们通常将k 表为下面指数的形 式：时1 谬砖】，这表示长度为k t 的区组有啦个1 i 8 定义a = m a x 9 z ：圣口( 夕) ，则我们称d 为个循环差填充，简称为( 口，k ，入) 一c d p 。进一步 地，如果d 形成磊的个划分，那么我们称口为一个( ，k ，a ) 可划分循环 差填充( p a r t i t i o n e dc y c l i cd i f f e r e n c ep a c k i n g ) ，记作( 仃，k ，入) p c d p 不难证明下面的性质与可划分循环差填充的定义是等价的： d 是一个( ，k ，入) p c d p 当且仅当口是z 口的一个划分，并且对任给 g z ：，方程z y = g 至多有入个解，这里( z ，y ) u d d dx d 一多重集 口= u i = - 1 0a d i = u r 扛r $ - - 0 1 n b ：a ，b d i 并且a 6 ) 中覆盖z 。的每一个元素至多a 次 当对任意g z ：，有圣口( g ) = a 时，( 秒，k ，a ) p c d p 是我们熟知的( ”，k ，a ) 可划 分循环差族 给定正整数 ，m 0 ，那么c 是一个无逗点码，因 此我们可以从两个码字的串联上分辨出一个码，即使有【( ，( c ) 一1 ) 2 j 个错误 发生具体细节见【9 ，1 4 】 具有无逗点码指标的码可用差系统集( d s s ) 来构作，这是由l e v e n s h t e y n 【1 2 】( 也可以见：【1 1 ，1 4 】) 引进的一个组合构作一个( ，k ，叼) d s s 是个z 廿 上具有m 个不相交的集合所组成的族：厂= d t ，忱，) ，且重集 q b ( r o o d ) ：d d i ，b 岛，1 i ，歹m 并且i 歹) 覆盖z ：的每个元素至少7 7 次，这里k = 【i m l ：d 习差系统集在码同步现 象的应用中要求冗余度： m r m ( 钉，7 ) = i d i i i = l 3 ( 4 m ，4 ，4 ) - p c d p s 的构作 一 引言 尽可能的小l e v e n s h t e y n 【1 2 】证明了 讪v 票r l m ( v 孚- 1 ) 下面的定理是差系统集与p c d p 之间的关系 ( 2 ) 定理1 3 ( 2 1 ) 设仇和u = 哗+ e m 是正整数，0 e y d , 一1 如果 一个( m j u + e ，【( p + 1 ) 旷叫】，p ) 一p c d p 存在，那么一个具有最小冗余度u 的 ( ，【( p + 1 ) 矿叫】，7 ) - d s s 也存在，这里7 7 = t j p = ( m 一1 ) d + e 定理1 3 说明由一个最优p c d p 导出的差系统集具有最小冗余度，因此 可以产生一个达到不等式( 2 ) 的下界的最优无逗点码这是我们研究p c d p s 的第二个背景 p c d p s 在常重复合码方面也有重要的应用( 见：【4 ，5 1 ) 1 3 研究问题和结果 由于p c d p 有很强的应用背景，有关达到下界的最优p c d p 的存在性 和构作方法受到国内外不少学者的研究，并取得了重要的进展 本文中，我们研究具有m 个长度为4 的基区组的p c d p ，即( u ，【4 m 】，a ) p c d p 显然，我们有t ，= 4 m 由定理1 1 知p ( 4 m ，m ) 4 ，由此可知，当 a = 4 时，一个( 4 m ，【4 m 】，a ) - p c d p 是最优的为表述方便，下文中我们将最 优( 4 m ，【4 m 】，4 ) 一p c d p 简称为( 4 m ，4 ，4 ) p c d p 本文通过直接构作和递推构作得到如下结果 ( 1 ) 完全解决了( 4 m ，4 ，4 ) p c d p s ( m 0 ( r o o d4 ) ) 的存在性问题； ( 2 ) 给出了( 4 m ，4 ，4 ) 一p c d p s ( m 兰0 ( r o o d4 ) ) 的一些构作方法，并构作了 ( 4 m ，4 ，4 ) - p c d p s ( m - - = 0 ( r o o d4 ) ) 的若干无穷类 在构作过程中，我们还得到一些新的循环带洞差矩阵 4 ( 4 m ，4 ，4 ) - p c d p s 的构作 二基本构作方法 二基本构作方法 为了建立本文的主要结果，我们需要介绍一些相关的定义和预备结论 设g 为g 阶加法群，d = ( 如) ( 0 l 七一1 ，0g 9 一1 ) 是一个k x g 矩阵， 盔，g ，若对d 中任意两行t ，r ( 0 u ， 是一1 ) ，重集 a d = 如一奶l 0s 歹sg 1 ) 恰好包含g 中的每个元素，则称d 为g 上的差矩阵，记作( g ，七，1 ) 一d m 当g 是循环群时，也即g = 忍，则称d 为g 上的循环差矩阵，记作( 9 ，七，1 ) 一c d m 当d 的第一行和第一列全为零时，则称此循环差矩阵为正规的 如果将正规循环差矩阵d 中的任意一行或任意一列的所有元素都加上 磊中的某一元素，得到的矩阵也保持循环差矩阵的性质不失一般性，我 们也认为此循环差矩阵是正规的如果我们将正规的( g ，k ，1 ) ，c d m 的第一 行去掉得到一个导出的( g ，七一1 ，1 ) c d m ，它的每一行是乙上的一个置换，我 们用文章【7 】中的术语称导出的( g ，k l ，1 ) c d m 为齐次的齐次循环差矩阵 的每一行是毛上的一个置换，并且第一列全为零显然正规( g ，七，1 ) 一c d m 的 存在性与齐次( g ，一1 ，1 ) c d m 的存在性是等价的 循环差矩阵在构作p c d p 时发挥了重要的作用，因此我们需要引入循 环差矩阵的一些存在性结果 素数域磊上的乘法表构成了一个正规，p ，1 ) 一c d m ，因此，对任意素数 p ，齐次，p 一1 ，1 ) c d m 存在，从这个齐次循环差矩阵中删掉p 一1 一七行我 们就可得到一个齐次( p ，七，1 ) c d m ，将这一事实以下面定理的形式给出： 引理2 1 ( 【3 】) 设p 是一个素数，k 是一个整数，且满足2 七9 1 ，则齐次 0 ，k ，1 ) 一c d m 存在 关于循环差矩阵的复合构作有如下已知结果( 见【1 6 】) ： 引理2 。2 如果齐次( 9 l ，免，1 ) ，c d m 和齐次( 9 2 ，晃，1 ) - c d m 都存在，那么齐次 5 ( 4 m ，4 ，4 ) 一p c d p s 的构作 二基本构作方法 ( 9 1 9 2 ，k ，1 ) - c d m 也存在 结合引理2 1 和引理2 2 ，我们得到如下结果： 引理2 3 设正整数夕3 ，且其所有素因子均不小于素数p ，那么对任意正整数 k ，2 七p 一1 ，齐次( g ，k ，1 ) ，c d m 存在 在本文的构作过程中还需要以下结果： 引理2 4 ( 融) 设口是奇正整数 e = 3 ，9 ，9 p ，p 是除去3 ，5 ，7 ，1 1 ，1 3 ，1 7 ，2 3 ，2 9 ，3 1 ，1 0 9 的奇素数 如果 盛e ，那么( ，5 ，1 ) 一c d m 存在 引理2 4 中的( 2 7 ，5 ，1 ) 一c d m 的存在性可以在【1 3 】中找到利用齐次循环 差矩阵可以构作可划分循环差填充的基区组，下面的这种构造方法可以参 见f 2 1 引理2 5 设m ，t 是正整数，若齐次( m ，t ，1 ) - c d m 存在，则最优( 伽仉， 矿】， 让) p c d p 也存在 为了得到本文的结果，我们需要推广【2 】中的个复合构作 引理2 6 如果最优( u m ，【t m 】，t ) p c d p 和齐次( n ，t ，1 ) c d m 都存在，那么最 优( t t m n ， 让仇1 ，札) 一p c d p 也存在 证明：设d = 【口1 i ，a 2 i ，d 越) ：1 i m ) 为一个最优( 伽，【俨1 ，u ) p c d p ，故 p 是的个划分，且a z ) = 仇奄一q 南1 1 i ，j 钍，1 k m ) 覆盖上的 每个元素至多t 次由最优( u m ，【矿】，珏) 一p c d p 的每一基区组 a m ，a u i ) ， 我们可以构作最优( 7 t m t ，【】，u ) p c d p 的n 个基区组： a l l + u m d l j ，a 2 i + u m d 2 j ，口撕+ 伽叽) ，1 歹n 其中， d l j ，锄，如) 是齐次( n ，t ，1 ) 一c d m 的列故d = 口1 + u m d l j , a 2 + 懈奶，+ u m d , , j ) ：1 i 冬m ，l j n ) 是磊踟的一个划分，且由最优 6 ( 4 m ，4 ，4 ) 一p c d p s 的构作 二 基本构作方法 ( u m ，【u m l ，u ) 一p c d p 和齐次( n ，乱，1 ) - c d m 的性质知d + = ( o 谤一吩七) + t | m ( d 一 d j k ) l l i ，j 让，1 k m ，1 k n ，) 覆盖n 的每个元素至多t 次因此 刃是一个最优( u m l t ，【妒”l ，u ) 一p c d p ，故结论成立 口 构作( 4 m ，4 ，4 ) p c d p ( m 三0 ( r o o d4 ) ) 的方法中用到循环带洞差矩阵， 因此循环带洞差矩阵在构作p c d p 中也起着很大的作用有关带洞差矩阵 的相关信息见【6 】下面介绍一下循环带洞差矩阵的定义 设磊为u 阶循环群，日是磊的叫阶子群，m = ( m i i ) ( 1 i 尼，l j _ v - w ) ( m o e g ) 为一个k x ( v 一叫) 矩阵，若对m 中任意两行t ，h ( 1 蜒七) ，重集 a m = m m i l t t i i1 i 一叫) 恰好包含z v h 中的每个元素，则称m 为磊上的循环带洞差矩阵记作 ( k ，t ，；t t ，) - c h d m 将循环带洞差矩阵m 上的任意一列加上磊中的某一元素，得到的矩阵 也保持循环带洞差矩阵的性质不失一般性，一个循环带洞差矩阵第一行上 的元素可以全部为零，如果我们将这样的矩阵的第一行去掉得到一个( k 一1 ， 移；钮) c h d m ，其每一行上的元素是磊日的一个置换，我们称导出的( 七一1 ， u ；伽) 一c h d m 为齐次的 利用齐次( 4 ，m ；2 ) c h d m 可以得到( 4 m ，4 ，4 ) p c d p 构作方法如下： 引理2 7 如果齐次( 4 ，m ；2 ) c h d m 存在，那么( 4 m ，4 ，4 ) - p c d p 存在 证明：设m = ( m 巧) ( o i 3 ，o j m 一3 ) 是上的齐次( 4 ，m ；2 ) 一c h d m ，我 们用i + 4 m 巧替换m 中的m i j ( o l 3 ，o j m 一3 ) ，则在瓦n 上构作一个新 的4 ( m 一2 ) 矩阵足我们用功表示兄的第j 列o g m 一3 ，并将d j 作为 ( 4 m ，4 ，4 ) p c d p 的基区组再添加( 4 m ，4 ，4 ) - p c d p 的另外两个基区组为t d m 一2 = 【o ，1 ，2 m ，2 m + 3 ) ，d m 一1 = 2 ，3 ，2 m + 1 ，2 m + 2 ) 7 ( 4 m ，4 ，4 ) 一p c d p s 的构作 二基本构作方法 下面我们来说明刃= 风，d l i ，玩一1 为历m 上的一个( 4 m ，4 ，4 ) 一p c d p 由齐 次( 4 ，m ；2 ) c h d m 的性质及d 一2 ，d 一。的特点保证了d 满足如下性质： ( 1 ) 秒是毛m 上的一个划分； ( 2 ) 让仃= 4 = 【句：o g m 一1 ) 是乃m 的唯一加法子群对任给的非 零元z 五m ，我们有： 喇= 0 iz x 釜e 茹h 2 m 2 ， 因此d 是一个( 4 m ，4 ，4 ) p c d p 我们直接构作的齐次( 4 ，仇；2 ) 一c h d m 如下t 引理2 8 对任意( u ，t t ，) 0 6 ，2 ) ，( 1 8 ，2 ) ，( 2 4 ，2 ) ) ，个齐次( 4 ， ；t l j ) 一c h d m 存在 证明：满足条件的齐次循环带洞差矩阵直接构作如下： 一个齐次( 4 ，1 6 ；2 ) 一c h d m 为： 一个齐次( 4 ，1 8 ；2 ) 一c h d m 为： 一个齐次( 4 ，2 4 ；2 ) 一c h d m 为，m = ( d 卜d ) ，其中d 为： 8 口 、llil 5 1 l 9 1 4 4 l 5 1 1 1 2 3 2 1 3 1 1 心7 6 5 n 垢2 9加他7 坞 t l 9 5 1 1 4 7 l 5 l 6 4 9 3 5 4 6 3 0 5 哇l 1 l 2 0 3 6 1 l 3 4 2 1 1 l 1 2 3 7 ，j一 、-、 7 5 2 11 1 6 2 3 4 l l l l 5 1 1 j 寸i 1 1 41 8 7 2 3 o 1 l 3 5 2 6 4 3 1 1 1 1 1 0 6 l 6 1 1 0 3 1 1 5 3 4 8 1 2 7 7 2 5 1 1 1 1 6 0 6 l 1 l7 5 3 6 1 5 1 4 l 1 1 7 3 5 1 6 2 1 8 4 l 2 4 8 ，一， ( 4 m ，4 ，4 ) 一p c d p s 的构作二基本构作方法 因此，对任意( u ，叫) ( 1 6 ，2 ) ，( 1 8 ，2 ) ，( 2 4 ，2 ) ，一个齐次( 4 ，t ，；t 7 ) c h d m 存在 结合引理2 7 和引理2 8 ，我们很快得到如下结果： 引理2 9 当仇【1 6 ，1 8 ，2 4 ) 时，( 4 m ，4 ，4 ) p c d p 存在 9 口 、ll-i-、 l 7 9 0 ，j，l l o 9 3 l 1 6 2 3 5 9 2 4 l l， 8 2 l 3 7 垢8 m6培船2 o 5 l 2 7 4 8 q 8 1 1l 3 6 9 1 3 9 2 4 l l l 2 3 4 ，illll-ii、 = d ( 4 m ，4 ，4 ) 一p c d p s 的构作三( 4 m ，4 ，4 ) 一p c d p s ( m 0( m o d4 ) ) 的存在性 三( 4 m ，4 ，4 ) 一p c d p s ( m 0 ( m o d4 ) ) 的存在性 本节中，我们将给出( 4 m ，4 ，4 ) p c d p s ( m 0 ( m o d4 ) ) 存在性的证明 首先我们用直接构作的方法来构作一些可划分循环差填充 定理3 1 任给正整数m ，m 1 3 ，( 4 m ，4 ，4 ) 一p c d p 存在 证明：当m 5 ，7 ，1 3 ) 时，由引理2 1 知齐次( m ，4 ，1 ) c d m 存在，再由引理2 5 知( 4 m ，4 ，4 ) p c d p 存在对于其它正整数m ，m 1 3 ，我们以下面表格的形 式分别给出对应m 的一个( 4 m ，4 ，4 ) p c d p m 基区组 1 o ，1 ，2 ，3 ) 2 o ，1 ，3 ，7 ， 2 ，4 ，5 ，6 ) 3 【o ，3 ，8 ，l o ) ， 1 ，2 ，4 ，7 ) ，【5 ，6 ，9 ，1 1 4 ( o ，1 ，2 ，3 ， 4 ，6 ，9 ，1 3 ， 0 且仇三2 ( r o o d4 ) 时，存在( 4 m ，4 ，4 ) 一p c d p 证明：因为m 三2 ( m o d4 ) ，所以可将m 写成如下形式：m = 2 - 3 p p ，这里p 的 所有素因子都大于3 当m 【2 3 6 ：6 = 0 ，1 ，2 ) 时，由定理3 1 和引理2 9 知( 4 m ， 4 ，4 ) 一p c d p 存在现在我们将p 写成如下形式：p = 3 t + 6 ，t 0 ，6 ( o ，1 ，2 ) ， 根据前面证明知( 4 ，23 6 ，4 ，4 ) p c d p 存在，由引理2 4 知齐次( 3 乱p ，4 ，1 ) c d m 存在，则由引理2 6 知对正整数m ，m 三2 ( r o o d4 ) ，( 4 m ，4 ，4 ) p c d p 存在 结合定理3 1 ，定理3 2 和定理3 3 ，我们得到本文的一个存在性结果， 定理3 4 对任意的正整数m ，m 0 ( m o d4 ) ，达到( 1 ) 式下界的( 4 m ，4 ，4 ) 一 p c d p 存在 ( 4 m ，4 ，4 ) 一p c d p s 的构作四( 4 m ，4 ，4 ) - p c d p s ( m 兰0( m o d4 ) ) 的构作 四( 4 m ，4 ，4 ) 一p c d p s ( m 三0 ( m o d4 ) ) 的构作 本节中我们给出由存在的p c d p 得到新的p c d p 的若干构造方法，并 应用这些方法构作了( 4 m ，4 ，4 ) p c d p s ，m 三0 ( r o o d4 ) 的若干无穷类 为了给出p c d p 的构作方法，我们首先介绍一些记号和相关性质 设d 是一个( 4 2 ，4 ，4 ) 一p c d p , 其基区组的元素按递增顺序排列，记 d = d l i a 2 i ，a 3 i ，a 4 i ：a l i a 2 i a a i 口钺，1 i 2 t ) 由d 产生的正差记 作d + = 一a u ：1 t 歹4 ，i = 1 ，2 ，2 ) 由d 产生的差剩余记作 l z ) = 4oz 4 2 , 4 - a d ( 其中，4oz 4 2 s 表示五2 t 的每个元素出现4 次，下文中 的 砖，毋，口警 表示a t 出现i 。次) 给定正整数t ，设b 是u = z 4 2 tu ( 五2 t + 4 t 2 t ) 上2 t + 1 个长度为4 的基区 组构成的族，且b 构成u 的一个划分由层产生形如d ，4 u 2 t + h ( d ，h z 4 2 t ) 的差( 在磊岫2 t 上计算) 记作a b + ，如果召满足如下性质，则称召与d 相关 对任意的1 d 4 2 1 ，a b + 覆盖d ，4 竹2 t + d 的次数不超过a t ) + u l ：d 覆盖d 的次数 4 u 2 t 在a 8 + 中至多出现2 次 引理4 1 设d 是一个( 4 2 ，4 ，4 ) p c d p ，如果存在u = z 4 2 tu ( 乙2 t + 3 2 2 ) 上 与口相关的一个划分b ，则一个( 4 2 t + 4 ，4 ，4 ) p c d p 存在 证明： 设d = 口1 ，口2 i ，a 戳，a 4 ) ：8 “ 0 2 i n 3 i ，a b + = 1 3 ，2 2 ，3 1 ，3 2 2 ，( 3 2 + 1 ) 3 ，( 3 2 + 3 ) 1 ) 因此 b 与d 相关，由引理4 1 知个( 4 2 4 ，4 ，4 ) p c d p 存在； ( 2 ) d = “o ，1 ，3 ，7 ) ， 2 ，4 ，5 ，6 ) 是一个( 8 ，4 ，4 ) 一p c d p ，u = 磊u 6 4 + z s ) 上 的一个划分召为： o ，3 ，7 ，6 4 ， 6 4 + l ，6 4 + 3 ，6 4 + 7 ，1 ) 2 ，4 ，5 ，6 4 + 6 ) ， 6 4 + 2 ，6 4 + 4 ，6 4 + 5 ，6 ) 贝4 d + = 1 3 ，2 3 ，3 2 ，4 2 ，6 1 ，7 1 ，l d = 【0 4 ，3 2 ，5 2 ) ，a b + = 1 2 ，2 3 ，3 3 ，4 2 ，6 1 ，7 1 ，6 4 2 ，( 6 4 + 1 ) 2 ，( 6 4 + 2 ) 3 ，( 6 4 + 3 ) 1 ，( 6 4 + 4 ) 2 ，( 6 4 + 6 ) 1 ，( 6 4 + 7 ) 1 ) 因此b 与d 相关，由引理 4 1 知一个( 4 2 5 ，4 ，4 ) p c d p 存在； ( 3 ) d = o ，1 ，2 ，3 ) ， 4 ，6 ，9 ，1 3 ， 因此b 与d 相关，由引理 4 2 知一个( 4 3 2 4 , 4 ，4 ) 一p c d p 存在； ( 4 m ，4 ，4 ) 一p c d p s 的构作四( 4 m ，4 ，4 ) p c d p s ( 仇三0( r o o d4 ) ) 的构作 ( 3 ) d = “o ，1 ，2 ，3 ) ， 4 ，6 ，9 ，1 3 ， 5 ，8 ，1 0 ，x 4 ， 7 ，1 1 ，1 2 ，1 5 ) 是一个( 1 6 ，4 ，4 ) p c d p ，u = 互6u 1 9 2 + 五6 ) 上的一个划分b 为： l ，2 ，3 ，1 9 2 + 3 ) ， 1 9 2 ，1 9 2 + 1 ，1 9 2 + 2 ，o ， 4 ，9 ，1 3 ，1 9 2 + 6 ) ， 1 9 2 十4 ，1 9 2 + 9 ，1 9 2 + 1 3 ，6 ) 8 ，1 o ，1 4 ，1 9 2 + 5 ) ， 1 9 2 + 8 ，1 9 2 + 1 0 ，1 9 2 + 1 4 ，5 ) 7 ，1 2 ，1 5 ，1 9 2 + 1 1 ， 1 9 2 + 7 ，1 9 2 + 1 2 ，1 9 2 + 1 5 ，a l 则a d + = 【1 4 ，2 4 ，3 4 ，4 4 ，5 3 ，6 1 ，8 1 ，9 2 ) ，l d = 0 4 ，5 1 ，6 3 ，7 2 ，8 2 ，9 2 ，1 0 3 ，1 1 1 ) ，a b + = 1 4 ，2 4 , 3 2 ，4 2 ，5 ，6 2 ，8 2 ，9 2 ，1 9 2 2 ，( a 9 2 + 1 ) 4 ，( 1 9 2 + 2 ) 4 ，( 1 9 2 + 3 ) 4 ，( 1 9 2 + 4 ) 4 ，( 1 9 2 + 5 ) 2 ，( 1 9 2 + 7 ) 2 ，( 1 9 2 + 9 ) 2 ) 因此召与口相关，由引理4 2 知一个( 4 3 2 s , 4 ，4 ) 一p c d p 存 在 引理4 3 设刃是个( 4 2 ，4 ，4 ) p c d p ，如果存在u = 五型u ( 五2 t + 3 6 2 ) 上 与d 相关的个划分b ，则个( 4 3 2 2 t + l ，4 ，4 ) - p c d p 存在 例4 3 ：( 4 3 2 2 ，4 ，4 ) 一p c d p ，( 4 3 2 2 3 , 4 ，4 ) 一p c d p 都存在 证明：( 1 ) v = o ，1 ，3 ，7 ) ， 2 4 ，5 ，6 ) ) 是一个( 8 ，4 ，4 ) 一p c d p ，u = 磊u 7 2 + z s 上的个划分召为： o ，3 ，7 ，7 2 ) ， 7 2 + 1 ，7 2 + 3 ，7 2 + 7 ，1 ) 2 ，4 ，5 ，7 2 + 6 ) ， 7 2 + 2 ，7 2 + 4 ，7 2 + 5 ，6 ) 则a d + = 1 3 ，2 3 ，3 2 ，4 2 ，6 1 ，7 x ) ，l d = 0 4 ，3 2 ，5 2 ) ，a b + = 是一个( 1 6 ，4 ，4 ) 一 p c d p ，矽= 历6u 1 4 4 + 磊6 ) 上的一个划分召为： l ，2 ，3 ，1 4 4 + 3 ) ， 1 4 4 ，1 4 4 + 1 ，1 4 4 + 2 ，o ) ( 4 m ，4 ，4 ) 一p c d p s 的构作 四( 4 m ，4 ，4 ) p c d p s ( 仇三0( m o d4 ) ) 的构作 4 ，9 ，1 3 ，1 4 4 + 6 ， 1 4 4 + 4 ，1 , 1 4 + 9 ，1 4 4 + 1 3 ，6 【8 ，1 0 ，1 4 ，1 4 4 + 5 ) ， 1 4 4 + 8 ，1 4 4 + 1 0 ，1 4 4 + 1 4 ，5 ) 7 ，1 2 ，1 5 ，1 4 , 1 + 1 1 ， 1 4 4 + 7 ，1 4 4 + 1 2 ，1 4 4 + 1 5 ，1 1 ) 则a d + = 1 4 ，2 4 ，3 4 ，4 4 ，5 3 ，6 1 ，8 1 ，9 2 ) ，l d = 0 4 ，5 1 ，6 3 ，7 2 ，8 2 ，9 2 ，1 0 3 ，1 1 1 ) ，召+ = ( 1 4 ，2 4 ，3 2 ，4 2 ，5 4 ，6 2 ，8 2 ，9 2 ，1 4 4 2 ，( 1 4 4 + 1 ) 4 ，( 1 4 4 + 2 ) 4 ，( 1 4 4 + 3 ) 4 ，( 1 4 4 + 4 ) 4 ，( a 4 4 + 5 ) 2 ，( 1 4 4 + 7 ) 2 ，( 1 4 4 + 9 ) 2 ) 因此召与d 相关，由引理4 3 知一个( 4 3 2 ，2 ，4 ，4 ) - p c d p 存 在凸 当m 兰0 ( r o o d4 ) 时，我们可将m 写成如下形式：仇= 2 c , 3 t 3 比，g c d ( 6 ，p ) = 1 ， a 2 由引理2 3 知齐次( p ，4 ，1 ) c d m 存在当筘3 时由引理2 4 知齐次 ( 3 芦，4 ，1 ) c d m 存在因此，为了确定( 4 m ，4 ，4 ) p c d p s ( 仇三0 ( r o o d4 ) ) 的 存在性，我们只要解决如下情况：7 7 , = 2 c 3 6 ，j o ，1 ，2 ，a 2 由于齐次 ( 2 c , 3 矗，4 ，1 ) c d m 不存在，所以构作( 4 ( 2 口3 6 ) ，4 ，4 ) 一p c d p 非常困难下面我们 利用前面的例子构作( 4 m ，4 ，4 ) p c d p s ( 仇三0 ( r o o d4 ) ) 的若干无穷类 定理4 1 设缸为所有素因子均大于3 的奇正整数，对于n 2 ，3 ，4 ，5 ，6 ) ，则 存在( 4 2 a u ，4 ，4 ) 一p c d p 证明：由定理3 1 知当口 2 ，3 】时，( 4 2 a ，4 ，4 ) - p c d p 存在由例4 1 知 当q 4 ，5 ，6 ) 时，( 4 2 口，4 ，4 ) p c d p 存在对于所有素因子均大于3 的 奇正整数u ，由引理2 3 知齐次( p ，4 ，1 ) 一c d m 存在，所以应用引理2 6 ，对于 q 【2 ，3 ，4 ，5 ，6 ) ，( 4 - 2 口- t ，4 ，4 ) 一p c d p 存在 r l 定理4 2 设t 为所有素因子均大于3 的奇正整数，对于o 2 ，3 ，4 ，5 ) ，则存 在( 4 3 2 a t ，4 ，4 ) 一p c d p 证明：由定理3 1 知当口= 2 时，( 4 3 2 ，4 ，4 ) - p c d p 存在由例4 2 知 当q 3 ，4 ，5 ) 时，( 4 3 2 n ，4 ，4 ) p ( 3 d p 存在对于所有素因子均大于3 的 奇正整数u ，由引理2 3 知齐次( 弘，4 ，1 ) 一c d m 存在，所以应用引理2 6 ，对于 & 仫3 ，4 ，5 ) ，( 4 3 2 口“，4 ，4 ) 一p c d p 存在 凸 1 6 ( 4 m ，4 ，4 ) 一p c d p s 的构作四( 4 m ，4 ，4 ) - p c d p s ( m 三0( m o d4 ) ) 的构作 定理4 3 设u 为所有素因子均大于3 的奇正整数，对于口 2 ，3 ) ，则存在 ( 4 3 2 2 口t ，4 ，4 ) p c d p 证明：由例4 3 知当a 2 ，3 ) 时，( 4 3 2 2 a ，4 ，4 ) 一p c d p 存在对于所有素 因子均大于3 的奇正整数t i ，由引理2 3 知齐次( 弘，4 ，1 ) 一c d m 存在，所以应用 引理2 6 ，对于口 2 ，3 ) ，( 4 3 2 2 。t | ，4 ，4 ) 一p c d p 存在 ( 4 m ，4 ，4 ) 一p c d p s 的构作 参考文献 参考文献 f l 】y 。c h a n ga n dy 。m i a o ，c o n s t r u c t i o n sf o ro p t i m a lo p t i c a lo