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 $n$“.

The basic plan is that we will work with a set $\mathcal{U}$ of subsets of $\mathbb{N}$ 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, $\forall_\mathcal{U} n, P(n)$)

to mean

$\{n \in N : P(n) \text{ holds}\}\in \mathcal{U}$.

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 $\mathbb{N}$ must be infinite.

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

• $\mathbb{N} \in \mathcal{U}, \emptyset \not\in \mathcal{U}$
• $A,B \in \mathcal{U} \Leftrightarrow A\cap B \in \mathcal{U}$
• $A\cup B \in \mathcal{U} \Leftrightarrow A \in \mathcal{U} \text{ or } B \in \mathcal{U}$
• For every $A \subseteq \mathbb{N}$, precisely one of $A, \mathbb{N}\backslash A$ is in $\mathcal{U}$.
• There is no finite set in $\mathcal{U}$.

These, it turns out, do axiomatise the structure of consistent sets of subsets of $\mathbb{N}$ called nonprincipal ultrafilters.

Note the “nonprincipal” bit comes from our final condition that $\mathcal{U}$. 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 $m$.” 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 $\mathbb{R}$. If we take a countable product $\mathbb{R}^\mathbb{N}$ it is obvious we don’t automatically get a field (though we do get a rather large vector space), since an element like $(3,\pi,0,2,-4.3,.....)$ is on the one hand clearly not equal to $(0,0,0,...)$ 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 $\mathbb{R}^\mathbb{N}$ by

$x=(x_1,x_2,...,) \sim y=(y_1,...)$ if for most $i, x_i=y_i$ (where we fix “for most” to be with respect to some ultrafilter $\mathcal{U}$).

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

$\mathbb{R}_\mathcal{U} := \mathbb{R}^\mathbb{N} / \sim$

As a quick exercise, work out what this looks like if $\mathcal{U}$ is a principal ultrafilter.

If $\mathcal{U}$ 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 $x_1, x_2, .... \in \mathbb{N}$  such that $FS((x_i)):= \{x_{i_1}+...+x_{i_m}: m,i_1,...,i_m \in \mathbb{N}\}$ is monochromatic.

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

$\mathcal{U} + \mathcal{V} = \{S \subset \mathbb{N}: (\forall_\mathcal{U} x)(\forall_\mathcal{V} y) x+y \in S\}$.

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: $\mathcal{U} + \mathcal{U} = \mathcal{U}$. Then the proof can be rapidly finished off by picking a single colour class $C$ lying in $\mathcal{U}$ (which can be seen to exist by an easy induction), and building up the sequence step by step passing to nonempty nested subsets of $C$ still lying inside $\mathcal{U}$ 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.

What is the greatest number $N_d(\theta)$ of unit vectors in $\mathbb{R}^d$ such that the angle between any two is greater than or equal to angle $\theta$?
Firstly, it is almost obvious that if $\theta \geq \frac{\pi}{2}$ then $N_d(\theta) \leq 2d$. 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.