Теорема Роньяи

Рассмотрим двумерный случай проблемы Эрдеша – Гинзбурга – Зива.

Пусть дано число $n$. При каком наименьшем $f$ мы можем гарантировать, что для любого набора $(a_1, b_1), \ldots , (a_ f, b_ f)$ $\exists I \subset \{ 1, 2, \ldots , f\} , |I| = n\colon \sum \limits _{i\in I} a_ i \equiv 0\ (n), \sum \limits _{i\in I} b_ i \equiv 0\ (n)$?

$f = f(n) \geqslant 4n-3$.

Пример: $(0, 0) \times (n-1), (0, 1) \times (n-1), (1, 0) \times (n-1), (1, 1) \times (n-1)$, выбрать $n$ пар таким образом нельзя.

• Кемниц в 70-е высказал гипотезу, что $f(n) = 4n-3$.

• 1990, Алон и Дубинер доказали, что $f(n) \leqslant 6n-5, n \geqslant n_0$.

• 2000, Роньяи доказал, что $f(n) \leqslant 4n-2$.

• 2003, Райер доказал гипотезу Кемница, $f(n) = 4n-3$.

Дальше будет доказана теорема Роньяи.