Чувствительность булевых функций

Александр Разборов
«Квант» №10, 2020

В этой статье мы расскажем о красивой и важной задаче с вполне элементарной формулировкой, которая была предметом интенсивных исследований многих математиков (включая автора этой статьи) на протяжении нескольких десятилетий и при этом не поддавалась никаким усилиям. А дальше все произошло как в сказке: 1 июля 2019 года на сайте arxiv.org появилась шестистраничная работа [1] американского математика по имени Хао Хуан (Hao Huang) с полным решением проблемы совершенно неожиданным и удивительно простым способом.

Начнем с азов.

Булевы функции, раскраски гиперкуба и чувствительность. Через {0,1}ⁿ мы будем обозначать множество всех двоичных слов длины n: например, {0,1}³ состоит из восьми элементов (000), (001), (010), (011), (100), (101), (110), (111). Булева функция от n переменных f_n : {0,1}ⁿ → {0,1} классифицирует слова x ∈ {0,1}ⁿ в «хорошие» (те, для которых f_n(x) = 1) и «плохие» (f_n(x) = 0). Нижний индекс всегда будет обозначать число переменных.

Булевы функции, как, впрочем, и любые другие, можно подставлять друг в друга; не менее важно то, что их можно подвергать логическим операциям, таким как И, ИЛИ, НЕ. Поэтому булевы функции являются одним из наиболее фундаментальных и часто встречающихся объектов в различных компьютерных науках (и теоретических, и прикладных) как способ представления и преобразования дискретной информации.

Нас сегодня будут больше интересовать свойства булевых функций как комбинаторных объектов, а также иногда их аналитические¹ свойства; изучением последних занимается целая дисциплина, называемая «анализ булевых функций». Поэтому, чтобы подчеркнуть комбинаторную и геометрическую природу булевых функций, давайте по возможности вместо формул рассматривать картинки и графы.

Два слова x, y ∈ {0,1}ⁿ называются соседними, если они отличаются ровно в одной позиции i ∈ {1, ..., n}. Соединяя ребром все пары соседних вершин, получим граф Q_n на 2ⁿ вершинах. Эти графы (на рисунке 1 показаны графы Q₁, Q₂ и Q₃) называются гиперкубами, и они очень важны в комбинаторике по многим разным причинам. Тем самым булевы функции f_n : {0,1}ⁿ → {0,1} превращаются в раскраски множества вершин V (Q_n) n-мерного гиперкуба в два цвета: зеленый (f_n (x) = 1) и красный (f_n (x) = 0). На рисунке 2 показаны булевы функции, соответствующие наиболее базисным операциям: И, ИЛИ, сложение по модулю 2 (XOR) и функция голосования (MAJ₃: значение MAJ₃(x) равно 1, если и только если слово х содержит хотя бы две единицы). На каждом рисунке также выделено синим цветом множество Cut(f_n) ребер графа Q_n, вершины которых покрашены в разные цвета. Это множество называется разрезом (данной функции), и оно является центральным для нашей статьи понятием.

Докажите, что всякая функция f₂ , существенно зависящая от обеих своих переменных, является обобщенно-симметричной. А верно ли то же самое для функций от 3 и большего числа переменных?

Мы теперь готовы определить важную числовую характеристику булевой функции f_n — ее чувствительность s(f_n). Начнем с чувствительности s(f_n,x) функции f_n в данной вершине x ∈ V (Q_n): по определению, она просто равна числу ребер в разрезе Cut(f_n), выходящих из x. Это одна из нескольких естественных возможностей измерять, насколько именно функция в точке x чувствительна к малым (в данном случае — ровно в одной координате) изменениям во входных данных. Чувствительность функции f_n определяется как максимально возможное значение s(f_n,x):

\(\mathrm{s}(f_n)={\underset{x\in V()Qn)}{\max \mathrm{s}(f_n,x)}}.\) (1)

Таким образом (для знакомых с терминологией теории графов), s(f_n) — это не что иное, как максимальная степень (вершины) графа c множеством ребер Cut(f_n) .

Для больших n имеет место оценка

\(\mathrm{s}(f_n)\geq\frac{1}{2}\log_2 n -\frac{1}{2}\log_2\log_2n+\frac{1}{2}\), (2)

