«Команда A» з математики доводить важливий зв’язок між додаванням і множинами | Журнал Quanta

У навмання обраному наборі чисел додавання може стати диким.

Додайте кожну пару з такого набору, і ви отримаєте новий список, який, імовірно, матиме набагато більше чисел, ніж те, з якого ви почали. Почніть з 10 випадкових чисел, і цей новий список (званий сумою) матиме близько 50 елементів. Почніть зі 100, і сума, ймовірно, матиме близько 5,000; 1,000 випадкових початкових чисел дають суму 500,000 XNUMX чисел.

Але якщо ваш початковий набір має структуру, підсумковий набір може мати менше чисел, ніж це. Розглянемо інший набір із 10 чисел: усі парні числа від 2 до 20. Оскільки різні пари в сумі дають одне й те саме число — 10 + 12 — це те саме, що 8 + 14 і 6 + 16 — сума складається лише з 19 чисел, а не 50. Ця різниця стає все більш і більш глибокою, оскільки набори стають більшими. Структурований список із 1,000 чисел може мати підсумковий набір лише з 2,000 чисел.

У 1960-х роках математик ім Грегорі Фрейман почав досліджувати множини з невеликими множинами, намагаючись дослідити зв’язок між додаванням і структурою множини — важливий зв’язок, який визначає математичне поле адитивної комбінаторики. Фрейман досяг вражаючого прогресу, довівши, що множина з маленькою сумою повинна міститися у більшій множині, елементи якої розташовані у дуже регулярному шаблоні. Але потім поле застоїлося. «Початковий доказ Фреймана було надзвичайно важко зрозуміти, до того моменту, коли ніхто не був абсолютно впевнений у його правильності. Тож це справді не мало такого впливу, який могло б мати», — сказав Тімоті Гауерс, математик у Колеж де Франс і Кембриджському університеті та лауреат Філдсової медалі. "Але з іншого боку Імре Ружа вирвався на сцену».

У серії два документи у 1990-х роках Руза повторно довів теорему Фреймана новим елегантним аргументом. Через кілька років, Каталін Мартон, впливовий угорський математик, який помер у 2019 році, змінив питання про те, що означає мала сума на структурі вихідної множини. Вона замінила типи елементів, які з’явилися в наборі, і тип структури, яку математики повинні шукати, вважаючи, що це дозволить математикам отримати ще більше інформації. Гіпотеза Мартона пов'язана з системами доказів, теорією кодування та криптографією, і займає високе місце в адитивній комбінаториці.

Її припущення «здається справді однією з найпростіших речей, яких ми не розуміли», — сказала вона Бен Грін, математик Оксфордського університету. Це «просто підкреслило багато речей, які мене хвилюють».

Грін об'єднав зусилля з Гауерсом, Фредді Меннерс Університету Каліфорнії, Сан-Дієго, і Теренс Дао, медаліст Філдса в Каліфорнійському університеті в Лос-Анджелесі, щоб сформувати те, що ізраїльський математик і блогер Гіл Калай називається "Команда» математиків. Вони довели версію гіпотези в статті поділився 9 листопада.

Нетс Кац, математик з Університету Райса, який не брав участі в роботі, описує доказ як «прекрасно простий» — і «більш-менш абсолютно несподівано».

Тоді Тао розпочав спробу формалізувати доказ Нахиліться, мова програмування, яка допомагає математикам перевіряти теореми. Лише за кілька тижнів ця спроба вдалася. Рано вранці у вівторок 5 грудня — оголосив Тао що Lean довів гіпотезу без будь-яких «вибачте» — стандартного твердження, яке з’являється, коли комп’ютер не може перевірити певний крок. Це найпопулярніше використання такого інструменти перевірки з 2021 року, і позначає точку перегину в тому, як математики пишуть докази в термінах, зрозумілих комп’ютеру. Якщо ці інструменти стануть достатньо простими для використання математиками, вони зможуть замінити часто тривалий і обтяжливий процес експертної оцінки, сказав Гауерс.

