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.

May 6, 2008

Theorems Into Coffee II

Posted by John Baez

Nobody instantly solved my first coffee challenge, but I hope that interest is brewing. Maybe some of you will perk up if I throw another $15 in the pot?

It’s a slight variation on the same theme: taking a nice category where the morphisms are m×nm \times n matrices, interpreting it as a PROP, and asking what sort of algebraic gadget is defined by this PROP.

As before, I would love to have access to a proof of this result. So, under the same terms as before, I’ll send a $15 Starbucks gift certificate (or check) to anybody who gives me, in LaTeX, a well-written rigorous proof of the following theorem:

Let Mat()Mat(\mathbb{Z}) be the category whose objects are natural numbers and whose morphisms f:nmf : n \to m are m×nm \times n matrices of integers, with composition being given by matrix multiplication. Think of Mat()Mat(\mathbb{Z}) as a symmetric monoidal category in the obvious way where the tensor product of objects nn and mm is n+mn + m, and the tensor product of morphisms is direct sum of matrices.

Theorem: Mat()Mat(\mathbb{Z}) is the PROP for bicommutative Hopf algebras.

In a bit more detail: we can talk about the models — I guess most people say ‘algebras’ — of a PROP in any symmetric monoidal category CC. I’m claiming that the category of models of Math()Math(\mathbb{Z}) in CC is equivalent to the usual category of ‘bicommutative Hopf algebras’ in CC. You might prefer to call them ‘bicommutative Hopf objects’, since no linear algebra is involved. They’re just bicommutative monoid objects as defined last time, but now also equipped with an antipode satisfying the usual conditions in the definition of a Hopf algebra — written out in diagrammatic form, of course.

The point is that the antipode S:HHS: H \to H of our Hopf object is an operation with one input and one output. It should thus correspond to a 1×11 \times 1 matrix of integers. We’ll take this matrix to be (1)(-1). The following equation then encodes the fact that if we comultiply something, apply the antipode to one of the outputs, and then multiply them, we get the unit:

1+(1)=01 + (-1) = 0

Anyone who can prove the last theorem should be well on the way to proving this one too. I would love for people to collaborate, though perhaps this ‘prize’ format doesn’t encourage that. Be nice! — coffee tastes better shared with a friend.

If you need some basic information on PROPs, this paper could be a good place to start, along with the Wikipedia article I cited before:

This book has a lot more detail:

Posted at May 6, 2008 4:57 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1671

21 Comments & 1 Trackback

Re: Theorems Into Coffee II

Hi,

The proof of the fact that Mat(N) is the PROP for bicommutative bialgebras can be found in the draft version of my paper where I construct the “PRO” corresponding to a category of games and strategies interpreting a fragment of first-order propositional logic (comments are of course very welcome!). I think that the credits and coffees for this result should go to Albert Burroni and Yves Lafont who introduced the general methodology for constructing such PROs. As far as I know, the notions of polygraph and canonical form used to prove the result were introduced by Albert in Higher dimensional word problem with application to equational logic and deeply studied and refined by Yves in Towards an Algebraic Theory of Boolean Circuits. I haven’t checked the details, but this method should extend to the case of Mat(Z) without major difficulties (I can give a notion of canonical form for this PROP or more details if anyone is interested).

Posted by: Samuel Mimram on May 6, 2008 6:14 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

This is just a comment on history. What is called polygraph by Burroni and his group is actually a computad, the notion introduced by Ross Street 14 years before Burroni.

Posted by: Michael Batanin on May 7, 2008 1:37 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

Samuel wrote:

The proof of the fact that Mat()\mathbb{N}) is the PROP for bicommutative bialgebras can be found in the draft version of my paper where I construct the “PRO” corresponding to a category of games and strategies interpreting a fragment of first-order propositional logic (comments are of course very welcome!)

Cool! I’ll study this paper more carefully as soon as I can.

Is there any chance that you’ll be at the Algebraic Topological Methods in Computer Science conference in Paris this summer? Yves Lafont is one of the organizers. If you attend, and if I’m able to follow the proof of your Theorem 14, I can give you your coffee prize there.

I think that the credits and coffees for this result should go to Albert Burroni and Yves Lafont who introduced the general methodology for constructing such PROs.

Winners are, of course, free to pass on the coffee to anyone they wish to choose!

Posted by: John Baez on May 8, 2008 3:36 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

Yes, I had planned to attend to ATMS. I’d be glad to discuss with you there!

Posted by: Samuel Mimram on May 11, 2008 12:39 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

Great! I just noticed (from reading your paper) that your advisor is Paul-André Melliès. I plan to visit him from June 6th to August 15th! So, there should be more chances to talk, besides that conference.

Posted by: John Baez on May 15, 2008 7:55 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

I am intrigued by this result.

I also have a question. Greg Kuperberg has shown that the category of cobordisms between surfaces is the PROP for involutory Hopf algebras; see

  • Involutory Hopf algebras and 3-manifold invariants Internat. J. Math. 2 (1991), no. 1, 41–66, arXiv:math/9201301 .