где, как и в упражнении 3, функция f_n существенно зависит от всех своих переменных. Эта оценка, доказанная Х.У. Симоном (H.U.Simon) в 1983 году, по-видимому, является первым нетривиальным результатом в исследовании чувствительности булевых функций. На первый взгляд она может показаться чрезмерно грубой, но на самом деле оценка довольно точна.

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

Так, например, в формуле (1) вместо взятия максимума по всем x ∈ V (Q_n) можно взять среднее значение. Получится средняя чувствительность as(f_n) функции f_n, которая, как легко понять, является не чем иным, как размером разреза |Cut(f_n)|, нормированным подходящим (вычислите его!) множителем. Это понятие играет центральную роль в анализе булевых функций.

Нас сегодня, однако, больше интересует другая модификация: bs(f_n) называемая блочной чувствительностью. Как и раньше, начнем со случая, когда у нас есть функция f_n и входное слово x ∈ {0, 1}ⁿ. Тогда чувствительным блоком называется подмножество B ⊆ {1,2,...,n} такое, что f(x^B) ≠ f(x), где x^B — результат изменения слова x одновременно во всех позициях i ∈ B. Например, функция MAJ₃ на рисунке 1 в точке (000) имеет четыре чувствительных блока, а именно, те подмножества B ⊆ {1,2,3}, для которых |B| ≥ 2. Блочной чувствительностью bs(f_n,x) функции f_n на входе² x называется максимальное значение l, для которого существуют l попарно непересекающихся чувствительных блоков. Таким образом, bs(MAJ₃,000) = 1 просто потому, что любые два чувствительных блока имеют непустое пересечение. И, наконец, как и раньше, полагаем

\(\mathrm{bs}(f_n)\overset{a}{=}\underset{x\in V(Q_n)}{max}\mathrm{bs}(f_n,x)\).

Ниже мы объясним, почему блочная чувствительность важна и интересна, но вначале давайте сравним ее с обыкновенной, а также сформулируем гипотезу (уже доказанную), которая послужила поводом для написания этой статьи.

Прежде всего, обыкновенная чувствительность, очевидно, соответствует ограничению, состоящему в том, что все чувствительные блоки имеют размер 1. Поэтому s(f_n,x) ≤ bs(f_n,x) и, соответственно, s(f_n) ≤ bs(f_n).

Насколько большим может быть разрыв между s(f_n) и bs(f_n)? Первый общий пример в этом направлении принадлежит Рубинштейну (Rubinstein, 1995). Соответствующую функцию R_n от n = m² переменных описать довольно легко, но лучше это делать не на картинке. Итак, у нас есть двоичное слово x длины m². Первым делом разобьем его на m блоков по m знаков в каждом блоке. Назовем блок хорошим, если он содержит ровно две единицы, причем эти единицы следуют друг за другом. Раскрасим x в зеленый цвет, если в нем найдется хотя бы один хороший блок, и в красный, если такого нет.

Итак, разрыв между чувствительностью и блочной чувствительностью может выражаться квадратичной функцией, и попытки его увеличить оставались совершенно безуспешными в течение долгого времени. Улучшить мультипликативную константу в примере Рубинштейна удалось лишь совсем недавно, но функция при этом так и осталась квадратичной. Все это побудило Нисан и Сегеди (Nisan и Szegedy) сформулировать в 1994 году следующую гипотезу, быстро завоевавшую широкую известность.

Гипотеза о блочной чувствительности. Существуют такие абсолютные константы ε, δ > 0, что для любой булевой функции f_n имеет место s(f_n) ≥ δ bs(f_n)^ε.

Если эту гипотезу сформулировать словами, то в ней утверждается, что функции s(f_n) и bs(f_n) совпадают «с точностью до некоторого полинома (многочлена)». Такой уровень точности, в особенности когда полиномиальные функции противопоставляются экспоненциальным, является типичным для современной теории сложности; более подробно об этом можно прочитать в популярном очерке [2].

Достигнутый в течение 25 лет прогресс в доказательстве этого утверждения (или построении к нему контрпримера) преимущественно сводился к нахождению новых гипотез или фактов, напрямую с ним связанных. Приятным исключением является работа Кеньон и Кутина (Kenyon и Kutin) 2004 года, в которой гипотеза о блочной чувствительности доказана в предположении, что все чувствительные блоки имеют ограниченный (например, ≥10) размер. Мы отсылаем заинтересованного читателя к обзору [3], а сами переходим непосредственно к доказанному Хуаном результату.

