Hindman’s Theorem, partial semigroups and some of my most lacking intuitions (part 5)08 Sep 2011
Last time, I left you hanging – I promised the Central Sets Theorem, but only bothered you with some more stuff on partial semigroup, i.e., condensations. Let me make it up to you.
The Central Sets Theorems
So what is this mysterious theorem that, even though ergodic in origin is so close to the heart of algebra in the Stone–Čech compactification? It is not easy to formulate, but luckily I kept bugging you with and condensations, so we are well prepared.
Since there are many different versions of the theorem as it has been improved and generalized over the last 30 years, the most general formulations are quite something to process. As you might remember, this series started out as an expository piece, so let’s write down a very simple version first, even weaker than the very first version proved by Fürstenberg (but who knows, maybe that’s the version he first noticed). Remember that central sets are some kind of partition regular sets (that I haven’t even properly defined yet but who cares).
Central Sets Theorem (simple version) Let be a central set. Imagine I’m giving you some abitrary . Then you can find a and in such that
Just to repeat: if we set , then
This is quite odd, no? Even though the sequence has nothing to do with , the central set can “gobble it up”. As is to be expected, cannot “gobble it” up all of it, but there’s a full condensation that can be translated into in a rather peculiar fashion. Somehow, is able to reproduce a shifted version of the algebraic structure of the FS-set.
Well, it gets even better. The original theorem allows us to “iterate” this result in a strong way.
Central Sets Theorem (less simple version) Let be a central set. This time, I’m giving you finitely many . Not only can you get the above version for each sequence, but you can get them “together”:
You can find a single and a single in such that for all simultaneously
Again repeat: if we set , then for all
The crucial strength is that all the are constructed using the one fixed sequence of ’s – regardless of the given sequences! That’s crazy! Even though the sequences are completely unrelated, we will find condensations uniformly and translate by the same sequence of ’s.
Ok, maybe this difference is a bit subtle at first, but it is quite potent. For example, we immediately get van der Waerden’s Theorem!
van der Waerden’s Theorem (sort of) If is central and some given, we can find an an arithmetic progression of length in , i.e., there exists and such that
In fact, we can find the increment in any prescribed FS-set!
This last sentence is kind of cool: you want the increment to be a multiple of 10? 42? A gazillion? No problem!
Let’s derive this from the Central Sets Theorem. I know it’s a bit meaningless without having seen the proof of the Central Sets Theorem (which is, by the way, very elegant using ultrafilters and I hope I’ll get around to it)
Proof. Well, the “in fact” should be taken as a hint. So I give you some length for the arithemetic progression and as well as one FS-set, say ; you want to find an arithmetic progression in by some increment .
In other words, you’re trying to make work. The idea is to look at the sequences to apply the version of the Central Sets Theorem that allows for finitely many FS-sets.
What does it give you? Well, you get a lot of (a sequence/FS-/FP-set whatever, but let’s just take one of each) such that
for each – oh but that’s an arithmetic progression with increment , so we’re done!
Look at how much more we have, though. We can predescribe the FS-set to pick from, we get an FS-set (induced by the FP-set) we get an FS-set of starting points and so forth.
This was but a first taste. The Central Sets Theorem can be pushed much further. With some restrictions a central set can “gobble up” infinitely many FS-sets, it can be proved for commutative semigroups and, in a much more complicated version, for non-commutative semigroups. But we’ll stop here for now.