🔢 mathematics

Superlinear complexity of the $(3/2)^n$ steering word

यह शोध पत्र सिद्ध करता है कि $(3/2)^n$ मैप द्वारा जनरेट किए गए स्टीयरिंग शब्द (steering word) की सबवर्ड जटिलता (subword complexity) सुपरलीनियर है, जो कि सबस्पेस थ्योरम (Subspace Theorem) का उपयोग करके स्थापित किया गया एक परिणाम है और इसे Lean-4 में पूरी तरह से औपचारिक रूप दिया गया है।

मूल लेखक: Ralf Stephan

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

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

CC0 1.0

मूल लेखक: Ralf Stephan

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

एक जादुई मशीन की कल्पना करें जो एक संख्या लेती है, उसे 1.5 से गुणा करती है, और फिर उसे निकटतम पूर्ण संख्या (whole number) तक राउंड करती है। अब, 1 से शुरू करके इस मशीन को बार-बार चलाने की कल्पना करें।

1 बनता है 1.5, जो राउंड होकर 2 हो जाता है।
2 बनता है 3, जो 3 ही रहता है।
3 बनता है 4.5, जो राउंड होकर 5 हो जाता है।
5 बनता है 7.5, जो राउंड होकर 8 हो जाता है।

यह पूर्ण संख्याओं की एक श्रृंखला बनाता है: 1, 2, 2, 3, 5, 8, इत्यादि। लेकिन यह शोध पत्र केवल संख्याओं में रुचि नहीं रखता; यह उस "स्टीयरिंग व्हील" (steering wheel) में रुचि रखता है जो मशीन को बताती है कि वह वहां कैसे पहुँची। हर एक चरण में, मशीन को यह चुनना था कि निकटतम पूर्णांक तक पहुँचने के लिए ऊपर की ओर राउंड करना है या नीचे की ओर। उन्होंने इन सभी छोटे निर्णयों को एक कोड (जैसे कि -2, -1, 0, 1, या 2 का उपयोग करके) के रूप में रिकॉर्ड किया। जब आप इन निर्णयों को एक साथ जोड़ते हैं, तो आपको एक लंबा, अनंत "स्टीयरिंग शब्द" (steering word) प्राप्त होता है।

बड़ा सवाल यह है: इस कोड की जटिलता क्या है?

पैटर्न की दुनिया में, कुछ कोड उबाऊ रूप से सरल होते हैं। एक गाने के बारे में सोचें जो अनंत काल तक "ला-ला-ला" दोहराता रहता है। वह एक सरल पैटर्न है। अन्य कोड रेडियो पर आने वाले शोर (static) की तरह अराजक और अव्यवस्थित होते हैं। गणितज्ञ इस "अव्यवस्था" को कोड के एक निश्चित लंबाई के अद्वितीय छोटे टुकड़ों (या subwords) को गिनकर मापते हैं। यदि एक कोड सरल है, तो उसके अद्वितीय टुकड़ों की संख्या धीरे-धीरे बढ़ती है (जैसे एक सीधी रेखा)। यदि यह जटिल है, तो उसके अद्वितीय टुकड़ों की संख्या विस्फोट की तरह बढ़ती है।

मुख्य निष्कर्ष
यह शोध पत्र सिद्ध करता है कि यह विशिष्ट स्टीयरिंग शब्द अत्यधिक जटिल (wildly complex) है। यह केवल एक सीधी रेखा में नहीं बढ़ता; यह "सुपरलीनियरली" (superlinearly) बढ़ता है। इसका अर्थ यह है कि जैसे-जैसे आप कोड के लंबे और लंबे टुकड़ों को देखते हैं, आपको मिलने वाले अद्वितीय पैटर्न की संख्या तेजी से बढ़ती है और अनंत की ओर भागती है।

