# Complexity of coherence diagrams in an $n$-category

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$$?

• It is not even clear to me if it has been proved a finite number of coherence diagram is enough for each $n$. The only definition of weak n-category I can think that is expressed in terms of "operations with coherence diagrams" are the Grothendieck/Batanin/Maltsitioniotis style definition, and in their standard formulation they involve an infinite number of coherence diagrams (due to them being written in a "unbiased" style). Jun 19, 2022 at 22:02

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. thesis1 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.

• Interesting! Perhaps you could use stabilization to show your result applies to all (symmetric/sylleptic/braided etc) monoidal n-categories as well, at the very least. I wonder then if the coherence diagrams of n-categories are necessarily a subset of those for monoidal n-categories, as they are in n=1. Jun 22, 2022 at 10:20
• @JackRomo Sorry, the statement I formulated was needlessly narrow. The same result holds for $\mathbb{E}_n$-monoids in an arbitrary $(k+1,1)$-category. In particular it holds for the $(k+1,1)$-category of $(k,m)$-categories. Does this address your further question? Jun 22, 2022 at 10:26
• Hmm, I suppose you could use that to look at the hom k-groupoid from a discrete singleton (k, m)-category to any (k, m)-category C and infer the coherence conditions on C (assuming they’re all invertible), in particular that they’re finite. Is that accurate? Jun 22, 2022 at 12:29
• @JackRomo Not sure I'm following. My comment was meant to suggest that adding monoidal structures into the mix doesn't affect the difficulty of the question Jun 22, 2022 at 13:17
• Right, I see. In my first comment I suggested monoidal structure since by stabilization, monoidal k-categories can be seen as (k+1)-categories with one object, ie. with a connected space of objects. So your method could get the coherence conditions on an arbitrary monoidal k-category. Jun 22, 2022 at 15:41

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!

• In my answer, I think I'm assuming that we have access to a presentation of $Spaces_k$ as a quasicategory $X$ where we consider it "unproblematic" to talk about a simplex in $X$. However, if we construct $X$ by taking the homotopy coherent nerve of something, we might consider that each time we write down a simplex in $X$, we have to assemble some more primitive "coherence data". So perhaps in some sense there are more "coherence diagrams" required than what I've said here. (Although most likely we would consider this more a question of the size rather than number of coherence diagrams.) Jun 22, 2022 at 18:45