Interested Article - Лемма Шварца — Зиппеля

Лемма Шварца — Зиппеля (также лемма Де Милло — Липтона — Шварца — Зиппеля ) — результат, широко используемый в , то есть, в задаче проверки некоторого многочлена многих переменных на тождественное равенство нулю. Лемма была независимо открыта , , а также и Ричардом Липтоном , хотя версия Де Милло и Липтона появилась на год раньше результата Шварца и Зиппеля . Версия леммы для конечных полей было доказана Ойстином Оре в 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$ совершенное паросочетание ?

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

( )

Подмножество $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$ при этом является данного двудольного графа.

Примечания

( )
( )
( )
Ö. Ore, Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I (1922), no. 7, 15 pages.
( )

Литература

Agrawal, Manindra; Biswas, Somenath. (англ.) // Journal of the ACM : journal. — 2003. — Vol. 50 , no. 4 . — P. 429—443 . — doi : .
Berman, Piotr; (англ.) ( ; Larmore, Lawrence L.; Plandowski, Wojciech; (англ.) ( . (англ.) // (англ.) ( : journal. — 2002. — Vol. 65 , no. 2 . — P. 332—350 . — doi : .
Grigoriev, Dima; Karpinski, Marek. The matching problem for bipartite graphs with polynomially bounded permanents is in NC (англ.) . — 1987. — P. 166—172. — ISBN 978-0-8186-0807-0 . — doi : .
(2010). An Alternative Proof of The Schwartz-Zippel Lemma.
(англ.) ( ; (англ.) ( . A probabilistic remark on algebraic program testing (англ.) // (англ.) ( : journal. — 1978. — Vol. 7 . — P. 193—195 . — doi : .
Rudich, Steven. Computational Complexity Theory (неопр.) / AMS. — 2004. — Т. 10. — (IAS/Park City Mathematics Series). — ISBN 978-0-8218-2872-4 .
(англ.) ( . (англ.) // Journal of the ACM : journal. — 1980. — October ( vol. 27 , no. 4 ). — P. 701—717 . — doi : .
(англ.) ( . (неопр.) // J. London Math. Soc.. — 1947. — April ( т. 22 , № 2 ). — С. 107—111 . — doi : .
Zippel, Richard. Probabilistic algorithms for sparse polynomials (англ.) . — 1979. — Vol. 72. — P. 216—226. — ISBN 978-3-540-09519-4 . — doi : .
Zippel, Richard (ps) (февраль 1989). Дата обращения: 15 июня 2008.
Zippel, Richard. (неопр.) / (англ.) ( . — 1993. — Т. 241. — (The Springer International Series in Engineering and Computer Science). — ISBN 978-0-7923-9375-7 .