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

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