Лемма Шварца-Зиппеля

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

Пусть задан полином [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]