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

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

И пара цитат в заключение — одна из самого Фюрстенберга, из той самой его работы 1977 года —

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

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