On a perturbed Hofstadter $Q$-recursion

यहाँ बेनोइट क्लोइत्रे (Benoît Cloitre) के शोध पत्र "On a perturbed Hofstadter Q-recursion" का विस्तृत तकनीकी सारांश दिया गया है।

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

होफस्टैडर Q-अनुक्रम ($Q(n)$) एक प्रसिद्ध नेस्टेड पुनरावृत्ति (nested recurrence) है जिसे $Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2))$ के रूप में परिभाषित किया गया है, जहाँ $Q(1)=Q(2)=1$ है। दशकों के अध्ययन के बावजूद, मौलिक प्रश्न अनसुलझे हैं:

• क्या $Q(n)$ सभी $n$ के लिए सुपरिभाषित (well-defined) है?
• क्या अनुपात $Q(n)/n$ अभिसरित (converge) होता है?
• यह अनुक्रम अराजक व्यवहार (chaotic behavior) प्रदर्शित करता है, जहाँ $Q(n)/n$ बिना किसी सिद्ध सीमा के $1/2$ के आसपास उतार-चढ़ाव करता रहता है।

2026 में, मंतोवनली (Mantovanelli) ने एक पैरिटी-परटर्बड वेरिएंट (parity-perturbed variant) पेश किया, जिसे $\tilde{Q}(n)$ द्वारा दर्शाया गया है, जो इस प्रकार परिभाषित है:
$$\tilde{Q}(n) = \tilde{Q}(n-\tilde{Q}(n-1)) + \tilde{Q}(n-\tilde{Q}(n-2)) + (-1)^n$$
जहाँ $\tilde{Q}(1)=\tilde{Q}(2)=1$ है। संख्यात्मक प्रयोगों ने सुझाव दिया कि यह विचलन (perturbation) अराजकता को नियमित करता है, जिससे सटीक डियाडिक स्व-समानता (exact dyadic self-similarity) और $1/2$ की ओर अभिसरण उत्पन्न होता है।

लक्ष्य: यह सिद्ध करना कि $\tilde{Q}(n)$ सभी $n$ के लिए सुपरिभाषित है, $\tilde{Q}(n)/n$ के $1/2$ की ओर अभिसरण की दर स्थापित करना, और उतार-चढ़ाव के सटीक स्पर्शोन्मुखी आवरण (asymptotic envelope) की पहचान करना।

---

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

यह शोध पत्र संयोजन विज्ञान (combinatorics), ऑटोमेटा सिद्धांत (automata theory), और विश्लेषणात्मक संयोजन विज्ञान (analytic combinatorics) के बहुआयामी दृष्टिकोणों का उपयोग करता है।

A. पैरिटी स्प्लिट और उप-अनुक्रम (Parity Split and Subsequences)

चूँकि $\tilde{Q}(n)$ हमेशा विषम (odd) होता है, लेखक $R(n) = (\tilde{Q}(n)+1)/2$ को परिभाषित करते हैं। इंडेक्स को पैरिटी (parity) के आधार पर अलग करके, पुनरावृत्ति दो युग्मित अनुक्रमों $A(m)$ और $B(m)$ में विभाजित हो जाती है:

• $A(m) = R(2m-1)$
• $B(m) = R(2m)$
  ये "रीडिंग हेड्स" (reading heads) के साथ सटीक पुनरावृत्तियों का पालन करते हैं जो पिछले मानों को देखते हैं। अंतर $\delta(m) = B(m) - A(m)$ और योग $\sigma(m) = A(m) + B(m) - m$ का विश्लेषण किया जाता है।

B. आर्च अपघटन (Arch Decomposition)

अनुक्रम $\delta(m)$ धनात्मक और ऋणात्मक मानों के बीच दोलन करता है, जिससे आर्च (arches) बनते हैं (वे अंतराल जहाँ $\delta \ge 0$ या $\delta \le 0$ हो)।

• धनात्मक आर्च (Positive Arches): अंतराल $[u_r, v_r]$ जहाँ $\delta(m) \ge 0$ है।
• ऋणात्मक आर्च (Negative Arches): अंतराल $[v_r, u_{r+1}]$ जहाँ $\delta(m) \le 0$ है।
  इन आर्चों की संरचना $a_r$ और $b_r$ मापदंडों द्वारा नियंत्रित होती है, जो घातीय रूप से बढ़ते हैं ($a_r \sim \frac{2}{3}4^r$)।

C. इंटरलीव ट्रांसड्यूसर (The Interleave Transducer)

एक प्रमुख संरचनात्मक खोज यह है कि इस पुनरावृत्ति को एक नियत द्वि-टेप इंटरलीविंग मशीन (deterministic two-tape interleaving machine) के रूप में मॉडल किया जा सकता है।

