ایک اے آئی نے رنگ بھرنے کی ایک پہیلی سلجھا دی

لکیروں سے جڑے نقطوں کا ایک جال لیں — جسے ریاضی دان گراف کہتے ہیں۔ اب نقطوں میں اس طرح رنگ بھریں کہ لکیر سے جڑے دو نقطے کبھی ایک رنگ کے نہ ہوں۔ رنگوں کی وہ کم سے کم تعداد جس سے یہ ہو جائے، گراف کا رنگی عدد (chromatic number) کہلاتی ہے۔ ایک مشہور خاص صورت چار رنگوں کا مسئلۂ اثبات ہے، جو 1977 میں ثابت ہوا، اور جس کا عنوان سب کچھ کہہ دیتا ہے: “Every planar map is four colorable” (ہر مسطح نقشے میں چار رنگوں سے رنگ بھرا جا سکتا ہے)۔

ہیڈوِگر کی 1943 کی شرط

1943 میں ہیڈوِگر نے تمام گرافوں کے لیے ایک ہمہ گیر اصول تجویز کیا۔ نقطے یا لکیریں مٹا کر، اور دو جڑے ہوئے نقطوں کو ملا کر ایک بنا کر، گراف کو چھوٹا کریں۔ نتیجہ مائنر (minor) کہلاتا ہے۔ ہیڈوِگر نے سب سے بڑے مکمل گراف کو دیکھا — ایسا جھرمٹ جس میں ہر نقطہ باقی ہر نقطے سے جڑا ہو — جو اس طرح حاصل کیا جا سکے، اور قیاس کیا کہ درکار رنگوں کی تعداد کبھی اس جھرمٹ کے سائز سے زیادہ نہیں ہوتی۔

مقالہ اسے “گراف تھیوری کے قدیم ترین اور بنیادی ترین مسائل میں سے ایک” کہتا ہے۔ یہ صرف چھوٹی صورتوں کے لیے ثابت ہے: پانچ تک کے جھرمٹوں کے لیے، جہاں یہ چار رنگوں کے مسئلۂ اثبات کے مساوی یا اس پر قابلِ تحویل نکلتا ہے۔ چھ سے آگے یہ کھلا ہے۔

قریب تر، ایک لوگارتھم کے بعد دوسرا

چونکہ اصل بیان قابو میں نہیں آتا، محققین نے رنگوں کی تعداد کو جھرمٹ کے سائز کے کسی ایسے تفاعل سے محدود کرنے کی کوشش کی جو جتنا ممکن ہو آہستہ بڑھے۔ مقالہ پیش رفت کی کہانی سناتا ہے۔ دہائیوں تک بہترین حد تناسب سے کچھ تیز بڑھتی رہی — ایک لوگارتھم کے جذرِ مربع پر مشتمل عامل کے ساتھ۔ چند سال پہلے نورِن، پوسٹل اور سونگ نے یہ رکاوٹ توڑی۔ پھر ڈیلکور اور پوسٹل نے اسے مزید بہتر کیا اور، سب سے اہم بات، یہ دکھایا کہ کافی حد تک چھوٹے گرافوں سے نمٹ لینا کافی ہے۔ لیو اور لوو نے اضافی عامل کو گھٹا کر تہرے لوگارتھم تک پہنچا دیا۔

فطری منزل خطی ہیڈوِگر قیاس ہے: جھرمٹ کے سائز کا ایک مقررہ گنا ہمیشہ کافی ہوتا ہے۔ مونٹریال کی میک گل یونیورسٹی کے سرگئی نورِن اور ای ٹی ایچ زیورخ کے رافائل شٹائنر اب اسی کو ثابت کرنے کا دعویٰ کرتے ہیں۔

مشین کا کردار

