# Как граф длины три объясняет структуру чисел: разбор теоремы BSG в MIT

Источник: https://www.youtube.com/watch?v=DGBuM5pEdoo
Канал: MIT OpenCourseWare
Опубликовано: 03.11.2025

---

В рамках курса MIT OpenCourseWare по аддитивной комбинаторике профессор Лоуренс Гут (Lawrence Guth) представил доказательство одной из центральных теорем дисциплины — теоремы Балога — Семереди — Гауэрса. Этот результат, связывающий структуру графов с теорией чисел, стал фундаментом для многих современных достижений в математике, предлагая изящное решение сложной проблемы аддитивной структуры множеств.

## 🔢 Суть и формулировка теоремы Балога — Семереди — Гауэрса
[[JUMP:00:12]]

Теорема Балога — Семереди — Гауэрса (BSG) описывает ситуацию, когда в подмножестве пар чисел наблюдается аномально много «аддитивных совпадений». В классической постановке рассматриваются два множества $A$ и $B$ в абелевой группе, размер которых не превышает $N$ [01:00]. Если мы выберем достаточно большое подмножество пар $X$ (где размер $X$ пропорционален $k^{-1}N^2$), а количество различных сумм вида $a+b$ для этих пар (обозначаемое как $\pi_1(X)$) окажется неожиданно малым, то это свидетельствует о скрытой структуре множеств [01:14].

Ключевые выводы теоремы:

*   Существуют значительные подмножества $A' \subset A$ и $B' \subset B$, которые сами по себе «почти» являются арифметическими прогрессиями или имеют малую удвоенную сумму [02:05].
*   Размер суммы этих подмножеств $A' + B'$ ограничен полиномом от параметра $k$, умноженным на $N$ [03:07].
*   Это означает, что если в большом наборе пар суммы ведут себя «дружелюбно», то внутри исходных множеств можно найти плотные ядра с очень жесткой аддитивной структурой [02:32].

Профессор Гут приводит пример: если $A$ и $B$ — это просто числа от 1 до $N$ с добавлением некоторого количества случайного «мусора», то теорема позволяет эффективно отсечь этот шум и найти структурную основу множеств [03:50].

## 📜 История вопроса: от «ужасных» границ к полиномам
[[JUMP:05:12]]

История теоремы — это путь от качественного понимания к количественной точности. Первоначальное доказательство было предложено математиками Балогом и Семереди. Однако их метод опирался на знаменитую лемму Семереди о регулярности графов [05:25].

По словам Лоуренса Гута, оценки в оригинальной работе были «действительно ужасными» [06:11]:

1.  Зависимость параметров представляла собой «башню» экспонент (tower of exponentials) [05:57].
2.  Хотя результат был качественным триумфом, он был практически бесполезен для приложений, требующих эффективных вычислений.

Ситуация изменилась в 1990-х годах, когда британский математик Тимоти Гауэрс (Gowers) пересмотрел теорему [06:24]. Он предложил новое доказательство, которое дало полиномиальную зависимость параметров. Именно этот вариант, который Гут называет «умным, но не слишком сложным», стал стандартом в современной аддитивной комбинаторике [06:52].

## 🕸 Графовый подход: визуализация через пути длины 3
[[JUMP:07:07]]

Для доказательства теоремы математики используют теорию графов. Множество пар $X$ представляется как двудольный граф, где вершины левой доли — элементы множества $A$, правой — множества $B$, а наличие ребра означает, что пара $(a, b)$ принадлежит $X$ [07:36].

Центральным понятием здесь становится количество путей длины $k$ между вершинами, обозначаемое как $P_k(a, b)$ [08:24]. Профессор акцентирует внимание на путях длины 3:

*   Путь длины 3 между $a$ и $b$ выглядит как цепочка $a \to b_1 \to a_1 \to b$ [11:15].
*   Математическая связь заключается в том, что сумму $a+b$ можно выразить через другие суммы в графе: $a+b = (a+b_1) - (a_1+b_1) + (a_1+b)$ [12:04].
*   Если между парой вершин существует много таких путей, это гарантирует, что сумма $a+b$ может быть представлена множеством способов через элементы множества сумм $\pi_1(X)$ [13:18].

## 📐 Оценки путей и использование неравенства Коши — Буняковского
[[JUMP:21:11]]

Для того чтобы доказать существование «хороших» подмножеств, необходимо оценить количество путей в графе. Гут демонстрирует, как элементарные вероятностные методы и неравенство Коши — Буняковского позволяют получить нижние границы для путей различной длины [24:35].

Основные технические выводы:

*   **Пути длины 1:** Это просто количество ребер в графе, которое по условию велико ($|X| \ge K^{-1}AB$) [21:50].
*   **Пути длины 2:** Среднее количество путей $P_2(a_1, a_2)$ между двумя вершинами левой доли составляет как минимум $K^{-2}B$ [26:15].
*   **Пути длины 3:** В среднем между любыми $a \in A$ и $b \in B$ существует не менее $K^{-3}AB$ путей [26:47].

Однако средней оценки недостаточно. Математикам нужно найти такие подмножества, где для *каждой* пары вершин количество путей велико. Это значительно сложнее, так как граф может быть крайне неоднородным (например, состоять из отдельных плотных кластеров) [42:11].

## 🛠 Алгоритм «очистки» и выбор подмножеств
[[JUMP:1:00:08]]

Доказательство ключевой леммы строится в несколько этапов, которые профессор Гут описывает как процесс «селекции» лучших элементов:

1.  **Первичное удаление (Pruning):** Сначала из множества $A$ удаляются вершины с аномально низкой степенью (те, у которых слишком мало соседей в $B$) [1:00:36].
2.  **Выбор окрестности:** В качестве нового множества $A'$ выбирается окрестность какой-то «хорошей» вершины $b$ из множества $B$ [51:27].
3.  **Разделение на «хорошие» и «плохие» пары:** Внутри выбранного множества выделяются пары, между которыми достаточно путей длины 2. С помощью линейности ожидания доказывается, что «плохих» пар будет немного [49:50].
4.  **Финальная фильтрация:** На последнем этапе определяется подмножество $B'$, состоящее из вершин, имеющих много связей с отобранным «ядром» в $A$ [1:04:13].

В итоге получается структура, в которой любая пара $(a, b)$ из новых множеств $A'$ и $B'$ соединена огромным количеством путей длины 3 [1:06:54].

## 🏛 Заключение: Почему это удивляет?
[[JUMP:1:12:10]]

В завершение лекции Лоуренс Гут делится своим видением того, почему это доказательство до сих пор поражает математиков. Несмотря на то, что аддитивная комбинаторика часто использует мощные инструменты анализа Фурье, в данном случае они оказываются малоэффективными [1:12:39].

По мнению Гута, удивительно то, что:

*   Чистая линейная алгебра также не дает прямого пути к решению, хотя задачу можно сформулировать через степени матриц смежности [1:13:24].
*   Победу одерживает «элементарный, но изощренный» двойной подсчет в теории графов [1:13:37].

Теорема Балога — Семереди — Гауэрса остается одним из самых полезных инструментов в арсенале математика, позволяя переходить от слабых корреляций к жестким алгебраическим структурам [1:14:17].