🔢 mathematics

On the Factor Complexity Associated with a Family of Multidimensional Continued Fraction Algorithms

यह शोध पत्र 216 ट्राइएंगल पार्टीशन (TRIP) मानचित्रों के एक परिवार द्वारा उत्पन्न $S$ -adic अनुक्रमों की कारक जटिलता (factor complexity) की जांच करता है, विशिष्ट मामलों के लिए $3n$ और $2n+1$ के ऊपरी आबद्ध (upper bounds) स्थापित करता है, "छिपे हुए $\mathbb{R}^2$ व्यवहार" (hidden $\mathbb{R}^2$ behavior) की अवधारणा प्रस्तुत करता है, और $3n$ द्वारा सीमित जटिलता वाले TRIP मानचित्रों का लगभग पूर्ण वर्गीकरण प्रदान करता है।

मूल लेखक: Thomas Garrity, Otto Vaughn Osterman

प्रकाशित 2026-07-22

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Thomas Garrity, Otto Vaughn Osterman

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

संख्याओं के ब्रह्मांड की कल्पना एक विशाल, अनंत पुस्तकालय के रूप में करें। इस पुस्तकालय में, कुछ पुस्तकें सरल, दोहराव वाले पैटर्न के साथ लिखी गई हैं, जबकि अन्य अराजक और अप्रत्याशित हैं। गणितज्ञ लंबे समय से "स्टर्मियन वर्ड्स" (Sturmian words) नामक एक विशेष वर्ग की पुस्तकों के प्रति आकर्षित रहे हैं। ये अक्षरों के ऐसे अनुक्रम हैं जो इतने जटिल हैं कि वे खुद को कभी दोहराते नहीं हैं, फिर भी इतने सरल हैं कि एक निश्चित लंबाई के अद्वितीय "वाक्यांशों" (या उपशब्दों) की संख्या एक पूर्णतः अनुमानित, सीधी रेखा के तरीके से बढ़ती है। इसे एक ऐसी रेसिपी की तरह समझें जहाँ हर बार जब आप एक नया घटक जोड़ते हैं, तो आपको केवल ठीक एक नया स्वाद संयोजन प्राप्त होता है। यह पूर्ण संतुलन दुर्लभ और सुंदर है, और यह अपरिमेय संख्याओं (irrational numbers) को उनके निरंतर भिन्नों (continued fractions) का उपयोग करके अनुमानित करने के तरीके से गहराई से जुड़ा हुआ है—जो अव्यवस्थित संख्याओं को व्यवस्थित, पूर्णांक-आधारित चरणों में तोड़ने की एक विधि है।

दशकों से, गणितज्ञों ने एक-आयामी दुनिया से उच्च-आयामी दुनिया में जाने के लिए इन सुंदर सरलताओं का विस्तार करने का प्रयास किया है, जिससे "बहु-आयामी निरंतर भिन्न" (multidimensional continued fractions) का निर्माण हुआ। यह एक ऐसे भूलभुलैया में नेविगेट करने जैसा है जो केवल एक रेखा नहीं है, बल्कि एक बहु-स्तरीय संरचना है। बड़ा सवाल यह है कि क्या ये उच्च-आयामी भूलभुलैया अभी भी उन सरल, अनुमानित अनुक्रमों को उत्पन्न करती हैं, या वे अराजकता में बदल जाती हैं? यह शोध पत्र 216 अलग-अलग गणितीय मानचित्रों (maps) के एक विशाल परिवार की जांच करता है जो इन उच्च-आयामी भूलभुलैयाओं का पता लगाने के लिए डिज़ाइन किए गए हैं। लेखक मूल रूप से मानचित्रकारों (cartographers) की भूमिका निभा रहे हैं, जो यह मानचित्रण करने की कोशिश कर रहे हैं कि इनमें से कौन से 216 पथ सरल, व्यवस्थित अनुक्रमों की ओर ले जाते हैं और कौन से पथ जंगली, जटिल अनुक्रमों की ओर ले जाते हैं। वे उस "स्वीट स्पॉट" (sweet spot) की तलाश कर रहे हैं जहाँ जटिलता कम हो, जिसका अर्थ है कि अद्वितीय वाक्यांशों की संख्या धीरे-धीरे और अनुमानित रूप से बढ़ती है, न कि अनियंत्रित रूप से विस्फोट करती है।

