Просмотр кода страницы Лемма Шварца — Зиппеля

'''Лемма Шварца — Зиппеля''' (также '''лемма Де Милло — Липтона — Шварца — Зиппеля''') — результат, широко используемый в [[Проверка равенства многочленов|проверке равенства многочленов]], то есть, в задаче проверки некоторого [[Многочлен|многочлена]] многих переменных на тождественное равенство нулю. Лемма была независимо открыта [[Шварц, Джек|Джеком Шварцем]]<ref>{{harv|Schwartz|1980}}</ref>, [[Зиппель, Ричард|Ричардом Зиппелем]]<ref>{{harv|Zippel|1979}}</ref>, а также [[Де Милло, Ричард|Ричардом Де Милло]] и [[Липтон, Ричард|Ричардом Липтоном]], хотя версия Де Милло и Липтона появилась на год раньше результата Шварца и Зиппеля<ref>{{harv|DeMillo & Lipton|1978}}</ref>. Версия леммы для [[Конечное поле|конечных полей]] было доказана [[Оре, Ойстин|Ойстином Оре]] в 1922 году<ref>Ö. Ore, Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I (1922), no. 7, 15 pages.</ref>.

== Лемма ==
Входом задачи является многочлен от <math>n</math> переменных над полем <math>\mathbb F</math>. Он может быть в задан в виде [[Арифметическая схема|арифметической схемы]] или как определитель некоторой [[Лямбда-матрицы|матрицы многочленов]]. На текущий момент нет известных ''детерминированных'' субэкспоненциальных алгоритмов, позволяющих проверить, что этот многочлен ненулевой. Однако, есть известные рандомизированные алгоритмы, решающие данную задачу за полиномиальное время. При их анализе обычно требуется оценить вероятность того, что ненулевой многочлен будет равен нулю в некоторой случайным образом выбранной точке. Лемма Шварца — Зиппеля формулируется так:

{{Теорема|''Пусть <math>P \in F[x_1,x_2,\dots,x_n]</math> — ненулевой многочлен [[степень многочлена|степени]] <math>d \geq 0</math> над [[поле (алгебра)|полем]] <math>\mathbb F</math>. Пусть <math>S</math> — конечное подмножество <math>\mathbb F</math> и пусть элементы <math>r_1, r_2, \dots, r_n</math> были выбраны из <math>S</math> равномерно и независимо друг от друга. Тогда <math>\Pr[P(r_1,r_2,\dots,r_n)=0] \leq \frac{d}{\vert S\vert}</math>.''}}
{{Доказательство|В случае одной переменной лемма следует напрямую из того, что у многочлена [[степень многочлена|степени]] <math>d</math> может быть не больше <math>d</math> различных корней над полем <math>\mathbb F</math>.

Доказать лемму в общем виде можно [[математическая индукция|математической индукцией]] по количеству переменных <math>n</math>. Базовый случай <math>n=1</math> был доказан выше. 

Пусть теперь теорема верна для всех многочленов на <math>n-1</math> переменных. Можно рассматривать <math>P</math> как многочлен от <math>x_1</math>, записав его в виде

:<math>P(x_1,\dots,x_n)=\sum_{i=0}^d x_1^i P_i(x_2,\dots,x_n)</math>.

Так как <math>P</math> не равен нулю тождественно, существует некоторый номер <math>i</math> такой что <math>P_i</math> также не равен нулю. Пусть <math>i</math> — наибольший из таких номеров. Тогда <math>\deg P_i\leq d-i</math>, так как степень <math>x_1^iP_i</math> не превосходит <math>d</math>.

Пусть теперь <math>r_2,\dots,r_n</math> выбраны случайно из <math>S</math>. По предположению индукции, <math>\Pr[P_i(r_2,\ldots,r_n)=0]\leq\frac{d-i}{|S|}</math>.

Если <math>P_i(r_2,\ldots,r_n)\neq 0</math>, то <math>P(x_1,r_2,\ldots,r_n)</math> имеет степень <math>i</math> (и потому не равен нулю тождественно), поэтому

: <math>\Pr[P(r_1,r_2,\ldots,r_n)=0|P_i(r_2,\ldots,r_n)\neq 0]\leq\frac{i}{|S|}</math>.

Если обозначить событие <math>P(r_1,r_2,\ldots,r_n)=0</math> как <math>A</math>, событие <math>P_i(r_2,\ldots,r_n)=0</math> как <math>B</math> и дополнительное к <math>B</math> событие как <math>B^c</math>, то

: <math>\begin{align}
\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{align}
</math>}}

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

