🔢 mathematics

Hamilton decompositions of all directed tori at odd modulus

यह शोध पत्र सिद्ध करता है कि $d$ निर्देशित $m$ -चक्रों (directed $m$ -cycles) का निर्देशित कार्तीय उत्पाद (directed Cartesian product), सभी आयामों $d \geq 2$ और सभी विषम माड्यूली $m \geq 3$ के लिए एक निर्देशित हैमिल्टन विखंडन (directed Hamilton decomposition) स्वीकार करता है, जिसमें नए क्लोजर तंत्रों (closure mechanisms), आधार आयाम परिणामों (base dimension results) और लीन 4 (Lean 4) में औपचारिक सत्यापन (formal verification) का संयोजन उपयोग किया गया है।

मूल लेखक: SangHyun Park

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

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

CC BY 4.0

मूल लेखक: SangHyun Park

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

कल्पना कीजिए कि एक विशाल, बहु-आयामी डोनट (donut) बिंदुओं के एक ग्रिड से बना है। गणित में, इसे एक टोरस (torus) कहा जाता है। अब, कल्पना कीजिए कि इस डोनट के हर एक बिंदु पर, पड़ोसी बिंदुओं की ओर जाने वाली कई एक-तरफ़ा सड़कें (तीर) हैं। आपका दिया गया पेपर एक बहुत ही विशिष्ट पहेली के बारे में है: क्या हम इन सभी एक-तरफ़ा सड़कों को अलग-अलग रंगों से रंग सकते हैं ताकि प्रत्येक रंग एक एकल, विशाल लूप (loop) बनाए जो डोनट के प्रत्येक बिंदु से ठीक एक बार होकर गुजरे?

यदि हम ऐसा कर सकते हैं, तो हमने डोनट को पूर्ण, गैर-अतिव्यापी (non-overlapping) लूपों में "विभाजित" (decompose) कर दिया है। यह पेपर सिद्ध करता है कि एक विशिष्ट प्रकार के डोनट के लिए (जहाँ प्रत्येक तरफ बिंदुओं की संख्या एक विषम संख्या जैसे 3, 5, 7, आदि है), उत्तर हाँ, हम हमेशा ऐसा कर सकते हैं, चाहे वह डोनट कितने भी आयामों (dimensions) का क्यों न हो।

यहाँ लेखकों ने इस पहेली को कैसे हल किया, इसे सरल उपमाओं के माध्यम से समझाया गया है:

1. लक्ष्य: पूर्ण लूप (The Perfect Loop)

डोनट को एक ऐसे शहर के रूप में सोचें जहाँ आप $d$ अलग-अलग दिशाओं ( $d$ different directions) में गाड़ी चला सकते हैं (उत्तर, पूर्व, ऊपर, आदि)। शहर बहुत बड़ा है, और प्रत्येक चौराहे पर ठीक $d$ सड़कें बाहर निकल रही हैं।

चुनौती: आपको शहर की हर सड़क को $d$ अलग-अलग रंगों से पेंट करना है।
नियम: यदि आप केवल "लाल" सड़कों का अनुसरण करते हैं, तो आपको अंततः शहर के प्रत्येक चौराहे से गुजरना चाहिए और बिना किसी चौराहे पर दोबारा आए, अपने शुरुआती बिंदु पर वापस आना चाहिए। यही बात "नीले", "हरे" और अन्य प्रत्येक रंग के लिए भी सच होनी चाहिए।
पेपर का दावा: किसी भी शहर के आकार के लिए जहाँ प्रत्येक दिशा में ब्लॉकों की संख्या एक विषम संख्या (odd number) है, यह पूर्ण रंगाई हमेशा संभव है।

2. दो मुख्य उपकरण (The Two Main Tools)

लेखकों ने केवल अनुमान नहीं लगाया; उन्होंने शहर के आकार की तुलना में दिशाओं की संख्या के आधार पर दो अलग-अलग "मशीनें" बनाईं।

टूल A: "हाई-राइज" मशीन (बड़े शहरों के लिए)

यह कब काम करता है: जब शहर बहुत बड़ा हो (ब्लॉकों की संख्या $m$ , दिशाओं की संख्या $d$ से बड़ी हो)।
यह कैसे काम करता है: कल्पना करें कि शहर एक गगनचुंबी इमारत है जिसमें कई मंजिलें हैं। लेखक "प्रिफिक्स-काउंट" (Prefix-Count) नामक एक चतुर गणना तकनीक का उपयोग करते हैं।

