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: learning: questions

Topic: Quick question on polynomial functors

Keith Elliott Peterson (Mar 18 2024 at 11:35):

I understand that single variate polynomial functors (of sets) are coproducts of representables, as explained by the Poly book, but what exactly are the polynomial functors in the multivariate case?

Nathaniel Virgo (Mar 18 2024 at 12:34):

Multivariate polynomials!

Nathaniel Virgo (Mar 18 2024 at 12:35):

(At least I think so. I had the same question a while back and that was the conclusion I came to - I don't remember the details right now.)

Nathaniel Virgo (Mar 18 2024 at 12:40):

or if you were looking for the formal definition of a multivariate polynomial functor you can find it in Gambino and Kock's Polynomial functors and polynomial monads.

image.png

Nathaniel Virgo (Mar 18 2024 at 12:45):

So it's a tuple of $J$-many polynomials in $I$-many variables. I think you can think of it as a categorified version of a function $\R^i\to \R^j$ where each of the $j$ outputs is a polynomial function of the $i$ inputs.

Keith Elliott Peterson (Mar 18 2024 at 22:19):

No, I get that. I mean, what does $I$-many variables mean? $I$-indexed representables, ($y_i^X, i\in I$)?

Keith Elliott Peterson (Mar 18 2024 at 22:20):

Also, what are the lens-like objects that correspond to the multivariate case?

Nathaniel Virgo (Mar 19 2024 at 02:42):

So when we write, e.g. $y^2 + y$, it really stands for a functor $Y\mapsto Y^2 + Y$, functorial in $Y$. Given that, we can consider writing something like $(x^2 + 2xy + z, 3z)$, which stands for a functor $(X,Y,Z) \mapsto (X^2 + 2\times X\times Y + Z, 3\times Z)$, with type $\mathbf{Set}^3 \to \mathbf{Set}^2$. The definition above is just extending this idea to polynomials with set-many terms (and set-many dimensions etc.) instead of only finitely many.

Nathaniel Virgo (Mar 19 2024 at 02:45):

I don't know how to characterise natural transformations between these as something lens-like, but it's an interesting thing to think about.

Keith Elliott Peterson (Mar 19 2024 at 07:07):

Nathaniel Virgo said:

I don't know how to characterise natural transformations between these as something lens-like, but it's an interesting thing to think about.

@David Spivak, would you happen to know?

David Spivak (Mar 19 2024 at 17:12):

Comonoids in $(Poly, y, \lhd)$ are categories, but among them are the discrete categories. For a set A, the discrete category on A is a comonoid of the form Ay. A multivariate polynomial with I-many variables is a bicomodule of the form y <|------<| Iy. If you want J-many polynomials in I-many variables, that's equivalent to a bicomodule of the form Jy <|--------<| Iy.

As mentioned above, it's also a map Set/I ---> Set/J. And a map between two such things is indeed a natural transformation. It is certainly lens like: a bicomodule as above is just a (one-variable) polynomial p equipped with maps $Jy\lhd p\leftarrow p\to p\lhd Iy$, and a map of such bicomodules (a natural transformation) is a map of (one-variable) polynomial functors making some diagrams commute. Maps of polynomials are lens-like.

Does that help?

Kevin Carlson (aka Arlin) (Mar 19 2024 at 18:22):

In case you're not up on the whole bicomodule story, another way to think about this is that a multivariate polynomial in some $\mathrm{Set}$ is represented by a diagram $I\leftarrow E\to B \to J$; if the arrows are $s,f,t$ from left to right then the corresponding functor $\mathrm{Set}/I\to mathrm{Set}/J$ is given by $\Sigma_t\circ \Pi_f\circ \Delta_s,$ where $\Sigma,\Pi,\Delta$ are members of the adjoint triple defining $\mathrm{Set}$'s local cartesian closure. Then you can produce maps between polynomial functors from maps between their presenting diagrams in two ways:

Kevin Carlson (aka Arlin) (Mar 19 2024 at 18:22):

1. An ordinary natural transformation $(I\leftarrow E\to B\to J)\to (I\leftarrow E'\to B'\to J)$ of diagrams that is identity on $I,J$ and cartesian on $E,B$:

Screenshot-2024-03-19-at-10.55.24AM.png

2. A lensy natural transformation that is also identity on $B$ but goes backwards on $E,E'$:

Screenshot-2024-03-19-at-10.57.01AM.png

Kevin Carlson (aka Arlin) (Mar 19 2024 at 18:23):

You can compose these two kinds of morphisms to get arbitrary natural transformations. It's enough to see this for the case that $J=\{*\}.$ Then a polynomial functor $\mathrm{Set}/I\to \mathrm{Set}$ is given by a sum $p=\sum_{j\in J}\sum_{b\in t^{-1}(j)}\prod_{e\in f^{-1}(b)} y_{s(e)},$ where for $i\in I,$ the variable $y_i:\mathrm{Set}/I\to\mathrm{Set}$ is represented by $\{i\}\to I.$ Let's now assume $J$ is a point since maps of $J$-indexed families of polynomials are just families of maps of polynomials.

Kevin Carlson (aka Arlin) (Mar 19 2024 at 18:23):

Polynomials of the form $\prod_{e\in f^{-1}(b)} y_{s(e)}$ are representable, being represented by the restriction of $s:E\to I$ to $f^{-1}(b)$, so maps out of them commute with coproducts. Therefore most of the work in computing maps between polynomials comes in computing maps $\prod_{x\in X}y_{s(x)}\to \prod_{x'\in X'}y_{s'(x')}$ where $s,s':X,X'\to I.$ Such a map is precisely a morphism $s'\to s$ in $\mathrm{Set}/I$ or a map $X'\to X$ over $I$, by the Yoneda lemma.

Kevin Carlson (aka Arlin) (Mar 19 2024 at 18:23):

In other words, to get a map $p\to p'$ of polynomials $\mathrm{Set}/I\to \mathrm{Set}$, for every "position" $b\in B$ you need to choose a position $b'\in B'$ and a map $\prod_{e\in f^{-1}(b)} y_{s(e)}\to \prod_{e'\in f'^{-1}(b')} y_{s'(e')},$ which is to say a map $f'^{-1}(b')\to f^{-1}(b)$ over $I.$ This is almost exactly the same as the lensy notion of morphism of univariant polynomials you're used to--a forward map on positions and a backward map on directions, in David's terminology--except that the direction sets are colored by elements of $I$ and the direction maps must respect that.

Kevin Carlson (aka Arlin) (Mar 19 2024 at 18:23):

This is a way of seeing what David was getting at with the bicomodule story: a multivariate polynomials is just extra structure on a univariate polynomial, since you get a univariate polynomial by just composing $s$ and $t$ with the projections to a one-point set. Therefore it "must" be the case that a map of multivariate polynomials is just a special kind of map of univariate polynomials, as we've seen above.

Kevin Carlson (aka Arlin) (Mar 19 2024 at 18:23):

Interestingly, it's not true that every natural transformation of polynomial functors comes from a lensy diagram if you generalize past the case $\mathrm{Set}.$ Kock and Gambino observe that the nontrivial endomorphism of the identity endofunctor of $\mathrm{Set}^{\mathbb Z/2\mathbb Z}$, for instance, doesn't arise in this way. So there be dragons in the direction of trying to think about general polynomial endofunctor maps in terms of lenses. I don't know whether we know much about this story all in all.