Existence of 3 Anti-cocircular Truncated Möbius Planes and Constructions of Strength-4 Covering Arrays

Basic Information

• Paper ID: 2510.13122
• Title: Existence of 3 anti-cocircular truncated Möbius planes and constructions of strength-4 covering arrays
• Authors: Kianoosh Shokri (University of Ottawa), Lucia Moura (University of Ottawa), Brett Stevens (Carleton University)
• Classification: math.CO (Combinatorics)
• Publication Date: October 15, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.13122

Abstract

This paper investigates combinatorial constructions in finite geometry and covering arrays. The authors prove that for odd prime powers q, there exist three anti-cocircular truncated Möbius planes such that the intersection of any one circle selected from each plane has size at most 3. Based on this geometric structure, they construct strength-4 covering arrays CA(3q⁴-2; 4, (q²+1)/2, q). For q≥11, these covering arrays improve upon previously known optimal results by approximately 25%. Additionally, recursive construction methods are provided, yielding CA(5q⁴-4q³-q²+2q; 4, q²+1, q).

Research Background and Motivation

Problem Background

1. Importance of Covering Arrays: Covering arrays have important applications in software testing, significantly reducing the number of test cases. A strength-t covering array CA(N; t, k, v) is an N×k array that guarantees all possible t-tuples appear at least once in any t columns.
2. Geometric Construction Methods: Finite geometry provides powerful tools for constructing covering arrays. Orthogonal projective planes are known to construct strength-3 covering arrays, but extending to strength-4 constructions has remained challenging.
3. Limitations of Existing Methods:
   • Existing strength-4 covering array constructions rely primarily on computational search
   • Lack of systematic geometric construction theory
   • For larger parameters, known results still have room for improvement

Research Motivation

The core motivation of this paper is to generalize the success of orthogonal projective planes to higher-dimensional geometric objects, particularly ovoidal plane sections in PG(3,q) forming Möbius planes, to construct superior strength-4 covering arrays.

Core Contributions

1. Theoretical Contribution: Proves that for odd prime powers q, there exist three anti-cocircular truncated Möbius planes such that the intersection of any three circles (one from each plane) has size at most 3.
2. Construction Method: Provides explicit construction of strength-4 covering arrays CA(3q⁴-2; 4, (q²+1)/2, q) based on geometric structures.
3. Performance Improvement: For q≥11, the newly constructed covering arrays achieve approximately 25% improvement over previously known optimal results.
4. Recursive Extension: Provides recursive construction methods yielding covering arrays CA(5q⁴-4q³-q²+2q; 4, q²+1, q) using all ovoid points.
5. Geometric Insights: Establishes deep connections between hypersurface theory and covering array construction.

Methodology Details

Problem Definition

Construct strength-4 covering arrays, i.e., find an N×k matrix A such that for any 4 columns, all possible 4-tuples (a,b,c,d)∈F_q⁴ appear at least once in some row.

Core Geometric Construction

1. Möbius Planes and Ovoidal Structures

• Ovoid Definition: An ovoid O in PG(3,q) is a set of q²+1 points where no three are collinear
• Möbius Plane: Plane sections of an ovoid form a 3-(q²+1, q+1, 1) design, called a Möbius plane of order q

2. Construction of Three Truncated Möbius Planes

Based on generating matrices G_l^c, three truncated Möbius planes are defined:

• M₁: (M^(e), {C∩M^(e) : C∈C}), where M^(e) is the set of points with even indices
• M₂: (M^(e), {(C∩M^(e))/2 : C∈C})
• M₁/₂: (M^(e), {2(C∩M^(e)) : C∈C})

The corresponding generating matrices are G_{q+1}^{(q²+1)/2}, G_{2(q+1)}^{(q²+1)/2}, G_{(q+1)/2}^{(q²+1)/2}, respectively.

3. Proof of Anti-cocircular Property

Core Theorem 4.25: The three truncated Möbius planes M₁, M₂, M₁/₂ satisfy the anti-cocircular property, i.e., the intersection of any three circles (one from each plane) has size at most 3.

Proof Strategy:

1. Transform the geometric problem into a hypersurface intersection problem in PG(3,q⁴) via linear transformation Ω
2. Establish correspondence between difference sets and hypersurfaces using properties of the trace function Tr(α^i)
3. Prove the intersection bound through detailed algebraic calculations

Technical Innovations

1. Geometric-Algebraic Correspondence: Establishes one-to-one correspondence between circles of Möbius planes and hypersurfaces in PG(3,q⁴)
2. Hypersurface Intersection Theory: Systematically studies intersection properties of linear, quadratic, and quartic hypersurfaces with ovoidal structures
3. Anti-cocircular Concept: Generalizes the concept of orthogonal planes to Möbius planes, defining the anti-cocircular property
4. Constructive Proofs: All existence results are accompanied by explicit construction methods

Experimental Setup

Theoretical Verification

The paper is primarily theoretical, verifying result correctness through rigorous mathematical proofs.

