Multiple Recurrence and dynamical progressions

Posted on 18/04/2025 by Joel Moreira
When Furstenberg translated Szemerédi’s theorem into an ergodic statement (as the original application of the correspondence principle) he formulated the “ergodic Szemerédi theorem”, nowadays often called Furstenberg’s multiple recurrence theorem as follows.
Theorem 1 (Ergodic Szemerédi) Let {(X,{\mathcal B},\mu,T)} be a measure preserving system and {A\subset X} a measurable set with {\mu(A)>0}. For every {k\in{\mathbb N}} there exist {n\in{\mathbb N}} such that {\mu(A\cap T^{-n}A\cap\cdots\cap T^{-kn}A)>0}.

Here {(X,{\mathcal B},\mu)} is an arbitrary probability space and {T:X\rightarrow X} any measurable map that preserves {\mu}. In the same paper Furstenberg also writes a dynamical reformulation for van der Waerden’s theorem (though it is not proved explicitly there that the two statements are equivalent).

Theorem 2 (Dynamical van der Waerden) Let {(X,T)} be a minimal system and {A\subset X} open and non-empty. For every {k\in{\mathbb N}} there exists {n\in{\mathbb N}} such that {A\cap T^{-n}A\cap\cdots\cap T^{-kn}A\neq\emptyset}.

Here {X} is a compact metric space and {T:X\rightarrow X} is a homeomorphism such that every orbit {\{T^nx:n\in{\mathbb Z}\}} is dense. More generally one might consider compact Hausdorff spaces but it turns out that the apparently stronger statement is in fact equivalent to the one stated (ultimately because the statement uses only one set and its (countable) orbit, which therefore can all be realized in a metrizable factor).

Continue reading →

Posted in Ergodic Theory, Topological Dynamics | Tagged dynamical progressions, Erdos progressions, Furstenberg, multiple recurrence | Leave a comment

The density finite sums theorem

Posted on 12/04/2025 by Joel Moreira

Bryna Kra, Florian Richter, Donald Robertson and I just submitted to the arXiv our paper entitled “The density finite sums theorem”, whose main goal is to prove the following theorem.

Theorem 1 Let {A\subset{\mathbb N}} have positive upper Banach density. Then for every {k\in{\mathbb N}} there exist {t\in{\mathbb N}} and an infinite set {B\subset{\mathbb N}} such that

\displaystyle \left\{\sum_{n\in F}n:F\subset B,\ 0<|F|\leq k\right\}\subset A-t. \ \ \ \ \ (1)

This theorem is motivated by the celebrated finite sums theorem of Hindman.

Theorem 2 If {{\mathbb N}} is finitely coloured, then there exists an infinite set {B\subset {\mathbb N}} such that the set

\displaystyle FS(B):=\left\{\sum_{n\in F}n:F\subset B,\ 0<|F|<\infty\right\}

is monochromatic.

An example of Straus (see Theorem 2.20 in this paper) shows that, in a sense, Theorem 1 is the best one can hope for as a density version of Hindman’s theorem: there are sets {A} with positive density such that for every {t} and {B} there is some {k} for which (1) fails. On the other hand some rather tantalizing questions asked in our survey (Questions 2.11 and 2.12) remain unanswered: while {t} must change with {k} it is possible that {B} does not!

The case {k=2} of Theorem 1 was proved in our earlier paper and had been conjectured by P. Erdös, who also asked for a density version of Hindman’s theorem. Our proof of Theorem 1 when restricted to the case {k=2} is different (and arguably simpler) than our earlier proof. Theorem 1 also implies the main results of our two earlier papers, and again in both cases the proof is different; therefore our paper yields new proofs of those theorems.

In the rest of the post I will outline the main steps in the proof of Theorem 1. Continue reading →

Posted in Combinatorics, Ergodic Theory, paper, Ramsey Theory, Topological Dynamics | Tagged Combinatorics, Erdos progressions, hindman theorem, Kra, Richter, Robertson, Sumsets | 1 Comment