=== Сравнение двух многочленов ===
''Даны два многочлена <math>p_1(x)</math> и <math>p_2(x)</math>, верно ли, что''
    
::: <math>p_1(x) \equiv p_2(x)?</math>

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

::: <math>[p_1(x) - p_2(x)] \equiv 0.</math>

Таким образом, если возможно определить, что
   
::: <math>p(x) \equiv 0,</math>
   
где

::: <math>p(x) = p_1(x)\;-\;p_2(x),</math>
   
то также можно определить, равны ли данные два многочлена.

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

=== Проверка простоты ===
''Дано число <math>n \in \mathbb{Z^+}</math>, является ли <math>n</math> [[Простое число|простым числом]]?''

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

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

::: <math>(1+z)^n = 1+z^n (\mbox{mod}\;n).</math>

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

Пусть

::: <math>\mathcal{P}_n(z) = (1+z)^n - 1 -z^n.</math>

Тогда <math>\mathcal{P}_n(z) = 0\;(\mbox{mod}\;n)</math> ''[[Необходимое и достаточное условия|если и только если]]'' <math>n</math> ''является простым числом''<ref>{{harv|Agrawal|2003}}</ref>. Однако так как <math>n</math> может как быть, так и не быть простым числом, метод Шварца — Зиппеля здесь работать не будет. Аграваль и Бисвас используют более сложную технику, которая включает в себя деление <math>\mathcal{P}_n</math> на случайный [[приведённый многочлен]] небольшой степени.

=== Совершенное паросочетание ===
''Дан [[Граф (математика)|граф]] <math>G = (V, E)</math> на'' <math>n</math> ''вершинах, где <math>n</math> — чётное число. Содержит ли <math>G</math> [[совершенное паросочетание]]?''

{{теорема|''Определитель [[матрица Татта|матрицы Татта]] не является тождественно нулевым многочленом [[если и только если]] в графе есть совершенное паросочетание.''|{{harv|Tutte|1947}}}}

Подмножество <math>D</math> множества рёбер <math>E</math> называется паросочетанием если каждая вершина из <math>V</math> [[Инцидентность|инцидентна]] не более, чем одному ребру из <math>D</math>. Паросочетание называется совершенным если каждая вершина из <math>V</math> инцидентна ровно одному ребру из <math>D</math>. Матрица Татта <math>A</math> это матрица:

::: <math>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}</math>

где

:::<math>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}</math>

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

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

В особом случае сбалансированного [[Двудольный граф|двудольного графа]] на <math> n =m + m </math> вершинах матрица Татта принимает вид [[Блочная матрица|блочной матрицы]]

::: <math>A = \begin{pmatrix} 0 & X \\ -X^t & 0 \end{pmatrix}</math>

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

== Примечания ==
{{примечания|colwidth=25em}}

