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

Теорема (Роньяи). Если $m = 4p-2$, $p$ — простое, то $\forall (a_1, b_1), \ldots , (a_ m, b_ m)$
$\exists I \subset \{ 1, 2, \ldots , m\} \colon$ $|I| = p$ и $\sum \limits _{i\in I} a_ i \equiv 0\ (p)$, $\sum \limits _{i\in I} b_ i \equiv 0\ (p)$.

Лемма. Пусть $(a_1, b_1), \ldots , (a_{3p}, b_{3p})$ таковы, что $\sum \limits _{i=1}^ p a_ i\equiv 0\ (p)$, $\sum \limits _{i=1}^ p b_ i\equiv 0\ (p)$. Тогда $\exists I \subset \{ 1, 2, \ldots , 3p\} \colon |I| = p$ и $\sum \limits _{i\in I} a_ i \equiv 0\ (0)$, $\sum \limits _{i\in I} b_ i \equiv 0\ (0)$.

$\blacktriangle$ (Лемма) Рассмотрим три многочлена $F_1, F_2, F_3\colon$

$F_1(x_1, \ldots , x_{3p-1}) := \sum \limits _{i=1}^{3p-1} a_ i x_ i^{p-1}$.

$F_2(x_1, \ldots , x_{3p-1}) := \sum \limits _{i=1}^{3p-1} b_ i x_ i^{p-1}$.

$F_3(x_1, \ldots , x_{3p-1}) := \sum \limits _{i=1}^{3p-1} x_ i^{p-1}$.

$\begin{cases} F_1(x_1, \ldots , x_{3p-1}) \equiv 0\ (p), \\F_2(x_1, \ldots , x_{3p-1}) \equiv 0\ (p), \\F_3(x_1, \ldots , x_{3p-1}) \equiv 0\ (p). \end{cases}$

$\deg F_ i = p-1$, $\deg F_1 + \deg F_2 + \deg F_3 = 3p-3 < 3p-1$.

$(0, \ldots , 0)$ — решение системы. Тогда есть $(x_1, \ldots , x_{3p-1})$ — решение системы, у которого не все координаты равны 0 (по Т. Варнинга).

Пусть $J$ — множество тех $i \in \{ 1, \ldots , 3p-1\}$, что $x_ i \not\equiv 0\ (p)$.
$(x_1, \ldots , x_{3p-1})$ — является решением нашей системы, значит

1) $F_1(x_1, \ldots , x_{3p-1}) \equiv 0\ (p)$, т.е. $\sum \limits _{i=1}^{3p-1} a_ i x_ i^{p-1} \equiv 0\ (p)$, т.е. $\sum \limits _{i\in J} a_ i x_ i^{p-1} \equiv 0\ (p) \Rightarrow$ $\sum \limits _{i\in J} a_ i \equiv 0\ (p)$.

2) $\sum \limits _{i\in J} b_ i \equiv 0\ (p)$.

3) $\sum \limits _{i\in J} 1 = |J| \equiv 0\ (p)$.

Если $|J| = p$, то положим $I = J$.

Если $|J| = 2p$, то положим $I = \{ 1, \ldots , 3p\} \backslash J$. $|I| = p, \sum \limits _{i\in I} = \sum \limits _{i=1}^{3p} a_ i - \sum \limits _{i\in J} a_ i \equiv 0\ (p)$. $\blacksquare$

$\blacktriangle$ (Теорема) Путь $m = 4p-2$ и $(a_1, b_1), \ldots , (a_ m, b_ m)$ — произвольные точки.

Предположим, что $\forall I \subset \{ 1, \ldots , m\} \colon |I| = p$ либо $\sum \limits _{i\in I} a_ i \not\equiv 0\ (p)$, либо $\sum \limits _{i\in I} b_ i \not\equiv 0\ (p)$.

За счёт леммы можно усилить предположение: $\forall I\subset \{ 1, \ldots , m\} \colon |I| \in \{ p, 3p\}$ либо $\sum \limits _{i\in I} a_ i \not\equiv 0\ (p)$, либо $\sum \limits _{i\in I} b_ i \not\equiv 0\ (p)$.

Рассмотрим

