The n-Category Café

Last time we proved Flajolet’s Fundamental Lemma about enumerating Dyck paths. This time I want to give some examples, in particular to relate this to what I wrote previously about Dyck paths, Schröder paths and what they have to do with reverse Bessel polynomials.

We’ll see that the generating function of the sequence of reverse Bessel polynomials $\left(\theta_i(R)\right)_{i=0}^\infty$ has the following continued fraction expansion.

$$\sum_{i=0}^\infty \theta_i(R) \,t^i = \frac{1}{1-Rt- \frac{t}{1-Rt - \frac{2t}{1-Rt- \frac{3t}{1-\dots}}}}$$

I’ll even give you a snippet of SageMath code so you can have a play around with this if you like.

I’m running a special session on applied category theory, and now the program is available:

• Applied category theory, Fall Western Sectional Meeting of the AMS, 4-5 November 2017, U.C. Riverside.

This is going to be fun.

My former student Brendan Fong is now working with David Spivak at M.I.T., and they’re both coming. My collaborator John Foley at Metron is also coming: we’re working on the CASCADE project for designing networked systems.

Dmitry Vagner is coming from Duke: he wrote a paper with David and Eugene Lerman on operads and open dynamical system. Christina Vaisilakopolou, who has worked with David and Patrick Schultz on dynamical systems, has just joined our group at UCR, so she will also be here. And the three of them have worked with Ryan Wisnesky on algebraic databases. Ryan will not be here, but his colleague Peter Gates will: together with David they have a startup called Categorical Informatics, which uses category theory to build sophisticated databases.

That’s not everyone — for example, most of my students will be speaking at this special session, and other people too — but that gives you a rough sense of some people involved. The conference is on a weekend, but John Foley and David Spivak and Brendan Fong and Dmitry Vagner are staying on for longer, so we’ll have some long conversations… and Brendan will explain decorated corelations in my Tuesday afternoon network theory seminar.

Wanna see what the talks are about?

In my last post I talked about certain types of lattice paths with weightings on them and formulas for the weighted count of the paths, in particular I was interested in expressing the reverse Bessel polynomials as a certain weighted count of Schröder paths. I alluded to some connection with continued fractions and it is this connection that I want to explain here and in my next post.

In this post I want to prove Flajolet’s Fundamental Lemma. Alan Sokal calls this Flajolet’s Master Theorem, but Viennot takes the stance that it deserves the high accolade of being described as a ‘Fundamental Lemma’, citing Aigner and Ziegler in Proofs from THE BOOK:

“The essence of mathematics is proving theorems – and so, that is what mathematicians do: They prove theorems. But to tell the truth, what they really want to prove, once in their lifetime, is a Lemma, like the one by Fatou in analysis, the Lemma of Gauss in number theory, or the Burnside-Frobenius Lemma in combinatorics.

“Now what makes a mathematical statement a true Lemma? First, it should be applicable to a wide variety of instances, even seemingly unrelated problems. Secondly, the statement should, once you have seen it, be completely obvious. The reaction of the reader might well be one of faint envy: Why haven’t I noticed this before? And thirdly, on an esthetic level, the Lemma – including its proof – should be beautiful!”

Interestingly, Aigner and Ziegler were building up to describing a result of Viennot’s – the Gessel-Lindström-Viennot Lemma – as a fundamental lemma! (I hope to talk about that lemma in a later post.)

Anyway, Flajolet’s Fundamental Lemma that I will describe and prove below is about expressing the weighted count of paths that look like

as a continued fraction

$$\frac{1} {1- c_{0} - \frac{a_{1} b_{1}} {1-c_{1} - \frac{a_{2} b_{2}} {1- c_2 - \frac{a_3 b_3} {1-\dots }}}}$$

Next time I’ll give a few examples, including the connection with reverse Bessel polynomials.

We’re having a conference on applied category theory!

• Applied Category Theory (ACT 2018). Summer school April 23rd to 27th and conference April 30th to May 4th 2018 at the Lorentz Center in Leiden, the Netherlands. Organized by Bob Coecke (Oxford), Brendan Fong (MIT), Aleks Kissinger (Nijmegen), Martha Lewis (Amsterdam), and Joshua Tan (Oxford).

The plenary speakers will be:

• Samson Abramsky (Oxford)
• John Baez (UC Riverside)
• Kathryn Hess (EPFL)
• Mehrnoosh Sadrzadeh (Queen Mary)
• David Spivak (MIT)

There will be a lot more to say as this progresses, but for now let me just quote from the conference website.

guest post by Spencer Breiner

One Year Postdoc Position at Carnegie Mellon/NIST

We are seeking an early-career researcher with a background in category theory, functional programming and/or electrical engineering for a one-year post-doctoral position supported by an Early-concept Grant (EAGER) from the NSF’s Systems Science program. The position will be managed through Carnegie Mellon University (PI: Eswaran Subrahmanian), but the position itself will be located at the US National Institute for Standards and Technology (NIST), located in Gaithersburg, Maryland outside of Washington, DC.

