Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

December 13, 2019

Applied Category Theory Postdocs at NIST

Posted by John Baez

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

Posted at 10:44 PM UTC | Permalink | Post a Comment

December 11, 2019

Random Permutations (Part 9)

Posted by John Baez

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 nn raindrops land on your head in a minute, if on average one lands on your head every kk minutes.
  • The probability that a random permutation of a huge finite set has nn cycles of length kk.

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 kk in a random permutation of an nn-element set as a random variable. What do the moments of this random variable approach as nn \to \infty?

First, let me take a moment to explain moments.

Posted at 9:45 AM UTC | Permalink | Followups (2)

December 8, 2019

Random Permutations (Part 8)

Posted by John Baez

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?

Posted at 9:55 PM UTC | Permalink | Followups (10)

December 7, 2019

Random Permutations (Part 7)

Posted by John Baez

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

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

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

Posted at 11:25 PM UTC | Permalink | Followups (6)

A Visual Telling of Joyal’s Proof Of Cayley’s Formula

Posted by Tom Leinster

Cayley’s formula says how many trees there are on a given set of vertices. For a set with nn elements, there are n n2n^{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 VV, the probability that it’s nilpotent is 1/#V1/\#V. And I’ll also give a new (?) proof of that fact, imitating Joyal’s. But that’s for another day.

Posted at 5:29 PM UTC | Permalink | Followups (5)

December 5, 2019

Position at U. C. Riverside

Posted by John Baez

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.

Posted at 5:25 PM UTC | Permalink | Post a Comment

Topoi from Lawvere Theories

Posted by John Baez

Often we get a classifying topos by taking a finite limits theory TT and forming the category of presheaves T^=Set T op\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?

Posted at 4:24 PM UTC | Permalink | Followups (8)

December 4, 2019

A Couple of Talks in Vienna

Posted by David Corfield

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.

Posted at 4:01 PM UTC | Permalink | Post a Comment

December 3, 2019

Counting Nilpotents

Posted by Tom Leinster

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

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

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

— the reciprocal of the number of elements of VV.

I’ll explain why. Along the way, we’ll meet some dynamical linear algebra, some qq-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!

Posted at 4:37 PM UTC | Permalink | Followups (22)

December 1, 2019

Random Permutations (Part 6)

Posted by John Baez

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 kk in a random permutation of an nn-element set?

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

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

11+122++1nn=n 1 \cdot 1 + \frac{1}{2} \cdot 2 + \cdots + \frac{1}{n} \cdot n = n

Whew!

Posted at 8:36 PM UTC | Permalink | Followups (18)