Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: deprecated: logic

Topic: word problem for braided monoidal categories

Antonin Delpeuch (May 11 2021 at 06:38):

how would you determine if two morphisms in a braided monoidal category are equal up to the braided monoidal axioms? I was surprised not to be able to find any algorithm for it. So far I have only been able to show that it is at least as hard as untying knots (https://arxiv.org/abs/2105.04237). Any ideas?

Amar Hadzihasanovic (May 12 2021 at 06:55):

Hi Antonin, nice work (although I've only looked at it quickly)! But I'm not convinced by the implication on the word problem for tricategories. The reason is that while braided monoidal categories are in a sense equivalent to doubly degenerate tricategories, it is not true that a free braided monoidal category is a free tricategory through the comparison functors. So you can't reduce the word problem for braided monoidal categories to the word problem for tricategories.

Amar Hadzihasanovic (May 12 2021 at 06:56):

What you can certainly do is reduce the word problem for braided strict monoidal categories to the one for Gray-categories.

Amar Hadzihasanovic (May 12 2021 at 07:00):

I imagine that the one for non-strict monoidal reduces to the one for strict monoidal, so you do have the implication (w.p. for braided monoidal cats) -> (w.p. for Gray-cats).

Amar Hadzihasanovic (May 12 2021 at 07:07):

If you look at Cheng-Gurski Theorem 2.1 you'll see that a doubly degenerate tricategory has a lot more "weak" structure that's declared to be identites when you turn a braided monoidal category into a tricategory, whence the loss of freeness...

Antonin Delpeuch (May 13 2021 at 16:15):

Ah interesting! Then there is a subtlety I haven't grasped here. I took Gray-categories and tricategories as equivalent, but I guess I don't understand that equivalence well enough to understand why one word problem in one is not equivalent to a word problem in the other?

David Michael Roberts (May 13 2021 at 16:17):

Maybe something due to Bicat is not triequivalent to Gray?

John Baez (May 13 2021 at 17:28):

Amar wrote:

The reason is that while braided monoidal categories are in a sense equivalent to doubly degenerate tricategories, it is not true that a free braided monoidal category is a free tricategory through the comparison functors. So you can't reduce the word problem for braided monoidal categories to the word problem for tricategories.

John Baez (May 13 2021 at 17:35):

Let's think about this a minute. Let X be a tricategory given by finitely many generators and relations, and X' its equivalent Gray-category. Let f and g be two 3-morphisms in X, described in terms of generators. We're trying to see if they're equal. We map them via our equivalence to 3-morphisms f' and g' in X'. f and g will be equal iff f' and g' are equal. Say we know how to solve the word problem for Gray-categories. Then we can decide if f' and g' are equal if we have a presentation of X' with finitely many generators and relations, and we know how to express f' and g' in terms of these generators.

But how do we get this presentation, and this way of expressing f' and g'?

John Baez (May 13 2021 at 17:35):

At the very least it seems there's some work to be done here.

Amar Hadzihasanovic (May 13 2021 at 18:39):

@John Baez Yes, I agree. I think the 'standard' semi-strictification of a tricategory, just like the strictification of a monoidal category, will certainly not be finitely generated except in very simple cases (e.g. the strictification of a monoidal category has one generating object for each finite sequence of objects of the original monoidal category).

Amar Hadzihasanovic (May 13 2021 at 18:41):

Besides, even if we could make this work (i.e. solve the w.p. for a tricategory by embedding it into a Gray-category and using a solution for the w.p. of the Gray-category), it would only tell us that the word problem for tricategories is not harder than the word problem for Gray-categories (which is at least as hard as the word problem for braided strict monoidal categories). So we still would not have the intended implication.

Amar Hadzihasanovic (May 13 2021 at 18:46):

That said, I do think it is likely, given Jamie's and Antonin's result, that one can solve unknotting from the w.p. for tricategories. It's just that it's not a corollary of their result: I'm afraid one may have to rephrase their proofs directly in terms of tricategorical diagrams...

John Baez (May 13 2021 at 18:58):

Okay, so maybe one needs to handle the word problem for such infinitely generated structures; the generators and relations are certainly recursively enumerable.

Antonin Delpeuch (May 13 2021 at 19:17):

Actually it is not clear to me why it makes a difference whether the corresponding tricategory is finitely or countably generated. As long as the structures are freely generated, without any axioms between the generators, then as far as word problems are concerned, why do we care? To define an instance of the word problem you only need to consider the generators that occur in the word problem instance (plus their domains/codomains recursively, but that only adds a finitely many generators).
For me the important question is whether the equivalence mapping from Gray categories to tricategories (I think that's the only direction we need, no?) is something that can be computed polynomially on 3-morphisms.

Antonin Delpeuch (May 13 2021 at 19:18):

I have to admit that I don't actually have any idea what this mapping looks like in practice, I should have checked before claiming this corollary…

John Baez (May 13 2021 at 19:22):

I thought the idea was to convert a problem for tricategories into a simpler problem for Gray categories; if so we'd need the map going that way, right?

John Baez (May 13 2021 at 19:23):

Either way it does, we don't need this reduction to be computable in polynomial time is we're just asking about the "solvability of the word problem", which is about computability, not polynomial time computability.

But if we want solvability in polynomial time, then we'd need the reduction to be doable in polynomial time.

Antonin Delpeuch (May 13 2021 at 19:23):

If the goal is to say that the w.p. for tricategories is at least as hard as the unknotting problem (which is what we claim), then I believe we only need to be able to convert a braided monoidal morphism (so a 3-cell in a Gray category) to a 3-cell in a tricategory.

Antonin Delpeuch (May 13 2021 at 19:24):

I assumed that that conversion was straightforward but maybe it's indeed not, I need to look into it :)

John Baez (May 13 2021 at 19:25):

Right. I was talking about something else: proving that the word problem is solvable for tricategories, by reducing it to the perhaps easier word problem for Gray-categories.

John Baez (May 13 2021 at 19:25):

One thing to keep in mind is that a Gray category is not a special case of a tricategory.

Antonin Delpeuch (May 13 2021 at 19:26):

ok! I have literally no intuition as to why the w.p. for one might be easier than the other, really.

John Baez (May 13 2021 at 19:27):

I don't either, except that the definition of tricategory is a lot longer than the definition of Gray category: there's just a lot more stuff to keep track of.

Antonin Delpeuch (May 13 2021 at 19:32):

I think I'll just correct the claim to be about the w.p. of Gray categories rather than tricategories, because that's what I really meant…

Amar Hadzihasanovic (May 13 2021 at 20:08):

I also can't remember the specifics of the Gray strictification of tricategories but, again, I'm afraid it's safe to assume that it won't produce a free Gray-category from a free tricategory. Thinking of the simpler monoidal category strictification, it must contain isomorphisms between the “free” tensor product $(A,B)$ and the original tensor product $A \otimes B$, and a free strict monoidal category cannot contain any isomorphisms except the structural ones.

Amar Hadzihasanovic (May 13 2021 at 20:09):

Of course it's not impossible that, while not free, the resulting Gray-category still has a decidable word problem; but it's still more work to do.

Antonin Delpeuch (May 14 2021 at 05:38):

OK! But then again the direction I care about is the reverse one that you have in mind: I have a free Gray category and I want to turn that into a tricategory. Perhaps that has more chances of resulting in a free tricategory?

Amar Hadzihasanovic (May 14 2021 at 10:11):

So, iirc there are two different embeddings of Gray-categories into tricategories: a "left-handed" one and a "right-handed" one, let's call them $T_L$ and $T_R$. Restricted to doubly degenerate Gray-cats, the ones that correspond to braided strict monoidal categories, they correspond to a choice of whether to interpret a braiding as the "clockwise" or "counterclockwise" exchange of wires in 3d.

Amar Hadzihasanovic (May 14 2021 at 10:11):

Neither $T_L$ nor $T_R$ send free Gray-cats to free tricats.

Amar Hadzihasanovic (May 14 2021 at 10:14):

Something you can do, I'm pretty sure, is construct both a free tricategory and a free Gray-category (in fact a free braided strict monoidal category) on the same data, i.e. a monoidal signature. Let's call $F_T$ and $F_G$ the two functors that do this, defined on an appropriate category of monoidal signatures.

Amar Hadzihasanovic (May 14 2021 at 10:16):

A free braided monoidal category is isomorphic to its "dual" where braidings and inverse braidings are exchanged, so you will have that $T_L \circ F_G$ and $T_R \circ F_G$ are naturally isomorphic functors.

Amar Hadzihasanovic (May 14 2021 at 10:19):

Now I think it's plausible that you can quotient the free tricategory to get the free Gray-category (as embedded through one of $T_R$ or $T_L$) on the same signature, and that this quotient should be a weak equivalence.

Amar Hadzihasanovic (May 14 2021 at 10:20):

So let's assume that the best possible thing is true, that is, we have a natural transformation $F_T \Rightarrow T_L \circ F_G$ whose components are all weak equivalences.

Amar Hadzihasanovic (May 14 2021 at 10:23):

This is still going in the wrong direction for what your goal is. There's no way there are functors going the other way.

Amar Hadzihasanovic (May 14 2021 at 10:25):

No matter how you put it, I'm afraid Gray-categories have "more equations" than tricategories so their word problem is going to be at least as hard as the one for tricategories.

Amar Hadzihasanovic (May 14 2021 at 10:29):

Nevertheless I think there is a decent chance that the encoding of the unknot problem into the w.p. for braided strict monoidal categories can be tweaked to an encoding into the w.p. for tricategories. I'm pretty confident that that is the best course of action, even though it is more work.

Amar Hadzihasanovic (May 14 2021 at 10:50):

By the way, the adjunctions between Gray-categories, braided strict monoidal categories, and coloured probs (which include in particular free braided strict monoidal cats) and their main properties are spelled out in Section 2 of my most recent paper. I don't discuss tricategories though.