45
правок
Изменения
Нет описания правки
== Формулировка ==
Пусть задан полином <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 S </tex>. Тогда <tex> p(q(r_1, ..., r_n) = 0) \le \frac{d}{|S|} </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> 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> 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> \{x_1, ..., x_{n-1}\} </tex>, для которого <tex> q_j(x_1, ..., x_{n-1}) \ne 0 </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>.
