Лемма Шварца–Циппеля

Инструмент, используемый в вероятностной полиномиальной проверке идентичности

В математике лемма Шварца–Циппеля (также называемая леммой Демилло–Липтона–Шварца–Циппеля ) — это инструмент, обычно используемый в вероятностной проверке идентичности полиномов . Проверка идентичности — это проблема определения того, является ли заданный многомерный полином 0-полиномом, полиномом, который игнорирует все свои переменные и всегда возвращает ноль. Лемма утверждает, что оценка ненулевого полинома на входах, выбранных случайным образом из достаточно большого набора, скорее всего, обнаружит вход, который даст ненулевой выход.

она была открыта независимо Джеком Шварцем , ^[1] Ричардом Циппелем, ^[2] и Ричардом Демилло и Ричардом Дж. Липтоном , хотя версия Демилло и Липтона была показана за год до результата Шварца и Циппеля. ^[3] Версия этой границы для конечного поля была доказана Ойстейном Оре в 1922 году. ^[4]

Утверждение и доказательство леммы

Теорема 1 (Шварц, Циппель). Пусть

${\displaystyle P\in R[x_{1},x_{2},\ldots ,x_{n}]}$

— ненулевой многочлен полной степени d  ≥ 0 над областью целостности  R. Пусть S — конечное подмножество R и пусть r ₁ ,  r ₂ , ...,  r _n выбираются случайным образом независимо и равномерно из S. Тогда

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

Эквивалентно, Лемма утверждает, что для любого конечного подмножества S из R, если Z(P) является нулевым множеством P, то

${\displaystyle |Z(P)\cap S^{n}|\leq d\cdot |S|^{n-1}.}$

Доказательство. Доказательство проводится методом математической индукции по n . При n  = 1 P может иметь не более d корней по фундаментальной теореме алгебры . Это дает нам базовый случай. Теперь предположим, что теорема верна для всех многочленов от n  − 1 переменных. Тогда мы можем считать P многочленом от x ₁ , записав его как

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

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

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

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

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

Если мы обозначим событие как A , событие как B , а дополнение к B как , то мы имеем ${\displaystyle P(r_{1},r_{2},\ldots ,r_{n})=0}$ ${\displaystyle P_{i}(r_{2},\ldots ,r_{n})=0}$ ${\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 (x_{1}+3x_{2}-x_{3})(3x_{1}+x_{4}-1)\cdots (x_{7}-x_{2})\equiv 0\ ?}$

Чтобы решить эту задачу, мы можем перемножить ее и проверить, что все коэффициенты равны 0. Однако это занимает экспоненциальное время . В общем случае многочлен можно алгебраически представить с помощью арифметической формулы или схемы .

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

Дана пара многочленов и , есть ${\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),}$

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

Сравнение полиномов имеет приложения для ветвящихся программ (также называемых диаграммами бинарных решений ). Программа ветвления с однократным чтением может быть представлена ​​полилинейным полиномом , который вычисляет (над любым полем) на {0,1}-входах ту же самую булеву функцию , что и программа ветвления, а две программы ветвления вычисляют ту же самую функцию тогда и только тогда, когда соответствующие полиномы равны. Таким образом, тождество булевых функций, вычисляемых программами ветвления с однократным чтением, может быть сведено к проверке тождества полинома.

Сравнение двух многочленов (и, следовательно, проверка тождественности многочленов) также имеет приложения в двумерном сжатии, где задача нахождения равенства двух двумерных текстов A и B сводится к задаче сравнения равенства двух многочленов и . ${\displaystyle p_{A}(x,y)}$ ${\displaystyle p_{B}(x,y)}$

Тестирование простоты

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

Простой рандомизированный алгоритм, разработанный Маниндрой Агравалом и Соменатом Бисвасом, позволяет вероятностно определить, является ли число простым, и использует для этого проверку полиномиальной идентичности. ${\displaystyle n}$

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

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

Это следствие эндоморфизма Фробениуса .

Позволять

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

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

Простые числа используются в ряде приложений, таких как определение размера хэш-таблиц, генераторы псевдослучайных чисел и генерация ключей для криптографии . Поэтому нахождение очень больших простых чисел (порядка (как минимум) ) становится очень важным и требуются эффективные алгоритмы проверки простоты. ${\displaystyle 10^{350}\approx 2^{1024}}$

Идеальное соответствие

Пусть — граф из n вершин, где n четно. Содержит ли G идеальное паросочетание ? ${\displaystyle G=(V,E)}$

Теорема 2 (Тутте, 1947): Определитель матрицы Тутте не является 0 -многочленом тогда и только тогда, когда существует совершенное паросочетание.

Подмножество D множества E называется паросочетанием, если каждая вершина в V инцидентна не более чем одному ребру в D. Паросочетание является совершенным, если каждая вершина в V имеет ровно одно ребро, инцидентное ей в D. Создайте матрицу Тутта 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{if}}\;(i,j)\in E{\mbox{ and }}i<j\\-x_{ji}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i>j\\0\;\;\;\;{\mbox{otherwise}}.\end{cases}}}$

