Feeds:
Posts
Comments

Archive for the ‘combinatorics’ Category

Let C be a (locally small) category. Recall that any such category naturally admits a Yoneda embedding

\displaystyle Y : C \ni c \mapsto \text{Hom}(-, c) \in \widehat{C}

into its presheaf category \widehat{C} = [C^{op}, \text{Set}] (where we use [C, D] to denote the category of functors C \to D). The Yoneda lemma asserts in particular that Y is full and faithful, which justifies calling it an embedding.

When C is in addition assumed to be small, the Yoneda embedding has the following elegant universal property.

Theorem: The Yoneda embedding Y : C \to \widehat{C} exhibits \widehat{C} as the free cocompletion of C in the sense that for any cocomplete category D, the restriction functor

\displaystyle Y^{\ast} : [\widehat{C}, D]_{\text{cocont}} \to [C, D]

from the category of cocontinuous functors \widehat{C} \to D to the category of functors C \to D is an equivalence. In particular, any functor C \to D extends (uniquely, up to natural isomorphism) to a cocontinuous functor \widehat{C} \to D, and all cocontinuous functors \widehat{C} \to D arise this way (up to natural isomorphism).

Colimits should be thought of as a general notion of gluing, so the above should be understood as the claim that \widehat{C} is the category obtained by “freely gluing together” the objects of C in a way dictated by the morphisms. This intuition is important when trying to understand the definition of, among other things, a simplicial set. A simplicial set is by definition a presheaf on a certain category, the simplex category, and the universal property above says that this means simplicial sets are obtained by “freely gluing together” simplices.

In this post we’ll content ourselves with meandering towards a proof of the above result. In a subsequent post we’ll give a sampling of applications.

(more…)

Read Full Post »

The goal of this post is to collect a list of applications of the following theorem, which is perhaps the simplest example of a fixed point theorem.

Theorem: Let G be a finite p-group acting on a finite set X. Let X^G denote the subset of X consisting of those elements fixed by G. Then |X^G| \equiv |X| \bmod p; in particular, if p \nmid |X| then G has a fixed point.

Although this theorem is an elementary exercise, it has a surprising number of fundamental corollaries.

(more…)

Read Full Post »

Occasionally I see mathematical questions that seem “grammatically incorrect” in some sense.

Example. “Is [0, 1] open or closed?”
Example. “Is \{ 1, 2, 3 \} a group?”
Example. “What’s the Fourier series of \sin x + \sin \pi x?”

Here are some sillier examples.

Example. “Is a rectangle prime?”
Example. “Is 17 \in 3?”
Example. “What’s the Fourier series of the empty set?”

What all of these examples have in common is that they are type errors: they are attempts to apply some mathematical process to a kind of mathematical object it was never intended to take as input. If you tried to write a program in some highly mathematical programming language to answer these questions, it (hopefully!) wouldn’t compile.

Mathematical objects are usually not explicitly thought of as having types in the same way that objects in a programming language with a type system has types. Ordinary mathematics is supposed to be formalizable within Zermelo-Fraenkel (ZF) set theory, possibly with the axiom of choice, and in ZF every mathematical object is constructed as a set. In that sense they all have the same type. (In particular, the question “is 17 \in 3?” is perfectly meaningful in ZF! This is one reason not to like ZF as a foundation of mathematics.) However, I think that in practice mathematical objects are implicitly thought of as having types, and that this is a mental habit mathematicians pick up but don’t often talk about.

Instead of thinking in terms of set theory, thinking of mathematical objects as having types allows us to import various useful concepts into mathematics, such as the notions of type safety, typecasting, subtyping, and overloading, that help us make more precise what we mean by a mathematical sentence being “grammatically incorrect.” The rest of this post will be a leisurely discussion of these and other type-based concepts as applied to mathematics in general. There are various categorical ideas here, but for the sake of accessibility we will restrict them to parenthetical remarks.

(more…)

Read Full Post »

Previously I mentioned very briefly Granville’s The Anatomy of Integers and Permutations, which explores an analogy between prime factorizations of integers and cycle decompositions of permutations. Today’s post is a record of the observation that this analogy factors through an analogy to prime factorizations of polynomials over finite fields in the following sense.

Theorem: Let q be a prime power, let n be a positive integer, and consider the distribution of irreducible factors of degree 1, 2, ... k in a random monic polynomial of degree n over \mathbb{F}_q. Then, as q \to \infty, this distribution is asymptotically the distribution of cycles of length 1, 2, ... k in a random permutation of n elements.

One can even name what this random permutation ought to be: namely, it is the Frobenius map x \mapsto x^q acting on the roots of a random polynomial f, whose cycles of length k are precisely the factors of degree k of f.

Combined with our previous result, we conclude that as q, n \to \infty (with q tending to infinity sufficiently quickly relative to n), the distribution of irreducible factors of degree 1, 2, ... k is asymptotically independent Poisson with parameters 1, \frac{1}{2}, ... \frac{1}{k}.

(more…)

Read Full Post »

Previously we showed that the distribution of fixed points of a random permutation of n elements behaves asymptotically (in the limit as n \to \infty) like a Poisson random variable with parameter \lambda = 1. As it turns out, this generalizes to the following.

