Сто шагов в неизвестное

5. 1993. Остров, где мамонты задержались

1993. Рубрика: Результаты в России. Остров Врангеля; Санкт-Петербург и Москва. Сергей Вартанян, Вадим Гарутт, Андрей Шер.

В 1993 году Сергей Вартанян, Вадим Гарутт и Андрей Шер сообщили: мамонты острова Врангеля пережили своих материковых сородичей на тысячи лет. Ключом стали радиоуглеродные датировки останков, в том числе зубов мамонтов.

Часть останков оказалась значительно моложе привычной границы конца ледникового времени. Мамонты жили на острове примерно четыре тысячи лет назад. Мир уже знал земледелие, города и письменность, а в Арктике ещё сохранялись животные, которых мы мысленно помещаем в гораздо более далёкое прошлое.

Эти две картины не противоречат друг другу. Земледельческое общество в одной части планеты ничего не говорит о составе фауны на другом конце света. Открытие заставило раздвинуть границы воображения, но сделано оно было вполне проверяемым способом: измерением возраста конкретных остатков.

Пока организм жив, он получает углерод из окружающей среды, в том числе радиоактивный углерод-14. После смерти это поступление прекращается, а углерод-14 продолжает распадаться с известной скоростью. Его доля относительно стабильного углерода постепенно уменьшается. Сравнивая её с оценкой исходного соотношения изотопов, можно определить, сколько времени прошло. Это не часы с циферблатом на кости: образец надо очистить, учесть загрязнение, проверить сохранность вещества и перевести радиоуглеродную шкалу в календарную. Несколько независимых находок убедительнее одной неожиданно молодой даты.

Работа принадлежала исследователям заповедника «Остров Врангеля», Зоологического института и Института эволюционной морфологии и экологии животных. Само место здесь существенно. Остров может стать убежищем, когда подходящие условия на материке исчезают, а может превратиться в ловушку: уйти дальше некуда. После отделения от материка животные оказываются в пространстве с ограниченными запасами пищи и числом возможных партнёров.

Небольшая популяция меняется иначе, чем большая. Редкие варианты генов могут случайно исчезнуть. Родственные особи чаще оставляют потомство друг с другом, и вредные наследственные варианты с большей вероятностью встречаются в двух копиях. Но отсюда ещё не следует, что каждая маленькая популяция обречена немедленно погибнуть. Численность, доступная пища, болезни и случайные события действуют одновременно.

Спустя три десятилетия этот вопрос стало возможно изучать по древним геномам. Международная работа 2024 года, в которой участвовали и российские специалисты, проследила генетическую историю мамонтов до и после изоляции острова. После сильного сокращения численность восстановилась до некоторого устойчивого уровня; генетические последствия сокращения сохранялись. Картина не поддержала простую историю о непрерывном наследственном ухудшении, которое само по себе неизбежно привело к вымиранию.

Здесь важно различать две неизвестности. Генетика может описать длительное состояние популяции, но не всегда способна назвать событие, погубившее её последних представителей. А самая молодая найденная кость даёт позднюю подтверждённую дату присутствия, но не свидетельство смерти последнего животного. Новые находки способны передвинуть границу.

Датировки 1993 года заставили искать объяснение столь разным срокам исчезновения мамонтов. Общая картина вымирания должна учитывать и условия, в которых островная популяция смогла сохраняться ещё тысячи лет.

Источники к главе 5

6. 1994. Почему привычный путь к доказательству может не привести к цели

1994 — первая конференционная публикация; 1997 — журнальная версия. Рубрика: Международные исследования с российским участием. Александр Разборов, Математический институт имени В. А. Стеклова РАН (МИАН) и Институт перспективных исследований в Принстоне; Стивен Рудич, Университет Карнеги — Меллона, США.

Проверить готовое решение часто легче, чем найти его. Если нам предъявили расписание, можно последовательно убедиться, что два занятия не назначены в одну аудиторию на одно время. Построить подходящее расписание с множеством ограничений бывает гораздо труднее. Это бытовой вход в один из центральных вопросов теоретической информатики: насколько различаются поиск и проверка?

Математики выражают вопрос через классы задач P и NP. Для задач из P существует алгоритм, время работы которого ограничено некоторой степенью размера входных данных. Для задач из NP положительный ответ имеет свидетельство, проверяемое за такое время. Когда о таких алгоритмах говорят «быстро», это условное сокращение. Даже степень может быть слишком высокой для практики, но различие между степенным и экспоненциальным ростом принципиально при увеличении задачи. Вопрос P и NP состоит в том, можно ли любую задачу с быстро проверяемым свидетельством положительного ответа также быстро решить.

