英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
强度为3的新的正交阵和覆盖阵的构造
季利均，殷剑兴
苏州大学数学系，江苏苏州 215006
摘要：一个大小为N，强度为t，度为k，阶数为v的覆盖阵列，或简称CA（N; t,k,v），是一个取自v元符号上的阵列. 在每个ttimes;N的子阵列中，每个t元组列向量至少出现一次. 当“至少”被替换为“完全”时，这定义了一个正交数组OA(t,k,v). 一个差异覆盖阵列，或者一个 DCA(k,n; v)，在v阶的交换群G上是一个元素来自于G的ktimes;n阵列()(1ik,1jn)，使得对于D的任意两个不同的行l和h(1llt;hk),差异列表Delta;={d-d,d-d,...,d-d }包含G的每个元素至少一次.
覆盖阵列在统计和计算机科学以及药物筛选中有重要的应用. 在本文中，我们提出了两种使用DCAs的方法来获得强度为3的正交阵列和覆盖阵列. 因此，我们证明了对于任意整数v4和v2 (mod 4)有一个OA（3,5,v)，并且一个 OA(3, 6, v)对任意正整数v满足gcd(v,4)2且gcd(v,18)3. 还证明了当k=5且v2 (mod 4)或者k=6,v2 (mod 4)且gcd(v,18)3时，CA（N; 3,k,v）的大小CAN（3，k，v）不能超过v v.
关键词：正交阵列；覆盖阵列；差异覆盖阵列
Constructions of new orthogonal arrays and covering arrays of strength three
Lijun Ji, Jianxing Yin
Department of Mathematics, Suzhou University, Suzhou 215006, China
Abstract: A covering array of size N, strength t, degree k, and order v, or a CA(N;t,k, v) in short, is a k times; N array on v symbols. In every t times; N subarray, each t-tuple column vector occurs at least once. When lsquo;at leastrsquo; is replaced by lsquo;exactlyrsquo;, this defines an orthogonal array, OA(t,k,v). A difference covering array, or a DCA(k,n; v), over an abelian group G of order v is a k times;n array (a) (1ik,1jn) with entries from G, such that, for any two distinct rows l and h of D (1l lt; hk), the difference list ={d-d,d-d,...,d-d} contains every element of G at least once. Covering arrays have important applications in statistics and computer science, as well as in drug screening. In this paper, we present two constructive methods to obtain orthogonal arrays and covering arrays of strength 3 by using DCAs. As a consequence, it is proved that there are an OA(3, 5, v) for any integer v4 and v2 (mod 4), and an OA(3, 6, v) for any positive integer v satisfying gcd(v,4)2 and gcd(v, 18).It is also proved that the size CAN(3,k, v) of a CA(N; 3,k, v) cannot exceed v vwhen k = 5 and v equiv; 2 (mod 4), or k = 6, v equiv; 2 (mod 4) and gcd(v, 18)3.
Keyword: Orthogonal array, Covering array, Difference matrix
- 介绍
一个覆盖阵列或者简称CA（N; t, k, v）是一个定义在v元集上的Ntimes;k阵列. 在每个ttimes;N的子阵列中，每个t元组列向量至少出现一次. 其中t为相互作用覆盖的强度，k是因子数，v是每个因素的水平数，在上下文无关紧要时，大小N被忽略. 使CA（N; t, k, v）存在的最小的正整数N称为覆盖数，记做CAN(t, k, v).
当在CA（N; t, k, v）的定义中，“至少”被“恰好”替换时，上述的定义被称为正交阵列，用OA（N; t, k, v）表示，或简短的表示为 OA(t, k, v). 这意味着当N=时，一个OA（N; t, k, v）是一个CA（N; t, k, v）. 在t = 2的情况下，OA（N;2，k，v）等价于边v的一组k - 2个相互正交的拉丁方.当t3时，它也相当于一个横向的t设计.
众所周知(见[1,7,22])，覆盖阵列，特别是正交阵列，在设计理论中是很重要的. 它们在统计学，编码理论和计算机科学以及药物筛选方面也有各种各样的应用. 在这方面，有兴趣的读者可参见 [2,6,13,21,22]. 函数CAN(t, k, v)的确定一直是许多研究的主题(例如[5,7,11,12]). 覆盖阵列也被 Seroussi和 Bshouty [18]作为t-surjective阵列， Stevens和Mendelsohn [19,20]作为横向覆盖以及由Kouml;rner等人[15,17]的一组大小为N的定性独立分区来研究.关于t3时OA(t, k, v)的存在性，以下的显着结果是 Bush [4]的功劳.
定理 1.1.(见[4].) 如果n是素数，且tlt;n，则OA（t,n 1,n)存在. 而且如果n4是2的幂，则OA（3,n 2,n）存在.
在本文中，我们将主要精力集中在强度为3的覆盖阵列上. 我们提出了两种建设性的方法来构造强度为3的正交阵列和覆盖阵列. 因此，我们证明了对于任意整数v4和v 2 (mod 4)时有一个OA(3,5,v)，并且一个OA(3, 6, v)对任意正整数v满足gcd(v,4)2且gcd(v,18)3. 还证明了当k=5且v2 (mod 4)或者k=6,v2 (mod 4)且gcd(v,18)3时，CA(N; 3,k,v)的大小CAN(3,k,v)不能超过v v.
- 第一个构造
我们的第一个构造方法使用差覆盖数组(DCAs).
设G是v阶的阿贝尔群，参见 [24]，一个差覆盖阵列，或者一个 DCA(k, n; v)，是一个元素来自于G的ktimes;n阵列()(1ik,1jn)，使得对于D的任意两个不同的行l和h(1llt;hk),差异列表 Delta;={d-d,d-d,...,d-d}包含G的每个元素至少一次. 当“至少”被“恰好”替换时，这定义了一个差矩阵（（v,k;1）-DM).一个在v阶循环群上的DM（DCA）被认为是循环的并且由CDM（CDCA）表示.
差覆盖阵列和差异矩阵已经被证明是在覆盖阵列的建设是非常有用的.在[7,24]中表明了一个DCA（k, n; v）可以用来构造一个CA(vn;2,k,v). 有关差异矩阵的详细信息，读者可以参考[1,8]及其中的参考文献. 朱和第一作者[14]使用（g,4;1）-DM构造的g成对不相交横向设计TD(2,4,g)相当于一个TD（3,5,g)[16]. 我们在下面的定理中陈述的第一个构造可以被看作是上述思想的一个概括.
定理 2.1. 如果DCA（4,n;v）存在，则CA（vn;3,5,v）存在.
证明：设D =（d）是在阿贝尔群G上给定的一个DCA(4,n;v). 对于这个DCA的每一列(d,d,d,d)，构造以下列：
C(j, u, e)=(d u, d u, d u e, d u e, e),其中e, uG.
表1
需要检查由上述vtimes;n列组成的矩阵M是一个CA(3,5,v). 我们只需要证明任何列B =(x, y, z)出现在M的行a，b，c上至少一次，其中1alt;blt;c5.
情况1. 假设c = 5. 如果(a, b){(1,2), (3,4)}，则有一个整数jI= {1，2，...，n}使得d-d= y-x，因为D是G上的一个DCA(4,n; v). 那么当（a, b）=（1,2）时，B出现在M的行a，b，c的列C（j, x - d,z）和（a，b）=（3,4）时，B出现在列C（j, x-z-d,z）中. 如果(a, b){(1,3),(1,4),(2,3),(2,4)}，则有一个整数jI使得d-d=y minus; z minus; x，那么B出现在M的行a，b，c的列C（j, x-d,z）上.
情况2. 假设c lt;5. 如果(a, b, c){(1,2,3),(1,2,4)}，则有一个整数jI使得d-d= y-x，那么B出现在M的行a，b，c的列C（j, x - d,z-x-d d）中，如果(a, b, c){(1,3,4),(2,3,4)}，则有一个整数jI使得d-d=zminus;y，那么B出现在M的行a，b，c的列C（j, x - d,z-x-d d）中，证毕.
如果我们从（v,4; 1）-DM开始，而不是从DCA（4,n; v）开始，那么我们从定理2.1得到下面已知的结论.
在[9,23]中已被证明（v,4; 1）-DM只有在v2（mod 4）的情况下才存在，而（v，4; 1）-CDM只有在v是奇数时才存在.
推论2.2. (见[14,16]) 如果（v,4; 1）-DM存在，则OA(3,5,v)存在.
引理2.3. (见[10]) 设v4是一个整数，如果v2 (mod 4)，那么一个(v, 4; 1)-DM存在.
引理2.4. (见[23]) 对于所有的正整数v，都存在一个CDCA(4,v 1; v).
从引理2.3和引理2.4，我们可以应用推论2.2和定理2.1来建立以下结果.
引理2.5. 设v4是一个整数，如果v2 (mod 4)，那么存在一个OA（3，5，v）.
引理2.6. 对于任何偶正整数v，都存在一个CA（v v; 3,5,v），因此CAN(3，5，v)v v.
在定理2.5和2.6中建立的结果降低了我们在表1中展示的已知CAN（3，5，v）的上界.
- 第二个构造
3.1 构造原理的描述
我们的第二个结构使用差覆盖阵列满足一个更多的要求.
设D =（d）是在阿贝尔群G上给定的DCA(4，n; v). 如果G中的每个元素都在多重集{s, s,..., s}上至少出现一次，一个在G上的n元组s =(s, s,..., s)被称为覆盖数组D的加法器，并且矩阵
D=(d)，其中d=d(i{1,2})，d=d s(i{3,4}),
也是在G上的一个DCA(4,n; v).
引理 3.1. 有一个CDCA（4,3;2）和一个CDCA（4,11;10）与一个加法器相关联.
证明：在Z上的一个CDCA（4，3; 2）由以下矩阵给出：
在这里，数组的前四行形成一个DCA（4,3; 2），最后一行是它的相应加法器.
在Z上的一个CDCA（4，11; 10）由以下矩阵给出：
如上所述，前四行形成一个CDCA（4,11; 10），最后一行是其相应的加法器.
利用与加法器相关的DCA（4,n; v），我们可以给出我们的第二个构造.
定理 3.2. 如果存在一个与加法器相关联的DCA（4,n; v），则存在一个CA(vn; 3,6,v).
证明：设D =（d）和s =(s, s,..., s)分别是在阿贝尔群G上给定的DCA(4，n; v)及其相对应的加法器.
对于这个DCA的每一列(d,d,d,d)，构造以下列：
C(j, u, e)=(d u, d u, d u e s, d u e s, e, e s),其中e, uG.
只需检查由上述vtimes;n列组成的矩阵M是一个CA(3，6，v).
考虑由第1,2,3,4和6行组成的子矩阵，类似于定理2.1的证明，它是CA（3，5，v），因为D是DCA(4,n; v). 类似地，由行1,2,3,4和5组成的子矩阵也是一个CA（3,5，v），因为D通过定义一个相关的加法器也是一个DCA(4,n;v). 那么我们只需要证明对于i{1,2,3,4}，由行i，5,6组成的每个子矩阵至少包含列向量B =(x，y，z)至少一次.
由于每个组元素在相关的加法器中至少出现一次，则有一个整数jI使得s= z-y. 如果i{1,2}，那
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[23670]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