Theorem: As n \to \infty, the number of cycles of length 1, 2, ... k of a random permutation of n elements are asymptotically independent Poisson with parameters 1, \frac{1}{2}, ... \frac{1}{k}.

This is a fairly strong statement which essentially settles the asymptotic description of short cycles in random permutations.

(more…)

Read Full Post »

The following two results are straightforward and reasonably well-known exercises in combinatorics:

  1. The number of permutations on n elements with no fixed points (derangements) is approximately \frac{n!}{e}.
  2. The expected number of fixed points of a random permutation on n elements is 1.

As it turns out, it is possible to say substantially more about the distribution of fixed points of a random permutation. In fact, the following is true.

Theorem: As n \to \infty, the distribution of the number of fixed points of a random permutation on n elements is asymptotically Poisson with rate \lambda = 1.

(more…)

Read Full Post »

Previously we described all finite-dimensional random algebras with faithful states. In this post we will describe states on the infinite-dimensional ^{\dagger}-algebra \mathbb{C}[x]. Along the way we will run into and connect some beautiful and classical mathematical objects.

A special case of part of the following discussion can be found in an old post on the Catalan numbers.

(more…)

Read Full Post »

For two categories C, D let D^C denote the functor category, whose objects are functors C \to D and whose morphisms are natural transformations. For C a locally small category, the Yoneda embedding is the functor C \to \text{Set}^{C^{op}} sending an object x \in C to the contravariant functor \text{Hom}(-, x) and sending a morphism x \to y to the natural transformation \text{Hom}(-, x) \to \text{Hom}(-, y) given by composition. The goal of the next few posts is to discuss some standard properties of this embedding and try to gain some intuition about it.

Below, whenever we talk about the Yoneda lemma we implicitly restrict our attention to locally small categories.

(more…)

Read Full Post »

We continue our exploration of ultrafilters. Today we’ll discuss the infinite Ramsey theorem, which is the following classical result:

Theorem: Suppose the complete graph K_{\infty} on countably many vertices has its edges colored in one of k colors. Then there is a monochromatic K_{\infty} (i.e. an infinite subgraph all of whose edges are the same color).

The finite Ramsey theorem implies that there is a monochromatic K_n for every positive integer n, but this is a strictly stronger result; it implies not only the finite Ramsey theorem but the “strengthened” finite Ramsey theorem, and by the Paris-Harrington theorem this is independent of Peano arithmetic (although Peano arithmetic can prove the finite Ramsey theorem). Indeed, while the standard proof of the finite Ramsey theorem uses the finite pigeonhole principle, the standard proof of the infinite Ramsey theorem uses the infinite pigeonhole principle, which is stronger; this is part of the subject of a post by Terence Tao which is quite enlightening.

Given a non-principal ultrafilter F on \mathbb{N}, any partition of \mathbb{N} into finitely many disjoint subsets (that is, any coloring) has the property that exactly one of the subsets is in F (that is, has “full measure”), and this subset must be infinite. This subset can, in turn, be colored (partitioned), and exactly one of the blocks of the partition is in F, and it must again be infinite, and so forth. It follows that a non-principal ultrafilter lets us use the infinite pigeonhole principle repeatedly (in fact this is in some sense what a non-principal ultrafilter is), and since this is exactly what is needed to prove the infinite Ramsey theorem we might expect that we could use a non-principal ultrafilter to prove the infinite Ramsey theorem. Today we’ll describe this proof, and then describe how the infinite Ramsey theorem implies the finite Ramsey theorem, which involves a different use of a non-principal ultrafilter on \mathbb{N}.

(more…)

Read Full Post »

Remark: To forestall empty set difficulties, whenever I talk about arbitrary sets in this post they will be non-empty.

We continue our exploration of ultrafilters from the previous post. Recall that a (proper) filter on a poset P is a non-empty subset F such that

  1. For every x, y \in F, there is some z \in F such that z \le x, z \le y.
  2. For every x \in F, if x \le y then y \in F.
  3. P is not the whole set F.

If P has finite infima (meets), then the first condition, given the second, can be replaced with the condition that if x, y \in F then x \wedge y \in F. (This holds in particular if P is the poset structure on a Boolean ring, in which case x \wedge y = xy.) A filter is an ultrafilter if in addition it is maximal under inclusion among (proper) filters. For Boolean rings, an equivalent condition is that for every x \in B either x \in F or 1 - x \in F, but not both. Recall that this condition tells us that ultrafilters are precisely complements of maximal ideals, and can be identified with morphisms in \text{Hom}_{\text{BRing}}(B, \mathbb{F}_2). If B = \text{Hom}(S, \mathbb{F}_2) for some set S, then we will sometimes call an ultrafilter on B an ultrafilter on S (for example, this is what people usually mean by “an ultrafilter on \mathbb{N}“).

Today we will meander towards an ultrafilter point of view on topology. This point of view provides, among other things, a short, elegant proof of Tychonoff’s theorem.

(more…)

Read Full Post »

Older Posts »

Follow

Get every new post delivered to your Inbox.

Join 283 other followers