Двое молодых математиков ошеломили коллег, представив полное доказательство гипотезы Кана-Калаи — обобщающее утверждение о том, как возникает структура в случайных множествах и графах.
Когда математики Джефф Кан и Гиль Калаи в 2006 году впервые выдвинули свою гипотезу о «пороге ожидания», они сами в нее не поверили. Их тезис – широкое утверждение о природе математических объектов, именуемых «случайными графами» — казался слишком категоричным, слишком всеобъемлющим, слишком смелым, чтобы претендовать на истинность. Казалось, что он скорее выдает желаемое за действительное, чем отражает математическую истину. Даже с такими оговорками, никто не смог опровергнуть эту гипотезу, и она быстро стала одной из важнейших нерешенных задач в своей области.
Теперь, более 15 лет спустя, двое молодых математиков из Стэнфордского университета сделали то, что, по мнению Кана и Калаи, граничит с невозможным. В на удивление кратком препринте, выложенном в онлайне всего несколько недель назад, Джинён Пак и Гью Туан Фам дали полное доказательство этой гипотезы.
«Оно получилось поразительно простым и изобретательным», — сказал Калаи, — «Завораживающим. Чудесным».
Полученный результат автоматически доказывает сотни более специфичных утверждений, каждое из которых с большим трудом поддавалось бы доказательству само по себе — и влечет с собой еще более глубокие следствия для нашего понимания случайных графов и математических множеств в более широком смысле.
«Я бы назвал их доказательство волшебным», — сказал Джейкоб Фокс, стэнфордский математик, а также научный руководитель Фама, — «оно продвинет вперед значительную часть всей дисциплины».
Замораживаем граф
Гипотеза Кана-Калаи очень обширна и сформулирована на абстрактном языке множеств и их элементов – но, понять ее можно на достаточно простом примере. Для начала представьте граф: множество точек (вершин), соединенных линиями (ребрами). Чтобы сделать случайный граф, возьмем несимметричную монету – такую, что выпадает решкой в 1% случаев, или 30%, или с любым иным процентным соотношением от 0% до 100% - и подбросим ее единожды для каждой пары вершин. Если монета упадет решкой, соединим эти вершины ребром, если упадет орлом – не соединим. Повторим этот процесс для любых возможных пар вершин.
Математики заинтересовались, когда такой граф, вероятно, может обладать той или иной интересной структурой. Может быть, в нем образуется треугольник, а может быть — гамильтонов цикл; цепочка ребер, проходящая через каждую из вершин ровно один раз. Можно подумать о любом свойстве, до тех пор, пока оно идет с «нарастанием» — то есть, если при добавлении ребер в граф, уже обладающий данным свойством, данное свойство сохраняется.
Если вероятность падения монеты решкой невелика, то и ребра будут редки, а такие структуры как гамильтонов цикл, вряд ли возникнут. Но, если удастся настроить вероятность, то произойдет нечто странное. Каждое свойство обладает так называемым «порогом»: уровень вероятности, при котором возникает структура, зачастую – совершенно внезапно.
Точно как ледяные кристаллы начинают формироваться, как только температура упадет ниже нуля по Цельсию, вероятность возникновения некоторого свойства вдруг становится очень высокой по мере того, как все больше ребер добавляется в граф. Когда ребра добавляются в случайный граф с N вершин, с вероятностью, например, менее log(N)/N, в таком графе вряд ли возникнет гамильтонов цикл. Но, стоит откорректировать вероятность так, чтобы она была хотя бы чуточку выше log(N)/N, вероятность возникновения гамильтонова цикла становится крайне высокой.
Математики хотят определять такие пороговые уровни для различных свойств, представляющих интерес. «Возможно, пороги — самая фундаментальная вещь, которую мы пытаемся понять», — говорит Фокс, — «я рассматриваю случайный объект: обладает ли он интересующим меня свойством»? Но, тогда как такие пороговые значения уже вычислены для гамильтоновых циклов и некоторых других конкретных структур, в большинстве случаев по-прежнему очень затруднительно определить такой порог или даже уверенно оценить его.
Поэтому математики зачастую полагаются на более простое вычисление, дающее минимально возможное значение порога, то есть, его нижнюю границу. Этот «порог ожидания» в сущности, вычисляется взятием средневзвешенного значения. «Самое приятное с этим порогом ожидания — в том, что он очень легко вычисляется», — говорит Дэвид Конлон, математик из Калифорнийского технологического института, — «в принципе, всего в двух строках можно рассчитать порог ожидания практически для чего угодно».
Но средние значения бывают обманчивы. Так, для гамильтонова цикла порог ожидания равен 1/N, что гораздо ниже истинного значения log(N)/N, в log(N) раз.
В 2006 году Кан и Калаи постулировали, что это, на самом деле, наихудший сценарий. Согласно гипотезе, названной в их честь, разрыв между ожидаемым и истинным пороговым значением никогда не может превышать логарифмического множителя. По Конлону, эта гипотеза «в сущности, берет за основу центральный вопрос, касающийся случайных графов, и предлагает на него общий ответ».
Но это был всего лишь простой случай. Данная гипотеза актуальна далеко не только для случайных графов. Если она верна, то справедлива и для последовательностей случайных чисел, и для обобщений графов — так называемых гиперграфов, и даже для еще более обширных категорий систем. Вот почему Кан и Калаи сформулировали свое утверждение в терминах абстрактных множеств. Случайные графы – это всего лишь частный случай — случайный граф можно трактовать как случайное подмножество от множества всех возможных ребер — но есть и многочисленные иные объекты, попадающие в область применения этой гипотезы. «Странно, но, работая с графами, доказать ее в таком контексте было бы очень сложно», — говорит Конлон, — «но, именно в такой абстрактной постановке задачи каким-то образом раскрывается суть всей проблемы».
Утверждение Кана-Калаи казалось столь невероятным именно из-за своей всеохватности. «Это была очень смелая гипотеза», — сказал Шахар Ловетт, специалист по теоретической информатике из Калифорнийского университета в Сан-Диего. Во-первых, она мгновенно спрямила огромный фронт работ в комбинаторике — попытки рассчитать пороговые значения для различных свойств. «Вопросы, требовавшие, казалось бы, очень длинных и сложных доказательств, вдруг просто исчезли», — говорит Алан Фриз, математик из университета Карнеги-Меллона. — «Доказательства превратились просто в тривиальные варианты применения этой гипотезы».
Тот факт, что столь многие, казалось бы, несвязанные проблемы, удавалось уладить при помощи такой широкой гипотезы, казался многим математикам натяжкой. «Честно говоря, это казалось полным безумием», — сказал Конлон. Кан и Калаи, сформулировав свою гипотезу, не пытались ее доказать. Они занялись поиском контрпримера. Существовало так много постановок задачи, которые они могли бы исследовать, что, заключили эти ученые, рано или поздно они на такой пример наткнутся.
Но, как оказалось (это слова Калаи), «история стала развиваться по совсем иному сценарию», чем они ожидали.
Путеводный подсолнух
Методы, которые в итоге привели к новому доказательству гипотезы Кана-Калаи, начались с прорыва в решении, казалось бы, совсем иной задачи. Во многом эта история начинается с так называемой «гипотезы подсолнечника», сформулированной математиками Палом Эрдёшем и Рихардом Радо в 1960 году. В рамках этой гипотезы рассматривается, можно ли собирать совокупности множеств по принципу, напоминающему расположение лепестков подсолнуха.
В 2019 году Ловетт работал в составе команды, очень близко подобравшейся к полному решению задачи подсолнечника. На тот момент казалось, что эта работа никак не связана с гипотезой Кана-Калаи, которая оперирует вероятностными рассуждениями. «Я не вижу никакой связи с вашей гипотезой», — сказал Калаи. Не видел такой связи и Ловетт, признавший, что «мы не подозревали о том, что она касается иных вопросов. Нас интересовали подсолнечники».
Но Кан, Пак (на тот момент – докторантка Кана) и их коллеги в итоге смогли связать две эти задачи, когда, несколько месяцев спустя, попытались доказать облегченную версию гипотезы Кана-Калаи. (Их доказательство было опубликовано в журнале Annals of Mathematics в прошлом году). В этой облегченной версии, которую сформулировал французский математик Мишель Талагран, «порог ожидания» из гипотезы Кана-Калаи заменялся «дробным» порогом ожидания — в сущности, применялся иной способ взятия средневзвешенного значения. В пересмотренном определении «появляется больше пространства для маневра при работе», как выразился Ловетт.
Группа, в которой работали Кан и Пак, осознала: можно позаимствовать приемы, позволившие в 2019 году получить результат по гипотезе подсолнечника, скорректировать их и применить к гипотезе Талаграна. «Определенно, это послужило нам толчком», — сказал Кан.
Математики стали решать задачу итерационным методом. Они взялись показать, что, если выбрать случайное множество — скажем, случайный граф — то в нем будет структура, например, гамильтонов цикл. Но они решили выбирать такое случайное множество не сразу, а фрагмент за фрагментом, примерно так, как Ловетт и его коллеги подходили к гипотезе подсолнечника. «Мы итеративно выполняем своеобразный случайный процесс», — говорит Пак, — «пошагово выбираем ребро за ребром». И так, пока в них не соберется полный гамильтонов цикл.
Чтобы добиться этого, команда обратилась к понятию «разброс», характеризующему степень случайности. Если гамильтоновы циклы обладают хорошим «разбросом», это значит, что не так много циклов содержат одно и то же ребро или подмножество ребер. «Каким-то образом набор ребер разбросан в пространстве», — говорит Фам, — «он не демонстрирует особой кластеризации или концентрации в какой-либо части». Если циклы хорошо распределены таким образом, то процесс случайного поэлементного включения гарантированно позволит захватить как минимум один гамильтонов цикл, даже, если многие другие циклы будут при этом упущены.
Такой подход оказался возможен только благодаря критически важной эквивалентности: разброс можно квантифицировать таким способом, который напрямую соотносится с дробным порогом ожидания. Именно поэтому математикам удалось переписать гипотезу Талаграна в терминах разброса.
Занятно, что доказательства этой более слабой гипотезы хватило, чтобы решить целый вихрь задач, связанных с порогами. «Каждое следствие, которое, как нам известно, вытекает из полной гипотезы, также вытекает и из более слабой», — сказал Кан. Фактически, ему, Калаи и другим это подсказывало, что две гипотезы могут быть более или менее одинаковы, то есть, что значения дробных и исходных порогов ожидания были, в сущности, эквивалентны. Если бы кому-нибудь удалось доказать эту эквивалентность, то была бы доказана и гипотеза Кана-Калаи. «Я всегда думал, что единственный способ доказать нашу гипотезу — именно такой», — сказал Кан.
Но произошло нечто другое. Пока другие математики пытались придерживаться именно такого маршрута к полному доказательству гипотезы Калаи-Кана, Пак и Фам нашли совершенно новый подход. «Джинён и Гью нашли эту невероятно прямую, невероятно короткую линию доказательств, которая просто простреливает всю проблему», — сказал Конлон, — «и это экстраординарно. Я такого совершенно не ожидал».
Кан согласен. «Это одна из тех прелестных вещей, какие случаются в математике», — говорит он, — «вещи, казавшиеся нам безнадежными, оказываются не только небезнадежными, но даже несложными».
Удивительный подход
Поначалу ни Пак, ни Фам не планировали браться за исходную гипотезу. Пак, впервые узнавшая об этой задаче в аспирантуре, по ее словам, «смогла почувствовать красоту и силу этой гипотезы, но никогда и не думала, что сможет ее доказать».
«Мы этого совершенно не планировали», — добавляет Фам.
Напротив, они занимались другой гипотезой, сформулированной Талаграном, когда их, по словам Фама, «просто озарило». Они осознали, что «картина, которая здесь открывается перед нами, идеи, которые у нас есть, почему-то должны быть гораздо мощнее, чем кажутся». Эти идеи, рассудили они, вполне помогут пройти весь путь к доказательству гипотезы Кана-Калаи.
Всего за одну бессонную мартовскую ночь они сформулировали, как заставить это доказательство работать.
Нормальный порог ожидания, в отличие от дробного, никак не связан с разбросом. Разброс «дает отправную точку. И ты переходишь к исходной, недробной гипотезе, а та отправная точка просто исчезает»,— говорит Кан, — «так что все выглядело очень сурово».
«Что же делать в таком случае?», — сказал Фам, — «мы тогда просто взглянули на проблему под другим углом».
В частности, они стали размышлять над этой задачей в терминах математической сущности, именуемой «покрытием». Покрытие – это совокупность множеств, где каждый объект, обладающий определенным свойством, содержит одно из этих множеств. Например, одно из возможных покрытий всех гамильтоновых циклов — это совокупность всех ребер. Каждый гамильтонов цикл будет содержать одно из этих ребер.
Пак и Фам переписали гипотезу Калаи-Кана таким образом, который позволил им работать с покрытиями. В исходной версии гипотезы налагаются ограничения на то, какова должна быть вероятность падения симметричной монеты решкой, чтобы гарантировать, что случайный граф или множество будут содержать некоторое свойство. В частности, в ней говорится, что вероятность должна быть не менее порога ожидания для данного свойства, который умножен на логарифмический коэффициент. Пак и Фам перевернули ситуацию: если возникновение некоторого свойства маловероятно, то вероятность, присвоенная симметричной монете, будет ниже порога ожидания, умноженного на логарифмический коэффициент.
Тут в игру и вступают покрытия: когда для подмножества структур можно собрать небольшое покрытие (скажем, таким подмножеством может быть небольшой набор гамильтоновых циклов), это означает, что вклад данного подмножества в порог ожидания невелик. (Напомню: порог ожидания рассчитывается взятием средневзвешенного значения для всех возможных структур заданного типа). Поэтому, теперь Пак и Фаму требовалось показать, что, если в случайном множестве невелика вероятность присутствия искомой структуры, то для всех таких искомых структур должно существовать небольшое покрытие. Основная часть их доказательства посвящена сборке такого небольшого покрытия.
Они решили задачу при помощи пофрагментного сбора образцов – процесса, уже применявшегося при получении более ранних результатов, а также введя, как выразился Фокс, «очень умный аргумент подсчета». Неделю спустя после той бессонной мартовской ночи, они выложили свою изящную шестистраничную статью в Интернете.
«Их доказательство суперпростое. Они берут базовую идею, разработанную нами, а также идеи из других статей – и добавляют в нее небольшой вираж», — говорит Ловетт, — «и с этим новым виражом все значительно, значительно упрощается».
Фриз того же мнения. «Не могу этого объяснить, но, поразительно, тут все верно», — говорит он.
Гипотеза Кана-Калаи, верность которой уже доказана, точно как и дробный результат, автоматически подразумевает доказательство целой кучи смежных гипотез. Но, более того, «это мощная доказательная техника, которая может привести нас к множеству других вещей», — говорит Нога Эйлон, математик из Принстонского университета, — «главное, что они смогли сделать это как следует».
Пак и Фам уже начали применять свой метод к решению других задач. В частности, они стремятся точнее понять разрыв, отделяющий порог ожидания и реальный порог. Доказав гипотезу Кана-Калаи, они продемонстрировали, что этот разрыв обычно сопоставим с логарифмическим коэффициентом – но иногда гораздо меньше, а бывает, что его и нет. В настоящее время не существует более широкого механизма, позволившего бы классифицировать, в каких случаях каждый из этих сценариев может быть верен; математикам придется проработать его пример за примером. На данный момент «мы считаем, что, при помощи такой эффективной техники, можно надеяться, что удастся с гораздо более высокой точностью локализовать эти пороги», — говорит Фам.
А еще это доказательство может привести к совершенно иным следствиям. «Ведь гипотеза Кана-Калаи – совершенно не конец истории», — говорит Пак.
Комментарии (26)
Emulyator
01.05.2022 10:18+2Интересно, какой порог для свой свойства "сознание" в графе типа "мозг" )
Bedal
02.05.2022 22:44Вы под «сознанием» подразумеваете «разум»? Сейчас весьма устойчиво сошлись на «человек становится разумным, когда начинает думать словами». Эта формулировка явно верна, и к тому же хорошо описывает процедуру возникновения разума, да и пути возникновения нового тоже.
Emulyator
03.05.2022 12:09Есть исследования, есть гипотезы, философские подходы,.. много всего, но думаю, что не выйдет дать хорошее определение "сознанию", не имея четких представлений о его механизмах. Например, в случае "радуги" меня вполне устраивает описательное определение типа "разноцветная дуга в небе" без оглядки на физические механизмы, потому что она легко выделяется из окружающего мира. На интуитивном уровне мы также понимаем слово "сознание", но вот нет уверенности, что без понимания механизмов, можно четко определить границы явления, не всунуть в определение лишнего, не пропустить принципиально важное, или даже иметь убеждение, что явление существует в принципе. Думаю, что на данном этапе развития науки можно поставить на паузу споры и договоренностях об определениях, а активно исследовать механизмы психики, в том числе на виртуальных моделях.
Bedal
03.05.2022 17:58В подавляющем большинстве случаев принципиальное описание явления или сущности появляется задолго до того, как будут известны механизмы. Так что требование «четких представлений о его механизмах» не выглядит обоснованным.
Дальше — не диктую никаких абсолютных истин, но показываю логику рассуждений:
Исторически было проведено изрядное (увы) количество экспериментов по выращиванию детей без обучения языку (речи). Это и глухонемые, и намеренные эксперименты по выявлению «настоящего исходного языка», и аутисты, и маугли… Сумма всех этих наблюдений позволяет уверенно проводить границу разумности именно по наличию речи. И столь же уверенно можно утверждать, что человек, воспитанный вне языковой среды (язык любой, хотя бы жестовый или графический) — не разумен.
С другой стороны — все теплокровные в той или иной степени демонстрируют «разумные эпизоды», когда ведут себя и решают проблемы лучше даже присутствующих людей. Любой, кто внимательно относится к домашним животным или наблюдает диких животных и птиц, это подтвердит. Но это именно эпизоды, кратковременные и не связанные друг с другом. Чем развитее (в интуитивном понимании) животное — тем чаще эти эпизоды встречаются.
Итого, разумно :-) предположить, что разум — аппаратно-обеспеченные разумные эпизоды, связанные в единый непрерывный процесс речью. Соответственно, разум появляется именно в обществе. Когда отдельный человек начинает думать словами, он замыкает этот процесс «на себя» и становится индивидуально разумным.в том числе на виртуальных моделях.
Тут уже совсем моё, личное мнение:
Когда-нибудь устройства IoT станут достаточно «умными», по крайней мере с нейросетями (собственно, уже есть такие). Эти устройства, конечно, должны работать совместно, и обилие моделей и производителей, а также нечёткость входных и выходных данных нейросетей вынудит переходить от протоколов к языку обмена информацией. Вот тут и появится настоящий ИИ. А сделать его, какие суперкомпьютеры ни используй — не получится.
Sergey_Kovalenko
01.05.2022 11:17+5Звучит заманчиво. Может стать еще одной жемчужиной вроде основной теоремы алгебры или теоремы Уитни о погружении. Если бы я был юношей, то прочитав эту статью мне бы вновь захотелось связать свою жизнь с математикой. Надеюсь кто-нибудь в университетах оформит этот результат в какую-то доступную монографию, которая бы содержала все необходимое, чтобы ее прочесть не будучи специалистом данной конкретной проблемы.
Спасибо за перевод.
agalakhov
01.05.2022 15:07+1Очень напоминает обобщение теории перколяции. Мы на лекции порог перколяции для прямоугольной сетки выводили.
knstqq
01.05.2022 22:15+4не нашёл в статье ссылку на саму статью:
https://arxiv.org/abs/2203.17207
A Proof of the Kahn-Kalai Conjecture
phenik
Нифига не понятно, но интересно можно это применить к моделированию эволюционных процессов? Мутации случайны, но в целом направленность эволюции далеко не случайна.
RealSup
Если рассматривать на примере эволюции то гипотеза утверждает, что чем больше воздействий, тем больше вероятность эволюции для объекта, причем зависимость не линейная, а с пороговыми значениями. Так что ответ на ваш вопрос скорее нет чем да.
tzlom
Не с той стороны смотрите, пороговые значения означают что если в вашем поле посевной пшеницы будет 1% дикой то посевная не будет менять свои параметры при пересевах, а вот при условных 2% уже начнется дрейф генов. Пример от балды и скорее всего не верный, но как пример куда можно применить знания о порогах сойдёт.
phenik
У меня возникли ассоциации скорее с конвергентной эволюцией.
vsevolodB
Мутации случайны, но не случаен именно естественный отбор, который выражается в условиях обитания. Конечно, это несколько филосовский вопрос, но у эволюции нет направленности - это просто процесс изменений под внешними факторами.
phenik
v1000
Тут ещё одна интересная тема - если эволюция как последовательность мелких изменений под изменения внешней среды в принципе понятна, то как объяснить возникновение сложных структур, которые не могут возникнуть одномоментно из-за своей сложности, но при этом на каждом этапе своего формирования не приносят организму эволюционных преимуществ, а, скорее, наоборот.
phenik
Bedal
Это легко наблюдать в биологической эволюции и легко моделируется, хотя бы и программно. Достаточно исполнения пяти аксиом естественного отбора.
cyberenigma
Эволюцию и без этого вроде как-то моделируют. Вот например
phenik
Да, моделей много, особенно специализированных, исходя из устоявшихся представлений. Интересны концептуальные модели эволюции вроде автоматных, типа игры Жизнь, кот. выявляют принципиальные моменты, например, появление эмерджентных свойств и объектов. В таких моделях даже неважны привязки к свойствам генома земной жизни. Такое моделирование могло бы объяснить возникновение интеллекта, не привязываясь к конкретным реализациям, и интересно в рамках разработки ИИ.
napa3um
В эволюции неслучайность (направленность) мутаций - это реализация "памяти генома", а не математических свойств случайных графов. Структура генома "запоминает" свои "соприкосновения с факторами отбора", что выражается в неодинаковости вероятностей мутаций, которые в нём в принципе могут возникать. Есть более активные с точки зрения мутагенеза участки, отражающие наиболее важные для популяции факторы отбора, есть очень консервативные, защищаемые различными механизмами (репарации, дублирования, т.д.) Если биологическую эволюцию представить как изменение направления русла рек, то случайные графы в этом смысле будут лишь мелкой рябью на воде, совершенно не влияющие на форму этих рек.
DaneSoul
Собственно говоря, по таким участкам смотрят генетическое сходство между очень отдаленными группами организмов.
napa3um
«Важность» появляется исключительно из-за памяти, а не из-за того, что геном посчитал что-то важным от стремления к прекрасному. Вы даже не понимаете, чему и как возражаете, маскируя свой средневековый ламаркизм обрывками околонаучных терминов :).
Не сходство смотрят (оно бывает конвергентным), а именно родственность, и эта родственность именно в том и заключается, что два генома имеют общую историю и происходят от одного предкового вида, отпечатавшего в себе тот самый общий кусочек генома (запомнив таким образом те самые факторы отбора :)).
Ваше возражение звучало умно и авторитетно, была видна замотивированность, только нужно чуть-чуть почётче сформулировать (для себя прежде всего), что именно вы хотели опровергнуть. Кто там куда смотрит, зачем, и какое это отношение имеет к моему комментарию :).
DaneSoul
Что Вы понимаете под «памятью»? Как она выражается на физико-химическом уровне?
КАК именно запомнил?
Все банально проще — мутации генов кодирующих критически важные процессы/структуры банально летальны в подавляющем большинстве случаев.
Они случаются, но закрепится не могут, так как с ними не выживают.
Смотрят именно сходство последовательностей нуклеотидов в определенных генах, например кодирующих рибосомы или гемоглобин, затем на основании % различий последовательностей уже строят филогенетические деревья предсказывающие степень родственности.
napa3um
Только это и было вашим мотивом написать комментарий :). Не надо переоценивать свои компетенции :).
В самом абстрактном смысле - состояние, отличаемое от других состояний :). Выражается как угодно - в последовательности генов, в структуре генома (в том числе динамической).
Посредством эволюционной динамики :). Если просто - носители генов с неподходящими генами умерли, с подходящими - передали их дальше :).
А я и не пытался усложнять, это начали делать вы сами :).
Ничего страшного, пусть занимаются, это полезное занятие :).
Да бох с вами, кто тут кого пытается переубедить :).
Уже всё ответил, по существу, в объёме, в котором посчитал это нужным для написания (и интересным для себя) :).
DaneSoul
Я совершенно без проблем готов признать публично свою ошибку, но если будут приведены факты и аргументы.
По сути, сейчас наши мнения не противоречат друг другу, просто описывают это по разному.
Bedal
направленность эволюции с естественным отбором действительно не случайна, но можно и не гадать: поскольку существуют те особи/объекты, для которых существовали все предки «от начала», направление эволюции состоит в росте количества особей (не популяций, не видов, не классов!), для которых вероятность существования отдалённого во времени потомства выше «средней по больнице».