Parameter Range

• Prime Powers: Considers odd prime powers q = 3, 5, 7, 9, 11, 13, 17, 19, 23, 25
• Covering Array Parameters: Strength t=4, number of columns k=(q²+1)/2 or q²+1, alphabet size v=q

Comparison Benchmarks

Compared against known optimal results maintained in Colbourn's covering array table6.

Experimental Results

Main Results

Performance of Strength-4 Covering Arrays CA(3q⁴-2; 4, (q²+1)/2, q)

Performance of Recursive Construction CA(5q⁴-4q³-q²+2q; 4, q²+1, q)

Key Findings

1. Significant Improvement: For q≥11, the new construction achieves 21-25% improvement when k=(q²+1)/2
2. Recursive Extension: Recursive methods can handle more columns; while improvements are smaller, they still outperform known results
3. Theoretical Optimality: Construction methods have clear geometric foundations, providing theoretical guidance for further optimization

Related Work

Orthogonal Plane Theory

• Historical Development: Existence of orthogonal projective planes has been independently proven multiple times1,4,14,16,19,25,31
• Construction Methods: Include primitive polynomial methods, Cremona transformations, and other techniques
• Applications: Successfully constructed strength-3 covering arrays CA(2q³-1; 3, q²+q+1, q)

Covering Array Construction

• Computational Methods: Based on simulated annealing, greedy algorithms, and other heuristic approaches
• Algebraic Methods: Utilizing finite fields, difference sets, and other algebraic structures
• Geometric Methods: The category to which this paper belongs, utilizing combinatorial properties of projective geometry

Higher-Dimensional Geometric Objects

• Ovoid Theory: Classification and properties of ovoidal structures in PG(3,q)
• Möbius Planes: Combinatorial structures as 3-designs
• Hypersurface Geometry: Geometric properties of algebraic varieties such as quadratic and quartic forms

Conclusions and Discussion

Main Conclusions

1. Existence Theorem: For any odd prime power q, there exist three anti-cocircular truncated Möbius planes
2. Construction Theorem: Based on this geometric structure, strength-4 covering arrays can be explicitly constructed
3. Performance Theorem: The new construction achieves known optimal results across multiple parameters

Limitations

1. Odd Prime Power Restriction: Current results apply only to odd prime powers; the even prime power case remains open
2. Parameter Range: While significant improvements are achieved, they are effective only within specific parameter ranges
3. Computational Complexity: The construction process involves complex algebraic calculations, which may pose challenges for practical implementation

Future Directions

1. Strength-5 Generalization: Authors mention the possibility of constructing strength-5 covering arrays
2. Even Prime Power Extension: Seeking similar constructions applicable to even prime powers
3. Recursive Optimization: Improving recursive constructions to obtain better parameters
4. Computational Implementation: Developing efficient algorithms to implement these theoretical constructions

In-Depth Evaluation

Strengths

1. Theoretical Depth: Perfectly combines abstract geometric theory with concrete combinatorial construction problems
2. Strong Innovation: The introduction of the anti-cocircular concept opens new research directions in this field
3. Significant Results: The 25% performance improvement represents a major breakthrough in this area
4. Systematic Methodology: Forms a complete methodological system from theoretical proofs to concrete constructions
5. Clear Exposition: Complex geometric and algebraic concepts are presented in a well-organized manner

Weaknesses

1. Limited Scope: Restricted to odd prime powers, limiting the universality of the method
2. Computational Complexity: While explicit constructions are provided, practical computation remains complex
3. Experimental Verification: As theoretical work, lacks large-scale computational verification
4. Application Analysis: Limited discussion of practical applications in software testing

Impact

1. Academic Value: Provides new geometric perspectives for covering array theory, potentially inspiring further research
2. Practical Value: Significant performance improvements have direct value for software testing and related applications
3. Methodological Contribution: The established geometric-algebraic framework may apply to other combinatorial optimization problems
4. Extensibility: Lays foundation for constructing strength-5 and higher-strength covering arrays

Applicable Scenarios

1. Software Testing: Combinatorial test case generation for large-scale software systems
2. Experimental Design: Orthogonal experimental design in statistics
3. Coding Theory: Construction and analysis of error-correcting codes
4. Cryptography: Security analysis of certain cryptographic protocols

References

The paper cites 33 related references, primarily including:

• Geometric Theory Foundations: Classical textbooks by Bose3, Casse5, and others on projective geometry
• Orthogonal Plane Theory: Pioneering work by Baker et al.1, Bruck4, Glynn14, and others
• Covering Array Theory: Survey literature by Colbourn7,8, Torres-Jimenez et al.29, and others
• Computational Methods: Constructive results by Raaphorst et al.25, Panario et al.22, and others

Overall Assessment: This is an excellent paper that balances theoretical depth with practical value, solving important problems in covering array theory through ingenious geometric constructions and making significant contributions to the field. While certain limitations exist, its innovative methodology and significant results represent important progress in this research area.