2025-11-11T16:10:09.893794

On the Combinatorics of Pseudo-Latin Squares

Pendleton
We introduce a new class of combinatorial objects called consecutive pseudo-Latin squares (CPLSs), a variant of Latin squares in which at least one row or column is in consecutive or reverse-consecutive order, but every element may not appear in every row or column. We derive exact and asymptotic formulas for the number of CPLSs of order $n$, showing that their proportion among all pseudo-Latin squares (PLSs) rapidly approaches zero as $n\to\infty$. We also analyze the distribution of CPLSs under uniform random sampling, and explore connections to algebraic structures, interpreting CPLSs as Cayley tables related to those of unital magmas. Finally, we supplement our theoretical results with Monte Carlo simulations for small values of $n$.
academic

छद्म-लैटिन वर्गों की संयोजकता पर

मूल जानकारी

  • पेपर ID: 2510.11980
  • शीर्षक: On the Combinatorics of Pseudo-Latin Squares
  • लेखक: Andrew Pendleton
  • वर्गीकरण: math.CO (संयोजक गणित)
  • प्रकाशन समय: सितंबर 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2510.11980

सारांश

यह पेपर एक नई संयोजक वस्तु - सतत छद्म-लैटिन वर्ग (CPLSs) - का परिचय देता है, जो लैटिन वर्गों का एक प्रकार है जिसमें कम से कम एक पंक्ति या स्तंभ सतत या विपरीत सतत क्रम में होता है, लेकिन प्रत्येक तत्व आवश्यक रूप से प्रत्येक पंक्ति या स्तंभ में प्रकट नहीं होता है। लेखक n-क्रम CPLSs की संख्या के लिए सटीक और स्पर्शोन्मुख सूत्र प्राप्त करते हैं, यह साबित करते हैं कि जब n→∞ होता है, तो CPLSs का अनुपात सभी छद्म-लैटिन वर्गों (PLSs) में तेजी से शून्य की ओर प्रवृत्त होता है। लेख समान यादृच्छिक नमूनाकरण के तहत CPLSs के वितरण का विश्लेषण करता है, बीजगणितीय संरचनाओं के साथ संबंध की खोज करता है, CPLSs को एकात्मक मैग्मा (unital magmas) से संबंधित Cayley तालिकाओं के रूप में व्याख्या करता है। अंत में, छोटे n मानों के लिए सैद्धांतिक परिणामों को मोंटे कार्लो सिमुलेशन द्वारा सत्यापित किया जाता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

1. समस्या का प्रस्तुतीकरण

यह अनुसंधान लैटिन वर्गों के संयोजक गुणों की खोज से उत्पन्न होता है। परंपरागत लैटिन वर्गों के लिए आवश्यक है कि प्रत्येक तत्व प्रत्येक पंक्ति और स्तंभ में बिल्कुल एक बार प्रकट हो, जबकि छद्म-लैटिन वर्ग इस बाधा को शिथिल करते हैं, जिससे तत्वों को विभिन्न पंक्तियों और स्तंभों में अलग-अलग बार प्रकट होने की अनुमति मिलती है। लेखक विशेष रूप से सतत गुणों वाले छद्म-लैटिन वर्गों पर ध्यान केंद्रित करते हैं।

2. अनुसंधान प्रेरणा

  • खेल-प्रेरित: अनुसंधान प्रेरणा donotfindthefox.com वेबसाइट के "FOX in Boxes" खेल से आती है, जिसमें 4×4 ग्रिड में विशिष्ट शब्दों को वर्तनी से बचने के लिए यादृच्छिक रूप से अक्षर रखे जाते हैं
  • सैद्धांतिक मूल्य: सातत्य संयोजक संरचनाओं में एक महत्वपूर्ण गुण है, और छद्म-लैटिन वर्गों में इसके प्रदर्शन का अध्ययन सैद्धांतिक महत्व रखता है
  • अनुप्रयोग संभावनाएं: लैटिन वर्ग और उनके प्रकार प्रायोगिक डिजाइन, क्रिप्टोग्राफी, त्रुटि-सुधार कोड आदि क्षेत्रों में व्यापक अनुप्रयोग रखते हैं

3. मौजूदा अनुसंधान की सीमाएं

  • परंपरागत लैटिन वर्ग सिद्धांत मुख्य रूप से पूर्ण संतुलित संरचनाओं पर केंद्रित है
  • शिथिल बाधाओं वाले छद्म-लैटिन वर्गों के लिए, विशेष रूप से विशेष गुणों (जैसे सातत्य) वाले प्रकारों के लिए, व्यवस्थित सैद्धांतिक विश्लेषण की कमी है
  • बड़े पैमाने पर इस प्रकार की वस्तुओं के स्पर्शोन्मुख व्यवहार की गहन समझ की कमी है

मुख्य योगदान

  1. नई अवधारणा परिभाषा: सतत छद्म-लैटिन वर्गों (CPLSs) की पहली बार व्यवस्थित परिभाषा
  2. सटीक गणना सूत्र: n-क्रम CPLSs की संख्या के लिए सटीक संयोजक सूत्र की व्युत्पत्ति
  3. स्पर्शोन्मुख विश्लेषण: यह साबित करना कि CPLSs का अनुपात सभी PLSs में 4nn+1(n2−n)!(n2)!\frac{4n^{n+1}(n^2-n)!}{(n^2)!} की गति से शून्य की ओर प्रवृत्त होता है
  4. संभाव्यता वितरण: यादृच्छिक PLS में सतत पंक्तियों और स्तंभों की संख्या के संभाव्यता द्रव्यमान फलन का पूर्ण लक्षण वर्णन
  5. बीजगणितीय व्याख्या: CPLSs और निकट-एकात्मक मैग्मा Cayley तालिकाओं के बीच पत्राचार की स्थापना
  6. कम्प्यूटेशनल सत्यापन: बड़े पैमाने पर मोंटे कार्लो सिमुलेशन द्वारा सैद्धांतिक परिणामों की सटीकता का सत्यापन

विधि विवरण

कार्य परिभाषा

छद्म-लैटिन वर्ग (PLS): n-क्रम छद्म-लैटिन वर्ग एक n×n सरणी है, जिसके तत्व बहु-समुच्चय {1,1,…,1,2,2,…,n,n,…,n}\{1,1,\ldots,1,2,2,\ldots,n,n,\ldots,n\} से आते हैं, जहां प्रत्येक तत्व की बहुलता n है।

सतत छद्म-लैटिन वर्ग (CPLS): कम से कम एक पंक्ति या स्तंभ सतत या विपरीत सतत क्रम में होने वाला छद्म-लैटिन वर्ग।

मुख्य विधि आर्किटेक्चर

1. गणना सैद्धांतिक ढांचा

लेखक मुख्य गणना उपकरण के रूप में समावेशन-बहिष्करण सिद्धांत (PIE) का उपयोग करते हैं:

  • RR को कम से कम एक सतत पंक्ति वाले n-क्रम PLSs का समुच्चय मानें
  • CC को कम से कम एक सतत स्तंभ वाले n-क्रम PLSs का समुच्चय मानें
  • तब Σn=R∪C\Sigma_n = R \cup C, और ∣Σn∣=∣R∣+∣C∣−∣R∩C∣|\Sigma_n| = |R| + |C| - |R \cap C|

2. निर्माणात्मक गणना विधि

निम्नलिखित चरणों के माध्यम से विभिन्न प्रकार के PLSs की संख्या की गणना करें:

  1. सतत पंक्ति/स्तंभ का चयन: निर्धारित करें कि कौन सी पंक्तियां या स्तंभ सतत होंगी
  2. क्रम निर्धारण: सतत या विपरीत सतत व्यवस्था चुनें
  3. शेष स्थान भरना: शेष तत्वों को गैर-सतत स्थानों में रखें
  4. PIE लागू करना: दोहरी गणना से बचें

3. मुख्य प्रमेय प्रणाली