• स्टेप वर्ड्स (Step Words): प्रत्येक आर्च पर वृद्धियाँ (increments) $\Delta A$ और $\Delta B$ बाइनरी वर्ड्स $P_r$ (धनात्मक आर्च) और $N_r$ (ऋणात्मक आर्च) बनाते हैं।
• इंटरलीव ऑपरेटर (Interleave Operator): स्तर $r+1$ का स्टेप वर्ड, स्तर $r$ के संशोधित वर्ड्स को इंटरलीव करके बनाया जाता है। विशेष रूप से, $P_{r+1} = \text{Interleave}(S_0, S_1, 0)$, जहाँ $S_0$ और $S_1$, $N_r$ से व्युत्पन्न हैं।
• गुणधर्म: यह ऑपरेटर एंटी-पलिंड्रोमिकिटी (anti-palindromicity) और संतुलन (balance - 0s और 1s की समान संख्या) को संरक्षित करता है, जिससे अनुक्रम सुव्यवस्थित बना रहता है।

D. दो विश्लेषणात्मक मार्ग (Two Analytical Routes)

अभिसरण स्थापित करने के लिए प्रमाण दो अलग-अलग मार्गों का उपयोग करता है:

1. मार्ग B (आवृत्ति - बिना शर्त/Unconditional): डियाडिक ब्लॉक्स पर $A(m)$ और $B(m)$ के विज़िट मल्टीप्लिसिटी (visit multiplicities) की आवृत्ति का विश्लेषण करता है। यह मार्ग मानों के वितरण पर निर्भर करता है और अभिसरण दर का एक बिना शर्त प्रमाण देता है।
2. मार्ग A (आयाम - सशर्त/Conditional): आर्च की ऊँचाई ($V^+(r)$) का विश्लेषण करता है। यह मार्ग स्टेप वर्ड्स में 1 के रन-लेंथ (run-lengths) के लिए एक "स्टेयरकेस पुनरावृत्ति" पर निर्भर करता है। सटीक एनवेलप स्थिरांक (envelope constant) प्राप्त करने के लिए इसे दो अप्रामाणित अवलोकनों (जो $r=6$ तक संगणना द्वारा सत्यापित हैं) की आवश्यकता होती है।

---

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

A. सुपरिभाषितता और सीमाएँ (Well-Definedness and Bounds)

• प्रमेय 4.7 और 4.8: सिद्ध किया गया कि $\tilde{Q}(n)$, $n \ge 1$ के लिए सुपरिभाषित है और $1 \le \tilde{Q}(n) \le n$ को संतुष्ट करता है।
• 1-लिप्सचिट्ज़ गुण (1-Lipschitz Property): $\Delta A(m)$ और $\Delta B(m)$ की वृद्धियाँ सख्ती से $\{0, 1\}$ में हैं, जो यह सुनिश्चित करती है कि अनुक्रम एकदिष्ट (monotonically) और धीमी गति से बढ़ते हैं।

B. अभिसरण दर (अनकंडीशनल)

• प्रमेय 1.1(a): अनुपात $1/2$ की ओर $O(1/\sqrt{\log n})$ के त्रुटि पद के साथ अभिसरित होता है:
  $$\left| \frac{\tilde{Q}(n)}{n} - \frac{1}{2} \right| = O\left(\frac{1}{\sqrt{\log n}}\right)$$
• तंत्र: यह मानों के विज़िट काउंट (frequency counts) से प्राप्त होता है। डियाडिक ब्लॉक्स पर $A$ और $B$ विज़िट्स के बीच असंतुलन केंद्रीय द्विपद गुणांकों (central binomial coefficients) $\binom{2k+2}{k+1}$ द्वारा नियंत्रित होता है, जिनका योग $O(4^k/\sqrt{k})$ होता है।

C. सटीक एनवेलप स्थिरांक (सशर्त)

• प्रमेय 1.1(b): दो अवलोकनों ("रिकॉर्ड क्लेम" और "नॉन-सिंगलटन रन्स की पहचान") के सशर्त आधार पर, उतार-चढ़ाव का स्पर्शोन्मुखी व्यवहार सटीक रूप से निर्धारित है:
  $$\limsup_{n \to \infty} \left| \frac{\tilde{Q}(n)}{n} - \frac{1}{2} \right| \sqrt{\log_2 n} = \frac{1}{3\sqrt{2\pi}}$$
• आयाम वृद्धियाँ (Amplitude Increments): आर्च की ऊँचाई वृद्धियाँ $W_r$, कैटलन-संबंधित संख्याओं द्वारा दर्शाई गई हैं:
  $$W_r = \binom{2r+1}{r}$$
  यह स्पर्शोन्मुखी विकास $V^+(r) \sim \frac{8}{3\sqrt{\pi}} \frac{4^r}{\sqrt{r}}$ की ओर ले जाता है।

