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

3 प्रतिसहवृत्ताकार छिन्न Möbius तलों का अस्तित्व और शक्ति-4 आवरण सरणियों का निर्माण

मूल जानकारी

  • पत्र ID: 2510.13122
  • शीर्षक: Existence of 3 anti-cocircular truncated Möbius planes and constructions of strength-4 covering arrays
  • लेखक: Kianoosh Shokri (ओटावा विश्वविद्यालय), Lucia Moura (ओटावा विश्वविद्यालय), Brett Stevens (कार्लटन विश्वविद्यालय)
  • वर्गीकरण: math.CO (संयोजन गणित)
  • प्रकाशन समय: 15 अक्टूबर 2025 (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 आदि के निर्माणात्मक परिणाम

समग्र मूल्यांकन: यह एक उत्कृष्ट पत्र है जो सैद्धांतिक गहराई और व्यावहारिक मूल्य दोनों को संतुलित करता है। चतुर ज्यामितीय निर्माण के माध्यम से आवरण सरणी सिद्धांत में एक महत्वपूर्ण समस्या को हल किया गया है, जो इस क्षेत्र के विकास में महत्वपूर्ण योगदान देता है। हालांकि कुछ सीमाएँ हैं, लेकिन इसकी नवीन विधि और उल्लेखनीय परिणाम इसे इस क्षेत्र में एक महत्वपूर्ण प्रगति बनाते हैं।