Tag Archives: andreas blass

One day in Colorado or Strongly summable ultrafilters are rapid

by

Picking up from the prelude about micro-contributions, let me tell you the story of a small result I would like to share with you. (Before you frantically scroll down to find the proof, it’s not really here but will be in the follow-up post).

Please keep in mind that this is not a mathematical paper (hm… did I really have to write this?). I’ll mostly delay (or forget) defining (or referencing) terminology. I hope my explanations will suffice when they are needed but this more of a story than a formal proof. In any case, if you find a notion that’s not defined, keep reading or ask for clarification through a comment.

Thankfully, Jana Flašková was kind enough to read through the draft correcting a few mistakes; fortunately, her recollection of this story does not greatly disagree with mine.

Results have stories, too

In 2010, I had the pleasure of visiting BLAST 2010 in Boulder, Colorado. It was a great experience (I wrote a couple of blog posts back then). One afternoon, I was sitting somewhere on campus with Jana Flašková and she asked me if idempotent ultrafilters could be rapid.

My initial reaction was “Of course not!”. My intuition said, rapid ultrafilters are just as bad as Q-points! they have too many gaps! they can’t be sums! But Jana insisted. And she was, of course, right. So let me take a step back and talk about these notions.

P-points, Q-points and sums of ultrafilters

Coming from set theory, one of the things that initially attracted me to (and annoyed me about) Algebra in the Stone-Čech compactification (of $\mathbb{N}$) was the fact that those ultrafilters on $\omega$ studied in set theory have (almost) no relevance in the field. The reason (usually) is that those ultrafilters (for example P-points and Q-points) cannot be sums of ultrafilters — and Algebra in the Stone-Čech compactification is all about sums of ultrafilters (well, or products if you work in an arbitrary semigroup).

This isn’t terribly surprising, in the sense that almost nothing is a sum of ultrafilters, i.e., it is well known that

Folklore (van Douwen?) $ \mathbb{N}^* + \mathbb{N}^* $ is nowhere dense in $ \mathbb{N}^*$ (the Stone-Cech remainder $ \beta \mathbb{N} \setminus \mathbb{N}$).

So from a Baire category point of view, you shouldn’t expect any ultrafilter to be a sum of ultrafilters.

But the reason goes deeper because the argument for this topological observations resembles arguments you frequently see for P- and Q-points. In fact, let’s see how you prove this folklore result:

  • consider a basic open set, i.e., take an infinite $A\subseteq \mathbb{N}$ and induce a basic open set $\hat A := \{ p \in \beta \mathbb{N}: A\in p\}$
  • thin out $A$ to an infinite $B \subseteq A$ with larger and larger gaps between the elements of $B$, i.e., such that $\lim_{n \to \infty} b_{n+1} – b_n = \infty$ (where the $b_n$ form the natural enumeration of $B$).
  • In other words, you make sure that $B$ has larger and larger gaps between its elements.
  • Then the induced open set $ \hat B $ misses all sums of free ultrafilters.

Why? Well, no sum of free ultrafilters can have a set with these kinds of increasing gaps. Instead, there will always be many small gaps. This simply is due to the natural base of a sum of ultrafilters:

  • A sum of ultrafilters $p+q$ has a base consisting of sets of the form $$\bigcup_{v\in V} v + W_v$$ where $V\in p$ and all the $W_v \in q$.

How does that base help produce small gaps?

  • Take $v_1 \neq v_2 \in V$
  • then $ W_{v_1} \cap W_{v_2} \in q$
  • But then $v_1 + (W_{v_1} \cap W_{v_2}) \cup v_2 + (W_{v_1} \cap W_{v_2})$ (a subset of our base set) will have infinitely pairs $v_1 +w, v_2+w$, hence infinitely many gaps of size at most $|v_2 – v_1|$.
  • In other words, no set in our base can be in a set with increasing gaps!

Ok, I drifted off topic for a minute. What you should take with you from this is that sums have sets that aren’t “thin” like $B$.

P-points, Q-points, for real this time

Now back to P-points and Q-points. Why can’t they be sums of ultrafilters? Guess what? They always contain “thin” sets!

For Q-points, this is relatively easy. Just look at the set $$ \bigcup_{n\in \omega} [10^{2n}, 10^{2n+1}).$$

or its complement, whichever is in our Q-point -- they do look very much alike. A Q-point, by definition, can turn any finite-to-one function into a one-to-one function on a set in the Q-point. The above partition can be viewed as the finite-to-one function answering "which interval do you lie in?". But a set where this function is one-to-one, well, such as set shares at most one point with each interval -- hence such a set has $\lim a_{n+1} - a_n = \infty$.

For P-points the argument is different and I hesitate to put it here -- it might do more harm than good since it's unimportant in what follows. But I guess you can decide for yourself if you'd rather skip it.

Take a set $A$ in a P-point; let's enumerate it again naturally by $ ( a_n : n \in \omega) $. Now define a map $ f: A \rightarrow \mathbb{N} $ by $$ f(a_n) = (a_{n+1} - a_n) .$$ In other words, by the size of the gap following $ a_n $.

