The n-Category Café

Inspired by John’s recent series of posts on random permutations, I started thinking about random operators on vector spaces, and nilpotent operators, and Cayley’s tree formula, and, especially, Joyal’s wonderful proof of Cayley’s formula that led him (I guess) to create the equally wonderful theory of species.

Blog posts and comments are often rambling and discursive. That’s part of the fun of it: we think out loud, we try out ideas, we stumble ignorantly through things that others have done better before us, we make mistakes, we refine our ideas, and we learn how to communicate those ideas more efficiently. My own posts on this topic (1, 2, 3) are no exception.

But short sharp accounts are also good! So I wrote a 4.5-page paper containing the thing I think is new. It’s a new proof of the old theorem that when you choose at random a linear operator on a vector space of finite cardinality $N$, the probability of it being nilpotent is $1/N$. And this proof is a linear analogue of Joyal’s proof of Cayley’s formula.

Yay! The first volume of Compositionality has been published! You can read it here:

https://compositionality-journal.org

“Compositionality” is about how complex things can be assembled out of simpler parts. Compositionality is a journal for research using compositional ideas, most notably of a category-theoretic origin, in any discipline. Example areas include but are not limited to: computation, logic, physics, chemistry, engineering, linguistics, and cognition.

Many mathematicians like the drawings of Escher, or sculptures of surfaces, or colourful plots of fractals and other mathematical phenomena. My own taste seems to be a bit different. I’m not sure how to describe it, but over the years I’ve amassed on my computer a small collection of “mathematical” images, in some rather loose sense of the word. Every time I save one I tell myself I might use it in a blog post one day, but every time I write a blog post, I forget.

Since I never use them, and since it’s Christmas, I thought I’d present them all here instead in one big gallery. Some illustrate some mathematical concept, some refer to the experience of being a mathematician, and a couple are silly visual puns. But many just ring a bell in a part of my mind that seems to me to be connected with the activity of doing mathematics.

I’m afraid I have no idea who any of them were created by (not me!); all have been downloaded from the internet at some point. If you want to find out, I’d suggest a reverse image search.

Merry Christmas! And don’t take the images too seriously — this is just for fun.

Erwin Schrödinger fled Austria during World War II. In 1940 he found a position in the newly founded Dublin Institute for Advanced Studies. This allowed him to think again. He started publishing papers on unified field theories in 1943, based on earlier work of Eddington and Einstein. He was trying to unify gravity, electromagnetism and a scalar ‘meson field’… all in the context of classical field theory, nothing quantum.

Then he had a new idea. He got very excited about it, and January of 1947 he wrote:

At my age I had completely abandoned all hope of ever again making a really big important contribution to science. It is a totally unhoped-for gift from God. One could become a believer or superstitious [gläubig oder abergläubig], e.g., could think that the Old Gentleman had ordered me specifically to go to Ireland to live in 1939, the only place in the world where a person like me would be able to live comfortably and without any direct obligations, free to follow all his fancies.

He even thought he might get a second Nobel prize.

He called a press conference… and the story of how it all unraveled is a bit funny and a bit sad. But what was his theory, actually?

I think I’m closing in on a good understanding of random permutations using species and groupoid cardinality. Today I want to use this approach to state and prove a categorified version of the Cycle Length Lemma, which is Lemma 2.1 here:

• Kevin Ford, Anatomy of Integers and Random Permutations — Course Lecture Notes.

This is a grand generalization of the result in Part 10.

Like last year and the year before, there will be a school associated to this year’s conference on applied category theory! If you’re trying to get into applied category theory, this is the best possible way.

• Applied Category Theory 2020 — Adjoint School.

The school will consist of online meetings from February to June 2020, followed by a research week June 29–July 3, 2020 at MIT in Cambridge Massachusetts. The conference follows on July 6–10, 2020, and if you attend the school you should also go to the conference.

The deadline to apply is January 15 2020; apply here.

Let $V$ be a finite set. What’s the probability that a random endofunction of $V$ is eventually constant — that is, becomes constant after you iterate it enough times? It’s $1/\#V$. That’s basically Cayley’s tree formula, Joyal’s beautiful proof of which I showed you recently.

Now suppose that $V$ has the structure of a vector space. What’s the probability that a random linear operator on $V$ is eventually constant — or as one usually says, nilpotent? It’s still $1/\#V$. I recently showed you a proof of this using generating functions, but it gave no indication of why the answer is as simple as it is. There was some miraculous cancellation.

Today I’ll show you a much more direct proof of the probability of getting a nilpotent, or equivalently the number of nilpotents. The argument shadows Joyal’s proof of Cayley’s formula.

Groupoids generalize sets in an obvious way: while elements of a set can only be the same or different, objects of a groupoid can be ‘the same’ — that is, isomorphic — in more than one way.

Less obviously, groupoids also let us generalize the concept of cardinality. While the cardinality of a finite set is a natural number, the cardinality of a finite groupoid can be any nonnegative rational number!

This suggests that probabilities in combinatorics could secretly be cardinalities of groupoids. Indeed, Poisson distributions naturally show up this way. For a good self-contained introduction, see:

• Qiaochu Yuan, Groupoid cardinality, Annoying Precision, November 8, 2012.

Now I want to explain how groupoid cardinality can be used to prove some important (and well-known) facts about random permutations.

Here is an advertisement for postdoc positions in applied category theory at the National Institute of Standards and Technology.

In our quest to understand the true nature of random permutations, Part 7 took us into a deeper stratum: their connection to Poisson distributions. I listed a few surprising facts. For example, these are the same:

