🔢 mathematics

Balanced Fibonacci word rectangles, and beyond

यह शोध पत्र प्रदर्शित करता है कि फाइबोनैकी शब्दों (Fibonacci words) से निर्मित आयताकार आव्यूहों (rectangular matrices) के संतुलन गुणों (balance properties) को एक परिमित स्वचालक (finite automaton) द्वारा निर्धारित किया जा सकता है, इस परिणाम को द्विघाती अपरिमेय संख्याओं (quadratic irrationals) से जुड़े स्टर्मियन शब्दों (Sturmian words) तक विस्तारित करता है, और ट्राइबोनैकी (Tribonacci) तथा थ्यू-मौरिस (Thue-Morse) शब्दों के लिए समान गुणों की जांच करता है।

मूल लेखक: Jeffrey Shallit, Ingrid Vukusic

प्रकाशित 2026-03-31

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

CC BY 4.0

मूल लेखक: Jeffrey Shallit, Ingrid Vukusic

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

कल्पना कीजिए कि आपके पास कागज की एक अनंत पट्टी है जो काले और सफेद बिंदुओं के पैटर्न से ढकी हुई है। यह पैटर्न यादृच्छिक (random) नहीं है; यह एक बहुत ही विशिष्ट, गणितीय लय का पालन करता है जिसे फाइबोनैची शब्द (Fibonacci word) कहा जाता है। यह कुछ ऐसा दिखता है: 01001010... (जहाँ 0 सफेद है और 1 काला है)।

अब, कल्पना कीजिए कि आप कैंची लेकर इस पट्टी से एक आयताकार खिड़की काटते हैं। आप इस खिड़की को पट्टी के साथ खिसका सकते हैं, और हर बार जब आप इसे हिलाते हैं, तो आप अपनी खिड़की के भीतर बिंदुओं की एक अलग व्यवस्था देखते हैं।

बड़ा सवाल:
यदि आप इस खिड़की को खिसकाना जारी रखते हैं, तो क्या इसके अंदर काले बिंदुओं की संख्या लगभग समान रहेगी? या यह बहुत अधिक उतार-चढ़ाव दिखाएगी, कभी लगभग सभी काले बिंदु और कभी लगभग सभी सफेद बिंदु?

