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

Informations de base

  • ID de l'article: 2510.13122
  • Titre: Existence of 3 anti-cocircular truncated Möbius planes and constructions of strength-4 covering arrays
  • Auteurs: Kianoosh Shokri (Université d'Ottawa), Lucia Moura (Université d'Ottawa), Brett Stevens (Université Carleton)
  • Classification: math.CO (Mathématiques combinatoires)
  • Date de publication: 15 octobre 2025 (prépublication arXiv)
  • Lien de l'article: https://arxiv.org/abs/2510.13122

Résumé

Cet article étudie les problèmes de construction combinatoire en géométrie finie et en théorie des tableaux de couverture. Les auteurs démontrent que pour toute puissance de nombre premier impair q, il existe trois plans de Möbius tronqués anti-cocirculaires tels que l'intersection de tout triplet de cercles (un de chaque plan) contient au plus 3 éléments. Sur la base de cette structure géométrique, ils construisent des tableaux de couverture de force 4 : CA(3q⁴-2; 4, (q²+1)/2, q). Pour q≥11, ces tableaux améliorent les résultats optimaux connus d'environ 25%. De plus, une méthode de construction récursive est proposée, produisant CA(5q⁴-4q³-q²+2q; 4, q²+1, q).

Contexte et motivation de la recherche

Contexte du problème

  1. Importance des tableaux de couverture: Les tableaux de couverture jouent un rôle crucial dans les tests de logiciels, réduisant significativement le nombre de cas de test. Un tableau de couverture de force t, noté CA(N; t, k, v), est une matrice N×k garantissant que tous les t-uplets possibles apparaissent au moins une fois dans toute sélection de t colonnes.
  2. Méthodes de construction géométrique: La géométrie finie fournit des outils puissants pour construire des tableaux de couverture. Les plans projectifs orthogonaux permettent de construire des tableaux de couverture de force 3, mais la généralisation à la force 4 reste un défi.
  3. Limitations des méthodes existantes:
    • Les constructions actuelles de tableaux de couverture de force 4 reposent principalement sur la recherche computationnelle
    • Absence d'une théorie géométrique systématique
    • Pour les paramètres plus grands, les résultats connus laissent place à l'amélioration

Motivation de la recherche

La motivation centrale de cet article est de généraliser le succès des plans projectifs orthogonaux à des objets géométriques de dimension supérieure, en particulier aux ovoïdes dans PG(3,q) et aux plans de Möbius formés par leurs sections planes, afin de construire des tableaux de couverture de force 4 supérieurs.

Contributions principales

  1. Contribution théorique: Démonstration que pour toute puissance de nombre premier impair q, il existe trois plans de Möbius tronqués anti-cocirculaires tels que l'intersection de trois cercles quelconques (un de chaque plan) contient au plus 3 éléments.
  2. Méthode de construction: Construction explicite de tableaux de couverture de force 4 CA(3q⁴-2; 4, (q²+1)/2, q) basée sur la structure géométrique.
  3. Amélioration de performance: Pour q≥11, les nouveaux tableaux améliorent les résultats optimaux connus d'environ 25%.
  4. Extension récursive: Fourniture d'une méthode de construction récursive produisant des tableaux de couverture CA(5q⁴-4q³-q²+2q; 4, q²+1, q) utilisant tous les points de l'ovoïde.
  5. Insights géométriques: Établissement de liens profonds entre la théorie des hypersurfaces et la construction de tableaux de couverture.

Détails méthodologiques

Définition du problème

Construire un tableau de couverture de force 4, c'est-à-dire trouver une matrice N×k telle que pour toute sélection de 4 colonnes, tous les 4-uplets possibles (a,b,c,d)∈F_q⁴ apparaissent au moins une fois dans une ligne.

Construction géométrique centrale

1. Plans de Möbius et ovoïdes

  • Définition d'ovoïde: Un ovoïde O dans PG(3,q) est un ensemble de q²+1 points tel qu'aucun triplet n'est colinéaire
  • Plan de Möbius: Les sections planes d'un ovoïde forment un plan de Möbius d'ordre q, qui est un 3-(q²+1, q+1, 1)-design

2. Construction de trois plans de Möbius tronqués

Basée sur la matrice génératrice G_l^c, trois plans de Möbius tronqués sont définis:

  • M₁: (M^(e), {C∩M^(e) : C∈C}), où M^(e) est l'ensemble des points d'indice pair
  • M₂: (M^(e), {(C∩M^(e))/2 : C∈C})
  • M₁/₂: (M^(e), {2(C∩M^(e)) : C∈C})

