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: theory: category theory

Topic: polynomial functors

Jules Hedges (May 07 2020 at 14:09):

I want to draw attention and start a discussion thread on @David Spivak's new preprint https://arxiv.org/abs/2005.01894 on the category of polynomial functors

Jules Hedges (May 07 2020 at 14:11):

I suspect this category might be very folkloric, I wonder if anyone's seen it in anything old? (There's a cluster of literature beginning with https://www.cs.nott.ac.uk/~psztxa/publ/fossacs03.pdf and Michael Abbott's thesis, which I already told David about, which studies this category)

Jules Hedges (May 07 2020 at 14:12):

Bob Atkey also wrote me this: "There's even more structure in Poly! Tamara von Glehn's thesis shows that it is a model of dependent types with an equality type that refutes functional extensionality. Also, there's an interesting skew-monoidal product related to selective functors."

Jules Hedges (May 07 2020 at 14:16):

David told me about this category over a year ago, and explained it as "it's like locally ringed spaces, except you replace local rings with sets and also replace topological spaces with sets". So for a while we called it "setted sets". So I wonder if it already appears in Grothendieck or something equally old and in French?

Jules Hedges (May 07 2020 at 14:17):

(Since it looks like I'm just bashing it, I should add that I'm extremely excited about this paper)

Exequiel Rivas (May 07 2020 at 14:25):

@Joachim Kock 's notes on polynomial functors has a section of historical remarks, and probably knows much more about the history of this category.

Jules Hedges (May 07 2020 at 14:34):

http://mat.uab.es/~kock/cat/polynomial.pdf (long pdf!)

Nathanael Arkor (May 07 2020 at 14:58):

Part of the difficulty with finding references to properties of polynomial functors is that they're spread across both category theory (as "polynomial functors") and computer science (as "indexed containers").

Nathanael Arkor (May 07 2020 at 15:04):

Another thing to be aware of is that sometimes results are stated just for polynomials in $\mathbf{Set}$, like in @David Spivak's new preprint, and some for arbitrary categories with pullbacks. Some of the properties stated in the preprint are not true for the category of polynomials in an arbitrary category.

(=_=) (May 07 2020 at 16:28):

This $\textrm{Poly}$ is the same one in $\textrm{\S}$ 2.5 of Kock's notes, I take it?

(=_=) (May 07 2020 at 16:51):

Nathanael Arkor said:

Part of the difficulty with finding references to properties of polynomial functors is that they're spread across both category theory (as "polynomial functors") and computer science (as "indexed containers").

Over on the category-theoretic side, there are some interesting applications of polynomial functors (and monads) to topology. It'd be interesting to see how they can be interpreted through this lens (pun somewhat intended).

Nathanael Arkor (May 07 2020 at 16:55):

Rongmin Lu said:

This $\textrm{Poly}$ is the same one in $\textrm{\S}$ 2.5 of Kock's notes, I take it?

I believe it's the category $\mathbf{Set}[X]$ defined in §2.1 of the notes. $\mathbf{Poly}$ of Kock's notes restricts to cartesian natural transformations.

(=_=) (May 07 2020 at 17:01):

Nathanael Arkor said:

Rongmin Lu said:

This $\textrm{Poly}$ is the same one in $\textrm{\S}$ 2.5 of Kock's notes, I take it?

I believe it's the category $\mathbf{Set}[X]$ defined in §2.1 of the notes. $\mathbf{Poly}$ of Kock's notes restricts to cartesian natural transformations.

Thank you. I think restricting to Cartesian natural transformations can be useful. In the case of lenses, which can be viewed as an optic associated to a special case of polynomial functors, I think this gives you lawful lenses. (I haven't verified this, this is something I've heard in a seminar somewhere.)

Jules Hedges (May 07 2020 at 17:12):

Woah, that would be really amazing if that's true

Jules Hedges (May 07 2020 at 17:13):

I'm not sure the claim typechecks though, it doesn't make sense to talk about lawful lenses between arbitrary objects of the category

(=_=) (May 07 2020 at 17:13):

This was from a seminar at Macquarie by Mike Johnson pre-Covid. I have notes somewhere that I need to dig up.

(=_=) (May 07 2020 at 17:18):

In the context of data manipulation, lawfulness is desirable for safety purposes. Even there, however, there are also instances where you want lenses to be less lawful.

(=_=) (May 07 2020 at 17:21):

