Просмотр кода страницы Комбинаторная теорема о нулях

'''Комбинаторная теорема о нулях''' (теорема Алона, ''сombinatorial nullstellensatz'') — [[алгебра]]ическая [[теорема]], связывающая коэффициент многочлена при определённом [[одночлен]]е с его значениями. Теорема даёт нижнюю оценку на размеры [[Прямое произведение|комбинаторного параллелепипеда]], на котором многочлен не равен тождественно нулю. Эта оценка зависит от степени старшего одночлена по каждой переменной.

== История ==
Впервые теорема была доказана и применена в статье [[Алон, Нога|Ноги Алона]] и Мишеля Тарси 1989 года<ref>{{статья
|заглавие=A nowhere-zero point in linear mappings
|том=9
|страницы=393—395
|mr=1054015
|doi=10.1007/BF02125351
|номер=4
|язык=und
|автор=[[Алон, Нога|Alon, Noga]]; Tarsi,  Michael
|год=1989}}</ref> и в дальнейшем развита Алоном, Натанзоном и Рузса в 1995—1996 годах.
Она была переформулирована Алоном в 1999 году.<ref name="Alon1999">{{статья
|ссылка=http://www.math.tau.ac.il/~nogaa/PDFS/null2.pdf
|заглавие=Combinatorial Nullstellensatz
|том=8
|номер=1—2
|страницы=7—29
|mr=1684621
|doi=10.1017/S0963548398003411
|язык=und
|автор=[[Алон, Нога|Alon, Noga]]
|год=1999
|archivedate=2016-03-03
|archiveurl=https://web.archive.org/web/20160303170225/http://www.math.tau.ac.il/~nogaa/PDFS/null2.pdf
}}</ref>

== Формулировка теоремы ==
Далее запись <math>[{ {x_1}^{d_1} \dots {x_n}^{d_n} }] f(x_1, \dots, x_n)</math> означает коэффициент многочлена <math>f</math> при одночлене <math>{x_1}^{d_1} \dots {x_n}^{d_n}</math> в многочлене <math>f</math>.

Пусть <math>f(x_1, \dots, x_n)</math> — многочлен над некоторым [[Поле (алгебра)|полем]] <math>K</math> и <math>{x_1}^{d_1} {x_2}^{d_2} \dots {x_n}^{d_n}</math> — его старший моном в том смысле, что в любом другом мономе (с ненулевым коэффициентом) степень хотя бы одной переменной меньше, чем в данном.

Теорема утверждает, что если <math>[{ {x_1}^{d_1} \dots {x_n}^{d_n} }] f \not = 0</math>, то для любых множеств <math>A_1, \dots, A_n</math> с мощностями <math>|A_i| \ge d_i+1</math>, найдутся <math>a_i \in A_i</math> такие, что <math>f(a_1, \dots, a_n) \not = 0</math>.

=== Интерполяционный многочлен ===
Теорема непосредственно следует из обобщения формулы [[Интерполяционный многочлен Лагранжа|интерполяционного многочлена Лагранжа]] <math>f(x) = \sum \limits_{i=0}^{n} {y_i \prod \limits_{i \not = j} {\frac{x-x_j}{x_i-x_j}}}</math> для многочлена <math>f</math> степени <math>n</math>.

Из формулы Лагранжа можно вычленить старший коэффициент многочлена <math>[x^n]f = \sum \limits_{i=0}^{n} {{y_i}\prod \limits_{i \not = j} {\frac 1{x_i-x_j}}}</math>.  В частности, правая часть зануляется на любом многочлене степени ''n''−1.

Поэтому при заданном условии на степени монома <math>{x_1}^{d_1} \dots {x_n}^{d_n}</math> эта формула обобщается: правая часть

<math>[{ {x_1}^{d_1} \dots {x_n}^{d_n} }] f = \sum \limits_{a_1 \in A_1} \dots \sum \limits_{a_n \in A_n} {\frac{f(a_1,\dots,a_n)}{ \prod \limits_{a_1 \not = b_1 \in A_1} \dots \prod \limits_{a_n \not = b_n \in A_n} {(a_1-b_1) \dots (a_n-b_n)} }}</math>

может зависеть только от <math display="inline">[{ {x_1}^{d_1} \dots {x_n}^{d_n} }] f</math>, откуда и следует равенство и, очевидным образом, теорема о нулях.

== Приложения ==
Комбинаторная теорема о нулях может использоваться для доказательства [[Теорема существования|теорем существования]], когда существование ненулевого значения многочлена в некоторой точке означает удовлетворение некоторого объекта искомому свойству, а множество всех объектов (среди которых нужно доказать существование) взаимно-однозначно сопоставляется со множеством возможных наборов значений переменных.

=== Теорема Алона — Фридланда — Калаи ===
Рассмотрим для примера следующую теорему:

