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

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

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).