Partition regularity of (generalized) Pythagorean pairs

Posted on 12/07/2024 by Joel Moreira

Nikos Frantzikinakis, Oleksiy Klurman and I have just uploaded to the arXiv our article entitled “Partition regularity of generalized Pythagorean pairs” which is a sequel to our previous paper “Partition regularity of Pythagorean pairs” .

Both papers address the question of partition regularity of quadratic equations. A diophantine equation is partition regular if for every partition (or coloring) of the natural numbers into finitely many sets {{\mathbb N}=C_1\cup\cdots\cup C_r}, some {C_i} contains a solution to the equation. For linear equations partition regularity is characterized by Rado’s theorem, which I discussed in this previous blog post. According to Rado’s theorem, the linear equation {a_1x_1+\cdots+a_kx_k=0} is partition regular if and only if there exists a non-empty set {S\subset\{1,\dots,k\}} for which {\sum_{i\in S}a_i=0}. Despite the relatively simple answer for linear equations, understanding partition regularity for polynomial equations remains very challenging, and in particular even the following simple looking question of Erdös and Graham remains open.

Question 1 Is the equation {x^2+y^2=z^2} partition regular?

Until 2016, this was open even for partitions of {{\mathbb N}} into only two sets. The two-color case has now been settled by Heule, Kullmann and Marek, but the verification made extensive use of computer checking, so it is unlikely that even the three-color case can be handled similarly (and of course no (finite) amount of computation can fully answer Question 1).

About a decade ago, Frantzikinakis and Host developed an ergodic theoretic framework to study more general equations of the form

\displaystyle ax^2+by^2=cz^2 \ \ \ \ \ (1)

for non-zero coefficients {a,b,c\in{\mathbb Z}}. (In fact this approach work as well for “non-diagonal” forms involving mixed terms {xy, xz} and {yz}, but for simplicity I will restrict this post to equation (1).) While this strategy does not give full partition regularity, it can be used to establish partition regularity of pairs.
Definition 2 Given {a,b,c\in{\mathbb Z}}, we say that (1) is partition regular with respect to {x,y} if for every finite coloring of {{\mathbb N}} there exist {x,y,z} satisfying (1) with {x} and {y} of the same color.

Continue reading →

Posted in Number Theory, paper, Ramsey Theory | Tagged Concentration estimates, Frantzikinakis, Klurman, Multiplicative Functions, Pythagorean Pairs | 2 Comments

Chowla’s conjecture and the Riemann hypothesis via the Liouville function

Posted on 23/07/2022 by Joel Moreira

Last week I was at the Bernoulli center in Lausanne, Switzerland to participate in the Young Researchers in Mathematics program organized by Florian Richter, and since the topic of the program was in number theory, we had some interesting conversations about prime number theory from an ergodic theory viewpoint. I decided to record some amusing conclusions that seem to connect Chowla’s conjecture to the Riemann hypothesis. To be clear, I am not suggesting any kind of progress in either of these problems, and in fact nothing in this post is particularly deep.

This also seemed to be an appropriate place to spell out some basic facts and conjectures from prime number theory and the relations between them as seen from my personal (i.e. ergodic) perspective.

Continue reading →

Posted in Classic results, Number Theory, Probability | Tagged Chowla, Matomaki, Radziwill, Riemann, Tao | 1 Comment

A proof of Erdos’ B+B+t conjecture

Posted on 27/06/2022 by Joel Moreira

Bryna Kra, Florian Richter, Donald Robertson and I have just uploaded to the arXiv our article entitled “A proof of Erdös’s {B+B+t} conjecture”. This (until now open) conjecture states that any set with positive density contains a configuration of the form {B\oplus B+t} for some {t\in{\mathbb N}} and some infinite subset {B\subset A}. Here we use the notation {B\oplus B} to denote the restricted sumset {\{b_1+b_2:b_1,b_2\in B,\ b_1\neq b_2\}}. Our result establishes this property for sets having positive upper Banach density, which is a slightly weaker assumption than, say, having positive natural density.