Then we should see Mat(Z) as a quotient of this symmetric category. This might even give a strategy for proving the result on Mat(Z).

Posted by: Bruce Westbury on May 7, 2008 1:04 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

Good point, Bruce! Yes, so we should get a morphism of PROPs from some category of cobordisms between surfaces (I’m fuzzy about the details) to Mat()Mat(\mathbb{Z}).

How does this work, explicitly? How do we get a matrix of integers from such a cobordism?

If we restrict to invertible cobordisms, do we get an interesting homomorphism from some group to GL(n,)GL(n,\mathbb{Z})?

Posted by: John Baez on May 8, 2008 5:40 AM | Permalink | Reply to this

Re: Theorems Into Coffee II

I don’t know how to do this explicitly. This seems to me to be an interesting exercise which would give some insight into both PROPs.

Can I offer a small inducement to get someone else to do this?

Posted by: Bruce Westbury on May 8, 2008 7:50 AM | Permalink | Reply to this

Re: Theorems Into Coffee II

Kuperberg’s paper defines the “Heegard category” to be something like the free compact symmetric monoidal category on an involutory Hopf object with invertible dimension for which the trace is a left and right integral and for the cotrace is a cointegral. He doesn’t seem to quite come out and assert an equivalence of symmetric monoidal categories between this “Heegard category” and a category defined in terms of 3-manifolds, but he comes darn close. It’s probably just my impatience that seeks a crisper statement of equivalence. Does anyone know of subsequent work that asserts an equivalence of symmetric monoidal categories like this?

Posted by: John Baez on May 8, 2008 4:01 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

Here is something I missed. In Greg’s paper we have a Hopf algebra and its dual. Formally this means we have a spherical category and informally it means we are restricting to finite dimensional Hopf algebras.

The categories Mat(N) and Mat(Z) do not include the dual Hopf algebra. Therefore the bicommutative quotient of Greg’s Heegard category will be larger.

In Samuel Mimram’s paper his category Games is spherical and has an extra relation which he calls qualitative.

The obvious question then is: is there a nice description of the spherical versions of Mat(N) or Mat(Z)?

This may (or may not) be related to something else that was puzzling me. I was trying to think how we might get a functor from cobordisms to Mat(Z). The first thought is that on objects we send a surface to the first homology group. However this has rank twice the expected rank. It also has a symplectic form.

Posted by: Bruce Westbury on May 8, 2008 6:25 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

I don’t claim to deserve any coffee for that, but I don’t think all bicommutative Hopf bialgebras are involutive (1){}^{(1)}, are they?

If not, then the theorem should probably be stated for involutive bicommutative Hopf algebras, right?

(1) From wikipedia, a Hopf bialgebra is involutive when its antipode SS is such that S 2=idS^2 = \mathit{id}.

Posted by: Tom Hirschowitz on May 7, 2008 2:54 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

Yes, actually they are! I really didn’t deserve any coffee.

Posted by: Tom Hirschowitz on May 7, 2008 2:56 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

Tom wrote:

I really didn’t deserve any coffee.

But maybe you needed some.

Don’t feel bad — I was confused about this issue for a long time. Yes, bicommutative Hopf algebras are automatically involutory.

Posted by: John Baez on May 8, 2008 5:34 AM | Permalink | Reply to this

Re: Theorems Into Coffee II

reference please or the argument if simpleminded

jim

Posted by: jim stasheff on May 8, 2008 1:15 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

I have in mind a result that says that the square of the antipode is conjugation by an invertible element. I don’t recall a reference.

If this is correct then a commutative Hopf algebra is involutory.

Posted by: Bruce Westbury on May 8, 2008 2:38 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

Exercise 10(a) to the first chapter of Waterhouse’s ‘Introduction to affine group schemes’?

Posted by: lieven on May 8, 2008 3:32 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

Hello !

I have a question/comment (it might be stupid but …) about John’s first coffee challenge.

1) Denote by C the (Z-linear) PROP of bicommutative bialgebras. As a free Z-module, the space C(2,2) is generated by three elements (identity, permutation and product followed by coproduct).

I might have misunderstood the challenge itself. But it seems to me that there is no chance for the existence of an isomorphsim C –> Mat(Z).

2) To my opinion a more reasonable statement should be that there is an isomorphism between the PROP Mat(Z) and the PROP of commutative (or cocommutative) bialgebras.
Let me explain why.

a) Denote by BiAlg the (Z-linear) PROP of bialgebras. Enriquez and Etingof (see Proposition 6.2 of math/0306212) found a Z-linear basis of BiAlg(n,m) (see also example 59 in Markl’s review math/0601129).

The main idea is that using compatibility between product and coproduct you can write any composition of many of them in a unique way with all products on the right and all coproducts on the left.

As far as I understand the basis can be described as follows :
a Z-linear basis of BiAlg(n,m) is given by triples (s,u,v) where
* s is a permutation of [k].
* u=((u_1,p_1),…,(u_k,p_k)), where (u_1,…,u_k) is a k-partition of n and each p_i is a permutation of [u_i].
* v=((v_1,q_1),…,(v_k,q_k)), where (v_1,…,v_k) is a k-partition of m and each q_i is a permutation of [v_k].