Anyway, all I'm trying to say is that Cartesian natural transformations came up in the discussion of lawfulness during Mike's seminar. It's 3 in the morning here and I'll look at this in more detail later.

Jules Hedges (May 07 2020 at 18:29):

Rongmin Lu said:

It's definitely more restrictive, but I'm not sure what you mean by "arbitrary objects of the category" and why it doesn't "typecheck".

Not totally sure, I was kinda thinking out loud, but in the case of the category I call "bimorphic lenses" (which is apparently equivalent to the full subcategory of monomials) has objects of the form $(a, b)$ (corresponding to the monomial $ax^b$), but you can only write the definition of lawful lenses for lenses of the form $(a, a) \to (c, c)$

(=_=) (May 07 2020 at 18:42):

Right. And since I can't sleep without correcting my mistake...

I think in Kock's notes, it's stated in $\textrm{\S}$ 2.1 that "every natural transformation between polynomial functors factors as a representable one followed by a cartesian." In the case of lenses, the Cartesian thing is the put. Often, though, you want to relax the Cartesian assumption. That got garbled into the "amazing" thing that's surely not true.

Jules Hedges (May 07 2020 at 18:45):

Still very much shooting from the hip here, but it sounds like how every lens $(a,b) \to (c,d)$ factors in the form $(a,b) \to (c,b) \to (c,d)$ which comes from the fact that lenses are fibred over sets, so that's a vertical and a cartesian morphism. I'm not sure it's the same sense of "cartesian" or not!

(=_=) (May 08 2020 at 08:17):

The sense in which Kock means "Cartesian morphisms" (actually, "Cartesian natural transformations") is defined in between Lemma 2.1.5 and Remark 2.1.6. It looks like the same definition as the one in the nLab.

(=_=) (May 10 2020 at 00:23):

Somewhat off-topic, but re. your musings on quantum machine learning, this is actually an emerging research area.

Was daydreaming and it suddenly hit me that "quantum machine learning" actually makes total sense and isn't (just) buzzword soup. Machine learning is at least half linear algebra, and linear algebra is home territory for quantum computation

- julesh (@_julesh_)

Joachim Kock (May 11 2020 at 23:12):

It is indeed not so easy to trace the origin of the theory of polynomial functors. Joyal had them in the 1980s in connection with his discovery of combinatorial species and analytic functors, but did not really develop the theory because it is not rich enough to cover species and operads. Joyal himself claims that the notion should be attributed to Grothendieck :-) (I don't know exactly what this means...)

At the CT2010 in Genova, Peter Johnstone helped me draw a very interesting map of precursors to the notion of polynomial functors. I remember there were dozens of them, but unfortunately I don't have the map anymore :-( There are polynomial functors already in Arbib and Manes, but they did not see the pleasant representation of them in terms of maps E -> B.

For me the really cool feature of polynomial functors is their representability feature --- how they can be manipulated in terms of E -> B. The first printed evidence of this viewpoint that I am aware of is [Bisson-Joyal (1995): The Dyer-Lashof algebra in bordism (extended abstract), 1995]. That's some very grown-up algebraic topology they are up to, and their E -> B is really a covering space! They don't have time to talk much about polynomial functors, though. In logic, I believe the first explicit appearance is [Moerdijk-Palmgren (2000): Wellfounded trees in categories], where they show that Martin-Löf's W-types are initial algebras for polynomial endofunctors. The really nice many-variable formalism I believe was introduced by [Gambino-Hyland (2003): Wellfounded Trees and Dependent Polynomial Functors]. It is very curious though, that this shape of diagram,
I <- E -> B -> J was studied by Tambara already in 1993 --- yes! it is the same Tambara as in Tambara modules! Tambara essentially proved (without noticing it) that finite polynomial functors are the Lawvere theory theory for commutative semirings. See [Gambino-Kock (2013): Polynomial functors and polynomial monads] for this result.

Generally in [GK] we made a big effort to collect history and to unify the various developments, and in particular to bring all the container stuff into more mathematical language. I recommend that paper as a basic reference :-)

John Baez (May 11 2020 at 23:13):

Joachim wrote:

The first printed evidence of this viewpoint that I am aware of is [Bisson-Joyal (1995): The Dyer-Lashof algebra in bordism (extended abstract), 1995]. That's some very grown-up algebraic topology they are up to [...]

John Baez (May 11 2020 at 23:13):

Yeah, sounds like it! I hope I understand that stuff when I grow up!