• The probability that $N$ raindrops land on your head in a minute, if on average one lands on your head every $k$ minutes.
• The probability that a random permutation of a huge finite set has $N$ cycles of length $k$.

Here the raindrops are Poisson distributed, and ‘huge’ means I’m taking a limit as the size of a finite set goes to infinity.

Now let’s start trying to understand what’s going on here! Today we’ll establish the above connection between raindrops and random permutations by solving this puzzle:

Puzzle 12. Treat the number of cycles of length $k$ in a random permutation of an $n$-element set as a random variable. What do the moments of this random variable approach as $n \to \infty$?

First, let me take a moment to explain moments.

Last time we saw a strong connection between random permutations and Poisson distributions. Thinking about this pulled me into questions about partitions and the moments of Poisson distributions. These may be a bit of a distraction — but maybe not, since every permutation gives a partition, namely the partition into cycles.

Here’s a good puzzle to start with:

Puzzle 11. Suppose raindrops are falling on your head, randomly and independently, at an average rate of one per minute. What’s the average of the cube of the number of raindrops that fall on your head in one minute?

Last time I computed the expected number of cycles of length $k$ in a random permutation of an $n$-element set. The answer is wonderfully simple: $1/k$ for all $k = 1, \dots, n$.

As Mark Meckes pointed out, this fact is just a shadow of a more wonderful fact. Let $C_k$ be the number of cycles of length $k$ in a random permutation of an $n$-element set, thought of as a random variable. Then as $n \to \infty$, the distribution of $C_k$ approaches a Poisson distribution with mean $1/k$.

But this is just a shadow of an even more wonderful fact!

Cayley’s formula says how many trees there are on a given set of vertices. For a set with $n$ elements, there are $n^{n - 2}$ of them. In 1981, André Joyal published a wonderful new proof of this fact, which, although completely elementary and explicit, seems to have been one of the seeds for his theory of combinatorial species.

All I’m going to do in this post is explain Joyal’s proof, with lots of pictures. In a later post, I’ll explain the sense in which Cayley’s formula is the set-theoretic analogue of the linear-algebraic fact I wrote about last time: that for a random linear operator on a finite vector space $V$, the probability that it’s nilpotent is $1/\#V$. And I’ll also give a new (?) proof of that fact, imitating Joyal’s. But that’s for another day.

The Department of Mathematics at the University of California, Riverside invites application to a faculty position at the full professor level in the general area of pure mathematics. The successful candidate is expected to fill the F. Burton Jones Chair in Pure Mathematics. The search seeks candidates with national and international recognition, an outstanding research track record and outlook, a strong record in mentoring and teaching, and leadership in promoting diversity and serving the professional community.

A PhD in mathematics is required. It is expected that at UCR, the candidate will lead a rigorous research program, will develop and teach graduate and undergraduate courses, will advise and mentor graduate and undergraduate students, will vigorously promote diversity, and will engage in both campus and professional service activities.

A start-up package will be provided. The F. Burton Jones endowment fund will be made available to support the candidate’s research and mentoring activities. This position will start between July 1, 2020 and July 1, 2021.

Often we get a classifying topos by taking a finite limits theory $T$ and forming the category of presheaves $\hat{T} = Set^{T^{op}}$. For example, in their book, Mac Lane and Moerdijk get the classifying topos for commutative rings from the finite limits theory for rings this way. My student Christian Williams suggested an interesting alternative: what if we take the category of presheaves on a Lawvere theory?

For example, suppose we take the category of presheaves on the Lawvere theory for commutative rings. We get a topos. What is it the classifying topos for?

I’m in Vienna to give a couple of talks, one yesterday and one later this afternoon. Draft slides of both talks are on this page.

The first sees me take up again the work of Michael Friedman, in particular his Dynamics of Reason. I see that I was lamenting the difficulty of getting my original article published back in 2007. (But then I was still a couple of months away from finding out that I had a permanent job after a very long search, and so evidently fed up.)

In any case, I think the story I’m telling is improving with age - we now appear to have modal homotopy type theory and M-theory in harmony. But irrespective of whether Urs Schreiber’s Hypothesis H bears fruit, there’s still an important story to tell about mathematics modifying its framework.

The second talk introduces ideas from my forthcoming Modal homotopy type theory: The prospect of a new logic for philosophy.

What is the probability that a random linear operator is nilpotent?

Recall that a linear operator $T$ on a vector space $V$ is called “nilpotent” if $T^n = 0$ for some $n$. Assuming that $V$ is finite-dimensional and over a finite field, there are only finitely many operators on $V$. Choose one at random. It turns out that the probability of it being nilpotent is

$$\frac{1}{\# V}$$

— the reciprocal of the number of elements of $V$.

I’ll explain why. Along the way, we’ll meet some dynamical linear algebra, some $q$-formalism, and a kind of generating function adapted to linear algebra over a finite field.

This post was inspired by John’s recent series on random permutations, but is free-standing and self-contained. Enjoy!

Now I’ll tackle a really fundamental question about random permutations — one whose answer will quickly deliver the solutions to many others!

Puzzle 7. What is the expected number of cycles of length $k$ in a random permutation of an $n$-element set?

The answer is beautiful: it’s $1/k$. More precisely, this holds whenever the question is reasonable, meaning $1 \le k \le n$.

Note that this answer passes a simple sanity check. If on average there’s $1$ cycle of length $1$, $1/2$ cycles of length $2$, and so on, the average number of elements in our $n$-element set must be

$$1 \cdot 1 + \frac{1}{2} \cdot 2 + \cdots + \frac{1}{n} \cdot n = n$$

Whew!