$F(x_1, \ldots , x_ m) = \left( \left(\sum \limits _{i=1}^ m a_ i x_ i\right)^{p-1} - 1 \right)$ $\left( \left(\sum \limits _{i=1}^ m b_ i x_ i \right)^{p-1} - 1 \right)$ $\left( \left(\sum \limits _{i=1}^ m x_ i \right)^{p-1} - 1 \right)$ $\left( \sigma _ p(x_1, \ldots , x_ n) - 2 \right)$.

$\sigma _ p(x_1, \ldots , x_ m) = \sum \limits _{\substack {\scriptscriptstyle I \subset \{ 1, \ldots , m\} , \\ \scriptscriptstyle |I| = p}} \prod \limits _{\scriptscriptstyle i\subset I} x_ i$.

$\sigma _1(x_1, \ldots , x_ m) = x_1 + \ldots + x_ m$.

$\sigma _2(x_1, \ldots , x_ m) = x_1 x_2 + x_1 x_3 +\ldots + x_{m-1} x_ m$.

$\deg F = 4p-3 < m$.

Последовательно подставим в $F$ все возможные $(x_1, \ldots , x_ m) \in \{ 0, 1\} ^ m$.

1. Пусть $(x_1, \ldots , x_ m)$ такое, что число единиц в нём не делится на $p$. Тогда, за счёт третьей скобки $F(x_1, \ldots , x_ m) \equiv 0\ (p)$.

2. Пусть $(x_1, \ldots , x_ m)$ — такое, что число единиц в нём равно $p$ или $3p$. Обозначим $I$ — множество индексов $i\colon x_ i = 1$. По предположению противного либо $\sum \limits _{i\in I} a_ i \not\equiv 0\ (p)$, либо $\sum \limits _{i\in I} b_ i \not\equiv 0\ (p) \Rightarrow$ либо $\sum \limits _{i=1}^ m a_ i \not\equiv 0\ (p)$, либо $\sum \limits _{i=1}^ m b_ i \not\equiv 0\ (p) \Rightarrow$ либо $\left(\sum \limits _{i=1}^ m a_ i x_ i\right)^{p-1} \equiv 1\ (p)$, либо $\left(\sum \limits _{i=1}^ m b_ i x_ i\right)^{p-1} \equiv 1\ (p) \Rightarrow F(x_1, \ldots , x_ m) \equiv 0\ (p)$.

3. Пусть $(x_1, \ldots , x_ m)$ — такое, что число единиц в нём равно $2p$. Тогда

   $\sigma _ p(x_1, \ldots , x_ n) = C_{2p}^ p \equiv 2\ (p) \Rightarrow F(x_1, \ldots , x_ m) \equiv 0\ (p)$.

4. $F(0, \ldots , 0) = (-1)(-1)(-1)(-2) = 2$.

Для всех $(x_1, \ldots , x_ m) \in \{ 0, 1\} ^ m$, кроме $(0, \ldots , 0)$, $F(x_1, \ldots , x_ m) \equiv 0\ (p)$. $F(0, \ldots , 0) = 2$.

Представим себе, что мы раскрываем скобки в определении $F$. Получается комбинация каких-то одночленов. $x_1^{\alpha _1}\cdot \ldots \cdot x_ m^{\alpha _ m} \to x_{i_1}^{\alpha _{i_1}}\cdot \ldots \cdot x_{i_ m}^{\alpha _{i_ m}} \to x_{i_1}\cdot \ldots \cdot x_{i_ m}$ (срежем степени).

$\widetilde{F}(x_1, \ldots , x_ m)$ — новый многочлен. $\deg \widetilde{F} \leqslant \deg F < m$.

Для всех $(x_1, \ldots , x_ m) \in \{ 0, 1\} ^ m$, кроме $(0, \ldots , 0)$. $\widetilde{F}(x_1, \ldots , x_ m) \equiv 0\ (p)$. $\widetilde{F} (0, \ldots , 0) = 2$.

Теорема. Многочлен $\widetilde{F}$, обладающий всеми этими свойствами, имеет вид

$2(1-x_1)(1-x_2)\cdot \ldots \cdot (1-x_ m)$.

По теореме, этот многочлен имеет степень $m$, однако у нас степень $\lt m$, противоречие. $\blacksquare$