Гипотеза Эрдёша об арифметических прогрессиях

Гипотеза Эрдёша об арифметических прогрессиях — предположение в аддитивной комбинаторике, сформулированное Палом Эрдёшем, согласно которому в случае, если сумма обратных величин положительных натуральных чисел некоторого множества расходится, то множество содержит сколь угодно длинные арифметические прогрессии.

Формально, если:

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

то есть $A$ — Шаблон:Нп3, то $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 Шаблон:Wayback, Séminaire Delange-Pisot-Poitou (14e année: 1972/1973), Théorie des nombres, Fasc 2., Exp. No. 24, pp. 7,
• 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
• Шаблон:Публикация