Mahler equations for Zeckendorf numeration

यहाँ ओलिवियर कार्टन और रीम यासावी के शोध पत्र "Mahler Equations for Zeckendorf Numeration" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या का विवरण और संदर्भ

यह शोध पत्र मानक बेस-$k$ संख्यात्मक प्रणालियों से पिसोट (Pisot) संख्यात्मक प्रणालियों, विशेष रूप से ज़ेकेनडॉर्फ (Zeckendorf) संख्यात्मकता (फाइबोनैकी संख्याओं पर आधारित) तक, क्रिस्टोल के प्रमेय (Christol's Theorem) के सामान्यीकरण और नियमित अनुक्रमों (regular sequences) तथा माहलर समीकरणों (Mahler equations) के बीच संबंध को संबोधित करता है।

• पृष्ठभूमि:
  • क्रिस्टोल का प्रमेय (Christol's Theorem): यह स्थापित करता है कि एक परिमित क्षेत्र $\mathbb{F}_q$ पर एक अनुक्रम $q$-स्वचालित (base-$q$ विस्तारों को पढ़ने वाले एक परिमित ऑटोमेटा द्वारा उत्पन्न) है यदि और केवल यदि उसका जनरेटिंग फंक्शन $\mathbb{F}_q(x)$ पर बीजगणितीय (algebraic) है।
  • नियमितता (Regularity): एललौच और शल्लाट ने क्रमविनिमेय वलयों (commutative rings) पर नियमित अनुक्रमों को भारित ऑटोमेटा (weighted automata) द्वारा उत्पन्न करने के लिए ऑटोमैटिसिटी का सामान्यीकरण किया।
  • माहलर समीकरण (Mahler Equations): बेकर और ड्यूमास ने $k$-नियमित अनुक्रमों और $k$-माहलर समीकरणों ($\sum A_i(x) \Phi^i(y) = 0$ के रूप में कार्यात्मक समीकरण, जहाँ $\Phi(f(x)) = f(x^k)$) के बीच एक संबंध स्थापित किया। उन्होंने दिखाया कि आइसोलेटिंग (isolating) $k$-माहलर समीकरणों (जहाँ $y$ का गुणांक 1 है) के समाधान $k$-नियमित होते हैं।
• अंतराल (The Gap): जबकि ये परिणाम बेस-$k$ प्रणालियों में लागू होते हैं, वे ज़ेकेनडॉर्फ (फाइबोनैकी) जैसी अमूर्त संख्यात्मक प्रणालियों पर सीधे लागू नहीं होते हैं। बेस-$k$ में, एक अंक जोड़ना एक रैखिक ऑपरेशन ($n \mapsto kn + d$) के अनुरूप होता है। ज़ेकेनडॉर्फ संख्यात्मकता में, इसके अनुरूप ऑपरेशन गैर-रैखिक (non-linear) है, जो कार्टियर ऑपरेटरों (Cartier operators) से जुड़े मानक प्रमाण तकनीकों को बाधित करता है।
• उद्देश्य: लेखक ज़ेकेनडॉर्फ संख्यात्मकता ($Z$) के लिए एक "क्रिस्टोल-प्रकार" का प्रमेय स्थापित करने का लक्ष्य रखते हैं। विशेष रूप से, वे यह सिद्ध करने का प्रयास करते हैं कि आइसोलेटिंग $Z$-माहलर समीकरणों के समाधान $Z$-नियमित (भारित ऑटोमेटा द्वारा उत्पन्न) होते हैं और इसके विपरीत भी।

2. कार्यप्रणाली (Methodology)

लेखक ऑटोमेटा सिद्धांत, संख्या सिद्धांत (पिसोट संख्याओं के गुण), और औपचारिक शक्ति श्रृंखला (formal power series) विश्लेषण के संयोजन का उपयोग करते हैं।

A. ज़ेकेनडॉर्फ संख्यात्मकता और मानचित्र $\phi$

• ज़ेकेनडॉर्फ प्रणाली ($Z$): प्रत्येक पूर्णांक $n$ को गैर-आसन्न फाइबोनैकी संख्याओं ($F_i$) के योग के रूप में अद्वितीय रूप से दर्शाया जा सकता है। इसका अंक सेट $\{0, 1\}$ है।
• ऑपरेटर $\Phi$: बेस-$k$ में, ऑपरेटर $\Phi(f(x)) = f(x^k)$ है। ज़ेकेनडॉर्फ के लिए, लेखक एक फलन $\phi: \mathbb{N} \to \mathbb{N}$ पर आधारित एक रैखिक ऑपरेटर $\Phi: R[[x]] \to R[[x]]$ को परिभाषित करते हैं।
  • यदि $n = \sum b_i F_i$ है, तो $\phi(n) = \sum b_i F_{i+1}$।
  • $\Phi(\sum f_n x^n) = \sum f_n x^{\phi(n)}$।
• रैखिकता दोष (The Linearity Defect): महत्वपूर्ण बाधा यह है कि $\phi$ रैखिक नहीं है। जबकि $\phi(m+n) = \phi(m) + \phi(n)$ तब सत्य होता है जब $m$ और $n$ के ज़ेकेनडॉर्फ विस्तारों में सपोर्ट विलग (disjoint) हो, यह सामान्य रूप से विफल हो जाता है।
  • लेखक रैखिकता दोष $\delta(m, n) = \phi(m+n) - \phi(m) - \phi(n)$ को परिभाषित करते हैं।
  • वे सिद्ध करते हैं (लेम्मा 18) कि $\delta(m, n) \in \{-1, 0, 1\}$ है।

B. दोष (Defect) के लिए ऑटोमेटा निर्माण

• इस गैर-रैखिकता को संभालने के लिए, लेखक एक डिटरमिनिस्टिक ऑटोमेटा का निर्माण करते हैं जो $m$ और $n$ के ज़ेकेनडॉर्फ विस्तारों को देखते हुए दोष $\delta(m-n, n)$ की गणना करता है।
• यह इस तथ्य पर निर्भर करता है कि ज़ेकेनडॉर्फ संख्यात्मकता में शून्य को दर्शाने वाले शब्दों का सेट नियमित (regular) है (प्रमेय 19)।
• यह ऑटोमेटा भारित ऑटोमेटा ढांचे के भीतर गैर-रैखिक मानचित्र $\phi$ को सिम्युलेट करने के लिए आवश्यक "कैरी" (carry) या "दोष" (defect) की जानकारी को ट्रैक करता है।

C. सार्वभौमिक भारित ऑटोमेटा (Universal Weighted Automata)

• बेस-$k$ मामला: लेखक पहले बेस-$k$ मामले का पुनरावलोकन करते हैं (अनुभाग 2.4)। वे एक सार्वभौमिक भारित $k$-ऑटोमेटा का निर्माण करते हैं जो समीकरण के गुणांकों को ट्रांजिशन वेट्स के रूप में स्थापित करके किसी भी आइसोलेटिंग $k$-माहलर समीकरण के समाधान को उत्पन्न कर सकता है। यह कार्टियर ऑपरेटरों की आवश्यकता को समाप्त करता है।
• ज़ेकेनडॉर्फ मामला: वे इस निर्माण को ज़ेकेनडॉर्फ संख्यात्मकता तक विस्तारित करते हैं। नए ऑटोमेटा का स्टेट सेट निम्नलिखित से बना है:
  1. माहलर समीकरण के घात (degree) से संबंधित इंडेक्स।
  2. "ऊंचाई" (polynomials की degree) को ट्रैक करने वाले इंडेक्स।
  3. महत्वपूर्ण रूप से: दोष-गणना करने वाले ऑटोमेटा से एक स्टेट और रैखिकता दोष $\delta$ को ट्रैक करने के लिए अंकों का एक बफर।

3. मुख्य योगदान

1. $Z$-माहलर समीकरणों की परिभाषा: यह शोध पत्र $\phi$ द्वारा परिभाषित ऑपरेटर $\Phi$ का उपयोग करते हुए कार्यात्मक समीकरणों के रूप में $Z$-माहलर समीकरणों को पेश करता है।
2. दोष ऑटोमेटा का निर्माण: एक डिटरमिनिस्टिक ऑटोमेटा का अभिनव निर्माण जो रैखिकता दोष $\delta(m, n)$ की गणना करता है, यह सिद्ध करता है कि $\phi$ की गैर-रैखिकता "नियमित" (regular) है और गणनीय (computable) है।
3. $Z$-माहलर समीकरणों के लिए सार्वभौमिक ऑटोमेटा: लेखक एक सार्वभौमिक भारित ऑटोमेटा को परिभाषित करते हैं जो, एक आइसोलेटिंग $Z$-माहलर समीकरण और प्रारंभिक स्थिति को देखते हुए, अद्वितीय समाधान अनुक्रम उत्पन्न करता है।
4. स्टेट कॉम्प्लेक्सिटी बाउंड्स: वे समाधान उत्पन्न करने वाले ऑटोमेटा के लिए आवश्यक स्टेट्स के स्पष्ट बाउंड प्रदान करते हैं, जो दिखाते हैं कि यह घातांक $d$, ऊंचाई $h$, और गोल्डन रेशियो $\phi$ पर निर्भर करता है।

4. मुख्य परिणाम

प्रमेय 1 (मुख्य परिणाम): समाधान योग्यता नियमितता को दर्शाती है (Solvability implies Regularity)

मान लीजिए $R$ एक क्रमविनिमेय वलय (commutative ring) है और $P(x, y) = 0$ एक आइसोलेटिंग $Z$-माहलर समीकरण है (जहाँ $y$ का गुणांक 1 है)। यदि $f(x) = \sum f_n x^n$ एक समाधान है, तो अनुक्रम $(f_n)_{n \ge 0}$ $Z$-नियमित है।

• प्रमाण रणनीति: समाधान गुणांकों की गणना एक भारित ऑटोमेटा द्वारा की जाती है जिसे सार्वभौमिक ऑटोमेटा संरचना को दोष-ट्रैकिंग ऑटोमेटा के साथ जोड़कर बनाया गया है। $\phi$ की गैर-रैखिकता को दोष घटक (defect component) के माध्यम से प्रबंधित किया जाता है।

प्रमेय 29 (मात्रात्मक परिणाम)

घातांक $d$ और ऊंचाई $h$ वाले $Z$-माहलर समीकरण के लिए, एक डिटरमिनिस्टिक ऑटोमेटा जो समाधान उत्पन्न करता है, उसमें अधिकतम $O(d h^2)$ स्टेट्स (विशेष रूप से $45d(3h+1)h$ द्वारा सीमित) होंगे। इसकी तुलना बेस-$k$ मामले में $O(dh)$ बाउंड से की जाती है, जो रैखिकता दोष को ट्रैक करने की लागत को उजागर करती है।

कोरोलरी 34: नियमितता समाधान योग्यता को दर्शाती है (Regularity implies Solvability)

इसके विपरीत, कोई भी $Z$-नियमित श्रेणी (series) एक (संभवतः गैर-आइसोलेटिंग) $Z$-माहलर समीकरण का समाधान होती है। यह दिशा एक नियमित अनुक्रम के कर्नेल (kernel) के परिमित होने को दिखाकर और उच्च-क्रम पदों को हटाने के लिए रैखिक बीजगणित का उपयोग करके सिद्ध की जाती है।

काउंटर-एग्जांपल (गैर-आइसोलेटिंग मामला)

लेखक एक गैर-आइसोलेटिंग $Z$-माहलर समीकरण का उदाहरण प्रदान करते हैं (प्रपोजिशन 38): $(1-x)f(x) = \Phi(f(x))$।

• वे सिद्ध करते हैं कि इस समीकरण का समाधान ऐसे गुणांकों को दर्शाता है जो सुपर-पॉलीनोमियल रूप से बढ़ते हैं ($f_n \ge C n^k$ सभी $k$ के लिए)।
• लेम्मा 5 द्वारा, $Z$-नियमित अनुक्रमों के गुणांक पॉलीनोमियल रूप से सीमित होने चाहिए।
• निष्कर्ष: आइसोलेटिंग समीकरणों का प्रतिबंध आवश्यक है; गैर-आइसोलेटिंग समीकरण गैर-नियमित समाधान दे सकते हैं।

5. महत्व और निहितार्थ

• शास्त्रीय सिद्धांत का सामान्यीकरण: यह शोध पत्र आधार-$k$ से फाइबोनैकी आधार (ज़ेकेनडॉर्फ), जो कि एक मौलिक पिसोट संख्यात्मक प्रणाली है, तक ऑटोमेटा सिद्धांत और बीजगणितीय/कार्यात्मक समीकरणों के बीच गहरे संबंध को सफलतापूर्वक विस्तारित करता है।
• गैर-रैखिकता पर विजय: "रैखिकता दोष" को ट्रैक करने के लिए एक ऑटोमेटा के स्पष्ट निर्माण का उपयोग करने की कार्यप्रणाली, उन संख्यात्मक प्रणालियों को संभालने के लिए एक नई तकनीक प्रदान करती है जहाँ शिफ्ट ऑपरेशन एक सरल रैखिक मानचित्र नहीं है। यह अन्य पिसोट प्रणालियों पर भी लागू हो सकता है।
• नियमित अनुक्रमों के लिए नया निर्माण: "सार्वभौमिक ऑटोमेटा" दृष्टिकोण कार्टियर ऑपरेटरों पर निर्भर किए बिना (जो गैर-मानक संख्यात्मक प्रणालियों में कठिन हैं) माहलर समीकरणों से नियमित अनुक्रमों को उत्पन्न करने के लिए एक सीधा, रचनात्मक तरीका प्रदान करता है।
• खुले प्रश्न: लेखक नोट करते हैं कि जबकि उन्होंने दिखाया है कि आइसोलेटिंग समीकरण नियमित अनुक्रम देते हैं, इसका विलोम (यह चरित्रित करना कि कौन से नियमित अनुक्रम वास्तव में आइसोलेटिंग समीकरणों को संतुष्ट करते हैं) ज़ेकेनडॉर्फ संख्यात्मकता के लिए खुला है, जैसा कि बेस-$k$ के लिए परिमित क्षेत्रों में होता है। वे माहलर विधियों के समान, $Z$-माहलर फलनों के मानों की ट्रांसेंडेंस (transcendence) के बारे में भी प्रश्न उठाते हैं।

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