положительна. Но это множество это последовательности, у которых на местах 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:

Если собрать их в производящую функцию,
F(z)=\sum_n C_n z^n,
то в правой части рекуррентного соотношения стоят коэффициенты F(z)^2 — которые ещё нужно сдвинуть на одну степень. Поэтому оно превращается в квадратное уравнение на производящую функцию:
F(z)-1=z F^2(z).

Отсюда находим F(z) —

(знак в числителе должен быть минусом, потому что иначе числитель не обратится в ноль при z=0, а у нас не может быть особенности вида 1/z).

И, наконец, разложив (1-4z)^{1/2} по биному Ньютона для нецелой степени — где нецелый биномиальный коэффициент определяется как