Lonely runner conjecture
نمبر تھیوری میں، خاص طور پر ڈیوفنٹائن تخمینہ کے مطالعہ میں، تنہا رنر قیاس آرائی ایک سرکلر ٹریک پر رنرز کے طویل مدتی رویے کے بارے میں ایک قیاس ہے۔ اس میں کہا گیا ہے کہ یونٹ لمبائی کے ٹریک پر دوڑنے والے، مستقل رفتار کے ساتھ ایک دوسرے سے الگ ہوتے ہیں، ہر ایک کسی نہ کسی وقت تنہا رہے گا-کم از کم دوسرے تمام سے یونٹ دور۔ یہ قیاس سب سے پہلے 1967 میں جرمن ریاضی دان جورگ ایم ولز نے خالصتا نمبر تھیوریٹک اصطلاحات میں پیش کیا تھا، اور آزادانہ طور پر 1974 میں ٹی ڈبلیو کوسک نے پیش کیا تھا۔ اس کی مثالی اور اب مقبول تشکیل 1998 کی ہے۔ قیاس 7 یا اس سے کم رنرز کے لیے درست معلوم ہوتا ہے، لیکن عمومی معاملہ حل نہیں ہوا ہے۔ قیاس آرائی کے اثرات میں دیکھنے میں رکاوٹ کے مسائل کا حل اور مخصوص گرافوں کے کرومیٹک نمبروں سے متعلق خصوصیات پر حدود شامل ہیں۔ تشکیل اکائی کی لمبائی کے سرکلر ٹریک پر دوڑنے والوں پر غور کریں۔ ابتدائی وقت میں، تمام دوڑنے والے ایک ہی پوزیشن پر ہوتے ہیں اور دوڑنا شروع کر دیتے ہیں۔ دوڑنے والوں کی رفتار مستقل ہوتی ہے، سب الگ ہوتی ہے، اور منفی ہو سکتی ہے۔ ایک رنر کو وقت پر تنہا کہا جاتا ہے اگر وہ کم از کم ہر دوسرے رنر سے فاصلے (دائرے کے ساتھ ماپا جاتا ہے) پر ہو۔ تنہا رنر کا قیاس یہ ہے کہ ہر رنر کسی نہ کسی وقت تنہا ہوتا ہے، چاہے رفتار کا انتخاب کچھ بھی ہو۔ قیاس کی یہ بصری تشکیل پہلی بار 1998 میں شائع ہوئی تھی۔ بہت سی فارمولیشنوں میں، جن میں جارگ ایم ولز کا اصل بھی شامل ہے، کچھ آسانیاں کی گئی ہیں۔ تنہا ہونے والا رنر 0 (صفر رفتار کے ساتھ) پر ساکن ہوتا ہے، اور اس لیے غیر صفر رفتار والے دوسرے رنرز کو سمجھا جاتا ہے۔ حرکت کرنے والے رنرز کو مزید صرف مثبت رفتار تک محدود کیا جا سکتا ہے: ہم آہنگی کے ذریعے، رفتار والے رنرز اور ہر وقت 0 سے یکساں فاصلہ رکھتے ہیں، اور اس لیے وہ بنیادی طور پر مساوی ہوتے ہیں۔ کسی بھی اسٹیشنری رنر کے لیے نتیجہ ثابت کرنے سے تمام رنرز کے لیے عمومی نتیجہ ظاہر ہوتا ہے، کیونکہ انہیں تمام رنرز سے ان کی رفتار گھٹا کر اسٹیشنری بنایا جا سکتا ہے، جس سے ان کی رفتار صفر رہ جاتی ہے۔ قیاس اس کے بعد بیان کرتا ہے کہ، مثبت، الگ رفتار کے کسی بھی مجموعہ کے لیے، کچھ وقت ایسا موجود ہوتا ہے کہ جہاں کا فریکشنل حصہ ظاہر ہوتا ہے۔ بصری طور پر تشریح کی گئی ہے، اگر رنر گھڑی کی مخالف سمت میں دوڑ رہے ہیں، تو عدم مساوات کی درمیانی مدت اصل سے ویں رنر تک کا فاصلہ ہے، جسے گھڑی کی مخالف سمت میں ماپا جاتا ہے۔ یہ روایت اس مضمون کے بقیہ حصے کے لیے استعمال کی گئی ہے۔ ولز کا قیاس ڈیوفنٹائن تخمینہ میں ان کے کام کا حصہ تھا، اس بات کا مطالعہ کہ فریکشن غیر معقول نمبروں کا کتنا قریب سے تخمینہ لگا سکتے ہیں۔ مضمرات فرض کریں کہ-جہتی جگہ () میں سائیڈ لمبائی کا ایک-ہائپر کیوب ہے۔ نصف عدد کوآرڈینیٹس کے ساتھ ہر نقطہ پر کی ایک مرکزی کاپی رکھیں۔ اصل سے آنے والی کرن یا تو اس کی تمام کاپیاں چھوٹ سکتی ہے، ایسی صورت میں ایک (لامحدود) خلا ہوتا ہے، یا کم از کم ایک کاپی مار سکتی ہے۔ اس سیاق و سباق میں تنہا رنر قیاس کی ایک آزاد تشکیل کی گئی ؛ قیاس کا مطلب یہ ہے کہ اگر اور صرف اس صورت میں خلا موجود ہیں، تو مربوط ہائپرپلین میں سے کسی ایک میں پڑنے والی کرنوں کو نظر انداز کریں۔ مثال کے طور پر، دو جہتی خلا میں رکھے گئے، اطراف کی لمبائی سے چھوٹے مربع خلا چھوڑ دیں گے، جیسا کہ دکھایا گیا ہے، اور اطراف کی لمبائی یا اس سے زیادہ والے مربع ہر ایسی کرن کو روک دیں گے جو محور کے متوازی نہیں ہے۔ قیاس اس مشاہدے کو کسی بھی تعداد میں جہتوں میں عام کرتا ہے۔ گراف تھیوری میں، انٹیجرز کے سیٹ پر ایک فاصلہ گراف، اور مثبت انٹیجر فاصلے کے کچھ محدود سیٹ کا استعمال کرتے ہوئے، اگر اور صرف اگر کے درمیان ایک کنارے رکھتا ہے۔ مثال کے طور پر، اگر، یکساں عددوں کا ہر مسلسل جوڑا، اور عجیب عددوں کا، ملحقہ ہے، تو سب مل کر دو جڑے ہوئے اجزاء بناتے ہیں۔ مرحلہ کے ساتھ انٹیجرز کا باقاعدہ رنگ ہر انٹیجر کو ماڈیولو کے بقیہ کی بنیاد پر رنگوں میں سے ایک تفویض کرتا ہے۔ مثال کے طور پر، اگر رنگ ہر عدد کو دہراتا ہے اور عدد کا ہر جوڑا ایک ہی رنگ کا ہوتا ہے۔ لینے سے، تنہا رنر قیاس کا مطلب ہے کہ کسی قدم کی قیمت کے لیے ایک مناسب-باقاعدہ رنگ (یعنی، ہر نوڈ اس کے ملحقہ حصوں سے مختلف رنگ کا ہوتا ہے) کو تسلیم کرتا ہے۔ مثال کے طور پر، اس سے پیدا ہونے والے فاصلے کے گراف پر ایک مناسب رنگ پیدا ہوتا ہے۔ (باقاعدہ کرومیٹک نمبر کے طور پر جانا جاتا ہے۔) ایک ہدایت شدہ گراف کو دیکھتے ہوئے، ہر کنارے پر کہیں بھی صفر کا بہاؤ ایک مثبت قدر کو جوڑتا ہے، اس طرح کہ ہر نوڈ سے باہر کی طرف بہاؤ اندر کی طرف بہاؤ کے برابر ہوتا ہے۔ لونلی رنر قیاس کا مطلب یہ ہے کہ، اگر زیادہ تر الگ الگ انٹیجر ویلیوز کے ساتھ کہیں صفر کا بہاؤ ہے، تو اس میں کہیں صفر کا بہاؤ ہوتا ہے جس میں صرف ان ویلیوز ہوتی ہیں (ممکنہ طور پر کچھ آرکس کی سمتوں کو الٹنے کے بعد)۔ یہ نتیجہ الگ الگ طریقوں سے ثابت ہوا، اور چونکہ لونلی رنر قیاس کے چھوٹے معاملات طے ہو جاتے ہیں، اس لیے مکمل نظریہ ثابت ہوتا ہے۔ معلوم نتائج دوڑنے والوں کے دیئے گئے سیٹ اپ کے لیے، دوڑنے والوں کے اکیلے پن کے زیادہ سے زیادہ فاصلے میں سے سب سے چھوٹے کو ظاہر کریں، اور تنہائی کا فرق دوڑنے والوں کے ساتھ تمام سیٹ اپس میں کم سے کم کو ظاہر کرتا ہے۔ اس اشارے میں، قیاس اس بات پر زور دیتا ہے کہ، ایک باؤنڈ جسے، اگر درست ہے، تو بہتر نہیں کیا جا سکتا۔ مثال کے طور پر، اگر تنہا رہنے والا رنر مستحکم ہے اور رفتار کا انتخاب کیا جاتا ہے، تو ایسا کوئی وقت نہیں ہے جس پر وہ دوسروں سے اکائیوں سے سختی سے زیادہ دور ہوں، یہ ظاہر کرتا ہے۔ متبادل طور پر، یہ نتیجہ فوری طور پر ڈیرچلیٹ اپروکسیمیشن تھیوریم سے اخذ کیا جا سکتا ہے۔ ایک سادہ نچلی حد کے لیے امکان کی دلیل کے ذریعے حاصل کیا جا سکتا ہے۔ قیاس آرائی کو رنرز کی رفتار کو مثبت عدد تک محدود کرنے کے لیے کم کیا جا سکتا ہے: اگر قیاس عدد رفتار والے رنرز کے لیے درست ہے، تو یہ حقیقی رفتار والے رنرز کے لیے درست ہے۔ سخت حدود نچلی حد پر ہلکی بہتری معلوم ہے۔ اس کے لیے دکھایا گیا ہے کہ اگر پرائم ہے، تو، اور اگر پرائم ہے، تو۔ کافی بڑے کے لیے غیر مشروط طور پر دکھایا گیا جس نے موجودہ سب سے مشہور غیر علامتی نتیجہ ثابت کیا: کافی بڑے کے لیے، کچھ مستقل کے لیے۔ انہوں نے یہ بھی دکھایا کہ مکمل قیاس آرائی کا مطلب سائز کی عدد رفتار کے قیاس کو ثابت کرنا ہے (بگ او نوٹیشن دیکھیں)۔ یہ مضمرات نظریاتی طور پر معاملات کے ایک محدود سیٹ کی جانچ کرکے دیئے گئے قیاس کو ثابت کرنے کی اجازت دیتا ہے، لیکن معاملات کی تعداد عملی ہونے کے لیے بہت تیزی سے بڑھتی ہے۔ یہ قیاس دوڑنے والوں کی رفتار پر مخصوص مفروضوں کے تحت ثابت ہوا ہے۔ کافی بڑے کے لیے، یہ درست ہے اگر دوسرے لفظوں میں، قیاس بڑے کے لیے درست ہے اگر رفتار کافی تیزی سے بڑھتی ہے۔ اگر مستقل 22 کو 33 سے تبدیل کر دیا جائے تو قیاس درست ہے۔ کافی بڑے کے لیے اسی طرح کے نتیجے کے لیے صرف اسی طرح کے مفروضے کی ضرورت ہوتی ہے۔ غیر مشروط طور پر، قیاس اگر سب کے لیے درست ہے۔ خاص طور پر قیاس دوڑنے والوں کے لیے درست ہے۔ ثبوت ابتدائی ہیں ؛ یہ مقدمہ 1972 میں قائم کیا گیا تھا۔ ،، اور مقدمات بالترتیب 1984، 2001 اور 2008 میں نمٹائے گئے۔ اس کا پہلا ثبوت کمپیوٹر کی مدد سے تھا، لیکن اس کے بعد سے تمام معاملات ابتدائی طریقوں سے ثابت ہوئے ہیں۔ کچھ کے لیے، اوپر دی گئی مثال کے علاوہ زیادہ سے زیادہ علیحدگی کے ساتھ وقفے وقفے سے مثالیں موجود ہیں۔ کیونکہ، واحد معروف مثال (شفٹ اور اسکیلنگ تک) ہے ؛ کیونکہ واحد معروف مثال ہے ؛ اور معروف مثالوں کے لیے ہیں اور۔ اس طرح کے چھٹپٹ معاملات کا ایک واضح لامحدود خاندان موجود ہے۔ قیاس آرائی کا ایک تیز تر ورژن وضع کیا جو قریب مساوات کے معاملات کو حل کرتا ہے۔ مزید خاص طور پر، وہ قیاس کرتا ہے کہ رفتار کے دیئے گئے سیٹ کے لیے، یا تو کسی مثبت عدد کے لیے، یا، اس سیٹ اپ کا تنہائی کا فرق کہاں ہے۔ انہوں نے چند خصوصی معاملات کے لیے اس قیاس کی تصدیق کی۔ دوڑنے والے کے تنہا ہونے کے لیے درکار وقت کے سائز کے سوال پر توجہ دی۔ انہوں نے ایک مضبوط قیاس تیار کیا جس میں کہا گیا ہے کہ ہر عدد کے لیے ایک مثبت عدد اس طرح ہوتا ہے کہ مثبت، الگ رفتار کے کسی بھی مجموعے کے لیے کچھ وقت ایسا موجود ہوتا ہے کہ ریففورڈ کے ساتھ اس قیاس کی تصدیق کی اور ظاہر کیا کہ ہر معاملے میں کم سے کم کے لیے اور کے ذریعے دیا جاتا ہے۔ مؤخر الذکر نتیجہ (کے لیے) سے پتہ چلتا ہے کہ اگر ہم چھ رنرز کو مستقل رفتار کے ساتھ وقت سے شروع کرنے اور الگ اور مثبت پر غور کریں تو جامد رنر کو سست ترین غیر جامد رنر کے پہلے دو راؤنڈز کے دوران کم از کم دوسروں سے فاصلے سے الگ کیا جاتا ہے (لیکن پہلے راؤنڈ کے دوران ضروری نہیں)۔ دیگر نتائج بے ترتیب طور پر منتخب کردہ رفتار کے لیے ایک بہت زیادہ مضبوط نتیجہ موجود ہے: اسٹیشنری رنر کنونشن کا استعمال کرتے ہوئے، اگر اور فکسڈ ہیں اور غیر صفر رفتار والے رنرز کو بے ترتیب طور پر یکساں طور پر منتخب کیا جاتا ہے، تو جیسا کہ۔ دوسرے لفظوں میں، بے ترتیب رفتار والے دوڑنے والے کسی وقت "بہت تنہا" ہونے کا امکان رکھتے ہیں-قریب ترین دوسرے دوڑنے والے سے تقریبا یونٹ۔ مکمل قیاس درست ہے اگر "تنہائی" کو "تقریبا تنہائی" سے تبدیل کر دیا جائے، جس کا مطلب ہے کہ زیادہ سے زیادہ ایک دوسرا رنر کسی دیئے گئے رنر کے اندر ہے۔ قیاس کو الجبرائی فنکشن فیلڈز میں اینالاگ کے لیے عام کیا گیا ہے۔ نوٹس اور حوالہ جات نوٹس سائٹیشن ورکس نے اوپن پروبلم گارڈن نمبر میں بیرونی لنکس آرٹیکل کا حوالہ دیا۔ 4، 551-562۔ ڈیوفنٹائن مساوات نمبر تھیوری میں غیر حل شدہ مسائل کا قیاس کرتی ہیں