D. कैटलन संयोजन विज्ञान से संबंध (Connection to Catalan Combinatorics)

यह शोध पत्र हॉफस्टैडर-प्रकार की पुनरावृत्ति और कैटलन संख्याओं के बीच एक गहरा संबंध पहचानता है।

• सिस्टम को नियंत्रित करने वाला "कर्नेल" समीकरण $1 - z + xz^2 = 0$ है, जो कैटलन जनरेटिंग फंक्शन का परिभाषित समीकरण है।
• विश्लेषण एक द्वैत (duality) प्रकट करता: आवृत्ति मार्ग केंद्रीय द्विपद गुणांकों (बाइनरी ट्री से संबंधित) का उपयोग करता है, जबकि आयाम मार्ग कैटलन-प्रकार के गुणांकों (कैटलन फॉरेस्ट से संबंधित) का उपयोग करता है।

---

4. महत्व और निहितार्थ (Significance and Implications)

1. एक मेटा-फाइबोनाची समस्या का समाधान: यह एक अराजक मूल (chaotic parent) वाले हॉफस्टैडर-प्रकार के अनुक्रम के लिए सुपरिभाषितता और अभिसरण का पहला कठोर प्रमाण है। यह दर्शाता है कि एक सरल पैरिटी परटर्बेशन ($(-1)^n$) एक अराजक प्रणाली को सटीक स्व-समानता वाले सिस्टम में बदल सकता है।
2. मूल Q-अनुक्रम के लिए प्रॉक्सी: संख्यात्मक प्रयोग बताते हैं कि मूल अराजक $Q(n)$ और नियमित $\tilde{Q}(n)$ के बीच का अंतर छोटा ($O(n/\sqrt{\log n})$) है। यदि यह सिद्ध हो जाता है, तो इसका अर्थ होगा कि मूल $Q(n)$ भी $1/2$ की ओर अभिसरित होता है और सुपरिभाषित है, जो दशकों पुराने खुले प्रश्न को हल कर देगा।
3. पुनरावृत्तियों में विश्लेषणात्मक संयोजन विज्ञान: यह शोध पत्र दिखाता है कि कैसे उन्नत उपकरणों (kernel method, generating functions, transducer theory) को गैर-रेखीय नेस्टेड पुनरावृत्तियों पर लागू किया जा सकता है, जो प्रतीत होने वाले यादृच्छिक अनुक्रमों में छिपी बीजगणितीय संरचनाओं (Catalan kernels) को प्रकट करते हैं।
4. नए खुले प्रश्न: यह "रिकॉर्ड क्लेम" अवलोकन को सिद्ध करने, कॉन्वे-मैलोस अनुक्रम (Conway-Mallows sequence) के परटर्बड वेरिएंट का विश्लेषण करने (जो $1/(2\phi)$ की ओर अभिसरित होते प्रतीत होते हैं), और आर्च मैक्सिमा और लैट्टिस पाथ (lattice paths) के बीच द्वैत संबंध की खोज करने जैसे नए मार्ग खोलता है।

प्रमाण रणनीति का सारांश (Summary of the Proof Strategy)

प्रमाण "आर्च स्तरों" $r$ पर आगमन (induction) द्वारा चलता है।

1. आधार (Base): पहले कुछ आर्चों के लिए संरचना स्थापित करना।
2. आगमन चरण (Inductive Step): इंटरलीव ट्रांसड्यूसर का उपयोग करके यह दिखाना कि स्तर $r+1$ का स्टेप वर्ड स्तर $r$ से निर्मित है।
3. धनात्मकता (Positivity): यह सिद्ध करना कि इंटरलीविंग में "पैडिंग" बिट्स पर्याप्त धनात्मक ऊँचाई इंजेक्ट करते हैं ताकि विचलन कभी शून्य से नीचे न गिरे (अनुक्रम को वैध बनाए रखना)।
4. गणना (Counting): स्व-समान संरचना का उपयोग करके यह गिनना कि मान कितनी बार देखे जाते हैं (मार्ग B) या आर्च कितने ऊँचे बढ़ते हैं (मार्ग A)।
5. व्युत्क्रमण (Inversion): गणना सांख्यिकी को $\tilde{Q}(n)/n$ के स्पर्शोन्मुखी व्यवहार में बदलना।

शोध पत्र निष्कर्ष निकालता है कि परटर्बड अनुक्रम एक सुलभ, स्व-समान वस्तु है जो कैटलन संयोजन विज्ञान द्वारा नियंत्रित है, जो मूल हॉफस्टैडर Q-अनुक्रम के रहस्यों को खोलने की एक संभावित कुंजी प्रदान करता है।