Лемма Шварца — Зиппеля (Lybbg Ofgjeg — {nhhylx)

Лемма Шварца — Зиппеля (также лемма Де Милло — Липтона — Шварца — Зиппеля) — результат, широко используемый в проверке равенства многочленов, то есть, в задаче проверки некоторого многочлена многих переменных на тождественное равенство нулю. Лемма была независимо открыта Джеком Шварцем, Ричардом Зиппелем, а также Ричардом Де Милло и Ричардом Липтоном, хотя версия Де Милло и Липтона появилась на год раньше результата Шварца и Зиппеля. Версия леммы для конечных полей было доказана Ойстином Оре в 1922 году.

Лемма

Входом задачи является многочлен от $n$ переменных над полем $\mathbb {F}$. Он может быть в задан в виде арифметической схемы или как определитель некоторой матрицы многочленов. На текущий момент нет известных детерминированных субэкспоненциальных алгоритмов, позволяющих проверить, что этот многочлен ненулевой. Однако, есть известные рандомизированные алгоритмы, решающие данную задачу за полиномиальное время. При их анализе обычно требуется оценить вероятность того, что ненулевой многочлен будет равен нулю в некоторой случайным образом выбранной точке. Лемма Шварца — Зиппеля формулируется так:

Пусть $P\in F[x_{1},x_{2},\dots ,x_{n}]$ — ненулевой многочлен степени $d\geq 0$ над полем $\mathbb {F}$. Пусть $S$ — конечное подмножество $\mathbb {F}$ и пусть элементы $r_{1},r_{2},\dots ,r_{n}$ были выбраны из $S$ равномерно и независимо друг от друга. Тогда $\Pr[P(r_{1},r_{2},\dots ,r_{n})=0]\leq {\frac {d}{\vert S\vert }}$.

Доказательство

В случае одной переменной лемма следует напрямую из того, что у многочлена степени $d$ может быть не больше $d$ различных корней над полем $\mathbb {F}$.

Доказать лемму в общем виде можно математической индукцией по количеству переменных $n$. Базовый случай $n=1$ был доказан выше.

Пусть теперь теорема верна для всех многочленов на $n-1$ переменных. Можно рассматривать $P$ как многочлен от $x_{1}$, записав его в виде

$P(x_{1},\dots ,x_{n})=\sum _{i=0}^{d}x_{1}^{i}P_{i}(x_{2},\dots ,x_{n})$.

Так как $P$ не равен нулю тождественно, существует некоторый номер $i$ такой что $P_{i}$ также не равен нулю. Пусть $i$ — наибольший из таких номеров. Тогда $\deg P_{i}\leq d-i$, так как степень $x_{1}^{i}P_{i}$ не превосходит $d$.

Пусть теперь $r_{2},\dots ,r_{n}$ выбраны случайно из $S$. По предположению индукции, $\Pr[P_{i}(r_{2},\ldots ,r_{n})=0]\leq {\frac {d-i}{|S|}}$.

Если $P_{i}(r_{2},\ldots ,r_{n})\neq 0$, то $P(x_{1},r_{2},\ldots ,r_{n})$ имеет степень $i$ (и потому не равен нулю тождественно), поэтому

$\Pr[P(r_{1},r_{2},\ldots ,r_{n})=0|P_{i}(r_{2},\ldots ,r_{n})\neq 0]\leq {\frac {i}{|S|}}$.

Если обозначить событие $P(r_{1},r_{2},\ldots ,r_{n})=0$ как $A$, событие $P_{i}(r_{2},\ldots ,r_{n})=0$ как $B$ и дополнительное к $B$ событие как $B^{c}$, то

${\begin{aligned}\Pr[A]&=\Pr[A\cap B]+\Pr[A\cap B^{c}]\\&=\Pr[B]\Pr[A|B]+\Pr[B^{c}]\Pr[A|B^{c}]\\&\leq \Pr[B]+\Pr[A|B^{c}]\\&\leq {\frac {d-i}{|S|}}+{\frac {i}{|S|}}={\frac {d}{|S|}}\end{aligned}}$■

Применения

Значимость леммы Шварца — Зиппеля и проверки равенства многочленов следует из алгоритмов, которые могут быть сведены к этой задаче.

Сравнение двух многочленов

Даны два многочлена $p_{1}(x)$ и $p_{2}(x)$, верно ли, что

$p_{1}(x)\equiv p_{2}(x)?$

Данную задачу можно свести к проверке равенства многочленов, так как достаточно проверить, что

$[p_{1}(x)-p_{2}(x)]\equiv 0.$

Таким образом, если возможно определить, что

$p(x)\equiv 0,$

где

$p(x)=p_{1}(x)\;-\;p_{2}(x),$

то также можно определить, равны ли данные два многочлена.

Сравнение двух многочленов может быть использовано в анализе программ с ветвлением. Read-once программа с ветвлением может быть представлена в виде мультилинейного многочлена, который вычисляет (над некоторым полем) на входе из нулей и единиц ту же булеву функцию, что и программа с ветвлением. Таким образом, две программы с ветвлением вычисляют одну и ту же булеву функцию если и только если соответствующие многочлены равны. Значит, проверка равенства булевых функций, которые вычисляются read-once программами с ветвлением может быть сведена к проверке равенства многочленов.

Проверка простоты

Дано число $n\in \mathbb {Z^{+}}$, является ли $n$ простым числом?

Маниндра Аграваль и Соменат Бисвас разработали простой рандомизированный алгоритм, использующий проверки равенства многочленов для определения простоты числа $n$.

Они показали, что все простые числа $n$ (и только простые числа) удовлетворяют следующему сравнению:

$(1+z)^{n}=1+z^{n}({\mbox{mod}}\;n).$

Указанный результат следует из эндоморфизма Фробениуса.

Пусть

${\mathcal {P}}_{n}(z)=(1+z)^{n}-1-z^{n}.$

Тогда ${\mathcal {P}}_{n}(z)=0\;({\mbox{mod}}\;n)$ если и только если $n$ является простым числом. Однако так как $n$ может как быть, так и не быть простым числом, метод Шварца — Зиппеля здесь работать не будет. Аграваль и Бисвас используют более сложную технику, которая включает в себя деление ${\mathcal {P}}_{n}$ на случайный приведённый многочлен небольшой степени.

Совершенное паросочетание

Дан граф $G=(V,E)$ на $n$ вершинах, где $n$ — чётное число. Содержит ли $G$ совершенное паросочетание?

Определитель матрицы Татта не является тождественно нулевым многочленом если и только если в графе есть совершенное паросочетание.

(Tutte 1947)

Подмножество $D$ множества рёбер $E$ называется паросочетанием если каждая вершина из $V$ инцидентна не более, чем одному ребру из $D$. Паросочетание называется совершенным если каждая вершина из $V$ инцидентна ровно одному ребру из $D$. Матрица Татта $A$ это матрица:

$A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1{\mathit {n}}}\\a_{21}&a_{22}&\cdots &a_{2{\mathit {n}}}\\\vdots &\vdots &\ddots &\vdots \\a_{{\mathit {n}}1}&a_{{\mathit {n}}2}&\ldots &a_{\mathit {nn}}\end{bmatrix}}$

