Доказательство теоремы Роньяи
Теорема (Роньяи). Если m=4p−2, p — простое, то ∀(a1,b1),…,(am,bm)
∃I⊂{1,2,…,m}: |I|=p и ∑i∈Iai≡0 (p), ∑i∈Ibi≡0 (p).
Лемма. Пусть (a1,b1),…,(a3p,b3p) таковы, что p∑i=1ai≡0 (p), p∑i=1bi≡0 (p). Тогда ∃I⊂{1,2,…,3p}:|I|=p и ∑i∈Iai≡0 (0), ∑i∈Ibi≡0 (0).
▴ (Лемма) Рассмотрим три многочлена F1,F2,F3:
F1(x1,…,x3p−1):=3p−1∑i=1aixp−1i.
F2(x1,…,x3p−1):=3p−1∑i=1bixp−1i.
F3(x1,…,x3p−1):=3p−1∑i=1xp−1i.
{F1(x1,…,x3p−1)≡0 (p),F2(x1,…,x3p−1)≡0 (p),F3(x1,…,x3p−1)≡0 (p).
degFi=p−1, degF1+degF2+degF3=3p−3<3p−1.
(0,…,0) — решение системы. Тогда есть (x1,…,x3p−1) — решение системы, у которого не все координаты равны 0 (по Т. Варнинга).
Пусть J — множество тех i∈{1,…,3p−1}, что xi≢.
(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.
Пусть (x_1, \ldots , x_ m) такое, что число единиц в нём не делится на p. Тогда, за счёт третьей скобки F(x_1, \ldots , x_ m) \equiv 0\ (p).
Пусть (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).
-
Пусть (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).
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