Our main theorem is the following.

Theorem 1 Let {A\subset{\mathbb N}} have positive upper Banach density, i.e. satisfying

\displaystyle d^*(A):=\limsup_{N-M\rightarrow\infty}\frac1{N-M}\big|A\cap\{M+1,\dots,N\}\big|>0.

Then there exist an infinite set {B\subset A} and a shift {t\in{\mathbb N}} such that {A-t} contains the restricted sumset {B\oplus B:=\{b_1+b_2:b_1,b_2\in B,\ b_1\neq b_2\}}.

Our proof of Theorem 1 uses some of the ergodic theoretic tools developed in our earlier paper, where we proved the following result.

Theorem 2 Let {A\subset{\mathbb N}} with {d^*(A)>0} and let {k\in{\mathbb N}}. Then {A} contains a sumset of the form {B_1+\cdots+B_k}, where {B_1,\dots,B_k} are infinite sets.

Both Theorems 1 and 2 extend (in different directions) a result of myself, Florian and Donald obtained a few years ago that also resolved a sumset conjecture of Erdös:

Theorem 3 If {A\subset{\mathbb N}} has positive upper Banach density, then there exist infinite sets {B,C\subset{\mathbb N}} such that {A\supset B+C=\{b+c:b\in B,c\in C\}}.

To see how Theorem 3 follows from Theorem 1 note that if {\tilde B\subset{\mathbb N}} is an infinite set such that {\tilde B\oplus\tilde B\subset A-t} for some shift {t\in{\mathbb N}}, then letting {B\subset\tilde B} be any infinite subset whose complement {\tilde B\setminus B} is also infinite, and letting {C:=t+\tilde B\setminus B} yields {B+C\subset A}.

A big part of the innovation in our earlier paper proving Theorem 2 was to obtain a different proof of Theorem 3 (which is the case {k=2}) that could be generalized to higher values of {k}. It turns out that this new proof can also be adapted to yield the stronger result in Theorem 1, although there are a few annoying issues that need to be handled. Continue reading →

Posted in Ergodic Theory, paper, Ramsey Theory | Tagged erdos, Kra, Richter, Robertson, Sumsets | 1 Comment

Infinite Sumsets in Sets with Positive Density

Posted on 08/06/2022 by Joel Moreira

Bryna Kra, Florian Richter, Donald Robertson and I have just uploaded to the arXiv our article entitled “Infinite Sumsets in Sets with Positive Density”. The main result of the paper is the following.

Theorem 1 Let {A\subset{\mathbb N}} have positive upper density, i.e. satisfying

\displaystyle \bar d(A):=\limsup_{N\rightarrow\infty}\frac1N\big|A\cap\{1,\dots,N\}\big|>0.

Then for any {k\in{\mathbb N}} there exist infinite sets {B_1,\dots,B_k\subset{\mathbb N}} such that {B_1+\cdots+B_k\subset A}.

One can in fact replace the positive upper density condition with the weaker condition of positive upper Banach density. Theorem 1 extends the Erdös sumset conjecture discussed in these previous posts, and answers a question (Question 6.3) raised in our previous paper with Richter and Robertson. Continue reading →

Posted in Combinatorics, Ergodic Theory, Number Theory, paper, Ramsey Theory | Tagged erdos, Erdos Cubes, Kra, Richter, Robertson, Sumsets | 2 Comments

Affine Images of Infinite sets

Posted on 01/05/2021 by Joel Moreira

— 1. Szemerédi’s theorem as affine images —

Szemerédi’s theorem is usually stated as “every set {A\subset{\mathbb N}} with positive upper density contains arbitrarily long arithmetic progressions”, but it can also be formulated without explicit mention of arithmetic progressions:
Theorem 1 (Szemerédi’s theorem, reformulated) Let {A\subset{\mathbb N}} have positive upper density, i.e.