इस शोध पत्र के लेखक, थॉमस गैरीटी और ओटो वॉन ऑस्टर्मन, इन मानचित्रों के एक विशिष्ट परिवार की जांच करने के लिए आगे बढ़े जिसे "ट्रायंगल पार्टीशन मैप्स" (Triangle Partition maps या TRIP maps) कहा जाता है। वे जानना चाहते थे कि प्रत्येक 216 संभावित मानचित्रों के लिए, उनके द्वारा उत्पन्न अनुक्रमों की जटिलता कितनी है? विशेष रूप से, वे उन मानचित्रों की तलाश में थे जो जटिलता को कम रखते हैं, आदर्श रूप से $3n$ (जहाँ $n$ वाक्यांश की लंबाई है) जैसे एक सरल सूत्र द्वारा सीमित रखते हैं।

उनकी मुख्य खोज "ट्रायंगल मैप" (या $(e, e, e)$ -TRIP मैप) के रूप में ज्ञात सबसे प्रसिद्ध मानचित्र के संबंध में एक विस्तृत प्रमाण है। उन्होंने सिद्ध किया कि इस मानचित्र द्वारा उत्पन्न अनुक्रम वास्तव में सुव्यवस्थित हैं। इन अनुक्रमों की जटिलता $2n + 1$ और $3n$ के बीच रहने की गारंटी है। सरल शब्दों में, इसका अर्थ है कि अनुक्रम दिलचस्प और गैर-दोहराव वाले होने के लिए पर्याप्त जटिल हैं, लेकिन इतने जटिल नहीं हैं कि वे अराजक हो जाएं। वे एक स्थिर, प्रबंधनीय गति से बढ़ते हैं।

हालाँकि, यह शोध पत्र एक फ़िल्टर के रूप में भी कार्य करता है, जो कई अन्य संभावनाओं को खारिज करता है। कंप्यूटर प्रयोगों के माध्यम से, लेखकों ने पाया कि अन्य 215 मानचित्रों में से कई के लिए, जटिलता विस्फोट की तरह बढ़ती है। उन्होंने विशिष्ट उदाहरणों की पहचान की जहाँ अद्वितीय वाक्यांशों की संख्या $3n$ से बहुत अधिक तेजी से बढ़ती है, जिससे प्रभावी रूप से यह सिद्ध होता है कि वे मानचित्र उन सरल, व्यवस्थित अनुक्रमों को उत्पन्न नहीं करते जिनकी गणितज्ञों को उम्मीद थी। उन्होंने "अपभ्रष्ट" (degenerate) मानचित्रों के एक विशेष समूह की भी पहचान की जो वास्तव में छद्म रूप में द्वि-आयामी हैं; ये सबसे सरल संभव अनुक्रम उत्पन्न करते हैं, जिन्हें स्टर्मियन वर्ड्स कहा जाता है, जो निम्न जटिलता के लिए स्वर्ण मानक हैं।

एक अत्यंत दिलचस्प खोज शामिल है जिसे लेखक "हिडन $R^2$ बिहेवियर" (hidden $R^2$ behavior) कहते हैं। उन्होंने पाया कि कुछ मानचित्रों के लिए, जैसे कि $(e, 13, e)$ मैप, सिस्टम मानचित्र के कुछ हिस्सों पर एक सरल द्वि-आयामी भूलभुलैया की तरह व्यवहार करता है, लेकिन अन्य स्थानों पर अलग व्यवहार करता है। यह "छिपी हुई" सरलता उन्हें यह सिद्ध करने की अनुमति देती है कि इन विशिष्ट मानचित्रों के लिए जटिलता भी बहुत कम है, जो $2n + 1$ या इसी तरह की एक सख्त सीमा द्वारा बंधी है।

अंत में, यह शोध पत्र एक बड़ा रहस्य अनसुलझा छोड़ देता है। एक शेष मानचित्र है, $(e, 23, e)$ -TRIP मैप, जिसके बारे में लेखक दृढ़ता से संदेह करते हैं कि इसमें भी कम जटिलता (बध $3n$ द्वारा) है। उन्होंने कंप्यूटर सिमुलेशन चलाए जो इस विचार का समर्थन करते हैं, जिससे पता चलता है कि उनके अनुक्रम बिल्कुल अनुमानित व्यवहार करते हैं, लेकिन वे अभी तक इसके लिए एक पूर्ण गणितीय प्रमाण नहीं लिख पाए हैं। वे भविष्य में इसे सिद्ध करने के तरीके के लिए एक रोडमैप भी प्रदान करते हैं, लेकिन फिलहाल, यह एक पुष्ट तथ्य के बजाय एक बहुत ही मजबूत अनुमान बना हुआ है।

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

तकनीकी सारांश: ट्राइएंगल पार्टिशन (TRIP) मानचित्रों के एक परिवार से जुड़े कारक जटिलता (Factor Complexity) पर

