گوگل محقق، ریاضی سے باہر، سیٹوں کے بارے میں شیطانی مسئلہ دراڑ دیتا ہے۔

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

ساکس اور گلمر نے دوپہر کے کھانے پر بات کی، لیکن انہوں نے ریاضی کے بارے میں بات نہیں کی۔ درحقیقت، گلمر نے 2015 میں Rutgers میں فارغ ہونے کے بعد سے ریاضی کے بارے میں سنجیدگی سے نہیں سوچا تھا۔ یہی وہ وقت تھا جب اس نے فیصلہ کیا تھا کہ وہ اکیڈمیا میں کیریئر نہیں چاہتا اور اس کے بجائے خود کو پروگرام سکھانا شروع کر دیا۔ جیسے ہی اس نے اور ساکس نے کھایا، گلمر نے اپنے پرانے سرپرست کو گوگل میں اپنی ملازمت کے بارے میں بتایا، جہاں وہ مشین لرننگ اور مصنوعی ذہانت پر کام کرتا ہے۔

جس دن گلمر نے رٹجرز کا دورہ کیا اس دن دھوپ تھی۔ جب وہ گھوم رہا تھا، اس نے یاد کیا کہ کس طرح 2013 میں اس نے ایک سال کا بہتر حصہ کیمپس کے انہی راستوں پر چلتے ہوئے گزارا تھا، اس مسئلے کے بارے میں سوچتے ہوئے جسے یونین بند قیاس کہا جاتا ہے۔ یہ ایک طے تھا، اگرچہ بے نتیجہ تھا: اپنی تمام تر کوششوں سے، گلمر صرف اپنے آپ کو یہ سکھانے میں کامیاب ہوا تھا کہ نمبروں کے سیٹ کے بارے میں سادہ نظر آنے والے مسئلے کو حل کرنا اتنا مشکل کیوں ہے۔

"میرے خیال میں بہت سارے لوگ اس مسئلے کے بارے میں سوچتے ہیں جب تک کہ وہ مطمئن نہ ہو جائیں کہ وہ سمجھتے ہیں کہ یہ مشکل کیوں ہے۔ میں نے شاید زیادہ تر لوگوں کے مقابلے میں اس پر زیادہ وقت گزارا،" گلمر نے کہا۔

اس کے اکتوبر کے دورے کے بعد، کچھ غیر متوقع ہوا: اسے ایک نیا آئیڈیا ملا۔ گلمر نے یونین بند قیاس کو حل کرنے کے لیے انفارمیشن تھیوری سے تکنیک کو لاگو کرنے کے طریقوں کے بارے میں سوچنا شروع کیا۔ اس نے ایک مہینے تک اس خیال کا پیچھا کیا، ہر موڑ پر اس کے ناکام ہونے کی توقع کی۔ لیکن اس کے بجائے، ثبوت کا راستہ کھلتا رہا۔ آخر کار 16 نومبر کو وہ اپنی نوعیت کا پہلا نتیجہ شائع کیا۔ اس سے ریاضی دانوں کو مکمل قیاس کو ثابت کرنے کا راستہ ملتا ہے۔

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

ادھا بھرا ہوا

یونین بند قیاس نمبروں کے مجموعے کے بارے میں ہے جسے سیٹ کہتے ہیں، جیسے کہ {1, 2} اور {2, 3, 4}۔ آپ سیٹوں پر آپریشن کر سکتے ہیں، بشمول ان کی یونین لینا، جس کا مطلب ہے ان کو ملانا۔ مثال کے طور پر، {1, 2} اور {2, 3, 4} کا اتحاد {1, 2, 3, 4} ہے۔

سیٹوں کا مجموعہ، یا خاندان، "یونین بند" سمجھا جاتا ہے اگر خاندان میں کسی بھی دو سیٹوں کا اتحاد خاندان میں موجود کسی بھی سیٹ کے برابر ہو۔ مثال کے طور پر، چار سیٹوں کے اس خاندان پر غور کریں:

{1}، {1، 2}، {2، 3، 4}، {1، 2، 3، 4}۔

کسی بھی جوڑے کو جوڑیں اور آپ کو ایک سیٹ مل جائے گا جو پہلے سے ہی خاندان میں ہے، خاندانی اتحاد کو بند کر دیتا ہے۔

