Вступ
В середині жовтня, Джастін Гілмер прилетів із Каліфорнії до Нью-Йорка, щоб відвідати весілля друга. Перебуваючи на східному узбережжі, він відвідав свого колишнього радника, Майкл Сакс, математик з Ратгерського університету, де Гілмер сім років тому отримав докторський ступінь.
Сакс і Гілмер зустрілися за обідом, але вони не говорили про математику. Насправді Гілмер не думав серйозно про математику з моменту закінчення навчання в Rutgers у 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-х роках математики обговорювали версії гіпотези про замкнутість об’єднань, але перше офіційне формулювання вона отримала в 1979 році в статті Петер Франкл, угорський математик, який емігрував до Японії у 1980-х роках і вважає вуличні виступи одним із своїх занять.
Франкл припустив, що якщо сімейство множин замкнене на об’єднання, воно повинно мати принаймні один елемент (або число), який з’являється принаймні в половині множин. Це був природний поріг з двох причин.
По-перше, є легкодоступні приклади замкнутих сімейств, у яких усі елементи присутні рівно в 50% множин. Як і всі різні набори, які ви можете складати, наприклад, із числами від 1 до 10. Існує 1,024 таких множини, які утворюють замкнуту сім'ю, і кожен з 10 елементів входить до 512 з них. І по-друге, у той час, коли Франкл висунув гіпотезу, ніхто ніколи не навів прикладу сім’ї, замкнутої на союз, у якій ця гіпотеза не виконувалася.
Тож 50% здавалося правильним прогнозом.
Це не означало, що це було легко довести. За роки, що минули після статті Франкла, було мало результатів. До роботи Гілмера в цих роботах вдалося лише встановити порогові значення, які змінювалися залежно від кількості наборів у сімействі (на відміну від того самого порогу в 50% для сімей наборів усіх розмірів).
«Здається, що це повинно бути легко, і це схоже на багато легких проблем, але воно протистоїть атакам», — сказав Вілл Савін Колумбійського університету.
Відсутність прогресу відображала як складну природу проблеми, так і той факт, що багато математиків воліли не думати про неї; вони хвилювалися, що втратять роки своєї кар’єри, гонившись за оманливою проблемою, яку неможливо вирішити. Ґілмер пам’ятає день у 2013 році, коли він зайшов до офісу Сакса й висловив гіпотезу про замкнутість об’єднання. Його радник — який у минулому сам боровся з цією проблемою — мало не вигнав його з кімнати.
«Майк сказав: Джастіне, ти знову змусиш мене думати про цю проблему, і я не хочу цього робити», — сказав Гілмер.
Розуміння невизначеності
Після свого візиту до Ратгерса Гілмер подумав про проблему, намагаючись зрозуміти, чому це було так важко. Він підказав собі основний факт: якщо у вас є сім’я з 100 наборів, є 4,950 різних способів вибрати двох і об’єднати їх. Тоді він запитав себе: як можливо, що 4,950 різних об’єднань відображаються лише на 100 наборах, якщо жоден елемент не з’являється в цих об’єднаннях принаймні з деякою частотою?
Навіть у той момент він був на шляху до доказу, хоча він ще не знав цього. Техніки з теорії інформації, яка забезпечує точний спосіб мислення про те, чого очікувати, коли ви навмання витягуєте пару об’єктів, приведуть його туди.
Теорія інформації була розроблена в першій половині 20-го століття, найвідоміша стаття Клода Шеннона 1948 року:Математична теорія комунікації.” Документ забезпечив точний спосіб розрахунку кількості інформації, необхідної для надсилання повідомлення, на основі кількості невизначеності щодо того, що саме міститиметься в повідомленні. Це посилання — між інформацією та невизначеністю — було чудове фундаментальне розуміння Шеннона.
Для прикладу іграшки уявіть, що я кидаю монету п’ять разів і надсилаю вам отриману послідовність. Якщо це звичайна монета, для її передачі потрібно п’ять біт інформації. Але якщо це завантажена монета — скажімо, 99% імовірності впаде на голови — потрібно набагато менше. Наприклад, ми могли б заздалегідь домовитися, що я надішлю вам 1 (єдиний біт інформації), якщо завантажена монета випаде головами всі п’ять разів, що дуже ймовірно. У результаті чесного підкидання монети більше здивування, ніж у упередженого, а отже, більше інформації.
Те саме мислення стосується інформації, що міститься в наборах чисел. Якщо я маю сімейство об’єднаних множин — скажімо, 1,024 множини, складені з чисел від 1 до 10 — я міг би навмання вибрати дві множини. Тоді я міг би повідомити вам елементи кожного набору. Обсяг інформації, необхідний для надсилання цього повідомлення, відображає кількість невизначеності щодо того, що це за елементи: існує, наприклад, 50% ймовірність того, що перший елемент у першому наборі є 1 (оскільки 1 з’являється в половині наборів у сім’я), так само як імовірність 50%, що першим результатом у послідовності чесних підкидань монети є голови.
Теорія інформації часто з’являється в комбінаториці, галузі математики, пов’язаної з підрахунком об’єктів, яку Гілмер вивчав, будучи аспірантом. Але коли він повертався додому до Каліфорнії, він хвилювався, що спосіб, яким він думав пов’язати теорію інформації з гіпотезою про закритий союз, був наївним прозрінням дилетанта: напевно, працюючим математикам натрапляв раніше на цей блискучий об’єкт і визнавав його золотом дурня. .
«Чесно кажучи, я трохи здивований, що ніхто не подумав про це раніше», — сказав Гілмер. «Але, можливо, мені не варто дивуватися, тому що я сам думав про це протягом року, і я знав теорію інформації».
Швидше, ніж ні
Гілмер працював над проблемою вночі, після закінчення роботи в Google, і у вихідні протягом другої половини жовтня і початку листопада. Його надихнули ідеї, які група математиків досліджувала багато років тому в відкрита співпраця на блозі видатного математика на ім'я Тім Гауерс. Він також працював з підручником, щоб знайти формули, які він забув.
«Можна подумати, що хтось, хто досяг чудового результату, не повинен звертатися до розділу 2 Елементи теорії інформації, але я зробив", - сказав Гілмер.
Стратегія Ґілмера полягала в тому, щоб уявити замкнуту на об’єднання сім’ю, в якій жодного елемента не було навіть у 1% усіх множин — контрприклад, який, якби він справді існував, фальсифікував би гіпотезу Франкла.
Припустімо, ви навмання вибираєте два набори, A і B, із цієї родини та розглядаєте елементи, які можуть бути в цих наборах, по одному. Тепер запитайте: яка ймовірність того, що набір A містить число 1? А набір B? Оскільки ймовірність того, що кожен елемент з’явиться в будь-якому заданому наборі, становить трохи менше 1%, ви не очікуєте, що А або В містять 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% було відносно просто, і вони дивувалися, чому Гілмер просто не зробив цього сам. Найпростіше пояснення виявилося правильним: після того, як більше ніж півдесяти років не займався математикою, Гілмер просто не знав, як виконати певну технічну аналітичну роботу, необхідну для цього.
«Я був трохи іржавим, і, чесно кажучи, я застряг», — сказав Гілмер. «Але я дуже хотів побачити, куди це приведе спільнота».
Проте Гілмер вважає, що ті самі обставини, які залишили його поза практикою, ймовірно, зробили його доказ можливим.
«Це єдиний спосіб, яким я можу пояснити, чому я думав про проблему протягом року в аспірантурі і не досяг успіху, я залишив математику на шість років, а потім повернувся до проблеми і зробив цей прорив», — сказав він. «Я не знаю, як це пояснити, крім того, що машинне навчання упередило моє мислення».
виправлення: Січень 3, 2023
У оригінальному заголовку Гілмер називався «інженер Google». Насправді він дослідник.