इसे एक मनोरंजक तरीके से कहें तो: यदि आप इस अनुक्रम के पिछले हिस्से को देखकर अगले कदम की भविष्यवाणी करने का प्रयास करते हैं, तो आप अंततः एक दीवार से टकरा जाएंगे। आप चाहे कितना भी लंबा पैटर्न खोज लें, यह अनुक्रम अंततः कुछ ऐसा करेगा जो आपने पहले कभी नहीं देखा होगा। यह एक लूप में सेटल होने से इनकार करता है।

यह पेपर क्या खारिज करता है?
यह पेपर इस विचार को स्पष्ट रूप से खारिज करता है कि यह अनुक्रम "अंततः आवर्ती" (eventually periodic) है। सरल शब्दोंियों में, इसका अर्थ है कि यह कभी भी एक टूटे हुए रिकॉर्ड की तरह दोहराव वाले चक्र में नहीं फँसेगा। यह कभी भी अनंत काल तक "1, 2, 3, 1, 2, 3" दोहराना शुरू नहीं करेगा। लेखक यह सिद्ध करते हैं कि आप चाहे कितनी भी दूर तक जाएँ, आपको कभी भी वह बिंदु नहीं मिलेगा जहाँ यह बस एक ही पैटर्न को बार-बार दोहराता रहे।

वे कितने आश्वस्त हैं?
लेखक केवल अनुमान नहीं लगा रहे हैं या कंप्यूटर पर इसका सिमुलेशन नहीं कर रहे हैं। उन्होंने सिद्ध किया है।

उन्होंने तर्क का एक किला बनाया जिसमें दो भारी-भरकम गणितीय उपकरण (कोर्वाजा-ज़ैनियर और नायर-कुमार-रौट के प्रमेय) शामिल हैं जो अटूट तालों की तरह कार्य करते हैं। उन्होंने एक विशेष कार्य भी किया: उन्होंने अपने पूरे प्रमाण को 'लीन-4' (Lean-4) नामक एक कंप्यूटर भाषा में अनुवादित किया। इस कंप्यूटर ने मानवीय त्रुटियों के बिना सुनिश्चित करने के लिए उनके तर्क के प्रत्येक चरण की जाँच की। कंप्यूटर ने कहा, "हाँ, यह प्रमाण वैध है।"

प्रमाण की यात्रा
यह प्रमाण तीन चरणों में होता है, जैसे कोई पहाड़ चढ़ना:

चरण 0 (नींव): उन्होंने पहले दिखाया कि यदि अनुक्रम एक लंबे पैटर्न को दोहराता, तो यह गणित के नियमों को तोड़ देता (विशेष रूप से, यह एक गणितीय असंभवता पैदा करता कि संख्याएँ कैसे विभाजित होती हैं)। इसने सिद्ध किया कि यह अनुक्रम एक साधारण लूप नहीं है और इसने पहले ही दिखाया कि यह सबसे सरल गैर-लूपिंग पैटर्न से अधिक जटिल है।
चरण 1 (न्यूनीकरण/Reduction): उन्होंने महसूस किया कि अत्यधिक जटिल होने को सिद्ध करने के लिए, उन्हें केवल एक विशिष्ट बात सिद्ध करने की आवश्यकता है: कि अनुक्रम में संख्याएं आपस में बहुत अधिक "करीब" नहीं आती हैं। यदि वे दूर रहतीं, तो कोड जटिल होने के लिए मजबूर होता।
चरण 2 (शिखर): उन्होंने उन भारी-भरकम गणितीय उपकरणों का उपयोग करके यह सिद्ध किया कि संख्याएं वास्तव में दूर रहती हैं। उन्होंने समस्या को तीन क्षेत्रों में विभाजित किया:
- छोटा अंतराल क्षेत्र (Small Gap Zone): जब अनुक्रम में संख्याएं पास होती हैं।
- विशाल अंतराल क्षेत्र (Huge Gap Zone): जब संख्याएं अनुक्रम में बहुत दूर होती हैं।
- मध्यम क्षेत्र (Middle Zone): बीच का पेचीदा क्षेत्र।