ریاضی دانوں نے 1960 کی دہائی تک یونین بند قیاس کے ورژن کے بارے میں بات چیت کی، لیکن اس کا پہلا باضابطہ بیان 1979 میں ایک مقالے میں موصول ہوا۔ پیٹر فرینک، ہنگری کے ایک ریاضی دان جو 1980 کی دہائی میں جاپان ہجرت کر گئے تھے اور جو سڑکوں پر پرفارم کرنے کو اپنے تعاقب میں شمار کرتے ہیں۔

فرینک نے قیاس کیا کہ اگر سیٹوں کا ایک خاندان یونین بند ہے تو اس میں کم از کم ایک عنصر (یا نمبر) ہونا چاہیے جو کم از کم نصف سیٹوں میں ظاہر ہوتا ہے۔ یہ دو وجوہات کی بنا پر ایک قدرتی حد تھی۔

سب سے پہلے، یونین بند خاندانوں کی آسانی سے دستیاب مثالیں ہیں جن میں تمام عناصر بالکل 50% سیٹوں میں ظاہر ہوتے ہیں۔ ان تمام مختلف سیٹوں کی طرح جو آپ نمبر 1 سے 10 تک بنا سکتے ہیں، مثال کے طور پر۔ اس طرح کے 1,024 سیٹ ہیں، جو ایک یونین بند خاندان بناتے ہیں، اور 10 عناصر میں سے ہر ایک ان میں سے 512 میں ظاہر ہوتا ہے۔ اور دوسرا، جس وقت فرینک نے یہ قیاس کیا تھا، اس وقت کسی نے بھی اتحاد سے بند خاندان کی مثال پیش نہیں کی تھی جس میں قیاس نہیں تھا۔

تو 50% درست پیشین گوئی کی طرح لگ رہا تھا.

اس کا مطلب یہ نہیں تھا کہ ثابت کرنا آسان تھا۔ فرینک کے مقالے کے بعد کے سالوں میں، بہت کم نتائج آئے ہیں۔ گلمر کے کام سے پہلے، وہ کاغذات صرف ان حدوں کو قائم کرنے میں کامیاب ہوتے تھے جو خاندان میں سیٹوں کی تعداد کے ساتھ مختلف ہوتے تھے (جیسا کہ تمام سائز کے سیٹ فیملیز کے لیے ایک ہی 50% حد ہونے کے برعکس)۔

"ایسا محسوس ہوتا ہے کہ یہ آسان ہونا چاہئے، اور یہ بہت سے مسائل کی طرح ہے جو آسان ہیں، لیکن اس نے حملوں کی مزاحمت کی ہے،" کہا۔ ول ساون کولمبیا یونیورسٹی کے.

پیشرفت کی کمی مسئلہ کی پیچیدہ نوعیت اور اس حقیقت دونوں کی عکاسی کرتی ہے کہ بہت سے ریاضی دانوں نے اس کے بارے میں سوچنے کو ترجیح نہیں دی۔ انہیں خدشہ تھا کہ وہ اپنے کیریئر کے سالوں کو ایک ایسے پرکشش مسئلے کا پیچھا کرتے ہوئے کھو دیں گے جسے حل کرنا ناممکن تھا۔ گلمر کو 2013 کا ایک دن یاد ہے جب وہ ساکس کے دفتر گیا اور یونین بند ہونے کا اندازہ لگایا۔ اس کا مشیر - جو ماضی میں خود اس مسئلے سے لڑا تھا - نے اسے تقریباً کمرے سے باہر پھینک دیا۔

"مائیک نے کہا، 'جسٹن، آپ مجھے دوبارہ اس مسئلے کے بارے میں سوچنے پر مجبور کریں گے اور میں ایسا نہیں کرنا چاہتا،'" گلمر نے کہا۔

غیر یقینی صورتحال کی بصیرت

Rutgers کے دورے کے بعد، گلمر نے اس مسئلے کو اپنے ذہن میں گھمایا، یہ سمجھنے کی کوشش کی کہ یہ اتنا مشکل کیوں تھا۔ اس نے خود کو ایک بنیادی حقیقت کے ساتھ اشارہ کیا: اگر آپ کے پاس 100 سیٹوں کا خاندان ہے، تو دو کو منتخب کرنے اور ان کا اتحاد لینے کے 4,950 مختلف طریقے ہیں۔ پھر اس نے اپنے آپ سے پوچھا: یہ کیسے ممکن ہے کہ 4,950 مختلف یونینیں صرف 100 سیٹوں پر نقشہ بنا لیں اگر ان یونینوں میں کم از کم کچھ تعدد کے ساتھ کوئی عنصر ظاہر نہ ہو؟

