Расширьтесь, граф

Главная математическая награда — премия Абеля — в этом году была присуждена Гилелю Фюрстенбергу и Григорию Маргулису, которые занимались исследованием таких математических объектов, как группы и графы. О работах лауреатов мы попросили рассказать профессора Санкт-Петербургского госуниверситета Федора Петрова.

Взаимное проникновение различных областей математики не только приводит к замечательным новым результатам — что в полной мере проявилось у Маргулиса и Фюрстенберга — но и производит большое эстетическое и интеллектуальное впечатление, даже когда доказываются факты давно известные. Одна из самых ранних и самых важных теорем математики — бесконечность ряда простых чисел 2,3,5,7... Читателю, знакомому с основами общей топологии, рекомендуем познакомиться с предложенным Фюрстенбергом топологическим доказательством этого факта.

Это доказательство Фюрстенберг, тогда еще Гарри (он родился в Германии в 1934 году, его семья успела бежать в Америку в 1939 году), придумал будучи студентом Нью-Йоркского Иешива-университета. Глубокую религиозность и интерес к иудейскому богословию он сохраняет на протяжении всей жизни. Познакомиться со взглядами Фюрстенберга по вопросам связи религии и науки можно из предисловия, написанного им к книге «Божественное действие и естественный отбор».

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

Из работ Григория Александровича Маргулиса обсудим статью «Явные конструкции расширителей» — самую цитируемую, потому что она непосредственно связана с приложениями. В ней идет речь о конструкции так называемых графов-расширителей. Чтобы не перегружать текст, не будем вводить определения этих объектов во всей полноте, но поясним суть.

Пусть d > 2 — данное натуральное число (в примере Маргулиса d = 5), α > 0 — фиксированная константа. Граф-расширитель устроен так: пусть в социальной сети есть N пользователей, и каждый дружит с d другими. Свойство расширения состоит в следующем: если взять любую группу из k < N/2 пользователей, то они дружат в совокупности хотя бы с α·k пользователями, не входящими в эту группу. Это значит, что если один из пользователей узнает большой секрет и начинает рассказывать его своим друзьям, те своим и так далее, то секрет распространяется со скоростью геометрической прогрессии: если сегодня его знают k пользователей, то завтра хотя бы (1 + α)·k, и так пока его не узнает хотя бы половина пользователей. Это происходит очень быстро: за логарифмическое по N число шагов. Ограничение N/2 не принципиально: можно заменить его на N/3 или 4N/5, суть останется той же — главное отделиться от N.

Почти все графы удовлетворяют свойству расширения. То есть, если взять, например, много пользователей сети и знакомить их между собой как попало, чтобы у каждого появилось d друзей, свойство расширения будет выполняться с вероятностью почти 1. Это не очень сложно установить, тем самым доказав существование графов-расширителей. Для полноты приведем пример графа, не обладающего свойством расширения. Представьте себе, что по кругу сидят N человек, и каждый знаком с d/2 соседями справа и d/2 соседями слева. В таком графе распространение информации происходит с линейной скоростью.

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

Графы-расширители имеют множество приложений, исторически одно из первых — создание на их основе кодов, позволяющих исправлять возникающие при передаче информации ошибки.

Именно задача построения явной конструкции графов-расширителей была решена в статье Маргулиса.

Доказать, что некоторый конкретный объект обладает свойствами случайного объекта, часто очень трудно. Приведем пару примеров. Если взять в отрезке [0,1] случайное число, то с вероятностью 1 оно обладает многими свойствами: например, среди цифр его десятичной записи все десять цифр встречаются одинаково часто. Доказательство этого для конкретных чисел (скажем,√2−1 или π−3) находится далеко за пределами возможностей современной математики, хотя в самом факте никто не сомневается. Но построить число с таким свойством возможно: например, годится число:

Однако если потребовать аналогичного свойства не только для десятичной системы, но одновременно для всех оснований систем счисления, то с вероятностью 1 подходит по-прежнему каждое число, — а явных примеров уже неизвестно.

Пример, который ближе к обсуждаемому, — из теории графов. Будем говорить (предупреждение: терминология не стандартная), что компания людей нарушает n-свойство Рамсея, если в ней не найдется ни n попарно знакомых людей, ни n попарно незнакомых — иными словами, среди любых n найдутся как двое знакомых, так и двое незнакомых. Например, если посадить за круглый стол пять человек и познакомить только соседей, такая компания нарушает 3-свойство Рамсея. А компания из 6 человек уже не может нарушить 3-свойства Рамсея: из любых 6 людей найдутся трое попарно знакомых или трое попарно незнакомых. Насколько большой может быть компания, нарушающая n-свойство Рамсея?

Поль Эрдёш заметил, что если взять не более чем 2^n/2 незнакомых людей и знакомить их как попало (любых двоих мы знакомим или нет в зависимости от того, как выпадет подброшенная с целью принять это решение монетка), то с положительной вероятностью n-свойство Рамсея нарушится.