Можно было бы попытаться доказать трудность задачи, рассматривая вычисление как схему из простых логических элементов. Каждый элемент выполняет небольшую операцию, а вся сеть преобразует входные биты в ответ. Быстрый алгоритм можно представить семейством схем, размер которых растёт не быстрее некоторой фиксированной степени размера входа. Если для какой-либо задачи из NP доказать, что таких схем недостаточно, то и быстрого алгоритма для неё не существует. Это был бы способ доказать различие P и NP, установив строгую нижнюю границу вычислительной сложности. Нижняя граница означает, что меньше ресурсов не хватит, каким бы изобретательным ни был конструктор в рамках модели.

Но как доказать, что большая схема действительно неизбежна, а не просто более короткую пока не нашли? Александр Разборов и Стивен Рудич исследовали возможности самих методов доказательства. В работе Natural Proofs они выделили общие свойства методов, уже давших результаты для ограниченных видов схем. При определённом криптографическом предположении оказалось, что методы с этой совокупностью свойств не способны установить нужные сильные нижние границы для общих схем.

«Естественное доказательство» здесь — специальный термин. Он не означает всякое понятное рассуждение и не делит математику на естественную и противоестественную. Среди существенных требований — возможность эффективно распознавать используемое свойство функции и его распространённость среди большого множества функций. При этом скорость проверки свойства измеряют относительно размера полной таблицы ответов функции, а не длины одного её входа. Для функции от n входных битов таблица содержит 2 в степени n ответов. Поэтому проверка, быстрая относительно всей таблицы, может требовать огромного времени по сравнению с длиной входа. Теорема относится к точно определённому классу подходов, поэтому её вывод нельзя расширять на любые будущие доказательства.

Откуда в вопросе о доказательствах появилась криптография? Для защиты информации полезны объекты, которые выглядят случайными для ограниченного вычислителя, хотя построены по короткому правилу. Если у наблюдателя достаточно ресурсов, он иногда сможет обнаружить структуру; если ресурсов недостаточно, различение должно оставаться недоступным. Это и есть одна из идей вычислительной псевдослучайности.

Предположим, что найдено достаточно быстро проверяемое свойство, которое встречается у заметной доли функций, но отсутствует у функций с небольшими схемами. Подходящую псевдослучайную функцию можно быстро вычислить по ключу — значит, она допускает небольшую схему и этого свойства у неё нет. У случайно выбранной функции свойство, напротив, иногда будет обнаруживаться. Так проверка свойства дала бы способ различать эти два случая. Если же существуют псевдослучайные функции со стойкостью, требуемой в теореме, такое различение недоступно даже при ресурсах этой проверки. Получается противоречие: либо криптографическое предположение неверно, либо метода доказательства с перечисленными свойствами не существует.

Это ограничение условно. Авторы не доказали, что криптографическое предположение истинно, и не решили вопрос P и NP. Они установили: при сформулированном предположении некоторый широкий путь к сильному результату перекрыт. В математике такой вывод обладает полноценным содержанием, потому что точно обозначает, какие утверждения могут одновременно быть верны.

Можно сравнить его с исследованием местности перед строительством дороги. Инженер ещё не проложил маршрут, но доказал, что дороги определённого типа не смогут пересечь препятствие при заданных условиях. Это знание предотвращает повторение одинаковой неудачи. Придётся либо отказаться от части привычных свойств метода, либо исследовать само условие, создающее препятствие.

В 2007 году работа Разборова и Рудича была отмечена премией Гёделя. Авторы показали, что препятствие может скрываться не только в трудности самой задачи, но и в устройстве привычных способов доказательства.

Для читателя вне математики здесь остаётся полезное различие: отсутствие найденного решения не доказывает невозможность, но и многократное применение привычного метода не гарантирует, что он вообще способен привести к цели.

Источники к главе 6

7. 1995. Граница, которая допускает ошибку

1995. Рубрика: Уроженцы России и СССР в мировой науке. AT&T Bell Laboratories, США. Коринна Кортес и Владимир Вапник.

Пусть на диаграмме нанесены два вида объектов: точки одного вида отмечены синим, другого — красным. Если группы хорошо разделены, между ними можно провести прямую так, чтобы все синие точки оказались с одной стороны, а красные — с другой. По этой границе можно классифицировать и новый объект: достаточно посмотреть, на чьей стороне окажется его точка. Но какую прямую выбрать? Известные точки можно правильно разделить несколькими способами. Если новая точка при одном варианте границы окажется на синей стороне, а при другом — на красной, результат классификации будет зависеть от выбора прямой.