वे आपके द्वारा उठाए गए प्रत्येक कदम को एक "स्कोर" देते हैं।
वे सुनिश्चित करते हैं कि यदि आप एक विशिष्ट रंग का अनुसरण करते हैं, तो आपके स्कोर इस तरह जुड़ते हैं कि यह गारंटी मिलती है कि आप एक छोटे लूप में नहीं फंसेंगे। आपको हर मंजिल और हर कमरे में जाने के लिए ऊपर चढ़ने के लिए मजबूर किया जाता है।
वे एक "साइन वाले बाइनरी" (signed binary) तरीके का उपयोग करते हैं (एक संतुलन पैमाने की तरह जिसमें धनात्मक और ऋणात्मक भार होते हैं) ताकि यह सुनिश्चित हो सके कि गणित पूरी तरह से काम करे और लूप केवल सभी से मिलने के बाद ही बंद हो।

टूल B: "बेस-एंड-टेल" मशीन (छोटे शहरों के लिए)

यह कब काम करता है: जब शहर छोटा हो (ब्लॉकों की संख्या $m$ , दिशाओं की संख्या $d$ से कम हो)।
यह कैसे काम करता है: यह एक पहले से हल किए जा चुके छोटे शहर को लेकर एक नया, जटिल शहर बनाने जैसा है जिसमें एक "पूंछ" (tail) जोड़ी जाती है।

बेस (Base): वे समस्या के एक छोटे संस्करण से शुरू करते हैं जिसे वे पहले से ही हल करना जानते हैं (जैसे कि 5-आयामी शहर)।
टेल (Tail): वे अतिरिक्त आयाम (the "tail") जोड़ते हैं।
व्यापार (The Trade): वे एक "लोकल स्वैप" (local swap) तकनीक का उपयोग करते हैं। कल्पना करें कि आप एक विशिष्ट चौराहे पर हैं। आपके पास "पूंछ" की ओर जाने वाली कुछ सड़कें हैं। लेखक दिखाते हैं कि आप इन सड़कों के रंगों को स्थानीय रूप से बदल सकते हैं (जैसे अपने पड़ोसी के साथ कार्ड बदलना) ताकि त्रुटियों को ठीक किया जा सके। ऐसे पर्याप्त छोटे बदलावों के माध्यम से, वे रंगों को व्यवस्थित कर सकते हैं ताकि पूरा नया, बड़ा शहर पूरी तरह से काम करे।

3. "लेगो" रणनीति (लूप को बंद करना)

सबसे शक्तिशाली हिस्सा पेपर का यह भाग है कि वे प्रत्येक आकार को हल करने के लिए इन उपकरणों को कैसे जोड़ते हैं।

प्रोडक्ट नियम (The Product Rule): यदि आप 2D डोनट और 3D डोनट के लिए पहेली हल कर सकते हैं, तो आप स्वचालित रूप से 6D डोनट के लिए इसे हल कर सकते हैं (क्योंकि $2 \times 3 = 6$ )। यह यह कहने जैसा है कि यदि आप एक पूर्ण 2x2 ब्लॉक और एक पूर्ण 3x3 ब्लॉक बना सकते हैं, तो आप उन्हें एक पूर्ण 6x6 ब्लॉक बनाने के लिए एक के ऊपर एक रख सकते हैं।
सक्सेसर नियम (The Successor Rule): यदि आप 5D डोनट के लिए इसे हल कर सकते हैं, तो आप स्वचालित रूप से 11D डोनट के लिए इसे हल कर सकते हैं (क्योंकि $2 \times 5 + 1 = 11$ )। यह एक नया "जादुई कदम" है जिसे लेखकों ने खोजा है।

महा निष्कर्ष (The Grand Conclusion):
लेखकों ने सिद्ध किया कि यदि आपके पास छोटे, बुनियादी बिल्डिंग ब्लॉक्स (आयाम 2, 3, 5 और 7) के समाधान हैं, तो आप किसी भी आयाम के समाधान को बनाने के लिए इन "प्रोडक्ट" और "सक्सेसर" नियमों का उपयोग कर सकते हैं।

