Understanding the Central Sets Theorem18 Apr 2010
To write the first post on the new domain I thought I might just write a little about what I’ve been studying recently — the Central Sets Theorem.
This theorem dates back to the 70s and the original formulation and proof are due to Hillel Furstenberg. In its current form as found say in De, Hindman, Strauss (DOI) it is probably the strongest algebraic partition theorem around. I had encountered the theorem many times before, in books, lectures, papers and talks but I never truly developed an understanding for it. Since I recently felt it might give me an edge in a problem I’m working on I decided to take a better look.
Detour 1 — metamathematics
How do you achieve an understanding of a theorem? In an incomplete list I would include the following
- Understand its most important application or corollary
- Understand its statement
- Understand its proof
- Improve its proof
- Understand how to come up with the proof
- Give a different proof
- Improve the theorem
I would say this list is in increasing order of understanding but that’s open for discussion.
I might write about the history (and applications) of the Central Sets Theorem some other time, but here I want to focus on its formulation; in fact, I don’t even want to write about what it means to be central (sorry) except that it is a partition regular notion.
So, what does the usual formulation look like?
Central Sets Theorem
Imagine you are given finitely many sequences in a commutative semigroup , say as well as a central set .
Then you can find a sequence in as well as a sequence of non-empty, disjoint and finite subsets of such that for
Complicated, no? I mean, a random bunch of sequences, some strange set and you find some other sequence and some weird subsets of of the natural numbers and then the IP-set of some strange sums are in that strange set — ye what?
Let’s cut it down a little and just consider the case .
simple Central Sets Theorem
Imagine you are given a sequence in a commutative semigroup as well as a central set .
Then you can find a sequence in as well as a sequence of non-empty, disjoint and finite subsets of such that
Detour 2 — oversimplification
Even this special case of the standard formulation somehow focuses on aspects that get me sidetracked. So I attempted to formulate it in a way that gives (me) better focus.
Now, the theorem says all kinds of complicated things about the existence of a sequence of disjoint finite subsets of . Can I get around this? I thought I should be able to. Let’s start with a much weaker version of the theorem.
A weak simple Central Sets Theorem
Imagine you are given a subsemigroup as well as a central set .
Then you can find a sequence in as well as a sequence in so that
I find this weaker version much easier to understand. It just says that I can always translate infinitely many elements from a given subsemigroup into the central set; additionally the finite sums stay within the set.
This is much weaker than the statement before. Of course, given a sequence we could consider the generated subsemigroup and use the weaker version. But this would not guarantee the result of applying the Central Sets Theorem — Furstenberg’s theorem gives much more control over which elements are picked since there are no repititions in the sums of the generators.
So where does this leave us? Well, when I hear finite subsets of I think of my favourite structure — in fact the favourite structure for a lot of algebra in the Stone–Čech compactification on , the semigroup . But let’s step back a little. The best way to think about is in terms of partial semigroups.
(Adequate) Partial Semigroups
A partial semigroup operation on a set is a map such that associativity holds in the sense that if one side is defined so is the other and they are equal. A partial semigroup is adequate if the sets
generate a filter, i.e., finitely many elements have a common compatible element.
This notion was introduced by Bergelson, Blass and Hindman (DOI) in the 90s. It tells us that the operation, although partial, is associative in a strong way. Additionally, it makes sure the operation is not just empty but defined for many elements (well, ok it could be just one for all, but that’s not the point).
For ultrafilters the critical point is the following.
Given an adequate partial semigroup and ultrafilters containing all . Then the operation
is well-defined and associative and semi-continuous. In other words, is a closed semi-continuous semigroup.
Now this is somewhat surprising. Even though our operation is partial, these ultrafilters are a full semigroup! With all the bells and whistles it takes to do algebra in the Stone–Čech compactification.
What does this have to do with the Central Sets Theorem?
Denote the non-empty, finite subsets of by . Consider the restriction of on defined by
Then in fact this constitutes a partial semigroup, adequate at that.
This partial semigroup structure could be called the free partial semigroup in the following sense: given any sequence in any semigroup we can consider the induced partial semigroup on the set of finite sums : we only allow sums where the index sets are disjoint (so that we are closed under our partial operation). Then all -sets are naturally isomorphic (in the appropriate sense of partial semigroups).
The weak version revisited
To come back to the weak version of the Central sets theorem — partial semigroups are exactly what it talks about. So let us reformulate,
simple Central Sets Theorem
Imagine we are given a partial subsemigroup of as well as a central set . Then we find sequences in and such that and
Now this sounds much closer to the original theorem. Since any sequence generates a partial semigroup on its -set (isomorphic to ), this is in fact the Central Sets Theorem for just one sequence.
Leaving the simplification
However, the actual theorem is more than just some kind of induction on the above version. It is considerably stronger and here it is time to let go of the simplifications of partial semigroups again. For the theorem really does talk about -sets, i.e., partial semigroups isomorphic to . The strength lies in the fact that the infinite sequences can be chosen uniformly in the sense that we pick from the different partial semigroups in the same prescribed way.
Central Sets Theorem
Imagine you are given finitely many -sets in a commutative semigroup , say as well as a central set .
Then you can find a sequence in as well as one disjoint sequence in such that for all
To see this strength at work it is time to look at the classical application.
Central sets in contain arbitrarily long arithmetic progressions
Take to be the multiples of (for ). Then the central set theorem guarantees we find such that for all
For this application is obviously critical that the to-be-translated elements can be chosen uniformly. That’s all for now but I hope I can write a follow up some other time.