Метод полиномов в комбинаторике - Polynomial method in combinatorics

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

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

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

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

Пример

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

Конечное поле Какейя Гипотеза: Позволять ${\displaystyle \mathbb {F} _{q}}$ конечное поле с ${\displaystyle q}$ элементы. Позволять ${\displaystyle K\subseteq \mathbb {F} _{q}^{n}}$ быть набором Какейя, т.е. для каждого вектора ${\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 \choose 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|}$ линейные уравнения для коэффициентов.

Теперь воспользуемся тем свойством, что ${\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}$

для всех ненулевых ${\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] с исходной структурой, разработанной на аналогичной проблеме над ${\displaystyle \mathbb {Z} _{4}^{n}}$ Крут, Лев и Пах^[8]

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

Смотрите также

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

Рекомендации

1. Гут, Л. (2016). Полиномиальные методы в комбинаторике. Серия университетских лекций. Американское математическое общество. ISBN  978-1-4704-2890-7. Получено 2019-12-11.
2. Алон, Нога (1999). «Комбинаторный Nullstellensatz». Комбинаторика, теория вероятностей и вычисления. 8 (1–2): 7–29. Дои:10.1017 / S0963548398003411. ISSN  0963-5483.
3. Двир, Зеев (2008). «О размере множеств Какейя в конечных полях». Журнал Американского математического общества. 22 (4): 1093–1097. Дои:10.1090 / S0894-0347-08-00607-3. ISSN  0894-0347.
4. Гут, Ларри; Кац, Сети (2015). «О проблеме различных расстояний Эрдеша на плоскости». Анналы математики: 155–190. Дои:10.4007 / анналы.2015.181.1.2. HDL:1721.1/92873. ISSN  0003-486X.
5. Каплан, Хаим; Матушек, Иржи; Шарир, Миха (2012). "Простые доказательства классических теорем в дискретной геометрии с помощью техники многочленов Гута – Каца". Дискретная и вычислительная геометрия. 48 (3): 499–517. arXiv:1102.5391. Дои:10.1007 / s00454-012-9443-3. ISSN  0179-5376.
6. Двир, Зеев (2012). «Теоремы инцидентности и их приложения». Основы и тенденции теоретической информатики. 6 (4): 257–393. arXiv:1208.5073. Bibcode:2012arXiv1208.5073D. Дои:10.1561/0400000056. ISSN  1551-305X.
7. Элленберг, Иордания; Гийсвейт, Дион (2017). "На больших подмножествах ${\displaystyle \mathbb {F} _{q}^{n}}$ без трехчленной арифметической прогрессии ". Анналы математики. 185 (1): 339–343. Дои:10.4007 / анналы.2017.185.1.8. ISSN  0003-486X.
8. Крут, Эрни; Лев, Всеволод; Пах, Петер (2017). "Наборы без прогрессирования в ${\displaystyle \mathbb {Z} _{4}^{n}}$ экспоненциально малы " (PDF). Анналы математики. 185 (1): 331–337. Дои:10.4007 / анналы.2017.185.1.7. ISSN  0003-486X.
9. Гут, Ларри; Кац, Nets Hawk (2010). «Алгебраические методы в дискретных аналогах проблемы Какея». Успехи в математике. 225 (5): 2828–2839. arXiv:0812.1043. Дои:10.1016 / j.aim.2010.05.015. ISSN  0001-8708.
10. Элекес, Дьёрдь; Каплан, Хаим; Шарир, Миха (2011). «О линиях, суставах и падениях в трех измерениях». Журнал комбинаторной теории, серия А. 118 (3): 962–977. Дои:10.1016 / j.jcta.2010.11.008. ISSN  0097-3165.

Внешняя ссылка

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