Complexity of coherence diagrams in an $n$-category

Question

As we proceed from categories to bicategories to tricategories to tetracategories, the coherence diagrams expand at an alarming rate, taking up a page, then 5 pages, then 51 pages. There is a shared view that an algebraic definition of $n$-category for high $n$ will be impractically enormous. While I agree with this opinion, I don't actually know any formal complexity result that specifies how quickly the coherence diagrams for an $n$-category blow up in scale with respect to $n$. One could perhaps look at associahedra for the associativity conditions, but this only handles one part of the problem. (I'm also not quite sure how one would define the 'complexity' of a diagram - perhaps by its number of objects and morphisms, for instance.)

Does anyone know any results or literature that give some insight into the precise expected scale of coherence diagrams in a weak $n$-category for general $n$?

Answer 1

This is not a full answer to the question but it was too long for a comment.

Depending on your conventions, "weak $n$-categories" might mean "$(n,n)$-categories" which are a special case of $(\infty,n)$-categories. If this is indeed the case, some things can be said. First, the question also makes sense for $\mathbb{E}_n$-monoids which (upto completion) may be thought of as $(\infty,n)$-categories whose space of objects is connected. Let me focus on that case.

In my Msc. thesis¹ I study the interplay between coherence and arity for $\cal O$-monoids where $\cal O$ is an $\infty$-operad and arity is, roughly speaking, the $k$ in $x_1 \otimes \cdots \otimes x_k$. In particular I show that the coherence data for $k$-truncated, $\mathbb{E}_n$-monoids is concentrated in arities $\le k+3$. Combining this with the fact that the $\infty$-operad $\mathbb{E}_n$ has finitely many cells in every arity, it follows that specifying an $(n,n)$-category with a connected space of objects involves only finitely many coherence diagrams.

Unfortunately, I don't have anything definitive to say about the general case. However, the tools I use seem very robust and I have no reason to believe that similar techniques might not be applicable beyond the connected case. I haven't attempted this though, as it is quite far from the original application I had in mind.

---

^{1 A preprint will soon appear on the Arxiv.}

Answer 2

Here are some off-the cuff ideas.

First, as I think Saal's answer starts to hint at, there's no particular reason to restrict attention to $(n,n)$-categories. It seems more natural to think about $(n+k,n)$-categories for various values of $n,k$.

To fix ideas, let's start with $n=1$. A $(1+k,1)$-category is a 1-category whose hom-spaces are all $k$-truncated. Let $Spaces_k$ denote the $\infty$-category of $k$-truncated spaces. Also, let's not worry about Rezk completeness for the moment.

We know that the simplex category $\Delta$ is dense (in the $Spaces$-enriched sense) in $(\infty,1)$-categories. So it's also dense in $(1+k,1)$-categories. But it's reasonable to guess that in the $Spaces_k$-enriched sense, there is a subcategory of $\Delta_{\leq [K]} \subset \Delta$ with $K+1$-many objects, which is already dense in $Cat_{(k+1,1)}$. But what is $K(k)$? When $k=1$, we can take $K = 2$. I suspect that in general we can take $K = k+1$. This would be in line with the way people often treat stacks via truncated simplicial objects, with the truncation level depending on how truncated the stacks are. At any rate, finding such a $K(k)$ is something which should be readily computable -- if I feel less lazy later I might try to work it through here.

Now, $\Delta_{\leq [K]}$ is finite as a $(1,1)$-category. But as an $(\infty,1)$-category, this is not so clear. Nevertheless, its nerve has only finitely many nondegenerate simplices in each degree. Since we're mapping only into $Spaces_k$, we only need to go up to the $k+1$-simplices of its nerve.

So we see that $Cat_{(k+1,1)}$ should be model-able in terms of presheaves valued in $Spaces_k$ on the finite simplicial set $sk^{k+1}\Delta_{\leq K}$ (where I think that $K = k+1$). The Segal conditions are not additional coherence diagrams, but just conditions that certain maps are isomorphisms.

The number of coherence diagrams in this model is the number of $\leq k+1$-simplices in the nerve of $\Delta_{\leq k+1}$. This is the number of strings of $k$ composable morphisms in the category. We can cut down the model slightly by restricting to the 1-object subcategory on $[k+1]$ itself, since everything else is a retract of that object and so the category of presheaves is the same. The number of nondegenerate $l$-simplices is $|Hom_\Delta([k+1],[k+1])|^{l-1}$. I think that $|Hom_\Delta([a],[b])|$ may be related to Stirling numbers? At any rate, we get an upper bound of $(k+1)^{(l-1)(k+1)}$. Adding these up from $l=0$ to $l=k+1$, we get an upper bound of something like $(k+1)^{(k+1)^2}$.

To do something similar for higher values of $n$, you could work with analogous full subcategories of Joyal's category $\Theta$, for instance.

Anyway, those estimates are pretty rough. But I wouldn't be surprised if it's not too much bigger than what a "sharp" upper bound would give you!