Almost Golomb Sequences

यहाँ बेनोइट क्लोइत्रे (Benoît Cloitre) के शोध पत्र "Almost Golomb Sequences" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण और प्रेरणा (Problem Statement and Motivation)

यह शोध पत्र स्व-संदर्भित पूर्णांक अनुक्रमों (self-referential integer sequences) के एक परिवार की जांच करता है जिन्हें "ऑलमोस्ट गोलोम्ब सीक्वेंस" (Almost Golomb Sequences) कहा जाता है। ये प्रसिद्ध गोलोम्ब अनुक्रम (Golomb's sequence) के परिमित-स्मृति (finite-memory) ट्रंकेशन (truncations) हैं।

• गोलोम्ब अनुक्रम ($G(n)$): इसे एक अद्वितीय गैर-घटते क्रम के रूप में परिभाषित किया गया है जहाँ $n$ ठीक $G(n)$ बार आता है। यह निम्नलिखित वैश्विक नियम (global rule) का पालन करता है:
  $$G\left(\sum_{k=1}^n G(k)\right) = n$$
  यह अनुक्रम सुचारू, उप-रैखिक वृद्धि (sublinear growth) प्रदर्शित करता है ($G(n) \sim C n^{\phi-1}$, जहाँ $\phi$ गोल्डन रेशियो है) और किसी भी $k \ge 2$ के लिए $k$-नियमित (k-regular) नहीं है।
• ट्रंकेशन (The Truncation): लेखक क्रम $r \ge 2$ के अनुक्रमों $(a_r(n))$ को अनंत संचयी योग (infinite cumulative sum) के स्थान पर $r$ सबसे हालिया पदों के एक स्लाइडिंग विंडो (sliding window) द्वारा प्रतिस्थापित करके पेश करते हैं:
  $$a_r\left(\sum_{j=0}^{r-1} a_r(n-j)\right) = n$$
  इस अनुक्रम का निर्माण लालची (greedy) तरीके से (न्यूनतम गैर-घटते विस्तार के रूप में) किया जाता है।
• मुख्य प्रश्न: स्व-संदर्भित नियम की "स्मृति" को अनंत से परिमित ($r$) तक सीमित करने से अनुक्रम की स्पर्शोन्मुखी व्यवहार (asymptotic behavior), नियमितता (regularity) और कॉम्बिनेटरियल संरचना में क्या परिवर्तन आता है?

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

यह शोध पत्र रचनात्मक कॉम्बिनेटरिक्स (constructive combinatorics), ऑटोमेटा थ्योरी (automata theory) और कंप्यूटर-सहायता प्राप्त प्रमाण सत्यापन (computer-assisted proof verification) के मिश्रण का उपयोग करता है।

• रन-लेंथ विश्लेषण (Run-Length Analysis): लेखक अनुक्रम में मानों के "रन" (लगातार आने वाले मान) का विश्लेषण करते हैं। वे स्थापित करते हैं कि क्रम $r$ के लिए, रन की लंबाई सीमित होती है, और रन के शुरुआती स्थान एक विशिष्ट पुनरावृत्ति (recurrence) का पालन करते हैं।
• डीनेस्टिंग (Denesting - Divide-and-Conquer): एक केंद्रीय तकनीक "डीनेस्टिंग" है, जहाँ निहित परिभाषा को $n$ के आधार-$r$ प्रतिनिधित्व (जैसे, $n$ के लिए $a(rn+i)$ के सूत्र) पर आधारित स्पष्ट पुनरावृत्ति संबंधों में बदल दिया जाता है।
• सुधार अनुक्रम (Correction Sequences): $r \ge 3$ के लिए, डीनेस्टिंग सूत्र शुद्ध रूप से रैखिक नहीं होते हैं; उन्हें बाइनरी सुधार अनुक्रमों (जिन्हें $\epsilon, \eta,$ आदि द्वारा दर्शाया गया है) की आवश्यकता होती है जो $r$-ऑटोमैटिक (r-automatic) होते हैं। ये अनुक्रम वृद्धि में होने वाले असतत दोलनों (discrete oscillations) की व्याख्या करते हैं।
• ऑटोमेटा थ्योरी (Automata Theory): शोध पत्र $r$-नियमितता को सिद्ध करने के लिए ऑलचे-शैलिट मानदंड (Allouche–Shallit criterion) का उपयोग करता है। यह सुधार अनुक्रमों को उत्पन्न करने के लिए 'डिटरमिनिस्टिक फाइनाइट ऑटोमेटा विद आउटपुट' (DFAO) का निर्माण करता है।
• कंप्यूटर सत्यापन (Computer Verification): $r=4$ और $r=5$ के लिए, लेखक व्युत्पन्न पुनरावृत्तियों और सुधार अनुक्रमों की ऑटोमैटिसिटी को प्रमाणित करने के लिए वॉलनट (Walnut) थ्योरम प्रूवर का उपयोग करते हैं, जो ह्यूरिस्टिक पैटर्न पहचान और कठोर प्रमाण के बीच के अंतर को पाटता है।

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

A. सार्वभौमिक $r$-नियमितता (Universal $r$-Regularity)

प्रमेय 2.9: प्रत्येक $r \ge 2$ के लिए, ऑलमोस्ट गोलोम्ब अनुक्रम $a_r(n)$, $r$-नियमित है।

• गोलोम्ब अनुक्रम (जो $k$-नियमित नहीं है) के विपरीत, परिमित-स्मृति प्रतिबंध इस अनुक्रम को ऑटोमैटिक/रेगुलर अनुक्रमों के क्षेत्र में ले आता है।
• अंतर अनुक्रम (difference sequence) $d(n) = a(n+1) - a(n)$ को $r$-ऑटोमैटिक दिखाया गया है।

B. स्पष्ट डीनेस्टिंग सूत्र (Explicit Denesting Formulas)

शोध पत्र छोटे $r$ के लिए स्पष्ट $r$-एडिक (r-adic) पुनरावृत्ति सूत्र प्रदान करता है:

• $r=2$ (Dyadic):
  $$a(2n) = a(n) + a(n+1) - 1$$
  $$a(2n+1) = a(n) + a(n+1)$$
  यह एक मैलोज़-प्रकार (Mallows-type) के नेस्टेड रिकरेंस की ओर ले जाता है: $a(n+1) = 1 + a(n+1 - a(a(n)+1) + a(a(n)-1))$.
• $r=3$ (Triadic): सूत्रों में एक सुधार अनुक्रम $\epsilon(n)$ शामिल है (यदि $n$ विशिष्ट अंतरालों में है तो 1, अन्यथा 0):
  $$a(3n) = a(n-2) + a(n-1) + a(n) + 1 + \epsilon(n-1)$$
  $$a(3n+1) = a(n-1) + a(n) + a(n+1)$$
  $$a(3n+2) = a(n) + a(n+1) + a(n+2) - 1 - \epsilon(n)$$
• $r=4, 5$: समान संरचनाएं मौजूद हैं लेकिन इनमें कई सुधार अनुक्रम शामिल हैं ($\epsilon_0, \dots, \epsilon_3$ $r=4$ के लिए और $(\epsilon, \eta)$ का जोड़ा $r=5$ के लिए)। इन्हें गणितीय रूप से पहचाना गया और Walnut द्वारा प्रमाणित किया गया।

C. $a(n)/n$ का अभिसरण न होना (Non-Convergence of $a(n)/n$)

प्रमेय 7.1, 7.5, 7.6, 7.8: सभी $r \ge 2$ के लिए, अनुपात $a(n)/n$ अभिसरित नहीं होता है।

• एक एकल सीमा के बजाय, अनुपात दो अलग-अलग परिमेय सीमा बिंदुओं (rational limit points) के बीच दोलन करता है।
• उदाहरण:
  • $r=2$: सीमाएँ $3/4$ और $2/3$ हैं।
  • $r=3$: सीमाएँ $8/15$ और $5/8$ हैं।
  • $r=4$: सीमाएँ $25/48$ और $10/21$ हैं।
• यह गोलोम्ब अनुक्रम के बिल्कुल विपरीत है, जहाँ $a(n)/n^{\phi-1}$ एक स्थिरांक (constant) पर अभिसरित होता है। यह दोलन स्लाइडिंग विंडो की असतत प्रकृति से प्रेरित है।

D. कॉम्बिनेटरियल व्याख्याएँ (Combinatorial Interpretations)

• $r=2$: किसी मान $m$ की बहुलता (multiplicity) $m-1$ के दूसरे सबसे महत्वपूर्ण बिट (second most significant bit) द्वारा निर्धारित होती है। अंतर अनुक्रम $d(n)$ एक बूलियन सेलुलर ऑटोमेटा नियम का पालन करता है: $d(2n)=1$ और $d(2n+1) = d(n) \land d(n+1)$।
• $r=3$: अंतर अनुक्रम ट्रायडिक ब्लॉक्स (triadic blocks) के भीतर एक पलिंड्रोमिक प्रतिस्थापन नियम (palindromic substitution rule) प्रदर्शित करता है, जहाँ ब्लॉक संरचना रन लेंथ $L_n$ द्वारा निर्धारित होती है।

E. "गोलोम्ब मेटा-स्ट्रक्चर" अनुमान (The "Golomb Meta-Structure" Conjecture)

शोध पत्र एक उल्लेखनीय संख्यात्मक अवलोकन प्रस्तुत करता है (अनुभाग 9):

• मान लीजिए $M(r)$ क्रम $r$ में अधिकतम बहुलता (किसी भी पूर्णांक के आने की अधिकतम संख्या) है।
• मान लीजिए $j_k$ वह न्यूनतम क्रम $r$ है कि $M(r) \ge k$।
• अनुमान (Conjecture): इन थ्रेशोल्ड्स (thresholds) के बीच का अंतर स्वयं गोलोम्ब अनुक्रम का पालन करता है:
  $$j_{k+1} - j_k = G(k)$$
  $$j_k = S(k-1) + 2$$
  जहाँ $S(k)$ गोलोम्ब अनुक्रम का आंशिक योग (partial sum) है।
• यह सुझाव देता है कि गोलोम्ब के नियम को ट्रंकेट करने से उत्पन्न अनुक्रम, इन ट्रंकेटेड अनुक्रमों के परिवार की जटिलता को नियंत्रित करने वाले नियम के रूप में "पुनः प्रकट" होता है। शोध पत्र इसे दो सीमावर्ती अनुमानों तक कम करता है: प्रिफिक्स कंजेक्चर (Prefix Conjecture) ($a_r(r) = G(r-1)$) और डोमिनेशन लेम्मा (Domination Lemma)।

4. महत्व (Significance)

1. एनालिटिक से ऑटोमैटिक की ओर संक्रमण: यह शोध पत्र स्व-संदर्भित अनुक्रमों में एक चरण संक्रमण (phase transition) को प्रदर्शित करता है। अनंत स्मृति (गोलोम्ब) से परिमित स्मृति (ऑलमोस्ट गोलोम्ब) की ओर जाने से अनुक्रम एनालिटिक पावर-लॉ ग्रोथ से रैखिक वृद्धि और ऑटोमैटिक दोलनों में बदल जाता है।
2. नियमित अनुक्रमों का नया वर्ग: यह स्पष्ट डिवाइड-एंड-कॉन्कर संरचनाओं वाले समृद्ध $r$-नियमित अनुक्रमों के एक परिवार को स्थापित करता है, जो स्लाइडिंग-विंडो पुनरावृत्तियों द्वारा परिभाषित अनुक्रमों के ज्ञात परिदृश्य का विस्तार करता है।
3. कॉम्बिनेटरियल गहराई: इन अनुक्रमों के लिए सेलुलर ऑटोमेटा नियमों और पलिंड्रोमिक प्रतिस्थापनों की खोज इन स्व-संदर्भित संरचनाओं के विश्लेषण के लिए नए उपकरण प्रदान करती है।
4. मेटा-स्ट्रक्चर घटना: यह अनुमान कि गोलोम्ब अनुक्रम अपने स्वयं के परिमित-स्मृति वेरिएंट के पदानुक्रम (hierarchy) को नियंत्रित करता है, एक गहरा और अप्रत्याशित संबंध है, जो यह सुझाव देता है कि स्व-संदर्भित प्रणालियों में एक गहरा अंतर्निहित बीजगणितीय ढांचा है।

5. खुले प्रश्न (Open Questions)

शोध पत्र कई खुले प्रश्नों के साथ समाप्त होता है, जिनमें शामिल हैं:

• $r \ge 3$ के लिए सेसेरो माध्य (Cesàro means) का व्यवहार।
• क्या पूर्ण बहुलता अनुक्रम $N_r(n)$ हमेशा $r$-ऑटोमैटिक होता है।
• जैसे-जैसे $r \to \infty$ जाता है, चरण संक्रमण (phase transition) की प्रकृति क्या है (क्या दोलन गायब होकर गोलोम्ब की सुचारू वृद्धि को पुनः प्राप्त कर लेते हैं?)।
• "गैप-$s$" (gap-$s$) अनुक्रमों के सामान्यीकरण जहाँ विंडो निरंतर (contiguous) नहीं है।

संक्षेप में, क्लोइत्रे का कार्य "ऑलमोस्ट गोलोम्ब" परिवार का कठोरता से वर्णन करता है, उनकी नियमितता को सिद्ध करता है, उनके दोलनी विकास (oscillatory growth) का विवरण देता है, और मूल गोलोम्ब अनुक्रम के साथ एक आश्चर्यजनक मेटा-स्ट्रक्चरल लिंक को उजागर करता है।