یہاں تک کہ اس وقت بھی وہ ایک ثبوت کی طرف جا رہا تھا، حالانکہ اسے ابھی تک اس کا علم نہیں تھا۔ انفارمیشن تھیوری کی تکنیکیں، جو اس بارے میں سوچنے کا ایک سخت طریقہ فراہم کرتی ہے کہ جب آپ اشیاء کے ایک جوڑے کو بے ترتیب طور پر کھینچتے ہیں تو اسے وہاں لے جاتے ہیں۔

انفارمیشن تھیوری 20 ویں صدی کے پہلے نصف میں تیار ہوئی، جو سب سے مشہور کلاڈ شینن کے 1948 کے مقالے کے ساتھ "مواصلات کا ایک ریاضی کا نظریہ" اس کاغذ نے پیغام بھیجنے کے لیے درکار معلومات کی مقدار کا حساب لگانے کا ایک درست طریقہ فراہم کیا، اس بات کی بنیاد پر کہ پیغام میں بالکل کیا کہا جائے گا۔ یہ لنک - معلومات اور غیر یقینی کے درمیان - شینن کی قابل ذکر، بنیادی بصیرت تھی۔

ایک کھلونا کی مثال لینے کے لیے، تصور کریں کہ میں ایک سکے کو پانچ بار پلٹتا ہوں اور نتیجہ کی ترتیب آپ کو بھیجتا ہوں۔ اگر یہ ایک عام سکہ ہے، تو اسے منتقل کرنے میں معلومات کے پانچ بٹس لگتے ہیں۔ لیکن اگر یہ ایک بھاری بھرکم سکہ ہے - کہہ لیں، 99% کے سر پر اترنے کا امکان ہے - اس میں بہت کم وقت لگتا ہے۔ مثال کے طور پر، ہم وقت سے پہلے اس بات پر متفق ہو سکتے ہیں کہ اگر بھاری بھرکم سکہ پانچوں بار سر پر آتا ہے تو میں آپ کو ایک 1 (معلومات کا ایک حصہ) بھیجوں گا، جس کے کرنے کا بہت امکان ہے۔ منصفانہ سکے پلٹنے کے نتیجے میں متعصب کے مقابلے میں زیادہ حیرت ہوتی ہے، اور اس وجہ سے مزید معلومات۔

یہی سوچ اعداد کے سیٹ میں موجود معلومات پر بھی لاگو ہوتی ہے۔ اگر میرے پاس یونین بند سیٹوں کا ایک خاندان ہے — کہیے کہ نمبر 1,024 سے 1 تک بنائے گئے 10 سیٹ — میں بے ترتیب طور پر دو سیٹ چن سکتا ہوں۔ تب میں آپ کو ہر سیٹ کے عناصر سے آگاہ کر سکتا ہوں۔ اس پیغام کو بھیجنے میں جو معلومات لی جاتی ہیں وہ اس بات کی غیر یقینی صورتحال کی عکاسی کرتی ہے کہ وہ عناصر کیا ہیں: 50% امکان ہے، مثال کے طور پر، کہ پہلے سیٹ میں پہلا عنصر 1 ہے (کیونکہ 1 نصف سیٹوں میں ظاہر ہوتا ہے۔ خاندان)، بالکل اسی طرح جیسے 50 فیصد امکان ہے کہ منصفانہ سکے کے پلٹنے کی ترتیب میں پہلا نتیجہ ہیڈز ہے۔

انفارمیشن تھیوری اکثر combinatorics میں ظاہر ہوتی ہے، ریاضی کا ایک ایسا شعبہ جس کا تعلق اشیاء کی گنتی سے ہے، جو گلمر نے بطور گریجویٹ طالب علم پڑھا تھا۔ لیکن جب وہ گھر واپس کیلیفورنیا پہنچا، تو اسے فکر ہوئی کہ جس طرح سے اس نے انفارمیشن تھیوری کو بند یونین کے قیاس سے جوڑنے کا سوچا وہ ایک شوقیہ کی سادہ بصیرت تھی: یقیناً کام کرنے والے ریاضی دان اس چمکدار چیز کو پہلے بھی دیکھ چکے تھے اور اسے بیوقوف کا سونا سمجھ چکے تھے۔ .

"سچ پوچھیں تو، میں تھوڑا حیران ہوں کہ اس سے پہلے کسی نے اس کے بارے میں نہیں سوچا تھا،" گلمر نے کہا۔ "لیکن شاید مجھے حیران نہیں ہونا چاہئے، کیونکہ میں نے خود ایک سال تک اس کے بارے میں سوچا تھا، اور میں انفارمیشن تھیوری کو جانتا تھا۔"