\displaystyle \bar d(A):=\limsup_{N\rightarrow\infty}\frac{|A\cap\{1,\dots,N\}|}N>0.

Then for any finite set {F\subset{\mathbb N}} there is an affine transformation {\phi:x\mapsto ax+b} with coefficients {a,b\in{\mathbb N}} such that {\phi(F)\subset A}.

To see how this result implies Szemerédi’s theorem, note that for any affine transformation {\phi}, the set {\phi(\{1,2,\dots,k\})} is a {k}-term arithmetic progression.

Conversely, assuming Szemerédi’s theorem, given {A\subset{\mathbb N}} with {\bar d(A)>0} and a finite set {F\subset{\mathbb N}} let {k=\max F}, so that {F\subset\{1,\dots,k\}}. Then there is a arithmetic progression of length {k+1} contained in {A}, say {\{b,b+a,\dots,b+ka\}\subset A}. Letting {\phi(x)=ax+b} it follows that {\phi(i)\in A} for every {i\leq k} and in particular {\phi(F)\subset A}.

The advantage of formulating Szemerédi’s theorem in this form is that it readily allows for analogues in other settings. For instance, the multidimensional Szemerédi theorem of Furstenberg and Katznelson can be formulated as follows.

Theorem 2 (Multidimensional Szemerédi theorem, reformulated) Let {d\in{\mathbb N}} and let {A\subset{\mathbb N}^d} have positive upper density, i.e.

\displaystyle \bar d(A):=\limsup_{N\rightarrow\infty}\frac{|A\cap\{1,\dots,N\}^d|}{N^d}>0.

Then for any finite set {F\subset{\mathbb N}^d} there is an affine transformation {\phi:x\mapsto ax+b} with coefficients {a\in{\mathbb N}}, {b\in{\mathbb N}^d} such that {\phi(F)\subset A}.

Continue reading →

Posted in Analysis, Combinatorics, Ramsey Theory | Tagged Affine transformations, Bourgain, erdos, Szemeredi's theorem | Leave a comment

Additive transversality of fractal sets in the reals and the integers

Posted on 14/07/2020 by Joel Moreira

Daniel Glasscock, Florian Richter and I have just uploaded to the arXiv our new paper entitled “Additive transversality of fractal sets in the reals and the integers”. In this paper we introduce a new notion of fractal sets of natural numbers in analogy with {\times r}-invariant subsets of {{\mathbb T}={\mathbb R}/{\mathbb Z}}, and obtain the analogues of several results pertaining {\times r}-invariant subsets of {{\mathbb T}={\mathbb R}/{\mathbb Z}}.

The prototypical example of the kind of fractal subsets of {{\mathbb N}_0=\{0,1,2,\dots\}} that we deal with is the integer middle thirds Cantor set consisting of all {n\in{\mathbb N}_0} that when represented in base {3} use only the digits {0} and {2}. Symbolically

\displaystyle C_{\mathbb Z}:=\left\{\sum_{i=0}^na_i3^i:n\in{\mathbb N}_0, (a_0,\dots,a_n)\in\{0,2\}^{n+1}\right\}.

For comparison, the classical middle thirds Cantor set consists of all {x\in[0,1]} that when written in base {3} use only the digits {0} and {2}, and can be described symbolically as

\displaystyle C_{\mathbb R}:=\left\{\sum_{i=1}^na_i3^{-i}:n\in{\mathbb N}_0, (a_1,\dots,a_n)\in\{0,2\}^{n+1}\right\}.

Continue reading →

Posted in Combinatorics, Number Theory, paper | Tagged Furstenberg, Glasscock, Hochman, integer dimension, integer fractal, Lindenstrauss, Meiri, Peres, Richter, Shmerkin, transversality, Wu | Leave a comment

Multiple ergodic averages along functions from a Hardy field: convergence, recurrence and combinatorial applications

Posted on 14/06/2020 by Joel Moreira