Теорема 1 ([1]). Для всякой булевой функции f_n имеем s(f_n) ≥ bs(f_n)^1/4.

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

Сертификационная сложность. Как всегда, начнем с рассмотрения индивидуального входа x ∈ {0,1}ⁿ. Множество позиций I ⊆ {1,...,n} называется сертифицирующим (для данного x), если набор значений (x_i|i ∈ I) (называемый сертификатом) полностью определяет f_n(x). Иными словами, для любого другого y ∈ {0,1}ⁿ, совпадающего с x во всех позициях из I, имеет место f_n(y) = f_n(x). Сертификаты далеко не единственны, и сертификационной сложностью C(f_n,x) называется минимальный (обратите внимание на отличие от определений чувствительности, в которых берется максимум) возможный размер |I| сертификата I. После этого, как и раньше,

\(C(f_n)\overset{\mathrm{def}}=\underset{x\in \{0,1\} }{\mathrm{max}}C(f_n,x)\).

То же самое понятие легко объяснить геометрически. Рассмотрим семейство подкубов в Q_n, имеющих коразмерность d (т. е. содержащих ровно 2^n − d вершин). Среди них нас интересуют монохроматические подкубы, т. е. такие, у которых все вершины покрашены в один и тот же цвет.

Легко понять, что , bs(f_n,x) ≤ C(f_n,x), следовательно, bs(f_n) ≤ C(f_n,x). Действительно, выберем произвольный сертификат I с |I| = C(f_n,x). Тогда всякий чувствительный блок B на входе x обязан содержать хотя бы один i ∈ I. Поэтому всякое дизъюнктное семейство чувствительных блоков (т. е. такое, что никакие два его блока не пересекаются) может содержать не более |I| членов.

В другую сторону это намного менее очевидно.

Теорема 2 (Нисан, Сегеди, 1994). Для всякой булевой функции f_n имеем C(fn) ≤ bs(f_n)².

Таким образом, bs(f_n) и C(f_n) «эквивалентны с точностью до полинома», и при желании в теореме 1 можно заменить блочную чувствительность на сертификационную сложность. От этого ее содержание (за исключением, возможно, константы в экспоненте) не изменится. Отметим также, что в геометрическом определении C(fn) можно дополнительно потребовать, чтобы искомое покрытие было на самом деле разбиением, т. е. все участвующие в покрытии подкубы попарно не пересекаются. Полученная величина все еще будет полиномиально эквивалентна bs(f_n) и C(f_n); почему это так, станет понятным в следующем разделе.

Разрешающие деревья. До сих пор мы в основном занимались комбинаторными и к тому же локальными (т. е. определяемыми в терминах некоторой «окрестности» фиксированной вершины x ∈ {0,1}ⁿ) свойствами булевых функций. В этом разделе мы покажем, как все это соотносится с теорией вычислительной сложности.

Разрешающие деревья (decision trees) — это, пожалуй, наиболее простая, но в то же время наиболее часто используемая в приложениях вычислительная модель. Многие, вероятно, знают игру в 20 вопросов, в которой требуется угадать неизвестный предмет, задавая про него вопросы, на которые допускаются лишь ответы ДА/НЕТ. Любую мыслимую стратегию для этой игры можно представить в виде разрешающего дерева (рис. 4). Его высотой называется максимальная возможная длина пути в этом дереве. Таким образом, высота дерева определяется числом вопросов, задаваемых в наиболее неблагоприятном (наихудшем) для нас случае. Например, если на рисунке 4 нам повезло и был загадан именно стол, то все равно высота дерева будет измеряться подсчетом длины вдоль других ветвей этого дерева.

Читателю предлагается обдумать следующий довольно нехитрый тезис: игру в 20 вопросов можно заведомо выиграть тогда и только тогда, когда для нее существует разрешающее дерево, имеющее высоту ≤ 20.

Как мы уже отмечали, разрешающие деревья в той или иной форме используются везде, и во многих приложениях достаточно рассматривать вычисление с их помощью булевых функций f_n. Чтобы разобраться в том, что это такое, давайте слегка модифицируем правила игры: предположим, что вместо предмета у нас загадано двоичное слово x ∈ {0,1}ⁿ. Тогда если ставится задача угадать x полностью, то легко понять, что никакое разрешающее дерево для решения этой задачи не может иметь высоту ≤ n − 1.

