При этом, если мы говорим о физических системах — например, о качающемся маятнике, или о планете, движущейся по орбите — то состояние это не только положение, но и скорость. А отображение 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)

Поэтому условие на верхнюю плотность — это условие на то, сколь часто итерации x_A возвращаются в C:

Но и условие на арифметическую прогрессию среди элементов A тоже проговаривается в динамических терминах. Например, если мы хотим, чтобы m+d, m+2d, m+3d все принадлежали A, то нужно, чтобы образы точки
f^{m-1}(x_A) за d, 2d и за 3d итераций одновременно принадлежали C. Или, иными словами, если мы возьмём декартово произведение XxXxX и на нём будем применять покомпонетно f, f^2 и f^3,

то точка (w,w,w), где w=f^{m-1}(x_A), должна за d итераций вернуться в CxCxC.

Но если говорить о возвращении, то в теории динамических систем есть теорема Пуанкаре о возвращении. Пусть отображение f сохраняет некоторую меру µ. Например, представим себе, что мы наблюдаем установившееся течение несжимаемой жидкости. Тогда, если мы выделим какое-то множество B положительной меры, µ(B)>0, то µ-почти все точки рано или поздно в него вернутся.

Давайте я для простоты предположу, что динамическая система обратимая — наше отображение f, вообще-то, таковым не является (оно забывает первый символ), но мы можем рассмотреть и двусторонне-бесконечные последовательности с точно таким же отображением левого сдвига — сдвигающим всю последовательность на один индекс влево.

Так вот — давайте сначала увидим, что хоть одна точка B в него вернётся. Действительно, если это не так, то у нас будут образы B, f(B), f^2(B), все друг с другом не пересекающиеся. И у каждого будет одна и та же мера µ(B). Но на них на всех тогда не хватит места — мера µ(X) конечна (кажется, я не написал этого явно — но обычно в динамических системах меры берут вероятностными, т.е. µ(X)=1).

Ну и если бы мера подмножества B' тех точек, которые никогда не вернутся в B, была бы положительна — мы бы взяли B' вместо B (если точка никогда не возвращается в B, то и в его подмножество B' она никогда не вернётся), и повторили бы предыдущее рассуждение.

Так вот — буквально сослаться на теорему Пуанкаре о возвращении нельзя, и нам придётся всё-таки работать с исходной системой, а не с заманчиво-изящным декартовым произведением. А то, что нужно применить, называется Furstenberg multiple recurrence theorem (и собственно, в его динамическом доказательстве и скрыта вся сложность; так-то эта теорема оказывается просто эквивалентна теореме Семереди).
Но — я надеюсь, что какие-то стыкующиеся кусочки динамического взгляда в этой задаче уже проглядывают...