Несложно доказать (это один из частных случаев фундаментальной теоремы Рамсея), что компания из 4ⁿ людей нарушить свойство Рамсея не может. Таким образом,ответ на поставленный вопрос экспоненциален по n. Точное значение показателя экспоненты неизвестно, улучшение одного из приведённых показателей √2 или 4 было бы новостью первостепенной важности в математике. Но явных примеров компаний с экспоненциальным (хоть бы с каким показателем) числом членов, нарушающих n-свойство Рамсея, неизвестно. Точнее говоря, кандидаты на такие компании известны — не получается доказать.

Благодаря Григорию Маргулису с графами-расширителями дело обстоит лучше. Опишем их конструкцию. Пусть m — большое натуральное число. В нашей сети будет m² мужчин и m² женщин, всего N = 2m² человек. Сопоставим мужчинам различные пары остатков (x,y) при делении на m, то же сделаем для женщин. Мужчина (x, y) дружит с пятью женщинами: (x, y), (x + 1, y), (x, y + 1), (x, x + y), (−y, x). Некоторые из них могу совпадать, так что всего у него знакомых женщин не более пяти. Сложение и вычитание производится по модулю m: например, если x = m − 1, то x + 1 это 0, −x это 1, а x+x это m − 2.

Несложно видеть, что при этом каждая женщина (u, v) дружит не более, чем с пятью мужчинами: (u, v), (u−1, v), (u, v−1), (u, v−u), (−v, u). Больше никаких дружб (в том числе с людьми того же пола) нет. Для доказательства свойства расширения достаточно доказать, что любые t ≤ (1 +α)m²/2 мужчин дружат в совокупности хотя бы с ((1+3α)/(1−α))t женщинами. В самом деле, рассмотрим любую группу из k < N/2 = m² пользователей, пусть среди них k_m мужчин и k_f женщин. Надо доказать, что у них не менее αk друзей вне группы. Если k_f−k_m>αk, то уже женщины нашей группы знают хотя бы αk мужчин не из группы (так как они всего знают не менее k_f мужчин: посмотрим на мужчин с теми же парами остатков, что у них); аналогично если k_m−k_f>αk. В противном случае |k_m−k_f| < αk и получаем

и если выполнено предполагаемое свойство, то мужчины нашей группы знают хотя бы ((1+ 3α)/(1−α))·((1−α)/2)·k=((1+3α)/2)k женщин, из них хотя бы αk в группу не входит.

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

Ключевым оказывается так называемое свойство Каждана T, введенное несколькими годами ранее другим великим математиком Давидом Кажданом. Подробности уверенный в своих силах читатель может узнать здесь.

Использование непрерывных конструкций (в том числе непрерывных действий групп и гильбертова пространства) для доказательства дискретных утверждений возникает и в знаменитой работе Фюрстенберга. В ней строится общий принцип соответствия между вопросами арифметической комбинаторики и эргодической теории, он применяется к двум доказанным и другими методами теоремам — а впоследствии привёл к новым очень сильным результатам. Во-первых, Фюрстенберг устанавливает такую теорему, доказанную параллельно венгерским математиком Андрашем Саркози:

для любого ε > 0 при достаточно большом n любое множество A из не менее чем ε n целых чисел от 1 до n содержит два числа, разность которых — квадрат натурального числа.

Это утверждение, высказанное в качестве гипотезы знаменитым венгерским математиком Ласло Ловасом, доказывается с помощью соответствия Фюрстенберга очень коротко и служит прекрасной иллюстрацией механизма его работы. Мотивированное подходом Фюрстенберга, но в конечном итоге элементарное короткое доказательство можно узнать в блоге Теренса Тао.

Более сложное дело — теорема Эндре Семереди (также знаменитого венгерского математика, абелевского лауреата 2012 года). Формулировка её похожа на теорему Фюрстенберга — Саркози: для любого ε > 0 и любого натурального k при достаточно большом n любое множество A из не менее чем εn целых чисел от 1 до n содержит арифметическую прогрессию из k членов.

Доказательство Семереди было чисто комбинаторным и очень сложным. Подход Фюрстенберга не делает это утверждение тривиальным, и есть серьёзные основания считать, что принципиальная сложность теоремы Семереди сохраняется при любом подходе (подходов известно несколько, и каждый оказал большое влияние) — но он привел к альтернативному доказательству, а впоследствии и к доказательству утверждений, усиливающих теорему Семереди, комбинаторные доказательства которых еще не известны.

Идея Фюрстенберга такова. Теоремы Фюрстенберга — Саркози и Семереди могут быть пересказаны на языке сдвигов множеств целых чисел: в теореме Фюрстенберга—Саркози утверждается, что один из сдвигов A+b² множества A на точный квадрат пересекается с A; в теореме Семереди — что при некотором d > 0 непусто пересечение сдвигов множества A на d, 2d, 3d,..., kd. Рассмотрим оператор сдвига T, переводящий функцию f(x) на множестве целых чисел в функцию (Tf)(x) = f (x + 1). Тогда переходя от множеств к функциям и совершая предельный переход можно свести утверждение о сдвигах множеств к свойствам динамической системы — преобразования, сохраняющего меру на некотором метрическом компакте.

Читателям, заинтересовавшимся графами-расширителями, рекомендую для дальнейшего знакомства с предметом популярную статью, а арифметической комбинаторикой — обстоятельный обзор.

Федор Петров