प्रमेय 2.1: PLSs की कुल संख्या ∣Ωn∣=(n2)!(n!)n|\Omega_n| = \frac{(n^2)!}{(n!)^n} है

प्रमेय 2.2: कम से कम एक सतत पंक्ति वाले PLSs की संख्या: ∣R∣=∑i=1n(−1)i+1⋅2i⋅n!(n2−in)!(n−i)!n+1i!|R| = \sum_{i=1}^n (-1)^{i+1} \cdot 2^i \cdot \frac{n!(n^2-in)!}{(n-i)!^{n+1}i!}

तकनीकी नवाचार बिंदु

1. स्तरीय गणना रणनीति

  • जटिल गणना समस्याओं को कई स्तरों में विभाजित करें
  • विभिन्न संख्या में सतत पंक्तियों और स्तंभों के प्रतिच्छेदन को व्यवस्थित रूप से संभालें
  • सीधी गणना के संयोजक विस्फोट से चतुराई से बचें

2. समरूपता का उपयोग

  • 90° घुमाव के माध्यम से पंक्तियों और स्तंभों के बीच द्विभाजन स्थापित करें
  • प्रतिबिंब जैसे रूपांतरणों के माध्यम से दोहरी गणना को सरल बनाएं
  • विशेष रूप से विषम और सम क्रम के अंतर को संभालें

3. स्पर्शोन्मुख विश्लेषण तकनीक

  • प्रमुख पद की पहचान करें: साबित करें कि पहला पद 2∣R∣2|R| पूरी अभिव्यक्ति पर हावी है
  • सटीक त्रुटि अनुमान: स्पर्शोन्मुख सन्निकटन के अभिसरण की गति दें

प्रायोगिक सेटअप

डेटा जनरेशन

  • यादृच्छिक PLSs जनरेशन: तत्वों के यादृच्छिक क्रमचय के माध्यम से समान रूप से वितरित n-क्रम PLSs उत्पन्न करें
  • स्केल सेटिंग: n∈{3,4,5} के लिए 10810^8 स्वतंत्र परीक्षण करें
  • सत्यापन रेंज: छोटे पैमाने पर सटीक सत्यापन, बड़े पैमाने पर स्पर्शोन्मुख व्यवहार परीक्षण

मूल्यांकन मेट्रिक्स

  • सिद्धांत बनाम प्रायोगिक संभाव्यता अंतर: मोंटे कार्लो अनुमान और सैद्धांतिक भविष्यवाणी के बीच विचलन को मापें
  • अभिसरण विश्लेषण: पुनरावृत्ति संख्या के साथ अभिसरण व्यवहार का अवलोकन करें
  • विश्वास अंतराल: max⁡{5p(1−p)N,p100}\max\{5\sqrt{\frac{p(1-p)}{N}}, \frac{p}{100}\} को त्रुटि सीमा के रूप में उपयोग करें

कार्यान्वयन विवरण

  • प्रोग्रामिंग भाषा: Python
  • यादृच्छिक संख्या जनरेशन: मानक पुस्तकालय के समान यादृच्छिक संख्या जनरेटर का उपयोग करें
  • समानांतरकरण: tqdm पुस्तकालय के माध्यम से प्रगति ट्रैकिंग लागू करें
  • मेमोरी अनुकूलन: सभी उत्पन्न मैट्रिक्स को संग्रहीत करने से बचने के लिए स्ट्रीम प्रोसेसिंग

प्रायोगिक परिणाम

मुख्य परिणाम

1. CPLS संभाव्यता सत्यापन

छोटे n मानों के लिए, सैद्धांतिक भविष्यवाणी और प्रायोगिक परिणाम अत्यधिक सामंजस्यपूर्ण हैं:

nसैद्धांतिक संभाव्यता P(ω∈Σₙ)प्रायोगिक त्रुटि रेंज
30.490476±0.0016
40.090006±0.0009
50.009760±0.0003

2. स्पर्शोन्मुख सन्निकटन सटीकता