Предположим, однако, что все слово x нас не интересует, а интересует некоторое его свойство, задаваемое булевой функцией f_n(x). В такой постановке задача не слишком интересна, потому что про загаданное свойство можно просто спросить. Однако в рассматриваемой нами модели мы разрешаем угадывающему задавать только очень простые вопросы, а именно выяснять значение индивидуального бита x_i(i ∈ {1,...,n}) в слове x. Пример такого разрешающего дерева приведен на рисунке 5; требуется, чтобы информации, полученной угадывающим вдоль каждой ветви, было достаточно для определения значения f_n(x) независимо от тех значений, про которые не спрашивали. Сложность D(f_n) булевой функции f_n по отношению к разрешающим деревьям (query complexity) определяется как минимально возможная высота разрешающего дерева, вычисляющего нашу функцию. Иными словами, это наименьшее число простых вопросов про вход x ∈ {0,1}ⁿ, которых заведомо достаточно для вычисления значения f_n(x).

Теперь давайте свяжем все это с предыдущими рассмотрениями. Как всегда, в одну сторону это просто. Если имеется разрешающее дерево, то каждой заключительной вершине соответствует сертификат, состоящий из ответов на все вопросы, которые угадывающий спросил про x по дороге в эту вершину. На рисунке 5 этот сертификат выписан явно для одной (закрашенной) вершины. Размер этого сертификата не превосходит высоты дерева, и более того, каждый вход x обладает ровно одним таким сертификатом. Таким образом, C(f_n) ≤ D(f_n)и, более того (сравните с замечанием в конце предыдущего раздела), построенная нами система подкубов является разбиением {0,1}ⁿ.

В обратную сторону это намного менее очевидно.

Теорема 3 (Билз и др., 2001). Для всякой булевой функции f_n имеем D(f_n) ≤ C(f_n)bs(f_n) (что ≤ bs(f_n)³ ввиду теоремы 2).

Доказательство этой теоремы выходит за рамки этой статьи, но она позволяет добавить разрешающие деревья к списку мер сложности, полиномиально эквивалентных блочной чувствительности. Отметим лишь одно ее замечательное свойство: величины C(f_n), bs(f_n) в правой части имеют сугубо комбинаторную (или геометрическую, если угодно) природу. В то же время разрешающие деревья — это концепция алгоритмическая. Таким образом, теорема 3 утверждает существование алгоритма, качество работы которого целиком определяется комбинаторными свойствами функции, к которой он применяется.

Булевы функции и полиномы. В этом разделе мы рассматриваем 0 и 1 просто как вещественные числа, совершенно абстрагируясь от их логического смысла. Кроме того, нас будет интересовать слегка более общая ситуация f_n : {0,1}ⁿ → \(\mathbb{R}\), т. е. областью определения функции f_n все еще служат вершины гиперкуба, но значениями могут быть уже произвольные вещественные числа.

Мы хотим представить функции f_n максимально простым выражением, причем под «представлением» мы имеем в виду, что значение нашего выражения должно совпадать с f_n там, где эта функция определена (т. е. при x ∈ {0, 1}ⁿ), и может вести себя произвольно на всех остальных.

Самые простые и важные аналитические выражения — это полиномы (многочлены) от нескольких переменных, и оказывается, что в самом деле любая функция fn : {0,1}n → \(\mathbb{R}\) допускает полиномиальное представление. Более того, в таком представлении нет нужды в высших (≥ 2) степенях одной и той же переменной: так как x_i ∈ {0,1}, то d_xⁱ при d ≥ 2 всегда можно упростить до x_i. Иными словами, достаточно ограничиться мультилинейными полиномами, т. е. такими, у которых степень по каждой переменной не превосходит 1 (и, следовательно, суммарная степень не превосходит n).

Указание. Напишите явную формулу, связывающую f_n(x₁,...,x_n) с f_n(x₁,...,x_n − ,0) и fn(x₁,...,x_n − 1,1).

Оказывается, что такое представление к тому же и единственно. Таким образом, всякую функцию f_n : {0,1}ⁿ → \(\mathbb{R}\) (и, в частности, всякую булеву функцию) можно отождествить с ее мультилинейным полиномиальным представлением.

