WikiSort.ru - Не сортированное

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

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

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

Гипотеза Эрдёша эквивалентна^[5] определённому несложному усилению теоремы Семереди. Обозначим через ${\displaystyle A_{k}(n)}$ наибольшее множество ${\displaystyle A_{k}(n)\subset \left\lbrace {1,\dots ,n}\right\rbrace }$ , не содержащее арифметических прогрессий длины ${\displaystyle k}$ . Обозначим плотность этого множества в отрезке ${\displaystyle [1;n]}$ как ${\displaystyle a_{k}(n)={\frac {|A_{k}(n)|}{n}}}$ .

Тогда гипотеза Эрдёша эквивалентна утверждению о том, что ряд ${\displaystyle \sum \limits _{t=1}^{\infty }{{a_{k}}(4^{t})}}$ расходится при любом ${\displaystyle k\geq 3}$ .

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

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

Однако на данный момент доказано только^[6], что ${\displaystyle a_{k}(N)=O\left({\frac {1}{(\log {\log {n}})^{c_{k}}}}\right)}$ , где ${\displaystyle c_{k}=2^{-2^{k+9}}}$ , а также, в частном случае ${\displaystyle k=3}$ , что ${\displaystyle a_{3}(N)=O\left({\sqrt {\frac {\log {\log {N}}}{\log {N}}}}\right)}$ .