स्पर्शोन्मुख सूत्र S(n)S(n) की सन्निकटन गुणवत्ता n के साथ तेजी से सुधरती है:

| n | |Σₙ|/S(n) | |---|----------| | 5 | 0.995 | | 6 | 0.9996 | | 7 | 0.99997 | | 8 | 0.999998 |

3. संभाव्यता द्रव्यमान फलन सत्यापन

सतत पंक्तियों और स्तंभों की संख्या के वितरण के लिए, सभी परीक्षण मामलों के प्रायोगिक मान सैद्धांतिक भविष्यवाणी के विश्वास अंतराल के भीतर आते हैं।

विलोपन प्रयोग

1. विभिन्न n मानों का व्यवहार अंतर

  • n=3: CPLSs अभी भी काफी अनुपात में हैं (~49%)
  • n=4: अनुपात में उल्लेखनीय गिरावट (~9%)
  • n≥5: तेजी से शून्य की ओर प्रवृत्त (<1%)

2. सतत पंक्ति बनाम सतत स्तंभ

90° घुमाव समरूपता के माध्यम से, पंक्तियों और स्तंभों के योगदान को पूरी तरह से समान सत्यापित करें।

3. प्रतिच्छेदन पद की महत्ता

साबित करें कि PIE गणना में, उच्च-क्रम प्रतिच्छेदन पद अंतिम परिणाम में नगण्य योगदान देते हैं।

प्रायोगिक निष्कर्ष

  1. तीव्र क्षय: CPLSs अनुपात की क्षय गति अपेक्षा से अधिक तेज है
  2. छोटे n विसंगति: n≤4 समय बड़े n से भिन्न व्यवहार प्रदर्शित करते हैं
  3. संख्यात्मक स्थिरता: यहां तक कि 10810^8 परीक्षणों के लिए, मोंटे कार्लो अनुमान उच्च सटीकता बनाए रखता है

संबंधित कार्य

लैटिन वर्ग सिद्धांत

  • Euler की 36 अधिकारी समस्या: ऐतिहासिक रूप से लैटिन वर्ग अनुसंधान को आगे बढ़ाने वाली शास्त्रीय समस्या
  • आधुनिक विकास: अर्ध-समूहों, प्रायोगिक डिजाइन, त्रुटि-सुधार कोड के साथ संबंध
  • गणना समस्याएं: परंपरागत लैटिन वर्गों की गणना अभी भी एक खुली समस्या है

छद्म-लैटिन वर्ग अनुसंधान

  • Norton का कार्य: छद्म-लैटिन वर्गों की अवधारणा को पहली बार पेश करना, लंबवत लैटिन वर्गों के समूहों के अध्ययन के लिए उपयोग किया जाता है
  • बीजगणितीय अनुप्रयोग: मैग्मा सिद्धांत के साथ संबंध

इस पेपर का अद्वितीय योगदान

  • सतत गुणों वाले छद्म-लैटिन वर्गों का पहली बार व्यवस्थित अध्ययन
  • सटीक गणना सिद्धांत की स्थापना
  • बीजगणितीय संरचना का नया दृष्टिकोण प्रदान करना

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. दुर्लभता प्रमेय: साबित करें कि CPLSs बड़े n में अत्यंत दुर्लभ हैं, अनुपात शून्य की ओर प्रवृत्त होने की गति O(4nn+1(n2−n+1)n)O(\frac{4n^{n+1}}{(n^2-n+1)^n}) है
  2. वितरण पूर्ण लक्षण वर्णन: सतत पंक्तियों और स्तंभों की संख्या का पूर्ण संभाव्यता द्रव्यमान फलन दें
  3. बीजगणितीय पत्राचार: CPLSs और निकट-एकात्मक मैग्मा के बीच सैद्धांतिक संबंध स्थापित करें

