Комбінаторна теорема про нулі

Комбінаторна теорема про нулі (теорема Алона, combinatorial 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$ цей многочлен завжди перетворюється на нуль, що суперечить комбінаторній теоремі про нулі.

Див. також

• Арифметична комбінаторика
• Многочлен Лагранжа