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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

,

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

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

Связь с другими утверждениями[править | править вики-текст]

Следствия из гипотезы[править | править вики-текст]

Гипотеза Эрдёша является обобщением теоремы Семереди (поскольку ряд расходится как гармонический), а также теоремы Грина-Тао (поскольку сумма , где суммирование ведётся по простым числам, также расходится[4]).

Эквивалентность[править | править вики-текст]

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

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

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

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

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

Примечания[править | править вики-текст]

  1. Гипотезу иногда путают с гипотезой Эрдёша — Турана (англ.)
  2. Bollobás, Béla (March 1988). «To Prove and Conjecture: Paul Erdős and His Mathematics». American Mathematical Monthly 105 (3): 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
  5. И. Д. Шкредов, Теорема Семереди и задачи об арифметических прогрессиях, стр. 139-140
  6. И. Д. Шкредов, Теорема Семереди и задачи об арифметических прогрессиях, стр. 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,
  • 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