— 1. Introduction —
Previously on this blog I presented a proof of van der Waerden’s theorem which asserts that given a finite partition of , one of the cells of the partition contains arbitrarily long arithmetic progressions.
It turns out that actually each subset of 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 is defined by
It is easy to prove that given a finite partition partition of , 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 , one of the cells contain three numbers such that . However, in the set of odd numbers, which has density , no such 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 with by a non-zero integer , the resulting set no longer has the property that .
This brings us to the following conjecture (which turned out to be false) posed by Bergelson: If in every finite partition of one can find a “configuration” of some sort and if those configurations are invariant under translation, then every subset of with positive density contains one such configuration.
The notion of configuration here needs to be made more precise. Let be a family of finite subsets of (like the set of all finite arithmetic progressions, or the set of all such that ). We say that is translation invariant if for each and each , the finite set is also in . Thus the family of arithmetic progressions is translation invariant but the family of sets such that 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 be a translation invariant family of finite subsets of and assume that for any finite partition of , one of the cells contains a set in . Then each set with positive upper density also contains an element of .
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 with in some set. For instance the set of pairs for which is a square. More generally, given some set we can construct a translation invariant consisting of all pairs such that .
To say that “a set contains some element of ” is the same thing as “there are two elements of whose difference is in “, or equivalently ““. Thus every set with positive upper density contains an element of if and only if 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 be a probability space and be a measurable map such that for each measurable we have . Then if and there exists some such that
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 and topological dynamics (parallel to the relation between density results on and measure preserving systems). Pursuing this suggested relation, we define:
Definition 3 (Topologically recurrent set) A set is topologically recurrent if for every compact space , each continuous map which is minimal (i.e. there is no non-trivial compact subset such that ) and any open set there is some such that is non-empty.
Definition 4 (Chromatically intersective set) Let . A set is -intersective if in any partition of into cells, there are two elements on the same cell whose difference is in . Equivalently, if in any partition of into cells, one of the cells contains an element of the translation invariant family .
A set is chromatically intersective if it is -intersective for each . Equivalently if in any finite partition of there are two elements on the same cell whose difference is in , and also equivalently, if in any partition of , one of the cells contains an element of the translation invariant family .
It shouldn’t now be too surprising that those two notions coincide:
Proof: Let be a chromatically intersective set. Let be a minimal system and be open. The set is an open -invariant set, so its complement is a compact -invariant subset of . By minimality we conclude that . Because is compact there exists a finite set such that . Let be arbitrary and for each choose some such that . This induces a partition of . Since is chromatically intersective, there exist such that and and are in the same cell of the partition. In other words . From this we conclude that and also , so and therefore that intersection is non-empty.
To prove the other direction, assume now that is topologically recurrent and let be a finite partition of (the cells are the sets for each ). We can see as a point in the space . Let be the left shift, in other words we have that Give the product topology, this turns it into a compact space by Tychonoff’s theorem. Moreover the shift is continuous with respect to this topology.
Let be the compact set generated by , i.e. . 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 -invariant subsets of ), call it and let be arbitrary. The set is open, so for some we have . Let be some point in that intersection, then we have . Let be the neighborhood of defined by . Since , there is some such that and so for . In particular , so the two numbers and have the same color and the difference is in . We conclude that is a chromatically intersective set.
— 3. Kříž Theorem —
This lemma is the only tool we need to prove Kříž’ theorem:
As a corollary we get that the translation invariant family consisting of all pairs of positive integers such that is a counter-example for conjecture 1.
Proof:Let be large (to be determined later) and let be large primes to be also determined later. Let . Let . In what follows we don’t consider to be either even or odd. Let
We can explicitly count the cardinalities of and , and we get
It is not difficult to verify that if we make large enough, large enough and large enough we can make . Finally let
If and then let be the set of primes for which . Then and so for more than of those primes we have being odd. For each of those (more than ) primes we have being even, and thus . We just proved that and the same argument proves that as well.
Finally we need to verify that is a -recurrent set. Let be such that for exactly primes in and for all other . Given a partition of , it induces in particular a partition of . But has a natural bijection to the -subsets of , so by lemma 6 there exist in the same cell and such that for no prime in we have . For each of the at least primes in for which one of the we have . Thus and we conclude that is -recurrent. This finishes the proof.
Now we can finish the proof of theorem 7. The key observation to turn this finitistic version into Kříž theorem is that if is -intersective then for any , the set is also -intersective. To see this notice that given a partition of into colors, we can create a new partition by making and if have then and both .
Proof of theorem 7:
Fix . Let, for each , be a small real number to be determined later. Let be given by proposition 8applied to . Also let , and for . We will take . Since is a -intersective set, is an intersective set. Now note that each can be written uniquely as
with some and , the (finite) sequence are called the digits of . Let be the set of those such that the digit is either or belongs to . Thus the upper density . Moreover the are periodic, therefore the intersection has density .
Now let be the subset of those for which the number of digits in is even and let be the subset of those for which the number of digits in is odd. Then one of those subsets have upper density larger than . Let be that subset.
Now to conclude that , let , then for some we have , say and let , with digits . Note that both and are contained in , so we can add an element of with an element of digitwise.
If then and , so and thus . If (the same argument applies if it is in ) then and it’s not either. Now if , then and thus not in . We conclude that . Since this is the only digit in different from , we conclude that the parity of the number of digits in is changed from to , and thus . This finishes the proof.
This gives a nice corollary that disproves another conjecture.
Corollary 9 There exists some set with positive density and such that for any syndetic set we have ?
The proof follows from the observation that if is a syndetic set then must intersect any chromatically intersective set. Indeed by definition, a finite number of shifts of cover , so we can create a finite partition of such that each cell is contained in some shift of . This implies that the difference of two elements in the same cell is in , and therefore by the definition of chromatically intersective set, each such set intersects .
Now given any chromatically intersective set which is not intersective, there is some with positive density such that . By what we proved, for any syndetic set we have so if is syndetic we have .