Гіпотеза Ердеша про арифметичні прогресії

Гіпотеза Ердеша про арифметичні прогресії^[1] — припущення в адитивній комбінаториці, сформульоване Палом Ердешем, згідно з яким у випадку, якщо сума обернених величин додатних натуральних чисел деякої множини розбіжна, то множина містить як завгодно довгі арифметичні прогресії.

Формально, якщо:

${\displaystyle \sum _{n\in A}{\frac {1}{n}}=\infty }$ ,

тобто ${\displaystyle A}$ — велика множина^[en], то ${\displaystyle A}$ містить арифметичну прогресію будь-якої наперед заданої довжини.

За доведення гіпотези Ердеш обіцяв свого часу премію 3 тис. доларів США^[2]; станом на 2008 рік було встановлено премію 5 тис. доларів США^[3].

Зв'язок з іншими твердженнями

Наслідки з гіпотези

Гіпотеза Ердеша є узагальненням теореми Семереді (оскільки ряд ${\displaystyle \sum \limits _{n=1}^{\infty }{\frac {1}{kn}}={\frac {1}{k}}\left({\sum \limits _{n=1}^{\infty }{\frac {1}{n}}}\right)}$ розбіжний як гармонійний), а також теореми Ґріна — Тао (оскільки сума ${\displaystyle \sum \limits _{p}{\frac {1}{p}}}$, де підсумовування ведеться за простими числами, також розбіжна^[4]).

Твердження, з яких випливає гіпотеза

Через еквівалентність розбіжності ${\displaystyle \sum \limits _{t=1}^{\infty }{{a_{k}}(4^{t})}}$, гіпотезу Ердеша можна буде довести, якщо буде доведено, що ${\displaystyle \forall k\geq 3:\ \forall \varepsilon >0:\ a_{k}(N)=O\left({\frac {1}{(\log {N})^{1+\varepsilon }}}\right)}$.

Однак на даний момент^[коли?] доведено лише^[5], що ${\displaystyle a_{k}(N)=O\left({\frac {1}{(\log {\log {n}})^{c_{k}}}}\right)}$, де ${\displaystyle c_{k}=2^{-2^{k+9}}}$, а також, в окремому випадку ${\displaystyle k=3}$, що ${\displaystyle a_{3}(N)=O\left({\sqrt {\frac {\log {\log {N}}}{\log {N}}}}\right)}$.