Vitaly Bergelson, Florian Richter and I have recently uploaded to the arXiv our new paper entitled “Multiple ergodic averages along functions from a Hardy field: convergence, recurrence and combinatorial applications”. We establish a new multiple recurrence result (and consequentially a new generalization of Szemerédi’s theorem) which contains several previously known results as special cases and many new results.

An example of a result that follows as a special case from our main theorem but was currently unknown is that for any positive real numbers {a,b>0}, any set {E\subset{\mathbb N}} with positive upper density, i.e.

\displaystyle \bar d(E):=\limsup_{N\rightarrow\infty}\frac{|E\cap\{1,\dots,N\}|}N>0,

contains a configuration {\{x,x+\lfloor n^a\rfloor,x_\lfloor n^b\rfloor\}} for some {x,n\in{\mathbb N}}. Here, as usual, we denote by {\lfloor\cdot\rfloor} the floor function. This result was known when both {a} and {b} are integers, and when both {a} and {b} are non-integers, but the mixed case was, somewhat surprisingly, still unknown. Below the fold I briefly mention the history of related results and present the main steps in the proof, highlighting the main novelties.

Continue reading →

Posted in Combinatorics, Ergodic Theory, paper, Ramsey Theory | Tagged Bergelson, Hardy fields, nonconventional ergodic averages, Richter | Leave a comment

Distal systems and Expansive systems

Posted on 08/05/2020 by Joel Moreira

A topological dynamical system is a pair {(X,T)} where {X} is a compact metric space and {T:X\rightarrow X} is a continuous map. This gives rise to an action of the semigroup {({\mathbb N},+)} on {X}, where {n\in{\mathbb N}} acts via the iterated map {T^n=T\circ T^{n-1}} (and as usual {T^0} denotes the identity map). If {T} is invertible (i.e. a homeomorphism), then in fact it induces a {({\mathbb Z},+)}-action. More generally, one may consider an action {T=(T_g)_{g\in G}} of any semigroup {G} on {X} by continuous functions. This means that for each {g\in G} we have a continuous map {T_g:X\rightarrow X} which satisfy the semigroup law {T_g\circ T_h=T_{gh}}. In this case we say that {(X,T)} is a {G}-system. Throughout this post I will denote by {d_X} (or {d} if the underlying space is clear) a compatible metric on {X}.

Two important classes of topological dynamical systems are the class of distal systems and the class of expansive systems.

Definition 1

  • A {G}-system {(X,T)} is distal if

    \displaystyle \forall x,y\in X, \ x\neq y,\ \inf\big\{d(T_g x,T_g y):g\in G\big\}>0.

  • A {G}-system {(X,T)} is expansive if there exists {\delta>0} such that

    \displaystyle \forall x,y\in X, \ x\neq y,\ \sup\big\{d(T_g x,T_g y):g\in G\big\}>\delta.

While not entirely trivial, both properties are preserved by topological conjugacy (i.e., isomorphism in the category of {G}-systems), and in particular don’t depend on the choice of the (compatible) metric {d}.

At a first glance at the definition it looks like the two conditions are quite similar. They both fall into the loose statement that “if two points are distinct, then they are far apart in the future” (at least if the acting semigroup is {{\mathbb N}}). However, it turns out that the two properties are very much different, and in some sense actually incompatible.

In this post I will mention some examples and properties of distal and expansive systems which illustrate this difference between the two classes, and present a proof of the incompatibility result:

Theorem 2 An {{\mathbb Z}}-system which is both distal and expansive must be finite. The same is true for {{\mathbb N}}-systems.

It is clear that any finite system (i.e., where {X} is a finite set) is both distal and expansive.

EDIT (25/03/2024): Sebastián Donoso informed me that an example of Meyerovitch and Salo (Example 2.6 in this paper) shows that the analogue of Theorem 2 does not hold for general G-systems.

Continue reading →

Posted in Classic results, Topological Dynamics | Tagged Countable semigroups, distal, expansive | 2 Comments