Полиномиальный метод в комбинаторике

В математике полиномиальный метод — это алгебраический подход к задачам комбинаторики , который включает в себя определение некоторой комбинаторной структуры с помощью полиномов и обсуждение их алгебраических свойств. Недавно полиномиальный метод привел к разработке удивительно простых решений нескольких давних открытых проблем. Полиномиальный метод охватывает широкий спектр конкретных методов использования полиномов и идей из таких областей, как алгебраическая геометрия, для решения комбинаторных задач. Хотя некоторые методы, которые следуют структуре полиномиального метода, такие как комбинаторный Nullstellensatz Алона , известны с 1990-х годов, только примерно в 2010 году была разработана более широкая основа полиномиального метода.

Математический обзор

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

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

Пример

В качестве примера мы приведем доказательство Двиром гипотезы Какеи о конечном поле с использованием полиномиального метода.

Гипотеза Какеи о конечном поле : пусть $\mathbb {F} _{q}$ быть конечным полем с $q$ элементы. Позволять $K\subseteq \mathbb {F} _{q}^{n}$ быть множеством Какеи, т.е. для каждого вектора $y\in \mathbb {F} _{q}^{n}$существует $x\in \mathbb {F} _{q}^{n}$ такой, что $K$ содержит строку $\{x+ty,t\in \mathbb {F} _{q}\}$. Тогда набор $K$ имеет размер как минимум $c_{n}q^{n}$где $c_{n}>0$ является константой, которая зависит только от $n$.

Доказательство: Доказательство, которое мы приведем, покажет, что $K$ имеет размер как минимум $c_{n}q^{n-1}$. Граница $c_{n}q^{n}$ можно получить тем же методом, проделав небольшую дополнительную работу.

Предположим, у нас есть набор Какеи. $K$ с

$|K|<{q+n-3 \choose n-1}$

Рассмотрим множество мономов вида $x_{1}^{d_{1}}x_{2}^{d_{2}}\dots x_{n}^{d_{n}}$ степени точно $q-2$. Есть точно ${q+n-3 \choose n-1}$ такие мономы. Таким образом, существует ненулевой однородный полином $P(x_{1},x_{2},\dots ,x_{n})$ степени $q-2$ который исчезает во всех точках $K$. Обратите внимание: это связано с тем, что нахождение такого полинома сводится к решению системы уравнений. $|K|$ линейные уравнения для коэффициентов.

Теперь мы воспользуемся свойством, которое $K$ набор Какеи, чтобы показать это $P$ должен исчезнуть на всех $\mathbb {F} _{q}^{n}$. Четко $P(0,0\dots ,0)=0$. Далее, для $y\neq 0$, есть $x$ такой, что линия $\{x+ty,t\in \mathbb {F} _{q}\}$ содержится в $K$. С $P$ является однородным, если $P(z)=0$ для некоторых $z\in \mathbb {F} _{q}^{n}$ затем $P(cz)=0$ для любого $c\in \mathbb {F} _{q}$. В частности

$P(tx+y)=P(t(x+t^{-1}y))=0$

для всех ненулевых $t\in \mathbb {F} _{q}$. Однако, $P(tx+y)$ является полиномом степени $q-2$ в $t$ но у него есть по крайней мере $q-1$ корни, соответствующие ненулевым элементам $\mathbb {F} _{q}$ поэтому он должен быть тождественно нулю. В частности, подключение $t=0$ мы делаем вывод $P(y)=0$.

Мы показали, что $P(y)=0$ для всех $y\in \mathbb {F} _{q}^{n}$ но $P$ имеет степень меньше $q-1$ в каждой из переменных, поэтому это невозможно по лемме Шварца–Циппеля . Мы приходим к выводу, что на самом деле мы должны иметь

$|K|\geq {q+n-3 \choose n-1}\sim {\frac {q^{n-1}}{(n-1)!}}$

Полиномиальное разбиение

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

Приложения

Вот несколько примеров давних открытых проблем, которые были решены с использованием полиномиального метода:

• поле Гипотеза Какеи о конечном от Двир
• Проблема набора ограничений Элленберга и Гейсвейта с исходной структурой, разработанной для решения аналогичной проблемы $\mathbb {Z} _{4}^{n}$ Крут, Лев и Пах
• о различных расстояниях Эрдеша Задача Гута и Каца
• Проблема суставов в 3D Гута и Каца. Их аргументы позже были упрощены Элекесом, Капланом и Шариром.

См. также

• Комбинаторная теорема о нулевом месте

Внешние ссылки

• по полиномиальному методу Обзор Теренса Тао
• Обзор полиномиального метода Ларри Гута