WikiSort.ru - Не сортированное

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

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

Далее при заданном условии на степени монома ${\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})}}}}$

откуда и следует очевидным образом теорема о нулях.

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

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

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