== Литература ==
{{refbegin|colwidth=25em}}
* {{статья |ссылка=http://ieeexplore.ieee.org/iel5/6604/17631/00814592.pdf |заглавие=Primality and Identity Testing via Chinese Remaindering |accessdate=2008-06-15 |издание=[[Journal of the ACM]] |том=50 |номер=4 |ref=Agrawal |страницы=429—443 |doi=10.1145/792538.792540 |язык=en |тип=journal |автор=Agrawal, Manindra; Biswas, Somenath |год=2003}}
* {{статья |ссылка=http://www.egr.unlv.edu/~larmore/Research/pattern.ps.gz |заглавие=On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts |accessdate=2008-06-15 |издание={{Нп3|Journal of Computer and System Sciences}} |том=65 |номер=2 |страницы=332—350 |doi=10.1006/jcss.2002.1852 |ref=Berman |язык=en |тип=journal |автор=Berman, Piotr; {{Нп3|Karpinski, Marek|Karpinski, Marek||Marek Karpinski}}; Larmore, Lawrence L.; Plandowski, Wojciech; {{Нп3|Rytter, Wojciech|Rytter, Wojciech||Wojciech Rytter}} |год=2002}}
* {{книга |заглавие=The matching problem for bipartite graphs with polynomially bounded permanents is in NC |journal=Proceedings of the Annual Symposium on Foundations of Computer Science |год=1987 |страницы=166—172 |doi=10.1109/SFCS.1987.56 |ref=Grigoriev |isbn=978-0-8186-0807-0 |язык=en |автор=Grigoriev, Dima; Karpinski, Marek}}
* [[Dana Moshkovitz|Moshkovitz, Dana]] (2010). An Alternative Proof of The Schwartz-Zippel Lemma.
* {{статья |заглавие=A probabilistic remark on algebraic program testing |издание={{Нп3|Information Processing Letters}} |том=7 |страницы=193—195 |doi=10.1016/0020-0190(78)90067-4 |ref=DeMillo & Lipton|язык=en |тип=journal |автор={{Нп3|DeMillo, Richard A.|DeMillo, Richard A.||Richard DeMillo}}; {{Нп3|Lipton, Richard J.|Lipton, Richard J.||Richard Lipton}} |год=1978}}
* {{книга |заглавие=Computational Complexity Theory |серия=IAS/Park City Mathematics Series |том=10 |isbn=978-0-8218-2872-4 |ref=Rudich |год=2004 |язык=und |автор=Rudich, Steven |ответственный=AMS}}
* {{статья |ссылка=http://delivery.acm.org/10.1145/330000/322225/p701-schwartz.pdf |заглавие=Fast probabilistic algorithms for verification of polynomial identities |accessdate=2008-06-15 |издание=[[Journal of the ACM]] |страницы=701—717 |ref=Schwartz |doi=10.1145/322217.322225 |том=27 |номер=4 |citeseerx=10.1.1.391.1254 |язык=en |тип=journal |автор={{Нп3|Schwartz, Jack|Schwartz, Jack||Jack Schwartz}} |месяц=10 |год=1980}}
* {{статья |ссылка=http://jlms.oxfordjournals.org/cgi/reprint/s1-22/2/107.pdf |заглавие=The factorization of linear graphs |accessdate=2008-06-15 |том=22 |номер=2 |издание=J. London Math. Soc. |ref=Tutte |страницы=107—111 |doi=10.1112/jlms/s1-22.2.107 |язык=und |автор={{Нп3|Tutte, W.T.|Tutte, W.T.||W. T. Tutte}} |месяц=4 |год=1947}}
* {{книга |заглавие=Probabilistic algorithms for sparse polynomials |год=1979 |ref=Zippel |doi=10.1007/3-540-09519-5_73 |journal=Lecture Notes in Computer Science |том=72 |страницы=216—226 |isbn=978-3-540-09519-4 |язык=en |автор=Zippel, Richard}}
* {{cite web|url=http://historical.ncstrl.org/tr/ps/cornellcs/TR89-965.ps|title=An Explicit Separation of Relativised Random Polynomial Time and Relativised Deterministic Polynomial Time|first=Richard|last=Zippel|date=1989-02|format=ps|accessdate=2008-06-15}}
* {{книга |заглавие=Effective Polynomial Computation |ссылка=https://www.springer.com/computer/mathematics/book/978-0-7923-9375-7 |серия=The Springer International Series in Engineering and Computer Science |том=241 |ref=Zippel |isbn=978-0-7923-9375-7 |год=1993 |язык=und |автор=Zippel, Richard |ответственный={{Нп3|Springer Publishing|Springer|en|Springer Publishing}}}}

{{refend}}

== Ссылки ==

* [http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma The Curious History of the Schwartz-Zippel Lemma], by [[Richard J. Lipton]]

[[Категория:Многочлены]]
[[Категория:Вычислительная алгебра]]
[[Категория:Леммы]]