2025-11-12T01:01:29.514663

Existence of 3 anti-cocircular truncated Möbius planes and constructions of strength-4 covering arrays

Shokri, Moura, Stevens
Two projective (affine) planes with the same point sets are orthogoval if the common intersection of any two lines, one from each, has size at most two. The existence of a pair of orthogoval projective planes has been proven and published independently many times. A strength-$t$ covering array, denoted by CA$(N; t, k, v)$, is an $N \times k$ array over a $v$-set such that in any $t$-set of columns, each $t$-tuple occurs at least once in a row. A pair of orthogoval projective planes can be used to construct a strength-$3$ covering array CA$(2q^3-1; 3, q^2 + q + 1, q)$. Our work extends this result to construct arrays of strength $4$. A $k$-cap in a projective geometry is a set of $k$ points no three of which are collinear. In $PG(3,q)$, an ovoid is a maximum-sized $k$-cap with $k =q^2+1$. Its plane sections (circles) are the blocks of a $3-(q^2 + 1, q + 1, 1)$ design, called a Möbius plane of order $q$. For $q$ an odd prime power, we prove the existence of three truncated Möbius planes, such that for any choice of these circles, one from each plane, their intersection size is at most three. From this, we construct a strength-$4$ covering array CA$(3q^4-2; 4, \frac{q^2+1}{2}, q)$. For $q \geq 11$, these covering arrays improve the size of the best-known covering arrays with the same parameters by almost 25 percent. The CA$(3q^4 -3; 4, \frac{q^2 +1}{2}, q)$ is used as the main ingredient in a recursive construction to obtain a CA$(5q^4 - 4q^3 - q^2 + 2q; 4, q^2 +1, q)$. Some improvements are obtained in the size of the best-known arrays using these covering arrays.
academic

Existence of 3 anti-cocircular truncated Möbius planes and constructions of strength-4 covering arrays

基本信息

  • 论文ID: 2510.13122
  • 标题: Existence of 3 anti-cocircular truncated Möbius planes and constructions of strength-4 covering arrays
  • 作者: Kianoosh Shokri (University of Ottawa), Lucia Moura (University of Ottawa), Brett Stevens (Carleton University)
  • 分类: math.CO (组合数学)
  • 发表时间: 2025年10月15日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.13122

摘要

本文研究了有限几何与覆盖阵列的组合构造问题。作者证明了对于奇质数幂q，存在三个反共圆截断Möbius平面，使得从每个平面中任选一个圆的交集大小至多为3。基于此几何结构，构造了强度为4的覆盖阵列CA(3q⁴-2; 4, (q²+1)/2, q)。对于q≥11，这些覆盖阵列比已知最优结果改进了近25%。此外，还给出了递归构造方法，得到CA(5q⁴-4q³-q²+2q; 4, q²+1, q)。

研究背景与动机

问题背景

  1. 覆盖阵列的重要性：覆盖阵列在软件测试中具有重要应用，可以显著减少测试用例数量。强度为t的覆盖阵列CA(N; t, k, v)是一个N×k的阵列，保证任意t列的所有可能t元组都至少出现一次。
  2. 几何构造方法：有限几何为构造覆盖阵列提供了强有力的工具。已知正交射影平面可以构造强度为3的覆盖阵列，但推广到强度4的构造一直是个挑战。
  3. 现有方法的局限性：
    • 现有的强度4覆盖阵列构造方法主要依赖于计算搜索
    • 缺乏系统的几何构造理论
    • 对于较大参数，已知结果的规模仍有改进空间

研究动机

本文的核心动机是将正交射影平面的成功经验推广到高维几何对象，特别是PG(3,q)中的卵形(ovoid)及其平面截面形成的Möbius平面，以构造更优的强度4覆盖阵列。

核心贡献

  1. 理论贡献：证明了对于奇质数幂q，存在三个反共圆截断Möbius平面，任意选择的三个圆(每个平面一个)的交集大小至多为3。
  2. 构造方法：基于几何结构，给出了强度4覆盖阵列CA(3q⁴-2; 4, (q²+1)/2, q)的显式构造。
  3. 性能改进：对于q≥11，新构造的覆盖阵列比已知最优结果改进了约25%。
  4. 递归扩展：提供了递归构造方法，得到使用全部卵形点的覆盖阵列CA(5q⁴-4q³-q²+2q; 4, q²+1, q)。
  5. 几何洞察：建立了超曲面理论与覆盖阵列构造之间的深层联系。

方法详解

任务定义

构造强度为4的覆盖阵列，即找到N×k矩阵A，使得对于任意4列，所有可能的4元组(a,b,c,d)∈F_q⁴都至少在某一行出现一次。

核心几何构造

1. Möbius平面与卵形

  • 卵形定义：PG(3,q)中的卵形O是q²+1个点的集合，其中任意三点不共线
  • Möbius平面：卵形的平面截面构成3-(q²+1, q+1, 1)设计，称为阶数为q的Möbius平面

2. 三个截断Möbius平面的构造

基于生成矩阵G_l^c，定义三个截断Möbius平面：

  • M₁: (M^(e), {C∩M^(e) : C∈C})，其中M^(e)为偶数索引点集
  • M₂: (M^(e), {(C∩M^(e))/2 : C∈C})
  • M₁/₂: (M^(e), {2(C∩M^(e)) : C∈C})

对应的生成矩阵分别为G_{q+1}^{(q²+1)/2}, G_{2(q+1)}^{(q²+1)/2}, G_{(q+1)/2}^{(q²+1)/2}。

3. 反共圆性质的证明

核心定理4.25：三个截断Möbius平面M₁, M₂, M₁/₂满足反共圆性质，即任意选择三个圆(每个平面一个)的交集大小至多为3。