Задача обучения состоит не только в воспроизведении уже показанных меток. Нужно выбрать правило, которое будет работать на ещё неизвестных случаях. Это различие между запоминанием и обобщением лежит в основе статистической теории обучения, в развитии которой Владимир Вапник сыграл большую роль ещё в советский период вместе с Алексеем Червоненкисом.

Работа Коринны Кортес и Вапника 1995 года относится к следующему, зарубежному этапу. Они работали в AT&T Bell Laboratories в США и предложили важную форму метода опорных векторов для данных, которые нельзя идеально разделить. Вапник родился в 1936 году в Узбекской ССР, СССР.

Один принцип выбора границы — оставить вокруг неё как можно более широкий свободный зазор. В двумерном рисунке это полоса между двумя группами точек. В пространстве множества признаков геометрия становится многомерной, но идея сохраняется. Чем дальше точка от границы, тем больше её нужно сдвинуть, чтобы она оказалась на другой стороне и получила другую метку.

Ближайшие к разделению примеры особенно важны. Они определяют, насколько широко можно раздвинуть края полосы, не затронув данные. Каждый пример представлен вектором — набором числовых признаков. Отсюда название «опорные векторы»: положение границы опирается на определённые обучающие объекты. Это математическое описание их роли, а не утверждение, что остальные наблюдения всегда бесполезны.

Однако реальные данные редко оказываются послушным рисунком. Измерения шумят, признаки неполны, а метки иногда ошибочны. Если любой ценой провести границу так, чтобы она без исключений согласовалась со всеми примерами, можно получить хрупкое и чрезмерно сложное правило. Правило, подогнанное под каждую такую особенность учебного набора, может хуже классифицировать новые объекты.

Мягкий зазор допускает, что некоторые обучающие точки окажутся внутри разделительной полосы или даже на стороне другой группы. При обучении уравновешивают две цели: сделать полосу шире и уменьшить общий штраф за такие нарушения. Параметр модели определяет, насколько сильно штраф влияет на выбор границы.

Есть и другая трудность: группы могут быть вложены одна в другую, так что прямая в исходных координатах бессильна. Тогда помогает переход к более богатому набору признаков. Можно, например, учитывать не только координаты, но и их сочетания. После такого преобразования нелинейная граница исходного рисунка может соответствовать линейному разделению в новом пространстве.

Для построения границы методу нужны скалярные произведения векторов — вычисляемые по парам объектов величины, описывающие их взаимное расположение в пространстве признаков. Ядро — функция, которая при соблюдении математических условий позволяет получить эти величины, не выписывая все новые координаты. Благодаря этому можно использовать гораздо более богатый набор признаков, чем удобно хранить и обрабатывать явно. Слово «ядро» не связано здесь ни с атомным ядром, ни с центральным процессором. Нелинейный классификатор с таким приёмом развивали Бернхард Бозер, Изабель Гийон и Владимир Вапник ещё в работе 1992 года. Кортес и Вапник в 1995 году соединили этот подход с описанным выше мягким зазором.

Метод опорных векторов не гарантирует хорошего ответа при любых данных. Имеют значение признаки, выбор ядра, параметры и проверка на новых примерах. Кроме того, высокая точность классификации сама по себе не объясняет причинные механизмы: алгоритм может находить полезные совпадения, не раскрывая устройство явления.

Кортес и Вапник соединили геометрический выбор границы с возможностью учитывать несовершенство наблюдений. Безошибочность на учебном наборе перестала быть обязательной целью.

Источники к главе 7

8. 1996. Когда два языка математики говорят об одном

1996 — доказательство представлено; 2003 — окончательная журнальная публикация. Рубрика: Уроженцы России и СССР в мировой науке. США и Германия. Владимир Воеводский; развитие мотивных методов совместно с международным математическим сообществом.

Числа можно складывать и умножать. Но уже попытка деления показывает различие между математическими мирами. Среди целых чисел не всякое деление возможно: разделив единицу на два, мы выходим за их пределы. Рациональные числа допускают такое деление. Система, в которой можно выполнять четыре арифметических действия, кроме деления на ноль, называется полем. Привычные дроби — один пример, но не единственный.