Таким образом, с каждой булевой функцией f_n можно связать еще одну меру сложности, на этот раз алгебраическую, а именно степень deg(f_n) представляющего ее мультилинейного полинома. Отметим ее важное отличие от всех ранее рассмотренных мер. А именно, до сих пор в наши определения входили разнообразные минимумы и максимумы, что на практике ведет к тому, что вычислить их, или даже приблизить разумным образом, может быть непросто. Напротив, степень deg(f_n) соответствует единственному представлению функции f_n , и, как следствие, ее можно вычислить явно в большинстве интересных ситуаций, просто выписав представляющий полином.

Видимо, читатель уже догадался, к чему мы ведем: степень deg(f_n) оказывается эквивалентной всем ранее рассмотренным мерам. Доказать неравенство в одну сторону довольно легко.

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

\(\mathrm{deg}(f_n)\geq \frac{1}{3}\sqrt{\mathrm{bs}(f_n)}\).

Доказательство весьма нетривиально и использует глубокий факт из теории полиномиальной аппроксимации. Грубо говоря, основная идея состоит в том, что bs(f_n) ≥ s — это утверждение позитивное, именно этим блочная чувствительность и удобна. Оно означает существование входа x и блоков B₁,...,B_s с определенными свойствами. Показывается, что наличие таких x,B₁,...,B_s несовместимо с наличием полиномиального представления малой степени.

В заключение этого раздела отметим, что другой важной характеристикой булевой функции, в особенности при рассмотрении вероятностных и квантовых алгоритмов, является ее приближенная степень \(\widetilde{deg}\)(f_n). Она определяется как минимальная возможная степень мультилинейного полинома p_n(x₁,...,x_n), для которого |p_n(x₁,..,x_n) − f_n(x₁,...,x_n)| ≤ 1/3 для всех x ∈ {0,1}ⁿ (точное значение константы 1/3 здесь большой роли не играет, важно лишь, что она меньше 1/2). В этом определении уже присутствует минимум, поэтому приближенная степень — намного более сложная величина, чемобыкновенная. Скажем, даже для простой функции на рисунке 6 доказательство того, что ее приближенная степень линейна по n, потребовало многих лет работы и было получено сравнительно недавно специально разработанным для этой цели методом (Бун, Талер (Bun, Thaler), 2013; Шерстов, 2014).

Однако если мы работаем «c точностью до полинома», то приближенная степень пополняет нашу коллекцию мер, полиномально эквивалентных блочной чувствительности. Неравенство \(\widetilde{deg}\)(f_n) ≤ deg(f_n) очевидно, а метод, используемый для доказательства нижней оценки (3) на степень, с тем же успехом работает и для приближенной степени.

Мы познакомились с некоторыми базовыми мерами сложности булевых функций. Несмотря на то, что они имеют совсем разную природу, все они эквивалентны друг другу в некотором разумном смысле, кроме (до 2019 года!) обыкновенной чувствительности. Осталось сказать несколько слов о доказательстве Хуана, лишающем обыкновенную чувствительность ее особого статуса.

Блочная чувствительность полиномиально эквивалентна чувствительности. Доказательство из [1] существенно опирается на предыдущую работу Готсмана и Линиала (1997), в которой предложена еще одна характеризация блочной чувствительности, и мы начнем с этой работы, тем более что эта часть почти элементарна.

Отправной точкой для нас служит булева функция f_n с deg(f_n) = d , а в конце будет показано, что s(f_n) ≥ d^1/2.

Первое наблюдение состоит в том, что без ограничения общности можно считать d = n. Для этого достаточно в представляющем f_n полиноме выделить произвольный член старшей степени, скажем αx₁x₂...x_d (где α ≠ 0). Подставим вместо оставшихся переменных x_d + 1,...,x_n произвольные 0–1 значения (например, нули). Легко понять, что от такой операции степень полинома уменьшиться не может, просто потому что член αx₁...x_d мы не трогаем и сокращаться ему будет не с кем. С другой стороны, чувствительность (как, впрочем, и все остальные рассмотренные в этой статье меры) от такой подстановки может только уменьшиться.