Інгредієнти доказу кипіли десятиліттями. Гауерс задумав свої перші кроки на початку 2000-х. Але знадобилося 20 років, щоб довести те, що Калай назвав «святим Граалем» цієї галузі.

Внутрішня група

Щоб зрозуміти гіпотезу Мартона, корисно ознайомитися з поняттям групи, математичного об’єкта, який складається з множини та операції. Подумайте про цілі числа — нескінченний набір чисел — і операцію додавання. Кожного разу, коли ви додаєте два цілі числа, ви отримуєте інше ціле число. Додавання також підпорядковується декільком іншим правилам групових операцій, наприклад асоціативності, яка дозволяє змінювати порядок операцій: 3 + (5 + 2) = (3 + 5) + 2.

Усередині групи іноді можна знайти менші набори, які задовольняють усі властивості групи. Наприклад, якщо додати будь-які два парні числа, ви отримаєте інше парне число. Парні числа є окремою групою, що робить їх підгрупою цілих чисел. Непарні числа, навпаки, не є підгрупою. Якщо скласти два непарних числа, ви отримаєте парне число — не в оригінальному наборі. Але ви можете отримати всі непарні числа, просто додавши 1 до кожного парного числа. Подібна зміщена підгрупа називається косетом. Вона не має всіх властивостей підгрупи, але багато в чому зберігає структуру своєї підгрупи. Наприклад, як і парні числа, непарні числа розташовані рівномірно.

Мартон припустив, що якщо у вас є набір, то ми подзвонимо A складається з групових елементів, сума яких не набагато більша ніж A сама, то існує якась підгрупа — назв G — з особливою властивістю. Shift G кілька разів, щоб зробити сумісники, і разом узяті ці сумки міститимуть вихідний набір A. Крім того, вона припустила, що кількість сумісних класів не зростає набагато швидше, ніж розмір сумарної сукупності — вона вважала, що це має бути пов’язане поліноміальним фактором, на відміну від набагато швидшого експоненціального зростання.

Це може здатися дуже технічною цікавістю. Але оскільки це пов’язано з простим тестом — що станеться, коли ви додасте лише два елементи до набору? — для загальної структури підгрупи це дуже важливо для математиків і комп’ютерників. Та сама загальна ідея з’являється, коли комп’ютерники намагаються зашифрувати повідомлення, щоб ви могли декодувати лише частину повідомлення за раз. Він також з’являється в імовірнісно перевірених доказах, формі доказів, які інформатики можуть перевірити, перевіряючи лише кілька окремих бітів інформації. У кожному з цих випадків ви працюєте лише з кількома пунктами в структурі — декодуючи лише кілька бітів із довгого повідомлення або перевіряючи невелику частину складного доказу — і робите висновок про більшу структуру вищого рівня.

«Ви можете або вдавати, що все є великою підмножиною групи», — сказав Том Сандерс, колишній студент Гауерса, який зараз є колегою Ґріна в Оксфорді, або ви можете «отримати все, що хотіли, завдяки існуванню багатьох адитивних збігів. Обидва ці погляди корисні».

Ружа опублікував гіпотезу Мартона в 1999 році, віддаючи їй повну заслугу. «Вона прийшла до цієї гіпотези незалежно від мене і Фреймана і, можливо, до нас», — сказав він. «Ось чому, коли я з нею розмовляв, я вирішив назвати це її припущенням». Тим не менш, математики тепер називають це поліноміальною гіпотезою Фреймана-Руззи, або PFR.

Нулі та одиниці

Групи, як і багато інших математичних об’єктів, мають багато різних форм. Мартон припускала, що її гіпотеза справедлива для всіх груп. Це ще належить показати. Нова стаття доводить це для певного типу групи, яка приймає як елементи списки двійкових чисел, наприклад (0, 1, 1, 1, 0). Оскільки комп’ютери працюють у двійковому форматі, ця група має вирішальне значення в інформатиці. Але це також було корисно в адитивній комбінаториці. «Це схоже на іграшкову обстановку, в якій можна щось пограти та спробувати», — сказав Сандерс. «Алгебра набагато, набагато приємніша», ніж робота з цілими числами, додав він.