Когда математик исследует поле, его интересуют не только отдельные вычисления. Какие уравнения в нём разрешимы? Какие новые числа придётся добавить, чтобы получить корни? Какие преобразования сохраняют все арифметические связи? За простым названием скрывается устройство целого мира допустимых действий.

Вот небольшой пример. Если x и y — действительные числа, сумма x² + y² равна нулю только при x = y = 0. Среди комплексных чисел появляется другое решение: x = 1, y = i, потому что i² = −1. Формула осталась прежней, но выбор поля изменил ответ. Именно поэтому математику недостаточно написать уравнение: нужно сказать, с какими числами разрешено работать.

Один способ узнать сложный объект — построить его характеристики, или инварианты. Их можно сравнить, даже когда сами объекты слишком велики для прямого описания. Например, число отверстий помогает различать поверхности, не перечисляя каждую точку. В алгебре инварианты гораздо менее наглядны, но задача похожа: извлечь из бесконечного множества отношений информацию, которую можно удержать и использовать.

Гипотеза Джона Милнора утверждала связь двух таких способов исследования полей. Один строился средствами алгебраической K-теории: из элементов поля составляли специальные символы и задавали отношения между ними. Другой использовал когомологии Галуа — язык, работающий с симметриями алгебраических расширений. Воеводский доказал требуемое соответствие для коэффициентов по модулю два. Здесь двойка играет две разные роли. Для самого поля требуется, чтобы в его арифметике 1 + 1 не равнялось нулю; это называют характеристикой, отличной от двух. А коэффициенты, с помощью которых описывают инварианты этого поля, берут по модулю два: в таком счёте 1 + 1 = 0. Это не противоречие, а два разных уровня описания.

Простейший пример счёта по модулю два — различение чётного и нечётного: два одинаковых остатка при сложении дают ноль, два разных — единицу. В теореме с такими коэффициентами работают гораздо более сложные объекты. Два способа их описания выглядели чужими друг другу. В одном естественны произведения алгебраических символов, в другом — действия групп и сложные цепочки связей. Проверить совпадение на нескольких примерах недостаточно. Требуется показать, что отображение между описаниями не теряет нужной информации и не добавляет лишней во всём указанном классе случаев.

Владимир Воеводский родился в Москве в 1966 году. Работа над доказательством относится к его зарубежному периоду. Препринт «Гипотеза Милнора» появился в декабре 1996 года; позднее доказательство перерабатывалось, и журнальная версия вышла в 2003-м. Доказательство стало одной из ключевых работ, за которые Воеводский получил Филдсовскую медаль в 2002 году, ещё до выхода окончательной журнальной версии.

Чтобы связать алгебраические описания, Воеводский развивал мотивные когомологии и гомотопические методы в алгебраической геометрии. Они переносят в алгебраическую геометрию приёмы топологии — науки о свойствах, сохраняющихся при непрерывных преобразованиях. Для алгебраических объектов пришлось построить собственные аналоги таких преобразований и сохраняемых характеристик. Работа выросла из большого направления, связанного, среди прочих, с Андреем Суслиным и Маркусом Ростом. Доказательство имеет автора, но язык, на котором оно стало возможным, создавался многими.

Если задача плохо поддаётся одному аппарату, доказанное соответствие позволяет сформулировать её на другом языке и воспользоваться его преимуществами. Исследователь может выбирать описание, в котором нужная связь видна яснее. Так две прежде раздельные системы математических инструментов начинают работать вместе.

Источники к главе 8

9. 1996. Озеро под четырьмя километрами льда

1996. Рубрика: Международные исследования с российским участием. Станция Восток, Антарктида; Москва и британские научные центры. Андрей Капица, Игорь Зотиков, Джефф Ридли, Гордон Робин, Мартин Зигерт.

Под станцией Восток лежит почти четыре километра антарктического льда, а подо льдом — озеро. В 1996 году Андрей Капица, Игорь Зотиков и британские коллеги описали огромный водоём, не добравшись до его воды. Для этого потребовалось согласовать более ранние сейсмические, радиолокационные и спутниковые данные. Догадки о воде под станцией возникали и прежде; теперь удалось установить масштаб, значительную глубину и пресноводный характер скрытого водоёма.

Вопрос о жидкой воде под ледяным щитом на первый взгляд кажется парадоксом. На поверхности чрезвычайно холодно, но температура внутри толщи определяется не только погодой. Лёд изолирует нижние слои, снизу поступает тепло Земли, а давление меняет условия плавления. Поэтому основание толстого ледника может находиться близко к температуре таяния, хотя воздух над ним остаётся очень холодным.