पहले दो क्षेत्रों के लिए, उन्होंने एक शक्तिशाली प्रमेय का उपयोग किया। मध्यम क्षेत्र के लिए, उन्होंने एक चतुर तकनीक (एक "द्वंद्व" या dichotomy) का उपयोग किया जिसने दिखाया कि यदि पैटर्न सरल होने की कोशिश करता है, तो यह एक विरोधाभास की ओर ले जाएगा (जैसे यह सिद्ध करना कि एक भिन्न वास्तव में एक पूर्ण संख्या है, जो असंभव है)।

निष्कर्ष
(3/2) अनुक्रम के लिए स्टीयरिंग शब्द एक अराजक, गैर-दोहराव वाला उत्कृष्ट नमूना है। यह इतना जटिल है कि इसमें मौजूद अद्वितीय पैटर्न की संख्या किसी भी सीधी रेखा से अधिक तेजी से बढ़ती है। यह केवल एक सुझाव या सिमुलेशन नहीं है; यह एक गणितीय रूप से सिद्ध तथ्य है, जिसे एक कंप्यूटर द्वारा दोबारा जांचा गया है, जो यह दर्शाता है कि यह सरल दिखने वाला नियम एक अनंत रूप से जटिल संख्यात्मक नृत्य उत्पन्न करता है।

तकनीकी सारांश: $(3/2)^n$ स्टीयरिंग वर्ड की सुपरलीनियर जटिलता (Superlinear Complexity)

समस्या विवरण
यह शोध पत्र मैपिंग $x \mapsto \frac{3}{2}x$ के तहत संख्या 1 की कक्षा (orbit) द्वारा उत्पन्न प्रतीकात्मक गतिकी (symbolic dynamics) की जांच करता है, जो विशेष रूप से निकटतम-पूर्णांक राउंडिंग त्रुटियों (nearest-integer rounding errors) के अनुक्रम पर केंद्रित है। यद्यपि अनुक्रम $\|(\frac{3}{2})^n\|$ (निकटतम पूर्णांक से दूरी) का वितरण संख्या सिद्धांत में एक लंबे समय से खुला प्रश्न है, यह कार्य "स्टीयरिंग वर्ड" $T = (t_n)_{n \geq 0}$ पर ध्यान केंद्रित करता है। यह शब्द उन पूर्णांक अनुवादों (integer translates) को रिकॉर्ड करता है जिन्हें प्रत्येक चरण में स्वायत्त गतिकी (autonomous dynamics) द्वारा चुना जाता है, जिसे $t_n = 2m_{n+1} - 3m_n$ के रूप में परिभाषित किया गया है, जहाँ $m_n = \text{round}((\frac{3}{2})^n)$ है। संबोधित मुख्य प्रश्न $T$ की सबवर्ड जटिलता (subword complexity) $p_T(k)$ है, जो $T$ में लंबाई $k$ के विभिन्न कारकों (factors) की संख्या को गिनती है। इस शोध का लक्ष्य यह सिद्ध करना है कि यह जटिलता सुपरलीनियर (superlinear) है, जिसका अर्थ है $\lim_{k \to \infty} p_T(k)/k = \infty$ ।

कार्यप्रणाली (Methodology)
प्रमाण रणनीति तीन अलग-अलग चरणों में संरचित है, जो बीजगणिक संख्या जटिलता (विशेष रूप से एडमचवेस्की-बुगेऑड विधि) के अध्ययन से विधियों को इस गतिशील परिवेश में स्थानांतरित करती है। तर्क काफी हद तक सबस्पेस प्रमेय (Subspace Theorem) पर निर्भर है और इसे Lean-4 में पूरी तरह से औपचारिक रूप दिया गया है।

