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

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

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

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


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


 Гипотеза Эрдёша является обобщением теоремы Семереди (поскольку ряд n=11kn=1k(n=11n) расходится как гармонический), а также теоремы Грина-Тао (поскольку сумма p1p, где суммирование ведётся по простым числам, также расходится).

Эквивалентность


 Гипотеза Эрдёша эквивалентна некоторому несложному усилению теоремы Семереди. Обозначим через Ak(n) наибольшее множество Ak(n){1,,n}, не содержащее арифметических прогрессий длины k. Обозначим плотность этого множества в отрезке [1;n] как $a_k(n)=\frac{|
 Тогда гипотеза Эрдёша эквивалентна утверждению о том, что ряд \sum \limits_{t=1}^{\infty} {{a_k}(4^t)}расходитсяприлюбомk \ge 3$.

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


 Ввиду эквивалентности расхождению t=1ak(4t), гипотеза Эрдёша может быть доказана, если будет доказано, что k3: ε>0: ak(N)=O(1(logN)1+ε).
 Однако на данный момент доказано только, что ak(N)=O(1(loglogn)ck), где ck=22k+9, а также, в частном случае k=3, что a3(N)=O(loglogNlogN).