Метод полиномов в комбинаторике

В математике полиномиальный метод - это алгебраический подход к задачам комбинаторики, который включает в себя захват некоторой комбинаторной структуры с использованием полиномов и обсуждение их алгебраических свойств. В последнее время полиномиальный метод привел к разработке замечательно простых решений нескольких давних открытых проблем. ^[1] Метод полиномов включает в себя широкий спектр конкретных методов использования полиномов и идей из таких областей, как алгебраическая геометрия, для решения задач комбинаторики. В то время как несколько методов, которые следуют структуре полиномиального метода, такие как Combinatorial Nullstellensatz Алона , ^[2] были известны с 1990-х годов, только примерно в 2010 году была разработана более широкая основа для полиномиального метода.

Математический обзор [ править ]

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

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

Пример [ править ]

В качестве примера мы приводим доказательство Двира гипотезы Какейя с конечным полем с использованием полиномиального метода. ^[3]

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

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

Предположим, у нас есть набор Какея с ${\ displaystyle K}$

${\ displaystyle | K | <{q + n-3 \ выберите n-1}}$

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

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

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

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

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

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

Полиномиальное разбиение [ править ]

Вариант полиномиального метода, часто называемый полиномиальным разбиением, был введен Гутом и Кацем в их решении проблемы различных расстояний Эрдеша . ^[4] Полиномиальное разбиение включает использование многочленов для разделения основного пространства на регионы и обсуждение геометрической структуры разбиения. Эти аргументы опираются на результаты алгебраической геометрии, ограничивающие количество инцидентностей между различными алгебраическими кривыми. Техника полиномиального разбиения была использована для нового доказательства теоремы Семереди – Троттера с помощью полиномиальной теоремы о бутерброде ветчины и была применена к множеству задач в инцидентной геометрии. ^{[5] [6]}

Приложения [ править ]

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

• Гипотеза Какея конечного поля ^[3] Двира
• Задача о множестве крышек Элленберга и Гийсвейта ^[7] с исходной структурой, разработанной на основе аналогичной проблемы Кроотом, Львом и Пахом ^[8]${\displaystyle \mathbb {Z} _{4}^{n}}$

• Проблема различных расстояний Эрдеша Гута и Каца ^[4]
• Проблема суставов в 3D Гут и Кац. ^[9] Их аргумент был позже упрощен Элекесом, Капланом и Шариром ^[10]

См. Также [ править ]

• Комбинаторный Nullstellensatz

Ссылки [ править ]

Внешние ссылки [ править ]

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