You are currently browsing the category archive for the ‘Combinatorics’ category.

Have just come across a fairly groovy gadget: ultrafilter-based quantifiers, essentially a rigorous way of talking about statements being true “for almost all “.

The basic plan is that we will work with a set of subsets of which are to be considered “very large” or “almost every natural number”. We then can define the logical statement * *

*P(n) holds for almost every n *(or, )

to mean

.

So all we really have to do is work out how ‘large’ sets behave, or how we want these propositions to work out. The following seem like reasonable assumptions:

- The entire set of natural numbers is a large subset. The empty set is not.
- P and Q hold for almost all naturals if and only if P holds for almost all naturals and Q holds for almost all naturals.
- Either P holds or Q holds for almost every natural if either P holds for almost every natural, or if Q does.
- If not almost every natural has property P, then almost every natural has property “not P”
- A large subset of must be infinite.

Writing in terms of our collection of ‘large sets’ we obtain the rules:

- For every , precisely one of is in .
- There is no finite set in .

These, it turns out, do axiomatise the structure of consistent sets of subsets of called *nonprincipal ultrafilters.*

Note the “nonprincipal” bit comes from our final condition that . If we remove this restriction, we allow the existence of a small number of so-called ‘principal’ ultrafilters of the form “every set containing the number .” One can easily verify that this set satisfies all the remaining axioms.

Great! So we have a bunch of rules telling us these structures can work. Furthermore, it’s possible without a great amount of thought to construct one using transfinite induction (usually in the form of Zorn’s Lemma). However, it’s clear they still perhaps are not quite what we might intuitively think. For example, at some point during the construction of an ultrafilter we are *required* to decide whether the set of even numbers is a “large” set or if the odd numbers are. Annoyingly, our above terminology will translate into “Almost every number is even” and “Almost no number is odd” or vice-versa with neither being canonically ‘correct’ (though I can think of meta-arguments for both ways round).

So why is this somewhat eclectic formalism helpful?

Firstly, it helps us to fudge situations that “don’t quite work” as things stand. For example, it is often true that if one takes a product of some number of algebraic structures one gets a similar structure. Groups and topological spaces both have reasonably nicely defined products (with operations componentwise). An obvious type of structure that won’t have this property is a field. For example, let’s take . If we take a countable product it is obvious we don’t automatically get a field (though we do get a rather large vector space), since an element like is on the one hand clearly not equal to but on the other hand has no inverse, because the zero in the third entry causes problems.

Oh, what shame… so I guess there’s no hope for constructing lots of new fields from old fields by taking huge products… If only there was some way in which we could say that a sequence (1,0.5,0,0,0,0,……0,0,0,….) has *so many* zeroes it is basically the same as the zero element, whereas (0,1,1,1,…,1,1,…) has so *few* zeroes, it could just as well be (1,1,……1,1,…) and we wouldn’t care, in such a way that removes all our problems. Aha! But we can do this! Define an equivalence relation on by

if *for most* (where we fix *“for most*” to be with respect to some ultrafilter ).

And define the **ultraproduct **as the quotient of the product space by this equivalence relation

As a quick exercise, work out what this looks like if is a principal ultrafilter.

If is nonprincipal this gives rise to a new (much larger) field called the *hyper-real numbers* where “infinite” and “infinitessimal” numbers can be thought to exist. Taking a product of different fields (and modifying the ultrafilter) may lead to diverse fields with different structures.

As a further application, a couple of days ago I stumbled across a beautiful proof in a paper by Imre Leader of the following result. Unfortunately the details are too long for me to replicate, but I can hopefully sketch some of what is going on, though I must confess that this post derives from awe rather than a deep understanding on my part.

**Theorem (Finite Sums Thm): **Let the natural numbers be coloured with finitely many colours. Then there exist such that is monochromatic.

To prove this, one defines an *addition* operation on ultrafilters, by

.

One can check that this is associative (but not commutative) and left-continuous in a standard compact topology on the space of natural ultrafilters, and then deduce (nontrivially) that there is some idempotent ultrafilter: . Then the proof can be rapidly finished off by picking a single colour class lying in (which can be seen to exist by an easy induction), and building up the sequence step by step passing to nonempty nested subsets of still lying inside at each stage.

Finally, an amusing application is Godel’s proof of the existence of God, where an ultrafilter structure is noted on the poset of “good properties”. I am not sure if he accounts for the possibility that “goodness” could itself be a primitive property and generate a principal ultrafilter, but I haven’t followed the argument closely, instead referring the reader to the relevent wikipedia page.

One of the recent questions from an example sheet in Metric and Topological Spaces gave rise to the following more interesting general question:

*What is the greatest number of unit vectors in such that the angle between any two is greater than or equal to angle ?*

I don’t want to ruin this question by posting a solution, or even a sketch solution on this blog, but there is some very interesting behaviour revealed once you look into it. Anyone who wishes to investigate fully independently should now stop reading. I am going to post a few interesting remarks that break down the kind of behaviour the problem exhibits (without giving any proofs).

Firstly, it is almost obvious that if then . Unfortunately, the ‘obvious’ proof of this is a proof by ‘worst case scenario’ (an orthogonal set and its negation is *clearly* the best example), which unfortunately doesn’t really hold water. However, this does turn out to be true, and my process of finding proof gave me an interesting perspective on what ‘really spread out’ vectors look like.

Now we get a bizarre phenomenon: acute angles seem to behave frighteningly differently to right and obtuse angles. Any sort of inductive bound one tries to find seems to fail, yet coming up with reasonable explicit constructions is tricky. In fact it turns out that a sudden jump is made from there being linearly many unit vectors to their being exponentially many unit vectors. Getting the upper bound for this is quite simple. A lower bound is harder.