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

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

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

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

,

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

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

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

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

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

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

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

Однак на даний момент^[коли?] доведено лише^[5], що $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)$ .

Примітки

↑ Гіпотезу іноді плутають із гіпотезою Ердеша — Турана^[en]
↑ Bollobás, Béla. To Prove and Conjecture: Paul Erdős and His Mathematics // American Mathematical Monthly : journal. — 1988. — Vol. 105, no. 3 (3). — P. 233.
↑ Soifer, Alexander (2008); The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators; New York: Springer. p. 354. ISBN 978-0-387-74640-1
↑ М. Айгнер, Г. Циглер, «Доказательства из книги» — М. «Мир», 2006, стр. 13
↑ Шкредов, 2006, с. 115—116.

Посилання

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. Архівовано квітень 28, 2016 на сайті Wayback Machine.
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:10.1007/BF02579174
И. Д. Шкредов. Теорема Семереди и задачи об арифметических прогрессиях // УМН. — 2006. — Вип. 6(372). — С. 111—178.

[1] Гіпотезу іноді плутають із гіпотезою Ердеша — Турана^[en]

[2] Bollobás, Béla. To Prove and Conjecture: Paul Erdős and His Mathematics // American Mathematical Monthly : journal. — 1988. — Vol. 105, no. 3 (3). — P. 233.

[3] Soifer, Alexander (2008); The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators; New York: Springer. p. 354. ISBN 978-0-387-74640-1

[4] М. Айгнер, Г. Циглер, «Доказательства из книги» — М. «Мир», 2006, стр. 13

[FOOTNOTEШкредов2006115—116-5] Шкредов, 2006, с. 115—116.

[1]

[2]

[3]

[4]

[5]