Beatty Sequences for a Quadratic Irrational: Decidability and Applications

यहाँ ल्यूक शेफ़र, जेफ़्री शालिट और स्टेफ़न ज़ोर्सिक के शोध पत्र "Beatty Sequences for a Quadratic Irrational: Decidability and Applications" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र असमरूप बीटी अनुक्रमों (inhomogeneous Beatty sequences) के निर्णयक्षमता (decidability) और संरचनात्मक गुणों को संबोधित करता है, जो $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ के रूप में होते हैं, जहाँ $\alpha$ और $\beta$ एक ही क्वाड्रेटिक फील्ड (quadratic field) (अर्थात, किसी वर्ग-मुक्त पूर्णांक $d$ के लिए $\mathbb{Q}(\sqrt{d})$) के सदस्य हैं।

विशेष रूप से, लेखक निम्नलिखित की जांच करते हैं:

• क्या ये अनुक्रम सिंक्रोनाइज्ड (synchronized) हैं (अर्थात, क्या एक परिमित ऑटोमेटा (finite automaton) $n$ और $y$ के निरूपणों को देखते हुए संबंध $y = \lfloor n\alpha + \beta \rfloor$ को सत्यापित कर सकता है)।
• क्या इन अनुक्रमों का प्रथम-क्रम तार्किक सिद्धांत (first-order logical theory) (योग के साथ) निर्णयक्षम (decidable) है।
• योगात्मक संख्या सिद्धांत (additive number theory), शब्दों पर संयोजन (combinatorics on words), और 'ऑन-लाइन एनसाइक्लोपीडिया ऑफ इंटीजर सीक्वेंसेस' (OEIS) में विशिष्ट अनुमानों (conjectures) से संबंधित खुले प्रश्नों में इस निर्णयक्षमता के अनुप्रयोग।

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

मुख्य कार्यप्रणाली ऑटोमेटा सिद्धांत (automata theory), संख्या सिद्धांत (number theory), और तर्कशास्त्र (logic) के संगम पर आधारित है, जिसे Walnut नामक सॉफ्टवेयर टूल के माध्यम से लागू किया गया है।

• ओस्ट्रोवस्की संख्या प्रणाली (Ostrowski Numeration Systems): लेखक एक द्विघाती अपरिमेय $\gamma$ पर आधारित पूर्णांकों के ओस्ट्रोवस्की निरूपण का उपयोग करते हैं। मानक बेस-$k$ निरूपणों के विपरीत, ओस्ट्रोवस्की निरूपण $\gamma$ के निरंतर भिन्न (continued fraction) के अभिसारियों (convergents) के हरों (denominators) का उपयोग करते हैं। द्विघाती अपरिमेयों के लिए, ये निरूपण यह सुनिश्चित करते हैं कि योग संबंध ($x+y=z$) को एक परिमित ऑटोमेटा द्वारा पहचाना जा सके।
• सिंक्रोनाइज्ड अनुक्रम (Synchronized Sequences): एक अनुक्रम "सिंक्रोनाइज्ड" तब होता है जब एक परिमित ऑटोमेटा जोड़ों के निरूपण $(n, y)$ को स्वीकार करता है यदि और केवल यदि $y = s_n$ हो। लेखक सिद्ध करते हैं कि द्विघाती अपरिमेयों के लिए विषम बीटी अनुक्रम सिंक्रोनाइज्ड होते हैं।
• प्रमेय 9 (मुख्य संरचनात्मक परिणाम): लेखक सिद्ध करते हैं कि यदि $0 < \gamma < 1$ एक द्विघाती अपरिमेय है जिसका निरंतर भिन्न पूर्णतः आवर्ती (purely periodic) है, और $\alpha, \beta \in \mathbb{Q}(\gamma)$ हैं, तो अनुक्रम $(\lfloor n\alpha + \beta \rfloor)$ एक $\gamma$-ओस्ट्रोवस्की सिंक्रोनाइज्ड अनुक्रम है।
  • मुख्य लेम्मा (Key Lemma): वे निरंतर भिन्नों के लिए एक मैट्रिक्स दृष्टिकोण का उपयोग करके यह दिखाने के लिए कि $\lfloor n\gamma \rfloor$ को ओस्ट्रोवस्की अंकों के रैखिक रूप में व्यक्त किया जा सकता है, जिससे एक सिंक्रोनाइज्ड ऑटोमेटा का निर्माण संभव होता है।
  • संवर्धन गुण (Closure Properties): वे इस तथ्य का लाभ उठाते हैं कि सिंक्रोनाइज्ड अनुक्रम रैखिक संयोजन, संयोजन (composition), और पूर्णांक गुणांकों वाले फ्लोर फंक्शन (floor functions) के अंतर्गत बंद (closed) होते हैं।