The project aims to develop a compositional semantics for electrical networks which is suitable for system prediction, analysis and control. This work will extend existing methods for linear circuits (featured on this blog!) to include (i) probabilistic estimates of future consumption and (ii) top-down incentives for load management. We will model a multi-layered system of such “distributed energy resources” including loads and generators (e.g., solar array vs. power plant), different types of resource aggregation (e.g., apartment to apartment building), and across several time scales. We hope to demonstrate that such a system can balance local load and generation in order to minimize expected instability at higher levels of the electrical grid.

This post is available full-time (40 hours/5 days per week) for 12 months, and can begin as early as October 1st.

For more information on this position, please contact Dr. Eswaran Subrahmanian (sub@cmu.edu) or Dr. Spencer Breiner (spencer.breiner@nist.gov).

I want to show you a combinatorial interpretation of the reverse Bessel polynomials which I learnt from Alan Sokal. The sequence of reverse Bessel polynomials begins as follows.

$$\begin{aligned} \theta_0(R)&=1\\ \theta_1(R)&=R+1\\ \theta_2(R)&=R^2+3R+3\\ \theta_3(R)&= R^3 +6R^2+15R+15 \end{aligned}$$

To give you a flavour of the combinatorial interpretation we will prove, you can see that the second reverse Bessel polynomial can be read off the following set of ‘weighted Schröder paths’: multiply the weights together on each path and add up the resulting monomials.

In this post I’ll explain how to prove the general result, using a certain result about weighted Dyck paths that I’ll also prove. At the end I’ll leave some further questions for the budding enumerative combinatorialists amongst you.

These reverse Bessel polynomials have their origins in the theory of Bessel functions, but which I’ve encountered in the theory of magnitude, and they are key to a formula I give for the magnitude of an odd dimensional ball which I have just posted on the arxiv.

• The magnitude of odd balls via Hankel determinants of reverse Bessel polynomials

In that paper I use the combinatorial expression for these Bessel polynomials to prove facts about the magnitude.

Here, to simplify things slightly, I have used the standard reverse Bessel polynomials whereas in my paper I use a minor variant (see below).

I should add that a very similar expression can be given for the ordinary, unreversed Bessel polynomials; you just need a minor modification to the way the weights on the Schröder paths are defined. I will leave that as an exercise.

I hope you know that a Lawvere theory is a category $T$ with finite products where the objects are all of the form $x^n$ for some object $x$. A model of $T$ is a finite-product-preserving functor $M : T \to \Set$. There’s a category $Mod(T)$ where the objects are models and the morphisms are natural transformations between such functors. Many familiar algebraic structures defined by $n$-ary operations and equations, like groups or vector spaces over some field $k$, can be seen as models of Lawvere theories. So, there’s a Lawvere theory $T$ for which $Mod(T)$ is equivalent to $Grp$, another one that gives $Vect_k$, and so on.

Categories of this sort have been studied a lot and are sometimes called finitary monadic categories or finitary algebraic categories (though sometimes the latter term is used more generally — see the link). These categories always have coproducts, so it’s natural to wonder when the canonical morphism

$$i: M \to M + N$$

is monic. After all, it’s true in $Grp$ and $Vect_k$, and in enough other cases that people sometimes call $i$ the ‘inclusion’ of an object $M$ in $M + N$.

But $i: M \to M + N$ is not always monic in the category of models of a Lawvere theory. Can you think of a counterexample before read on?

I’m looking for a reference. Homotopy theorists love simplicial sets; certain other topologists love simplicial complexes; they are related in various ways, and I’m interested in one such relation.

Let me explain…

John and I are currently enjoying Applied Algebraic Topology 2017 in the city of Sapporo, on the northern Japanese island of Hokkaido.

I spoke about magnitude homology of metric spaces. A central concept in applied topology is persistent homology, which is also a homology theory of metric spaces. But magnitude homology is different.

It was brought into being one year ago on this very blog, principally by Mike Shulman, though Richard Hepworth and Simon Willerton had worked out a special case before. You can read a long post of mine about it from a year ago, which in turn refers back to a very long comments thread of an earlier post.

But for a short account, try my talk slides. They introduce both magnitude itself (including some exciting new developments) and magnitude homology. Both are defined in the wide generality of enriched categories, but I concentrated on the case of metric spaces.

Of course, John’s favourite slide was the one shown.

guest post by David Myers

Proarrow equipments (which also go by the names “fibrant double categories” and “framed bicategories”) are wonderful and fundamental category-like objects. If categories are the abstract algebras of functions, then equipments are the abstract algebras of functions and relations. They are a fantastic setting to do formal category theory, which you can learn about in Mike’s post about them on this blog!