نہیں سے زیادہ امکان

گلمر نے گوگل پر اپنا کام ختم کرنے کے بعد، اور اکتوبر کے دوسرے نصف اور نومبر کے اوائل میں ویک اینڈ پر رات کو اس مسئلے پر کام کیا۔ اس کی حوصلہ افزائی ان خیالات سے ہوئی جو ریاضی دانوں کے ایک گروپ نے برسوں پہلے ایک میں دریافت کی تھیں۔ کھلا تعاون ٹم گاورز نامی ایک ممتاز ریاضی دان کے بلاگ پر۔ اس نے اپنے ساتھ ایک درسی کتاب کے ساتھ بھی کام کیا تاکہ وہ ان فارمولوں کو تلاش کر سکے جنہیں وہ بھول گیا تھا۔

"آپ کو لگتا ہے کہ جو کوئی بہت اچھا نتیجہ لے کر آتا ہے اسے باب 2 سے مشورہ نہیں کرنا چاہئے۔ انفارمیشن تھیوری کے عناصر، لیکن میں نے کیا،" گلمر نے کہا۔

گلمر کی حکمت عملی ایک یونین بند خاندان کا تصور کرنا تھی جس میں تمام سیٹوں میں سے 1% میں بھی کوئی عنصر ظاہر نہیں ہوتا تھا - ایک جوابی مثال کہ، اگر یہ واقعی موجود ہے، تو فرینک کے قیاس کو غلط ثابت کرے گا۔

فرض کریں کہ آپ اس خاندان سے بے ترتیب طور پر دو سیٹ، A اور B کا انتخاب کریں اور ان عناصر پر غور کریں جو ان سیٹوں میں ہو سکتے ہیں، ایک وقت میں ایک۔ اب پوچھیں: وہ کیا مشکلات ہیں جو سیٹ A میں نمبر 1 پر مشتمل ہے؟ اور سیٹ بی؟ چونکہ ہر عنصر کا کسی بھی سیٹ میں ظاہر ہونے کا 1% سے تھوڑا کم امکان ہوتا ہے، اس لیے آپ A یا B میں سے کسی ایک میں 1 ہونے کی توقع نہیں کریں گے۔ جس کا مطلب ہے کہ بہت کم حیرت ہے — اور بہت کم معلومات حاصل کی گئی ہیں — اگر آپ یہ سیکھتے ہیں کہ نہ ہی حقیقت میں کرتا ہے

اس کے بعد، اس موقع کے بارے میں سوچیں کہ A اور B کے ملاپ میں 1 ہے۔ اس کا اب بھی امکان نہیں ہے، لیکن یہ ان مشکلات سے زیادہ ہے جو انفرادی سیٹوں میں سے کسی ایک میں ظاہر ہوتا ہے۔ یہ A میں ظاہر ہونے والے امکانات کا مجموعہ ہے اور B میں ظاہر ہونے والے امکان کو کم کر کے یہ دونوں میں ظاہر ہوتا ہے۔ تو، شاید صرف 2٪ سے کم۔

یہ اب بھی کم ہے، لیکن یہ 50-50 تجویز کے قریب ہے۔ اس کا مطلب ہے کہ نتیجہ شیئر کرنے کے لیے مزید معلومات درکار ہوتی ہیں۔ دوسرے لفظوں میں، اگر کوئی یونین بند خاندان ہے جس میں تمام سیٹوں میں سے کم از کم 1% میں کوئی عنصر ظاہر نہیں ہوتا ہے، تو دو سیٹوں کے اتحاد میں خود ان دونوں سیٹوں کے مقابلے میں زیادہ معلومات ہوتی ہیں۔

"چیزوں کے عنصر کو عنصر کے ذریعہ ظاہر کرنے اور آپ کے سیکھنے والی معلومات کی مقدار کو دیکھنے کا خیال انتہائی ہوشیار ہے۔ یہ ثبوت کا بنیادی خیال ہے،" کہا ریان الویز پرنسٹن یونیورسٹی کے.

اس وقت گلمر نے فرینک کے قیاس کو ختم کرنا شروع کر دیا تھا۔ اس کی وجہ یہ ہے کہ یہ ظاہر کرنا آسان ہے کہ یونین سے بند خاندان میں، دو سیٹوں کے اتحاد میں لازمی طور پر سیٹوں سے کم معلومات ہوتی ہیں - زیادہ نہیں۔

