محقق گوگل، مدت زیادی از ریاضی خارج شده است، مشکل شیطانی درباره مجموعه ها را حل می کند

در اواسط اکتبر، جاستین گیلمر از کالیفرنیا به نیویورک پرواز کرد تا در عروسی یکی از دوستانش شرکت کند. هنگامی که در ساحل شرقی بود، از مشاور سابق خود دیدن کرد، مایکل ساکس، ریاضیدان دانشگاه راتگرز، جایی که گیلمر هفت سال پیش از آن دکترای خود را دریافت کرده بود.

ساکس و گیلمر سر ناهار صحبت کردند، اما در مورد ریاضی صحبت نکردند. در واقع، گیلمر از زمانی که در سال 2015 در راتگرز به پایان رسید، به طور جدی به ریاضیات فکر نکرده بود. در آن زمان بود که تصمیم گرفت نمی‌خواهد در آکادمیک شغلی داشته باشد و در عوض شروع به آموزش برنامه‌نویسی کرد. وقتی او و ساکس غذا می‌خوردند، گیلمر به مربی قدیمی‌اش درباره شغلش در گوگل گفت، جایی که او در زمینه یادگیری ماشینی و هوش مصنوعی کار می‌کند.

روزی که گیلمر از راتگرز دیدن کرد، آفتابی بود. همانطور که در اطراف قدم می زد، به یاد می آورد که چگونه در سال 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 مورد از آنها ظاهر می شود. و دوم، در زمانی که فرانکل این حدس را مطرح کرد، هیچ‌کس نمونه‌ای از خانواده‌های بسته‌شده در اتحادیه ارائه نکرده بود که در آن حدس‌ها صادق نبود.

بنابراین 50% پیش بینی درستی به نظر می رسید.

این بدان معنا نیست که اثبات آن آسان است. در سالهای پس از مقاله فرانکل، نتایج کمی حاصل شده است. قبل از کار گیلمر، آن مقالات فقط توانستند آستانه‌هایی را تعیین کنند که با تعداد مجموعه‌ها در خانواده متفاوت بود (در مقابل همان آستانه 50 درصدی برای خانواده‌های مجموعه‌ای در همه اندازه‌ها).

"به نظر می رسد که باید آسان باشد، و شبیه به بسیاری از مشکلات است که آسان هستند، اما در برابر حملات مقاومت کرده است." ویل ساوین از دانشگاه کلمبیا

فقدان پیشرفت هم ماهیت مشکل و هم این واقعیت را منعکس می کند که بسیاری از ریاضیدانان ترجیح می دهند به آن فکر نکنند. آنها نگران بودند که سال ها از حرفه خود را به دنبال یک مشکل فریبنده که حل آن غیرممکن بود از دست بدهند. گیلمر روزی را در سال 2013 به یاد می آورد که به دفتر ساکس رفت و حدس بسته بودن اتحادیه را مطرح کرد. مشاور او - که در گذشته خودش با این مشکل دست و پنجه نرم می کرد - تقریباً او را از اتاق بیرون انداخت.

گیلمر گفت: "مایک گفت، "جاستین، تو می‌خواهی دوباره مرا به این مشکل فکر کنی و من نمی‌خواهم این کار را انجام دهم."

بینشی از عدم قطعیت

گیلمر پس از بازدید از راتگرز، این مشکل را در ذهن خود جابجا کرد و سعی کرد بفهمد چرا آنقدر سخت است. او خود را با یک واقعیت اساسی ترغیب کرد: اگر شما یک خانواده 100 مجموعه ای دارید، 4,950 راه مختلف برای انتخاب دو و گرفتن اتحاد آنها وجود دارد. سپس از خود پرسید: چگونه ممکن است که 4,950 اتحادیه مختلف به 100 مجموعه برگردند اگر هیچ عنصری در آن اتحادیه ها حداقل با مقداری فرکانس ظاهر نشود؟

حتی در آن نقطه او در راه خود برای اثبات بود، اگرچه هنوز آن را نمی دانست. تکنیک‌های تئوری اطلاعات، که روشی دقیق برای تفکر در مورد اینکه وقتی یک جفت شی را به‌طور تصادفی می‌کشید چه انتظاری داشته باشید، او را به آنجا می‌برد.

نظریه اطلاعات در نیمه اول قرن بیستم توسعه یافت که مشهورترین آن با مقاله کلود شانون در سال 20 بود.یک نظریه ریاضی ارتباطات" این مقاله روشی دقیق برای محاسبه مقدار اطلاعات مورد نیاز برای ارسال پیام، بر اساس میزان عدم قطعیت در مورد اینکه پیام دقیقاً چه می‌گوید، ارائه کرد. این لینک - بین اطلاعات و عدم قطعیت - بینش قابل توجه و اساسی شانون بود.

