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: combinatorics

Topic: Lambert W species interpretation

Tim Campion (Oct 23 2021 at 16:25):

The Lambert W function is defined by the functional equation $W(z)e^{W(z)} = z$. It has multiple branches, yadda yadda yadda.

One of those branches has a very interesting Taylor series expansion, $W(z) = \sum_{n \geq 1} \frac{(-1)^{n-1}}{n!} n^{n-1} z^n$. I'd like an interpretation in terms of combinatorial species.

First let's get rid of the minus signs. Let $w(z):= -W(-z)$ be defined by the functional equation $w(z)e^{-w(z)} = z$ (this quantity seems to be what actually comes up whenever I've wanted to use the Lambert $W$ function in my life, so I'm encouraged by the need to do this transformation.) We get $w(z) = \sum_{n \geq 1} \frac{n^{n-1}}{n!} z^n$.

This looks pretty promising -- we appear to be looking at some kind of species $\mathcal W$ where a $\mathcal W$-structure on a set $X$ with $n$ elements is a function from a set with $(n-1)$ elements to $X$, or something like that? I'm a bit confused, though:

1. How exactly should a $\Sigma_n$ action on functions $(n-1) \to n$ be defined?
2. How does this connect to the functional equation $w(z)e^{-w(z)} =z$, particulary with an eye toward the species interpretation of $e^z$?

Reid Barton (Oct 23 2021 at 16:27):

It's been a long time but I seem to recall generatingfunctionology has a discussion of the Lambert W function, have you looked in there?

Tim Campion (Oct 23 2021 at 16:28):

I haven't tried anywhere, I decided to lazily try the internet first :)

Tim Campion (Oct 23 2021 at 16:28):

Yeah, I haven't looked at generatingfunctionology in awhile

Tim Campion (Oct 23 2021 at 16:28):

it's a fun book though

Tim Campion (Oct 23 2021 at 16:33):

Wilf talks about something called a Lambert series more generally (in exercise 31 to Ch. 2 on p. 70 of gfology)

Tim Campion (Oct 23 2021 at 16:36):

He says that that a "Lambert series" is one of the form $\sum a_n \frac{x^n}{1-x^n}$ and says that they're hard in general. But isn't this basically what you want Stirling numbers for?

Tim Campion (Oct 23 2021 at 16:40):