चरण 0: सटीक पहचान और बिना शर्त सीमाएँ (अनुभाग 2)
लेखक एक सटीक "पुनरावृत्ति पहचान" (repetition identity) व्युत्पन्न करते हैं। यदि लंबाई $k$ का एक कारक स्थितियों $a$ और $c$ ( $a < c$ ) पर दोहराया जाता है, तो यह संबंध $3^k(\varepsilon_c - \varepsilon_a) = 2^k(\varepsilon_{c+k} - \varepsilon_{a+k})$ को अनिवार्य बनाता है, जहाँ $\varepsilon_n$ राउंडिंग त्रुटि है।

यह पहचान एक विभाज्यता स्थिति प्रदान करती है: $2^k \mid (m_c - m_a)$ ।
कक्षा के विकास गुणों के साथ मिलकर, यह स्थापित करता है कि लंबे दोहराव शब्द में मनमाने ढंग से बहुत देर तक नहीं हो सकते।
बिना शर्त परिणाम (Unconditional Result): यह शोध पत्र सिद्ध करता है कि $T$ अंततः आवधिक (eventually periodic) नहीं है और एक रैखिक निचली सीमा $p_T(k) \geq \frac{41}{24}k - 3$ स्थापित करता है, जो आवधिक शब्दों के मोर्स-हेडlundलंड फ्लोर ( $k+1$ ) से स्पष्ट रूप से ऊपर है।

चरण 1: डायोफेंटाइन कर्नेल (Diophantine Kernel) में न्यूनीकरण (अनुभाग 3)
सुपरलीनियर जटिलता को सिद्ध करने की समस्या को एक एकल डायोफेंटाइन कथन में बदल दिया गया है, जिसे कर्नेल (K) कहा जाता है।

कथन (K): प्रत्येक परिमेय $\theta \in (0, 1)$ के लिए, $2 \leq a < c$ वाले जोड़ों $(a, c)$ का सेट, जो $\|(\frac{3}{2})^c - (\frac{3}{2})^a\| \leq \theta^c$ को संतुष्ट करता है, परिमित (finite) है।
यह एक "घातांकीय युग्म प्रतिकर्षण" (exponential pair repulsion) गुण का प्रतिनिधित्व करता है, जो कक्षा बिंदुओं के बीच की दूरी के मामूली निचली आधार $2^{-1}$ को आधार $\theta < 1$ तक सुधारता है।
न्यूनीकरण यह दर्शाता है कि यदि (K) सत्य है, तो $p_T(k)/k \to \infty$ होगा।

चरण 2: कर्नेल की स्थापना (अनुभाग 4 और 5)
(K) की सिद्धि को संभावित समाधानों के सेट को तीन "स्लाइस" में विभाजित करके प्राप्त किया गया है, और डायोफेंटाइन सन्निकटन के गहरे परिणामों को लागू किया गया है:

बाउंडेड गैप स्लाइस (Bounded Gap Slice): निश्चित अंतराल $c-a$ के लिए, कोर्वजा-ज़ैनियर मुख्य प्रमेय (जो श्मिट सबस्पेस प्रमेय का एक परिणाम है) का उपयोग करके परिमितता सिद्ध की गई है।
ह्यूज-गैप स्लाइस (Huge-Gap Slice): उस क्षेत्र के लिए जहाँ $a \leq \epsilon' c$ , कोर्वजा-ज़ैनियर प्रमेय के माध्यम से परिमितता स्थापित की गई है, इसे छद्म-पिसोट अपवर्जन (pseudo-Pisot exclusion) के एक विशिष्ट मामले के रूप में माना गया है।
मिडल बैंड (Middle Band): शेष क्षेत्र के लिए जहाँ अंतराल बढ़ रहे हैं लेकिन $a$ , $c$ की तुलना में नगण्य नहीं है, लेखक एक गैप द्विशाख (gap dichotomy) का उपयोग करते हैं। यदि समाधानों का सेट अनंत होता, तो एक उप-परिवार निकाला जा सकता था जिसमें अलग-अलग अंतराल हों। इससे नैर-कुमार-रूट S-यूनिट टुपल प्रमेय के माध्यम से एक विरोधाभास उत्पन्न होता, जो यह संकेत देता कि किसी $c$ के लिए $(\frac{3}{2})^c$ एक पूर्णांक है, जो कि असंभव है।

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