सीमाएं

  1. कम्प्यूटेशनल जटिलता: सटीक सूत्र जटिल संयोजक अभिव्यक्तियों को शामिल करते हैं, कम्प्यूटेशनल लागत n के साथ तेजी से बढ़ती है
  2. लागू रेंज: मुख्य परिणाम छोटे से मध्यम आकार के मामलों पर केंद्रित हैं
  3. व्यावहारिक अनुप्रयोग: वास्तविक अनुप्रयोग परिदृश्यों के साथ संबंध को अभी भी आगे की खोज की आवश्यकता है

भविष्य की दिशाएं

  1. सामान्यीकरण अनुसंधान: अन्य प्रकार की "संरचित" छद्म-लैटिन वर्गों पर विचार करें
  2. एल्गोरिदम अनुकूलन: अधिक कुशल गणना और जनरेशन एल्गोरिदम विकसित करें
  3. अनुप्रयोग अन्वेषण: क्रिप्टोग्राफी, कोडिंग सिद्धांत में संभावित अनुप्रयोग

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक कठोरता: गणितीय व्युत्पत्ति पूर्ण है, प्रमाण तर्क स्पष्ट है
  2. विधि नवाचार: निर्माणात्मक गणना और समावेशन-बहिष्करण सिद्धांत को चतुराई से संयोजित करें
  3. पर्याप्त प्रयोग: बड़े पैमाने पर मोंटे कार्लो सत्यापन परिणामों की विश्वसनीयता बढ़ाता है
  4. अंतः-विषय दृष्टिकोण: संयोजक समस्याओं को बीजगणितीय संरचनाओं से जोड़ता है

कमियां

  1. अनुप्रयोग प्रेरणा: हालांकि खेल-प्रेरित है, लेकिन व्यावहारिक अनुप्रयोग मूल्य पर्याप्त स्पष्ट नहीं है
  2. कम्प्यूटेशनल दक्षता: बड़े n मानों के लिए, सूत्र की गणना अव्यावहारिक हो जाती है
  3. सामान्यीकरण: परिणाम मुख्य रूप से विशिष्ट सातत्य गुणों के लिए हैं, अन्य संरचनात्मक गुणों में सामान्यीकरण की संभावना सीमित है

प्रभाव

  1. सैद्धांतिक योगदान: छद्म-लैटिन वर्ग सिद्धांत के लिए अनुसंधान की नई दिशा प्रदान करता है
  2. विधि मूल्य: गणना तकनीकें अन्य संयोजक संरचनाओं पर लागू हो सकती हैं
  3. पुनरुत्पादनीयता: पूर्ण कोड कार्यान्वयन प्रदान करता है, सत्यापन और विस्तार को सुविधाजनक बनाता है

लागू परिदृश्य

  1. संयोजक गणित अनुसंधान: लैटिन वर्ग प्रकारों के सैद्धांतिक आधार के रूप में
  2. संभाव्यता विश्लेषण: यादृच्छिक संयोजक संरचनाओं के गुणों का अध्ययन
  3. एल्गोरिदम डिजाइन: विशेष बाधाओं के तहत संयोजक अनुकूलन समस्याएं

संदर्भ

यह पेपर 13 महत्वपूर्ण संदर्भों का हवाला देता है, जो लैटिन वर्गों के ऐतिहासिक विकास, आधुनिक अनुप्रयोगों और संबंधित सिद्धांतों को शामिल करते हैं, विशेष रूप से ध्यान देने योग्य हैं:

  • McKay आदि (2007): छोटे लैटिन वर्गों, अर्ध-समूहों और वलयों का व्यवस्थित अध्ययन
  • van Lint & Wilson (1992): संयोजकता पाठ्यपुस्तक में लैटिन वर्ग अध्याय
  • Norton (1952): लंबवत पंक्ति लैटिन वर्गों के समूहों का अग्रणी कार्य

समग्र मूल्यांकन: यह संयोजक गणित क्षेत्र में सैद्धांतिक मूल्य वाला एक कठोर पेपर है। हालांकि अनुप्रयोग संभावनाओं को आगे की खोज की आवश्यकता है, लेकिन इसकी विधि नवाचार और सैद्धांतिक योगदान संबंधित अनुसंधान के लिए मूल्यवान आधार प्रदान करते हैं।