• Walnut के माध्यम से निर्णयक्षमता (Decidability via Walnut): चूंकि ये अनुक्रम सिंक्रोनाइज्ड हैं और ओस्ट्रोवस्की प्रणाली में योग गणनीय (computable) है, इसलिए इन अनुक्रमों का प्रथम-क्रम सिद्धांत निर्णयक्षम है। लेखक ऑटोमेटा का निर्माण करने और तार्किक सूत्रों का मूल्यांकन करने के लिए ऑटोमैटिक अनुक्रमों के लिए एक प्रमेय-सिद्धक (theorem-prover) Walnut का उपयोग करते हैं।
• विपरीत प्रमाण (Converse Proof - Theorem 28): वे सिद्ध करते हैं कि यदि कोई बीटी अनुक्रम सिंक्रोनाइज्ड है, तो $\alpha$ और $\beta$ को उस द्विघाती क्षेत्र (quadratic field) से संबंधित होना चाहिए जो अंतर्निहित ऑटोमेटा की संख्या प्रणाली द्वारा उत्पन्न होता है, जो एक आवश्यक और पर्याप्त स्थिति स्थापित करता है।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

अ. सैद्धांतिक आधार (Theoretical Foundations)

1. द्विघाती बीटी अनुक्रमों का सिंक्रोनाइज़ेशन: यह शोध पत्र स्थापित करता है कि किसी भी एक ही द्विघाती क्षेत्र में स्थित $\alpha, \beta$ के लिए, विषम बीटी अनुक्रम सिंक्रोनाइज्ड है। यह इन अनुक्रमों के योग के साथ प्रथम-क्रम सिद्धांत की निर्णयक्षमता के लिए एक नया, सरल प्रमाण प्रदान करता है।
2. विपरीत प्रमेय (Converse Theorem): लेखक सिद्ध करते हैं कि सिंक्रोनाइज़ेशन यह संकेत देता है कि पैरामीटर $\alpha$ और $\beta$ को ऑटोमेटा की संख्या प्रणाली से संबंधित द्विघाती क्षेत्र में होना चाहिए।
3. योगात्मक आधार की निर्णयक्षमता (Additive Basis Decidability): यह निर्णयक्षम है कि क्या एक सेट $\{\lfloor n\alpha + \beta \rfloor\}$ क्रम $r$ का एक योगात्मक आधार (additive basis) या अनंत योगात्मक आधार (asymptotic additive basis) बनाता है। ऐसा न्यूनतम क्रम प्रभावी रूप से गणनीय (effectively computable) है।

ब. अनुप्रयोग और खुले प्रश्नों का समाधान (Applications and Solving Open Problems)

लेखक अपने निर्णय प्रक्रिया को कई विशिष्ट समस्याओं को हल करने के लिए लागू करते हैं:

