Лемма Шварца-Зиппеля — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Индукционный переход: исправил бред в индукционном предположении)
(не показано 5 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
== Формулировка ==
 
== Формулировка ==
Пусть задан полином <tex> q(x_1, ..., x_n) \not\equiv 0 </tex> степени <tex> d </tex> над полем <tex> F </tex>, а также произвольное множество <tex> S \subset F: |S| < \infty </tex>. Пусть также <tex> \{r_i\}_{i=1}^n </tex> — набор независимых случайных величин, равномерно распределенных в <tex> S </tex>. Тогда <tex> p(q(r_1, ..., r_n) = 0) \le \frac{d}{|S|} </tex>.
+
Пусть задан полином <tex> q(x_1, ..., x_n) \not\equiv 0 </tex> степени <tex> d </tex> над полем <tex> F </tex>, а также произвольное множество <tex> S \subset F: |S| < \infty </tex>. Пусть также <tex> \{r_i\}_{i=1}^n </tex> — набор независимых случайных величин, равномерно распределенных в <tex> S </tex>. Тогда <tex> P(q(r_1, ..., r_n) = 0) \leqslant \frac{d}{|S|} </tex>.
  
 
== Доказательство ==
 
== Доказательство ==
Строка 9: Строка 9:
  
 
=== Индукционный переход ===
 
=== Индукционный переход ===
Пусть утверждение верно для всех полиномов степени <tex> n - 1 </tex> (и для всех меньших). Разложим <tex> q </tex> по степеням <tex> x_n </tex>:
+
Пусть утверждение верно для всех полиномов от не более чем <tex> n - 1 </tex> переменных. Разложим <tex> q </tex> по степеням <tex> x_n </tex>:
  
 
<tex> q(x_1, ..., x_n) = \sum_{i=0}^d q_i(x_1, ..., x_{n-1}) x_n^i </tex>
 
<tex> q(x_1, ..., x_n) = \sum_{i=0}^d q_i(x_1, ..., x_{n-1}) x_n^i </tex>
  
Так как <tex> q \not\equiv 0 </tex>, хотя бы один <tex> q_i \not\equiv 0 </tex>. Пусть <tex> j = \max \{ i | q_i \not\equiv 0\} </tex>.
+
Так как <tex> q \not\equiv 0 </tex>, хотя бы один полином <tex> q_i \not\equiv 0 </tex>. Пусть <tex> j = \max \{ i \mid q_i \not\equiv 0\} </tex>.
 
По формуле полной вероятности имеем:
 
По формуле полной вероятности имеем:
<tex> p(q = 0) = p(q = 0 | q_j = 0) p(q_j = 0) + p(q = 0 | q_j \ne 0) p(q_j \ne 0) </tex>.
+
<tex> P(q = 0) = P(q = 0 \mid q_j = 0) P(q_j = 0) + P(q = 0 \mid q_j \ne 0) P(q_j \ne 0) </tex>.
  
Заметим, что <tex> q_j </tex> полином от <tex> n - 1 </tex> переменных, а потому к нему применимо предположение индукции. Кроме того, <tex> \mathrm{deg} q_j \le d - j </tex>. Таким образом, <tex> p(q = 0 | q_j = 0) p(q_j = 0) \le 1 * \frac{d - j}{|S|} </tex>.
+
Заметим, что <tex> q_j </tex> полином от <tex> n - 1 </tex> переменных, а потому к нему применимо предположение индукции. Кроме того, <tex> \mathrm{deg} \, q_j \le d - j </tex>. Таким образом, <tex> P(q = 0 \mid q_j = 0) P(q_j = 0) \leqslant 1 \cdot \frac{d - j}{|S|} </tex>.
  
 
Для получения оценки второго слагаемого зафиксируем некоторый набор <tex> \{x_1, ..., x_{n-1}\} </tex>, для которого <tex> q_j(x_1, ..., x_{n-1}) \ne 0 </tex>.
 
Для получения оценки второго слагаемого зафиксируем некоторый набор <tex> \{x_1, ..., x_{n-1}\} </tex>, для которого <tex> q_j(x_1, ..., x_{n-1}) \ne 0 </tex>.
Тогда для <tex> q(x_1, ... x_n) </tex> как для полинома 1 переменной степени <tex> j </tex> будет выполнено:
+
Тогда для <tex> q(x_1, ..., x_n) </tex> как для полинома одной переменной степени <tex> j </tex> будет выполнено:
<tex> p(q = 0 | q_j \ne 0) p(q_j \ne 0) \le \frac{j}{|S|} * 1 </tex>.
+
<tex> P(q = 0 \mid q_j \ne 0) P(q_j \ne 0) \leqslant \frac{j}{|S|} \cdot 1 </tex>.
  
<tex> p(q = 0) \le \frac{d-j}{|S|} + \frac{j}{|S|} = \frac{d}{|S|} </tex>, что и требовалось доказать.
+
<tex> P(q = 0) \leqslant \frac{d-j}{|S|} + \frac{j}{|S|} = \frac{d}{|S|} </tex>, что и требовалось доказать.
  
 
== Применение ==
 
== Применение ==
С помощью этой леммы можно, например, показать принадлежность задачи проверки эквивалентности двух полиномов классу [[Классы RP и coRP|coRP]]
+
С помощью этой леммы можно, например, показать принадлежность задачи проверки эквивалентности двух полиномов классу [[Сложностные классы RP и coRP|coRP]].
 
=== Формулировка задачи ===
 
=== Формулировка задачи ===
Пусть даны два полинома — <tex> p(x_1, ..., x_n) </tex> и <tex> q(x_1, ..., x_n) </tex>. Нужно проверить, верно ли, что <tex> p \equiv q </tex>.
+
Пусть даны два полинома — <tex> p(x_1, ..., x_n) </tex> и <tex> q(x_1, ..., x_n) </tex>. Необходимо проверить, верно ли, что <tex> p \equiv q </tex>.
  
 
=== Утверждение ===
 
=== Утверждение ===
Сформулированная выше задача принадлежит классу <tex> coRP </tex>.
+
Сформулированная выше задача принадлежит классу <tex> \mathrm{coRP} </tex>.
  
 
=== Доказательство ===
 
=== Доказательство ===
 
Для доказательства построим такой алгоритм m, что:
 
Для доказательства построим такой алгоритм m, что:
* <tex> p(m(\langle p, q \rangle) = 1 | p \equiv q) = 1 </tex>
+
* <tex> P(m(\langle p, q \rangle) = 1 \mid p \equiv q) = 1 </tex>
* <tex> p(m(\langle p, q \rangle) = 0 | p \not\equiv q) \ge \frac{1}{2} </tex>
+
* <tex> P(m(\langle p, q \rangle) = 0 \mid p \not\equiv q) \geqslant \frac{1}{2} </tex>
  
 
Для этого рассмотрим полином <tex> h = p - q </tex>. Очевидно, что <tex> h \equiv 0 \Leftrightarrow p \equiv q </tex>. Рассмотрим <tex> h </tex> над некоторым полем <tex> F </tex>. Очевидно, что если <tex> h \equiv 0 </tex>, то это будет выполнено и в <tex> F </tex> (обратное, вообще говоря, неверно). Возьмем случайный набор <tex> \{x_1, ..., x_n\} </tex>. По
 
Для этого рассмотрим полином <tex> h = p - q </tex>. Очевидно, что <tex> h \equiv 0 \Leftrightarrow p \equiv q </tex>. Рассмотрим <tex> h </tex> над некоторым полем <tex> F </tex>. Очевидно, что если <tex> h \equiv 0 </tex>, то это будет выполнено и в <tex> F </tex> (обратное, вообще говоря, неверно). Возьмем случайный набор <tex> \{x_1, ..., x_n\} </tex>. По
доказанной выше лемме <tex> p(h(x_1, ..., x_n) = 0) \le \frac {\mathrm{deg} h}{|F|} </tex>. Тогда алгоритм, выдающий по данным <tex> p </tex> и <tex> q </tex> <tex> [h(x_1, ..., x_n) = 0] </tex>, удовлетворяет поставленным условиям, лишь только <tex> |F| \ge 2 deg  h </tex>, что тем более верно, если <tex> |F| \ge 2 \max(\mathrm{deg} p, \mathrm{deg} q) </tex>.
+
доказанной выше лемме <tex> p(h(x_1, ..., x_n) = 0) \leqslant \frac {\mathrm{deg} \, h}{|F|} </tex>. Тогда алгоритм, по данным <tex> p </tex> и <tex> q </tex> выдающий <tex> [h(x_1, ..., x_n) = 0] </tex>, удовлетворяет поставленным условиям, лишь только <tex> |F| \geqslant 2 \mathrm{deg} \, h </tex>, что тем более верно, если <tex> |F| \geqslant 2 \max(\mathrm{deg} \, p, \mathrm{deg} \, q) </tex>.

Версия 12:07, 1 июня 2021

Формулировка

Пусть задан полином [math] q(x_1, ..., x_n) \not\equiv 0 [/math] степени [math] d [/math] над полем [math] F [/math], а также произвольное множество [math] S \subset F: |S| \lt \infty [/math]. Пусть также [math] \{r_i\}_{i=1}^n [/math] — набор независимых случайных величин, равномерно распределенных в [math] S [/math]. Тогда [math] P(q(r_1, ..., r_n) = 0) \leqslant \frac{d}{|S|} [/math].

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

Проведем доказательство леммы индукцией по [math] n [/math].

База индукции

В случае, когда [math] n = 1 [/math], утвержение следует из того, что произвольный полином степени [math] d [/math] над полем имеет не более чем [math] d [/math] корней.

Индукционный переход

Пусть утверждение верно для всех полиномов от не более чем [math] n - 1 [/math] переменных. Разложим [math] q [/math] по степеням [math] x_n [/math]:

[math] q(x_1, ..., x_n) = \sum_{i=0}^d q_i(x_1, ..., x_{n-1}) x_n^i [/math]

Так как [math] q \not\equiv 0 [/math], хотя бы один полином [math] q_i \not\equiv 0 [/math]. Пусть [math] j = \max \{ i \mid q_i \not\equiv 0\} [/math]. По формуле полной вероятности имеем: [math] P(q = 0) = P(q = 0 \mid q_j = 0) P(q_j = 0) + P(q = 0 \mid q_j \ne 0) P(q_j \ne 0) [/math].

Заметим, что [math] q_j [/math] — полином от [math] n - 1 [/math] переменных, а потому к нему применимо предположение индукции. Кроме того, [math] \mathrm{deg} \, q_j \le d - j [/math]. Таким образом, [math] P(q = 0 \mid q_j = 0) P(q_j = 0) \leqslant 1 \cdot \frac{d - j}{|S|} [/math].

Для получения оценки второго слагаемого зафиксируем некоторый набор [math] \{x_1, ..., x_{n-1}\} [/math], для которого [math] q_j(x_1, ..., x_{n-1}) \ne 0 [/math]. Тогда для [math] q(x_1, ..., x_n) [/math] как для полинома одной переменной степени [math] j [/math] будет выполнено: [math] P(q = 0 \mid q_j \ne 0) P(q_j \ne 0) \leqslant \frac{j}{|S|} \cdot 1 [/math].

[math] P(q = 0) \leqslant \frac{d-j}{|S|} + \frac{j}{|S|} = \frac{d}{|S|} [/math], что и требовалось доказать.

Применение

С помощью этой леммы можно, например, показать принадлежность задачи проверки эквивалентности двух полиномов классу coRP.

Формулировка задачи

Пусть даны два полинома — [math] p(x_1, ..., x_n) [/math] и [math] q(x_1, ..., x_n) [/math]. Необходимо проверить, верно ли, что [math] p \equiv q [/math].

Утверждение

Сформулированная выше задача принадлежит классу [math] \mathrm{coRP} [/math].

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

Для доказательства построим такой алгоритм m, что:

  • [math] P(m(\langle p, q \rangle) = 1 \mid p \equiv q) = 1 [/math]
  • [math] P(m(\langle p, q \rangle) = 0 \mid p \not\equiv q) \geqslant \frac{1}{2} [/math]

Для этого рассмотрим полином [math] h = p - q [/math]. Очевидно, что [math] h \equiv 0 \Leftrightarrow p \equiv q [/math]. Рассмотрим [math] h [/math] над некоторым полем [math] F [/math]. Очевидно, что если [math] h \equiv 0 [/math], то это будет выполнено и в [math] F [/math] (обратное, вообще говоря, неверно). Возьмем случайный набор [math] \{x_1, ..., x_n\} [/math]. По доказанной выше лемме [math] p(h(x_1, ..., x_n) = 0) \leqslant \frac {\mathrm{deg} \, h}{|F|} [/math]. Тогда алгоритм, по данным [math] p [/math] и [math] q [/math] выдающий [math] [h(x_1, ..., x_n) = 0] [/math], удовлетворяет поставленным условиям, лишь только [math] |F| \geqslant 2 \mathrm{deg} \, h [/math], что тем более верно, если [math] |F| \geqslant 2 \max(\mathrm{deg} \, p, \mathrm{deg} \, q) [/math].