مصنفین صاف کہتے ہیں: ثبوت اوپن اے آئی کے ماڈل GPT-6 Astra نے ان کی ہدایات پر چلتے ہوئے ڈھونڈا۔ پہلے انہوں نے اس سے بہت گھنے گرافوں کی صورت ثابت کرنے کو کہا، جسے وہ گمشدہ ٹکڑا سمجھتے تھے۔ وہ کامیاب ہوا، وہ لکھتے ہیں، “صرف دو ایک گھنٹوں اور کچھ حوصلہ افزائی کے بعد”۔ جب اس سے ایک انحصار کو واضح کرنے کو کہا گیا تو اس نے ایک خاص سائز تک کے گرافوں کا احاطہ کیا — لیکن پوری مطلوبہ حد کا نہیں۔ پھر انہوں نے خلا پاٹنے کے لیے اس سے ایک نیا خیال مانگا، جس سے حتمی ثبوت کا “بوٹ اسٹریپ” قدم نکلا۔ وہ کہتے ہیں کہ مصنفین کے اپنے ثبوت کے مخصوص خیالات میں سے تقریباً کوئی بھی باقی نہیں بچا، سوائے انقباض (contraction) سے متعلق ایک تجویز کے۔

تحریر انسانوں کی ہے۔ اوپن اے آئی کے ایک اور ماڈل نے پروف ریڈنگ اور کتابیات میں مدد کی۔ مصنفین بتاتے ہیں کہ اوپن اے آئی کے Codex نے ثبوت معاون Lean میں پورے ثبوت کا ایک باضابطہ، مشین سے جانچا جا سکنے والا نسخہ تیار کیا، جو اے آئی کے لکھے ہوئے ایک ابتدائی مسودے کے ساتھ آن لائن رکھا گیا ہے۔ ریاضی کی پوری ذمہ داری وہ خود لیتے ہیں۔

ثبوت کے اندر

دلیل کے دو حصے ہیں:

1. چھوٹے گراف، کم رنگ۔ ایسے گرافوں کے لیے جو جھرمٹ کی حد سے بہت زیادہ بڑے نہیں، مصنفین دکھاتے ہیں کہ جھرمٹ کے سائز کا تقریباً چار گنا کافی ہے۔ نقطۂ آغاز رِیڈ اور سیمور کا 1998 کا ایک نتیجہ ہے: رنگ بھرنے کی ایک نرم کی گئی، “کسری” (fractional) شکل پہلے ہی دو کے عامل کے ساتھ خطی اصول کی پابندی کرتی ہے۔ نیا کام گراف میں چند اضافی لکیریں جوڑ کر اور ایک معاون ڈھانچے میں بہت بڑی جوڑیاں (matchings) ڈھونڈ کر کسری رنگ بندیوں کو حقیقی رنگ بندیوں میں بدلتا ہے۔
2. ایک بوٹ اسٹریپ۔ دوسری دلیل ہر قدم پر قوت نما میں چار تہائی کے عامل سے گراف کے احاطہ شدہ سائزوں کی حد بڑھاتی ہے، ایک بڑے مستقلے کی قیمت پر۔ دس قدم اس حد کو ایک تہائی سے تقریباً 5.92 تک لے جاتے ہیں، ڈیلکور-پوسٹل تحویل کے لیے درکار 5 کی دہلیز سے آگے۔ یہ حصہ گیارفاش کی ایک پرانی ترکیب استعمال کرتا ہے، جو مصنفین کے مطابق اس مسئلے پر کبھی لاگو نہیں کی گئی تھی۔

مصنفین ثبوت کو معلوم اوزاروں سے بنا ہوا بیان کرتے ہیں — “موجودہ نتائج کے محدب احاطے (convex hull) کے اندر”، مگر اس کے کسی واضح کنارے پر نہیں۔

جو ابھی کھلا ہے

مستقلہ بہت بڑا ہے: ایک موٹا اندازہ تقریباً 10¹⁰⁰ دیتا ہے۔ مصنفین اسے 10¹⁰ سے نیچے لانے کی گنجائش دیکھتے ہیں، لیکن سمجھتے ہیں کہ مثلاً 100 تک پہنچنے کے لیے نئے خیالات درکار ہوں گے۔ ہیڈوِگر کا اصل قیاس جوں کا توں ہے: “ہم نے فیصلہ نہیں کیا”، وہ لکھتے ہیں۔ مقالہ ایک پری پرنٹ ہے؛ نئی ریاضی کے 41 صفحات کو اب دوسرے ماہرین کی کڑی جانچ کا سامنا کرنا ہوگا۔