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

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

,

то есть  — , то содержит арифметическую прогрессию любой наперёд заданной длины.

Эрдёш обещал в своё время премию в 3 тыс. долларов США за доказательство гипотезы, по состоянию на 2008 год была установлена премия в 5 тыс. долларов США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).

Эквивалентность Гипотеза Эрдёша эквивалентна определённому несложному усилению теоремы Семереди. Обозначим через наибольшее множество , не содержащее арифметических прогрессий длины . Обозначим плотность этого множества в отрезке как .

Тогда гипотеза Эрдёша эквивалентна утверждению о том, что ряд расходится при любом .

Утверждения, из которых следует гипотеза Ввиду эквивалентности расхождению , гипотеза Эрдёша может быть доказана, если будет доказано, что .

Однако на данный момент доказано только, что , где , а также, в частном случае , что .

Примечания

Ссылки 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, 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.

Категория:Комбинаторика Категория:Теория чисел Категория:Математические гипотезы