Инструменты для доказательства теоремы Роньяи

Пусть $F \in \mathbb {K}[x_1, \ldots , x_ n]$ (многочлен от $n$ переменных с коэффициентами из кольца $\mathbb{K}$), тогда $F(x_1, \ldots , x_ n) = \sum \limits _{\scriptscriptstyle i_1, \ldots , i_ n} a_{i_1, \ldots , i_ n} x_1^{i_1} \cdot \ldots \cdot x_ n^{i_ n}$, $\deg F = \max \{ i_1 + \ldots + i_ n\}$.

Положим $\mathbb {K} = \mathbb {Z}_ p$ и
рассмотрим все возможные наборы $(x_1, \ldots , x_ n) \in \mathbb {Z}_ p^ n$, удовлетворяющие сравнению
$F(x_1, \ldots , x_ n) \equiv 0\pmod p$. Всего таких наборов не больше, чем $p^ n$.

Теорема (Шевалле). Пусть $F \in \mathbb {Z}_ p[x_1, \ldots , x_ n]$ и $\deg F < n$. Тогда число решений в $\mathbb {Z}_ p^ n$ сравнения $F(x_1,\ldots ,x_ n)\equiv 0\ (p)$ делится на $p$.

$\blacktriangle$  Пусть $N_ p$ — количество решений.
$$N_ p \equiv \sum \limits _{x_1=1}^ p\ldots \sum \limits _{x_ n=1}^ p (1 - F^{p-1}(x_1, \ldots , x_ n))\pmod p.$$

Если $(x_1, \ldots , x_ n)$ — решение сравнения, то $F(x_1, \ldots , x_ n)\equiv 0$.

Иначе $F(x_1, \ldots , x_ n) \not\equiv 0 \Rightarrow F^{p-1}(x_1, \ldots , x_ n) \equiv 1$.

Для доказательства того, что $N_ p \equiv 0$, достаточно проверить, что
$\sum \limits _{x_1=1}^ p\ldots \sum \limits _{x_ n=1}^ p F^{p-1}(x_1, \ldots , x_ n) \equiv 0$.

$\deg F^{p-1} \leqslant (n-1)(p-1)$.

$F^{p-1}(x_1, \ldots , x_ n) = \left(\sum a_{1,\ldots ,n}x_1^{\alpha _1}\cdot \ldots \cdot x_ n^{\alpha ^ n}\right)^{p-1} =$ $\sum b_{1,\ldots ,n}x_1^{\beta _1}\cdot \ldots \cdot x_ n^{\beta ^ n}$, $\beta _1+\ldots +\beta _ n \leqslant (p-1)(n-1)$.

Итак, нас интересует $\sum \limits _{x_1=1}^ p\ldots \sum \limits _{x_ n=1}^ p (\sum b_{1,\ldots ,n}x_1^{\beta _1}\cdot \ldots \cdot x_ n^{\beta ^ n})$.

Достаточно доказать, что $\forall \beta _1, \ldots , \beta _ n, \beta _1+\ldots +\beta _ n \leqslant (p-1)(n-1)\colon$
$\sum \limits _{x_1=1}^ p\ldots \sum \limits _{x_ n=1}^ p x_1^{\beta _1}\cdot \ldots \cdot x_ n^{\beta ^ n} \equiv 0 \pmod p$.

Сумму можно перезаписать как $\left(\sum \limits _{x_1=1}^ p x_1^{\beta _1}\right)\cdot \ldots \cdot \left(\sum \limits _{x_ n=1}^ p x_ n^{\beta _ n}\right)$.

Докажем, что хотя бы один сомножитель, делится на $p$.

Рассмотрим несколько случаев.

Случай 1. $p = 2$. $\beta_1 + \ldots + \beta_ n \leqslant (n-1) \Rightarrow \exists i\colon \beta _ i=0 \Rightarrow$ $\sum \limits _{x_ i=1}^ p x^{\beta _ i} = \sum \limits _{x_ i=1}^ p 1 = p \equiv 0 \pmod p$.

Случай 2. $p \geqslant 3, \beta _ i \geqslant 1$. $\exists i\colon 1 \leqslant \beta_ i \leqslant p-2$. Рассмотрим $S := \sum \limits _{x_ i=1}^ p x_ i^{\beta _ i}$

Задача. Если $a\colon 1 \leqslant a \leqslant p-2$, то $\exists b \not\in \{ 0, 1\} \colon b^ a \not\equiv 1\ (p)$.

Возьмём такое $b$ и рассмотрим $b^{\beta _ i} S = \sum \limits _{x_ i=1}^ p (b x_ i)^{\beta _ i} \equiv \sum \limits _{y=1}^ p y^{\beta _ i} = S \Rightarrow$ $b^{\beta _ i} S \equiv S \Rightarrow$
$S(b^{\beta _ i} - 1) \equiv 0 \Rightarrow S \equiv 0$. $\blacksquare$

Следствие из Т. Шевалле (Т. Варнинга) Пусть все условия как в Т. Шевалле, и, более того, $F(0,\ldots ,0) \equiv 0\pmod p$. Тогда есть $(x_1, \ldots , x_ n)\colon$ не все $x_ i \equiv 0 \pmod p$ и $F(x_1, \ldots , x_ n) \equiv 0\ (p)$.

Обобщение теоремы. Пусть $F_1, \ldots , F_ k \in \mathbb {Z}_ p[x_1, \ldots , x_ n]$. Пусть $\deg F_1 +\ldots + \deg F_ k < n$. Тогда число решений системы сравнений

$\begin{cases} F_1(x_1, \ldots , x_ n) \equiv 0\ (p),\\\ldots \\F_ k(x_1, \ldots , x_ n) \equiv 0\ (p) \end{cases}$ делится на $p$.

Обобщение следствия. Если есть нулевое решение системы, то есть хотя бы ещё одно решение.