Lonely runner conjecture
संख्या सिद्धांत में, विशेष रूप से डायोफैंटाइन सन्निकटन के अध्ययन में, अकेला धावक अनुमान एक गोलाकार ट्रैक पर धावकों के दीर्घकालिक व्यवहार के बारे में एक अनुमान है। इसमें कहा गया है कि इकाई लंबाई के ट्रैक पर दौड़ने वाले, एक दूसरे से अलग गति के साथ, प्रत्येक किसी न किसी समय अकेले होंगे-कम से कम अन्य सभी से इकाइयों की दूरी पर। यह अनुमान पहली बार 1967 में जर्मन गणितशास्त्री जोर्ग एम. विल्स द्वारा विशुद्ध रूप से संख्या-सैद्धांतिक शब्दों में और स्वतंत्र रूप से 1974 में टी. डब्ल्यू. कुसिक द्वारा प्रस्तुत किया गया था; इसका सचित्र और अब लोकप्रिय सूत्रीकरण 1998 का है। अनुमान 7 या उससे कम धावकों के लिए सही माना जाता है, लेकिन सामान्य मामला अनसुलझा रहता है। अनुमान के प्रभावों में दृश्य-बाधा समस्याओं का समाधान और कुछ ग्राफों के वर्णात्मक संख्याओं से संबंधित गुणों पर सीमाएं शामिल हैं। सूत्रीकरण इकाई लंबाई के वृत्ताकार पथ पर धावकों पर विचार करें। प्रारंभिक समय में, सभी धावक एक ही स्थिति में होते हैं और दौड़ना शुरू करते हैं; धावकों की गति स्थिर होती है, सभी अलग-अलग होती है, और नकारात्मक हो सकती है। एक धावक को उस समय अकेला कहा जाता है जब वह कम से कम हर दूसरे धावक से दूरी (वृत्त के साथ मापा जाता है) पर होता है। एकल धावक अनुमान में कहा गया है कि प्रत्येक धावक किसी न किसी समय अकेला होता है, चाहे गति का चुनाव कुछ भी हो। अनुमान का यह दृश्य सूत्रीकरण पहली बार 1998 में प्रकाशित हुआ था। जोर्ग एम. विल्स द्वारा मूल सहित कई सूत्रीकरणों में कुछ सरलीकरण किए गए हैं। एकल धावक 0 (शून्य गति के साथ) पर स्थिर होता है, और इसलिए गैर-शून्य गति वाले अन्य धावकों को माना जाता है। चलने वाले धावकों को केवल सकारात्मक गति तक ही सीमित किया जा सकता हैः समरूपता द्वारा, गति वाले धावक और हर समय 0 से समान दूरी रखते हैं, और इसलिए अनिवार्य रूप से बराबर होते हैं। किसी भी स्थिर धावक के लिए परिणाम साबित करने का तात्पर्य सभी धावकों के लिए सामान्य परिणाम से है, क्योंकि उन्हें सभी धावकों से उनकी गति को घटाकर स्थिर बनाया जा सकता है, जिससे वे शून्य गति के साथ रह सकते हैं। अनुमान तब कहता है कि, सकारात्मक, विशिष्ट गति के किसी भी संग्रह के लिए, कुछ समय ऐसा मौजूद होता है कि जहां के आंशिक भाग को दर्शाता है। यदि धावक घड़ी की विपरीत दिशा में दौड़ रहे हैं, तो असमानता का मध्य पद मूल से th धावक तक की दूरी है, जिसे घड़ी की विपरीत दिशा में मापा जाता है। इस परंपरा का उपयोग इस लेख के शेष भाग के लिए किया गया है। विल्स का अनुमान डायोफैंटाइन सन्निकटन में उनके काम का हिस्सा था, यह अध्ययन कि अंश अपरिमेय संख्याओं को कितनी बारीकी से अनुमानित कर सकते हैं। प्रभाव मान लीजिए कि-आयामी स्थान () में पार्श्व लंबाई का एक-हाइपरक्यूब है। प्रत्येक बिंदु पर अर्ध-पूर्णांक निर्देशांक के साथ एक केंद्रित प्रति रखें। मूल से एक किरण या तो सभी प्रतियों से चूक सकती है, जिस स्थिति में एक (असीम) अंतराल होता है, या कम से कम एक प्रति हिट हो सकती है। इस संदर्भ में एकल धावक अनुमान का एक स्वतंत्र सूत्रीकरण किया गया; अनुमान का तात्पर्य है कि अंतराल हैं यदि और केवल तभी, समन्वय हाइपरप्लेन में से एक में पड़ी किरणों की अनदेखी करते हुए। उदाहरण के लिए, 2-आयामी स्थान में रखे गए, पार्श्व लंबाई से छोटे वर्ग अंतराल छोड़ देंगे, जैसा कि दिखाया गया है, और पार्श्व लंबाई या उससे अधिक वाले वर्ग प्रत्येक किरण को बाधित करेंगे जो एक अक्ष के समानांतर नहीं है। अनुमान इस अवलोकन को किसी भी संख्या में आयामों में सामान्यीकृत करता है। ग्राफ सिद्धांत में, पूर्णांकों के सेट पर एक दूरी ग्राफ, और सकारात्मक पूर्णांक दूरी के कुछ सीमित सेट का उपयोग करते हुए, यदि और केवल यदि के बीच एक किनारा होता है। उदाहरण के लिए, यदि सम पूर्णांकों और विषम पूर्णांकों की प्रत्येक क्रमिक जोड़ी निकटवर्ती है, तो सभी मिलकर दो जुड़े हुए घटक बनाते हैं। चरण के साथ पूर्णांकों का एक-नियमित रंग प्रत्येक पूर्णांक को मॉड्यूलो के अवशेष के आधार पर रंगों में से एक निर्धारित करता है। उदाहरण के लिए, यदि रंग प्रत्येक पूर्णांक को दोहराता है और पूर्णांकों की प्रत्येक जोड़ी एक ही रंग की होती है। इसे लेते हुए, एकल धावक अनुमान का तात्पर्य है कि कुछ चरण मूल्य के लिए एक उचित-नियमित रंग (यानी, प्रत्येक नोड अपनी निकटताओं से अलग रंग का होता है) को स्वीकार करता है। उदाहरण के लिए, द्वारा उत्पन्न दूरी ग्राफ पर एक उचित रंग उत्पन्न करता है। (इसे नियमित क्रोमेटिक संख्या के रूप में जाना जाता है।) एक निर्देशित ग्राफ को देखते हुए, एक शून्य-शून्य प्रवाह प्रत्येक किनारे के लिए एक सकारात्मक मान देता है, जैसे कि प्रत्येक नोड से बाहर की ओर प्रवाह अंदर की ओर प्रवाह के बराबर होता है। एकाकी धावक अनुमान का तात्पर्य है कि, यदि अधिकांश विशिष्ट पूर्णांक मानों के साथ कहीं-शून्य प्रवाह है, तो केवल मानों के साथ कहीं-शून्य प्रवाह है (संभवतः कुछ चापों की दिशाओं को उलटने के बाद)। यह परिणाम अलग-अलग तरीकों से सिद्ध किया गया था, और क्योंकि एकाकी धावक अनुमान के छोटे मामलों का निपटारा किया जाता है, इसलिए पूर्ण प्रमेय सिद्ध होता है। ज्ञात परिणाम धावकों की दी गई व्यवस्था के लिए, धावकों की अकेलेपन की अधिकतम दूरी में से सबसे छोटी दूरी को दर्शाते हैं, और अकेलेपन का अंतर धावकों के साथ सभी व्यवस्थाओं में न्यूनतम को दर्शाता है। इस संकेतन में, अनुमान इस बात पर जोर देता है कि, एक ऐसी सीमा जिसे, यदि सही है, तो सुधार नहीं किया जा सकता है। उदाहरण के लिए, यदि अकेला रहने वाला धावक स्थिर है और गति का चयन किया जाता है, तो ऐसा कोई समय नहीं है जब वे अन्य सभी से इकाइयों से सख्ती से अधिक दूर हों, जो यह दर्शाता है। वैकल्पिक रूप से, इस निष्कर्ष को डिरिचलेट सन्निकटन प्रमेय से जल्दी से प्राप्त किया जा सकता है। एक साधारण निचली सीमा के लिए एक संभाव्यता तर्क के माध्यम से प्राप्त किया जा सकता है। अनुमान को धावकों की गति को सकारात्मक पूर्णांक तक सीमित करने के लिए कम किया जा सकता हैः यदि अनुमान पूर्णांक गति वाले धावकों के लिए सही है, तो यह वास्तविक गति वाले धावकों के लिए सही है। सख्त सीमाएँ निचली सीमा पर थोड़ा सुधार ज्ञात हैं। उसके लिए दिखाया गया है कि यदि अभाज्य है, तो, और यदि अभाज्य है, तो। पर्याप्त रूप से बड़े के लिए बिना शर्त दिखाया गया जो वर्तमान सबसे प्रसिद्ध एसिम्प्टोटिक परिणाम साबित करता हैः पर्याप्त रूप से बड़े के लिए, कुछ स्थिरांक के लिए। उन्होंने यह भी दिखाया कि पूर्ण अनुमान आकार की पूर्णांक गति के लिए अनुमान को साबित करके निहित है (बड़े ओ संकेतन देखें)। यह निहितार्थ सैद्धांतिक रूप से मामलों के एक सीमित समूह की जांच करके दिए गए अनुमान को साबित करने की अनुमति देता है, लेकिन मामलों की संख्या व्यावहारिक होने के लिए बहुत जल्दी बढ़ती है। यह अनुमान धावकों की गति पर विशिष्ट धारणाओं के तहत साबित हुआ है। पर्याप्त रूप से बड़े के लिए, यह सच है यदि दूसरे शब्दों में, अनुमान बड़े के लिए सच है यदि गति तेजी से बढ़ती है। यदि स्थिरांक 22 को 33 से प्रतिस्थापित किया जाता है, तो अनुमान के लिए सही है। पर्याप्त रूप से बड़े के लिए एक समान परिणाम के लिए केवल एक समान धारणा की आवश्यकता होती है। बिना शर्त, अनुमान यदि सभी के लिए सच है। विशिष्ट रूप से अनुमान धावकों के लिए सही है। सबूत प्राथमिक हैं; मामला 1972 में स्थापित किया गया था। , और मामलों का निपटारा क्रमशः 1984,2001 और 2008 में किया गया था। इसका पहला प्रमाण कंप्यूटर-सहायता प्राप्त था, लेकिन तब से सभी मामले प्रारंभिक तरीकों से साबित हुए हैं। कुछ लोगों के लिए, ऊपर दिए गए उदाहरण के अलावा अधिकतम पृथक्करण के साथ छिटपुट उदाहरण मौजूद हैं। क्योंकि, एकमात्र ज्ञात उदाहरण (शिफ्ट और स्केलिंग तक) है; क्योंकि एकमात्र ज्ञात उदाहरण है; और ज्ञात उदाहरणों के लिए हैं और। इस तरह के छिटपुट मामलों का एक स्पष्ट अनंत परिवार मौजूद है। अनुमान का एक तेज संस्करण तैयार किया जो निकट-समानता के मामलों को संबोधित करता है। अधिक विशेष रूप से, वह अनुमान लगाता है कि गति के एक दिए गए सेट के लिए, या तो कुछ सकारात्मक पूर्णांक के लिए, या, उस सेटअप के अकेलेपन का अंतर कहाँ है। उन्होंने कुछ विशेष मामलों के लिए इस अनुमान की पुष्टि की। एक धावक के अकेले होने के लिए आवश्यक समय के आकार के प्रश्न को संबोधित किया। उन्होंने यह कहते हुए एक मजबूत अनुमान तैयार किया कि प्रत्येक पूर्णांक के लिए एक सकारात्मक पूर्णांक होता है जैसे कि सकारात्मक, विशिष्ट गति के किसी भी संग्रह के लिए, कुछ समय ऐसा होता है कि रिफफोर्ड के साथ इस अनुमान की पुष्टि की और दिखाया कि प्रत्येक मामले में न्यूनतम के लिए और के लिए दिया जाता है। बाद के परिणाम (के लिए) से पता चलता है कि यदि हम छह धावकों को समय पर स्थिर गति के साथ और विशिष्ट और सकारात्मक के साथ शुरू करने पर विचार करते हैं तो स्थिर धावक को सबसे धीमे गैर-स्थिर धावक (लेकिन पहले दौर के दौरान आवश्यक नहीं) के पहले दो दौरों के दौरान कम से कम दूसरों से दूरी से अलग किया जाता है। अन्य परिणाम यादृच्छिक रूप से चुनी गई गति के लिए एक बहुत मजबूत परिणाम मौजूद हैः स्थिर-धावक परंपरा का उपयोग करते हुए, यदि और स्थिर हैं और गैर-शून्य गति वाले धावकों को यादृच्छिक रूप से समान रूप से चुना जाता है, तो जैसे। दूसरे शब्दों में, यादृच्छिक गति वाले धावक किसी बिंदु पर "बहुत अकेले" होने की संभावना रखते हैं-निकटतम अन्य धावक से लगभग इकाइयाँ। पूरा अनुमान सही है यदि "अकेलेपन" को "लगभग अकेलेपन" से बदल दिया जाता है, जिसका अर्थ है कि अधिक से अधिक एक अन्य धावक किसी दिए गए धावक के भीतर है। इस अनुमान को बीजगणितीय फलन क्षेत्रों में एक अनुरूप के रूप में सामान्यीकृत किया गया है। नोट्स और संदर्भ नोट्स साइटेशन वर्क्स ने ओपन प्रॉब्लम गार्डन नं. में बाहरी लिंक लेख का हवाला दिया। 4, 551-562। डायोफैंटाइन समीकरण संख्या सिद्धांत में अनसुलझी समस्याओं का अनुमान लगाते हैं