то точка (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" —

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

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

доказательство теоремы Пифагора при помощи перекашиваний (см. также Квантик 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.