Списки мають фіксовану довжину, і кожен біт може дорівнювати 0 або 1. Ви додаєте їх разом, додаючи кожен запис до його відповідника в іншому списку за правилом, що 1 + 1 = 0. Отже (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR — це спроба з’ясувати, як може виглядати набір, якщо він не зовсім підгрупа, але має деякі групові особливості.

Щоб зробити PFR точним, уявіть, що у вас є набір двійкових списків A. Тепер візьміть кожну пару елементів з A і складіть їх. Отримані суми складають суму A, Називаний A + A. Якщо елементи в A вибираються випадково, то більшість сум відрізняються одна від одної. Якщо є k елементи в A, це означає, що навколо буде k²/2 елементи в сумі. Коли k великий — скажімо, 1,000 — k²/2 набагато більше, ніж k. Але якщо A є підгрупою, кожен елемент A + A В A, що означає, що A + A такого ж розміру, як A себе.

PFR розглядає набори, які не є випадковими, але також не є підгрупами. У цих множинах кількість елементів в A + A є дещо малим — скажімо, 10kАбо 100k. «Це дуже корисно, коли ваше уявлення про структуру набагато багатше, ніж просто точна алгебраїчна структура», — сказав Шачар Ловетт, комп’ютерний науковець з Каліфорнійського університету в Сан-Дієго.

Усі відомі математикам множини, які підкоряються цій властивості, «досить близькі до справжніх підгруп», — сказав Тао. «Це була інтуїція, що не було ніяких інших фальшивих груп». Фрейман довів версію цього твердження у своїй оригінальній роботі. У 1999 році Руза розширив теорему Фреймана з цілих чисел на встановлення двійкових списків. Він довів що коли кількість елементів в A + A є постійним кратним розміру A, A міститься в підгрупі.

Але теорема Рузи вимагала, щоб підгрупа була величезною. Ідея Мартона полягала в тому, що замість того, щоб міститися в одній гігантській підгрупі, A може міститися в поліноміальному числі сумісних класів підгрупи, яка не більша за початковий набір A.

«Я знаю реальну ідею, коли бачу реальну ідею»

Приблизно на рубежі тисячоліть Гауерс наткнувся на докази Рузси теореми Фреймана під час вивчення іншої проблеми про множини, що містять рядки рівномірно розташованих чисел. «Мені потрібно було щось на кшталт цього, якби отримати структурну інформацію з набагато меншої інформації про певний набір», — сказав Гауерс. «Мені дуже пощастило, що незадовго до цього Руза представила цей абсолютно чудовий доказ».

Гауерс почав розробляти потенційний доказ поліноміальної версії гіпотези. Його ідея полягала в тому, щоб почати з набору A сума яких була відносно невеликою, потім поступово маніпулювати A в підгрупу. Якби він міг довести, що отримана підгрупа була подібна до вихідної множини A, він міг легко зробити висновок, що припущення вірне. Гауерс поділився своїми ідеями з колегами, але ніхто не міг втілити їх у повний доказ. Хоча в одних випадках стратегія Гауерса була успішною, в інших маніпуляції виявилися непоганими A далі від бажаного висновку поліноміальної гіпотези Фреймана-Руззи.

Згодом поле зрушило з місця. У 2012 році Сандерс майже довів ПФР. Але необхідна йому кількість зміщених підгруп була вище поліноміального рівня, хоча й трохи. «Коли він зробив це, це означало, що це стало менш терміновою справою, але все одно справді гарною проблемою, до якої я дуже люблю», — сказав Гауерс.

Але ідеї Гауерса жили в пам’яті та на жорстких дисках його колег. «Тут є справжня ідея», — сказав Грін, який також був учнем Гауерса. «Я знаю справжню ідею, коли бачу реальну ідею». Цього літа Грін, Меннерс і Тао нарешті звільнили ідеї Гауерса з чистилища.

Грін, Тао і Меннерс співпрацювали на 37 сторінках, перш ніж задумали повернутися до ідей 20-річної давності Гауерса. У 23 червня папір, вони успішно використали концепцію з теорії ймовірностей, яка називається випадковими змінними, щоб дослідити структуру множин із малими сумами. Зробивши цей перемикач, група могла маніпулювати своїми наборами з більшою тонкістю. «Робота з випадковими змінними дещо менш жорстка, ніж робота з наборами», — сказав Меннерс. За допомогою випадкової змінної «я можу трохи змінити одну з ймовірностей, і це може дати мені кращу випадкову змінну».

Використовуючи цю імовірнісну перспективу, Грін, Меннерс і Тао могли перейти від роботи з кількістю елементів у наборі до вимірювання інформації, що міститься у випадковій змінній, величині, яка називається ентропією. Ентропія не була новим для адитивної комбінаторики. Справді, Тао намагався для популяризації концепції наприкінці 2000-х років. Але ніхто ще не намагався використати його на поліноміальній гіпотезі Фреймана-Руззи. Грін, Меннерс і Тао виявили, що він потужний. Але вони так і не змогли довести цю гіпотезу.

Коли група розглядала свої нові результати, вони зрозуміли, що нарешті створили середовище, в якому могли б процвітати бездіяльні ідеї Гауерса. Якби вони вимірювали розмір набору, використовуючи його ентропію, а не кількість елементів, технічні деталі могли б працювати набагато краще. «У якийсь момент ми зрозуміли, що ці старі ідеї Тіма 20-річної давності насправді спрацюють з більшою ймовірністю, ніж ті, які ми пробували», — сказав Тао. «І тому ми повернули Тіма до проекту. І тоді всі деталі напрочуд гарно поєднуються».

І все-таки потрібно було з’ясувати багато деталей, перш ніж зібратися докази. «Це була якась дурість, що ми всі четверо були неймовірно зайняті іншими справами», — сказав Меннерс. «Ви хочете опублікувати цей чудовий результат і розповісти про це світові, але насправді вам все одно потрібно написати проміжні тести». Зрештою група проштовхнула свою роботу і 9 листопада опублікувала свою статтю. Вони довели, що якщо A + A не більше ніж k рази більше розміру A, То A може бути покрито не більше ніж о k¹² зрушення підгрупи, яка не перевищує A. Це потенційно величезна кількість змін. Але це поліном, тому він не зростає експоненціально швидше, ніж k стає більшим, як це було б, якби k були в експоненті.

Через кілька днів Тао почав формалізуйте доказ. Він спільно керував проектом формалізації, використовуючи пакет керування версіями GitHub для координації внесків від 25 волонтерів по всьому світу. Використовували інструмент під назвою План розроблений Патрік Массо, математик з Університету Париж-Сакле, щоб організувати зусилля з перекладу з того, що Дао званий «Математична англійська мова» в комп’ютерний код. Blueprint може, серед іншого, створити a намітити зображуючи різні логічні етапи доказу. Коли всі бульбашки були вкриті тим, що Тао назвав «чудовим зеленим відтінком», команда закінчила роботу. Вони виявили кілька дуже незначних помилок у газеті — в Інтернеті повідомлення, Тао зазначив, що «найбільш цікаві з математичної точки зору частини проекту було відносно легко формалізувати, але найдовше зайняли технічні «очевидні» кроки».

Мартон померла всього за кілька років до того, як її знаменита гіпотеза була доведена, але докази повторюють її справа життя з ентропії та теорії інформації. «Усе працює набагато краще, коли ви робите це в цій системі ентропії, ніж у структурі, яку я намагався зробити», — сказав Гауерс. «Мені це все ще здається дещо магічним».

Quanta проводить серію опитувань, щоб краще обслуговувати нашу аудиторію. Візьміть наші опитування читачів з математики і ви будете введені, щоб виграти безкоштовно Quanta мерч.