المُقدّمة
في منتصف أكتوبر ، جاستن جيلمر طار من كاليفورنيا إلى نيويورك لحضور حفل زفاف أحد الأصدقاء. أثناء تواجده في الساحل الشرقي زار مستشاره السابق ، مايكل ساكس، عالم رياضيات في جامعة روتجرز ، حيث حصل جيلمر على الدكتوراه قبل سبع سنوات.
تناول ساكس وجيلمر الغداء ، لكنهما لم يتحدثا عن الرياضيات. في الواقع ، لم يفكر جيلمر بجدية في الرياضيات منذ أن أنهى دراسته في جامعة روتجرز في عام 2015. كان ذلك عندما قرر أنه لا يريد مهنة في الأوساط الأكاديمية وبدلاً من ذلك بدأ في تعليم نفسه البرمجة. بينما كان ساكس يأكل ، أخبر جيلمر معلمه القديم عن وظيفته في Google ، حيث يعمل في التعلم الآلي والذكاء الاصطناعي.
كان الجو مشمسًا في اليوم الذي زار فيه جيلمر روتجرز. أثناء تجوله ، تذكر كيف قضى في عام 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 ، في ورقة كتبها بيتر فرانكل، عالم رياضيات مجري هاجر إلى اليابان في ثمانينيات القرن الماضي ويعتبر أداء الشارع من بين مساعيه.
توقع فرانكل أنه إذا كانت عائلة المجموعات مغلقة اتحادًا ، فيجب أن تحتوي على عنصر واحد (أو رقم) على الأقل يظهر في نصف المجموعات على الأقل. لقد كانت عتبة طبيعية لسببين.
أولاً ، هناك أمثلة متاحة بسهولة للعائلات المغلقة النقابية حيث تظهر جميع العناصر في 50 ٪ بالضبط من المجموعات. مثل كل المجموعات المختلفة ، يمكنك تكوينها من الأرقام من 1 إلى 10 ، على سبيل المثال. هناك 1,024 مجموعة من هذا القبيل ، والتي تشكل عائلة مغلقة النقابة ، ويظهر كل عنصر من العناصر العشرة في 10 منها. وثانيًا ، في الوقت الذي قدم فيه فرانكل التخمين ، لم يقدم أحد على الإطلاق مثالًا لعائلة مغلقة الاتحاد لا يصح فيها التخمين.
لذلك بدا أن 50٪ هو التوقع الصحيح.
هذا لا يعني أنه كان من السهل إثبات ذلك. في السنوات التي تلت بحث فرانكل ، كانت هناك نتائج قليلة. قبل عمل جيلمر ، تمكنت تلك الأوراق فقط من إنشاء عتبات تختلف باختلاف عدد المجموعات في العائلة (على عكس عتبة 50 ٪ نفسها للعائلات المحددة من جميع الأحجام).
قال "يبدو أنه يجب أن يكون سهلاً ، وهو مشابه للعديد من المشكلات السهلة ، لكنه قاوم الهجمات". ويل سوين من جامعة كولومبيا.
يعكس الافتقار إلى التقدم الطبيعة الصعبة للمشكلة وحقيقة أن العديد من علماء الرياضيات فضلوا عدم التفكير فيها ؛ كانوا قلقين من أن يفقدوا سنوات من حياتهم المهنية في مطاردة مشكلة خادعة كان من المستحيل حلها. يتذكر جيلمر يومًا في عام 2013 عندما ذهب إلى مكتب ساكس وطرح التخمينات النقابية المغلقة. وكاد مستشاره - الذي تصارع بنفسه في الماضي مع المشكلة - طرده من الغرفة.
قال جيلمر: "قال مايك ،" جاستن ، ستجعلني أفكر في هذه المشكلة مرة أخرى ولا أريد أن أفعل ذلك ".
نظرة ثاقبة لعدم اليقين
بعد زيارته لروتجرز ، قام جيلمر بتدوير المشكلة في ذهنه ، محاولًا فهم سبب صعوبة الأمر. لقد دفع نفسه بحقيقة أساسية: إذا كان لديك عائلة مكونة من 100 مجموعة ، فهناك 4,950 طريقة مختلفة لاختيار مجموعتين وأخذ اتحادهم. ثم سأل نفسه: كيف يمكن أن يعيد 4,950 نقابة مختلفة إلى 100 مجموعة فقط إذا لم يظهر أي عنصر في تلك النقابات ببعض التردد على الأقل؟
حتى في تلك المرحلة كان في طريقه إلى إثبات ، رغم أنه لم يكن يعرف ذلك بعد. إن التقنيات المستمدة من نظرية المعلومات ، والتي توفر طريقة صارمة للتفكير فيما يمكن توقعه عندما تسحب زوجًا من الأشياء بشكل عشوائي ، ستأخذه إلى هناك.
تطورت نظرية المعلومات في النصف الأول من القرن العشرين ، وأشهرها ورقة كلود شانون عام 20 ، "نظرية رياضية للتواصل. " قدمت الورقة طريقة دقيقة لحساب كمية المعلومات اللازمة لإرسال رسالة ، بناءً على مقدار عدم اليقين حول ما ستقوله الرسالة بالضبط. هذا الرابط - بين المعلومات وعدم اليقين - كانت رؤية شانون الرائعة والأساسية.
لأخذ مثال لعبة ، تخيل أنني أقلب عملة معدنية خمس مرات وأرسل التسلسل الناتج إليك. إذا كانت عملة عادية ، فسيحتاج الأمر إلى خمس أجزاء من المعلومات لإرسالها. ولكن إذا كانت عملة معدنية محملة - على سبيل المثال ، 99٪ من المحتمل أن تهبط على الوجه - فإنها تستغرق وقتًا أقل بكثير. على سبيل المثال ، يمكننا أن نتفق مسبقًا على أنني سأرسل لك 1 (جزء واحد من المعلومات) إذا هبطت العملة المحملة جميعًا خمس مرات ، وهو ما يحدث على الأرجح. هناك مفاجأة أكبر في نتيجة قلب العملة العادلة أكثر من تلك الموجودة في الوجه المتحيز ، وبالتالي المزيد من المعلومات.
ينطبق نفس التفكير على المعلومات الواردة في مجموعات من الأرقام. إذا كان لدي عائلة من المجموعات المغلقة النقابية - لنقل 1,024 مجموعة مصنوعة من الأرقام من 1 إلى 10 - يمكنني اختيار مجموعتين بشكل عشوائي. ثم يمكنني توصيل عناصر كل مجموعة إليك. تعكس كمية المعلومات اللازمة لإرسال هذه الرسالة مقدار عدم اليقين حول ماهية هذه العناصر: هناك احتمال بنسبة 50٪ ، على سبيل المثال ، أن يكون العنصر الأول في المجموعة الأولى هو 1 (لأن 1 يظهر في نصف المجموعات في العائلة) ، تمامًا كما توجد فرصة بنسبة 50٪ أن تكون النتيجة الأولى في سلسلة من تقلبات العملات العادلة هي الرؤوس.
غالبًا ما تظهر نظرية المعلومات في التوافقية ، وهي منطقة من الرياضيات معنية بحساب الأشياء ، وهو ما درسه جيلمر كطالب دراسات عليا. ولكن أثناء عودته إلى موطنه في كاليفورنيا ، شعر بالقلق من أن الطريقة التي يعتقد بها لربط نظرية المعلومات بتخمين الاتحاد المغلق كانت البصيرة الساذجة لأحد الهواة: من المؤكد أن علماء الرياضيات العاملين قد صادفوا هذا الكائن اللامع من قبل واعترفوا به على أنه ذهب أحمق. .
قال جيلمر: "بصراحة ، أنا مندهش قليلاً لم يفكر أحد في هذا من قبل". "لكن ربما لا ينبغي أن أتفاجأ ، لأنني كنت أفكر في الأمر لمدة عام ، وكنت أعرف نظرية المعلومات."
أكثر احتمالا من لا
عمل جيلمر على حل المشكلة ليلًا ، بعد إنهاء عمله في Google ، وفي عطلات نهاية الأسبوع طوال النصف الثاني من أكتوبر وأوائل نوفمبر. لقد شجعته الأفكار التي استكشفتها مجموعة من علماء الرياضيات قبل ذلك بسنوات تعاون مفتوح على مدونة عالم رياضيات بارز يدعى تيم جاورز. لقد عمل أيضًا مع كتاب مدرسي بجانبه حتى يتمكن من البحث عن الصيغ التي نسيها.
"كنت تعتقد أن الشخص الذي يأتي بنتيجة رائعة لا يجب أن يستشير الفصل 2 من عناصر نظرية المعلوماتقال جيلمر.
كانت إستراتيجية جيلمر هي تخيل عائلة مغلقة النقابة لا يظهر فيها أي عنصر حتى 1٪ من جميع المجموعات - مثال مضاد ، إذا كان موجودًا بالفعل ، من شأنه أن يزيف تخمين فرانكل.
لنفترض أنك اخترت مجموعتين ، A و B ، من هذه العائلة بشكل عشوائي وفكر في العناصر التي يمكن أن تكون في تلك المجموعات ، واحدة في كل مرة. اسأل الآن: ما هي احتمالات احتواء المجموعة أ على الرقم 1؟ والمجموعة ب؟ نظرًا لأن كل عنصر لديه فرصة أقل بقليل من 1٪ للظهور في أي مجموعة معينة ، فلن تتوقع أن يحتوي أي من A أو B على 1. مما يعني أن هناك القليل من المفاجأة - والقليل من المعلومات المكتسبة - إذا علمت أن أيًا منهما في الواقع هل.
بعد ذلك ، فكر في احتمال احتواء اتحاد A و B على 1. لا يزال من غير المحتمل ، لكنه أكثر احتمالية من احتمالات ظهوره في أي من المجموعتين الفرديتين. إنه مجموع احتمالية ظهوره في A واحتمالية ظهوره في B مطروحًا منه احتمال ظهوره في كليهما. لذا ، ربما أقل بقليل من 2٪.
هذا لا يزال منخفضًا ، لكنه أقرب إلى اقتراح 50-50. هذا يعني أن مشاركة النتيجة تتطلب مزيدًا من المعلومات. بعبارة أخرى ، إذا كانت هناك عائلة مغلقة اتحادًا لا يظهر فيها أي عنصر في 1٪ على الأقل من جميع المجموعات ، فهناك معلومات أكثر في اتحاد مجموعتين أكثر من أي من المجموعتين أنفسهما.
"إن فكرة الكشف عن الأشياء عنصرًا عنصرًا والنظر في مقدار المعلومات التي تتعلمها هي فكرة ذكية للغاية. هذه هي الفكرة الرئيسية للإثبات ريان الويس من جامعة برينستون.
في هذه المرحلة ، بدأ جيلمر في الاقتراب من تخمين فرانكل. هذا لأنه من السهل إثبات أنه في الأسرة المغلقة ، فإن اتحاد مجموعتين يحتوي بالضرورة على معلومات أقل من المجموعات نفسها - وليس أكثر.
لمعرفة السبب ، فكر في تلك العائلة المغلقة التي تحتوي على 1,024 مجموعة مختلفة يمكنك تكوينها من الأرقام من 1 إلى 10. إذا اخترت مجموعتين من هذه المجموعات عشوائيًا ، فستنتهي في المتوسط بمجموعات تحتوي على خمسة عناصر. (من بين تلك الـ 1,024،252 مجموعة ، 120 تحتوي على خمسة عناصر ، مما يجعل هذا الحجم الأكثر شيوعًا للمجموعة.) من المحتمل أيضًا أن ينتهي بك الأمر مع اتحاد يحتوي على حوالي سبعة عناصر. لكن هناك XNUMX طريقة مختلفة فقط لعمل مجموعات تحتوي على سبعة عناصر.
النقطة المهمة هي أن هناك قدرًا أكبر من عدم اليقين بشأن محتويات مجموعتين تم اختيارهما عشوائيًا أكثر مما هو موجود بشأن اتحادهما. ينحرف الاتحاد إلى مجموعات أكبر تحتوي على عدد أكبر من العناصر ، والتي توجد فيها احتمالات أقل. عندما تأخذ اتحاد مجموعتين في عائلة مغلقة النقابة ، فأنت تعرف نوعًا ما ما ستحصل عليه - مثل عندما تقلب عملة منحازة - مما يعني أن الاتحاد يحتوي على معلومات أقل من المجموعات التي يتكون منها.
مع ذلك ، كان لدى جيلمر دليل. كان يعلم أنه إذا لم يظهر أي عنصر في حتى 1٪ من المجموعات ، فإن الاتحاد مجبر على احتواء المزيد من المعلومات. لكن يجب أن يحتوي الاتحاد على معلومات أقل. لذلك يجب أن يكون هناك عنصر واحد على الأقل يظهر في 1٪ على الأقل من المجموعات.
الدفع إلى 50
عندما نشر جيلمر إثباته في 16 نوفمبر ، قام بتضمين ملاحظة أنه يعتقد أنه من الممكن استخدام طريقته للاقتراب أكثر من إثبات التخمين الكامل ، مما قد يرفع الحد الأدنى إلى 38٪.
بعد خمسة أيام ، ثلاثة مختلف مجموعات من علماء الرياضيات نشروا أوراقًا في غضون ساعات من بعضهم البعض بنيت على عمل جيلمر للقيام بذلك. إضافي أوراق يتبع، ولكن يبدو أن الاندفاع الأولي قد أخذ أساليب جيلمر بقدر ما سيذهبون ؛ من المرجح أن يستغرق الوصول إلى 50٪ أفكارًا جديدة إضافية.
مع ذلك ، بالنسبة لبعض مؤلفي أوراق المتابعة ، كان الوصول إلى 38٪ أمرًا بسيطًا نسبيًا ، وتساءلوا لماذا لم يفعل جيلمر ذلك بنفسه. تبين أن أبسط تفسير هو التفسير الصحيح: بعد أكثر من نصف عقد من الرياضيات ، لم يعرف جيلمر كيف يقوم ببعض العمل التحليلي الفني المطلوب لسحبه.
قال جيلمر: "كنت صدئًا بعض الشيء ، ولكي أكون صادقًا ، كنت عالقًا". "لكنني كنت حريصًا على معرفة إلى أين سيأخذها المجتمع."
ومع ذلك ، يعتقد جيلمر أن نفس الظروف التي تركته خارج الممارسة ربما جعلت إثباته ممكنًا في المقام الأول.
قال: "إنها الطريقة الوحيدة التي يمكنني من خلالها شرح سبب تفكيري في المشكلة لمدة عام في كلية الدراسات العليا وعدم إحراز أي تقدم ، وتركت الرياضيات لمدة ست سنوات ، ثم عدت إلى المشكلة وحققت هذا الاختراق". "لا أعرف كيف أشرح ذلك بخلاف كون تفكيري متحيزًا في التعلم الآلي."
تصحيح: ٣ فبراير ٢٠٢٤
أشار العنوان الرئيسي الأصلي إلى جيلمر على أنه "مهندس Google". في الحقيقة ، هو باحث.
