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

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

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

Далее запись ${\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}$ пока не удаётся найти комбинаторного доказательства. Но она легко доказывается через комбинаторную теорему о нулях.^[4]

Докажем это усиление от противного. Будем предполагать, что ${\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}$ этот многочлен всегда обращается в ноль, что противоречит комбинаторной теореме о нулях.

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

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (20 октября 2024)