یہ دیکھنے کے لیے کہ کیوں، اس یونین بند فیملی کے بارے میں سوچیں جس میں 1,024 مختلف سیٹس ہیں جو آپ نمبر 1 سے 10 تک بنا سکتے ہیں۔ اگر آپ ان میں سے دو سیٹوں کو بے ترتیب طور پر چنتے ہیں، تو اوسطاً آپ کو پانچ عناصر والے سیٹ ملیں گے۔ (ان 1,024 سیٹوں میں سے، 252 میں پانچ عناصر ہوتے ہیں، جو کہ سب سے عام سیٹ سائز بناتا ہے۔) آپ کا اختتام سات عناصر پر مشتمل یونین کے ساتھ ہونے کا بھی امکان ہے۔ لیکن سات عناصر پر مشتمل سیٹ بنانے کے صرف 120 مختلف طریقے ہیں۔

نقطہ یہ ہے کہ، تصادفی طور پر منتخب کردہ دو سیٹوں کے مواد کے بارے میں ان کے اتحاد کے بارے میں زیادہ غیر یقینی صورتحال ہے۔ یونین زیادہ عناصر کے ساتھ بڑے سیٹوں کی طرف جھکتی ہے، جس کے امکانات کم ہیں۔ جب آپ یونین سے بند خاندان میں دو سیٹوں کا اتحاد لیتے ہیں، تو آپ کو معلوم ہوتا ہے کہ آپ کیا حاصل کرنے جا رہے ہیں — جیسے جب آپ ایک متعصب سکے کو پلٹائیں — جس کا مطلب ہے کہ یونین میں ان سیٹوں سے کم معلومات ہوتی ہیں جن پر وہ بنا ہوا ہے۔

اس کے ساتھ، گلمر کے پاس ایک ثبوت تھا. وہ جانتا تھا کہ اگر 1٪ ​​سیٹوں میں بھی کوئی عنصر ظاہر نہیں ہوتا ہے، تو یونین مزید معلومات پر مشتمل ہونے پر مجبور ہے۔ لیکن یونین میں کم معلومات ہونی چاہئیں۔ اس لیے کم از کم ایک عنصر ہونا چاہیے جو کم از کم 1% سیٹوں میں ظاہر ہو۔

50 تک دھکیلیں۔

جب گلمر نے 16 نومبر کو اپنا ثبوت پوسٹ کیا تو اس نے ایک نوٹ شامل کیا کہ اس کے خیال میں مکمل قیاس کے ثبوت کے قریب جانے کے لیے اپنا طریقہ استعمال کرنا ممکن ہے، ممکنہ طور پر حد کو 38 فیصد تک بڑھانا۔

پانچ دن بعد، تین مختلف گروہوں ریاضی دانوں نے ایک دوسرے کے گھنٹوں کے اندر کاغذات پوسٹ کیے جو گلمر کے کام پر استوار کیے گئے تھے۔ ایڈیشنل کاغذات پیچھے پیچھے، لیکن لگتا ہے کہ ابتدائی برسٹ نے گلمر کے طریقوں کو جہاں تک جانا ہے وہاں لے لیا ہے۔ 50% تک پہنچنے کا امکان اضافی نئے آئیڈیاز لے گا۔

پھر بھی، فالو اپ پیپرز کے کچھ مصنفین کے لیے، 38% تک پہنچنا نسبتاً سیدھا تھا، اور وہ حیران تھے کہ گلمر نے یہ کام خود کیوں نہیں کیا۔ سب سے آسان وضاحت درست نکلی: ریاضی سے باہر آدھے دہائی سے زیادہ کے بعد، گلمر صرف یہ نہیں جانتا تھا کہ اسے ختم کرنے کے لیے درکار تکنیکی تجزیاتی کام میں سے کچھ کیسے کرنا ہے۔

گلمر نے کہا ، "میں تھوڑا زنگ آلود تھا ، اور سچ پوچھیں تو میں پھنس گیا تھا۔" "لیکن میں یہ دیکھنے کے لیے بے چین تھا کہ کمیونٹی اسے کہاں لے جائے گی۔"

پھر بھی گلمر کا خیال ہے کہ وہی حالات جنہوں نے اسے عملی طور پر چھوڑ دیا تھا شاید اس کا ثبوت پہلی جگہ ممکن ہوا۔

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

اصلاح: جنوری۳۱، ۲۰۱۹
اصل سرخی میں گلمر کو "گوگل انجینئر" کہا گیا ہے۔ درحقیقت وہ ایک محقق ہیں۔