И вторая — со страницы 28 работы Эрдеша, "On the combinatorial problems which I would most like to see solved" —

Ну и на этом я на сегодня хочу прекратить дозволенные речи.

По-моему, это прекрасно:

доказательство теоремы Пифагора при помощи перекашиваний (см. также Квантик 2020-2)

Давайте я соберу идеи доказательства Фюрстенберга теоремы Семереди в более строгий рассказ. Итак, пусть у нас есть множество A натуральных чисел положительной верхней плотности.

Рассмотрим множество X двусторонних последовательностей нулей и единиц — иными словами, отображений из Z в {0,1}.

На X есть (взаимно-однозначное) отображение f левого сдвига — сдвигающее всю последовательность на один символ влево. Есть подмножество E — состоящее из последовательностей, у которых на нулевом месте стоит 1. И есть последовательность x_A — характеристическая (или индикаторная) функция A.

Ингредиент, про который я в прошлый раз не очень подробно сказал, откуда он берётся, это инвариантная мера µ (вероятностная — то есть с µ(X)=1; вообще, в теории динсистем обычно меры вероятностные).

Есть такая теорема Крылова-Боголюбова: для любого непрерывного отображения f метрического компакта X в себя есть (хоть какая-то!) f-инвариантная мера.

И доказывается она (почти) явной конструкцией — которая называется процедурой Крылова-Боголюбова. А именно: возьмём любую начальную точку x_0 — и посмотрим на её орбиту x_n:=f^n(x_0).

Возьмём начальный отрезок этой орбиты длины n — и распределим по нему равномерно единичную массу:
(1/n) в точку x_0
(1/n) в точку x_1=f(x_0)
...
(1/n) в точку x_{n-1}.

Получающаяся мера µ_n ( =распределение единичной массы) не инвариантна: применение f переведёт её в чуть-чуть от неё отличающуюся (добавится (1/n) в точке x_n и пропадёт в точке x_0).

Но чем больше n — тем мера ближе к инвариантной. И поэтому любая предельная точка последовательности мер µ_n — это уже в точности инвариантная мера. А пространство вероятностных мер на компакте — само по себе компакт (относительно *-слабой сходимости мер, если говорить совсем аккуратно). Поэтому из последовательности µ_n можно выделить сходящуюся подпоследовательность µ_{n_j} — предел которой и будет искомой инвариантной мерой.

Так вот: запустим процедуру Крылова-Боголюбова для нашего отображения и для начальной точки x_A. При этом число n принадлежит A тогда и только тогда, когда на нулевом месте у f^n(x_A) стоит 1 — то есть f^n(x_A) лежит в E.

Поэтому мера µ_n(E) это доля элементов A среди отрезка 0,1,...,n-1. И по определению верхней плотности есть подпоследовательность моментов n_m, для которой µ_{n_m}(E) стремится к rho(A)>0.
Выделив сходящуюся подпоследовательность µ_{n_{m_j}} уже из µ_{n_m} — получим меру µ, которая и инвариантная, и такова, что µ(E)=\rho(A)>0.

После чего остаётся применить самый сложный шаг доказательства — теорему Фюрстенберга о кратном возвращении (Furstenberg Multiple Recurrence Theorem); я её процитирую по статье И.Д. Шкредова "Теорема Семереди и задачи об арифметических прогрессиях" (http://www.mi-ras.ru/~ishkredov/Paperru/12.pdf )

Итак — для некоторого d мера µ множества

положительна. Но это множество это последовательности, у которых на местах 0, d,...,(k-1)d стоят единицы.

А если вспомнить, как мы меру µ строили — усредняя сдвиги — то отсюда следует, что для того же d верхняя плотность тех m, для которых точки m, m+d,...,m+(k-1)d принадлежат A, положительна. В частности, такие прогрессии любой длины k есть.

Тот переход, что мы сейчас выполнили, называется принципом соответствия Фюрстенберга; опять-таки, я процитирую статью Шкредова: