The lonely runner conjecture holds for nine runners

तकनीकी सारांश: नौ धावकों के लिए लोनली रनर कंजेक्चर (The Lonely Runner Conjecture for Nine Runners)

समस्या विवरण
यह शोध पत्र 'लोनली रनर कंजेक्चर' (Lonely Runner Conjecture) को संबोधित करता है, जो कॉम्बिनेटोरियल नंबर थ्योरी (combinatorial number theory) की एक लंबे समय से चली आ रही खुली समस्या है, जिसे सर्वप्रथम विल्स (Wills) द्वारा 1967 में प्रस्तावित किया गया था। यह अनुमान (conjecture) यह प्रतिपादित करता है कि किसी भी पूर्णांक $k \ge 1$ और $k$ अलग-अलग पूर्णांकों के किसी भी सेट (जो धावकों की गति $v_1, \dots, v_k$ को दर्शाते हैं) के लिए, एक वास्तविक समय $t$ मौजूद होता है जब प्रत्येक धावक "अकेला" (lonely) होता है। गणितीय रूप से, इसका अर्थ है कि एक ऐसा $t$ मौजूद है जहाँ यूनिट सर्कल पर प्रत्येक धावक की मूल बिंदु (origin) से दूरी कम से कम $1/(k+1)$ होती है, जिसे $\|t v_i\| \ge 1/(k+1)$ के रूप में व्यक्त किया जाता है।

यद्यपि इस अनुमान की $k$ के छोटे मानों (जैसे $k=7$ तक) के लिए पुष्टि की जा चुकी है, लेकिन सामान्य मामले में यह अभी भी खुला प्रश्न बना हुआ है। यह शोध पत्र विशेष रूप से नौ धावकों ($k=9$) के मामले को लक्षित करता है।

कार्यप्रणाली (Methodology)
प्रमाण की रणनीति लेखक के आठ धावकों के लिए स्थापित पिछले कार्य पर आधारित है। मुख्य तर्क एक काल्पनिक "न्यूनतम प्रति-उदाहरण" (minimal counterexample) के गुणों से जुड़े विरोधाभास द्वारा प्रमाण (proof by contradiction) पर निर्भर करता है।

1. विभाज्यता बाधाओं में न्यूनीकरण (Reduction to Divisibility Constraints):
   प्रमाण मलिकियोसिस, सैंटोस और श्मिमुरा (थ्योरम 1) द्वारा प्राप्त एक सीमा का उपयोग करता है, जो यह बताता है कि यदि कंजलचर $k$ के लिए सत्य है, तो यह $k+1$ के लिए भी सत्य होगा, बशर्ते कि किसी भी न्यूनतम प्रति-उदाहरण में गतियों का गुणनफल एक विशिष्ट सीमा से अधिक हो। फलस्वरूप, $k+1$ के लिए कंजलचर को सिद्ध करने के लिए, यह दिखाना पर्याप्त है कि ऐसी $k$ गतियों का कोई सेट मौजूद नहीं है जो निर्धारित विभाज्यता बाधाओं को पूरा करते हुए "लोनली रनर प्रॉपर्टी" (LR property) का उल्लंघन करता हो।

2. भाजकों के लिए सामान्यीकृत लेम्मा (Generalized Lemma for Divisors):
   लेखक एक लेम्मा 6 पेश करते हैं, जो पिछले लेम्मा (लेम्मा 3) का एक सुदृढ़ और सामान्यीकृत संस्करण है। यह लेम्मा स्थापित करता है कि एक विशिष्ट पूर्णांक $d$ उन 8 पूर्णांकों के गति गुणनफल को विभाजित करेगा जिनका सेट LR प्रॉपर्टी प्रदर्शित नहीं करता है।

• लेम्मा एक गुणांक $c$ पेश करता है और $9cd$ मॉड्युलो (modulo) पर गतियों पर विचार करता है।
• इसमें 3 और 9 से विभाज्य गतियों की संख्या के संबंध में विशिष्ट विभाज्यता शर्तों को शामिल किया गया है (जो लेम्मा 5 से व्युत्पन्न है)।
• शर्त के लिए यह सत्यापित करना आवश्यक है कि विशिष्ट GCD और विभाज्यता बाधाओं को पूरा करने वाले 8 गतियों के किसी भी सेट के लिए, LR प्रॉपर्टी को संतुष्ट करने वाला एक समय $t$ मौजूद है।

3. कंप्यूटर-सहायता प्राप्त सत्यापन (सेट कवर पुनर्गठन):
   लेम्मा 6 की शर्तों को सत्यापित करना गणनात्मक रूप से गहन है। लेखक इसे एक सेट कवर (set cover) समस्या के रूप में पुनर्गठित करते हैं (लेम्मा 7)।

