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 </tex>. Тогда <tex> p(q(r_1, ..., r_n) = 0) \le \frac{d}{|S|} </tex>.
== Доказательство ==
Проведем доказательство теоремы индукцией по <tex> n </tex>.
=== База индукции ===
В случае, когда <tex> n = 1 </tex>, утвержение следует из того, что произвольный полином степени <tex> d </tex> над полем имеет не более чем <tex> d </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 \not\equiv 0 </tex>, хотя бы один <tex> q_i \not\equiv 0 </tex>. Пусть <tex> j = max \{ i | q_i \not\equiv 0\} </tex>
