Поэтому условие на верхнюю плотность — это условие на то, сколь часто итерации 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" —

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

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

доказательство теоремы Пифагора при помощи перекашиваний (см. также Квантик 2020-2)

Давайте я соберу идеи доказательства Фюрстенберга теоремы Семереди в более строгий рассказ. Итак, пусть у нас есть множество A натуральных чисел положительной верхней плотности.

Рассмотрим множество X двусторонних последовательностей нулей и единиц — иными словами, отображений из Z в {0,1}.

На X есть (взаимно-однозначное) отображение f левого сдвига — сдвигающее всю последовательность на один символ влево. Есть подмножество E — состоящее из последовательностей, у которых на нулевом месте стоит 1. И есть последовательность x_A — характеристическая (или индикаторная) функция A.

Ингредиент, про который я в прошлый раз не очень подробно сказал, откуда он берётся, это инвариантная мера µ (вероятностная — то есть с µ(X)=1; вообще, в теории динсистем обычно меры вероятностные).

Есть такая теорема Крылова-Боголюбова: для любого непрерывного отображения f метрического компакта X в себя есть (хоть какая-то!) f-инвариантная мера.