برای مثال اسباب بازی، تصور کنید که من یک سکه را پنج بار برمی گردانم و دنباله حاصل را برای شما ارسال می کنم. اگر یک سکه معمولی باشد، انتقال آن به پنج بیت اطلاعات نیاز دارد. اما اگر یک سکه بارگذاری شده باشد - مثلاً 99٪ احتمال دارد روی سر فرود بیاید - بسیار کمتر طول می کشد. به عنوان مثال، می‌توانیم از قبل توافق کنیم که اگر سکه بارگیری شده هر پنج بار به سر رسید، یک عدد 1 (یک بیت اطلاعات) برای شما ارسال کنم، که به احتمال زیاد انجام می‌شود. در نتیجه یک چرخش سکه منصفانه شگفتی بیشتری نسبت به یک سوگیر وجود دارد و بنابراین اطلاعات بیشتری وجود دارد.

همین تفکر در مورد اطلاعات موجود در مجموعه اعداد نیز صدق می کند. اگر خانواده‌ای از مجموعه‌های بسته‌شده اتحادیه داشته باشم - مثلاً 1,024 مجموعه ساخته شده از اعداد 1 تا 10 - می‌توانم دو مجموعه را به‌طور تصادفی انتخاب کنم. سپس می‌توانم عناصر هر مجموعه را به شما منتقل کنم. مقدار اطلاعاتی که برای ارسال آن پیام لازم است نشان دهنده میزان عدم قطعیت در مورد این عناصر است: به عنوان مثال، احتمال 50٪ وجود دارد که اولین عنصر در مجموعه اول 1 باشد (زیرا 1 در نیمی از مجموعه ها ظاهر می شود. خانواده)، همانطور که به احتمال 50% اولین نتیجه در یک دنباله از ورق زدن سکه های منصفانه سر است.

نظریه اطلاعات اغلب در ترکیبات، حوزه‌ای از ریاضیات که با شمارش اشیاء مرتبط است، ظاهر می‌شود، چیزی که گیلمر در دوران تحصیلات تکمیلی مطالعه کرده بود. اما در حالی که او به خانه خود به کالیفرنیا پرواز می کرد، نگران بود که روشی که او فکر می کرد برای اتصال نظریه اطلاعات به حدس اتحادیه بسته، بینش ساده لوحانه یک آماتور بود: مطمئناً ریاضیدانان شاغل قبلاً با این شی درخشان برخورد کرده بودند و آن را طلای احمق تشخیص داده بودند. .

گیلمر گفت: «راستش، من کمی تعجب کردم که هیچ‌کس قبلاً به این موضوع فکر نکرده بود. "اما شاید نباید تعجب کنم، زیرا خودم یک سال در مورد آن فکر کرده بودم و تئوری اطلاعات را می دانستم."

بیشتر احتمال دارد تا نه

گیلمر شب‌ها، پس از پایان کارش در گوگل و آخر هفته‌ها در نیمه دوم اکتبر و اوایل نوامبر روی این مشکل کار کرد. او با ایده هایی که گروهی از ریاضیدانان سال ها قبل در سال های قبل به بررسی آن پرداخته بودند، تشویق شد همکاری باز در وبلاگ یک ریاضیدان برجسته به نام تیم گورز. او همچنین با یک کتاب درسی در کنارش کار می کرد تا بتواند فرمول هایی را که فراموش کرده بود جستجو کند.

"شما فکر می کنید کسی که به یک نتیجه عالی می رسد نباید به فصل 2 مراجعه کند عناصر نظریه اطلاعاتگیلمر گفت، اما من انجام دادم.

استراتژی گیلمر این بود که یک خانواده بسته به اتحادیه را تصور کند که در آن هیچ عنصری حتی در 1٪ از کل مجموعه ها ظاهر نمی شود - مثالی متضاد که اگر واقعا وجود داشت، حدس فرانکل را جعل می کرد.

فرض کنید دو مجموعه A و B را به طور تصادفی از این خانواده انتخاب کرده و عناصری را که می‌توانند در آن مجموعه‌ها باشند، یکی یکی در نظر بگیرید. حال بپرسید: چه شانسی وجود دارد که مجموعه A دارای عدد 1 باشد؟ و مجموعه B؟ از آنجایی که هر عنصر کمی کمتر از 1% شانس دارد که در هر مجموعه مشخصی ظاهر شود، انتظار ندارید A و B حاوی 1 باشند. این بدان معناست که اگر بدانید که هیچ یک از این دو در واقع هیچ یک از آنها شگفت‌انگیز نیست - و اطلاعات کمی به دست می‌آید. میکند.

در مرحله بعد، در مورد احتمال اینکه اتحاد A و B حاوی 1 باشد فکر کنید. این احتمال هنوز بعید است، اما احتمال آن بیشتر از شانس است که در هر یک از مجموعه های فردی ظاهر شود. این مجموع احتمال ظاهر شدن آن در A و احتمال ظاهر شدن آن در B منهای احتمال ظاهر شدن در هر دو است. بنابراین، شاید فقط کمتر از 2٪.

این هنوز کم است، اما به پیشنهاد 50-50 نزدیکتر است. این بدان معناست که برای به اشتراک گذاشتن نتیجه به اطلاعات بیشتری نیاز است. به عبارت دیگر، اگر یک خانواده بسته‌شده اتحادیه وجود داشته باشد که در آن هیچ عنصری در حداقل ۱٪ از همه مجموعه‌ها ظاهر نشود، اطلاعات در اتحاد دو مجموعه بیشتر از هر یک از خود مجموعه‌ها است.