Another way to write the functional equation is $w(z) = z e^{w(z)}$ (where again I'm using $w(z) = -W(-z)$).

Tim Campion (Oct 23 2021 at 16:43):

How about this: we have $w'(z) = \sum_{n \geq 1} \frac{n^{n-1}}{(n-1)!} z^{n-1} = \sum_{m \geq 0} \frac {(m+1)^m}{m!} z^m$. That looks promising...

Tim Campion (Oct 23 2021 at 16:46):

So $w'(z)$ corresponds to the species $\mathcal W'$ where a $\mathcal W'$-structure on $X$ is just a map $X \to X+1$.

Tim Campion (Oct 23 2021 at 16:47):

The species $\mathcal W'$ actually comes with a natural species structure: the $\Sigma_X$ action on $Map(X,X+1)$ conjugates by the automorphism of $X$, fixing the new point of $X+1$.

Tim Campion (Oct 23 2021 at 16:48):

But from this perspective, it still seems a bit mysterious that the integral of $w'(z)$ should still have integral derivatives.

Tim Campion (Oct 23 2021 at 16:58):

Oh wait!

Tim Campion (Oct 23 2021 at 16:58):

The functional equation $w(z) = z e^{w(z)}$ is well-known.

Tim Campion (Oct 23 2021 at 16:59):

It characterizes the species of rooted trees.

Tim Campion (Oct 23 2021 at 17:01):

It says that the structure of a rooted tree on a set $X$ is given by choosing a point of $X$ to be the root (that's the $z$ factor), partitioning the remainder of $X$ somehow (that's the exponential), and putting the structure of a rooted tree on each member of the partition (that's the $w(z)$ in the exponential).

Tim Campion (Oct 23 2021 at 17:04):

Ok, and then the formula $w(z) = \sum_{n \geq 1} \frac{n^{n-1}}{n!} z^{n}$ says that in order to construct a rooted tree structure on $X$, what you do is you write down a partially-defined endomorphism of $X$ -- defined at all but one point. The endomorphism is the "predecessor" function for the tree structure; it is undefined only at the root point. EDIT: There is something wrong here -- the predecessor function can't be an arbitrary endofunction...

Tim Campion (Oct 23 2021 at 17:05):

I feel like there may have been an nCafe discussion of this at some point, but I did not remember that the resulting generating function is basically the Lambert W function.

Tim Campion (Oct 23 2021 at 17:07):

Maybe it's only in the intervening time that I became sensitive to the appearance of Lambert $W$

Tim Campion (Oct 23 2021 at 17:16):

Tim Campion said:

Ok, and then the formula $w(z) = \sum_{n \geq 1} \frac{n^{n-1}}{n!} z^{n}$ says that in order to construct a rooted tree structure on $X$, what you do is you write down a partially-defined endomorphism of $X$ -- defined at all but one point. The endomorphism is the "predecessor" function for the tree structure; it is undefined only at the root point. EDIT: There is something wrong here -- the predecessor function can't be an arbitrary endofunction...

Okay, I found Tom Leinster's post describing Joyal's proof of Cayley's formula, which gets this right. Interesting that it involves the identification of the species for linear orders and the species for permutations (which is non-canonical)

John Baez (Oct 25 2021 at 01:09):

Let me know how this works out... or write an updated description of what you're stuck on. I love species, but I haven't thought about the Lambert W function as the generating function of a (super)species.

Tim Campion (Oct 25 2021 at 12:21):

John Baez said:

Let me know how this works out... or write an updated description of what you're stuck on. I love species, but I haven't thought about the Lambert W function as the generating function of a (super)species.

So I think I was satisfied with the resolution here. Let me summarize (see the last bullet below for a lingering, more general question, about "solving species equations" in general):

• Define $w(z) = -W(-z)$ (to get rid of the minus signs in the Taylor series).

• This gives us a functional equation
  $(1) \qquad w(z) = z e^{w(z)}$.

• This functional equation $(1)$ categorifies to a "species equation" which exactly says that $w(z)$ is the exponential generating function for the species of rooted trees.

I think this species equation is well-known (it even appears as an example illustrating composition of species, buried in the wikipedia page for Combinatorial Species, where the species for rooted trees is called "$Ar$" -- as that's a French abbreviation, I suspect this example appears already in Joyal's original paper). But here's a rundown: if $X$ is a finite set, then a rooted tree structure on $X$ (corresponding to the $w(z)$ on the LHS of $(1)$) is given by choosing a basepoint (that's the $z$ factor on the RHS of $(1)$), partitioning the rest (that's the exponential on the RHS of $(1)$), and then choosing a rooted tree structure on each member of the partition (that's the $w(z)$ on the RHS of $(1)$).

• I don't know a direct argument which allows us to compute that

$(2) \qquad w(z) = \sum_{n \geq 1} \frac{n^{n-1}}{n!} z^n$.

But apparently it's a famous theorem of Cayley that the number of unrooted trees on a labeled set of order $n$ is $n^{n-2}$. You can deduce $(2)$ from Cayley's formula, of course, simply by noting that there are $n$ possible choices of "root" for each unrooted tree on $n$ elements. And in turn, Cayley's theorem has a beautiful "species-inspired" proof given by Joyal, again in his original paper on species. Everything I know about this I learned from Tom Leinster's lovely blog post on the topic.

(Here's what I learned from Tom's blog post: Joyal's proof actually proceeds by counting bipointed trees $T$ (where the two chosen points $A$ and $B$ are allowed to be equal). To see that there are $n^n$ of these, Joyal gives a bijection to the set of endofunctions of $X$ as follows. Observe that there is a unique path $[A,B]$ in $T$ from $A$ to $B$, specified by a total ordering of the vertices of $[A,B]$. The rest of the tree structure $T$ on $X$ amounts to the choice of a partial endofunction $P$ of $X$, which tells each vertex not in $[A,B]$ how to move one step closer to $[A,B]$. Now Joyal observes that total orderings on $[A,B]$ are in (noncanonical) bijection with permutations of $[A,B]$. Swapping the former for the latter, we now how the data to promote $P$ to an endofunction of all of $X$, and this correspondence between bipointed trees and endofunctions is bijective -- though not $\Sigma_n$-equivariant.)

• Earlier I referred to "the non-canonical identification of the species for linear orders and the species for permutations". That was an incorrect reference -- it's worse than that. Really the species $Lin$ of linear orders and the species of $Exp$ of permutations have the same generating function, but are not isomorphic species at all. One way to think about it is that $Exp(X)$ is the set $\Sigma_X$ with its natural conjugation action, whereas $Lin(X)$ is the set $\Sigma_X$ with its action by left multiplication. These $\Sigma_X$-sets are not isomorphic -- the latter, but not the former, is a $\Sigma_X$-torsor -- it has a unique orbit, which is free. The former has an orbit for every cycle type / partition of $|X|$, and they are not free.

• I wonder if there is another species categorifying the generating function $w(z)$ which is a sub-species of the species of endofunctions? Something like "partial endofunctions defined at all but one point", except that's not quite right unless you can say which point... This would be a natural species with the same generating function which is not isomorphic as a species, much as Joyal / Cayley show us that the species of bipointed trees and the species of endofunctions have the same generating function but are not isomorphic.

• I guess one thing I'd still like to understand better is the following: I'm a bit hazy on the art of "solving species equations" in general. If I have a functional equation of generating functions like $(1)$, then I suppose I could say something about the set of generating functions satisfying the equations. For instance, I could prove by inducting through the coefficients of the Taylor series that $(2)$ is the unique solution to $(1)$. But if I interpret $(1)$ as a species equation, I suddenly get a bit worried -- sitting here right now I would not assert with 100% confidence that the species of rooted trees is the unique species satisfying $(1)$ (EDIT: wait -- do we even expect this??) -- I would have to really think about how to inductively nail down all the $\Sigma_n$ actions. And of course, the sense of "unique" is more flexible -- does the species of rooted trees have any automorphisms, for instance?

Tim Campion (Oct 25 2021 at 12:39):

I don't know why my "summary" is the longest post in this thread :upside_down:

John Baez (Oct 25 2021 at 17:22):

Because you actually explained what was going on? Thanks!

John Baez (Oct 25 2021 at 17:24):

The Big Red Book of Species has a lot on solving differential equations for species, but I don't know if they talk about whether there's a unique-up-to-iso species obeying something like

$F(z) \cong P(z) F(z)$

where $P$ is a known species and you're trying to solve this for $F$.

John Baez (Oct 25 2021 at 17:25):

I imagine people who know a lot about "initial algebras of endofunctors" might know, not a unique, but at least an initial solution of "fixed point equations" of this sort, in the category of species.

John Baez (Oct 25 2021 at 17:27):

Btw, the Big Red Book of Species is actually called Combinatorial Species and Tree-like Structures. That's just my personal name for it.

Tim Campion (Oct 25 2021 at 17:40):

Chapter 3 of that book appears to be all about solving functional equations in species, thanks!

Tim Campion (Oct 25 2021 at 17:42):

In particular, apparently they show that a functional equation of the form $Y = X \times R(Y)$, where $R$ is a species, has a unique solution species $Y$, up to unique canonical isomorphism!

Tim Campion (Oct 25 2021 at 17:43):

And there's an Implicit Species Theorem, cool!

Tim Campion (Oct 25 2021 at 17:49):

The implicit species theorem is very nice -- it says that if $H(X,Y)$ is a "2-sort species" (I think I can guess what that means...), and if $H(0,0) = \partial_2 H(0,0) = 0$, then there exists a species $A$, unique up to unique canonical isomorphism, such that $A \cong H(X,A)$ and $A(0) = 0$.

Tim Campion (Oct 25 2021 at 17:49):

which is weird -- why can't that species $A$ have automorphisms?

Tim Campion (Oct 25 2021 at 17:49):

maybe they mean unique up to canonical isomorphism?

Tim Campion (Oct 25 2021 at 17:50):

Oh yes they do.

Tim Campion (Oct 25 2021 at 17:50):

That's even what they say.

Jacques Carette (Oct 26 2021 at 13:23):

Note that that condition on $H$ can be loosened, see

C. Pivoteau, B. Salvy, and M. Soria, “Algorithms for Combinatorial Structures: Well-founded systems and Newton iterations,” Journal of Combinatorial Theory, Series A, vol. 119, pp. 1711–1773, 2012.

where there's also a non-paywalled version.