गणित की भाषा में, हम एक आयत को "संतुलित" (balanced) कहते हैं यदि उस आकार की किसी भी खिड़की में काले बिंदुओं की संख्या कभी भी बहुत अधिक नहीं बदलती है (विशेष रूप से, "सबसे अधिक काले" वाली खिड़की और "सबसे कम काले" वाली खि "खिड़की के बीच का अंतर 1 या 2 से अधिक नहीं होता है)।

जेफ्री शालिट और इंग्रिड वुकुसिक का यह शोध पत्र एक जासूसी कहानी की तरह है। वे इस सवाल का उत्तर देने की कोशिश कर रहे हैं: "खिड़कियों के किन आकारों (जैसे कि 4x5 या 7x12) के लिए पैटर्न पूरी तरह से संतुलित है?"

यहाँ उनकी खोज का विवरण दिया गया, जिसे रोजमर्रा के उदाहरणों के माध्यम से समझाया गया है:

1. "जादुई मशीन" (फाइनाइट ऑटोमेटा - Finite Automata)

लेखकों ने केवल अनुमान नहीं लगाया। उन्होंने एक "जादुई मशीन" बनाई (कंप्यूटर विज्ञान में जिसे फाइनाइट ऑटोमेटन कहा जाता है)।

इस मशीन को एक क्लब के बहुत सख्त बाउंसर के रूप में सोचें।

आप बाउंसर को दो संख्याएँ देते हैं: आपकी खिड़की की चौड़ाई ( $m$ ) और ऊंचाई ( $n$ )।
बाउंसर एक गुप्त नियम पुस्तिका (जो वास्तव में अवस्थाओं का एक जटिल फ्लोचार्ट है) की जांच करता है।
यदि खिड़की का आकार "संतुलित" है, तो बाउंसर आपको अंदर आने देता है (कहता है "हाँ")।
यदि खिड़की का आकार "असंतुलित" है, तो बाउंसर आपको बाहर निकाल देता है (कहता है "नहीं") है।

आश्चर्य की बात यह है कि फाइबोनैची शब्द के लिए, यह बाउंसर आश्चर्यजनक रूप से सरल है। इसे पूरी अनंत पट्टी को याद रखने की आवश्यकता नहीं है; इसे बस एक विशेष कोड (जिसे ज़ेकेनडॉरफ़ प्रतिनिधित्व कहा जाता है, जो फाइबोनैची संख्याओं का उपयोग करके गिनती करने जैसा है) में $m$ और $n$ को देखने और एक त्वरित निर्णय लेने की आवश्यकता है।

2. "सीढ़ी" का उदाहरण (यह क्यों काम करता है)

फाइबोनैची शब्द क्यों विशेष है? कल्पना कीजिए कि बिंदु सीढ़ी के पायदान हैं।

यदि आप एक कदम ऊपर जाते हैं, तो आप 0 से 1 पर जाते हैं।
यदि आप एक कदम नीचे जाते हैं, तो आप 1 से 0 पर जाते हैं।
फाइबोनैची शब्द इस तरह बनाया गया है कि आप कभी भी एक साथ दो कदम ऊपर नहीं लेते, और आप कभी भी एक साथ दो कदम नीचे नहीं लेते। यह एक बहुत ही कोमल, लयबद्ध चाल है।

लेखकों ने सिद्ध किया कि यदि आप किसी भी आयताकार खिड़की की "कुल ऊंचाई" (बिंदुओं का योग) को देखते हैं, तो उच्चतम खिड़की और निम्नतम खिड़की के बीच का अंतर बहुत कम होता है। उन्होंने एक विशिष्ट नियम पाया: यदि आपकी दोनों संख्याओं में से बड़ी संख्या (चौड़ाई या ऊंचाई) एक फाइबोनैची संख्या (जैसे 2, 3, 5, 8, 13...) है, तो खिड़की गारंटी के साथ संतुलित है।

लेकिन वे इससे भी आगे बढ़े! उन्होंने अन्य आकार भी खोजे जो संतुलित हैं, जैसे कि 4x3 की खिड़की। उन्होंने अपने "जादुई मशीन" का उपयोग करके सभी जीतने वाले आकारों की सूची बनाई।

3. "ट्राइबोनैची" और "थ्यू-मौरस" के चचेरे भाई

लेखकों ने केवल फाइबोनैची शब्द तक ही सीमित नहीं रहे। उन्होंने दो अन्य प्रसिद्ध पैटर्न भी देखे:

ट्राइबोनैची शब्द (Tribonacci Word): यह फाइबोनैची शब्द जैसा ही है लेकिन इसमें दो रंगों (0, 1 और 2) के बजाय तीन रंग हैं। यह अधिक अराजक (chaotic) है। उन्होंने पाया कि इस पैटर्न के लिए, यदि आपकी खिड़की बहुत लंबी (3 या अधिक पंक्तियाँ) है, तो इसका पूरी तरह से संतुलित होना असंभव है। यह एक डगमगाते हुए टॉवर को खड़ा करने जैसा है; अंततः वह गिर ही जाता है।
थ्यू-मौरस शब्द (Thue-Morse Word): यह एक ऐसा पैटर्न है जो खुद को कभी दोहराता नहीं है। यहाँ, गणित थोड़ा अलग है। लेखों ने पाया कि "असंतुलन" (सबसे अधिक और सबसे कम बिंदुओं के बीच का अंतर) हमेशा बहुत कम होता है (कभी भी 4 से अधिक नहीं होता), चाहे खिड़की का आकार कुछ भी हो। यह एक बहुत अच्छी तरह से मिश्रित सलाद की तरह है; आप कितना भी बड़ा स्कूप लें, सामग्री का अनुपात लगभग समान रहता है।

4. "कंप्यूटर मस्तिष्क" (वॉलनट - Walnut)

उन्होंने ये नियम कैसे खोजे? उन्होंने इसे पेंसिल और कागज से नहीं किया। उन्होंने वॉलनट (Walnut) नामक एक मुफ्त सॉफ़्टवेयर टूल का उपयोग किया।

वॉलनट को एक सुपर-पावर्ड कैलकुलेटर के रूप में सोचें जो "लॉजिक" (तर्क) की भाषा बोलता है। आप इसे बता सकते हैं: "हर संभावित खिड़की के आकार की जाँच करें। यदि आपको ऐसी खिड़की मिलती है जहाँ बिंदुओं की संख्या बहुत अधिक उतार-चढ़ाव करती है, तो उसे 'खराब' के रूप में चिह्नित करें।"
कंप्यूटर फिर स्वचालित रूप से "बाउंसर" (ऑटोमेटन) बनाता है। लेखकों को थ्यू-मौरस शब्द के लिए कंप्यूटर द्वारा गणना पूरी करने का इंतज़ार करना पड़ा, जिसमें 3 घंटे से अधिक का समय लगा और इसने मेमोरी (100 गीगाबाइट रैम) का एक विशाल हिस्सा इस्तेमाल किया—जैसे एक पहेली को हल करने के लिए हार्ड ड्राइवों से भरा एक छोटा गोदाम भरना!

निष्कर्ष (The Takeaway)

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

फाइबोनैची शब्द के लिए: एक सरल चेकलिस्ट (ऑटोमेटन) है जो यह बता सकती है कि कोई भी आयत का आकार निष्पक्ष और संतुलित है या नहीं।
अन्य शब्दों के लिए: हम उन्हीं उपकरणों का उपयोग यह देखने के लिए कर सकते हैं कि क्या वे निष्पक्ष हैं, और यदि नहीं, तो वे कितने अनुचित हैं।

यह एक प्रतीत होने वाले अनंत, अराजक पैटर्न को स्पष्ट "हाँ" या "नहीं" उत्तर वाली एक सुल्झने वाली पहेली में बदल देता है, जो तर्क और कंप्यूटर की शक्ति के कारण संभव हुआ है।

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

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

यह शोध पत्र अनंत अनुक्रमों (infinite sequences) से प्राप्त आयताकार उप-मैट्रिक्स (वर्ड रेक्टेंकल्स) के संतुलन गुणों (balance properties) की जांच करता है।

संदर्भ: $\{0, 1\}$ पर आधारित एक अनंत अनुक्रम $(a_i)_{i \ge 0}$ के लिए, एक अनंत मैट्रिक्स $A$ को इस प्रकार परिभाषित किया जाता है कि $A_{k,\ell} = a_{k+\ell}$ । इंडेक्स $i$ से शुरू होने वाला $m \times n$ उप-मैट्रिक्स $A(i, m, n)$ , अनुक्रम के एक "विंडो" का प्रतिनिधित्व करता है।
संतुलन की परिभाषा: एक जोड़ी आयाम $(m, n)$ को तब संतुलित (balanced) माना जाता है जब सभी संभावित प्रारंभिक स्थितियों $i$ में प्रविष्टियों का योग $T(i, m, n)$ , अधिकतम दो विशिष्ट मानों तक ही सीमित रहता है।
मुख्य प्रश्न: विशिष्ट अनंत शब्दों (फाइबोनैची, ट्राइबोनैची, थ्यू-मर्स) के लिए, ठीक से निर्धारित करना कि कौन सी प्राकृतिक संख्याओं के जोड़े $(m, n)$ संतुलित आयत (rectangles) परिणाम देते हैं।
पृष्ठभूमि: एंसेल्मो आदि के पिछले कार्य ने स्थापित किया था कि यदि $\max(m, n)$ एक फाइबोनैची संख्या है, तो $m \times n$ फाइबोनैची आयत संतुलित होते हैं। हालाँकि, यह स्थिति पर्याप्त (sufficient) है लेकिन आवश्यक (necessary) नहीं है (उदाहरण के लिए, $(4,3)$ संतुलित है)। यह शोध पत्र एक पूर्ण लक्षण वर्णन (complete characterization) प्रदान करने का लक्ष्य रखता है।

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

लेखक अपनी प्राथमिक कार्यप्रणाली के रूप में ऑटोमेटा थ्योरी (automata theory) और लॉजिकल डिसाइडेबिलिटी (logical decidability) का उपयोग करते हैं, जिसमें Walnut नामक सॉफ़्टवेयर टूल का प्रयोग किया गया है।

फाइनाइट ऑटोमेटा निर्माण (Finite Automata Construction):
- फाइबोनैची शब्द (एक स्टर्मियन शब्द जो क्वाड्रेटिक इरेशनल $\gamma = (3-\sqrt{5})/2$ के अनुरूप है) के लिए, लेखक ओस्ट्रोव्स्की $\alpha$ -न्यूमरेशन सिस्टम (विशेष रूप से ज़ेकेन्डॉर्फ प्रतिनिधित्व) का उपयोग करते हैं।
- वे एक मानदंड (लेम्मा 1) स्थापित करते हैं जिसमें कहा गया है कि आयत संतुलित हैं यदि और केवल यदि अंतरों का अनुक्रम $\Delta(i, m, n) = T(i+1, m, n) - T(i, m, n)$ विशिष्ट पैटर्न (जैसे $1, 0, \dots, 0, 1$ या $-1, 0, \dots, 0, -1$ के ब्लॉक्स) नहीं रखता है।
- चूँकि स्थिति $x = \lfloor n\alpha \rfloor$ को क्वाड्रेटिक इरेशनल्स के लिए फर्स्ट-ऑर्डर लॉजिक में व्यक्त किया जा सकता है, इसलिए संतुलन मानदंड को फर्स्ट-ऑर्डर फॉर्मूला में अनुवादित किया जा सकता है।
- Walnut का उपयोग करके, इस फॉर्मूले को एक फाइनाइट ऑटोमेटा में परिवर्तित किया जाता है जो जोड़ों $(m, n)$ (ज़ेकेन्डॉर्फ रूप में प्रतिनिधित्व) को स्वीकार करता है यदि और केवल यदि वे संतुलित हैं।
अन्य शब्दों का सामान्यीकरण (Generalization to Other Words):
- ट्राइबोनैची शब्द (Tribonacci Word): लेखक ट्राइबोनैची न्यूमरेशन सिस्टम का उपयोग करके दृष्टिकोण को अनुकूलित करते हैं। वे उप-आयतों में प्रतीकों $0, 1, 2$ की उपस्थिति को गिनने के लिए ऑटोमेटा का निर्माण करते हैं और 2-बैलेंस की स्थिति को सत्यापित करते हैं।
- थ्यू-मर्स (Thue–Morse) शब्द: थ्यू-मर्स अनुक्रम की विशिष्ट समरूपता ( $t_{2k} + t_{2k+1} = 1$ ) के कारण, लेखक योग को सीमित करने के लिए एक पेयरिंग तर्क (pairing argument) का उपयोग करते हैं। वे इसे Walnut में बेस-(-2) प्रतिनिधित्व का उपयोग करके लागू करते हैं ताकि नकारात्मक अंतरों को स्वाभाविक रूप से संभाला जा सके, और अंततः परिणाम को मानक बेस-2 ऑटोमेटा में परिवर्तित करते हैं।
रैखिक प्रतिनिधित्व (Linear Representations): डेंसिटी और डाइवर्सिटी परिणामों (थ्योरम 8) को सिद्ध करने के लिए, लेखक विशिष्ट $m$ और $n$ के अनुक्रमों के लिए $T(i, m, n)$ के सटीक मानों की गणना करने हेतु रैखिक प्रतिनिधित्व (मैट्रिक्स/वेक्टर के ट्रिपल) का उपयोग करते हैं, और Maple के माध्यम से पहचानों (identities) को सत्यापित करते हैं।

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

A. फाइबोनैची शब्द (The Fibonacci Word)

पूर्ण लक्षण वर्णन (Complete Characterization): लेखक एक 15-स्टेट फाइनाइट ऑटोमेटा (चित्र 1) का निर्माण करते हैं जो फाइबोनैची शब्द के लिए सटीक रूप से संतुलित जोड़ों $(m, n)$ को स्वीकार करता है। यह सिद्ध करता है कि संतुलित जोड़ों का सेट ज़ेकेन्डॉर्फ न्यूमरेशन सिस्टम में एक रेगुलर लैंग्वेज है।
मानव-पठनीय मानदंड (Human-Readable Criteria): वे थ्योरम 7 प्राप्त करते हैं, जो ज़ेकेन्डॉर्फ विस्तारों (इंडेक्स की पैरिटी और फाइबोनैची घटकों के सापेक्ष आकार शामिल करते हुए) पर आधारित एक गैर-ऑटोमेटा-आधारित लक्षण वर्णन है।
पिछले परिणामों की पुष्टि: ऑटोमेटा स्वचालित रूप से एंसेल्मो आदि के प्रमेय (कि यदि $\max(m, n)$ एक फाइबोनैची संख्या है, तो जोड़ी संतुलित है) को सत्यापित करता है।
डेंसिटी और डाइवर्सिटी (Density and Diversity):
- प्रपोजिशन 5: फाइबोनैची अंतराल के भीतर संतुलित जोड़ों के भीतर आवधिकता (periodicity) और समरूपता गुणों को स्थापित करता है।
- प्रपोजिशन 6: यह सिद्ध करता है कि किसी भी $m$ के लिए, एक $j \le F_{i+1}$ मौजूद है जिससे $(m, n+j)$ संतुलित है, जो संतुलित $n$ के घनत्व पर निचला स्तर (lower bound) स्थापित करता है।
- थ्योरम 8 और कोरोलरी 9: सिद्ध करता है कि $m=n=F_{3k/2}$ के लिए, $T(i, m, n)$ के विभिन्न मानों की संख्या $k$ के साथ रैखिक रूप से बढ़ती है (विशेष रूप से $\Theta(k)$ ), जो यह दर्शाता है कि सभी $m, n$ के लिए अलग-अलग योगों की संख्या एक स्थिरांक (constant) द्वारा सीमित नहीं है।

B. ट्राइबोनैची शब्द (The Tribonacci Word)

थ्योरम 10: ट्राइबोनैची शब्द (जो $\{0, 1, 2\}$ ${0, 1, 2}$ प्रतीकों का उपयोग करता है) के लिए 2-बैलेंस्ड आयतों का लक्षण वर्णन करता है:
- यदि $m=1$ , तो सभी $n$ संतुलित हैं।
- यदि $m=2$ , तो विशिष्ट $n$ को स्वीकार करने वाला एक 77-स्टेट ऑटोमेटा मौजूद है।
- यदि $m \ge 3$ , तो कोई भी $n$ मौजूद नहीं है जिससे आयत 2-बैलेंस्ड हो।
$m \ge 3$ के लिए प्रमाण दो आयतों के बीच प्रतीक '2' की गिनती में कम से कम 3 के अंतर वाले विशिष्ट काउंटर-उदाहरणों के निर्माण के माध्यम से शामिल है।

C. थ्यू-मर्स शब्द (The Thue–Morse Word)

थ्योरम 11: स्थापित करता है कि किसी भी $m \times n$ आयत के लिए, संतुलन (औसत योग $mn/2 $से विचलन) 4 तक सीमित है। विशेष रूप से,$ |2|A(i, m, n)|_1 - mn| \le 4$।
थ्योरम 12: किसी भी इनपुट $(m, n)$ $(m, n)$ के लिए सटीक संतुलन मान (1, 2, 3, या 4) निर्धारित करने के लिए एक 92-स्टेट ऑटोमेटा (बेस 2 में) का निर्माण करता है।
- नोट: यह गणना विशाल थी, जिसके लिए 12834 CPU सेकंड और 100GB RAM की आवश्यकता थी, और एक मध्यवर्ती ऑटोमेटा 32 मिलियन से अधिक अवस्थाओं तक पहुँच गया।
थ्योरम 14: सिद्ध करता है कि $m, n \ge 3$ के लिए, संतुलन ठीक 3 है यदि और केवल यदि $m$ और $n$ दोनों विषम (odd) हैं।

4. महत्व (Significance)

एल्गोरिद्मिक नंबर थ्योरी (Algorithmic Number Theory): यह शोध पत्र ऑटोमेटा-आधारित निर्णय प्रक्रियाओं (विशेष रूप से Walnut का उपयोग करके) की शक्ति को प्रदर्शित करता है, जो अनंत शब्दों पर जटिल कॉम्बिनेटोरियल समस्याओं को हल करती है। यह दिखाता है कि स्टर्मियन और अन्य मॉर्फिक शब्दों के गुणों को फाइनाइट ऑटोमेटा में पथों के अस्तित्व में बदला जा सकता है।
सामान्यीकरण (Generalization): यह केवल फाइबोनैची संख्याओं के विशिष्ट मामले से आगे बढ़कर एक सामान्य ढांचे तक जाता है जो किसी भी क्वाड्रेटिक इरेशनल के अनुरूप स्टर्मियन शब्द के लिए लागू होता है, और गैर-बाइनरी शब्दों (ट्राइबोनैची) और भिन्न संतुलन परिभाषाओं (थ्यू-मर्स) तक इसका विस्तार करता है।
सहज ज्ञान (Intuition) का खंडन: परिणाम दिखाते हैं कि जबकि कुछ "अच्छी" स्थितियाँ (जैसे फाइबोनैची आयाम) संतुलन सुनिश्चित करती हैं, संतुलित जोड़ों का पूर्ण सेट जटिल है और सटीक विवरण के लिए ऑटोमेटा की आवश्यकता होती है। इसके अलावा, अलग-अलग योगों की संख्या आयाम के साथ रैखिक रूप से बढ़ सकती है, जो इस विचार का खंडन करती है कि ये योग हमेशा कसकर क्लस्टर्ड (tightly clustered) होते हैं।
ओपन सोर्स सत्यापन (Open Source Verification): सभी प्रमाण रचनात्मक (constructive) हैं और कोड (Walnut और Maple) के माध्यम से सत्यापित हैं, जो पुनरुत्पादकता (reproducibility) सुनिश्चित करने के लिए सार्वजनिक रूप से उपलब्ध कराया गया है, जिससे समान समस्याओं के आगे के अन्वेषण की अनुमति मिलती है।