ایده آشکار کردن چیزها عنصر به عنصر و نگاه کردن به مقدار اطلاعاتی که یاد می گیرید بسیار هوشمندانه است. این ایده اصلی اثبات است رایان الوایس از دانشگاه پرینستون

در این مرحله گیلمر شروع به نزدیک شدن به حدس فرانکل کرد. به این دلیل که نشان دادن این موضوع آسان است که در یک خانواده بسته اتحادیه، اتحاد دو مجموعه لزوماً حاوی اطلاعات کمتری نسبت به خود مجموعه ها است - نه بیشتر.

برای اینکه بفهمید چرا، به آن خانواده بسته‌شده اتحادیه فکر کنید که شامل 1,024 مجموعه مختلف است که می‌توانید از اعداد 1 تا 10 بسازید. اگر دو تا از این مجموعه‌ها را به‌طور تصادفی انتخاب کنید، به‌طور متوسط ​​به مجموعه‌هایی با پنج عنصر خواهید رسید. (از این 1,024 مجموعه، 252 شامل پنج عنصر است، که این اندازه مجموعه رایج‌ترین اندازه است.) همچنین احتمالاً در نهایت به یک اتحادیه حاوی حدود هفت عنصر خواهید رسید. اما تنها 120 روش مختلف برای ساخت مجموعه های حاوی هفت عنصر وجود دارد.

نکته این است که عدم قطعیت در مورد محتوای دو مجموعه به طور تصادفی انتخاب شده بیشتر از اتحاد آنها وجود دارد. این اتحادیه به مجموعه های بزرگتر با عناصر بیشتر گرایش پیدا می کند که امکانات کمتری برای آنها وجود دارد. هنگامی که شما دو مجموعه را در یک خانواده بسته شده انتخاب می کنید، به نوعی می دانید که قرار است چه چیزی به دست آورید - مانند زمانی که یک سکه مغرضانه را ورق می زنید - به این معنی که اتحادیه حاوی اطلاعات کمتری نسبت به مجموعه هایی است که از آنها تشکیل شده است.

با آن، گیلمر یک مدرک داشت. او می‌دانست که اگر هیچ عنصری حتی در 1 درصد مجموعه‌ها ظاهر نشود، اتحادیه مجبور می‌شود اطلاعات بیشتری داشته باشد. اما اتحادیه باید حاوی اطلاعات کمتری باشد. بنابراین باید حداقل یک عنصر وجود داشته باشد که حداقل در 1٪ از مجموعه ها ظاهر شود.

فشار به 50

وقتی گیلمر مدرک خود را در 16 نوامبر پست کرد، یادداشتی را اضافه کرد که فکر می‌کرد می‌توان از روش خود برای نزدیک‌تر شدن به اثبات حدس کامل استفاده کرد و به طور بالقوه آستانه را به 38 درصد افزایش داد.

پنج روز بعد، سه مختلف گروه از ریاضیدانان مقالاتی را در عرض چند ساعت از یکدیگر ارسال کردند که بر اساس کار گیلمر برای انجام این کار ساخته شده بود. اضافی اوراق به دنبالاما به نظر می‌رسد که انفجار اولیه روش‌های گیلمر را تا آنجا که پیش خواهند برد، برد. رسیدن به 50 درصد احتمالاً به ایده های جدید بیشتری نیاز دارد.

با این حال، برای برخی از نویسندگان مقالات بعدی، رسیدن به 38 درصد نسبتاً ساده بود، و آنها متعجب بودند که چرا گیلمر این کار را خودش انجام نداده است. ساده‌ترین توضیح درست بود: پس از بیش از نیم دهه دوری از ریاضی، گیلمر نمی‌دانست چگونه برخی از کارهای تحلیلی فنی را که برای انجام آن لازم است انجام دهد.

گیلمر گفت: "من کمی زنگ زده بودم، و صادقانه بگویم، گیر کرده بودم." "اما من مشتاق بودم ببینم جامعه آن را به کجا خواهد برد."

با این حال، گیلمر فکر می‌کند همان شرایطی که او را از تمرین کنار گذاشت، احتمالاً در وهله اول اثبات او را ممکن کرد.

او گفت: «این تنها راهی است که می‌توانم توضیح دهم که چرا یک سال در مقطع تحصیلات تکمیلی به این مسئله فکر کردم و هیچ پیشرفتی نداشتم، شش سال ریاضی را ترک کردم، سپس به مسئله بازگشتم و به این پیشرفت دست یافتم. من نمی‌دانم چگونه آن را توضیح دهم جز اینکه حضور در یادگیری ماشینی باعث تعصب تفکر من شده است.»

اصلاح: ژانویه 3، 2023
تیتر اصلی از گیلمر به عنوان «مهندس گوگل» یاد می‌کرد. در واقع او یک محقق است.