Радиолокация посылает электромагнитный сигнал сквозь лёд и регистрирует отражения от границ. Гладкая граница льда с водой даёт сильное, ровное отражение; неровное каменное ложе рассеивает сигнал иначе. Сейсмические отражения тоже позволяют различать материалы: лёд, вода и горная порода по-разному проводят упругие волны. Спутник измеряет форму поверхности ледяного щита: над озером она заметно выравнивается и становится почти плоской. Каждый метод чувствителен к своему свойству; вместе они ограничивают круг возможных объяснений.

Это похоже на попытку узнать устройство закрытого здания по форме крыши и по эху, которое возвращается на разные сигналы. Ни один признак не даёт готового плана помещений. Но если несколько независимых измерений согласуются с одной моделью, описание становится значительно убедительнее. Для Востока важно было объяснить и отражающие границы, и геометрию поверхности, и старые сейсмические наблюдения.

Российская часть работы продолжала исследования советской антарктической программы. Андрей Капица участвовал в ранних измерениях, а теоретические работы Игоря Зотикова помогали понимать условия у основания ледников. Британские радарные и спутниковые исследования дали другие части картины. Приписать результат единственной стране означало бы потерять сам способ его получения.

В 1999 году появился дополнительный материал: анализ керна — столбика льда, извлечённого при глубоком бурении, — показал, что его нижняя часть образовалась при замерзании озёрной воды. Такой лёд называют аккреционным. Он отличается от льда, возникшего из выпавшего снега. Исследование изотопного состава, газов и структуры кристаллов позволило обсуждать обмен между озером и ледяной толщей ещё до прямого проникновения скважины в воду. Российская буровая группа впервые вскрыла озеро 5 февраля 2012 года — спустя шестнадцать лет после геофизической работы, определившей его масштаб.

Водоём оказался частью системы, где взаимодействуют вода, движущийся лёд, тепло и растворённые вещества. Чтобы понять историю озера, требуется выяснить, откуда вода поступает, где замерзает и как перемешивается. Даже слово «изолированное» нуждается в уточнении: отсутствие открытого контакта с атмосферой не делает внутренние процессы неподвижными.

Работа 1996 года не доказала существования в озере необычных животных или особой древней биосферы. Такие вопросы требуют собственных образцов и строгого контроля загрязнения. Достижение этой работы значительно и без таких ожиданий: огромный недоступный водоём удалось измерить и включить в физическую картину Антарктиды. История Востока показывает, как география продолжает делать открытия даже там, где карта поверхности давно кажется завершённой.

Источники к главе 9

10. 1996. Сколько сведений проходит через квантовый шум

1996 — препринт; 1998 — журнальная публикация. Рубрика: Результаты в России. МИАН, Москва, Россия. Александр Холево.

Разговор в шумном помещении показывает разницу между звуком и сообщением. Звук доходит до собеседника, но часть слов теряется. Можно говорить медленнее, повторять важное или заранее договориться о коротких обозначениях. Возникает вполне точный вопрос: с какой наибольшей скоростью удастся передавать сообщение так, чтобы вероятность ошибки становилась сколь угодно малой?

В классической теории связи ответ на этот вопрос дал Клод Шеннон. Но носители информации — свет, электроны, атомы — подчиняются квантовой механике. Когда отдельные квантовые состояния используются как сигналы, привычная задача обретает новые условия. Некоторые разные состояния невозможно гарантированно различить, измерив единственную копию сигнала. Сам процесс считывания также приходится включать в описание канала.

Александр Холево работал над этим кругом вопросов много лет. В постсоветский период он доказал теорему о пропускной способности классического канала с квантовыми состояниями на выходе, представленную в препринте 1996 года и опубликованную в 1998-м. Она дополняла результаты других исследователей и вошла в фундамент квантовой теории информации. Связанный комплекс результатов обычно обозначают именами Холево, Бенджамина Шумахера и Майкла Д. Вестморленда.

Классическое сообщение в этой задаче остаётся обычным: отправитель хочет передать буквы или последовательность нулей и единиц. Квантовыми являются физические состояния, которыми он эти символы кодирует. Получатель должен измерить пришедшие системы и восстановить сообщение. Рассматривается канал без памяти: последовательные его использования независимы, а прежние сигналы не меняют того, как он подействует на следующий сигнал. Это существенно отличается от другой задачи — передачи самого неизвестного квантового состояния, для которой действуют иные ограничения.