Since we're dealing with a P-point, there's an ultrafilter set $B\subseteq A$ such that $f$ restricted to $B$ is finite-to-one or constant.
It can't be constant, since either $ \bigcup_{n\in \omega} [10^{2n},10^{2n+1})$ or its complement is in our P-point. So it's finite-to-one -- and this should be enough to verify that our set $B$ has $ \lim_{n \to \infty} b_{n+1} - b_n = \infty$, right?
Ok, let's take a look. After finitely many steps, the differences will be larger than any prescribed bound (just be careful here, because our function $f$ compared $a_n$ with $a_{n+1}$, while here we compare $b_n$ with $b_{n+1}$ which is not the "successor" in $A$, but in $B$ -- but that isn't a problem since the "successor" in $B$ is at least as far away as the successor in $A$). (Hm... there should be an easier argument, maybe? (and less need for parantheses?))

Anway, I hope I've given some evidence to the claim that the usual crowd of set theoretically interesting ultrafilters turn out to be incompatible with the idea of a sum of ultrafilter. That's somewhat annoying, wouldn't you agree?

Back to our story

So sitting in the shade by a pond on a sunny day in Colorado, Jana asked me this question: can idempotent ultrafilters be rapid? And I answered that I wouldn't expect there to be rapid idempotents because the set theoretic properties (rapidity in this case) never turn out to be possible for sums because they would have too many gaps. But Jana replied "yes, they have gaps -- but they do not have to have gaps everywhere!"

At this point, I should probably explain what a rapid ultrafilter is, shouldn't I? It's quite easy, really.

If you identity a subset $ A\subseteq \mathbb{N} $ with its natural enumeration $n\mapsto a_n$ (as hopefully, you're willing to do at this point), a rapid ultrafilter is simply a (free) ultrafilter that happens to be a dominating family (in $\mathbb{N}^\mathbb{N}$), i.e., a cofinal family in the partial order $$f\leq^* g \text{ iff } f(n)\leq g(n) \text{ for all but finitely many } n.$$ (Since rapid ultrafilters are required to be free, we can drop the "all but finitely many" since we could modify our infinite sets to dominate everywhere but "almost everywhere" is the usual partial order.)

You could try and check that Q-points are always rapid, but there's a small trick, a change of perspective, a different characterization of Q-points that might trip you up -- oh, and the reverse is not always true.

So you see, given any function $f:\mathbb{N} \rightarrow \mathbb{N}$, we find a set $A$ in the rapid ultrafilter, such that $f(n)<a_n$ for all $n$ (and assuming the $a_n$ again form the natural enumeration).

Now, I wasn't completely wrong that rapid ultrafilters must have huge gaps -- just imagine a set dominating the Ackermann function or an incomputable function that dominates all computable functions!

But the point Jana was making is that even though for every function $f$ we need a set $A$ dominating $f$, it could "take a break" from dominating. That is, $a_n$ could be much bigger than $f(n)$, say it could be bigger than $f(2^n)$ -- and suddenly $a_{n+1}$ can be very close to $a_n$, no need for a gap at all!

So we sat in the Colorado sun and I thought (idealizing my memory ever so slightly here) if there's any chance for a rapid idempotent ultrafilter, then we must be able to construct a strongly summabe ultrafilter that is rapid.

Strongly summable ultrafilter FTW!

What are strongly summable ultrafilter, you ask? Well, I've written plenty about FS-sets, but it never hurts to repeat. FS-sets are simple: Take a sequence $(x_n)_{n\in \omega}$ in $\mathbb{N}$ and then take all finite sums of the $x_i$ -- but no repetitions allowed! More formally,

$$ FS(x_n) := \{ \sum_{i\in s} x_i : s \in [\omega]^{<\omega}, s \neq \emptyset \}.$$

Now a strongly summable ultrafilter is an ultrafilter that has a base of such FS-sets, i.e., every set in the ultrafilter contains an FS-set which is also in the ultrafilter. The last part is really the key. The Galvin-Glazer Theorem tells us that any idempotent ultrafilter has the property that any set in it, contains an FS-set — but the FS-set will not (in general) be in the ultrafilter! So strongly summable ultrafilter are very special that way. (Another way they are special is that they were the first and still the most important type of idempotent ultrafilters whose existence is independent of ZFC.) They are the purest idempotents if you like which often makes them the simplest to deal with.

Quick and dirty with CH

Why would I think that, if anything, I should try and build a strongly summable ultrafilter that is rapid? The reason is quite naive, really: given a function, we can choose an FS-set to dominate it with. At first, this doesn’t seem obvious. Sure, the generating sequence can easily be chosen to dominate any given function — but then all these sums come in and who knows what might happen?

Luckily, we know precisely what happens!

Imagine we have been given the generating sequence $(x_n)$, with larger and larger gaps. The only problem for the set $FS(x_n)$ appears after each $x_k$ — it is followed by the translates of $ x_k $ by sums of elements below $ x_k $ before we (presumably) have another big jump to $x_{k+1}$. So yes, there’s a problem — lots of elements close together — but we know how many elements are problematic before the next jump, $2^k$-many!

In other words, given some (strictly monotone) $f$ we replace it with $f \circ 2^n$ (see what I did there?). Then pick a sequence $(x_n)_{n\in \omega}$ dominating $f\circ 2^n$ — lo and behold, $FS(x_n)$ will still dominate $f$!

After this thought came up in my discussion with Jana, the initial argument was easy: just assume CH and build a strongly summable ultrafilter that is rapid by the usual transfinite induction!

Lunch break is over

The story continues, fortunately enough. After all, the title of this post indicates that all strongly summable ultrafilters are rapid, not just that I could construct one. How did we continue?

After our little proof in the park, I went to a talk and sat down next to Andreas Blass, my supervisor at Michigan. I told him about this fun question and the initial result that under CH some strongly summable ultrafilters are rapid.

I don’t remember who was giving the talk but I feel like I must apologize since I might have caused Andreas not to pay enough attention — right after the talk Andreas told me that he’d just shown that, in fact, an important class of strongly summable ultrafilters is rapid (iirc, he showed that all stable ordered union ultrafilters are rapid, but let’s not go there). This clear improvement in turn boosted my interest in re-claiming the result and later that day I found an argument that all strongly summable ultrafilters are rapid.

But here is a good point to stop the first post. In the second post, I will give the argument and an additional observation which proved to be far too easy.

I hope you enjoyed this a little. I think it is a common theme for small results: If you’re an expert in your area (however small that area might be), there are a ton of question that you simply won’t think of but nevertheless can answer relatively quickly. Sometimes, I get the feeling that I should be a little ashamed of such results. They come to quickly. There’s a meme in popular culture that mathematics has to be produced “the Wiles way”, in secret, laboring for years. We all know that’s not accurate at all, but I think some of us prefer to leave that impression. After all, if the argument is sufficiently transparent, it’s often hard to tell if took a short or a long time.

Anyway, stay tuned for part 2.

Flat Ultrafilters (Michigan Logic Seminar Sept 21, 2011)

by

Remember how our about page says that Booles’ Rings is about best practices for an acacdemic homepage? Ok, let’s try one: making notes to talks available.

Some introductory remarks

Skip this section if you only want mathematics.

Wednesday, I gave a short talk about flat ultrafilters at our Logic Seminar here at the University of Michigan (as announced on Set Theory Talks, the talk was recorded and the video will be online eventually is now online).

Flat Ultrafilters (2011/09/21 University of Michigan Logic Seminar) from Peter Krautzberger on Vimeo.

When I visited Toronto in June, Ilijas Farah introduced me to this somewhat strange new type of utrafilter on $\omega$. My talk this week was mostly about the results from a 2009 paper by Ilijas Farah, N. Christopher Philips and Juris Steprans [cite source='doi']10.1007/s00208-009-0448-z[/cite], but some of what I am going to write are insights I gained while discussing this notion with François Dorais and Andreas Blass. So, actually, this post is attempting another best practice: notes from reading a paper.

I would like to explain something about the result that P-points are not flat. When I started looking at their paper with Francois Dorais, we first re-proved that selective ultrafilters are not flat — instead of the (possibly stronger) functional analytic result from the paper we used the combinatorial definition of flat ultrafilters. Then we worked on improving that proof and, with Andreas’s help, got it to work for P-points.

Only after all of this happened did we notice that at the very end, the paper had already announced that they have a proof that P-points are not flat. Last week, Ilijas kindly send me some slides with further results on flat ultrafilters; even though the proof for P-points isn’t in there I would guess from the formulation on the slides that our proofs are essentially the same.

Long story short, the proof “P-points are not flat” below is “our” proof even though the result (and most likely the proof) should be credited to at least Steprans (according to the slides).

I will focus on my own interpretation of these notions, i.e., my rephrasing of the definition of flat ultrafilters; they might look different from what you’ll find in their paper even though it is formally the same notion.

Alright, nuff said. My talk was designed to first sketch the main functional analysis result of their paper. So the first two sections will be void of much explanations or proofs. But they motivate why the notion of flat ultrafilter is as strange as it is — it simply came out of those considerations.

Some functional analysis

Let $H$ be a (the) separable, infinite dimensional Hilbert space, i.e., $$H\cong l_2(\omega) = \{ s: \omega \rightarrow \mathbb{C}, \sum_{n\in \omega} |s_n|^2 < \infty \}.$$

Then $B(H)$ is the space of bounded, linear operators, i.e.,

$$ B(H) = \{ T: H\rightarrow H: T \mbox{ linear }, (\exists M)(\forall v\in H) ||Tv|| \leq M||v|| \},$$

and $K(H)$ the space of compact operators

$$K(H) = cl( \{ T \in B(H): T[H] \mbox{ finite dimensional } \}).$$

Finally, the Calkin Algebra is the quotient $C(H) = B(H) / K(H)$.

Farah, Philips and Steprans were interested in the relative commutant of subalgebras $A\subseteq B$: $$F_A(B) = \{ a\in A: (\forall b\in B) ab=ba \}.$$

The relative commutant in the ultrapower

If $p \in \beta \omega $ is an ultrafilter, we can consider the norm-ultrapowers of $B(H)$ and $C(H)$ which I’ll denote by $B(H)^p, C(H)^p$. That is $$ B(H)^p = \ell_\infty(B(H) / \{c \in \ell_\infty(B(H)): \lim_p ||c|| = 0\}.$$ (Similarly for $C(H)^p$.)

Kirchberg had shown that $F_{C(H)^p}(C(H)) = \mathbb{C} \cdot 1$ regardless of $p$ and asked it the analogous statement might be true of $B(H)$.

As a response, Farah, Philips and Steprans showed that $F_{B(H)^p}(B(H))$ depends on the choice of $p$ (under CH); the results from their paper relevant to this talk are as follows.

Theorem (Farah, Philips, Steprans)

  • If $p$ is a flat ultrafilter (see below), then $F_{B(H)^p}(B(H)) \neq \mathbb{C} \cdot 1$.

  • If $p$ is selective, then $F_{B(H)^p}(B(H)) = \mathbb{C} \cdot 1$; in particular, selective ultrafilters are not flat.

  • Flat ultrafilters exist under ZFC.

  • It was announced that P-points are not flat.

Curious fact: under CH all ultrapowers of $B(H)$ are isomorphic (via model theoretic arguments). Yet, by the above, if we take a flat and a selective ultrafilter, no such isomoprhism can map $B(H)$ to $B(H)$ (or else the relative commutants would be isomorphic). This is an odd situation.

If you look at the recording you will, as usual, see lots of confusion on my part. In particular, I remembered that the first result in the theorem was an equivalence. It turned out that the paper does not say so and this is an open question. In my defence, the slides did give it as an equivalence.

I’ll only give the proofs of the last two statements as well as some further observations on flat ultrafilters.

Flat ultrafilters

What are flat ultrafilters? Well, let’s first introduce the assisting structure of a flatness scale, a set of sequences in $[0,1]$.

Definition
A flatness scale H is a countable subset of $$\{ h:\omega \rightarrow [0,1]: h(0) =1, \lim_{i \rightarrow \infty} h(i)=0 \}.$$

Addendum Nothing spectacular so far — a flatness scale is just a bunch of sequences converging to $0$. As such they can have some wild behavior along the way — but flat ultrafilters tame them.

The original definition of flat ultrafilters is then phrased as follows.

Definition [Farah, Philips, Steprans]
An ultrafilter $p$ is flat if there is a flatness scale $H = (h_n: n\in \omega)$ such that for every increasing $f: \omega \rightarrow \omega $ with $f(0) > 0$
$$\lim_{n\to p} ||(h_n – h_n \circ f)||_\infty = 0.$$
In other words, for every $f$ as above and every $\varepsilon>0$, we have $$\{n\in \omega: \sup_i |h_n(i) – h_n(f(i))| < \varepsilon \} \in p .$$
We then say that $H$ is a flatness scale for p.

One of the goals was to find out how I can best think about the notion of flat ultrafilters.

Addendum What to make of this? The first observation is that flat ultrafilters have a flatness scale such that, given $\varepsilon$, almost all of the sequences (with respect to the ultrafilter) drop by at most $\varepsilon$. That’s slow, but it’s even slower! The functions $f$ in the definition should be thought of as vastly increasing (think: dominating family) and they code huge intervals of the form $[n,f(n)]$. But even given those vast intervals, still almost all sequences of the flatness scale drop only by $\varepsilon$ on such long intervals. In other words, they never really drop by much, yet they converge to $0$.

One of the things I found irritating was to think of them as ultrafilters on $\omega$. Thankfully, the enumeration of $H$ does not matter much. In other words, I don’t have to think of $p$ as an ultrafilter on $\omega$ that just happens to come with a map to a flatness scale $H$ — I can really think of $p$ to be an ultrafilter on $H$. So allow me to re-phrase.

Definition [reformulation] Given a flatness scale $H$ and an ultrafilter $p$ on $H$, we say that $p$ is flat, if for every increasing $f:\omega\to\omega$ with $f(0) > 0$ and every $\varepsilon>0$, $$\{ h \in H: \sup_i |h(i) – h (f(i))| < \varepsilon \} \in p .$$
In other words, $$\lim_{p} ||(h – h \circ f)||_\infty = 0.$$ Here $\lim_p$ is the usual limit along the ultrafilter $p$.

You might wonder if we’re not loosing too much information — after all, the original definition did not forbid repititions. We’ll see later that this is not a problem. For now, I will simply stick to the reformulation.

First there’s an obvious question about how complicated a flatness scale can be. So let me show you their construction of flat ultrafilters.

Constructing Flat Ultrafilters

A simple observation

For the construction of flat ultrafilters, the key observation is as follows: all we have to do is find a flatness scale $H$ such that the sets $$X_{f,\varepsilon} = \{h \in H : \sup_i|h(i) – h (f(i)| < \varepsilon \}$$
are infinite for every increasing $f:\omega\to\omega$ with $f(0) > 0$ and every $\varepsilon > 0$.

Once we have this, we get the finite intersection property for free since $$X_{\max(f_1,f_2),\min(\varepsilon_1,\varepsilon_2)} \subseteq X_{f_1,\varepsilon_1} \cap X_{f_2,\varepsilon_2}.$$

In other words, any ultrafilter $p$ containing all the sets $X_{f,\varepsilon}$ is flat — witnessed by the flatness scale $H$.

Luckily, It turns out that there is an extremely simple flatness scale with this property.

Proposition [Farah, Philips, Steprans] There is a flatness scale $H$ such that the set
$$X_{f,\varepsilon} = \{h \in H : \sup_i |h(i) – h(f(i)| < \varepsilon \}$$
is infinite for every increasing $f:\omega\to\omega$ with $f(0) > 0$ and every $\varepsilon > 0$.

Proof

  • Consider the finite subsets of $\omega$, $[\omega]^{<\omega}$.

  • We can think of $s\in [\omega]^{<\omega}$ as encoding a simple step function, dropping by $1/|s|$ at each of the elements of $s$; in other words, we define $h_s : \omega \rightarrow [0,1]$ by
    $$ h_s(i) = 1- \frac{|s\cap i|}{|s|}.$$

  • Clearly, $H_S := \{ h_s: s \in [\omega]^{<\omega} \}$ is a flatness scale (starting at $1$ and converging to zero, in fact being eventually zero).

  • Now imagine we’re given some increasing $f:\omega\to\omega$ with $f(0) > 0$ as well as some $\varepsilon >0$.

  • Then we can easily find infinitely many $s \in [\omega]^{<\omega}$ with the following properties:
    • $1/|s| < \varepsilon$
    • With the natural enumeration of $(s_i)_{i\in |s|}$ of $s$, $$s(i+1) \geq f(s(i))$$ for each $i < |s|$.

  • But this means that for all $i$, $$h_s(f(i)) \geq h_s(i+1) = \frac{1-|s\cap (i+1)|}{|s|}.$$

  • It follows that $\sup_i |h_s(i) – h_s(f(i))| \leq 1/|s| < \varepsilon$.

  • Since we can find infinitely many such $s$, the sets $X_{f,\varepsilon}$ are all infinite.

Combining this with the previous observation we have.

Corollary (Farah, Philips, Steprans)
There is a flat ultrafilter via the above flatness scale $H_S$. (Let’s keep that name.)

Some easy observations

Let’s try to get a feel for what we can actually expect from a flat ultrafilter.

For example, a flat ultrafilter must be non-principal — otherwise the flatness scale is just one map and it’s easy to find $f:\omega \rightarrow \omega$ that drops faster than a single sequence $h$!

Flatness scales are simple

The above results from Farah, Philips and Steprans is surprising: at first since the flatness scale is extremely simple! It’s only natural to ask how complicated flatness scales can really be. Luckily, it’s always this easy!

Proposition If $p$ is flat, then $H_S$ as above is a flatness scale for $p$.

Proof

  • Assume we have a flatness scale for $p$, say $H = (h_n: n\in \omega)$ with some fixed enumeration of $H$.

  • We can define another flatness scale as follows: simply choose $h’_n(i)$ to be a multiple of $1/n$ closest to $h_n(i)$, i.e., minimize $|h_n(i) – j/n|$.

  • Clearly, $h’_n \in H_S$.

  • Then $(h’_n : n\in \omega)$ (and hence $H_S$) is a flatness scale for $p$!
    • For $f,\varepsilon$ as in the defintion for flatness, we know $$\{ n: \sup_i |h_n(i) – h_n(f(i)| < \varepsilon / 3 \} \in p.$$
    • But $|h’_n(i) – h’_n(f(i))| \leq | h_n(i) – h_n(f(i)| + 2/n$.
    • Since all but finitely many $n$ have $1 / n < \epsilon / 3$ we have $$\{ h_n: \sup_i |h’_n(i) – h’_n(f(i)| < \varepsilon \} \supseteq^* \{ h_n: \sup_i |h_n(i) – h_n(f(i)| < \varepsilon / 3 \}.$$
    • In other words, both sets lie in $p$ — as desired.

The above proposition tells us that we can now think of flat ultrafilters as simply living on $[\omega]^{<\omega}$, extending a certain filter — I don’t know about you, but for me that’s much easier to picture. We can, therefore, re-phrase our definitions.

Definition revisited. An ultrafilter $p\in \beta( [\omega]^{<\omega}) \cong \beta \omega$ is flat if for all $f:\omega \rightarrow \omega$ with $f(0)>0$ and $\varepsilon>0$,
$$\{ s \in [\omega]^{<\omega}: \sup_i |h_s (i) – h_s(f(i))| < \varepsilon \} \in p .$$

We’re still sort of hiding the fact that we can vary the bijection between $[\omega]^{<\omega}$ and $\omega$. But I still think this phrasing simplifies things a little.

Convergence in the colums

The next important observation is that in each coordinate $i$, the values of the flatness scale at $i$ for a flat ultrafilter must converge to $1$ (along the ultrafilter).

Lemma If $p$ is flat, then $\lim_{s\rightarrow p} h_s(k) = 1$ for all $k \in \omega$.

Proof

  • Suppose $\lim_{s\to p} h_s(k) < 1 – \varepsilon$ for some $k \in \omega$ and $1> \varepsilon > 0$.

  • In other words, $X := \{ s: h_s(k) < 1 – \varepsilon \} \in p$.

  • Pick some $f:\omega\to\omega$, increasing with $f(0) = k$ (note $k > 0$ since $h_s(0) = 1$).

  • Then
    $$ \sup_i|h_s(i) – h_s (f(i)) | \geq |h_s(0) – h_s(k)| = 1 \geq \varepsilon $$
    for every $n \in X$.

  • In other words, $ X \subseteq \{ s \in [\omega]^{<\omega}: \sup_i |h_s (i) – h_s(f(i))| \geq \varepsilon \}$

  • But this contradics $\{ s \in [\omega]^{<\omega}: \sup_i |h_s (i) – h_s(f(i))| < \varepsilon \} \in p$.

A proof that P-points are not flat.

In their paper Farah, Philips and Steprans announced that P-points are not flat. Francois, Andreas and I overlooked that statement and re-proved the result as follows. (See also the comments at the beginning as well as later.)

Suppose for this section that $p$ is a flat $P$-point as witnessed by $H_S$.

As the first step, we will improve the p-convergence from earlier to actual convergence, i.e., $p$ contains $H\subseteq H_S$ that satisfies $\lim_{s\in H} h_s(k) = 1$ for every $k$.

In the second step, we will show that no ultrafilter can have such a flatness scale.

Lemma If $p$ is a flat P-point, then $p$ contains $H\subseteq H_S$ that satisfies $\lim_{s\in H} h_s(k) = 1$ for every $k$.

Proof

  • Since $\lim_{s\to p} h_s(k) = 1$ for all $k$ we know that $$X_{k,l} := \{ s: h_s(k) \geq 1 – 2^{-l} \} \in p,$$ for all $k,l \in \omega$.
  • Since $p$ is a P-point, we find $H \in p$ such that $H \subseteq^* X_{k,l}$ for all $k, l \in \omega$.
  • But that means precisely that $H$ has $\lim_{s\in H} h_s(k) = 1$ for every $k$.
  • Of course, restricting to $H$ does not change the fact that $$\lim_{n\to p} \sup_i|h_s(i) – h_s(f(i))| = 0$$ holds for every increasing function $f:\omega\to\omega$ with $f(0) > 0$ — so we’re done.

We may thus suppose that our original flatness scale satisfies $\lim_{n\to\infty} h_n(k) = 1$ for every $k$. But this is impossible for any ultrafilter!

Lemma No ultrafilter $p$ has a flatness scale $H$ with $\lim_{h\in H} h(k) = 1$.

Proof.

  • Else, for any fixed $\color{red}k$, there are only finitely many $\color{blue}h$ such that $h(k) < 3/4$.

  • For these finitely many $\color{blue}h$, there is a common $\color{yellow}\ell$ (depending only on $\color{red}k$) such that $\color{blue}h(\color{yellow}\ell) = 0$, and thus $h(m) =0$ for all $m \geq \color{yellow}\ell$.

  • In other words, we can define $\color{yellow}f:\omega\to\omega$ be an increasing function with $\color{yellow}f(0) > 0$ such that if $h(k) < 3/4$ then $h(\color{yellow}f(k)) = 0$.

  • Since $H$ is a flatness scale, we have that $$\{h : (\forall k)(h(k) – h(\color{yellow}f(k)) \leq 1/4)\} \in p.$$

  • So pick one of those $\color{blue}h$, i.e., with $\color{blue}h(k)-\color{blue}h(\color{yellow}f(k)) \leq 1/4$ for all $k$.

  • For this fixed $\color{blue}h$ we can, of course, find the first $\color{red}k$such that $\color{blue}h(\color{red}k) < 3/4$. (Note that $\color{red} k > 0$ since $\color{blue}h(0) = 1$.)

  • Since $\color{blue}h(\color{red}k-1) \geq 3/4$ and $\color{yellow}f(\color{red}k-1) \geq \color{red}k$, we see that $$\color{blue}h(\color{blue}k-1) – \color{blue}h(\color{red}k) \leq \color{blue}h(\color{red}k-1) – \color{blue}h(\color{yellow}f(\color{red}k-1)) \leq 1/4$$ by our choice of $h$.

  • Therefore, $\color{blue}h(\color{red}k) \geq 1/2$.

  • By choice of $\color{yellow}f$, we have that $\color{blue}h(\color{yellow}f(\color{red}k)) < 1/4$ and hence $\color{blue}h(\color{red}k) – \color{blue}h(\color{yellow}f(\color{red}k)) > 1/2 – 1/4 = 1/4$ — which contradicts our choice of $h$!

Flat ultrafilter and rapidity

Since selective ultrafilters are not flat, I was for the longest time under the impression that Q-points and, more generally, rapid ultrafilters might be connected.

(Un)fortunately, this is not the case. An easy argument yields flat but rapid ultrafilters.

Proposition If $p$ is flat and $p \leq_{RK} q$, then $q$ is flat. By contraposition, if $q$ is not flat, then $p$ is not flat.

Proof

  • If $H_S$ is a flatness scale for $p$ and $g:[\omega]^{<\omega} \rightarrow [\omega]^{<\omega}$ with $g(q)=p$, then $H_{g[S]}:=\{ h_{g(s)} :s \in \omega^{<\omega} \}$ is a flatness scale for $q$.
    • Given $f$ and $\varepsilon$, simply calculate $$\{ s : \sup_i |h_{g(s)}(i) – h_{g(s)}(f(i))| < \varepsilon \} = g^{-1} [ \{ s : \sup_i |h_s(i) - h_s(f(i))| < \varepsilon \}] \in q. $$

This is all we need.

Proposition If there exists a rapid ultrafilter, there exists an ultrafilter both flat and rapid.

  • Take $p$ rapid, and $q$ flat.
  • Then $q \otimes p$ is rapid and flat
    • Flat, since $q\otimes p \geq_{RK} q$.
    • By a folklore exercise, if $p$ is rapid, then any $q\otimes p$ is rapid.

That’s about all I actually covered in my talk. There might be a continuation at a later point.

2011/09/29 I added some badly drawn pictures and additional comments (preceded by “Addendum”)

Supervisor Precognition

by

I am currently working on a nice little proof. I was initially very confident that I could find the proof — mostly because I already gave a different proof for the same observation, albeit with completely different tools.

This time around the proof will probably end up as a series of stronger and stronger lemmas. Already 3 weeks ago I thought I had shown the strongest intermediary lemma I have formulated so far. Unfortunately, Andreas shot it down, then I found a different proof, and Andreas shot it down again, then I found another proof, and Francois shot it down. As painful as this sounds (and really, really is), I am so lucky to have such colleagues.

Finally, I think I have a found a proof for the intermediary lemma that will live (well, maybe I should wait until Francois sees it later today…). The creepiest thing about this proof, however, is Andreas’s precognition.

When I showed him the failed second attempt (which failed pretty much at line 1…), we discussed the phenomena involved and Andreas made two comments about the problem itself. The first was that due to the setting, an indirect proof seemed to him to be the way to go; second, he gave a very simple example, a special case of the problem that should turn up in some general form. And as you might expect, these two predictions came true — in almost every respect.

The first time I ever heard of such precognition was from a student of Stevo Todorcevic when I was just starting out on my PhD — and it scared the hell out of me to hear that he predicted a complication that the student only found after 3 months of work on that problem. I call this phenomenon ‘supervisor precognition’. It’s not like supervisors in mathematics always have an idea for an actual proof of a problem, usually not even for a strategy. However, supervisors often have a small but brilliant insight into the situation as such and might spot some critical properties far ahead, long before the student actually gets there.

I know that this strength has as much to do with experience as it does with mathematical talent, but it is both annoying and wonderful. Annoying, since I would like to pretend that I could be as productive without these amazing insights from other people. For Hikaru no Go fans, it feels like Akira playing Sai in the first game — it’s a move from far above, so to speak. To use a metaphor that I don’t really like, if we fight through a jungle to get on a mountain top, this precognition maybe is the equivalent of a greater height, allowing to see not the exact path ahead, but a few major obstacles ahead.

I think this precognition is perhaps the most important strength of a good supervisor. On some level, this precognition needs to be present to guide students to their own, independent research. Students should look out for signs of it (and ask around who’s got it) and researchers should try to develop it (if anyone can tell me how, please tell!). Now if only my proof was finished…

BLAST 2010 chalk slides

by

The organizers of BLAST 2010 asked the speakers to upload or give a link to the slides of their talk. Since I gave a chalk talk at the blackboard I had no slides. So instead of slides let me give a short recollection of my talk here.

The semigroup $\mathbb{F}$.

Like any bad math talk, let’s start with a definition…

Definition Denote the non-empty, finite subsets of $\mathbb{N}$ by $\mathbb{F}$ with semigroup operation $\cup$ (or if you prefer, $\Delta$).

To offer different choices for the operation may seem odd, but as mentioned in this post the real concern is with the restriction to disjoint sets, i.e., where both operations coincide.

FU-set Accordingly, in what follows, every sequence $\mathbf{s} = (s_i)_{i \in \omega}$ in $\mathbb{F}$ is supposed to be pairwise disjoint. Then the FU-set (generated by $\mathbf{s}$) is the set of all finite unions, i.e.,
\[
{FU(} \mathbf{s} ) := \{ \bigcup_{ i \in v} s_i : v \in \mathbb{F} \}.
\]
An FU-set is ordered if the generating sequence is, i.e., $\max(s_i) < \max(s_{i+1} ) $.

Union Ultrafilters

One of the most important examples of idempotent ultrafilters are union ultrafilters on $\mathbb{F}$.

Union Ultrafilters
a) $u \in \beta \mathbb{F}$ is called union ultrafilter if it has a base of FU-sets.
b) $u$ is an ordered union ultrafilter if it has a base of ordered FU-sets.
c) $u$ is a stable union ultrafilter if it is a union ultrafilter and for every choice of countably many $FU ( \mathbf{s}^k ) \in u$ ($k \in \omega$) there exists $ {FU(} \mathbf{t} ) \in u $ such that for all $ k \in \omega $
\[
{ \mathbf{t} } {\subseteq^*} {FU(} \mathbf{s}^k ).
\]

Here $\subseteq^*$ is the usual almost inclusion, i.e., up to a finite set; in other words, $\mathbf{t}$ is a pseudointersection of the ${FU(} \mathbf{s}^k )$. Note that ${FU(} \mathbf{t} )$ is not a pseudointersection — idempotents (in fact, products) can never be P-points.

These notions were introduced by Andreas Blass. Union ultrafilters are idempotent since ${\bigcup_{v \in {FU(} \mathbf{s}) } } v \cdot {FU(} \mathbf{s}) \subseteq {FU(} \mathbf{s})$. To digress.

Question Do union ultrafilters have a base of FU-sets generated by unnested sequences? (where unnested means $\min(s_i) < \min(s_j) \rightarrow \max(s_i) < \max( s_j)$)

This small question came up while preparing the talk; it has no ulterior motive (that I know of) and I never really thought about it.

Differences — orderedness.

As Andreas Blass said at the beginning of his BLAST 2010 tutorials, the very first question when it comes to ultrafilters is, how ultrafilters can be different from each other. In this case, the question becomes: are the three notions any different? Some results about ordered union ultrafilters are as follows.

  • Blass If $u$ is ordered union, then the images $\max(u)$, $\min(u)$ are non-isomorphic Q-points.
  • Blass, Hindman If $u$ is union, then the images $\max(u)$, $\min(u)$ are P-points.
  • Blass, Hindman There consistently exist $u$ union, such that $\max(u)$, $\min(u)$ are not Q-points. (in particular, such $u$ is not ordered union).
  • There consistenly exists $u$ union with $\max(u)$, $\min(u)$ both Q-points, but $u$ is not ordered. (hopefully on the arXiv soon…)

The actual results are usually a bit stronger, but that’s not important right now.

So on the one hand, ordered unions are really stronger than unions; on the other it is not enough for a union ultrafilter to map to Q-points to imply that it is ordered union. So it stays difficult to differentiate the two notions.

As a typical example of clever arguments with union ultrafilters, let’s prove something. This is from Blass, Hindman.

Theorem(Blass, Hindman) If $u$ is a union ultrafilter, then $\max(u)$ is a P-point.

Proof.

  1. Fix $f \in \omega^\omega$.
  2. Consider $A = \{ s \in \mathbb{F}: \min(s) < f(\max(s)) \}$.
  3. If $A \notin u$, then $f \circ \max$ is bounded (hence constant) on a set in $u$.
    1. Take ${FU(} \mathbf{t}) \in u$ disjoint from $A$.
    2. It’s a nice exercise to show that if ${FU(} \mathbf{t}) \in u$ then so are all the FU-sets generated by the $t_i$ with $i>k$ (for each $k$).
    3. Fix $t_0$. For all but finitely many $i$ we have $\max(t_0) < \min(t_i)$ (say from index $k$ onwards).
    4. Hence we calculate $v \in FU$$( \mathbf{t}_{>k})$
      \[
      \min(t_0) = \min(t_0 \cup v) \geq f(\max(t_0 \cup v)) = f(\max( v)).
      \]
      In other words, $f \circ \max$ is bounded by $\min(t_0)$.
  4. If $A \in u$, then $f$ is finite-to-one on a set in $\max(u)$.
    1. Take $ {FU(} \mathbf{t} {) \in u} $ included in A.
    2. We calculate $k = f(\max(v)) > \min(v)$.
    3. But $\max($ $FU$ $(\mathbf{t}$ $))=$ $\max$ $($ $\mathbf{t}$ $)$ and only finitely many $t_i$ have $\min$$(t_i) < k$.

If you look closely, the last line shows that $\max(u)$ is a rapid P-point; rapidity is attributed to Pierre Matet. The argument for $\min$ is a bit more complicated (and longer).

Stability.

So it is difficult to differentiate ordered from unordered — maybe the third notion helps? For this, Andreas Blass proved the following amazing theorem.

Theorem (Blass) If $u$ is a ordered union ultrafilter, then the following are equivalent.
1) Stability
2) Whenever $\mathbf{F}^2_<$$= \{ (s,t) \in \mathbf{F}^2: \max(s) < \min(t) \}$ is partitioned into two pieces, there exists $A\in u$ such that $A^2_<$ is homogeneous.
3) The analogue for $\mathbf{F}^k_<$ (and even $\mathbf{F}^\omega_<$ if one part of the partition is analytic).
4) The ultrapower $u$-prod$\omega$ has exactly 5 constellations generated by $id$, $\max$, $(\min,\max)$, $\min$ and $0$.
5) $\min$ generates an initial segment of $u$-prod$\omega$.

This result is just amazing. It connects a P-point-like property to a Ramsey property — quite unlike the classical situation. At the time it was not yet known that union ultrafilters give P-points as $\min$ and $\max$ (which follows easily from stability), so it was even more surprising.

Now, you’d think there must be a difference if you drop the orderedness of the union ultrafilter, right? Unfortunately, this is not really the case.

Theorem If $u$ is a union ultrafilter, then 1-4 are equivalent and implied by 5. (again, arXiv, hopefully, soon…)

The proof follows Andreas Blass’s proof. He needed orderedness only in ‘1 implies 2’ and ‘5 implies 1’ so this where one has to work a little.

This part 5) is a bit of a rogue since I hadn’t thought about that part until recently and so it is a ‘new’ observation. I do not know if it is strictly stronger and there is evidence that it might not be. But again there seems little hope to differentiate ordered from unordered by means other than the definition.

Regarding the restriction to ordered pairs: this cannot be weakened to disjoint pairs, since any FU-set (ordered or not) will contain ordered and unordered disjoint elements (if ordered, compare $s_1 \cup s_3$ to $s_2 \cup s_4$).

Now, all constructions in the literature yield stable union ultrafilters, hence the big open question for me is:

Question Does there consistently exist an unstable union ultrafilter, i.e. a union ultrafilter that is not stable?

I have worked on this for a while now and even though I hope these exist (say under CH or MA) I think at the moment it is wide open.

The other world.

My own interest lies more in the world of $(\mathbb{N},+)$.

Strongly Summable Ultrafilters An ultrafilter on $\mathbb{N}$ is called strongly summable if it has a base of FS-sets.

FS-sets stand for the analogue of FU-set, i.e., for ‘finite sums set’ — but here with no extra conditions on the sequence in $\mathbb{N}$.

If $u$ is a union ultrafilter, $f: \mathbb{F} \rightarrow \mathbb{N}, s \mapsto \sum_{i\in s} 2^i$, then $f(u)$ is a strongly summable ultrafilter.

This is easy since disjoint unions map to correct sums (there is no carrying over after all). There is also a way back, i.e., for every strongly summable there is a similar looking function that maps it to a union ultrafilter, see Blass, Hindman, however

Question If $p$ is strongly summable, is $f^{-1} (p)$ a union ultrafilter?

I hope this is not true, since it would simplify too many interesting questions, but it seems possible.

As an example why the other world is interesting, let me give (a special case of a) theorem (going back to a theorem by Neil Hindman and Dona Strauss).

Theorem If $u$ is a union ultrafilter, $q,r \in \beta \mathbb{N}$ with $q+r = f(u)$, then $q,r \in \mathbb{Z} + f(u)$ (arXiv, soon…).

What does this mean? The only way to write these kinds of strongly summable ultrafilters as a sum is the trivial way via integers. Ah, I should mention: it is an exercise to show that $\beta \mathbb{N}$ is a left ideal in $\beta \mathbb{Z}$ (so this actually makes sense…) and then that the integers commute (so this trivial way is always possible).

This is a fascinating property and these (and some more) strongly summables are the only known examples with this property (unlike nearly all other results for idempotents which are in ZFC). I hope to blog more about more special properties sometime soon but this is all I covered in my talk, so enough for today.