Комбинаторная теорема о нулях

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

История

Впервые теорема была доказана и применена в статье Ноги Алона и Мишеля Тарси 1989 года и в дальнейшем развита Алоном, Натанзоном и Рузса в 1995—1996 годах. Она была переформулирована Алоном в 1999 году.

Формулировка теоремы

Далее запись $[{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f(x_{1},\dots ,x_{n})$ означает коэффициент многочлена $f$ при одночлене ${x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}$ в многочлене $f$.

Пусть $f(x_{1},\dots ,x_{n})$ — многочлен над некоторым полем $K$ и ${x_{1}}^{d_{1}}{x_{2}}^{d_{2}}\dots {x_{n}}^{d_{n}}$ — его старший моном в том смысле, что в любом другом мономе (с ненулевым коэффициентом) степень хотя бы одной переменной меньше, чем в данном.

Теорема утверждает, что если $[{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f\not =0$, то для любых множеств $A_{1},\dots ,A_{n}$ с мощностями $|A_{i}|\geq d_{i}+1$, найдутся $a_{i}\in A_{i}$ такие, что $f(a_{1},\dots ,a_{n})\not =0$.

Интерполяционный многочлен

Теорема непосредственно следует из обобщения формулы интерполяционного многочлена Лагранжа $f(x)=\sum \limits _{i=0}^{n}{y_{i}\prod \limits _{i\not =j}{\frac {x-x_{j}}{x_{i}-x_{j}}}}$ для многочлена $f$ степени $n$.

Из формулы Лагранжа можно вычленить старший коэффициент многочлена $[x^{n}]f=\sum \limits _{i=0}^{n}{{y_{i}}\prod \limits _{i\not =j}{\frac {1}{x_{i}-x_{j}}}}$. В частности, правая часть зануляется на любом многочлене степени n−1.

Поэтому при заданном условии на степени монома ${x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}$ эта формула обобщается: правая часть

$[{{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})}}}$

может зависеть только от ${\textstyle [{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f}$, откуда и следует равенство и, очевидным образом, теорема о нулях.

Приложения

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

Теорема Алона — Фридланда — Калаи

Рассмотрим для примера следующую теорему:

Пусть $p$ — простое число и для графа $G=(V,E)$ максимальная степень $\Delta (G)\leq 2p-1$, а средняя степень ${\frac {2|E|}{|V|}}>2p-2$. Тогда в $G$ есть $p$-регулярный подграф.

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

$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})$

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

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

Усиление теоремы Коши — Давенпорта

Основная статья: Теорема Коши — Давенпорта

Далее $p$ — простое число.

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

Однако для её усиления вида $|A\oplus B|=|\{{a+b:a\in A,b\in B,a\not =b}\}|\geq \min\{{p,|A|+|B|-2}\}$ для $A\subset {\mathbb {Z} }_{p},B\subset {\mathbb {Z} }_{p},A\not =B$ пока не удаётся найти комбинаторного доказательства. Но она легко доказывается через комбинаторную теорему о нулях.

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

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

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

См. также

• Арифметическая комбинаторика
• Интерполяционный многочлен Лагранжа