# Hindman's Theorem, partial semigroups and some of my most lacking intuitions (part 1)

If you remember, I mentioned that I was working on a post on some research and it was getting out of hand. Well, it is still not finished, but long enough to start posting a series of posts.

It's no secret that I love the mathematical world surrounding Hindman's Theorem. Recently, I have been revisiting an old draft of mine. To get back into it, I want to jot down some informal notes about one of the research directions I think are worth pursuing -- even though I have no proof of this (pardon the pun). At the heart of this line of thought lies the notion of partial semigroups and, especially, my ideas for weaker forms of that notion. To fully make sense of it I have to take you from the elementary algebraic structures to less known structures to ultrafilters on those and finally to filters related to all of this.

But let me start at the beginning so that you can still enjoy reading a little bit of what I want to express without being lost after 5 minutes.

Hindman's Theorem is a typical Ramsey-type theorem, i.e., it tells us about a certain richness in some fixed mathematical structure (such as a graph in the original theorem by Ramsey), a richness which is partition regular:

Partition regular notions of richnessIf the structure is partitioned in to finitely many pieces (equivalently colored with finitely many colors), one piece (color) will have this kind of richness.

More concretely, Hindman's Theorem is about algebraic structures, namely, semigroups. Semigroups, if you don't remember, are simply sets with an associative operation

## semigroups? that's easy! subsemigroups!

If you are looking for partition regular notions and you meet a semigroup, you can, of course, ask yourself:

Are semigroups partition regular?

(Un)fortunately, that's not going to work.

To give you a counterexample, let's look at the natural numbers,

Ah, I just noticed: I have made a mistake. If you're a set theorist and

Oh well. But that's "clearly" not the point (especially if you're a set theorist). You'll most likely be interested in large, hopefully infinite structures -- and in any case, you're not interested in trivial solutions by idempotent elements...

To get back to our example, we'll ignore

## subsemigroup #Fail.

Subsemigroups have a nice property: they contain sets of 'multiples'. Given any element in the subsemigroup, we find all its 'multiples' since we can add it to itself repeatedly. Of course, for

If we have (thanks to the heading of this section) the suspicion that semigroups are not partition regular, we need to find a partition such that no part contains a set of multiples.

When I was lying in bed a couple of days ago, falling asleep but trying to put the ideas together for this post , it took me a while to come up with a partition. Since at the end I was actually asleep, I don't really remember how I got there. So I'm afraid I can't lead you to it, cannot communicate what intuitions about partitions of natural numbers came up in the process. If I would venture a guess, I probably just remembered the solution for a more complicated (i.e., weaker) structure. Not a grand revelation, I admit.

So how do we do this? Well, the thing about multiples is that they are evenly spaced. So if the parts of our partition have a large interval missing, say larger than some given number

So if we partition

we can do the following: Collect every other interval, i.e.,

and make

Then both

Now if we had a number in

In other words, for any given number, not all multiples lie in the same part of the partition, i.e., neither

## I'm not just messing with you

Now you can ask yourself if this hope for partition regular structures within semigroups was all but a dream and there's simply no algebraic structure that survives.

Luckily there's evidence dating back all the way to 1917 guaranteeing that at least *a tiny little bit* of algebraic structure will survive partitioning. Issai Schur proved that if you partition

It's not important, but the proof is quite simple actually, using Ramsey's Theorem (the original thing). Given a coloring of

, use that coloring to define a coloring of all unordered pairs of natural numbers: give (with ) the color of . By Ramsey's Theorem, there exists a homogeneous infinite set. Pick any three numbers in that homogeneous set. Then and all have the same color -- which solves our problem, since -- and notice how associativiy comes into play.

### Outlook

In the next post, I'll try to point out how far we can push this search for algebraic structures.