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

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

<math> \sum_{n\in A} \frac{1}{n} = \infty </math>,

то есть <math>A</math> — Шаблон:Нп3, то <math>A</math> содержит арифметическую прогрессию любой наперёд заданной длины.

Эрдёш обещал в своё время премию в 3 тыс. долларов США за доказательство гипотезы, по состоянию на 2008 год была установлена премия в 5 тыс. долларов США.

Связь с другими утверждениями

Следствия из гипотезы

Гипотеза Эрдёша является обобщением теоремы Семереди (поскольку ряд <math>\sum \limits_{n=1}^{\infty} \frac{1}{kn} = \frac{1}{k} \left({ \sum \limits_{n=1}^{\infty} \frac{1}{n} }\right)</math> расходится как гармонический), а также теоремы Грина — Тао (поскольку сумма <math>\sum \limits_{p} \frac{1}{p}</math>, где суммирование ведётся по простым числам, также расходится).

Утверждения, из которых следует гипотеза

Ввиду эквивалентности расхождению <math>\sum \limits_{t=1}^{\infty} {{a_k}(4^t)}</math>, гипотеза Эрдёша может быть доказана, если будет доказано, что <math>\forall k \ge 3:\ \forall \varepsilon > 0:\ a_k(N) = O\left({\frac{1}{(\log{N})^{1 + \varepsilon}}}\right)</math>.

Однако на данный момент доказано толькоШаблон:Sfn, что <math>a_k(N) = O\left({\frac{1}{(\log{\log{n}})^{c_k}}}\right)</math>, где <math>c_k=2^{-2^{k+9}}</math>, а также, в частном случае <math>k=3</math>, что <math>a_3(N) = O\left({\sqrt{\frac{\log{\log{N}}}{\log{N}}}}\right)</math>.

Ссылки

• 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
• Шаблон:Публикация