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

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

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

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

тобто $A$ — Шаблон:Iw, то $A$ містить арифметичну прогресію будь-якої наперед заданої довжини.

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

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

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

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

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

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

Однак на даний моментШаблон:Коли? доведено лишеШаблон:Sfn, що $a_k(N)=O\left(\frac{1}{(\log \log n{)}^{c_k}}\right)$, де $c_k=2^{-2^{k+9}}$, а також, в окремому випадку $k=3$, що $a_3(N)=O\left(\sqrt{\frac{\log \log N}{\log N}}\right)$.

Посилання

• P. Erdős: Résultats et problèmes en théorie de nombres, Séminaire Delange-Pisot-Poitou (14e année: 1972/1973), Théorie des nombres, Fasc 2., Exp. No. 24, pp. 7. Шаблон:Wayback
• P. Erdős: Problems in number theory and combinatorics, Proc. Sixth Manitoba Conf. on Num. Math., Congress Numer. XVIII(1977), 35-58.
• P. Erdős: On the combinatorial problems which I would most like to see solved, Combinatorica, 1(1981), 28. Шаблон:DOI
• Шаблон:Публікація