Processing math: 26%
Now you are in the subtree of Lecture Notes public knowledge tree. 

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

Теорема (Роньяи). Если m=4p2, p — простое, то (a1,b1),,(am,bm)
I{1,2,,m}: |I|=p и iIai0 (p), iIbi0 (p).

Лемма. Пусть (a1,b1),,(a3p,b3p) таковы, что pi=1ai0 (p), pi=1bi0 (p). Тогда I{1,2,,3p}:|I|=p и iIai0 (0), iIbi0 (0).

 (Лемма) Рассмотрим три многочлена F1,F2,F3:

F1(x1,,x3p1):=3p1i=1aixp1i.

F2(x1,,x3p1):=3p1i=1bixp1i.

F3(x1,,x3p1):=3p1i=1xp1i.

{F1(x1,,x3p1)0 (p),F2(x1,,x3p1)0 (p),F3(x1,,x3p1)0 (p).

degFi=p1, degF1+degF2+degF3=3p3<3p1.

(0,,0) — решение системы. Тогда есть (x1,,x3p1) — решение системы, у которого не все координаты равны 0 (по Т. Варнинга).

Пусть J — множество тех i{1,,3p1}, что 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.

  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