उन्होंने स्वयं आयाम 2 और 3 के लिए बुनियादी बातें सिद्ध कीं।
उन्होंने आयाम 5 और 7 के ज्ञात परिणामों का उपयोग किया।
उन्होंने इन नए नियमों के साथ इन्हें जोड़कर यह सिद्ध किया कि प्रत्येक आयाम में प्रत्येक विषम-आकार का टॉरस एक पूर्ण हैमिल्टन अपघटन (Hamilton decomposition) रखता है।

4. "कंप्यूटर प्रमाण" (The "Computer Proof")

लेखकों ने इसे केवल कागज पर नहीं लिखा; उन्होंने अपने पूरे प्रमाण को लीन (Lean) नामक एक कंप्यूटर प्रोग्राम के कोड में अनुवादित किया। यह एक रेसिपी लिखने जैसा है और फिर एक रोबोट शेफ को हर एक कदम का पालन करने के लिए कहना ताकि यह सुनिश्चित हो सके कि कोई गलती न हो। कंप्यूटर ने सत्यापित किया कि उनका तर्क पूरी तरह से सही है, जिससे उनके "पूर्ण लूप" के दावे पर अतिरिक्त विश्वास पैदा हुआ कि यह 100% सत्य है।

सारांश

संक्षेप में, यह पेपर बहु-आयामी डोनट पर यातायात मार्ग (routing traffic) के बारे में दशकों पुरानी पहेली को हल करता है। यह सिद्ध करता है कि जब तक डोनट में प्रत्येक दिशा में विषम संख्या में स्टॉप (stops) हैं, आप हमेशा सड़कों को इस तरह रंग सकते हैं कि प्रत्येक रंग पूरे शहर का एक पूर्ण, गैर-दोहराव वाला दौरा (tour) बनाता है। उन्होंने दो नई निर्माण विधियों का आविष्कार करके और उन्हें लेगो ब्रिक्स की तरह जोड़ने के तरीके दिखाकर ऐसा किया, जिससे किसी भी आकार के शहर के लिए समाधान बनाया जा सके।

तकनीकी सारांश: विषम माड्यूली (Odd Moduli) पर निर्देशित टोरी के हैमिल्टन विखंडन के लिए एक प्रीफिक्स-काउंट क्लोजर प्रमेय

समस्या विवरण
यह शोध पत्र चक्रों के निर्देशित कार्टेशियन उत्पादों (directed Cartesian products of cycles), विशेष रूप से ओरिएंटेड समान-पक्ष $d$ -टोरस $D_d(m) = \text{Cay}((\mathbb{Z}/m\mathbb{Z})^d, \{e_0, \dots, e_{d-1}\})$ के हैमिल्टन विखंडन की समस्या को संबोधित करता है। एक हैमिल्टन विखंडन के लिए $d|V|$ चापों (arcs) को ठीक $d$ विलगित (disjoint) निर्देशित हैमिल्टन चक्रों में विभाजित करने की आवश्यकता होती है। जबकि इस प्रकार के ग्राफों के लिए हैमिल्टनिसिटी (एक एकल स्पैनिंग चक्र का अस्तित्व) अच्छी तरह से अध्ययन किया गया है, सभी आयामों $d \ge 2$ और विषम माड्यूली $m \ge 3$ के लिए यह अधिक सशक्त आर्क-पार्टिशन (arc-partition) समस्या अनसुलझी रही है। इस शोध पत्र का लक्ष्य यह सिद्ध करना है कि प्रत्येक पूर्णांक $d \ge 2$ और प्रत्येक विषम पूर्णांक $m \ge 3$ के लिए $D_d(m)$ एक निर्देशित हैमिल्टन विखंडन स्वीकार करता है।

कार्यप्रणाली (Methodology)
प्रमाण रणनीति दो प्राथमिक क्लोजर तंत्रों (closure mechanisms) पर निर्भर करती है जो "हल किए गए" आधार आयामों के सेट के आधार पर मनमाने आयामों के लिए विखंडन निर्माण की अनुमति देते हैं। कार्यप्रणाली मॉड्यूलस $m$ और आयाम $d$ के बीच संबंध के आधार पर दो शाखाओं में विभाजित है:

उच्च-माड्यूली गणना शाखा ( $m \ge d$ ):
- रूट-फ्लैट प्रमाणपत्र (Root-Flat Certificates): लेखक एक "रूट-फ्लैट प्रमाणपत्र" पेश करते हैं, जो लेयर सम $S(x) = \sum x_i = 0$ पर परिभाषित एक संरचना है। यह वैश्विक विखंडन समस्या को एक रूट-फ्लैट स्लाइस $A_{d,m}$ पर स्थानीय मानचित्रों (local maps) के निर्माण में कम कर देता है।
- प्रीफिक्स निर्देशांक और वन-लेयर फैक्टराइजेशन: रूट-फ्लैट स्पेस को त्रिकोणीय बाइजेक्शन (triangular bijection) के माध्यम से प्रीफिक्स निर्देशांकों में मैप किया जाता है। विखंडन का निर्माण लेयर-दर-लेयर उन मानचित्रों $M^\sigma_c$ का उपयोग करके किया जाता है जो प्रतीक सेटों $\{0, \Delta, 2, \dots, d-1\}$ के आधार पर प्रीफिक्स निर्देशांकों को क्रमपरिवर्तित (permute) करते हैं।
- प्रीफिक्स-काउंट प्रिमिटिविटी (Prefix-Count Primitivity): एक प्रमुख मानदंड (प्रमेय 4.4) यह सुनिश्चित करता है कि इन लेयर मानचित्रों का संयोजन एक एकल चक्र बनाता है। इसके लिए अनुक्रम में उपयोग किए गए प्रतीकों पर विशिष्ट गणना स्थितियाँ आवश्यक हैं: $\gcd(N_0, m) = 1$ और $k \ge 2$ के लिए $\gcd(N_k - N_\Delta, m) = 1$ ।
- साइंड बाइनरी लेयर्स (Signed Binary Layers): $m \ge d$ (जहाँ $d$ विषम है) के लिए इन गणना शर्तों को संतुष्ट करने हेतु, लेखक "प्रीफिक्स-एडमिसेबल काउंट मैट्रिसेस" का निर्माण करते हैं। $q \ge 2$ (जहाँ $m = (d-1)q + r$ ) के लिए, वे आवश्यक मॉड्यूलर यूनिट्स को बनाए रखते हुए रो (row) और कॉलम (column) योगों को संतुलित करने के लिए deented बाइनरी लेयर्स (एंट्रीज़ $\{-2, -1, 1, 2\}$ वाले मैट्रिक्स) का उपयोग करते हैं। एक अलग मैचिंग करेक्शन प्रतिबंधित मामले $q=1$ को संभालता है।
बेस-टेल मॉड्यूलर-ट्रेड शाखा ( $m < d$ ):
- बेस-टेल लिफ्ट (Base-Tail Lift): जब आयाम के सापेक्ष मॉड्यूल छोटा होता है, तो शोध पत्र एक "बेस-टेल" निर्माण का उपयोग करता है। एक हल किए गए आधार आयाम $b$ (जहाँ $D_b(m)$ विखंडनीय है) को आयाम $T = d-b$ वाली एक पूंछ (tail) के साथ जोड़ा जाता है।
- सिलेंडर विखंडन: बेस मल्टीग्राफ को सिलेंडरों में विभाजित किया जाता है। बेस में सक्रिय चापों को "लोकल सिंबल ट्रेड्स" को शेड्यूल करने के लिए एक टेल अल्फाबेट से प्रतीकों को सौंपा जाता है।
- एक्टिव रेसिड्यू शेड्यूलिंग (Active Residue Scheduling): एक "सिलेंडर ट्रेड रिज़र्वोइर" का उपयोग करते हुए, लेखक रंगों के बीच प्रतीकों के स्थानीय स्वैप (swaps) करने के लिए विशिष्ट वर्टिसेस को आरक्षित करते हैं। यह टेल आयाम के लिए आवश्यक प्रीफिक्स-काउंट प्रिमिटिविटी स्थितियों को संतुष्ट करने के लिए कलर-सिंबल काउंट रेसिड्यूज़ को समायोजित करने की अनुमति देता है, जिससे बेस विखंडन को पूर्ण आयाम $d$ तक लिफ्ट किया जा सके।

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

