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

История

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

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

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

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

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

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

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

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

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

${\displaystyle [{{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}$ , откуда и следует равенство и, очевидным образом, теорема о нулях.

Приложения

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

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

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

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

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

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

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

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

Далее ${\displaystyle p}$ — простое число.

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

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

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

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

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

См. также

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

Примечания