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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
 
<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 | 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> deg \enskip 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> q(x_1, ... x_n) </tex> как для полинома 1 переменной степени <tex> j </tex> будет выполнено:
 +
<tex> p(q = 0 | q_j \ne 0) p(q_j \ne 0) \le \frac{i}{|S|} * 1 </tex>.
 +
 
 +
<tex> p(q = 0) \le \frac{d-j}{|S|} + \frac{j}{|S|} = \frac{d}{|S|} </tex>, что и требовалось доказать.

Версия 20:48, 13 апреля 2010

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

Пусть задан полином [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] F [/math]. Тогда [math] p(q(r_1, ..., r_n) = 0) \le \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 | q_i \not\equiv 0\} [/math]. По формуле полной вероятности имеем: [math] 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) [/math].

Заметим, что [math] q_j - [/math] полином от [math] n - 1 [/math] переменных, а потому к нему применимо предположение индукции. Кроме того, [math] deg \enskip q_j \le d - j [/math]. Таким образом, [math] p(q = 0 | q_j = 0) p(q_j = 0) \le 1 * \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] как для полинома 1 переменной степени [math] j [/math] будет выполнено: [math] p(q = 0 | q_j \ne 0) p(q_j \ne 0) \le \frac{i}{|S|} * 1 [/math].

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