Меню Главная Случайная статья Настройки Лемма Шварца — Зиппеля Материал из https://ru.wikipedia.org Лемма Шварца — Зиппеля (также лемма Де Милло — Липтона — Шварца — Зиппеля) — результат, широко используемый в проверке равенства многочленов, то есть, в задаче проверки некоторого многочлена многих переменных на тождественное равенство нулю. Лемма была независимо открыта Джеком Шварцем[1], Ричардом Зиппелем[2], а также Ричардом Де Милло и Ричардом Липтоном, хотя версия Де Милло и Липтона появилась на год раньше результата Шварца и Зиппеля[3]. Версия леммы для конечных полей было доказана Ойстином Оре в 1922 году[4]. Содержание 1 Лемма 2 Применения 2.1 Сравнение двух многочленов 2.2 Проверка простоты 2.3 Совершенное паросочетание 3 Примечания 4 Литература 5 Ссылки Лемма Входом задачи является многочлен от ${\displaystyle n}$ переменных над полем ${\displaystyle \mathbb {F} }$. Он может быть в задан в виде арифметической схемы или как определитель некоторой матрицы многочленов. На текущий момент нет известных детерминированных субэкспоненциальных алгоритмов, позволяющих проверить, что этот многочлен ненулевой. Однако, есть известные рандомизированные алгоритмы, решающие данную задачу за полиномиальное время. При их анализе обычно требуется оценить вероятность того, что ненулевой многочлен будет равен нулю в некоторой случайным образом выбранной точке. Лемма Шварца — Зиппеля формулируется так: Пусть ${\displaystyle P\in F[x_{1},x_{2},\dots ,x_{n}]}$ — ненулевой многочлен степени ${\displaystyle d\geq 0}$ над полем ${\displaystyle \mathbb {F} }$. Пусть ${\displaystyle S}$ — конечное подмножество ${\displaystyle \mathbb {F} }$ и пусть элементы ${\displaystyle r_{1},r_{2},\dots ,r_{n}}$ были выбраны из ${\displaystyle S}$ равномерно и независимо друг от друга. Тогда ${\displaystyle \Pr[P(r_{1},r_{2},\dots ,r_{n})=0]\leq {\frac {d}{\vert S\vert }}}$. В случае одной переменной лемма следует напрямую из того, что у многочлена степени ${\displaystyle d}$ может быть не больше ${\displaystyle d}$ различных корней над полем ${\displaystyle \mathbb {F} }$. Доказать лемму в общем виде можно математической индукцией по количеству переменных ${\displaystyle n}$. Базовый случай ${\displaystyle n=1}$ был доказан выше. Пусть теперь теорема верна для всех многочленов на ${\displaystyle n-1}$ переменных. Можно рассматривать ${\displaystyle P}$ как многочлен от ${\displaystyle x_{1}}$, записав его в виде ${\displaystyle P(x_{1},\dots ,x_{n})=\sum _{i=0}^{d}x_{1}^{i}P_{i}(x_{2},\dots ,x_{n})}$. Так как ${\displaystyle P}$ не равен нулю тождественно, существует некоторый номер ${\displaystyle i}$ такой что ${\displaystyle P_{i}}$ также не равен нулю. Пусть ${\displaystyle i}$ — наибольший из таких номеров. Тогда ${\displaystyle \deg P_{i}\leq d-i}$, так как степень ${\displaystyle x_{1}^{i}P_{i}}$ не превосходит ${\displaystyle d}$. Пусть теперь ${\displaystyle r_{2},\dots ,r_{n}}$ выбраны случайно из ${\displaystyle S}$. По предположению индукции, ${\displaystyle \Pr[P_{i}(r_{2},\ldots ,r_{n})=0]\leq {\frac {d-i}{|S|}}}$. Если ${\displaystyle P_{i}(r_{2},\ldots ,r_{n})\neq 0}$, то ${\displaystyle P(x_{1},r_{2},\ldots ,r_{n})}$ имеет степень ${\displaystyle i}$ (и потому не равен нулю тождественно), поэтому ${\displaystyle \Pr[P(r_{1},r_{2},\ldots ,r_{n})=0|P_{i}(r_{2},\ldots ,r_{n})\neq 0]\leq {\frac {i}{|S|}}}$. Если обозначить событие ${\displaystyle P(r_{1},r_{2},\ldots ,r_{n})=0}$ как ${\displaystyle A}$, событие ${\displaystyle P_{i}(r_{2},\ldots ,r_{n})=0}$ как ${\displaystyle B}$ и дополнительное к ${\displaystyle B}$ событие как ${\displaystyle B^{c}}$, то ${\displaystyle {\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}}}$ Применения Значимость леммы Шварца — Зиппеля и проверки равенства многочленов следует из алгоритмов, которые могут быть сведены к этой задаче. Сравнение двух многочленов Даны два многочлена ${\displaystyle p_{1}(x)}$ и ${\displaystyle p_{2}(x)}$, верно ли, что ${\displaystyle p_{1}(x)\equiv p_{2}(x)?}$ Данную задачу можно свести к проверке равенства многочленов, так как достаточно проверить, что ${\displaystyle [p_{1}(x)-p_{2}(x)]\equiv 0.}$ Таким образом, если возможно определить, что ${\displaystyle p(x)\equiv 0,}$ где ${\displaystyle p(x)=p_{1}(x)\;-\;p_{2}(x),}$ то также можно определить, равны ли данные два многочлена. Сравнение двух многочленов может быть использовано в анализе программ с ветвлением. Read-once программа с ветвлением может быть представлена в виде мультилинейного многочлена, который вычисляет (над некоторым полем) на входе из нулей и единиц ту же булеву функцию, что и программа с ветвлением. Таким образом, две программы с ветвлением вычисляют одну и ту же булеву функцию если и только если соответствующие многочлены равны. Значит, проверка равенства булевых функций, которые вычисляются read-once программами с ветвлением может быть сведена к проверке равенства многочленов. Проверка простоты Дано число ${\displaystyle n\in \mathbb {Z^{+}} }$, является ли ${\displaystyle n}$ простым числом? Маниндра Аграваль и Соменат Бисвас разработали простой рандомизированный алгоритм, использующий проверки равенства многочленов для определения простоты числа ${\displaystyle n}$. Они показали, что все простые числа ${\displaystyle n}$ (и только простые числа) удовлетворяют следующему сравнению: ${\displaystyle (1+z)^{n}=1+z^{n}({\mbox{mod}}\;n).}$ Указанный результат следует из эндоморфизма Фробениуса. Пусть ${\displaystyle {\mathcal {P}}_{n}(z)=(1+z)^{n}-1-z^{n}.}$ Тогда ${\displaystyle {\mathcal {P}}_{n}(z)=0\;({\mbox{mod}}\;n)}$ если и только если ${\displaystyle n}$ является простым числом[5]. Однако так как ${\displaystyle n}$ может как быть, так и не быть простым числом, метод Шварца — Зиппеля здесь работать не будет. Аграваль и Бисвас используют более сложную технику, которая включает в себя деление ${\displaystyle {\mathcal {P}}_{n}}$ на случайный приведённый многочлен небольшой степени. Совершенное паросочетание Дан граф ${\displaystyle G=(V,E)}$ на ${\displaystyle n}$ вершинах, где ${\displaystyle n}$ — чётное число. Содержит ли ${\displaystyle G}$ совершенное паросочетание? Определитель матрицы Татта не является тождественно нулевым многочленом если и только если в графе есть совершенное паросочетание. Подмножество ${\displaystyle D}$ множества рёбер ${\displaystyle E}$ называется паросочетанием если каждая вершина из ${\displaystyle V}$ инцидентна не более, чем одному ребру из ${\displaystyle D}$. Паросочетание называется совершенным если каждая вершина из ${\displaystyle V}$ инцидентна ровно одному ребру из ${\displaystyle D}$. Матрица Татта ${\displaystyle A}$ это матрица: ${\displaystyle 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}}}$ где ${\displaystyle 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}}}$ Определитель матрицы Татта (как многочлен от ${\displaystyle x_{ij},i<j}$) задаётся как определитель этой кососимметричной матрицы, который равен квадрату пфаффиана матрицы ${\displaystyle A}$ и не равен нулю тождественно если и только если в графе есть совершенное паросочетание. Таким образом, используя проверку равенства многочленов, можно проверить, содержит ли произвольный граф ${\displaystyle G}$ совершенное паросочетание. В особом случае сбалансированного двудольного графа на ${\displaystyle n=m+m}$ вершинах матрица Татта принимает вид блочной матрицы ${\displaystyle A={\begin{pmatrix}0&X\\-X^{t}&0\end{pmatrix}}}$ Первые ${\displaystyle m}$ строк (и, соответственно, столбцов) индексированы первой долей двудольного графа, а последние ${\displaystyle m}$ строк — второй долей. В данном случае пфаффиан (с точностью до знака) совпадает с обычным определителем матрицы ${\displaystyle X}$ размера ${\displaystyle m\times m}$. Матрица ${\displaystyle X}$ при этом является матрицей Эдмондса данного двудольного графа. Примечания (Schwartz 1980) (Zippel 1979) (DeMillo & Lipton 1978) . Ore, ber hhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I (1922), no. 7, 15 pages. (Agrawal 2003) Литература Agrawal, Manindra; Biswas, Somenath. Primality and Identity Testing via Chinese Remaindering (англ.) // Journal of the ACM : journal. — 2003. — Vol. 50, no. 4. — P. 429—443. — doi:10.1145/792538.792540. Berman, Piotr; Karpinski, Marek[англ.]; Larmore, Lawrence L.; Plandowski, Wojciech; Rytter, Wojciech[англ.]. On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts (англ.) // Journal of Computer and System Sciences[англ.] : journal. — 2002. — Vol. 65, no. 2. — P. 332—350. — doi:10.1006/jcss.2002.1852. 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:10.1109/SFCS.1987.56. Moshkovitz, Dana (2010). An Alternative Proof of The Schwartz-Zippel Lemma. DeMillo, Richard A.[англ.]; Lipton, Richard J.[англ.]. A probabilistic remark on algebraic program testing (англ.) // Information Processing Letters[англ.] : journal. — 1978. — Vol. 7. — P. 193—195. — doi:10.1016/0020-0190(78)90067-4. Schwartz, Jack[англ.]. Fast probabilistic algorithms for verification of polynomial identities (англ.) // Journal of the ACM : journal. — 1980. — October (vol. 27, no. 4). — P. 701—717. — doi:10.1145/322217.322225. Tutte, W.T.[англ.]. The factorization of linear graphs (неопр.) // J. London Math. Soc.. — 1947. — April (т. 22, № 2). — С. 107—111. — doi:10.1112/jlms/s1-22.2.107. Zippel, Richard. An Explicit Separation of Relativised Random Polynomial Time and Relativised Deterministic Polynomial Time  (ps) (февраль 1989). Дата обращения: 15 июня 2008. Ссылки The Curious History of the Schwartz-Zippel Lemma, by Richard J. Lipton