For my undergraduate thesis, I came up with a graphical calculus for working with equipments. I wasn’t the first to come up with it (if you’re familiar with both string diagrams and equipments, it’s basically the only sort of thing that you’d try), but I did prove it sound using a proof similar to Joyal and Street’s proof of the soundness of the graphical calculus for monoidal categories. You can see the full paper on the arXiv, or see the slides from a talk I gave about it at CT2017 here. Below the fold, I’ll show you the diagrams and a bit of what you can do with them.

In June I went to the following conference.

• Applied Topology in Będlewo 2017.

This was held at the Będlewo Conference Centre which is run by the Polish Academy of Sciences’ Institute of Mathematics. Like Oberwolfach it is kind of in the middle of nowhere, being about half an hour’s bus ride from Poznan. (As our excursion guide told us, Poznan is 300km from anywhere: 300 km from Warsaw, 300 km from Berlin, 300 km from the sea and 300 km from the mountains.) You get to eat and drink in the palace pictured below; the seminar rooms and accommodation are in a somewhat less grand building out of shot of the photo.

I gave a 20-minute long, magnitude-related talk. You can download the slides below. Do try the BuzzFeed-like quiz at the end. How many of the ten spaces can just identify just from their dimension profile?

• Instantaneous dimension of finite metric spaces via magnitude and spread

To watch the animation I think that you will have to use acrobat reader. If you don’t want to use that then there’s a movie-free version.

People have been using algebraic topology in data analysis these days, so we’re starting to see conferences like this:

• Applied Algebraic Topology 2017, August 8-12, 2017, Hokkaido University, Sapporo, Japan.

I’m giving the first talk at this one. I’ve done a lot of work on applied category theory, but only a bit on on applied algebraic topology. It was tempting to smuggle in some categories, operads and props under the guise of algebraic topology. But I decided it would be more useful, as a kind of prelude to the conference, to say a bit about the overall history of algebraic topology, and its inner logic: how it was inevitably driven to categories, and then 2-categories, and then $\infty$-categories.

This may be the least ‘applied’ of all the talks at this conference, but I’m hoping it will at least trigger some interesting thoughts. We don’t want the ‘applied’ folks to forget the grand view that algebraic topology has to offer!

For a long time Blake Pollard and I have been working on ‘open’ chemical reaction networks: that is, networks of chemical reactions where some chemicals can flow in from an outside source, or flow out. The picture to keep in mind is something like this:

where the yellow circles are different kinds of chemicals and the aqua boxes are different reactions. The purple dots in the sets X and Y are ‘inputs’ and ‘outputs’, where certain kinds of chemicals can flow in or out.

Our paper on this stuff just got accepted, and it should appear soon:

• John Baez and Blake Pollard, A compositional framework for reaction networks, to appear in Reviews in Mathematical Physics.

But thanks to the arXiv, you don’t have to wait: beat the rush, click and download now!

Or at least read the rest of this blog post….

Dominic Verity and I have just posted a paper on the arXiv entitled “The comprehension construction.” This post is meant to explain what we mean by the name.

The comprehension construction is somehow analogous to both the straightening and the unstraightening constructions introduced by Lurie in his development of the theory of quasi-categories. Most people use the term $\infty$-categories as a rough synonym for quasi-categories, but we reserve this term for something more general: the objects in any $\infty$-cosmos. There is an $\infty$-cosmos whose objects are quasi-categories and another whose objects are complete Segal spaces. But there are also more exotic $\infty$-cosmoi whose objects model $(\infty,n)$-categories or fibered $(\infty,1)$-categories, and our comprehension construction applies to any of these contexts.

The input to the comprehension construction is any cocartesian fibration between $\infty$-categories together with a third $\infty$-category $A$. The output is then a particular homotopy coherent diagram that we refer to as the comprehension functor. In the case $A=1$, the comprehension functor defines a “straightening” of the cocartesian fibration. In the case where the cocartesian fibration is the universal one over the quasi-category of small $\infty$-categories, the comprehension functor converts a homotopy coherent diagram of shape $A$ into its “unstraightening,” a cocartesian fibration over $A$.

The fact that the comprehension construction can be applied in any $\infty$-cosmos has an immediate benefit. The codomain projection functor associated to an $\infty$-category $A$ defines a cocartesian fibration in the slice $\infty$-cosmos over $A$, in which case the comprehension functor specializes to define the Yoneda embedding.

Australia’s Prime Minister Malcolm Turnbull, today:

The laws of mathematics are very commendable, but the only law that applies in Australia is the law of Australia.

The context: Turnbull wants Australia to undermine encryption by compelling backdoors by law. The argument is that governments should have the right to read all their citizens’ communications.

Technologists have explained over and over again why this won’t work, but politicians like Turnbull know better. The recent, enormous, Petya and WannaCry malware attacks (hitting British hospitals, for instance) show what can happen when intelligence agencies such as the NSA treat vulnerabilities in software as opportunities to be exploited rather than problems to be fixed.

Thanks to David Roberts for sending me the link.