समस्या विवरण
यह शोध पत्र ट्राइएंगल पार्टिशन (TRIP) मानचित्रों के रूप में ज्ञात बहु-आयामी निरंतर भिन्न (multidimensional continued fraction) एल्गोरिदम के एक विशिष्ट परिवार द्वारा उत्पन्न अनंत शब्दों (infinite words) की कारक जटिलता (distinct subwords की संख्या $n$ के लिए) की जांच करता है। जबकि शास्त्रीय निरंतर भिन्न स्टर्मियन शब्दों (Sturmian words) के अनुरूप होते हैं जिनकी कारक जटिलता $n+1$ होती है, उच्च आयामों (बहु-आयामी निरंतर भिन्नों) के सामान्यीकरण अक्सर उच्च जटिलता वाले अनुक्रम उत्पन्न करते हैं। लेखक इन 216 विशिष्ट TRIP मानचित्रों के लिए जटिलता सीमाओं को निर्धारित करने का लक्ष्य रखते हैं, जो $S_3 \times S_3 \times S_3$ में क्रमपरिवर्तनों (permutations) के त्रिक (triples) द्वारा अनुक्रमित हैं। विशेष रूप से, यह कार्य यह पहचानने का प्रयास करता है कि कौन से मानचित्र निम्न रैखिक जटिलता (low linear complexity) उत्पन्न करते हैं, विशेष रूप से जो $3n$ या $2n+1$ द्वारा सीमित हैं।

कार्यप्रणाली
लेखक गतिशील प्रणालियों के सिद्धांत (dynamical systems theory) और शब्दों के संयोजन विज्ञान (combinatorics on words) के संयोजन का उपयोग करते हैं।

ढांचा परिभाषा: वे TRIP मानचित्रों को एक 3-आयामी शंकु (3-dimensional cone) पर एक गतिशील प्रणाली के रूप में परिभाषित करते हैं (जो एक त्रिभुज $\Delta$ पर प्रक्षेपित होता है) और प्रत्येक मानचित्र को वर्णमाला $\{1, 2, 3\}$ पर कार्य करने वाले प्रतिस्थापन युग्मों ( $S_0, S_1$ ) के साथ जोड़ते हैं। अनंत शब्द (S-adic sequences) TRIP मानचित्र के तहत एक बिंदु की कक्षा (orbit) के आधार पर इन प्रतिस्थापनों को पुनरावृत्त करके उत्पन्न होते हैं।
जटिलता विश्लेषण उपकरण: जटिलता को सीमित करने के लिए प्राथमिक उपकरण 'बिसिस्पेशल कारकों' (bispecial factors) का विश्लेषण है (ऐसे शब्द जिन्हें दोनों ओर से कई तरीकों से बढ़ाया जा सकता है)। सूत्र $p(n+1) - p(n) = \sum (|E^-(w)| - 1)$ का उपयोग करते हुए, लेखक बिसिस्पेशल कारकों की बहुलता $m(w)$ के माध्यम से जटिलता के विकास को जोड़ते हैं।
आगमनात्मक निर्माण (Inductive Construction): केंद्रीय मामले $(e, e, e)$ मानचित्र (ट्राइएंगल मानचित्र) के लिए, लेखक बिसिस्पेशल शब्दों के "पूर्ववृत्तों" (antecedents) और "विस्तारित छवियों" (extended images) की एक श्रृंखला का निर्माण करते हैं। वे एक आधार मामले तक पहुँचने से पहले कितनी बार वि-प्रतिस्थापन (de-substitution) किया जा सकता है, इसके आधार पर बिसिस्पेशल शब्दों के लिए एक "आयु" (age) को परिभाषित करते हैं। प्रतिस्थापन प्रक्रिया के माध्यम से इन शब्दों के विस्तार सेटों (बाएं और दाएं) को कठोरता से ट्रैक करके, वे सिद्ध करते हैं कि लंबाई $\le n$ वाले गैर-तटस्थ बिसिस्पेशल कारकों के लिए बहुलता का योग सीमित है, जिससे एक रैखिक जटिलता सीमा प्राप्त होती है।
तुल्यता न्यूनीकरण (Equivalence Reduction): 216 मानचित्रों को प्रबंधित करने के लिए, लेखक "संयुग्मन" (conjugacy - वर्णमाला का पुन: लेबलिंग) और "ट्विनिंग" (twinning - प्रतिस्थापनों और फरे मैट्रिसेस के क्रम को उलटना) का उपयोग करके समस्या को 21 विशिष्ट तुल्यता वर्गों में कम करते हैं।
छिपा हुआ R2 व्यवहार (Hidden R2 Behavior): विशिष्ट मानचित्रों के लिए, लेखक एक ऐसी गतिशील घटना की पहचान करते हैं जहाँ प्रणाली एक सकारात्मक माप (positive measure) के उपसमुच्चय पर 2-आयामी निरंतर भिन्न की तरह व्यवहार करती है, जिससे कम जटिलता विश्लेषण की अनुमति मिलती है।

