Но чем больше 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 есть.

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

На самом деле, теорема Фюрстенберга о кратном возвращении теореме Семереди даже и эквивалентна (см. второе предложение выше). Но самый технически сложный шаг работы Фюрстенберга (и о чём я пока не сказал ни слова) — это как теорему о кратном возвращении динамическими методами доказывать. И там начинают возникать слова "слабое перемешивание", "компактный фактор", и ещё разные — но вот туда я как раз не пойду.

У этой науки есть ещё обобщения — многомерная теорема Фюрстенберга и Кацнельсона и следующая из неё многомерная версия теоремы Семереди ; см. https://terrytao.wordpress.com/2008/02/10/254a-lecture-10-the-furstenberg-correspondence-principle/ —

То есть в подмножестве Z^m с положительной верхней плотностью есть подмножества, гомотетичные любому конечному "шаблону" (v_1,...,v_k).

Но, наверное, в этом месте я хочу закончить рассказ об этой работе Фюрстенберга — и продолжить рассказ о других его работах в следующий раз.

===
В качестве паузы (чтобы писать не только о динамических системах) — короткий рассказ про совсем другое: про числа Каталана.

Допустим, нас интересует, сколькими способами можно расставить n открывающих и n закрывающих скобок так, чтобы в любом начальном подслове закрывающих скобок было не больше, чем открывающих. То есть (), (()), ()() можно, ())( или ())(()() нельзя.

Если нарисовать "по точкам" график разности "число открывающих скобок минус число закрывающих из первых k символов", то он состоит из отрезков, идущих под 45 градусов либо вправо-вверх, либо вправо-вниз. Соответственно, число Каталана это число таких путей, идущих из точки (0,0) в точку (2n,0) и не спускающихся ниже оси абсцисс по пути.

Оно же равно количеству деревьев на плоскости с n+1 вершиной, отмеченным корнем и "землёй" (или, равносильно, первым ребром из этой вершины): если обходить это дерево "снаружи", начиная с первого ребра — расстояние до корня как раз и будет меняться на +1/-1 на каждом шаге:

Оно же число триангуляций [диагоналями] n+2-угольника. Ну и вообще у чисел Каталана очень много разных определений и свойств — но речь не об этом, а о том, как их посчитать.

Во-первых, можно через производящие функции. Несложно увидеть рекуррентное соотношение для чисел Каталана C_n: