И — известно, что ряд из обратных простых 1/p тоже расходится. Это можно увидеть разными способами, правильнее всего, наверно, это увидеть через тождество Эйлера для дзета-функции:

При s=1 в левой части стоит (расходящийся) гармонический ряд, значит, сумма логарифмов сомножителей правой части расходится. А
-ln(1-1/p)~ 1/p.

Конечно, можно сослаться и на асимптотический закон распределения простых чисел, что p_n ~ n ln n, а ряд 1/(n ln n) расходится, но мне это показалось неправильным — ибо если посмотреть, сколько всего внутри асимптотического закона закопано, чтобы его вывести...

Так вот — сумма ряда из обратных простых расходится. Поэтому следствием из гипотезы Эрдеша было бы то, что есть сколь угодно длинные прогрессии, состоящие из простых чисел.

И это и правда так — утверждающая это теорема Грина-Тао была доказана ими в 2004 году (и это был один из результатов, принесших Тао премию Филдса).

Но что же до самой гипотезы Эрдеша про множества с расходящейся суммой обратных, то в общем виде она остаётся недоказанной — более того, не доказано даже, что в таком множестве найдутся арифметические прогрессии длины 3 !

Вот препринт 2014 года (и статья 2016го) — https://arxiv.org/abs/1405.5800 — где говорится, сколько может быть чисел на отрезке от 1 до N, так, чтобы среди них не было трёх последовательных членов арифметической прогрессии. Но оценка там совершенно не мешает расходимости ряда из обратных...
(См. также — https://en.wikipedia.org/wiki/Erd%C5%91s_conjecture_on_arithmetic_progressions )

Возвращаясь к доказательству Фюрстенберга теоремы Семереди. Удивительным образом, предложенное им доказательство такого "комбинаторного" факта работает на языке динамических систем.

Вообще, динамическая система [с дискретным временем] — это пара из множества состояний X и (обычно — непрерывного) отображения f:X->X.
Грубо говоря — отображение говорит, "в каком состоянии окажется система через секунду".

При этом, если мы говорим о физических системах — например, о качающемся маятнике, или о планете, движущейся по орбите — то состояние это не только положение, но и скорость. А отображение f — это решение задающего эволюцию системы дифференциального уравнения: "где и с какой скоростью мы окажется через заданный промежуток времени".

И при изучении теории динамических систем не начинают с чего-нибудь жутко сложного вроде всей Солнечной системы — а с модельных примеров. И один из таких (очень важных, и потом играющих во всей науке) примеров это "символическая динамика": X это множество всех последовательностей из 0 и 1, а f:X->X это "левый сдвиг" — первый элемент выбрасывается, все остальные сдвигаются на один влево.

Кстати — модельный пример хаотической динамики это "отображение удвоения" на окружности:
f: \varphi -> 2\varphi.
Одна его итерация удваивает расстояние между близкими точками — так что, если исходная точка известна лишь приближённо, через очень небольшое число итераций f о её образе уже ничего нельзя сказать ("нельзя предсказать погоду через месяц").

Так вот — если мы возьмём окружность длины 1 (а не 2π) и рассмотрим последовательность цифр после запятой в двоичной записи \varphi — то к этой последовательности как раз таки применяется левый сдвиг!

Более того, это я, конечно, отклоняюсь в сторону, но символическую динамику можно "пристегнуть" (пусть и разрывным образом, что не всегда хорошо) к любой динамической системе. Выберем любое подмножество A в X.
И сопоставим любой начальной точке x её судьбу — последовательность 0 и 1, говорящую, правда ли, что
f^k(x) принадлежит A.
Тогда судьба f(x) — это просто левый сдвиг судьбы x.

Ну и мы, на самом деле, уже видели пример такого, когда брали поворот окружности на золотое сечение — и в качестве судьбы получали слово Фибоначчи.

Но давайте вернёмся к теореме Семереди. Для её динамического доказательства Фюрстенберг перевёл её на язык динамических систем — а именно, как раз таки символической динамики.
А именно — начальное множество A это подмножество натуральных чисел. Так превратим его в его характеристическую функцию x_A — в последовательность 0 и 1, говорящих, принадлежит ли A данное натуральное число.

И давайте рассмотрим множество C ("цилиндр") последовательностей, у которых первый элемент это 1.

На множестве последовательностей действует отображение f — левый сдвиг. На этом языке

(где x_A — это та последовательность 0 и 1, которая кодирует A)