1. रेबल के अनुमान (Reble's Conjectures): वे फाइबोनैकी शब्द (Fibonacci word) में लंबाई 3 के मोनोक्रोमैटिक अंकगणितीय प्रगति (monochromatic arithmetic progressions) के अस्तित्व के संबंध में डॉन रेबल के तीन अनुमानों को सिद्ध करते हैं। वे उन पूर्णांकों के सेटों का लक्षण वर्णन करते हैं जिनके लिए ये प्रगति घटित होती हैं, जिसमें अनुक्रम A189377, A189378, और A189379 का उपयोग किया गया है।
2. ग्राहम का प्रश्न (Graham's Question): वे रोनाल्ड ग्राहम के "इवेंचुअल कवरिंग फैमिलीज" (ECF) से संबंधित एक विशेष प्रश्न को हल करते हैं। वे सिद्ध करते हैं कि $(\alpha_i, \beta_i)$ के युग्मों के लिए, यह निर्णयक्षम है कि क्या प्रत्येक पर्याप्त बड़े पूर्णांक ठीक एक सेट $S(\alpha_i, \beta_i)$ में आता है।
3. हिल्डेब्रांड आदि अनुक्रम (Hildebrand et al. Sequence): वे हिल्डेब्रांड, ली, ली और ज़ी द्वारा अध्ययन किए गए एक अनुक्रम $\tilde{c}(n)$ का स्पष्ट लक्षण वर्णन प्रदान करते हैं, यह सिद्ध करते हुए कि $0 \le c(n) - \tilde{c}(n) \le 2$ और अंतर के लिए ऑटोमेटा का निर्माण करते हैं।
4. किम्बरलिंग की स्वैपेज समस्या (Kimberling's Swappage Problem): वे 'लोअर ईवन स्वैपेज सीक्वेंस' (OEIS A141104) के संबंध में किम्बरलिंग के अनुमान का वैकल्पिक प्रमाण प्रदान करते हैं, यह दिखाते हुए कि यह $\phi^3$ के बीटी अनुक्रम से संबंधित है। वे चार संबंधित अनुक्रमों (A141105–A141107) का भी लक्षण वर्णन करते हैं।
5. योग-पूरक सेट (Sums-Complement Sets): वे सिद्ध करते हैं कि वे पूर्णांक जिन्हें एक द्विघाती बीटी अनुक्रम के दो तत्वों के अंतर के रूप में नहीं लिखा जा सकता, स्वयं एक ऑटोमैटिक अनुक्रम हैं। वे $\alpha = \sqrt{7}$ के मामले के लिए विशिष्ट ऑटोमेटा की गणना करते हैं।
6. $\sqrt{2}$ अनुक्रम: वे $\sqrt{2}$ से संबंधित सात OEIS अनुक्रमों (A097508, A001951, A003151, आदि सहित) के लिए अनुमानों को हल करते हैं और उनके बीच पहचान और संबंधों को सिद्ध करते हुए उनके लिए ऑटोमेटा प्रदान करते हैं।
7. आंशिक भाग (Fractional Parts): वे भिन्नात्मक भागों $\{\alpha x\} < \{\alpha y\}$ की तुलना को संभालने के लिए विधि का विस्तार करते हैं, उन्हें फ्लोर फंक्शन असमानताओं में बदलकर, जिससे यूनिट सर्कल पर आंशिक भागों के क्रम को निर्धारित करना संभव हो जाता है।

4. महत्व (Significance)

• एल्गोरिद्मिक संख्या सिद्धांत (Algorithmic Number Theory): यह शोध पत्र प्रदर्शित करता है कि योगात्मक संख्या सिद्धांत और शब्दों के संयोजन में गहरे प्रश्न, जो पहले कठिन या विशेष प्रमाणों की आवश्यकता वाले थे, उन्हें परिमित ऑटोमेटा और प्रथम-क्रम तर्क का उपयोग करके यांत्रिक रूप से हल किया जा सकता है।
• एकीकरण (Unification): यह बीटी अनुक्रमों, स्टर्मियन शब्दों (Sturmian words), और द्विघाती अपरिमेयों के अध्ययन को सिंक्रोनाइज्ड अनुक्रमों और ओस्ट्रोवस्की संख्या प्रणाली के ढांचे के तहत एकीकृत करता है।
• व्यावहारिक कार्यान्वयन (Practical Implementation): यह कार्य एक अनुसंधान उपकरण के रूप में Walnut की शक्ति को रेखांकित करता है। लेखक दिखाते हैं कि जटिल प्रमेयों को सेकंडों में सत्यापित किया जा सकता है, जिससे अमूर्त निर्णयक्षमता परिणामों को व्यावहारिक कम्प्यूटेशनल प्रमाणों में बदल दिया जाता है।
• खुले प्रश्नों का समाधान (Resolution of Open Problems): यह पत्र रेबल, किम्बरलिंग, इरविन और डेकिंग जैसे कई लंबे समय से चले आ रहे अनुमानों को हल करता है, जो वर्षों से खुले थे, और इन अनुक्रमों के लिए निश्चित उत्तर और स्पष्ट ऑटोमेटा प्रदान करता है।

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