Joachim Kock (May 11 2020 at 23:17):

Another big source of confusion is that there is something else which is also called polynomial functor: they are endofunctors F: Vect -> Vect such that for every pair of vector spaces the the map on hom spaces is given by polynomials. Such functors come up in representation theory, for example in connection with Schur functors. The appeared in Macdonalds book Symmetric Functions and Hall Polynomials, but in fact they were first studied in the 1950s (or even 1940s?) by Eilenberg and Mac Lane in connection with group cohomology. It's a very active area of research in representation theory and algebraic topology, for example in connection with functor cohomology.

The two theories of polynomial functors --- the one in cartesian contexts (such as logic and geometry), and the one in linear contexts -- do not seem to have so much in common at this point. For example, there are no representability features in the linear case. Adamek and Velebil show that the only pullback-preserving endofunctors of Vect are 'tensoring with a fixed vector space'.

Joachim Kock (May 11 2020 at 23:42):

Regarding my Notes on polynomial functors I should apologise for them being so messy and unprocessed.

I learned about polynomial functors when I was a postdoc with André Joyal in 2003-2004. We used polynomial functors to give a combinatorial version of the Baez-Dolan construction, and they have been a central topic in my research ever since.

Since there was not much literature available, I started to write notes at that time. By 2009, when the manuscript had over 400 pages, a huge mess (and containing mistakes), I put it on hold (that's its present state), because I realised I needed to upgrade everything from sets to groupoids, in order to cover the applications I had in mind in combinatorics and operad theory. Since then I have been learning about groupoids (and infinity-groupoids).

Groupoids really make a huge difference. With David Gepner and Rune Haugseng we showed that polynomial functors over groupoids are expressive enough to cover species, analytic functors, and operads. In fact with polynomial monads over infinity-groupoids we give a neat model for infinity-operads.

I think I am now in a position where I could go back to the manuscript and finish it -- with groupoids. But meanwhile, as you all know: each research project creates a number of new research projects, so it is not clear when I will actually come around to this.

However, the remarkable recent work of David Spivak and his collaborators is very motivating, and it is enjoyable to see how powerful the polynomial-functor toolbox is even in the case of one-variable polynomial functors over Set! Congratulations, David!

(Sorry for telling about myself. Maybe I should move this post to the present-yourself section.)

Nathanael Arkor (May 11 2020 at 23:49):

@Joachim Kock: one thing I was always curious about was how generalised species had an entire chapter dedicated to them in the table of contents for the notes (though sadly the chapter appears unwritten). Is this still a topic you would reserve a chapter for in the eventual updated book?

Joachim Kock (May 12 2020 at 00:01):

Jules Hedges said:

Still very much shooting from the hip here, but it sounds like how every lens $(a,b) \to (c,d)$ factors in the form $(a,b) \to (c,b) \to (c,d)$ which comes from the fact that lenses are fibred over sets, so that's a vertical and a cartesian morphism. I'm not sure it's the same sense of "cartesian" or not!

Yes, that's right, it's the same.

(=_=) (May 12 2020 at 00:04):

Joachim Kock said:

The two theories of polynomial functors --- the one in cartesian contexts (such as logic and geometry), and the one in linear contexts -- do not seem to have so much in common at this point.

I'm probably asking for too much, but I've always wondered how Goodwillie calculus can be related to these.

Joachim Kock (May 12 2020 at 00:20):

Nathanael Arkor said:

Joachim Kock: one thing I was always curious about was how generalised species had an entire chapter dedicated to them in the table of contents for the notes (though sadly the chapter appears unwritten). Is this still a topic you would reserve a chapter for in the eventual updated book?

I don't know if I would get around to this. The generalised species stuff (Fiore-Gambino-Hyland-Winskel) is really a different brand of polynomial functors (as you surely know) than the slice-category brand I mostly work with. The generalised-species stuff is about categories instead of groupoids -- very scary! It is closely related (is equal to?) the familial functors that Todd talked about in another thread, studied deeply by Mark Weber. And which Spivak uses for data migration. I would love to know more about that, but maybe it is not my highest priority right now -- and in any case my priorities tend to get overridden...

Joachim Kock (May 12 2020 at 00:21):

Rongmin Lu said:

I'm probably asking for too much, but I've always wondered how Goodwillie calculus can be related to these.

I think the Goodwillie calculus is more closely related to the Vect-based notion of polynomial functor that I mentioned a few posts back.