{{рамка}}
Пусть <math>p</math> — [[простое число]] и для [[Граф (математика)|графа]] <math>G=(V,E)</math> максимальная степень <math>\Delta(G) \le 2p-1</math>, а средняя степень <math>\frac{2|E|}{|V|} > 2p-2</math>.

Тогда в <math>G</math> есть [[Регулярный граф|<math>p</math>-регулярный]] [[подграф]].<ref>{{Cite web |url=http://www.slideshare.net/AlexDainiak/10-33023021 |title=Теорема Алона о нулях и её применения, МФТИ, весна 2014 |access-date=2016-02-12 |archive-date=2016-11-17 |archive-url=https://web.archive.org/web/20161117120006/http://www.slideshare.net/AlexDainiak/10-33023021 |deadlink=no }}</ref>
{{конец рамки}}

Обозначим через <math>E(v)</math> множество рёбер, смежных вершине <math>v</math>. Для доказательства теоремы рассмотрим многочлен в поле <math>{\mathbb Z}_p</math> {{s|(по модулю <math>p</math>)}} от <math>|E|</math> переменных, соответствующих рёбрам графа.

<math>P(x_1, \dots, x_{|E|}) = \prod \limits_{v \in V} {\left({1 - \left({\sum \limits_{e \in E(v)} {x_e}}\right)^{p-1}}\right)} - \prod \limits_{e \in E} (1 - x_e)</math>

В этом многочлене коэффициент при старшем мономе <math>\prod \limits_{e \in E} {x_e}</math> не равен нулю. При этом, очевидно, <math>P(0, \dots, 0) = 0</math>. Следовательно, существует непустой набор рёбер таких, что если для них положить <math>x_e=1</math>, а для остальных <math>x_e=0</math>, то многочлен на таком наборе примет ненулевое значение.

Так как вычитаемое в <math>P</math> будет нулём на всяком ненулевом наборе, то в рассматриваемом наборе <math>\sum \limits_{e \in E(v)} {x_e} \equiv 0\ (mod\ p)</math> для всех <math>v</math>, то есть в подграфе из этих рёбрер все степени вершин кратны <math>p</math>. А так как они все по условию строго меньше чем <math>2p</math>, то, удалив вершины с нулевой степенью, получим непустой <math>p</math>-регулярный подграф.

=== Усиление теоремы Коши — Давенпорта ===
{{основная статья|Теорема Коши — Давенпорта}}
Далее <math>p</math> — простое число.

Теорема Коши — Давенпорта, утверждающая, что <math>|A+B| = |\{{ a+b : a \in A, b \in B }\}| \ge \min \{{ p, |A|+|B|-1 }\}</math> для <math>A \subset {\mathbb Z}_p, B \subset {\mathbb Z}_p</math>, относительно несложно доказывается элементарными методами.

Однако для её усиления вида <math>|A \oplus B| = |\{{ a+b : a \in A, b \in B, a \not = b }\}| \ge \min \{{ p, |A|+|B|-2 }\}</math> для <math>A \subset {\mathbb Z}_p, B \subset {\mathbb Z}_p, A \not = B</math> пока не удаётся найти комбинаторного доказательства. Но она легко доказывается через комбинаторную теорему о нулях.<ref>[https://www.youtube.com/watch?v=WYi20sqyY2U Аддитивная комбинаторика, открытая библиотека видеолекций, математическая лаборатория имени П. Л. Чебышёва]</ref>

Докажем это усиление от противного. Будем предполагать, что <math>|A|+|B|-2 \le p</math>, потому что иначе из множеств можно просто убрать некоторые элементы.

Если <math>|A|=|B|</math>, то при <math>A \cap B = \varnothing</math> утверждение теоремы соответствует утверждению оригинальной теоремы Коши-Давенпорта. Если же <math>A \cap B \not = \varnothing</math>, то, так как <math>A \not = B</math>, можно воспользоваться тем фактом, что <math>(A \cap B) \oplus (A \cup B) \subset A \oplus B</math> и провести индукцию по размеру минимального из множеств <math>A</math> и <math>B</math>.

Следовательно, достаточно рассмотреть случай <math>|A| \not = |B|</math>. Пусть <math>(A \oplus B) \subset C</math> и <math>|C| = |A| + |B| - 3</math>. Рассмотрим многочлен <math>(x-y) \prod \limits_{c \in C} {(x+y-c)}</math>. Этот многочлен явно имеет ненулевой по модулю <math>p</math> коэффициент при мономе <math>x^{|A|-1} y^{|B|-1}</math>, который выражается через разность биномиальных коэффициентов. Однако для <math>x \in A</math>, <math>y \in B</math> этот многочлен всегда обращается в ноль, что противоречит комбинаторной теореме о нулях.

== См. также ==
* [[Арифметическая комбинаторика]]
* [[Интерполяционный многочлен Лагранжа]]

== Примечания ==
{{примечания|1}}

{{Нет источников |дата=2024-10-20}}

[[Категория:Теоремы алгебры]]
[[Категория:Комбинаторика]]