Математики спростували гіпотезу щодо двоярусного ліжка.

Препринт статті опубліковано в електронному архіві arXiv.org. Гіпотеза про двоярусне ліжко стосується теорії перколяції — розділу математики, що вивчає виникнення зв'язаних структур в незалежних середовищах. У 1980-х роках її запропонував голландський фізик Пітер Кастелейн: він хотів математично описати, як рідини просочуються через пористі поверхні, наприклад, як вода заповнює губку.

Гіпотеза базується на випадкових з'єднаннях вершин в уявному графі, схожому на двоярусне ліжко. Вона стверджує, що ймовірність виникнення зв'язку між двома вершинами на одному рівні вища, ніж ймовірність зв'язку між рівнями.

Це твердження інтуїтивно здається правильним, однак до недавнього часу не було знайдено переконливого доказу, який би підтвердив або спростував його. Скептики вважали, що твердження має занадто загальний характер і не може бути вірним для всіх випадків.

Частіше за все в математиці намагаються знайти доказ вірності твердження, лише зрідка робота спрямована на спростування. Але команда математиків з Росії — Ігор Пак, Микита Гладков і Олександр Зімін — змогла знайти контрприклад, який зруйнував гіпотезу.

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

Спочатку команда намагалася знайти контрприклад за допомогою методів машинного навчання. Дослідники навчили нейромережу знаходити можливі зв'язки в графах і намагалися перебрати всі варіанти. Однак для графів, у яких було більше дев'яти вершин, кількість можливих варіантів зв'язків стрімко зростала, і масштаб задачі швидко перевищив можливості аналізу. Доказ не було знайдено.

Тоді вони адаптували методи гіперграфів, для яких вже існувало спростування гіпотези двоярусного ліжка, до класичних графів і побудували дуже складну структуру, що містила тисячі вершин і ребер. У отриманому графі ймовірність зв'язку між верхнім і нижнім рівнями виявилася трохи більшою, ніж ймовірність зв'язку на нижньому рівні, що й дозволило зруйнувати гіпотезу.

«Ми з співавторами, Ігорем Паком і Микитою Гладковим, які зараз працюють в UCLA, відмінно доповнювали одне одного в цій задачі. Я надаю перевагу використанню числових методів. На мій погляд, щоб добре зрозуміти задачу, потрібно вміти її запрограмувати, пояснити комп'ютеру. А ось Микита вважає інакше і надає перевагу спиратися на більш абстрактний, інтуїтивний рівень», — розповідає один з авторів статті, аспірант факультету математики НІУ ВШЕ Олександр Зімін.

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

Знайдений контрприклад ставить перед наукою фундаментальні питання про те, чи можна покладатися на інтуїцію, наскільки важливий критичний підхід в математиці, а також в цілому про інтерпретацію доказів, основаних на ймовірнісних даних.