Меню Главная Случайная статья Настройки Гипотеза Эрдёша об арифметических прогрессиях Материал из https://ru.wikipedia.org Гипотеза Эрдёша об арифметических прогрессиях[1] — предположение в аддитивной комбинаторике, сформулированное Палом Эрдёшем, согласно которому в случае, если сумма обратных величин положительных натуральных чисел некоторого множества расходится, то множество содержит сколь угодно длинные арифметические прогрессии. Формально, если: ${\displaystyle \sum _{n\in A}{\frac {1}{n}}=\infty }$, то есть ${\displaystyle A}$ — большое множество[англ.], то ${\displaystyle A}$ содержит арифметическую прогрессию любой наперёд заданной длины. Эрдёш обещал в своё время премию в 3 тыс. долларов США за доказательство гипотезы[2], по состоянию на 2008 год была установлена премия в 5 тыс. долларов США[3]. Содержание 1 Связь с другими утверждениями 1.1 Следствия из гипотезы 1.2 Утверждения, из которых следует гипотеза 2 Примечания 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)}$. Примечания Гипотезу иногда путают с гипотезой Эрдёша — Турана[англ.] Bollobs, Bla. To Prove and Conjecture: Paul Erds and His Mathematics (англ.) // American Mathematical Monthly : journal. — 1988. — March (vol. 105, no. 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. Erds: Rsultats et problmes en thorie de nombres Архивная копия от 28 апреля 2016 на Wayback Machine, Sminaire Delange-Pisot-Poitou (14e anne: 1972/1973), Thorie des nombres, Fasc 2., Exp. No. 24, pp. 7, P. Erds: Problems in number theory and combinatorics, Proc. Sixth Manitoba Conf. on Num. Math., Congress Numer. XVIII(1977), 35-58. P. Erds: On the combinatorial problems which I would most like to see solved, Combinatorica, 1(1981), 28. doi:10.1007/BF02579174 И. Д. Шкредов. Теорема Семереди и задачи об арифметических прогрессиях // УМН. — 2006. — Т. 61, вып. 6(372). — С. 111—178. — doi:10.4213/rm5293.