Итак, предположим, что старший член x₁x₂...x_n присутствует в f_n с ненулевым коэффициентом α. Оказывается, что α имеет очень полезное комбинаторное описание. Развернем наш гиперкуб, чтобы на каждом горизонтальном уровне оказались входы с одинаковым количеством единиц, и поменяем цвет вершин с красного на зеленый и наоборот, но только на нечетных уровнях (рис. 7).

Что произойдет от такой операции? Во-первых, разрез Сut(f_n) превратится в множество монохроматических ребер, т. е. таких, у которых оба конца покрашены в один цвет. Тем самым, если мы рассмотрим подграфы G_n, R_n, индуцированные зелеными и красными (в новой раскраске!) вершинами соответственно, то s(f_n) станет не чем иным, как max(Δ(G_n), Δ(R_n)) где Δ(G)– максимальная степень вершины в графе G.

Оказывается, что коэффициент D просто измеряет «несбалансированность» нашей новой раскраски. Более точно, если g_n = |V(Gn)| и r_n |V(R)| — количества «новых» зеленых и красных вершин, то имеет место соотношение

\(g_n-r_n=\alpha \cdot 2^n\).

Для нас единственно важно, что g_n ≠ r_n, т. е. что одно из этих чисел (скажем, g_n) строго больше 2^n − 1.

Таким образом, нам «всего лишь» осталось показать, что для произвольного подмножества V_n ⊆ {0,1}ⁿ с |Vn| > 2^{n  − 1} в индуцированном этим подмножеством графе H_n есть вершина степени ≥ n^1/2.

Это и есть сведение Готсмана–Линиала. Для полноты картины отметим, что оно работает в обе стороны, и если в выделенном курсивом утверждении заменить n^1/2 на n^ε для произвольной константы ε, то получится еще одна переформулировка гипотезы о блочной чувствительности.

Итак, нижняя оценка на максимальную степень H_n и есть то, что доказывает Хуан. Доказательство несложно для понимания, но использует некоторые элементарные (на уровне первого курса любого математического факультета) факты из линейной алгебры. Строго их формулировать, а тем более доказывать, у нас возможности нет, но некоторое представление, о чем идет речь, мы дать можем.

Матрицей называется квадратная таблица A размера N × N, состоящая из чисел a_i,j (1 ≤ i ≤ N, 1 ≤ j ≤ N). Матрица A называется симметричной, если a_i,j = a_j,I для всех i, j. На картинке это означает, что матрица не изменится при отражении относительно главной диагонали, идущей из левого верхнего в правый нижний угол (рис. 8). В оставшейся части статьи нас будут интересовать исключительно симметрические матрицы.

Вектор размерности N — это столбец X высоты N, также состоящий из чисел x_j (1 ≤ j ≤ N). Матрицу A размера N × N всегда можно умножить на вектор той же размерности N; получится новый вектор, который обозначается через AX. В i-й позиции этого вектора помещается значение суммы a_i,1x₁ + ... + a_i,Nx_N; пример такого вычисления приведен на рисунке 8.

Этот пример интересен еще и потому, что вектор AX оказывается гомотетичен исходному вектору X, т. е. существует такое число λ, что (AX)_i = λx_i для всех 1 ≤ i ≤ N, или, в векторных обозначениях, AX λX. Векторы, обладающие этим замечательным свойством, называются собственными (для матрицы A), а «коэффициент гомотетии»³ λ — собственным значением, соответствующим собственному вектору X. У каждой матрицы есть тривиальный собственный вектор, а именно, состоящий из одних нулей нулевой вектор, но на первый взгляд непонятно, почему у A непременно должны быть какие-то другие.

На самом деле у произвольной (т. е. не обязательно симметрической) матрицы ихвполне может и не оказаться, и для полного понимания картины необходимо привлекать комплексные числа. Но для симметрических матриц все существенно проще: всякая такая матрица обладает полным набором X¹,...X^N линейно независимых (cм. следующий абзац) собственных векторов. Так, например, наша матрица A на рисунке 8, помимо уже известного нам собственного вектора X = X¹ обладает еще двумя, X² и X³. Тем самым у нас также появляется набор собственных значений λ₁,..., λ_N, соответствующих этим собственным векторам, причем (все это надо доказывать, конечно) с точностью до перестановки этот набор зависит только от матрицы A и называется ее спектром. В нашем примере спектр матрицы состоит из чисел (5,−1,−1); обратите внимание, что в нем появляются не только отрицательные числа, но и кратные значения, т. е. одному и тому же собственному значению могут соответствовать несколько (линейно независимых!) собственных векторов.

