Topological recurrence versus measure recurrence; a theorem of Kříž

— 1. Introduction —

Previously on this blog I presented a proof of van der Waerden’s theorem which asserts that given a finite partition of {{\mathbb N}}, one of the cells of the partition contains arbitrarily long arithmetic progressions.

It turns out that actually each subset of {{\mathbb N}} with positive upper density contains arbitrarily long arithmetic progressions, and this is the famous Szemerédi’s theorem. Here, as usual, the upper density of a set {A\subset{\mathbb N}} is defined by

\displaystyle \overline d(A)=\limsup_{n\rightarrow\infty}\frac1n|A\cap[1,n]|

It is easy to prove that given a finite partition partition of {{\mathbb N}}, one of the cells must have positive upper density, so van der Waerden becomes a corollary of Szemerédi’s theorem.

A different situation happens with Schur’s theorem, which states that given a finite partition of {{\mathbb N}}, one of the cells contain three numbers {x,y,z} such that {x+y=z}. However, in the set {2{\mathbb N}-1} of odd numbers, which has density {1/2>0}, no such {x,y,z} exist (because of the trivial fact that the sum of two odd numbers is an even number).

One difference between this two cases lies in the fact that when we translate an arithmetic progression we get again an arithmetic progression, but when we translate a set {(x,y,z)} with {x+y=z} by a non-zero integer {a}, the resulting set {(x',y',z')=(x+a,y+a,z+a)} no longer has the property that {x'+y'=z'}.

This brings us to the following conjecture (which turned out to be false) posed by Bergelson: If in every finite partition of {{\mathbb N}} one can find a “configuration” of some sort and if those configurations are invariant under translation, then every subset of {{\mathbb N}} with positive density contains one such configuration.

The notion of configuration here needs to be made more precise. Let {S} be a family of finite subsets of {{\mathbb N}} (like the set of all finite arithmetic progressions, or the set of all {(x,y,z)} such that {x+y=z}). We say that {S} is translation invariant if for each {F\in S} and each {a\in {\mathbb N}}, the finite set {a+F:=\{a+f|f\in F\}} is also in {S}. Thus the family of arithmetic progressions is translation invariant but the family of sets {(x,y,z)} such that {x+y=z} is not. By a “configuration of some sort” we mean one element of a given translation invariant family. We now formulate Bergelson’s conjecture more rigorously:

Conjecture 1 Let {S} be a translation invariant family of finite subsets of {{\mathbb N}} and assume that for any finite partition of {{\mathbb N}}, one of the cells contains a set {F} in {S}. Then each set {A\subset {\mathbb N}} with positive upper density also contains an element of {S}.

We remark that an affirmative answer to this conjecture would reduce Szemerédi’s theorem to van der Waerden’s theorem. However this conjecture turns out to be false, even in a very weak case, and that’s the content of Kříž theorem.

Besides disproving Bergelson’s conjecture, Kříž theorem tells us that sets of recurrence for topological systems don’t need to be sets of recurrence for measure preserving systems.

— 2. Measure recurrent and topological recurrent sets —

One example of a translation invariant family is the family of all pairs {\{x,y\}} with {x-y} in some set. For instance the set of pairs {\{x,y\}} for which {x-y} is a square. More generally, given some set {R\subset {\mathbb N}} we can construct a translation invariant {S_R} consisting of all pairs {\{x,y\}} such that {x-y\in R}.

To say that “a set {A\subset{\mathbb N}} contains some element of {S_R}” is the same thing as “there are two elements of {A} whose difference is in {R}“, or equivalently “{(A-A)\cap R\neq\emptyset}“. Thus every set {A\subset{\mathbb N}} with positive upper density contains an element of {S_R} if and only if {R} is an intersective set, by definition. I previously dealt with such sets in this blog, for instance in this post. On that post I prove that intersective sets are also recurrent sets, and actually by Furstenberg’s correspondence principle, the two notions turn out to be the same.

By the same correspondence principle, to prove Szemerédi’s theorem it suffices to prove a statement about measure preserving systems, namely:

Theorem 2 (Furstenberg’s Multiple Recurrence Theorem) Let {(X,\mu)} be a probability space and {T:X\rightarrow X} be a measurable map such that for each measurable {A} we have {\mu(T^{-1}A)=\mu(A)}. Then if {\mu(A)>0} and {k\in {\mathbb N}} there exists some {n\in{\mathbb N}} such that {\mu(A\cap T^{-n}A\cap T^{-2n}A\cap...\cap T^{-kn}A)>0}

The deduction of Szemerédi’s theorem from this result was done in my previous post.

Similarly, one way to prove van der Waerden’s theorem, starts by reducing it to a statement about topological dynamics. This suggests a relation between partitions of {{\mathbb N}} and topological dynamics (parallel to the relation between density results on {{\mathbb N}} and measure preserving systems). Pursuing this suggested relation, we define:

Definition 3 (Topologically recurrent set) A set {R\subset {\mathbb N}} is topologically recurrent if for every compact space {X}, each continuous map {T:X\rightarrow X} which is minimal (i.e. there is no non-trivial compact subset {Y\subset X} such that {T^{-1}Y=Y}) and any open set {A\subset X} there is some {r\in R} such that {A\cap T^{-r}A} is non-empty.

Definition 4 (Chromatically intersective set) Let {k\in {\mathbb N}}. A set {R\subset{\mathbb N}} is {k}-intersective if in any partition of {{\mathbb N}} into {k} cells, there are two elements on the same cell whose difference is in {R}. Equivalently, if in any partition of {{\mathbb N}} into {k} cells, one of the cells contains an element of the translation invariant family {S_R}.

A set {R} is chromatically intersective if it is {k}-intersective for each {k}. Equivalently if in any finite partition of {{\mathbb N}} there are two elements on the same cell whose difference is in {R}, and also equivalently, if in any partition of {{\mathbb N}}, one of the cells contains an element of the translation invariant family {S_R}.

It shouldn’t now be too surprising that those two notions coincide:

Proposition 5 A set {R\subset {\mathbb N}} is chromatically intersective if and only if it is topologically recurrent.

Proof: Let {R} be a chromatically intersective set. Let {(X,T)} be a minimal system and {A\subset X} be open. The set {\bigcup_{\mathbb N} T^{-n}A} is an open {T}-invariant set, so its complement is a compact {T}-invariant subset of {X}. By minimality we conclude that {\bigcup_{\mathbb N} T^{-n}A=X}. Because {X} is compact there exists a finite set {F\subset{\mathbb N}} such that {X=\bigcup_{n\in F}T^{-n}A}. Let {x\in A} be arbitrary and for each {i\in{\mathbb N}} choose some {n_i\in F} such that {T^ix\in T^{-n_i}A}. This induces a partition of {{\mathbb N}}. Since {R} is chromatically intersective, there exist {i<j} such that {j-i\in R} and {i} and {j} are in the same cell of the partition. In other words {T^ix,T^jx\in T^{-n_i}A}. From this we conclude that {T^{i+n_i}x\in A} and also {T^{j+n_i}x=T^{j-i}(T^{i+n_i}x)\in A}, so {T^{i+n_i}x\in A\cap T^{-{j-i}}A} and therefore that intersection is non-empty.

To prove the other direction, assume now that {R} is topologically recurrent and let {x:{\mathbb N}\rightarrow[k]} be a finite partition of {{\mathbb N}} (the cells are the sets {\{i:x(i)=a\}} for each {a\in[k]}). We can see {x} as a point in the space {[k]^{\mathbb N}}. Let {T:[k]^{\mathbb N}\rightarrow[k]^{\mathbb N}} be the left shift, in other words we have that {(Ty)(i)=y(i+1)} Give {[k]^{\mathbb N}} the product topology, this turns it into a compact space by Tychonoff’s theorem. Moreover the shift {T} is continuous with respect to this topology.

Let {X\subset[k]^{\mathbb N}} be the compact set generated by {x}, i.e. {X=\overline{\{T^nx:n=0,1,...\}}}. We can now extract a minimal subsystem (this is achieved by the standard trick of applying Zorn’s lemma to the collection of all compact {T}-invariant subsets of {[k]^{\mathbb N}}), call it {\Omega} and let {\omega\in \Omega} be arbitrary. The set {A=\{y\in\Omega:y(0)=\omega(0)\}} is open, so for some {r\in R} we have {T^{-r}A\cap A\neq \emptyset}. Let {y} be some point in that intersection, then we have {y(0)=y(r)}. Let {U\subset X} be the neighborhood of {y} defined by {U=\{z\in X: z(i)=y(i)\text{ for all }i=0,...,r\}}. Since {y\in X}, there is some {n} such that {T^nx\in U} and so {(T^nx)(i)=y(i)} for {i=0,...,r}. In particular {x(n)=x(n+r)}, so the two numbers {n} and {n+r} have the same color and the difference is in {R}. We conclude that {R} is a chromatically intersective set. \Box

— 3. Kříž Theorem —

The proof we present is from this paper of McCutcheon (as well as the statement, which is in a slightly different form than that of Kříž’ original paper). We need a lemma, proved by Lovász

Lemma 6 Let {k,r\in {\mathbb N}} and let {T} be a set with {2r+k} elements. Let {D} be the family of {r}-element subsets of {T}. Then for any partition of {D} into {k} cells, there are two disjoint elements of {D} in the same cell.

This combinatorial result was conjectured by Krasner in 1955 and first proved by Lovász. A very short proof was found later by Bárány, but it builds on some other combinatorial results.

This lemma is the only tool we need to prove Kříž’ theorem:

Theorem 7 (Kříž) For every {\epsilon>0} there exists a chromatically intersective set {C\subset{\mathbb N}} and a set {A\subset {\mathbb N}} with upper density {\bar d(A)>\frac12-\epsilon} and such that {(A-A)\cap C=\emptyset}. In particular {C} is not intersective.

As a corollary we get that the translation invariant family {S_C} consisting of all pairs of positive integers {\{n,m\}} such that {|n-m|\in C} is a counter-example for conjecture 1.

The proof of theorem 7 is constructive and goes in two parts, first we need to prove a finitistic version, it is in this part that we need lemma 6. In what follows, and as usual, given {n\in{\mathbb N}} we denote {[n]=\{0,1,...,n\}}.

Proposition 8 For each {\epsilon>0} and {k\in{\mathbb N}} there are {N,M\in{\mathbb N}}, {A,B\subset[M(N-1)]} and {C\subset[M-1]} such that {A,B} and {C} are pairwise disjoint, {(A+C)\cap A=(B+C)\cap B=\emptyset}, and {\nu(A),\nu(B)>\frac12-\epsilon}, where {\nu} is the normalized counting measure on {[M(N-1)]}. Moreover, {C} is {k}-intersective and {0\notin C}.

Proof:Let {r,N\in{\mathbb N}} be large (to be determined later) and let {p_1,...,p_{2r+k}} be large primes to be also determined later. Let {T=\{p_1,...,p_{2r+k}\}}. Let {M=p_1...p_{2r+k}}. In what follows we don’t consider {0} to be either even or odd. Let

\displaystyle A=\{a:M\leq a<(N-1)M\text{ and }a\mod p_i\text{ is even for }<r\text{ indices and odd for all the other}\}

\displaystyle B=\{b:M\leq b<(N-1)M\text{ and }b\mod p_i\text{ is odd for }<r\text{ indices and even for all the other}\}

We can explicitly count the cardinalities of {A} and {B}, and we get

\displaystyle \nu(A)=\nu(B)=\frac{N-2}{N-1}\sum_{i=0}^{r-1}\binom{2r+k}i\frac1{2^{2r+k}}\prod_{j=1}^{2r+k}\frac{p_j-1}{p_j}

It is not difficult to verify that if we make {r} large enough, {p_i} large enough and {N} large enough we can make {\nu(A)=\nu(B)>\frac12-\epsilon}. Finally let

\displaystyle C=\{c:0< c<M\text{ and }c\mod p_i\text{ is }\pm1\text{ for at least }2r\text{ of the primes}\}

If {a\in A} and {c\in C} then let {T_c\subset T} be the set of primes {p} for which {c\equiv\pm1\mod p}. Then {|T_c|\geq2r} and so for more than {r} of those primes we have {a\mod p} being odd. For each of those (more than {r}) primes we have {a+c\mod p} being even, and thus {a+c\notin A}. We just proved that {(A+C)\cap A=\emptyset} and the same argument proves that {(B+C)\cap B=\emptyset} as well.

Finally we need to verify that {C} is a {k}-recurrent set. Let {D\subset [M-2]} be such that {D\equiv 2\mod p_i} for exactly {r} primes in {p_1,...,p_{2r+k}} and {p\equiv 1\mod p_i} for all other {p_i}. Given a partition of {{\mathbb N}}, it induces in particular a partition of {D}. But {D} has a natural bijection to the {r}-subsets of {T}, so by lemma 6 there exist {d_1,d_2\in D} in the same cell and such that for no prime in {T} we have {d_1\equiv d_2\equiv 2\mod p_i}. For each of the at least {2r} primes in {T} for which one of the {d_j\equiv 2\mod p_i} we have {d_1-d_2\equiv\pm1\mod p_i}. Thus {d_1-d_2\in C} and we conclude that {C} is {k}-recurrent. This finishes the proof. \Box

Now we can finish the proof of theorem 7. The key observation to turn this finitistic version into Kříž theorem is that if {C} is {k}-intersective then for any {x\in{\mathbb N}}, the set {xC} is also {k}-intersective. To see this notice that given a partition of {{\mathbb N}} into {k} colors, {{\mathbb N}=G_1\cup...\cup G_k} we can create a new partition by making {G_i'=\{n:xn\in G_i\}} and if {n,m\in G_i'} have {n-m\in C} then {x(n-m)=xn-xm\in xC} and both {xn,xm\in G_i}.

Proof of theorem 7:
Fix {\epsilon>0}. Let, for each {k\in{\mathbb N}}, {\epsilon_k=\frac\epsilon{2^k}} be a small real number to be determined later. Let {M_k,N_k,A_k,B_k,C_k} be given by proposition 8applied to {\epsilon_k}. Also let {n_1=1}, and {n_i=n_{i-1}M_{i-1}N_{i-1}} for {i>1}. We will take {C=n_1C_1\cup n_2C_2\cup n_3C_3\cup...}. Since {n_kC_k} is a {k}-intersective set, {C} is an intersective set. Now note that each {n\in {\mathbb N}} can be written uniquely as

\displaystyle n=n_1\alpha_1+n_2\alpha_2+...+n_l\alpha_l

with some {l\in {\mathbb N}} and {\alpha_i\in [M_1N_i-1]}, the (finite) sequence {\alpha_1,...,\alpha_l} are called the digits of {n}. Let {D_k} be the set of those {n} such that the digit {\alpha_k} is either {0} or belongs to {A_k\cup B_k}. Thus the upper density {\bar d(D_k)=\nu(A_k\cup B_k)>1-2\epsilon_k}. Moreover the {D_k} are periodic, therefore the intersection {D=\bigcap D_k} has density {\bar d(D)>1-2\sum\epsilon_k=1-2\epsilon}.

Now let {E_1\subset D} be the subset of those {n} for which the number of digits {\alpha_k} in {A_k} is even and let {E_2=D\setminus E_1} be the subset of those {n} for which the number of digits {\alpha_k} in {A_k} is odd. Then one of those subsets have upper density larger than {\frac12-\epsilon}. Let {A\in\{E_1,E_2\}} be that subset.

Now to conclude that {(A-A)\cap C=\emptyset}, let {c\in C}, then for some {k} we have {c\in n_kC_k}, say {c=n_kc_k} and let {a\in A}, with digits {\{\alpha_i\}}. Note that both {A_k+C_k} and {B_k+C_k} are contained in {[MN-1]}, so we can add an element of {A} with an element of {C} digitwise.

If {\alpha_k=0} then {\alpha_k+c_k=c_k\notin A_k\cup B_k} and {c_k\neq0}, so {a+c\notin D} and thus {a+c\notin A}. If {\alpha_k\in A_k} (the same argument applies if it is in {B_k}) then {\alpha_k+c_k\notin A_k} and it’s not {0} either. Now if {\alpha_k+c_k\notin B_k}, then {a+c\notin D} and thus not in {A}. We conclude that {a_k+c_k\in B_k}. Since this is the only digit in {a+c} different from {a}, we conclude that the parity of the number of digits in {A_k} is changed from {a} to {a+c}, and thus {a+c\notin A}. This finishes the proof. \Box

This gives a nice corollary that disproves another conjecture.

Corollary 9 There exists some set {W\subset {\mathbb N}} with positive density and such that for any syndetic set {S} we have {S-S\not\subset W-W}?

The proof follows from the observation that if {S} is a syndetic set then {S-S} must intersect any chromatically intersective set. Indeed by definition, a finite number of shifts of {S} cover {{\mathbb N}}, so we can create a finite partition of {{\mathbb N}} such that each cell is contained in some shift of {S}. This implies that the difference of two elements in the same cell is in {S-S}, and therefore by the definition of chromatically intersective set, each such set intersects {S-S}.

Now given any chromatically intersective set {A} which is not intersective, there is some {W\subset{\mathbb N}} with positive density such that {(W-W)\cap A=\emptyset}. By what we proved, for any syndetic set {S} we have {(S-S)\cap A\neq\emptyset} so if {S} is syndetic we have {S-S\not\subset W-W}.

This entry was posted in Ergodic Theory, Ramsey Theory, Topological Dynamics. Bookmark the permalink.

3 Responses to Topological recurrence versus measure recurrence; a theorem of Kříž

  1. Pingback: Bauer’s theorem and a coloring trick of Bergelson | I Can't Believe It's Not Random!

  2. Pingback: Piecewise syndetic sets, topological dynamics and ultrafilters | I Can't Believe It's Not Random!

  3. Pingback: I Can't Believe It's Not Random!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s