Les matrices génératrices correspondantes sont respectivement G_{q+1}^{(q²+1)/2}, G_{2(q+1)}^{(q²+1)/2}, G_{(q+1)/2}^{(q²+1)/2}.

3. Preuve de la propriété anti-cocirculaire

Théorème central 4.25: Les trois plans de Möbius tronqués M₁, M₂, M₁/₂ satisfont la propriété anti-cocirculaire, c'est-à-dire que l'intersection de trois cercles quelconques (un de chaque plan) contient au plus 3 éléments.

Stratégie de preuve:

  1. Transformation linéaire Ω convertissant le problème géométrique en problème d'intersection d'hypersurfaces dans PG(3,q⁴)
  2. Utilisation des propriétés de la fonction trace Tr(α^i) pour établir une correspondance entre les différences et les hypersurfaces
  3. Calculs algébriques détaillés prouvant la borne supérieure de l'intersection

Points d'innovation technique

  1. Correspondance géométrie-algèbre: Établissement d'une bijection entre les cercles des plans de Möbius et les hypersurfaces dans PG(3,q⁴)
  2. Théorie de l'intersection d'hypersurfaces: Étude systématique des propriétés d'intersection des hypersurfaces linéaires, quadratiques et quartiques avec les ovoïdes
  3. Concept anti-cocirculaire: Généralisation du concept de plans orthogonaux aux plans de Möbius, définissant la propriété anti-cocirculaire
  4. Preuve constructive: Tous les résultats d'existence fournissent des méthodes de construction explicites

Configuration expérimentale

Vérification théorique

L'article est principalement un travail théorique, vérifiant la correction des résultats par des preuves mathématiques rigoureuses.

Plage de paramètres

  • Puissances de nombres premiers: Considération des puissances de nombres premiers impairs q = 3, 5, 7, 9, 11, 13, 17, 19, 23, 25
  • Paramètres des tableaux de couverture: Force t=4, nombre de colonnes k=(q²+1)/2 ou q²+1, nombre de symboles v=q

Références de comparaison

Comparaison avec les résultats optimaux connus dans le tableau des tableaux de couverture maintenu par Colbourn6.

Résultats expérimentaux

Résultats principaux

Performance des tableaux de couverture de force 4 CA(3q⁴-2; 4, (q²+1)/2, q)

qk=(q²+1)/2Nouvelle méthode N_sOptimal connu N_cTaux d'amélioration
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%

Performance de la construction récursive CA(5q⁴-4q³-q²+2q; 4, q²+1, q)

qk=q²+1Nouvelle méthode N_sOptimal connu N_cTaux d'amélioration
1112267,78270,521-3,9%
13170133,874138,385-3,3%
17290397,698412,369-3,6%
19362623,846644,347-3,2%

Découvertes clés

  1. Amélioration significative: Pour q≥11, la nouvelle construction réalise une amélioration de 21-25% avec les paramètres k=(q²+1)/2
  2. Extension récursive: La méthode récursive permet de traiter plus de colonnes, avec une amélioration modérée mais toujours supérieure aux résultats connus
  3. Optimalité théorique: La méthode de construction possède une base géométrique explicite, fournissant des orientations pour les optimisations futures

Travaux connexes

Théorie des plans orthogonaux

  • Développement historique: L'existence de plans projectifs orthogonaux a été prouvée indépendamment plusieurs fois1,4,14,16,19,25,31
  • Méthodes de construction: Incluant les méthodes de polynômes primitifs, transformations de Cremona et autres techniques
  • Applications: Construction réussie de tableaux de couverture de force 3 CA(2q³-1; 3, q²+q+1, q)

Construction de tableaux de couverture

  • Méthodes computationnelles: Basées sur le recuit simulé, algorithmes gloutons et autres méthodes heuristiques
  • Méthodes algébriques: Utilisant les corps finis, les différences et autres structures algébriques
  • Méthodes géométriques: Catégorie à laquelle appartient cet article, utilisant les propriétés combinatoires de la géométrie projective

Objets géométriques de dimension supérieure

  • Théorie des ovoïdes: Recherche sur la classification et les propriétés des ovoïdes dans PG(3,q)
  • Plans de Möbius: Structures combinatoires en tant que 3-designs
  • Géométrie des hypersurfaces: Propriétés géométriques des variétés algébriques comme les formes quadratiques et quartiques