• एक पूर्णांक $v$, पूर्णांक $j$ को "कवर" करता है यदि $\| \frac{jv}{9cd} \| < 1/8$ हो।
• लक्ष्य यह सत्यापित करना है कि कोई भी "खराब" 8-टुपल (8-tuple) मौजूद नहीं है जो आवश्यक पूर्णांकों को कवर करता हो और साथ ही विभाज्यता बाधाओं को पूरा करता हो।
• लेखकों ने अपने पिछले $k=7$ के कार्य पर महत्वपूर्ण अनुकूलन के साथ एक बैकट्रैकिंग एल्गोरिदम लागू किया:
  • कवर किए गए स्थानों के लिए प्रीकंप्यूटेड बिटसेट्स (bitsets) का उपयोग।
  • एक संभावित तत्व द्वारा कवर किए जा सकने वाले नए पूर्णांकों की अधिकतम संख्या के आधार पर प्रूनिंग (pruning) रणनीतियाँ।
  • रेडंडेंट सर्च पाथ्स (redundant search paths) को समाप्त करने के लिए मेमोइज़ेशन (memoization)।
• लेखकों ने SAT-सॉल्वर दृष्टिकोणों (Cardinality-CDCL और Minicard का उपयोग करके) का भी परीक्षण किया लेकिन पाया कि वे इस विशिष्ट समस्या संरचना के लिए उनके कस्टम बैकट्रैकिंग कार्यान्वयन की तुलना में काफी धीमे थे।

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

• नौ धावकों के लिए प्रमाण: शोध पत्र पूर्ण प्रमाण प्रदान करता है कि नौ धावकों के लिए लोनली रनर कंजलचर सत्य है।
• भाजकों की पहचान: एक कंप्यूटर प्रोग्राम के माध्यम से लेम्मा 6 को लागू करके, लेखकों ने पूर्णांकों के एक सेट $S$ की पहचान की (जिसमें $64, 81, 25$ जैसे प्राइम पावर और 191 तक के अभाज्य संख्याएँ शामिल हैं) जो 9 धावकों के किसी भी न्यूनतम प्रति-उदाहरण में गतियों के गुणनफल को विभाजित करते हैं।
• विरोधाभास: सेट $S$ के तत्वों का गुणनफल (जो एक दूसरे के सह-अभाज्य/coprime हैं) लगभग $9.09 \times 10^{79}$ है। हालाँकि, एक न्यूनतम प्रति-उदाहरण में गतियों के गुणनफल के लिए सैद्धांतिक ऊपरी सीमा (कोरोलरी 2 से व्युत्पन्न) लगभग $8.47 \times 10^{79}$ है। चूँकि आवश्यक विभाजकों का गुणनफल गतियों के अधिकतम संभव गुणनफल से अधिक है, इसलिए ऐसा कोई प्रति-उदाहरण अस्तित्व में नहीं हो सकता।
• एल्गोरिदम में सुधार: शोध पत्र एक विशिष्ट कार्यान्वयन विवरण देता है जिसने $k=7$ सत्यापन के लिए रनटाइम को 32 घंटों से घटाकर 50 मिनट कर दिया, जिससे अधिक जटिल $k=9$ सत्यापन संभव हो सका।

महत्व और दावे
लेखक कहते हैं कि यह परिणाम ज्ञात सीमा को 7 से बढ़ाकर 9 धावकों तक विस्तृत करता है। वे नोट करते हैं कि उपयोग की गई तकनीक सैद्धांतिक रूप से धावकों की किसी भी विशिष्ट संख्या के लिए लागू की जा सकती है, हालांकि गणनात्मक लागत तेजी से बढ़ती है।

• स्वतंत्रता: लेखक स्वीकार करते हैं कि ट्रैकुलथोंगचाई (Trakulthongchai) ने इस सबमिशन से कुछ समय पहले $k=9$ और $k=10$ के प्रमाण स्वतंत्र रूप से घोषित किए थे। ट्रैकुलथोंगचाई का कार्य भी $k=7$ के प्रमाण पर आधारित है और एक "चतुर सीविंग दृष्टिकोण" (clever sieving approach) का उपयोग करता है जो यहाँ प्रस्तुत विधि की तुलना में लगभग 100 गुना तेज़ प्रतीत होता है।
• भविष्य की रूपरेखा: शोध पत्र $k=10$ तक विस्तार करने की व्यवहार्यता पर चर्चा करता है। यद्यपि विधि अनुकूलनीय है, लगभग 263 तक की अभाज्य संख्याओं को सत्यापित करने के लिए अनुमानित गणनात्मक लागत एक सिंगल कोर पर दो वर्ष का समय ले सकती है। लेखक सुझाव देते हैं कि उनके सुधारों (जैसे छोटे प्राइम की घातों पर विचार करना) को ट्रैकुलथोंगचाई के सीविंग दृष्टिकोण के साथ मिलाने से $k=10$ का मामला अधिक सुलभ हो सकता है, लेकिन वे स्वयं इसे हल करने का दावा नहीं करते हैं।

संक्षेप में, यह शोध पत्र परिष्कृत सैद्धांतिक लेम्मा और अत्यधिक अनुकूलित कंप्यूटर सत्यापन के संयोजन के माध्यम से $k=9$ के मामले को सफलतापूर्वक हल करता है, और विनम्रतापूर्वक अपने कार्य को उच्च $k$ के लिए कंजलचर को हल करने के व्यापक प्रयास में एक कदम के रूप में प्रस्तुत करता है।