मुख्य प्रमेय (प्रमेय 1.1): स्टीयरिंग वर्ड $T$ की सबवर्ड जटिलता सुपरलीनियर ( $p_T(k)/k \to \infty$ ) है।
बिना शर्त निचली सीमा: शोध पत्र बिना किसी अपुष्ट अनुमानों पर निर्भर हुए एक स्पष्ट, बिना शर्त रैखिक निचली सीमा $p_T(k) \geq \frac{41}{24}k - 3$ प्रदान करता है।
औपचारिकीकरण (Formalization): पूरे तर्क को Lean-4 में औपचारिक रूप दिया गया है। औपचारिकीकरण केवल 3 चरों वाले एवरटेज़-श्लिकवेई सबस्पेस प्रमेय पर निर्भर है, जिससे यह पुष्टि होती है कि कोर्वजा-ज़ैनियर और नैर-कुमार-रूट परिणामों पर इसकी निर्भरता तार्किक रूप से सबस्पेस प्रमेय के परिणामों के अनुरूप है।
अनिरंतरता (Aperiodicity): यह प्रमाण कि स्टीयरिंग वर्ड अंततः आवधिक नहीं है, एक कठोर प्रमाण प्रदान करता है।

महत्व और दावे
शोध पत्र का दावा है कि यह डायोफेंटाइन सन्निकटन और प्रतीकात्मक गतिकी के बीच सेतु बनाकर इस विशिष्ट स्वायत्त गतिशील प्रणाली के लिए जटिलता प्रश्न को हल करता है।

पद्धतिगत स्थानांतरण (Methodological Transfer): यह एडमचवेस्की-बुगेऑड विधि को सफलतापूर्वक अनुकूलित करता है, जो आमतौर पर बीजगणिक संख्याओं के लिए उपयोग की जाती है, एक गतिशील शब्द के लिए। लेखक नोट करते हैं कि $(3/2)$ -गतिकी की स्वायत्त प्रकृति लेखा-जोखा (bookkeeping) को सरल बनाती है, जिससे बार-बार होने वाले कारक बिना प्रीफ़िक्स-एंकरिंग के स्वच्छ डायोफेंटाइन असमानताओं में संकुचित हो जाते हैं।
गहरे प्रमेयों पर निर्भरता: सुपरलिनियरिटी के संबंध में परिणाम कोर्वजा-ज़ैनियर प्रमेय (पीअर-रिव्यू किया गया) और नैर-कुमार-रूट प्रमेय (लेखन के समय एक प्रीप्रिंट) पर सशर्त हैं। हालाँकि, Lean-4 औपचारिकीकरण यह सत्यापन प्रदान करता है कि ये निर्भरताएं सबस्पेस प्रमेय के तार्किक रूप से सुसंगत परिणाम हैं।
सीमाएँ: सुपरलीनियर वृद्धि के संबंध में परिणाम अप्रभावी (ineffective) हैं; सबस्पेस प्रमेय अपवाद सेटों (डायोफेंटाइन असमानताओं के समाधानों का सेट) के आकार पर स्पष्ट सीमाएँ प्रदान नहीं करता है। यह शोध पत्र $\|(\frac{3}{2})^n\| \to 0$ की घनत्व संबंधी व्यापक खुली समस्या को हल करने का दावा नहीं करता है, बल्कि राउंडिंग अनुक्रम की कॉम्बिनेटरियल जटिलता का वर्णन करता है।

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