Редактирование: Лемма Шварца-Зиппеля
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
== Формулировка == | == Формулировка == | ||
| − | Пусть задан полином <tex> q(x_1, ..., x_n) \not\equiv 0 </tex> степени <tex> d </tex> над полем <tex> F </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> F </tex>. Тогда <tex> p(q(r_1, ..., r_n) = 0) \le \frac{d}{|S|} </tex>. |
== Доказательство == | == Доказательство == | ||
| − | Проведем доказательство | + | Проведем доказательство теоремы индукцией по <tex> n </tex>. |
=== База индукции === | === База индукции === | ||
| Строка 9: | Строка 9: | ||
=== Индукционный переход === | === Индукционный переход === | ||
| − | Пусть утверждение верно для всех полиномов | + | Пусть утверждение верно для всех полиномов степени <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 \not\equiv 0 </tex>, хотя бы один <tex> q_i \not\equiv 0 </tex>. Пусть <tex> j = max \{ i | q_i \not\equiv 0\} </tex>. |
По формуле полной вероятности имеем: | По формуле полной вероятности имеем: | ||
| − | <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> q_j </tex> | + | Заметим, что <tex> q_j — </tex> полином от <tex> n - 1 </tex> переменных, а потому к нему применимо предположение индукции. Кроме того, <tex> 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> \{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, ... | + | Тогда для <tex> q(x_1, ... x_n) </tex> как для полинома 1 переменной степени <tex> j </tex> будет выполнено: |
| − | <tex> | + | <tex> p(q = 0 | q_j \ne 0) p(q_j \ne 0) \le \frac{j}{|S|} * 1 </tex>. |
| − | <tex> | + | <tex> p(q = 0) \le \frac{d-j}{|S|} + \frac{j}{|S|} = \frac{d}{|S|} </tex>, что и требовалось доказать. |
== Применение == | == Применение == | ||
| − | С помощью этой леммы можно, например, показать принадлежность задачи проверки эквивалентности двух полиномов классу | + | С помощью этой леммы можно, например, показать принадлежность задачи проверки эквивалентности двух полиномов классу <tex> coRP </tex>. |
| + | |||
=== Формулировка задачи === | === Формулировка задачи === | ||
| − | Пусть даны два полинома — <tex> p(x_1, ..., x_n) </tex> и <tex> q(x_1, ..., x_n) </tex> | + | Пусть даны два полинома — <tex> p(x_1, ..., x_n) </tex> и <tex> q(x_1, ..., x_n) </tex>, Нужно проверить, верно ли, что <tex> p \equiv q </tex>. |
=== Утверждение === | === Утверждение === | ||
| − | Сформулированная выше задача принадлежит классу <tex> | + | Сформулированная выше задача принадлежит классу <tex> coRP </tex>. |
=== Доказательство === | === Доказательство === | ||
Для доказательства построим такой алгоритм m, что: | Для доказательства построим такой алгоритм m, что: | ||
| − | * <tex> | + | * <tex> p(m(\langle p, q \rangle) = 1 | p \equiv q) = 1 </tex> |
| − | * <tex> | + | * <tex> p(m(\langle p, q \rangle) = 0 | p \not\equiv q) \ge \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) \ | + | доказанной выше лемме <tex> p(h(x_1, ..., x_n) = 0) \le \frac {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(deg p, deg q) </tex>. |