b) for comBiAlg, the PROP of commutative bialgeras, the basis is the same but without the p_i’s.

c) Now I think I can construct a map from such triples (the ones defining the basis of comBiAlg) to Mat(Z) that is compatible with the PROP-structure.

c1) Let us first forget about q_i’s (and thus construct a map from C to Mat(Z)).
- to each u_i associate the line-matrix of lenght u_i with all entries being 1’s. Then construct a matrix
U:=diag(u_1,…u_k)
which will have the following form
111000000
000110000
000001111
if u_1=3,u_2=2 and u_3=4 .
- to each v_j associate the column-matrix of lenght v_j with all entries being 1’s.
Construct a matrix V similarly to the above construction for U.
- then multiply VSU, where S is the permutation matrix for s.

c2) for non-trivial q_i’s one has to take a different column-matrix v_i with entries being 1’s and 0’s (with a least one 1).
It can be constructed a s follows :
- consider the permutation matrix of q_i.
- if the element on the top-left of this matrix is 1 (resp. 0), then the first entry of v_i is 1 (resp. 0).
- remove the first line and first column of the permutation matrix.
- do the same with the new matrix you obtain to find the second entry of v_i
- etc …

The map constructed in c1) is NOT an isomorphism , because of 1).

I did not check if the map c2) is, but it seems more reasonable. Also in the case c2) one has to check that it is a morphism of PROPs (in the case c1) it is obvious).

This comment is very much longer than what I thought first.
Maybe I am very far from the orignial question, and I hope I did not write too many meaningless things.

Damien

Posted by: Damien on May 15, 2008 11:25 AM | Permalink | Reply to this

Re: Theorems Into Coffee II

I misread the challenge … it was about Hopf algebras (not only bialgebras).

OK, so forgetting about q_i’s and p_i’s, I think I have constructed in my previous message an injective morphism of PROPs
bicomBiAlg –> Mat(Z) (see point c1).

The challenge is now to incorporate the antipode in order to extend it to an isomorphism bicomHopf –> mat(Z).

Posted by: Damien on May 15, 2008 11:49 AM | Permalink | Reply to this

Re: Theorems Into Coffee II

Damien wrote:

I misread the challenge… it was about Hopf algebras (not only bialgebras).

I think I have constructed in my previous message an injective morphism of PROPs

bicomBiAlgMat()bicomBiAlg \to Mat(\mathbb{Z})

Perhaps you were accidentally working on my first Theorems Into Coffee challenge. There I asked people to show Mat()Mat(\mathbb{N}) (the PROP whose operations with nn inputs and mm outputs are m×nm \times n matrices of natural numbers) is the PROP for bicommutative bialgebras. If you construct an injective morphism of PROPS

bicomBiAlgMat()bicomBiAlg \to Mat(\mathbb{Z})

and then show its range is exactly Mat()Mat(\mathbb{N}), you’ve solved that problem!

However, winning the coffee requires that you write up the proof in LaTeX before anyone else, and it seems that Samuel Mimram is already close to having won the first Theorems Into Coffee challenge. I’ve been too busy running around to carefully check his solution, but last Wednesday he put it on the arXiv.

But, the Mat()Mat(\mathbb{Z}) problem remains open — though I know two café regulars who claim to have solved it and only need to write up the solution. And, I will soon issue a few more challenges regarding PROPs.

Posted by: John Baez on May 15, 2008 7:38 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

Dear John,

yes, I was actually confusing the first and second challenge.

But I also made another mistake by considering the PROP of nonunital and noncounital bicommutative bialgebras.

It’s true that Samuel seems to have proved the first statement. Anyway, I am not competing for the coffee (being part of the few mathematicians that do not like coffee!).

I wrote a small (unfinished) note about my argument (which I have cleaned).

I have the feeling that my proof is more or less equivalent to Samuel’s one, but maybe a little shorter.

Best,
Damien

Posted by: Damien on May 15, 2008 9:30 PM | Permalink | Reply to this

Re: Theorems Into Coffee II

I think that a proof along the lines you describe can be made to work I think, however there are still points to improve and formalize:
- the permutation σ in your canonical form is not unique because of (co)commutativity but you should be able to show that there is a bijection between possible σ in both worlds
- actually Δ and m are also not unique because of the equation δoμ=1 (but maybe is this related to your remark that “all cycles can be removed”?)
- showing that every morphism of a qualitative bicommutative bialgebra can be put in this form requires a rewriting system and it is really not obvious to show termination for such rewriting systems

Posted by: Samuel Mimram on May 20, 2008 8:54 AM | Permalink | Reply to this
Read the post Theorems Into Coffee III
Weblog: The n-Category Café
Excerpt: What is the symmetric monoidal category of finite sets and partially defined functions the PROP for? Prove your answer and win some coffee!
Tracked: May 16, 2008 6:32 PM

Post a New Comment