Определитель матрицы Тутта (в переменных x _ij , ⁠ ⁠ ${\displaystyle i<j}$ ) затем определяется как определитель этой кососимметричной матрицы , которая совпадает с квадратом пфаффиана матрицы A и является ненулевым (как полином) тогда и только тогда, когда существует идеальное паросочетание. Затем можно использовать проверку полиномиальной идентичности, чтобы выяснить, содержит ли G идеальное паросочетание. Существует детерминированный алгоритм черного ящика для графов с полиномиально ограниченными перманентами (Григорьев и Карпинский, 1987). ^[5]

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

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

если первые m строк (соотв. столбцов) индексированы первым подмножеством двураздела, а последние m строк — дополнительным подмножеством. В этом случае пфаффиан совпадает с обычным определителем матрицы X размером m × m (с точностью до знака). Здесь X — матрица Эдмондса .

Определитель матрицы с полиномиальными элементами

Позволять

${\displaystyle p(x_{1},x_{2},\ldots ,x_{n})}$

быть определителем полиномиальной матрицы .

В настоящее время не существует известного алгоритма с субэкспоненциальным временем , который может решить эту задачу детерминированно. Однако существуют рандомизированные полиномиальные алгоритмы, анализ которых требует ограничения вероятности того, что ненулевой полином будет иметь корни в случайно выбранных контрольных точках.

Примечания

1. Шварц 1980.
2. Циппель 1979.
3. ДеМилло и Липтон 1978.
4. Ö. Оре, Über höhere Kongruenzen. Норск Мат. Форенингс Скрифтер Сер. Я (1922), нет. 7, 15 страниц.
5. Григорьев и Карпинский 1987.

Ссылки

• Агравал, Маниндра; Бисвас, Соменат (21.02.2003). «Тестирование первичности и идентичности с помощью китайского остаточного кода». Журнал ACM . 50 (4): 429–443. doi :10.1145/792538.792540. S2CID  13145079. Получено 15.06.2008 .
• Берман, Петр; Карпински, Марек ; Лармор, Лоуренс Л.; Пландовски, Войцех; Риттер, Войцех (2002) . «О сложности сопоставления шаблонов для сильно сжатых двумерных текстов» (пс) . Журнал компьютерных и системных наук . 65 (2): 332–350. doi : 10.1006/jcss.2002.1852 . Получено 15 июня 2008 г.
• Григорьев, Дима; Карпинский, Марек (1987). "Проблема сопоставления для двудольных графов с полиномиально ограниченными перманентами находится в NC". Труды 28-го ежегодного симпозиума по основам компьютерной науки (FOCS 1987), Лос-Анджелес, Калифорния, США, 27-29 октября 1987 г. IEEE Computer Society. стр. 166–172. doi :10.1109/SFCS.1987.56. ISBN 978-0-8186-0807-0. S2CID  14476361.
• Мошковиц, Дана (2010). Альтернативное доказательство леммы Шварца-Циппеля. ECCC  TR10-096
• ДеМилло, Ричард А.; Липтон , Ричард Дж. (1978). «Вероятностное замечание об алгебраическом тестировании программ». Information Processing Letters . 7 (4): 193–195. doi :10.1016/0020-0190(78)90067-4.
• Рудич, Стивен (2004). AMS (ред.). Теория сложности вычислений . Серия IAS/Park City Mathematics. Том 10. ISBN 978-0-8218-2872-4.
• Шварц, Якоб Т. (октябрь 1980 г.). "Быстрые вероятностные алгоритмы для проверки полиномиальных тождеств" (PDF) . Журнал ACM . 27 (4): 701–717. CiteSeerX  10.1.1.391.1254 . doi :10.1145/322217.322225. S2CID  8314102 . Получено 15.06.2008 .
• Tutte, WT (апрель 1947 г.). «Факторизация линейных графов». J. London Math. Soc . 22 (2): 107–111. doi :10.1112/jlms/s1-22.2.107. hdl :10338.dmlcz/128215.
• Zippel, Richard (1979). "Вероятностные алгоритмы для разреженных полиномов". В Ng, Edward W. (ред.). Symbolic and Algebraic Computation, EUROSAM '79, Международный симпозиум по символическим и алгебраическим вычислениям, Марсель, Франция, июнь 1979 г., Труды . Lecture Notes in Computer Science. Том 72. Springer. стр. 216–226. doi :10.1007/3-540-09519-5_73. ISBN 978-3-540-09519-4.
• Zippel, Richard (февраль 1989). "Явное разделение релятивизированного случайного полиномиального времени и релятивизированного детерминированного полиномиального времени" (пс) . Получено 2008-06-15 .
• Zippel, Richard (1993). Springer (ред.). Эффективное полиномиальное вычисление. Международная серия Springer по инжинирингу и информатике. Том 241. ISBN 978-0-7923-9375-7.

Внешние ссылки

• Любопытная история леммы Шварца-Циппеля, Ричард Дж. Липтон