В заключение нашего краткого экскурса в линейную алгебру скажем, как мы уже обещали, несколько слов про теорию размерности. Векторы X¹,...,X^M размерности N называются линейно независимыми, если не существует никакой нетривиальной (т. е. такой, в которой хотя бы одно из α_i отлично от 0) линейной комбинации α₁X¹ + ... + α_MX^M, равной нулевому вектору. Число линейно независимых векторов M в такой системе не превосходит размерности N, и в случае M = N система линейно независимых векторов называется базисом. Базисы можно также охарактеризовать в противоположных (или, как часто говорят математики, двойственных) терминах. Именно, система X¹,...,X^N N-мерных векторов является базисом тогда и только тогда, когда любой другой N-мерный вектор Y можно выразить в виде линейной комбинации α₁X¹ + ... α_NX^N.

Вернемся к доказательству выделенного курсивом утверждения перед упражнением 19. В качестве первого шага Хуан конструирует специальную симметрическую матрицу A_n размера N x N, где N = 2ⁿ, строки и столбцы которой занумерованы всеми вершинами гиперкуба x, y (а не только элементами V_n). Все элементы в этой матрице равны 0, 1 или −1 , причем A_n(x,y) = 0 тогда и только тогда, когда x и y не соединены ребром (в частности, A_n (x,x) = 0 на диагонали).

Если бы вхождений −1 в матрице A_n не было вообще, то она называлась бы матрицей смежности (гиперкуба); это очень важный объект в теории графов. Ее спектр хорошо известен, но он не тот, что нам нужен. Путем замены 1 на −1 в правильным образом выбранных местах удается добиться того, что спектр будет состоять ровно из N/2 значений n^1/2 и N/2 значений −n^1/2.

Далее, множество вершин V_n определяет симметрическую подматрицу B_n в A_n. Эта подматрица имеет большой размер, и мы хотим вывести отсюда какое-нибудь нетривиальное заключение про ее спектр. Слегка упрощая доказательство Хуана, рассмотрим систему, состоящую из N/2 линейно независимых собственных векторов X₁,...,X^N/2 матрицы A_n, соответствующих собственному значению n^1/2 , а также векторов Y^υ , для каждого υ ∈ V_n, в которых в υ-й позиции стоит 1, а все остальные позиции заполнены нулями. Векторов в этой системе строго больше, чем N, поэтому базисом она быть не может. Следовательно, существует нетривиальное равенство вида \(\alpha_1X^1+...+\alpha_{N/2}X^{N/2}+\sum {_{\upsilon \in V_n}} \beta_\upsilon Y^\upsilon =0\); легко понять (проверьте!), что тогда \(\sum {_{\upsilon \in V_n}} \beta_\upsilon Y^\upsilon\) будет нетривиальным собственным вектором матрицы B_n, и ему все еще соответствует собственное значение n^1/2.

Наконец доказывается, что максимальная степень в графе H_n не меньше, чем любое собственное значение матрицы B_n. Если бы отрицательных вхождений −1 в матрице B_n не было (т. е. B_n была бы просто матрицей смежности), то этот факт широко известен и не менее широко применятся в теории графов. Замена некоторых 1 на −1 этому рассуждению только помогает, и это легко проверяется.

Вот собственно и все.

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

Литература:

1. Huang H. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. — Annals of Mathematics, 190(3):949–955, 2019.

2. Разборов А.А. Теория сложности. В книге: Математическая составляющая, 2-е изд. — М.: Математические этюды, 2019.

3. Hatami P., Kulkarni R. and Pankratov D. Variations on the sensitivity conjecture. — Theory of Computing Library, Graduate Surveys, 4:1–27, 2011.

---

¹ Здесь стоит напомнить, что 1 и 0 могут рассматриваться не только как логические константы ИСТИНА и ЛОЖЬ, но и просто как вещественные числа.

² Термин «вход» будет иногда использоваться в дальнейшем в качестве сокращения для «входное слово x ∈ {0,1}ⁿ».

³ Коэффициент λ вполне может быть нулевым или отрицательным!