سورج مکھی کا مفروضہ ثابت ہو گیا

1 سے n تک کے اعداد لیجیے اور ان میں سے کچھ کو چننے کے تمام طریقوں پر نظر ڈالیے: ایسے 2ⁿ ذیلی سیٹ ہیں۔ اب چند ایسے ذیلی سیٹ چنیے جن کا مشترک حصہ بالکل ایک جیسا ہو، اور اس کے سوا کچھ مشترک نہ ہو۔ ریاضی دان اسے سورج مکھی (sunflower) کہتے ہیں: مشترک حصہ مرکز ہے، اور ہر سیٹ کا باقی حصہ ایک پنکھڑی ہے جو کسی دوسری پنکھڑی کو نہیں چھوتی۔

سورج مکھیاں کمبی نیٹوریکس (combinatorics) کا بنیادی آلہ ہیں۔ مقالے میں ان کے تعلق کی فہرست دی گئی ہے: بعض منطقی سرکٹس کی حدود، “cap set” مسئلہ، میٹرکس کی تیز ضرب، اور نظریۂ معلومات۔

1970 کا ایک سوال

مصنفین کے مطابق ان کے بارے میں سب سے فطری سوال پال اردوش کے 1970 کے ایک مقالے تک جاتا ہے۔ {1, …, n} کے ذیلی سیٹوں کا مجموعہ کتنا بڑا ہو سکتا ہے اگر اس کے کوئی k سیٹ مل کر سورج مکھی نہ بنائیں؟

1970 کی دہائی میں اردوش اور اندرے زیمیریدی نے یہ مفروضہ پیش کیا کہ ایسا مجموعہ 2ⁿ ممکنہ ذیلی سیٹوں سے قوت نمائی حد تک چھوٹا ہونا چاہیے: زیادہ سے زیادہ cⁿ، جہاں c کوئی عدد ہے جو 2 سے سختی سے کم ہو۔

دہائیوں تک بہترین حدیں تھوڑا سا ہی کم کر پائیں، کبھی اتنا نہیں کہ بنیاد (base) 2 سے نیچے آ جائے۔ صرف تین پنکھڑیوں والا معاملہ (k = 3) 2016 میں حل ہوا، cap set مسئلے میں پیش رفت اور ایلون، شپلکا اور اومانز کی ایک تحویل (reduction) کی بدولت۔

حد

ماتیا بوچچ اور فانکانگ ہی (یونیورسٹی آف ویانا) اور ہیونوو لی (KAIST اور انسٹی ٹیوٹ فار بیسک سائنس، جنوبی کوریا) نے یہ مفروضہ ہر k ≥ 3 کے لیے ثابت کیا ہے۔ ان کا بنیادی مسئلہ (theorem): جس مجموعے میں k پنکھڑیوں والی کوئی سورج مکھی نہ ہو، اس کے ارکان زیادہ سے زیادہ

3 · (2 − 1/(16k³))ⁿ

ہوتے ہیں۔ بنیاد 2 سے ذرا سی کم ہے، لیکن یہ 2 سے کم ایک مقررہ عدد ہے، اور اردوش اور زیمیریدی نے بالکل یہی مانگا تھا۔ 1997 کی ایک تعمیر سے ظاہر ہوتا ہے کہ بڑے k کے لیے اصل قدر اس سے بہت زیادہ کم نہیں ہو سکتی۔

سیٹوں سے ویکٹروں تک

ثبوت مسئلے کے ایک ایسے روپ سے گزرتا ہے جس میں ویکٹر ہیں۔ اعداد کو D ارکان والے n بلاکس میں بانٹیے اور ہر بلاک سے ایک رکن چنیے: ہر ایسا انتخاب ایک ویکٹر ہے۔ کئی ویکٹر اس وقت سورج مکھی بناتے ہیں جب ہر مقام پر ان کے اندراجات یا تو سب برابر ہوں یا سب مختلف۔

پھر مصنفین ایک “سورج مکھی ٹیسٹر” بناتے ہیں: ایک فنکشن جو سورج مکھی سے پاک مجموعے پر صرف اس وقت صفر سے مختلف ہوتا ہے جب اس کے تمام داخلے ایک ہی ویکٹر ہوں۔ نیا جزو یہ ہے کہ اس فنکشن کو قدم بہ قدم کم درجے کے انٹرپولیشن کثیر رقمیوں (polynomials) سے لکھا جائے۔ ان کثیر رقمیوں کی گنتی مجموعے کے سائز کو محدود کر دیتی ہے (ان کا مسئلہ 2)۔ ایک احتمالی دلیل، یعنی بے ترتیب بلاکس جن کی تمام سیٹ سائزوں پر اوسط لی جاتی ہے، اس حد کو واپس عام سیٹوں تک لے آتی ہے۔

ایک مشین نے ڈھونڈا، دوسری نے جانچا

مصنوعی ذہانت کے بارے میں مقالے کا بیان غیر معمولی طور پر صاف ہے۔ مسئلہ 2 کا ثبوت ChatGPT 6 Astra Pro نے ڈھونڈا، ایک مختصر گفتگو کے بعد جس کا آغاز اس سے تین پنکھڑیوں والی معروف دلیل کو عام کرنے کی درخواست سے ہوا۔ مصنفین کو یہ قدم ایک اور مقصد کے لیے درکار تھا: زیمیریدی کے پیش کردہ گراف کے ایک مسئلے کا induced روپ، جس کا اعلان وہ ایک بعد کے نوٹ کے لیے کرتے ہیں۔

ماڈل نے اپنا ثبوت “slice rank” کی زبان میں لکھا۔ مصنفین نے اسے کثیر رقمی طریقے (polynomial method) کی زبان میں دوبارہ لکھا، جو ان کے خیال میں قارئین کے لیے آسان ہے۔ وہ کہتے ہیں کہ انہوں نے ہر نتیجے کی تصدیق کی ہے اور پوری ذمہ داری لیتے ہیں، اور یہ کہ ثبوت Lean 4.35 میں تصدیق شدہ ہے، جو ثبوت جانچنے کا ایک سافٹ ویئر ہے، اور یہ تصدیق Palomar ذخیرے پر شائع کی جائے گی۔

کیا حل نہیں ہوا

مصنفین نے بنیاد کو بہتر بنانے کی کوشش نہیں کی۔ تین پنکھڑیوں کے لیے یہ نیسلنڈ اور ساوِن کی 2017 کی حد، تقریباً 1.89، سے بہتر نہیں۔ اور زیادہ مضبوط بہن مسئلہ، یعنی اردوش-راڈو کا سورج مکھی مفروضہ، ابھی کھلا ہے: ان کی حدیں اب بھی بلاک کے سائز D پر بہت زیادہ منحصر ہیں، اور وہ مسئلہ بالکل اسی کی ممانعت کرتا ہے۔