Conclusions et discussion

Conclusions principales

  1. Théorème d'existence: Pour toute puissance de nombre premier impair q, il existe trois plans de Möbius tronqués anti-cocirculaires
  2. Théorème de construction: Sur la base de cette structure géométrique, on peut construire explicitement des tableaux de couverture de force 4
  3. Théorème de performance: La nouvelle construction atteint les résultats optimaux connus pour plusieurs paramètres

Limitations

  1. Restriction aux puissances de nombres premiers impairs: Les résultats actuels s'appliquent uniquement aux puissances de nombres premiers impairs; le cas des puissances de nombres premiers pairs reste à résoudre
  2. Plage de paramètres: Bien que l'amélioration soit significative, elle n'est efficace que pour une plage de paramètres spécifique
  3. Complexité computationnelle: Le processus de construction implique des calculs algébriques complexes, et l'implémentation pratique peut présenter des défis

Directions futures

  1. Généralisation à la force 5: Les auteurs mentionnent la possibilité de construire des tableaux de couverture de force 5
  2. Extension aux puissances de nombres premiers pairs: Recherche de constructions similaires applicables aux puissances de nombres premiers pairs
  3. Optimisation récursive: Amélioration de la construction récursive pour obtenir de meilleurs paramètres
  4. Implémentation computationnelle: Développement d'algorithmes efficaces pour implémenter ces constructions théoriques

Évaluation approfondie

Points forts

  1. Profondeur théorique: Fusion parfaite de la théorie géométrique abstraite avec les problèmes de construction combinatoire concrets
  2. Force d'innovation: L'introduction du concept anti-cocirculaire ouvre de nouvelles directions de recherche dans ce domaine
  3. Résultats remarquables: L'amélioration de 25% en performance constitue une percée majeure dans ce domaine
  4. Systématique méthodologique: Formation d'un système méthodologique complet, des preuves théoriques aux constructions concrètes
  5. Clarté de la rédaction: Exposition claire et ordonnée de concepts géométriques et algébriques complexes

Insuffisances

  1. Portée d'application: Limitation aux puissances de nombres premiers impairs, réduisant l'universalité de la méthode
  2. Complexité computationnelle: Bien que des constructions explicites soient fournies, les calculs pratiques restent complexes
  3. Vérification expérimentale: En tant que travail théorique, manque de vérification computationnelle à grande échelle
  4. Analyse d'application: Discussion limitée des applications pratiques aux tests de logiciels

Impact

  1. Valeur académique: Fournit une nouvelle perspective géométrique à la théorie des tableaux de couverture, susceptible d'inspirer davantage de recherches
  2. Valeur pratique: L'amélioration significative de performance a une valeur directe pour les applications en tests de logiciels et domaines connexes
  3. Contribution méthodologique: Le cadre géométrie-algèbre établi peut s'appliquer à d'autres problèmes d'optimisation combinatoire
  4. Extensibilité: Pose les fondations pour la construction de tableaux de couverture de force 5 et supérieure

Scénarios d'application

  1. Tests de logiciels: Génération de cas de test pour les tests combinatoires de systèmes logiciels à grande échelle
  2. Conception d'expériences: Conception d'expériences orthogonales en statistique
  3. Théorie du codage: Construction et analyse de codes correcteurs d'erreurs
  4. Cryptographie: Analyse de sécurité de certains protocoles cryptographiques

Références bibliographiques

L'article cite 33 références pertinentes, incluant principalement:

  • Fondements théoriques en géométrie: Manuels classiques de géométrie projective par Bose3, Casse5 et autres
  • Théorie des plans orthogonaux: Travaux fondateurs de Baker et al.1, Bruck4, Glynn14 et autres
  • Théorie des tableaux de couverture: Littérature de synthèse par Colbourn7,8, Torres-Jimenez et al.29 et autres
  • Méthodes computationnelles: Résultats constructifs de Raaphorst et al.25, Panario et al.22 et autres

Évaluation globale: Cet article est un excellent travail combinant profondeur théorique et valeur pratique. Par des constructions géométriques ingénieuses, il résout des problèmes importants en théorie des tableaux de couverture, apportant une contribution significative au développement du domaine. Bien que présentant certaines limitations, ses méthodes innovantes et ses résultats remarquables en font un progrès important dans ce domaine.