मुख्य योगदान और परिणाम

मुख्य प्रमेय (ट्राइएंगल मानचित्र): यह शोध पत्र सिद्ध करता है कि $(e, e, e)$ TRIP मानचित्र (ट्राइएंगल मानचित्र) के संगत S-adic अनुक्रमों की कारक जटिलता $p(n)$ इस प्रकार है कि $2n + 1 \le p(n) \le 3n$ । यह इस विशिष्ट मानचित्र के लिए एक सटीक रैखिक ऊपरी सीमा स्थापित करता है, जो पहले स्वतंत्र गतिशील महत्व का विषय था लेकिन जिसमें सटीक जटिलता सीमा का अभाव था।
द्वितीयक प्रमेय: लेखक $(e, 13, e)$ TRIP मानचित्र के लिए $2n + 1$ की ऊपरी सीमा सिद्ध करते हैं। यह परिणाम "छिपे हुए R2 व्यवहार" की खोज से जुड़ा है, जहाँ मानचित्र की गतिशीलता कुछ अपरिवर्तनीय उपसमुच्चयों पर 2-आयामी प्रणाली में बदल जाती है, जिसके परिणामस्वरूप स्टर्मियन-समान जटिलता गुण प्राप्त होते हैं।
TRIP मानचित्रों का वर्गीकरण: कम्प्यूटेशनल प्रयोगों और सैद्धांतिक प्रमाणों के माध्यम से, लेखक TRIP मानचित्रों के 21 तुल्यता वर्गों को वर्गीकृत करते हैं:
- निम्न जटिलता ( $\le 3n$ ): $(e, e, e)$ मानचित्र और इसके संयुग्मों/ट्विन्स को $\le 3n$ की जटिलता होने के लिए सिद्ध किया गया है। $(e, 23, 23)$ मानचित्र (कैसिएन मानचित्र) और इसके संयुग्मों को ठीक $2n + 1$ की जटिलता के लिए सिद्ध किया गया है।
- अपभ्रंश मामले (Degenerate Cases): $(e, 12, e)$ जैसे मानचित्रों को मूल रूप से 2-आयामी दिखाया गया है, जो $n \neq 1$ के लिए $n+1$ (स्टर्मियन) जटिलता प्रदान करते हैं।
- उच्च जटिलता: 14 विशिष्ट तुल्यता वर्गों के लिए, लेखक ऐसे प्रति-उदाहरण प्रदान करते हैं जो दर्शाते हैं कि कुछ $n$ के लिए जटिलता $3n$ से अधिक हो जाती है।
- अनुमान (Conjecture): एक शेष मामला, $(e, 23, e)$ मानचित्र और इसके संयुग्म/ट्विन्स, के लिए $3n$ का ऊपरी सीमा होने का अनुमान लगाया गया है। कम्प्यूटेशनल साक्ष्य इसका समर्थन करते हैं, लेकिन औपचारिक प्रमाण प्रदान नहीं किया गया है।

महत्व
यह शोध पत्र बहु-आयामी निरंतर भिन्न एल्गोरिदम के एक विशाल परिवार की कारक जटिलता को समझने के लिए एक व्यापक ढांचा प्रदान करता है। यह सिद्ध करके कि ट्राइएंगल मानचित्र $(e, e, e)$ की जटिलता $3n$ तक सीमित रैखिक है, लेखक यह प्रदर्शित करते हैं कि सभी बहु-आयामी सामान्यीकरण अनिवार्य रूप से सुपरलीनियर (superlinear) जटिलता की ओर नहीं ले जाते हैं। "छिपे हुए R2 व्यवहार" की पहचान एक नया गतिशील दृष्टिकोण प्रदान करती है कि कैसे उच्च-आयामी प्रणालियाँ विशिष्ट अपरिवर्तनीय सेटों पर निम्न-आयामी जटिलता गुण प्रदर्शित कर सकती हैं। यह कार्य प्रभावी रूप से TRIP मानचित्रों के परिदृश्य को संकुचित करता है, निम्न जटिलता वाले मानचित्रों को उच्च जटिलता वाले मानचित्रों से अलग करता है, और शेष खुले मामलों के लिए भविष्य के अनुसंधान के लिए एक स्पष्ट मार्ग निर्धारित करता है।

इसी तरह के और पेपर