证明思路：

  1. 通过线性变换Ω将几何问题转化为PG(3,q⁴)中的超曲面交集问题
  2. 利用迹函数Tr(α^i)的性质建立差集与超曲面的对应关系
  3. 通过详细的代数计算证明交集的上界

技术创新点

  1. 几何-代数对应：建立了Möbius平面的圆与PG(3,q⁴)中超曲面的一一对应关系
  2. 超曲面交集理论：系统研究了线性、二次、四次超曲面与卵形的交集性质
  3. 反共圆概念：推广了正交平面的概念到Möbius平面，定义了反共圆性质
  4. 构造性证明：所有存在性结果都给出了显式的构造方法

实验设置

理论验证

论文主要是理论性工作，通过严格的数学证明验证结果的正确性。

参数范围

  • 质数幂：考虑奇质数幂q = 3, 5, 7, 9, 11, 13, 17, 19, 23, 25
  • 覆盖阵列参数：强度t=4，列数k=(q²+1)/2或q²+1，符号数v=q

对比基准

与Colbourn维护的覆盖阵列表6中的已知最优结果进行比较。

实验结果

主要结果

强度4覆盖阵列CA(3q⁴-2; 4, (q²+1)/2, q)的性能

qk=(q²+1)/2新方法N_s已知最优N_c改进率
116143,92155,891-21.4%
138585,681109,837-22.0%
17145250,561329,137-23.9%
19181390,961520,543-24.9%
23265839,5211,119,361-25.0%
253131,171,8731,562,497-25.0%

递归构造CA(5q⁴-4q³-q²+2q; 4, q²+1, q)的性能

qk=q²+1新方法N_s已知最优N_c改进率
1112267,78270,521-3.9%
13170133,874138,385-3.3%
17290397,698412,369-3.6%
19362623,846644,347-3.2%

关键发现

  1. 显著改进：对于q≥11，新构造在参数k=(q²+1)/2时实现了21-25%的改进
  2. 递归扩展：通过递归方法可以处理更多列数，虽然改进幅度较小但仍优于已知结果
  3. 理论最优性：构造方法具有明确的几何基础，为进一步优化提供了理论指导

相关工作

正交平面理论

  • 历史发展：正交射影平面的存在性被多次独立证明1,4,14,16,19,25,31
  • 构造方法：包括本原多项式方法、Cremona变换等多种技术
  • 应用：成功构造了强度3覆盖阵列CA(2q³-1; 3, q²+q+1, q)

覆盖阵列构造

  • 计算方法：基于模拟退火、贪心算法等启发式方法
  • 代数方法：利用有限域、差集等代数结构
  • 几何方法：本文所属类别，利用射影几何的组合性质

高维几何对象

  • 卵形理论：PG(3,q)中卵形的分类和性质研究
  • Möbius平面：作为3-设计的组合结构
  • 超曲面几何：二次型、四次型等代数簇的几何性质

结论与讨论

主要结论

  1. 存在性定理：对于任意奇质数幂q，存在三个反共圆截断Möbius平面
  2. 构造定理：基于此几何结构可以显式构造强度4覆盖阵列
  3. 性能定理：新构造在多个参数下达到了已知最优结果

局限性

  1. 奇质数幂限制：当前结果仅适用于奇质数幂，偶质数幂情况仍待解决
  2. 参数范围：虽然有显著改进，但仅在特定参数范围内有效
  3. 计算复杂性：构造过程涉及复杂的代数计算，实际实现可能面临挑战

未来方向

  1. 强度5推广：作者提到了构造强度5覆盖阵列的可能性
  2. 偶质数幂扩展：寻找适用于偶质数幂的类似构造
  3. 递归优化：改进递归构造以获得更好的参数
  4. 计算实现：开发高效的算法实现这些理论构造

深度评价

优点

  1. 理论深度：将抽象的几何理论与具体的组合构造问题完美结合
  2. 创新性强：反共圆概念的提出为该领域开辟了新的研究方向
  3. 结果显著：25%的性能改进在该领域属于重大突破
  4. 方法系统：从理论证明到具体构造，形成了完整的方法体系
  5. 写作清晰：复杂的几何和代数概念阐述得条理清楚

不足

  1. 适用范围：仅限于奇质数幂，限制了方法的普适性
  2. 计算复杂性：虽然给出了显式构造，但实际计算仍然复杂
  3. 实验验证：作为理论工作，缺乏大规模的计算验证
  4. 应用分析：对于实际软件测试应用的讨论较少

影响力

  1. 学术价值：为覆盖阵列理论提供了新的几何视角，可能启发更多研究
  2. 实用价值：显著的性能改进对软件测试等应用领域有直接价值
  3. 方法论贡献：建立的几何-代数框架可能适用于其他组合优化问题
  4. 可扩展性：为强度5及更高强度的覆盖阵列构造奠定了基础

适用场景

  1. 软件测试：大规模软件系统的组合测试用例生成
  2. 实验设计：统计学中的正交实验设计
  3. 编码理论：纠错码的构造和分析
  4. 密码学：某些密码协议的安全性分析

参考文献

论文引用了33篇相关文献，主要包括：

  • 几何理论基础：Bose3, Casse5等关于射影几何的经典教材
  • 正交平面理论：Baker et al.1, Bruck4, Glynn14等的开创性工作
  • 覆盖阵列理论：Colbourn7,8, Torres-Jimenez et al.29等的综述性文献
  • 计算方法：Raaphorst et al.25, Panario et al.22等的构造性结果

总体评价：这是一篇理论深度和实用价值并重的优秀论文，通过巧妙的几何构造解决了覆盖阵列理论中的重要问题，为该领域的发展做出了重要贡献。虽然存在一些局限性，但其创新的方法和显著的结果使其成为该领域的重要进展。