где

$a_{ij}={\begin{cases}x_{ij}\;\;{\mbox{если}}\;(i,j)\in E{\mbox{ и }}i<j\\-x_{ji}\;\;{\mbox{если}}\;(i,j)\in E{\mbox{ и }}i>j\\0\;\;\;\;{\mbox{иначе}}.\end{cases}}$

Определитель матрицы Татта (как многочлен от $x_{ij},i<j$) задаётся как определитель этой кососимметричной матрицы, который равен квадрату пфаффиана матрицы $A$ и не равен нулю тождественно если и только если в графе есть совершенное паросочетание.

Таким образом, используя проверку равенства многочленов, можно проверить, содержит ли произвольный граф $G$ совершенное паросочетание.

В особом случае сбалансированного двудольного графа на $n=m+m$ вершинах матрица Татта принимает вид блочной матрицы

$A={\begin{pmatrix}0&X\\-X^{t}&0\end{pmatrix}}$

Первые $m$ строк (и, соответственно, столбцов) индексированы первой долей двудольного графа, а последние $m$ строк — второй долей. В данном случае пфаффиан (с точностью до знака) совпадает с обычным определителем матрицы $X$ размера $m\times m$. Матрица $X$ при этом является матрицей Эдмондса данного двудольного графа.

Ссылки

• The Curious History of the Schwartz-Zippel Lemma, by Richard J. Lipton