दो क्लोजर तंत्र: शोध पत्र समाधानित आयामों के सेट $S$ $S$ के लिए दो अलग-अलग क्लोजर नियमों को स्थापित करता है:
- प्रोडक्ट क्लोजर: यदि $a, b \in S$ , तो $ab \in S$ ।
- सक्सेसर क्लोजर: यदि $b \in S$ और $b \ge 5$ , तो $2b + 1 \in S$ ।
उच्च-माड्यूली निर्माण: $d \ge 5$ और $m \ge d$ के लिए एक समान निर्माण, जो किसी भी पूर्व-हल किए गए आधार आयामों से स्वतंत्र, साइन बाइनरी लेयर्स और प्रीफिक्स-काउंट मैट्रिसेस का उपयोग करता है।
बेस-टेल मॉड्यूलर-ट्रेड प्रमेय: एक सामान्य प्रमेय (प्रमेय 1.3) जो $D_d(m)$ को एक हल किए गए बेस $b$ के दिए जाने पर हल करता है, बशर्ते $d$ को $m$ के यूनिट्स के योग में विघटित किया जा सके और विशिष्ट आकार असमानताएं ( $T > b$ और $mb > m \cdot d \cdot T$ ) लागू हों।
औपचारिकीकरण (Formalization): परिणामों को एक लीन फॉर्मलाइजेशन (Lean 4) के साथ प्रस्तुत किया गया है जो ऑल-डायमेंशन थ्योरम और प्रमाण की विशिष्ट निर्भरता संरचना को सत्यापित करता है।

परिणाम
शोध पत्र प्रमेय 1.5 को सिद्ध करता है: प्रत्येक पूर्णांक $d \ge 2$ और प्रत्येक विषम पूर्णांक $m \ge 3$ के लिए, निर्देशित बेस केली टोरस $D_d(m)$ एक निर्देशित हैमिल्टन विखंडन स्वीकार करता है।

प्रमाण एक न्यूनतम आधार आयामों के सेट की पहचान करके आगे बढ़ता है:

आयाम 2 और 3: परिशिष्ट B में सिद्ध (आयाम 2 शास्त्रीय है; आयाम 3 विषम $m$ के लिए सिद्ध है)।
आयाम 5 और 7: उद्धृत बाहरी प्रमेयों ([22], [23]) से प्राप्त।

क्लोजर नियमों का उपयोग करते हुए:

प्रोडक्ट क्लोजर आयाम $4, 6, 8, 9, 10, \dots$ उत्पन्न करता है।
सक्सेसर क्लोजर (बहाव $b=5$ से शुरू होकर) $11$, और तत्पश्चात उच्च विषम आयामों को उत्पन्न करता है।
एक "डायैडिक-ट्रायैडिक इंटरवल-हिटिंग" तर्क (लेम्मा 10.3) यह दर्शाता है कि किसी भी विषम $d \ge 29$ के लिए, एक हल किया गया बेस $b \in \langle 2, 3 \rangle$ मौजूद है जिससे बेस-टेल की शर्तें पूरी होती हैं।
स्ट्रॉन्ग इंडक्शन पुष्टि करता है कि प्रत्येक $d \ge 2$ कवर किया गया है।

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

लेखक प्रमाण की संरचनात्मक प्रकृति पर जोर देते हैं:

यह दो अलग-अलग लेकिन पूरक तंत्रों (काउंट मैट्रिसेस बनाम मॉड्यूलर ट्रेड्स) के माध्यम से उच्च-माड्यूली और निम्न-माड्यूली मामलों को एकीकृत करता है।
यह सभी आयामों की अनंत समस्या को आधार इनपुट (2, 3, 5, 7) के एक परिमित सेट और दो बीजगणितीय क्लोजर ऑपरेशन्स में कम करता है।
मशीन-चेकेबल फॉर्मलाइजेशन का समावेश, विशेष रूप से बेस-टेल शाखा में जटिल गणना और मैचिंग स्थितियों के लिए, एक सत्यापन आर्टिफैक्ट के रूप में कार्य करता है।

यह शोध पत्र सम माड्यूली या गैर-समान-पक्ष टोरी के लिए समस्या को हल करने का दावा नहीं करता है, न ही इस विशिष्ट विखंडन समस्या के परे नए अनुप्रयोग प्रस्तावित करता है। इसका महत्व निर्दिष्ट ग्राफ वर्ग के लिए पूर्णता और प्रदान किए गए कठोर गणितीय सत्यापन में निहित है।